package brn.swans.route;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.HashSet;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Set;

import jist.runtime.JistAPI;
import jist.runtime.Main;
import jist.runtime.Util;
import jist.swans.Constants;
import jist.swans.mac.MacAddress;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.net.NetAddress;
import jist.swans.net.NetMessage;

import org.apache.commons.collections.BinaryHeap;
import org.apache.log4j.Logger;

import brn.sim.builder.NetBuilder.TxDOR;
import brn.swans.mac.MacTxDOR;
import brn.swans.route.cs.CandidateSelection;
import brn.swans.route.cs.CandidateSelection.NetAddressWithMetric;
import brn.swans.route.metric.ArpTableInterface;
import brn.swans.route.metric.ETTMetric;
import brn.swans.route.metric.EaxMetric;
import brn.swans.route.metric.LinkStat;
import brn.swans.route.metric.LinkTable;
import brn.swans.route.metric.RouteMetricInterface;
import brn.swans.route.metric.ETTMetric.EttData;
import brn.swans.route.metric.RouteMetricInterface.NoLinkExistsException;

@SuppressWarnings("unchecked")
public class RouteDsrTxDOR extends RouteDsrBrn implements RouteDsrTxDORInterface {

  // ////////////////////////////////////////////////
  // constants
  //

  private static Logger log = Logger.getLogger(RouteDsrTxDOR.class.getName());


  // ////////////////////////////////////////////////
  // nested classes
  //

  private static class PacketId {
    protected int id;
    protected NetAddress src;

    public PacketId(NetAddress src, int id) {
      this.src = src;
      this.id = id;
    }

    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      final PacketId that = (PacketId) o;

      if (id != that.id) return false;
      if (!src.equals(that.src)) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = id;
      result = 29 * result + src.hashCode();
      return result;
    }

    public String toString() {
      return "[" + src + "/" + id + "]";
    }
  }

  public class DuplicateTable {

    /**
     * Keep track of ExOR routed data packets
     */
    private Set dataPacketTable;

    public DuplicateTable() {
      dataPacketTable = new HashSet();
    }

    /**
     * Checks if we have recently forwarded this data packet with the given seqNum
     * coming from the given source.
     *
     * @param src the source address of the data packet
     * @param id  the ID number
     * @return whether the given data packet has been forwarded recently.
     */
    private boolean seenDataPacketBefore(NetAddress src, int id) {
      PacketId entry = new PacketId(src, id);

      return (dataPacketTable.contains(entry));
    }

    /**
     * Enters a new Data packet ID number into the ...
     *
     * @param src the address of the originator of the data packet
     * @param id  the ID number
     */
    protected void addDataPacketId(NetAddress src, int id) {
      // Otherwise add this id to the table
      dataPacketTable.add(new PacketId(src, id));
    }

    protected void addDataPacketId(RouteDsrBrnMsg msg, NetAddress src) {
      RouteDsrBrnMsg.Option optId = msg.getOption(RouteDsrBrnMsg.OPT_ID);
      int id = ((RouteDsrBrnMsg.OptionId)optId).getId();
      addDataPacketId(src, id);
    }

    public boolean isDuplicate(RouteDsrBrnMsg msg, NetAddress src) {
      RouteDsrBrnMsg.Option optId = msg.getOption(RouteDsrBrnMsg.OPT_ID);
      int id = ((RouteDsrBrnMsg.OptionId)optId).getId();
      boolean seen = seenDataPacketBefore(src, id);

      log.info(localAddr + "(" + JistAPI.getTime() + "): received packet (" +
          src + "," + id + ").");
      if (seen) {
        log.info(localAddr + "(" + JistAPI.getTime() + "): received "
                + "duplicate packet (" + src + "," + id + "); drop it.");
      }

      return seen;
    }

    public void remove(RouteDsrBrnMsg msg, NetAddress src) {
      RouteDsrBrnMsg.Option optId = msg.getOption(RouteDsrBrnMsg.OPT_ID);
      int id = ((RouteDsrBrnMsg.OptionId)optId).getId();
      dataPacketTable.remove(new PacketId(src, id));
    }

  }

  public static class CsWithMetric extends NetAddressWithMetric {
    public List cs;
    public int nextCandIdx;
    public CsWithMetric(List cs, int metric, int metricToSrc, int nextCandIdx) {
      super(null, metric, metricToSrc);
      this.cs = cs;
      this.nextCandIdx = nextCandIdx;
    }
    public String toString() {
      return "{" + cs + "," + metricToSrc + "," + metric + "}";
    }
    public int hashCode() {
      final int PRIME = 31;
      int result = super.hashCode();
      result = PRIME * result + ((cs == null) ? 0 : cs.hashCode());
      return result;
    }
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (!super.equals(obj))
        return false;
      if (getClass() != obj.getClass())
        return false;
      final CsWithMetric other = (CsWithMetric) obj;
      if (cs == null) {
        if (other.cs != null)
          return false;
      } else if (!cs.equals(other.cs))
        return false;
      return true;
    }
  }

  /**
   * Candidate selection for tx dor.
   *
   * Idea: candidates must have a good communication link between them,
   *  otherwise the passive story won't work. General idea is to start with a
   *  single candidate and take other candidates step by step, so that they make
   *  up something like a clique. This step is done for all neighbors until the
   *  candidate set is full or the metric gets worse.
   *
   *  A - B ... D
   *    - C ...
   *
   *  A wants to send to D via B or C. The metric of the link AB is b (c for AC)
   *  and the route metric BD is b' (c' for CD). The link metric between B and
   *  C is a.
   *
   *  M(B) = b + b'  (= ETX)
   *  M(B,C) = b c / (b+c-1) + min(b', c') + max(b', c') * (1 - 1/a)
   *
   *  Idea is that both b' and c' will not differ that much, so we simply
   *  average. The metric of the combined link A - B,C is derived from a
   *  consideration of link delivery probabilities:
   *
   * p_b^f p_c^f ( p_c^r + p_b^r - p_c^r p_b^r )
   *   + np_b^f p_c^f p_c^r  + np_c^f p_b^f p_b^r
   *   = 1/c + 1/b - 1/bc
   *
   *  p_c^f p_c^r = 1/c
   *  p_b^f p_b^r = 1/b
   *
   *  The scaling factor (2 - 1/a) is due to the observation if the link between
   *  both candidates is bad, both will forward the packet. If the final
   *  destination is within the candidate set, the link between all candidates
   *  is assumed non-existant.
   *
   * TODO candidate selection V2:
   * node-distance based candidate set: (center candidate, etx distance)
   * all nodes with a distance smaller than the given to the center candidate
   * are additional candidates.
   * @author kurth
   */
  protected static class TxDORSelection extends CandidateSelection {

    /** constant for an non-existing link */
    final static int INVALID_ROUTE_METRIC = 9999;

    protected CandMetricEvent candMetricEvent;
    protected int nodeId;

    /** max number of candidtes to calculate and use simulataneously */
    protected int noCandSets = 2;

    /** current cs index */
    private int idx;

    protected NetAddress dst;
    protected NetAddress src;
    protected BinaryHeap heap;
    protected int maxSize;
    protected CsWithMetric best;
    protected int bestMetric;
    protected PriorityQueue listBest;
    protected Comparator bestComperator;

    public TxDORSelection(int csSize, NetAddress localAddr,
        RouteMetricInterface routeMetric, int metricDelta, int maxMetricForNeighbor) {
      super(csSize, localAddr, routeMetric);
      this.nodeId = localAddr.getId();
      candMetricEvent = new CandMetricEvent();
      this.metricDelta = metricDelta;
      this.maxMetricForNeighbor = maxMetricForNeighbor;
      this.heap = new BinaryHeap();
      this.bestComperator = new Comparator() {
        public int compare(Object arg0, Object arg1) {
          CsWithMetric a = (CsWithMetric) arg0;
          CsWithMetric b = (CsWithMetric) arg1;
          return b.metric + b.metricToSrc - a.metric - a.metricToSrc;
        }
      };
    }

    /**
     * @return the noCandSets
     */
    public int getNoCandSets() {
      return noCandSets;
    }

    /**
     * @param noCandSets the noCandSets to set
     */
    public void setNoCandSets(int noCandSets) {
      this.noCandSets = noCandSets;
    }

    /**
     * @return the metricDelta
     */
    public int getMetricDelta() {
      return metricDelta;
    }


    /**
     * @param metricDelta the metricDelta to set
     */
    public void setMetricDelta(int metricDelta) {
      this.metricDelta = metricDelta;
    }

    protected int getInvalidRouteMetric() {
      return INVALID_ROUTE_METRIC;
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#getCachedCandidates(brn.swans.route.cs.CandidateSelection.CandidateCacheEntry)
     */
    protected List getCachedCandidates(CandidateCacheEntry entry) {
      List candidates = entry.getCandidates();
      if (null == candidates || candidates.size() == 0)
        return null;

      idx = (idx+1) % candidates.size();
      return (List)candidates.get(idx);
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#select(jist.swans.net.NetAddress, java.util.List)
     */
    protected List select(NetAddress src, NetAddress dst, List candidates) {
      this.idx = -1; // NOTE it is incremented first!!
      this.heap.clear();
      this.dst = dst;
      this.src = src;
      this.maxSize = Math.min(candidates.size(), cSetSize);
      this.listBest = new PriorityQueue(this.noCandSets, bestComperator);
      this.best = null;
      this.bestMetric = Integer.MAX_VALUE;

      if (0 == candidates.size()) {
        log.error(this.localAddr + "(" + JistAPI.getTime() + "): no route found to "
            + dst + ", candidate set noErrors");
        return null;
      }

      // sort all candidates according to their metrics
      Collections.sort(candidates);

      if (log.isInfoEnabled())
        log.info(this + "(" + JistAPI.getTime() + "): searching candidates from "
            + src + " to " + dst + " with cand " + candidates);

      // expand whole search space
      CsWithMetric currNode = new CsWithMetric(new ArrayList(), 0, 0, 0);
      expandCandidate(currNode, candidates);

      while(!heap.isEmpty()) {
        currNode = (CsWithMetric) heap.remove();

        // the metricToDst fields could only increase with additional candidates
        // if the metricToDst is already above the best metric (sum), exit
        // remember that the heap is sorted according to metricToDst
        if (this.bestMetric < currNode.metric) {
          break;
        }

        expandCandidate(currNode, candidates);
      }
      this.heap.clear();

      if (null == this.best || this.best.cs == null || this.best.cs.size() <= 0) {
        log.error(this + "(" + JistAPI.getTime() + "): no cs found with candidates "
            + candidates + " for dst " + dst);
        return new ArrayList();
      }

      if (candMetricEvent.isActive())
        candMetricEvent.handle(nodeId, best.cs, best.metricToSrc, best.metric);

      if (log.isInfoEnabled())
        log.info(this + "(" + JistAPI.getTime() + "): using cs " + this.best);

      // if the final dst is within a cs, use only one cs!
      ArrayList ret = new ArrayList(this.listBest.size());
      for (int j = 0; j < best.cs.size(); j++) {
        NetAddressWithMetric nawm = (NetAddressWithMetric) best.cs.get(j);
        if (nawm.ip.equals(this.dst)) {
          ret.add(convertToIpList(best.cs));
          return ret;
        }
      }

      while(!this.listBest.isEmpty())
        ret.add(convertToIpList(((CsWithMetric)this.listBest.remove()).cs));

      return ret;
    }


    /**
     * Recursive expansion of the whole search space.
     *
     * @param nodeToExpand current candidate selection
     * @param candidates list of avaliable candidates
     * return list of best candidates
     */
    private void expandCandidate(CsWithMetric nodeToExpand, List candidates) {
      List tmp = new ArrayList(nodeToExpand.cs);

      // go through all candidates and try to find the best candidate set
      tmp.add(candidates.get(0));
      int currCsSize = tmp.size();
      for (int i = nodeToExpand.nextCandIdx; i < candidates.size(); i++) {
        NetAddressWithMetric currCand = (NetAddressWithMetric) candidates.get(i);
        CsWithMetric newCandidate = constructNewCandidate(nodeToExpand,
            tmp, i, currCand);

        if (currCsSize < maxSize)
          heap.add(newCandidate);

        listBest.add(newCandidate);
        if (listBest.size() > noCandSets)
          listBest.remove();

        if (bestMetric > newCandidate.metric + newCandidate.metricToSrc) {
          best = newCandidate;
          bestMetric = newCandidate.metric + newCandidate.metricToSrc;
        }
      }
    }

    /**
     * Construct new expanded node.
     *
     * @param nodeToExpand
     * @param tmp
     * @param currCandIdx
     * @param currCand
     * @return new expanded node
     */
    protected CsWithMetric constructNewCandidate(CsWithMetric nodeToExpand,
        List tmp, int currCandIdx, NetAddressWithMetric currCand) {
      int currCsSize = tmp.size();
      tmp.set(currCsSize-1, currCand);

      int newMetricToSrc = 0;
      int newMetricToDst = 0;
      if (currCsSize == 1) {
        newMetricToSrc = currCand.metricToSrc;
        newMetricToDst = currCand.metric;
      }
      else if (currCsSize > 1) {
        newMetricToSrc = getMetricToSrc(nodeToExpand, currCand);
        newMetricToDst = getMetricToDst(currCsSize-1, nodeToExpand.metric, tmp, currCand);
      }

      return new CsWithMetric(new ArrayList(tmp),
          newMetricToDst, newMetricToSrc, currCandIdx+1);
    }

    protected int getMetricToDst(int curr, int metricToDst, List cs,
        NetAddressWithMetric currCand) {
      double candLink = getInterCandidateMetric(curr, cs, currCand);

      // determine new metric towards the destination
//      double newMetricToDst = (currCand.metric*curr + metricToDst) / (curr+1)
//      * (2. - 100./candLink);

      int min = Math.min(currCand.metric, metricToDst);
      int max = Math.max(currCand.metric, metricToDst);
//      if (max < currCand.metricToSrc)
//        max = currCand.metricToSrc;
      // use the min as baseline to make the metric more robust and avoid
      // frequent, very small variations
      double newMetricToDst = min
          + max * (1. - 100./candLink);

      return (int)newMetricToDst;
    }

    /**
     * Estimate the new metric to src from two individual source metrics.
     *
     * @param candidates
     * @param newCandidate
     * @return the new metric to source of the combined candidate set.
     */
    protected int getMetricToSrc(CsWithMetric candidates, NetAddressWithMetric newCandidate) {
      // determine new metric towards the source
      int newMetricToSrc = newCandidate.metricToSrc * candidates.metricToSrc
          / (newCandidate.metricToSrc + candidates.metricToSrc - 100);
      return newMetricToSrc;
    }

    protected double getInterCandidateMetric(int curr, List cs, NetAddressWithMetric currCand) {
      // if current node equals destination it is the last hop
      boolean lastHop = dst.equals(currCand.ip);

      // average of all link metrics between current and previous candidates
      double candLink = .0;
      for (int i = 0; i < curr && lastHop == false; i++) {
        NetAddressWithMetric otherCand = (NetAddressWithMetric) cs.get(i);

        lastHop = dst.equals(otherCand.ip);
        try {
          candLink += this.routeMetric.getLinkMetric(otherCand.ip, currCand.ip);
        } catch (NoLinkExistsException e) {
          return getInvalidRouteMetric();
        }
      }
      candLink = (!lastHop ? candLink / curr : getInvalidRouteMetric());
      return candLink;
    }
  }

  /**
   * Conservative candidate selection: the inter-candidate metric is always the
   * max of all possible links. Idea: prevent duplicates.
   *
   * simulations show a very high number of duplicates. the inter-candidate
   * link has to be extimated more conservative.
   *
   * @author kurth
   */
  protected static class TxDORSelConservative extends TxDORSelection {

    public TxDORSelConservative(int csSize, NetAddress localAddr,
        RouteMetricInterface routeMetric, int metricDelta, int maxMetricForNeighbor) {
      super(csSize, localAddr, routeMetric, metricDelta, maxMetricForNeighbor);
    }

    /* (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#getInterCandidateMetric(int, java.util.List, brn.swans.route.cs.CandidateSelection.NetAddressWithMetric)
     */
    protected double getInterCandidateMetric(int curr, List cs, NetAddressWithMetric currCand) {
      // if current node equals destination it is the last hop
      boolean lastHop = dst.equals(currCand.ip);

      // get the max of all link metrics between current and previous candidates
      double candLink = .0;
      for (int i = 0; i < curr && lastHop == false; i++) {
        NetAddressWithMetric otherCand = (NetAddressWithMetric) cs.get(i);

        lastHop = dst.equals(otherCand.ip);
        try {
          candLink = Math.max(candLink,
              routeMetric.getLinkMetric(otherCand.ip, currCand.ip));
        } catch (NoLinkExistsException e) {
          return getInvalidRouteMetric();
        }
      }
      candLink = (!lastHop ? candLink : getInvalidRouteMetric());
      return candLink;
    }
  }

  /**
   * Candidate selection when using a robust control rate for rts/cts/ack
   *
   * using a robust control rate the candidates metric to the source gets better
   * because acks are sent at a more robust control rate:
   *
   * etx' / etx = etx^-.5 / (DeltaSNR * .025  + etx^-.5)
   *
   * the inter-candidate link metric only considers the control rates, not the
   * (higher) data rates:
   *
   * etx'' / etx = etx^-1 / (DeltaSNR * .025 + etx^-.5)^2
   *
   * @author kurth
   */
  protected static class TxDORSelRobustControlRate extends TxDORSelection {

    /** SNR difference between data and control bit rate */
    protected double deltaSNR;

    /**
     * Gain in PDR per dBm SNR
     * shadowing sigma 4 -> .06, 8 -> .04, 12 ->  .025
     */
    public final double pdrGainPerSnr = .025;

    protected double deltaPDR;

    /** upper bound for neighbors on the first hop */
    protected int firstHopMetric = 250;

    public TxDORSelRobustControlRate(int csSize, NetAddress localAddr,
        RouteMetricInterface routeMetric, int metricDelta, int maxMetricForNeighbor,
        double deltaSNR) {
      super(csSize, localAddr, routeMetric, metricDelta, maxMetricForNeighbor);
      this.deltaSNR = deltaSNR;
      this.deltaPDR = this.deltaSNR * pdrGainPerSnr;
    }

    /* (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#select(jist.swans.net.NetAddress, jist.swans.net.NetAddress, java.util.List)
     */
    protected List select(NetAddress src, NetAddress dst, List candidates) {
      /*
       * TODO Idea: if the distance to the final destination is big (metric
       * is much larger than metricToSrc) try to quickly spread out using
       * only very good candidates and max. number of candidates (-> small
       * backoff and retries). Instead if we are near the final destination
       * try to concentrate the flow.
       */
      boolean firstHop = src.equals(this.msg.getSrc());
      Iterator iter = candidates.iterator();
      while (iter.hasNext()) {
        NetAddressWithMetric metric = (NetAddressWithMetric) iter.next();
        if (firstHop && metric.metricToSrc > firstHopMetric) {
          iter.remove();
          continue;
        }

        // scale the candidates metric to the source according to the snr
        // difference do not use this on the first hop
        double delivProb = 10. / Math.sqrt(metric.metricToSrc);
        metric.metricToSrc = Math.max(100,
          (int) (metric.metricToSrc * delivProb / (deltaPDR + delivProb)));
      }

      return super.select(src, dst, candidates);
    }

    /* (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#getInterCandidateMetric(int, java.util.List, brn.swans.route.cs.CandidateSelection.NetAddressWithMetric)
     */
    protected double getInterCandidateMetric(int curr, List cs, NetAddressWithMetric currCand) {
      double metric = super.getInterCandidateMetric(curr, cs, currCand);

      double delivProb = 10. / Math.sqrt(metric);
      metric = Math.max(100.,
          100. / (delivProb + deltaPDR) / (delivProb + deltaPDR));

      return metric;
    }

  }

  public static class EttNetAddressWithMetric extends NetAddressWithMetric {
    public int etxToSrc;

    public EttNetAddressWithMetric(NetAddress ip, int metric, int metricToSrc, int etxToSrc) {
      super(ip, metric, metricToSrc);
      this.etxToSrc = etxToSrc;
    }

    public EttNetAddressWithMetric(NetAddressWithMetric n, int etxToSrc) {
      this(n.ip, n.metric, n.metricToSrc, etxToSrc);
    }
  }

  public static class EttCsWithMetric extends CsWithMetric {
    public int etxToSrc;

    public EttCsWithMetric(List cs, int metric, int metricToSrc, int nextCandIdx, int etxToSrc) {
      super(cs, metric, metricToSrc, nextCandIdx);
      this.etxToSrc = etxToSrc;
    }
  }

  /**
   *
   *  M(B,C) = ETT(ETX(a,b) ETX(a,c) / (ETX(a,b)+ETX(a,c)-1))
   *    + (ETT(b,d) + ETT(c,d))/2 * (2 - 1/ETX(b,c))
   *
   * TODO consider multiple usage of more than one data rate (a la rf channel
   * clustering).
   *
   * @author kurth
   */
  protected static class CsSelectionEtt extends TxDORSelection {
    private LinkTable linkTable;
    private ETTMetric metric;
    private int maxMetricForNeighbor = 500;
    private Integer dataRate;
    private boolean scaleRemainingHops;

    public CsSelectionEtt(int csSize, NetAddress localAddr,
        RouteMetricInterface routeMetric, int metricDelta, int maxMetricForNeighbor,
        LinkTable linkTable, ETTMetric metric, Integer dataRate, boolean scaleRemainingHops) {
      super(csSize, localAddr, routeMetric, metricDelta, ETTMetric.INFINITE_METRIC);
      this.maxMetricForNeighbor = maxMetricForNeighbor;
      this.linkTable = linkTable;
      this.metric = metric;
      this.dataRate = dataRate;
      this.scaleRemainingHops = scaleRemainingHops;
    }

    private int getEtx(NetAddress from, NetAddress to) {
      ETTMetric.EttData linkInfo = (EttData) linkTable.getLinkInfo(from, to);
      if (null == linkInfo)
        return getInvalidRouteMetric();

//      if (Main.ASSERT)
//        Util.assertion(info.dataRate == dataRate);

      return linkInfo.etx();
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#getNeighbors(jist.swans.net.NetAddress)
     */
    protected List getNeighbors(NetAddress src) {
      List neighbors = routeMetric.getNeighbors(src);

      // do not use previous forwarders
      List lst = (List) anno.get(MessageAnno.ANNO_RTG_FORWARDER);
      Set forwarder = (lst == null) ? null : new HashSet(lst);

      // filter according to max neigbor etx metric.
      Iterator iter = neighbors.iterator();
      while (iter.hasNext()) {
        NetAddress nb = (NetAddress) iter.next();
        if (forwarder != null && forwarder.contains(nb)
            ||getEtx(src, nb) > this.maxMetricForNeighbor)
          iter.remove();
      }


      return neighbors;
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#getCachedCandidates(brn.swans.route.cs.CandidateSelection.CandidateCacheEntry)
     */
    protected List getCachedCandidates(CandidateCacheEntry entry) {
      List cached = super.getCachedCandidates(entry);
      if (null == cached || cached.size() == 0)
        return null;

      List lst = (List) anno.get(MessageAnno.ANNO_RTG_FORWARDER);
      for (int i = 0; null != lst && i < lst.size(); i++) {
        if (cached.contains(lst.get(i)))
          return null;
      }

      return cached;
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#getMetricToSrc(brn.swans.route.RouteDsrTxDOR.CsWithMetric, brn.swans.route.cs.CandidateSelection.NetAddressWithMetric)
     */
    protected int getMetricToSrc(CsWithMetric c, NetAddressWithMetric nc) {
      EttCsWithMetric candidates = (EttCsWithMetric) c;
      EttNetAddressWithMetric newCandidate = (EttNetAddressWithMetric) nc;

      // determine new metric towards the source
      int newEtxToSrc = newCandidate.etxToSrc * candidates.etxToSrc
          / (newCandidate.etxToSrc + candidates.etxToSrc - 100);

      return newEtxToSrc;
    }

    /*
     * (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#getInterCandidateMetric(int, java.util.List, brn.swans.route.cs.CandidateSelection.NetAddressWithMetric)
     */
    protected double getInterCandidateMetric(int curr, List cs, NetAddressWithMetric currCand) {
      // if current node equals destination it is the last hop
      boolean lastHop = dst.equals(currCand.ip);

      // average of all link metrics between current and previous candidates
      double candLink = .0;
      for (int i = 0; i < curr && lastHop == false; i++) {
        NetAddressWithMetric otherCand = (NetAddressWithMetric) cs.get(i);

        lastHop = dst.equals(otherCand.ip);
//        candLink += getEtx(otherCand.ip, currCand.ip);
        candLink = Math.max(getEtx(otherCand.ip, currCand.ip), candLink);
      }
//      candLink = (!lastHop ? candLink / curr : RouteMetricInterface.INVALID_ROUTE_METRIC);
      if (lastHop)
        candLink = getInvalidRouteMetric();
      return candLink;
    }


    /*
     * (non-Javadoc)
     * @see brn.swans.route.cs.CandidateSelection#calcShortestPathForEachNeighbor(java.util.List, jist.swans.net.NetAddress, jist.swans.net.NetAddress, int)
     */
    protected List calcShortestPathForEachNeighbor(final List neighbors,
        final NetAddress src, final NetAddress dst, final List route, final int metric) {
      List candidates = super.calcShortestPathForEachNeighbor(neighbors, src,
          dst, route, metric);

      // get the etx for each candidate!!!
      List newCandidates = new ArrayList(candidates.size());
      for (int i = 0; i < candidates.size(); i++) {
        NetAddressWithMetric candi = (NetAddressWithMetric) candidates.get(i);
        /*
         * NUGGET: consider the first hop for the initial source more important
         * than the remaining hops towards the final destination
         *
         * Idea: if the distance to the final destination is big (metric
         * is much larger than metricToSrc) try to quickly spread out using
         * only very good candidates and max. number of candidates (-> small
         * backoff and retries). Instead if we are near the final destination
         * try to concentrate the flow.
         *
         * TODO use this only on the first hop ??
         */
        if (scaleRemainingHops  && route.size() > 3)
          candi.metric /= (route.size()-2);
        int etx = getEtx(src, candi.ip);
        newCandidates.add(new EttNetAddressWithMetric(candi, etx));
        if (Main.ASSERT)
          Util.assertion(etx <= this.maxMetricForNeighbor);
      }

      return newCandidates;
    }

    /* (non-Javadoc)
     * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#constructNewCandidate(brn.swans.route.RouteDsrTxDOR.CsWithMetric, java.util.List, int, brn.swans.route.cs.CandidateSelection.NetAddressWithMetric)
     */
    protected CsWithMetric constructNewCandidate(CsWithMetric nodeToExpand,
        List tmp, int currCandIdx, NetAddressWithMetric c) {
      EttNetAddressWithMetric currCand = (EttNetAddressWithMetric) c;
      int currCsSize = tmp.size();
      tmp.set(currCsSize-1, currCand);

      int newMetricToSrc = 0;
      int newMetricToDst = 0;
      int etxToSrc = 0;
      if (currCsSize == 1) {
        newMetricToSrc = currCand.metricToSrc;
        newMetricToDst = currCand.metric;
        etxToSrc = currCand.etxToSrc;
      }
      else if (currCsSize > 1) {
        etxToSrc = getMetricToSrc(nodeToExpand, currCand);
        // TODO Integer.valueOf(Constants.BANDWIDTH_6Mbps)
        newMetricToSrc = (int)metric.ett(etxToSrc, dataRate, null);
        newMetricToDst = getMetricToDst(currCsSize-1, nodeToExpand.metric, tmp, currCand);
      }

      return new EttCsWithMetric(new ArrayList(tmp),
          newMetricToDst, newMetricToSrc, currCandIdx+1, etxToSrc);
    }
  }


  public static class EaxSelection extends RouteDsrTxDOR.TxDORSelection {

    private static EaxMetric metric;

    public EaxSelection(NetAddress localAddr, RouteMetricInterface routeMetric) {
      super(0, localAddr, routeMetric, -1, -1);
      if (null == metric)
        metric = new EaxMetric(routeMetric);
    }

    @Override
    protected List calculate(NetAddress src, NetAddress dst) {
      List ret = new ArrayList();
      ret.add(metric.getCandidates(src, dst));
      return ret;
    }

  }

  // ////////////////////////////////////////////////
  // locals
  //

  /** table holding information about duplicate packets */
  protected DuplicateTable duplicateTable;

  /** mac address of local node */
  protected MacAddress localMacAddress;

  /** metric to use for routing */
  protected RouteMetricInterface routeMetric;

  protected TxDORSelection candidateSelection;

  private RouteDsrTxDORInterface selfNotify;


  // ////////////////////////////////////////////////
  // initialization
  //

  public RouteDsrTxDOR(NetAddress localAddr, RouteMetricInterface routeMetric,
      ArpTableInterface arp, int maxMetricForNeighbor) {
    super(localAddr, arp);

    this.routeMetric = routeMetric;
    this.localMacAddress = arp.getArpEntry(localAddr);

    this.candidateSelection = new TxDORSelection(3, localAddr, routeMetric,
        0, maxMetricForNeighbor);

    this.duplicateTable = new DuplicateTable();
    this.selfNotify = (RouteDsrTxDORInterface) JistAPI.proxy(new RouteDsrTxDORInterface.Dlg(this),
        RouteDsrTxDORInterface.class);
    if (Main.ASSERT)
      Util.assertion(null != this.selfNotify);

    /*
     * NOTE: we use the artificial dlg class for proxy creation, so we can
     * support implementation inheritance.
     */
    self = (RouteDsrTxDORInterface) JistAPI.proxy(
        new RouteDsrTxDORInterface.Dlg(this), RouteDsrTxDORInterface.class);
  }

  // ////////////////////////////////////////////////
  // accessors
  //

  /**
   * @return the routeMetric
   */
  public RouteMetricInterface getRouteMetric() {
    return routeMetric;
  }

  public void setCandidateSelection(int csSel, double deltaSnr,
      LinkStat.Metric metric, Integer dataRate, boolean scaleRemainingHops) {
    switch (csSel) {
    case brn.swans.Constants.TXDOR_CSSEL_CONSERVATIVE:
      candidateSelection = new TxDORSelConservative(
          candidateSelection.getCSetSize(), localAddr, routeMetric,
          candidateSelection.getMetricDelta(),
          candidateSelection.getMaxMetricForNeighbor());
      break;
    case brn.swans.Constants.TXDOR_CSSEL_LESSCONS:
      candidateSelection = new TxDORSelection(
          candidateSelection.getCSetSize(), localAddr, routeMetric,
          candidateSelection.getMetricDelta(),
          candidateSelection.getMaxMetricForNeighbor());
      break;
    case brn.swans.Constants.TXDOR_CSSEL_ROBCONRAT:
      candidateSelection = new TxDORSelRobustControlRate(
          candidateSelection.getCSetSize(), localAddr, routeMetric,
          candidateSelection.getMetricDelta(),
          candidateSelection.getMaxMetricForNeighbor(),
          deltaSnr);
      break;
    case brn.swans.Constants.TXDOR_CSSEL_ETT:
      candidateSelection = new CsSelectionEtt(
          candidateSelection.getCSetSize(), localAddr, routeMetric,
          candidateSelection.getMetricDelta(),
          candidateSelection.getMaxMetricForNeighbor(),
          metric.getLinkTable(), (ETTMetric) metric, dataRate, scaleRemainingHops);
      discovery.setMinLinkMetric(ETTMetric.INFINITE_METRIC);
      break;
    case brn.swans.Constants.TXDOR_CSSEL_EAX:
      candidateSelection = new EaxSelection(localAddr, routeMetric);
      break;
    }
  }

  public void setMetricDelta(int metricDelta) {
    candidateSelection.setMetricDelta(metricDelta);
  }

  /**
   * @param noCandSets
   * @see brn.swans.route.RouteDsrTxDOR.TxDORSelection#setNoCandSets(int)
   */
  public void setNoCandSets(int noCandSets) {
    candidateSelection.setNoCandSets(noCandSets);
  }

  /**
   * @see CandidateSelection#setCSetSize(int)
   */
  public void setCsSize(int csSize) {
    this.candidateSelection.setCSetSize(csSize);
  }

  public RouteDsrTxDORInterface getNotifyProxy() {
    return selfNotify;
  }

  public void setCandidateCacheTimeout(long candidateCacheTimeout) {
    candidateSelection.setCandidateCacheTimeout(candidateCacheTimeout);
  }

  // ////////////////////////////////////////////////
  // overwrites
  //

  /*
   * (non-Javadoc)
   *
   * @see brn.swans.route.RouteDsrBrnInterface#send(jist.swans.net.NetMessage.Ip,
   *      int, jist.swans.mac.MacAddress, jist.swans.misc.MessageAnno)
   */
  public void send(NetMessage.Ip msg, int interfaceId, MacAddress nextHop, MessageAnno anno) {
    // delegate broadcasts to network layer
    if (msg.getDst().equals(NetAddress.ANY)) {
      netEntity.send(msg, interfaceId, nextHop, anno);
      return;
    }

    // Calculate candidate set and give to network layer
    List lstNetCandidates = candidateSelection.calculate(localAddr, msg.getDst(), msg, anno);
    if (null == lstNetCandidates || lstNetCandidates.size() == 0) {
      log.error(this + "(" + JistAPI.getTime() + "): no route found to " + msg.getDst());
      handleTransmitError(msg, anno);
      return;
    }

//    if (Main.ASSERT)
//      Util.assertion(!lstNetCandidates.contains(localAddr));

    List lstMacCandidates = new ArrayList(lstNetCandidates.size());
    for (int i = 0; i < lstNetCandidates.size(); i++)
      lstMacCandidates.add(arp.getArpEntry((NetAddress)lstNetCandidates.get(i)));

    anno.put(MessageAnno.ANNO_MAC_CANDIDATES, lstMacCandidates);
    if (log.isDebugEnabled())
      log.debug(this + "(" + JistAPI.getTime() + "): using candidate set " +
          lstMacCandidates);
    anno.put(MessageAnno.ANNO_MAC_FINALDST_IDX,
        new Byte((byte)lstNetCandidates.indexOf(msg.getDst())));

    if (candSelectedEvent.isActive()) {
      // TODO flow id
      Integer packetId = (Integer) anno.get(MessageAnno.ANNO_RTG_PACKETID);
      candSelectedEvent.handle(packetId.intValue(), lstMacCandidates, msg, anno);
    }

    netEntity.send(msg, interfaceId, MacTxDOR.ADDR_ANYCAST, anno);
  }

  /*
   * (non-Javadoc)
   *
   * @see jist.swans.route.RouteInterface#peek(jist.swans.net.NetMessage,
   *      jist.swans.misc.MessageAnno)
   */
  public void peek(NetMessage msg, MacAddress lastHop, MessageAnno anno) {
    discovery.peek(msg, lastHop, anno);

    if (!(msg instanceof NetMessage.Ip))
      return;

    NetMessage.Ip ipMsg = (NetMessage.Ip) msg;
    if (ipMsg.getProtocol() != Constants.NET_PROTOCOL_MCEXOR)
      return;

    RouteDsrBrnMsg mcExORMsg = (RouteDsrBrnMsg) ipMsg.getPayload();

    if (log.isDebugEnabled())
      log.debug(this + "(" + JistAPI.getTime() + "): saw message from "
          + ipMsg.getSrc() + "(" + lastHop + ") to " + ipMsg.getDst() + " ["
          + mcExORMsg + "]");

    //RouteDsrBrnMsg.OptionSourceRoute sourceRoute = mcExORMsg.getSourceRoute();
    List candidates = (List) anno.get(MessageAnno.ANNO_MAC_CANDIDATES);
    if (/*sourceRoute != null
        && localAddr.equals(sourceRoute.nextRecipient(ipMsg.getDst()))
        ||*/ candidates != null && candidates.contains(localMacAddress)) {
      forwardPacket(mcExORMsg, anno, lastHop, null, ipMsg.getSrc(),
          ipMsg.getDst(), ipMsg.getProtocol(), ipMsg.getPriority(), ipMsg
              .getTTL(), ipMsg.getId(), ipMsg.getFragOffset());
    }
  }

  /* (non-Javadoc)
   * @see brn.swans.route.RouteDsrBrn#receive(jist.swans.misc.Message, jist.swans.net.NetAddress, jist.swans.mac.MacAddress, byte, jist.swans.net.NetAddress, byte, byte, jist.swans.misc.MessageAnno)
   */
  public void receive(Message msg, NetAddress src, MacAddress lastHop,
      byte macId, NetAddress dst, byte priority, byte ttl, MessageAnno anno) {
    if (log.isInfoEnabled() && localAddr.equals(dst))
      // Don't count received broadcast packets?
      log.info(JistAPI.getTime() + ":" + this + " Received packet from " + src
          + " at " + dst);

    // Don't process any options here -- that's all done by peek. Just forward
    // any content on to the transport layer (or whatever).
    RouteDsrBrnMsg mcExORMsg = (RouteDsrBrnMsg) msg;

    if (mcExORMsg.getContent() != null) {
      // eliminate duplicates
      if (duplicateTable.isDuplicate((RouteDsrBrnMsg)msg, src)) {
        if (duplicateEvent.isActive())
          duplicateEvent.handle(msg, anno, arp.getArpEntry(lastHop), localAddr);
        return;
      }
      duplicateTable.addDataPacketId((RouteDsrBrnMsg)msg, src);

      // Preserve flow and packet id
      RouteDsrBrnMsg.OptionId id = (RouteDsrBrnMsg.OptionId)
          mcExORMsg.getOption(RouteDsrBrnMsg.OPT_ID);
      anno.put(MessageAnno.ANNO_RTG_FLOWID, new Integer(id.getAnnoFlowId()));
      anno.put(MessageAnno.ANNO_RTG_PACKETID, new Integer(id.getAnnoPacketId()));
      anno.put(MessageAnno.ANNO_RTG_HOPCOUNT, new Integer(id.getHopCount()+1));

      if (packetForwardedEvent.isActive())
        packetForwardedEvent.handle(msg, anno, arp.getArpEntry(lastHop), localAddr);

      // Now go through some strange contortions to get this message
      // received by the proper protocol handler
      NetMessage.Ip newIp = new NetMessage.Ip(mcExORMsg.getContent(),
              src, dst, mcExORMsg.getNextHeaderType(), priority, ttl);

      netEntity.receive(newIp, lastHop, macId, false, anno);

      if (log.isInfoEnabled())
        log.info(JistAPI.getTime() + ":" + this + " Received data packet from "
            + src + " at " + dst);
    }
  }

  /**
   * Forwards a McExOR packet containing a Source Route option to the next
   * intended recipient. An Acknowledgement Request option is added to the
   * headers, and the packet is retransmitted if no acknowledgement is
   * received before the allotted timeout elapses.
   *
   * @param msg        the <code>RouteMcExORMsg</code> to be forwarded
   * @param anno
   * @param opt        the Source Route option
   * @param src        the address of the originator of this packet
   * @param dest       the address of the ultimate destination of this packet
   * @param protocol   the IP protocol of this packet (usually McExOR)
   * @param priority   the IP priority of this packet
   * @param ttl        the IP time to live of this packet
   * @param id         the IP identification of this packet
   * @param fragOffset the IP fragmentation offset of this packet
   */
  protected void forwardPacket(RouteDsrBrnMsg msg, MessageAnno anno,
      MacAddress lastHop, RouteDsrBrnMsg.OptionSourceRoute opt, NetAddress src,
      NetAddress dest, short protocol, byte priority, byte ttl, short id,
      short fragOffset) {
    List candidates = (List) anno.get(MessageAnno.ANNO_MAC_CANDIDATES);
    long arrival = (Long) anno.get(MessageAnno.ANNO_NET_ARRIVAL);

    // If the packet is for me it doesn't need to be forwarded
    if (localAddr.equals(dest) || !candidates.contains(localMacAddress))
      return;

    // Preserve flow and packet id
    RouteDsrBrnMsg.OptionId optId = (RouteDsrBrnMsg.OptionId)
        msg.getOption(RouteDsrBrnMsg.OPT_ID);

    // increment forwarding counter and forward the packet
    if (packetForwardedEvent.isActive())
      packetForwardedEvent.handle(msg, anno, arp.getArpEntry(lastHop), localAddr);

    // Construct new routing envelop, important: clone id option field
    RouteDsrBrnMsg newMsg = (RouteDsrBrnMsg) msg.clone();
    RouteDsrBrnMsg.OptionId optIdNew = (RouteDsrBrnMsg.OptionId) optId.clone();

    // put forwarders received at mac layer into the id option field
    Set forwarder = (Set) anno.get(MessageAnno.ANNO_MAC_FORWARDER);
    Util.assertion(null != forwarder);
    for (Iterator iter = forwarder.iterator(); iter.hasNext(); ) {
      NetAddress netFwd = arp.getArpEntry((MacAddress) iter.next());
      if (null != netFwd && !optIdNew.getForwarder().contains(netFwd))
        optIdNew.addForwarder(netFwd);
    }
    if (Main.ASSERT)
      Util.assertion(forwarder.contains(lastHop));

    optIdNew.addForwarder(localAddr);
    optIdNew.intHopCount();
    newMsg.removeOption(RouteDsrBrnMsg.OPT_ID);
    newMsg.addOption(optIdNew);
    if (Main.ASSERT)
      Util.assertion(optId.getHopCount() + 1 == optIdNew.getHopCount());

    // Construct new anno (we do not want to get in confusion with old annos)
    // do not recycle the old one, because we need it in mac.
    anno = new MessageAnno();

    // put all stuff in annos ...
    anno.put(MessageAnno.ANNO_RTG_FLOWID, new Integer(optId.getAnnoFlowId()));
    anno.put(MessageAnno.ANNO_RTG_PACKETID, new Integer(optId.getAnnoPacketId()));
    anno.put(MessageAnno.ANNO_RTG_FORWARDER, optIdNew.getForwarder());
    anno.put(MessageAnno.ANNO_NET_ARRIVAL, arrival);

    NetMessage.Ip ipMsg = new NetMessage.Ip(newMsg, src, dest, protocol,
        priority, (byte) (ttl - 1), id, fragOffset);

    send(ipMsg, Constants.NET_INTERFACE_DEFAULT, null, anno);
  }
}
