package brn.swans.route;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import jist.runtime.JistAPI;
import jist.runtime.Util;
import jist.swans.Constants;
import jist.swans.radio.RadioInterface;
import jist.swans.mac.MacAddress;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.misc.MessageBytes;
import jist.swans.misc.Pickle;
import jist.swans.net.NetAddress;
import jist.swans.net.NetInterface;
import jist.swans.net.NetMessage;
import jist.swans.route.AbstractRoute;
import jist.swans.route.RouteInterface;
import jist.swans.trans.TransUdp;

import org.apache.log4j.Logger;

import brn.swans.route.cs.CandidateSetGraph;
import brn.swans.route.cs.CandidateSelection.NetAddressWithMetric;
import brn.swans.route.metric.RouteMetricInterface;
import brn.util.Tuple;

/**
 * Implementation of the McExOR routing protocol family:
 * - AODV-like behavior (channels: 1; cset size: 1)
 * - ExOR (channels: 1; cset size: >1)
 * - McExOR (channels: >1; cset size: >1)
 *
 * @author Zubow
 */
public final class RouteMcExOR extends AbstractRoute implements RouteMcExORInterface {

  //
  // DEBUG stuff
  //
  public static final Hashtable fwdLinks = new Hashtable();
  private Hashtable pos_tbl;
  /** constant for an non-existing link */
  final static int INVALID_ROUTE_METRIC = 9999;
  /** forward only route request which came from a link with a better metric of this */
  final static int MAX_LINK_METRIC_FOR_RREQ_FORWARDING = 5000;
  final static int MAX_ROUTE_METRIC_FOR_TX = 1016;

  //private final static double OPTIMAL_CS_DISTANCE[][] = { {282.9}, {590.3, 338.3}, {755.0, 571.3, 298.5}, {852, 745, 548, 272}};
  private final static double OPTIMAL_CS_DISTANCE[][] = { {300},
                                                          {600, 350},
                                                          {750, 550, 300},
                                                          {850, 750, 550, 272}
                                                        };
  public static class FwdLink {
    public NetAddress from;
    public NetAddress to;
    public int fromCh;
    public int toCh;
    public int flowId;

    public FwdLink(NetAddress from, int fromCh, NetAddress to, int toCh) {
      this.from = from;
      this.fromCh = fromCh;
      this.to = to;
      this.toCh = toCh;
    }

    public String getFromStr() {
      return from + ":" + fromCh;
    }

    public String getToStr() {
      return to + ":" + toCh;
    }

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

      final FwdLink fwdLink = (FwdLink) o;

      if (fromCh != fwdLink.fromCh) return false;
      if (toCh != fwdLink.toCh) return false;
      if (!from.equals(fwdLink.from)) return false;
      if (!to.equals(fwdLink.to)) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = from.hashCode();
      result = 29 * result + to.hashCode();
      result = 29 * result + fromCh;
      result = 29 * result + toCh;
      return result;
    }

    public void setFlowId(int flowId) {
      this.flowId = flowId;
    }
  }

  //
  // Constants
  //

  public static final int PROACTIVE_VERSION = 1;
  public static final int REACTIVE_VERSION = 2;

  /**
   * {@link #REACTIVE_VERSION} or {@link #PROACTIVE_VERSION}
   */
  protected int version;

  protected boolean floodingEnabled = true;

  /**
   * The usage of only one candidate results in an AODV like behavior.
   */
  public static final int AODV_CS_SIZE = 1;

  /**
   * The maximum size of the candidate set.
   */
  public static final int CS_SIZE = 4;

  //
  // constants used by the candidate set algorithm
  //

  public static final int GLOBAL_CSET_SELECTION = 1;
  public static final int LOCAL_CSET_SELECTION = 2;
  public static final int CSET_SELECTION_BESTPATHS = 3;
  public static final int CSET_SELECTION_AVERAGING = 4;
  public static final int CSET_SELECTION_OPTIMAL = 5;

  /**
   * {@link #GLOBAL_CSET_SELECTION} or {@link #LOCAL_CSET_SELECTION}
   */
  protected int csetSelection = LOCAL_CSET_SELECTION;

  /**
   * Max distance between two adjacent candidates.
   */
  public static final int MAX_METRIK_BETWEEN_CANDIDATES = 100;

  /**
   * Only neighbors with this maximum metric are considered to be potential candidates.
   */
  public static final int CS_MIN_METRIC = 350; //TODO 700

  /**
   * We must have a metric of not bigger than this value to a safe neighbor.
   */
  public static final int CS_MIN_METRIC_FOR_SAFE_NB = 115;

  /**
   * The maximum amount of jitter before sending a packet.
   */
  public static final long BROADCAST_JITTER = 10 * Constants.MILLI_SECOND;

  //
  // constants used by the reactive versions of this protocol
  //

  // (msecs)
  protected static final int DEFER_RREQ_FORWARD = 20;

  /**
   * The maximum amount of time a packet can remain in the Send Buffer.
   */
  public static final long SEND_BUFFER_TIMEOUT = 30 * Constants.SECOND;

  /**
   * The initial timeout before retransmitting a Route Request.
   */
  public static final long REQUEST_PERIOD = 1000 * Constants.MILLI_SECOND;

  /**
   * The maximum timeout before retransmitting a Route Request.
   */
  public static final long MAX_REQUEST_PERIOD = 10 * Constants.SECOND;

  /**
   * The minimum time between sending gratuitous Route Replies.
   */
  public static final long GRAT_REPLY_HOLDOFF = 1 * Constants.SECOND;

  /**
   * The maximum number of ID values to store in a single Route Request Table entry.
   */
  public static final int MAX_REQUEST_TABLE_IDS = 16;

  /**
   * The maximum Time-To-Live for a ExOR packet.
   */
  public static final byte MAX_TTL = (byte) 255;

  /**
   * This class is responsible for the flooding algorithm used by the proactive version
   */
  protected RouteMcExORFlood flooding;

  // Logging and tracing
  //

  /**
   * Event processor interface
   */
  protected List /* EventProcessor */  eventProcessors = null;

  /**
   * McExOR logger.
   */
  private static Logger log = Logger.getLogger(RouteMcExOR.class.getName());

  /**
   * The Gratuitous Route Reply Table is a set of
   * <code>RouteReplyTableEntry</code> s indicating which nodes have
   * recently triggered gratuitous Route Replies because of automatic route
   * shortening.
   */
  private HashSet routeReplyTable;

  /**
   * The interface to the network layer.
   */
  protected NetInterface netEntity;

  /**
   * The IP address of this node.
   */
  protected NetAddress localAddr;

  /**
   * List of <code>BufferedPacket</code> s waiting to be sent.
   */
  private LinkedList sendBuffer;

  /**
   * The route request table maps <code>NetAddress</code> es(destinations)
   * to <code>RouteRequestTableEntry</code>s, which are structures
   * containing various information used when performing Route Discovery.
   */
  private Hashtable routeRequestTable;

  /**
   * Keep track of forwarded flooding packets: {@link brn.swans.route.RouteMcExOR.PacketId}
   */
  private HashSet floodingTable;

  /**
   * The next ID number to use when sending a route request.
   */
  protected short nextRequestId;

  /**
   * Keep track of ExOR routed data packets: {@link brn.swans.route.RouteMcExOR.PacketId} (avoid duplicates)
   */
  private HashSet dataPacketTable;

  /**
   * sequence number counter for data packets (duplicate elimanation).
   */
  protected int nextDataPacketId;

  /**
   * Set of <code>NetAddress</code> es of destinations of currently active Route Requests.
   */
  protected HashSet activeRequests;

  /**
   * The proxy interface for this object.
   */
  protected RouteMcExORInterface self;

  /**
   * ARP table to resolve the ethernet address of a given ip address.
   */
  protected Hashtable arp;

  /**
   * the size of the candidate set initialized with the default value
   */
  protected int cSetSize = CS_SIZE;

  protected CandidateSetGraph csgraph = null;
  private RouteMetricInterface routeMetric = null;
  private long floodingPeriod = 10 * Constants.SECOND;

  //
  // Methods
  //

  /**
   * Reactive Version of the McExOR Routing Protocol
   *
   * @param localAddr the address of this node
   * @param arp       Arp table to resolve ip <-> mac addresses
   */
  public RouteMcExOR(NetAddress localAddr, RouteMetricInterface routeMetric,
                     Hashtable arp, int cSetSize) {
    this(localAddr);
    this.version = REACTIVE_VERSION;
    this.routeMetric = routeMetric;
    this.arp = arp;
    this.cSetSize = cSetSize;
    initDataPacketTable();
  }

  /**
   * Proactive Version of the McExOR Routing Protocol
   *
   * @param localAddr the address of this node
   * @param flood     used by the proactive protocol
   * @param arp       Arp table to resolve ip <-> mac addresses
   */
  public RouteMcExOR(NetAddress localAddr, RouteMetricInterface routeMetric,
                     RouteMcExORFlood flood, Hashtable arp) {
    this(localAddr, routeMetric, flood, arp, CS_SIZE);
  }

  /**
   * Proactive Version of the McExOR Routing Protocol
   *
   * @param localAddr the address of this node
   * @param flood     used by the proactive protocol
   * @param arp       Arp table to resolve ip <-> mac addresses
   */
  public RouteMcExOR(NetAddress localAddr, RouteMetricInterface routeMetric,
                     RouteMcExORFlood flood, Hashtable arp, int cSetSize) {
    this(localAddr, routeMetric, arp, cSetSize);
    this.version = PROACTIVE_VERSION;
    this.flooding = flood;
    initFloodingTable();
    initDataPacketTable();
  }

  /**
   * Creates a new Routing object.
   *
   * @param localAddr local node address
   */
  private RouteMcExOR(NetAddress localAddr) {

    // sequence numbers
    this.localAddr = localAddr;
    // InitRouteCache();
    initBuffer();
    initRequestTable();
    initRouteReplyTable();

    nextRequestId = 0;
    nextDataPacketId = Integer.MAX_VALUE;
    activeRequests = new HashSet();
    eventProcessors = new ArrayList();

    self = (RouteMcExORInterface) JistAPI.proxy(
        new RouteMcExORInterface.Dlg(this), RouteMcExORInterface.class);
  }

  /**
   * Sets the interface to the network layer.
   *
   * @param netEntity the interface to the network layer
   */
  public void setNetEntity(NetInterface netEntity) {
    this.netEntity = netEntity;
  }

  /**
   * Gets the proxy interface for this object.
   *
   * @return the proxy <code>RouteMcExORInterface</code> interface for this
   *         object
   */
  public RouteMcExORInterface getProxy() {
    return self;
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.route.AbstractRoute#getRouteProxy()
   */
  public RouteInterface getRouteProxy() {
    return self;
  }


  /**
   * Sends the given message. This method can be called because this node is
   * originating a packet (in which case a McExOR header is added to the
   * packet and it is sent) or because this node is forwarding a packet (in
   * which case this method actually does nothing, with all McExOR header
   * option processing being performed by <code>peek</code>.
   *
   * @param msg the message to be sent
   */
  public void send(NetMessage msg, MessageAnno anno) {

    if (!(msg instanceof NetMessage.Ip)) {
      throw new RuntimeException("Non-IP packets not supported");
    }

    NetMessage.Ip ipMsg = (NetMessage.Ip) msg;

    if (ipMsg.getProtocol() == Constants.NET_PROTOCOL_MCEXOR) {
      // We're not really supposed to "send" this packet -- we might have
      // to
      // to forward it, but that happens along with all the other option
      // processing in peek().
    } else {
      // Need to encapsulate and send this packet
      RouteEntry[] route = getRouteFromLinkTable(ipMsg.getDst());

      if (route == null) { // no valid route available
        if (version == PROACTIVE_VERSION) {
          log.error(localAddr + "(" + JistAPI.getTime() + "): Proactive protocol has no route ...");
          log.error(this.routeMetric);
          throw new RuntimeException("Proactive protocol has no route ...");
        } else if (version == REACTIVE_VERSION) {
          log.info(localAddr + "( " + JistAPI.getTime() + " ) (init-node) don't have route; searching for ... ( "
                  + localAddr + " " + ipMsg.getDst() + " )");
          self.insertBuffer(ipMsg, anno);
          activeRequests.add(ipMsg.getDst());
          discoverRoute(ipMsg.getDst(), nextRequestId++);
        }
      } else {  // we have a route
        // calculate candidate set
        List cs = new ArrayList();

        int ch = calculateCandidateSet(route, localAddr, ipMsg.getDst(), cs, true, null, null, route);

        if ((ch != -1) && (cs.size() > 0)) {

          if (cs.size() < cSetSize)
            log.warn(localAddr + "( " + JistAPI.getTime() + " ): CSSIZE is smaller than optimal: "
                    + cs.size() + " < " + cSetSize);

          int id = getUDPMsgId(ipMsg.getPayload());

          if (log.isInfoEnabled()) {
            log.info(localAddr + "(" + JistAPI.getTime() + "): Sending packet on ch " + ch + " id = " + id);
          }

//          processCSEvent(cs, id);

          // send packet
          sendWithCandidateSet(ipMsg, cs, ch, id, route);
        } else {
          log.fatal("Error !!!");
          throw new RuntimeException("calculateCandidateSet failed; no route found to dst!");
        }
      }
    }
  }

  /**
   * Forwards an ExOR routed packet.
   *
   * @param msg        the received msg
   * @param opt        the Route Request option
   * @param optBuf     the bytes of the Route Request option
   * @param src        the originator of the Route Request
   * @param dest       the destination of the Route Request (usually broadcast)
   * @param protocol   the IP protocol of the message
   * @param priority   the IP priority of the message
   * @param ttl        the IP time to live of the message
   * @param id         the IP identification of the message
   * @param fragOffset the IP fragmentation offset of the message
   * @param lastHop    the last forwarder
   */
  private void forwardPacket(RouteMcExORMsg msg, MessageAnno anno,
      RouteMcExORMsg.OptionDataNoRoute opt,  byte[] optBuf, NetAddress src,
      NetAddress dest, short protocol, byte priority, byte ttl, short id,
      short fragOffset, MacAddress lastHop, RouteEntry[] fallbackRoute) {
    // If the packet is for me it doesn't need to be forwarded
    if (localAddr.equals(dest))
      return;

    log.info(localAddr + "(" + JistAPI.getTime() + ")" + " forward packet ("
            + src + "," + opt.getSeqNum() + ")");

    // estimate the net address of the last hop
    NetAddress lastIp = rarp(lastHop);

    // Need to encapsulate and send this packet
    RouteEntry[] route = getRouteFromLinkTable(dest);// GetCachedRoute(ipMsg.getDst());

    if (route == null) { // no valid route available
      if (version == PROACTIVE_VERSION) {
        log.error(localAddr + "(" + JistAPI.getTime() + "): Proactive protocol has no route ...");
        log.error(this.routeMetric);
        throw new RuntimeException("Proactive protocol has no route ...");
      } else if (version == REACTIVE_VERSION) {
        log.info(localAddr + "(" + JistAPI.getTime() + ") (relay-node) don't have route; searching for ... " + dest);
        //TODO extrem dirty hack
        NetMessage.Ip bufferPacket = new NetMessage.Ip(msg.getContent(), src, dest, Constants.NET_PROTOCOL_UDP, priority, ttl);
        self.insertBuffer(bufferPacket, anno);
        activeRequests.add(bufferPacket.getDst());
        discoverRoute(bufferPacket.getDst(), nextRequestId++);
      }
    } else {  // we have a route
      byte[] chArray = opt.getUsedChannels();
      int chArrLen = (chArray != null) ? chArray.length : 0;
      byte[] nwArary = new byte[chArrLen + 1];
      if (chArray != null)
        System.arraycopy(chArray, 0, nwArary, 0, chArrLen);

      // last hop was on my home channel
      RadioInterface.RFChannel chLastHop = routeMetric.getHomeChannel(localAddr);// routeMetric.getHomeChannel(lastIp);

      nwArary[chArrLen] = (byte) chLastHop.getChannel();

      // calculate candidate set
      List cs = new ArrayList();
      int ch = calculateCandidateSet(route, localAddr, dest, cs, false, lastIp, nwArary, fallbackRoute);

      if ((ch != -1) && (cs.size() > 0)) {

        if (cs.size() < cSetSize)
          log.warn(localAddr + "( " + JistAPI.getTime() + " ): CSSIZE is smaller than optimal: "
                  + cs.size() + " < " + cSetSize);

        int p_id = getUDPMsgId(msg.getContent());

        if (log.isInfoEnabled()) {
          log.info(" " + localAddr + " (" + JistAPI.getTime() + "): Forwarding packet from "
                  + lastIp + " ( " + routeMetric.getHomeChannel(localAddr) + " ) on ch " + ch + " #id# = " + p_id);
        }

      boolean duplicateElimation = true;
      Iterator csIt = cs.iterator();
      while ( (csIt != null) && (csIt.hasNext()) ) {
        NetAddressWithMetric csItem = (NetAddressWithMetric) csIt.next();
        if (csItem.ip.equals(dest)) { // last hop
          duplicateElimation = false;
          break;
        }
      }

      // Check for duplicates and filter them out
      if (duplicateElimation && isDuplicate(msg, src)) {
        log.info(localAddr + " (" + JistAPI.getTime() + "): duplicate found " + msg.getSeqNr() );
        return;
      }

        if (log.isDebugEnabled()) {
          pushFwdLink(lastIp, p_id / 10000);
        }

//        processCSEvent(cs, p_id);

        log.debug(localAddr + " send packet on ch " + ch);
        RouteMcExORMsg newMsg = (RouteMcExORMsg) msg.clone();

        if (version == REACTIVE_VERSION) {
          newMsg.getOptions().remove(1);
        } else {
          newMsg.getOptions().remove(0);
        }
        newMsg.addOption(RouteMcExORMsg.OptionDataNoRoute.create(opt.getSeqNum(), nwArary));

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

        transmit(ipMsg, cs, ch);
      } else {
        if (version == REACTIVE_VERSION) {
          log.info(localAddr + "(" + JistAPI.getTime() + ") (relay-node) don't have route; searching for ... " + dest);
          //TODO extrem dirty hack
          NetMessage.Ip bufferPacket = new NetMessage.Ip(msg.getContent(), src, dest, Constants.NET_PROTOCOL_UDP, priority, ttl);
          self.insertBuffer(bufferPacket, anno);
          activeRequests.add(bufferPacket.getDst());
          discoverRoute(bufferPacket.getDst(), nextRequestId++);
        } else {
          log.error(routeMetric);
          log.error(localAddr + " drop message: no route available to " + dest);
          throw new RuntimeException("calculateCandidateSet failed!");
        }
      }
    }
  }

  private void pushFwdLink(NetAddress lastIp, int flowId) {

    RadioInterface.RFChannel channelLastHop = null;
    if ( (flooding != null) && null != flooding.getNodeHomeChannel(lastIp))
      channelLastHop = flooding.getNodeHomeChannel(lastIp);
    else if (!routeMetric.getHomeChannel(lastIp).equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL))
      channelLastHop = routeMetric.getHomeChannel(lastIp);

    FwdLink lnk = new FwdLink(lastIp, channelLastHop.getChannel(),
            localAddr, routeMetric.getHomeChannel(localAddr).getChannel());
    lnk.setFlowId(flowId);

    if (fwdLinks.get(lnk) == null)
      fwdLinks.put(lnk, new Integer(1));
    else
      fwdLinks.put(lnk, new Integer(((Integer) fwdLinks.get(lnk)).intValue() + 1));
  }

  /**
   * Checks whether we need to forward this flooding packet or not.
   *
   * @param floodMsgMc the Flooding packet.
   */
  private void forwardFlooding(RouteMcExORFlood.McFloodingMsg floodMsgMc) {

    if (seenFloodingBefore(floodMsgMc.getSrc(), floodMsgMc.getSeqNum())) {
      return;
    }

    // Otherwise forward the flooding packet

    // estimate the used channels
    List chInNBhood = flooding.estimateChannelsInNBhood();

    for (Iterator it = chInNBhood.iterator(); it.hasNext();) {
      Integer ch = (Integer) it.next();
      int delay = flooding.deferForward();
      JistAPI.sleep(Constants.MICRO_SECOND * delay);
      sendFloodingPacket(floodMsgMc, ch.intValue());
    }

    // Make a note of this request in the route request table
    addFloodingId(floodMsgMc.getSrc(), floodMsgMc.getSeqNum());
  }

  /**
   * Sends perdiodically {@link RouteMcExORFlood.McFloodingMsg} messages. Used by the proactive
   * routing protocol.
   */
  public void runFloodingSendHook() {
    log.warn(localAddr + "(" + JistAPI.getTime() + "): runFloodingSendHook; timeout.");

    long delay = flooding.calcNextSendPacket();

    // send probe packet
    RouteMcExORFlood.McFloodingMsg msg
            = (RouteMcExORFlood.McFloodingMsg) flooding.initFlooding();

    if (msg != null) {
      addFloodingId(msg.getSrc(), msg.getSeqNum());

      sendFloodingPacket(msg, msg.nextChannel);
    } else {
      // skip this flooding period (we haven't any neighbor)
    }

    // schedule next timeout
    JistAPI.sleep(Constants.MICRO_SECOND * delay);
    self.runFloodingSendHook();
  }

  /**
   * Sends a flooding packet via the given channel.
   *
   * @param msgMc   flooding packet
   * @param channel the channel
   */
  private void sendFloodingPacket(RouteMcExORFlood.McFloodingMsg msgMc, int channel) {

    NetMessage.Ip ipMsg = new NetMessage.Ip(msgMc, localAddr, NetAddress.ANY,
            Constants.NET_PROTOCOL_FLOODING,
            Constants.NET_PRIORITY_D_BESTEFFORT, (byte) 1);

    log.debug(localAddr + "(" + JistAPI.getTime() + "): forwarding flooding packet: "
            + msgMc.getSrc() + "/" + msgMc.getSeqNum() + " on ch " + channel);

    MessageAnno anno = new MessageAnno();
    //anno.put(MacInterface.ANNO_BITRATE, new Integer(msg.rate));
    //TODO make the freq dynamic
    anno.put(MessageAnno.ANNO_MAC_RF_CHANNEL, new RadioInterface.RFChannel(Constants.FREQUENCY_DEFAULT, channel));

    //msgMc.setNextChannel(channel);
    netEntity.send(ipMsg, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno);
  }


  /**
   * @see #calculateCandidateSet(NetAddress, NetAddress, List, boolean, NetAddress, byte[], RouteEntry[]}
   */
  public int calculateCandidateSet(RouteEntry[] route, NetAddress src, NetAddress dst, List cs,
                                   boolean preferHomeChannel, NetAddress lastIp, byte[] chArray,
                                   RouteEntry[] fallbackRoute) {

    if ((cSetSize == AODV_CS_SIZE) && (routeMetric.getChannels().length == 1)) {
      if (getCsetSelection() == CSET_SELECTION_OPTIMAL) {

        return calculateWithPositioning(dst, src, preferHomeChannel, chArray, cs);
      } else {
        // an ExOR with only one candidate bahaves like AODV
        NetAddressWithMetric nextHop;
        if ((route != null) && (route.length >= 2)) {
          nextHop = new NetAddressWithMetric(route[1].addr, route[1].metric);
  //      } else {
  //        nextHop = new NetAddressWithMetric(dst, 0);
        } else {
          throw new RuntimeException("route is null.");
        }
        cs.add(nextHop);

        log.info(localAddr + " Using [" + nextHop.ip + "]");

        return routeMetric.getHomeChannel(localAddr).getChannel();
      }
    } else {
      //
      // choose between the global candidate set selection algorithm and the local one
      //
      if (getCsetSelection() == CSET_SELECTION_OPTIMAL) {

        return calculateWithPositioning(dst, src, preferHomeChannel, chArray, cs);

      } else if ((getCsetSelection() == GLOBAL_CSET_SELECTION) && (!preferHomeChannel)) {
        //
        // Construct a CSetGraph
        Integer bestCh = csgraph.getNextCandidateSet(cs, src, dst, chArray);

        if (bestCh != null) {
          return bestCh.intValue();
        } else {
          throw new RuntimeException(localAddr + " Channel is NULL!");
        }
      } else {
        // local cset selection algorithm
        return calculateCandidateSet(src, dst, cs, preferHomeChannel, lastIp, chArray, fallbackRoute);
      }
    }
  }

  /**
   * Calculates the candidate set based on positioning information.
   */
  private int calculateWithPositioning(NetAddress dst, NetAddress src,
      boolean preferHomeChannel, byte[] chArray, List cs) {
    Hashtable peers = (Hashtable)pos_tbl.get(new Integer(localAddr.getId()));

    double dist_me_dst =
            ((Float)((Hashtable)pos_tbl.get(new Integer(localAddr.getId())))
                    .get(new Integer(dst.getId()))).doubleValue();

    Hashtable csSet = new Hashtable();
    double[] best_cs = OPTIMAL_CS_DISTANCE[cSetSize - 1];

    for (int c = 0; c < routeMetric.getChannels().length; c++) {
      for (int i = 0; i < best_cs.length; i++) {
        double req_distance = best_cs[i]; // find a node with this req_distance

        Enumeration keys = peers.keys();

        double _x = Double.MAX_VALUE;
        double _y = Double.MAX_VALUE;
        Integer best_cs_id = null;
        double route_m = Double.MAX_VALUE;
        while (keys.hasMoreElements()) {
          Integer key = (Integer)keys.nextElement();
          double dist_me_nb = ((Float)(peers.get(key))).doubleValue();
          NetAddress nb = new NetAddress(key.intValue());
          Integer home_ch = new Integer(flooding.getNodeHomeChannel(nb).getChannel());

          if (home_ch.intValue() != c)
            continue;

          //double diff_req_distance = Math.abs(req_distance - dist_me_nb);

          //List nb_route = routeMetric.queryRoute(nb, dst); // src, dst
          // calculate path metric
          //int dist_nb_dst = linkStat.getLinkTable().getRouteMetric(nb_route);
          double dist_nb_dst =
                  ((Float)((Hashtable)pos_tbl.get(new Integer(nb.getId())))
                          .get(new Integer(dst.getId()))).doubleValue();

          double x = Math.abs(dist_me_dst - (dist_me_nb + dist_nb_dst));
          double y = Math.abs(dist_me_nb - req_distance);

          if ( (x+y) < (_x+_y) ) {
            best_cs_id = key;
            _x = x;
            _y = y;
            route_m = dist_nb_dst;
          }
        }
        if (best_cs_id != null) {
          List csTmp;
          if (csSet.get(new Integer(c)) == null) {
            csSet.put(new Integer(c), new ArrayList());
          }
          csTmp = (List) csSet.get(new Integer(c));
          csTmp.add(new NetAddressWithMetric(new NetAddress(best_cs_id.intValue()), (int)route_m));
        }
      }
    }

    Integer bestChannel = chooseMostPromisingCs(csSet, src, preferHomeChannel, chArray);

    if (bestChannel != null) { // found a valid cs
      cs.addAll((List) csSet.get(bestChannel));

      return bestChannel.intValue();
    }
    return -1;
  }

  /**
   * Sends the given message ...
   *
   * @param msg the <code>RouteMcExORMsg</code> to be sent
   * @param cs  the (ordered) candidate set
   * @param ch  the channel
   */
  private void sendWithCandidateSet(NetMessage.Ip msg, List cs, int ch, int id,
      RouteEntry[] route) {
    // Slap on a ExOR Options header with the proper Source Route option
    RouteMcExORMsg ExORMsg = new RouteMcExORMsg(msg.getPayload());
    ExORMsg.setNextHeaderType(msg.getProtocol());

    // Make a note of this data packet
    addDataPacketId(localAddr, id);

    //
    // Add two options to this packet: rreply (fallback route) and data packet (exor routed)
    //
    // Fallback Route
    if (version == REACTIVE_VERSION) {
      if (route.length > 0) {
        ExORMsg.addOption(RouteMcExORMsg.OptionRouteReply.create(route));
      }
    }
    ExORMsg.addOption(RouteMcExORMsg.OptionDataNoRoute.create(id));

    if (log.isInfoEnabled()) {
      StringBuffer strRoute = new StringBuffer();
      for (int i = 0; i < route.length; i++)
        strRoute.append(route[i].addr).append(" ");
      log.info("SendWithRoute; len: " + route.length + " [" + strRoute
              + "]");
    }

    NetMessage.Ip ipMsg = new NetMessage.Ip(ExORMsg, msg.getSrc(), msg
            .getDst(), Constants.NET_PROTOCOL_MCEXOR, msg.getPriority(), msg
            .getTTL());

    log.info(localAddr + "(" + JistAPI.getTime() + ")" + " sending packet ("
            + localAddr + "," + id + ")");
    transmit(ipMsg, cs, ch);
  }

  /**
   * Sends the given message and looks for acknowledgement. If no
   * acknowledgement is forthcoming the message is retransmitted a limited
   * number of times.
   *
   * @param msg the message to send. The payload of this IP packet should be a
   *            <code>RouteMcExORMsg</code>, and it should not already
   *            contain an Acknowledgement Request.
   * @param cs  the (ordered) candidate set (NetAddress)
   * @param ch  the channel
   */
  private void transmit(NetMessage.Ip msg, List cs, int ch) {

    List macCs = new ArrayList();

    for (int i = 0; i < cs.size(); i++) {
      NetAddress ip = ((NetAddressWithMetric) cs.get(i)).ip;

      // resolv ethernet addresses
      MacAddress mac = (MacAddress) arp.get(ip);

      assert (mac != null);
      macCs.add(mac);
    }

    log.debug(localAddr + "(" + JistAPI.getTime() + "): McExOR::transmit on ch " + ch);

    MessageAnno anno = new MessageAnno();
    //anno.put(MacInterface.ANNO_BITRATE, new Integer(msg.rate));

    //TODO: make the freq dynamic
    anno.put(MessageAnno.ANNO_MAC_RF_CHANNEL, new RadioInterface.RFChannel(Constants.FREQUENCY_DEFAULT, ch));
    anno.put(MessageAnno.ANNO_MAC_CANDIDATES, macCs);

    // set via Net
    netEntity.send(msg, Constants.NET_INTERFACE_DEFAULT, MacAddress.NULL, anno);
  }

  /**
   * Sends the given message on my own home channel; this version is used in single
   * channel routing.
   *
   * @param msg the message to send. The payload of this IP packet should be a
   *            <code>RouteMcExORMsg</code>, and it should not already
   *            contain an Acknowledgement Request.
   * @param cs  the (ordered) candidate set (NetAddress)
   */
  private void transmit(NetMessage.Ip msg, List cs) {
    transmit(msg, cs, routeMetric.getHomeChannel(localAddr).getChannel());
  }

  /**
   * transmit the packet via source routing; used by route reply packets.
   *
   * @param msg  message to be send
   * @param dest the final destination
   */
  private void transmit(NetMessage.Ip msg, NetAddress dest) {

    RouteMcExORMsg exORMsg = (RouteMcExORMsg) msg.getPayload();
    RouteMcExORMsg.OptionSourceRouted sourceRoute = getSourceRoute(exORMsg);

    NetAddress nextHop;

    if (sourceRoute == null || sourceRoute.getNumSegmentsLeft() == 0) {
      nextHop = dest;
    }

    nextHop = nextRecipient(sourceRoute, dest);

    NetAddressWithMetric na = new NetAddressWithMetric(nextHop,
            INVALID_ROUTE_METRIC);

    List cs = new ArrayList();
    cs.add(na);

    // estimate RF channel of cs
    int nb_ch = routeMetric.getHomeChannel(na.ip).getChannel();

    Util.assertion(nb_ch != -1);

    log.info(localAddr + "(" + JistAPI.getTime() + "): sending unicast to next hop = " + cs.get(0) + " on ch " + nb_ch);

    transmit(msg, cs, nb_ch);
  }


  /**
   * This method calculates the candidate set for a packet with source address
   * {@param src} and destination {@param #dst} in regard to the used channels.
   *
   * @param src               the source address of the packet
   * @param dst               the final destination of the packet
   * @param rvalue            the list of candidates prioritized my their path metric towards
   *                          the final destination
   * @param preferHomeChannel indicates whether we should prefer the use of our home channel
   * @param lastIp            the ip address of the last hop
   */
  private int calculateCandidateSet(NetAddress src, NetAddress dst, List rvalue,
      boolean preferHomeChannel,NetAddress lastIp, byte[] chArray,
      RouteEntry[] fallbackRoute) {

    List candidates = new ArrayList();

    List route; // src, dst

    List neighbors = routeMetric.getNeighbors(src);

    route = routeMetric.queryRoute(src, dst, CS_MIN_METRIC); // src, dst

    // calculate my path metric to dst
    int myRouteMetric = routeMetric.getRouteMetric(route,
        INVALID_ROUTE_METRIC);

    // no route available
    if (myRouteMetric == -1)
      return -1;

    if (log.isInfoEnabled()) {
      int routeMetric = this.routeMetric.getRouteMetric(route,
          INVALID_ROUTE_METRIC);

      log.info("metric of shortest path is " + routeMetric);

      StringBuffer routeStr = new StringBuffer();
      for (int i = 0; i < route.size(); i++) {
        routeStr.append(route.get(i)).append(" ");
      }
      log.info("shortest path: " + routeStr.toString());
    }

    // for each of my neighbors calculate the shortest path to the destination
    calcShortestPathForEachNeighbor(neighbors, src, dst, myRouteMetric, candidates, preferHomeChannel, fallbackRoute);

    // group candidates by their home channel
    Hashtable csSet = createCsPerChannel(src, candidates);

    // choose the most promising candidate set
    Integer bestChannel = chooseMostPromisingCs(csSet, src, preferHomeChannel, chArray);

    if (bestChannel != null) { // found a valid cs

      List used_cs = (List) csSet.get(bestChannel);
      rvalue.addAll(used_cs);

      // algorithm to handle deafness in the multi channel case
      /*
      if (linkStat.getAllChannels().size() > 1) {
        // restore old canididates relay pref
        for (int i = 0; i < relay_pref_backup.size(); i++) {
          Tuple Tuple = (Tuple) relay_pref_backup.get(i);
          NetAddress addr = (NetAddress)Tuple.getX();
          Byte pref = (Byte)Tuple.getY();
          updateNodePref(addr, pref.byteValue());
        }
        relay_pref_backup.clear();

        // update candidates relay pref
        for (int i = 0; i < used_cs.size(); i++) {
          NetAddressWithMetric no = (NetAddressWithMetric) used_cs.get(i);

          byte relayPref = MacMcExOR.PREFERENCE_MAX;
          if (relayPreferences.get(no.ip) != null)
            relayPref = ((NodePref) relayPreferences.get(no.ip)).pref;

          updateNodePref(no.ip, (byte)(relayPref - 1));

          relay_pref_backup.add(new Tuple(no.ip, new Byte(relayPref)));
        }
      }*/

      //
      // sort candidates according to their metric as well as use some randomness
      //
      // TODO nugget candidate shuffling (but not within cs)
//      shuffleCandidates(rvalue);

      if (log.isInfoEnabled()) {
        StringBuffer str = new StringBuffer();
        str.append("Using [");
        for (int i = 0; i < rvalue.size(); i++) {
          str.append(((NetAddressWithMetric) rvalue.get(i)).ip);
          if (i < rvalue.size() - 1)
            str.append(", ");
        }
        str.append("] with ch " + bestChannel);
        log.info(localAddr + "(" + JistAPI.getTime() + "):" + str.toString());
      }

      return bestChannel.intValue();
    }

    return -1;
  }

  private void shuffleCandidates(List rvalue) {
    List oldcs = new ArrayList(rvalue);
    rvalue.clear();

    while (oldcs.size() > 0) {
      int cumRange = 0;
      int[] responsibilities = new int[oldcs.size()];
      for (int i = 0; i < oldcs.size(); i++) {
        NetAddressWithMetric cs = (NetAddressWithMetric) oldcs.get(i);
        if (cs.metric > 0)
          cumRange += INVALID_ROUTE_METRIC / cs.metric;
        else
          cumRange += INVALID_ROUTE_METRIC;
        responsibilities[i] = cumRange;
      }

      // search for random number between 0 and cumRange
      int ranNum = Constants.random.nextInt(cumRange);

      int curr = 0;
      for (int i = 0; i < responsibilities.length; i++) {
        int succ = responsibilities[i];
        if ((curr <= ranNum) && (succ > ranNum)) {
          NetAddressWithMetric cs = (NetAddressWithMetric) oldcs.get(i);
          log.info(cs);
          rvalue.add(cs);
          oldcs.remove(cs);
          break;
        }
        curr = responsibilities[i];
      }
    }
  }

  /**
   * This method chooses the most promising cset among all available candidate sets.
   *
   * @param csSet             the hashtable of available csets per channel
   * @param src               calculate the cset for this node
   * @param preferHomeChannel indicates whether we need to prefer the home channel
   */
  private Integer chooseMostPromisingCs(Hashtable csSet, NetAddress src,
      boolean preferHomeChannel, byte[] chArray) {

    Integer bestChannel = null;

    int currMinValue = Integer.MAX_VALUE;
    Enumeration chKeys = csSet.keys();
    int myHomeChannel = routeMetric.getHomeChannel(localAddr).getChannel();

    //
    // check the candidate set for each channel
    //
    while (chKeys.hasMoreElements()) {
      Integer chKey = (Integer) chKeys.nextElement();

      assert(chKey.intValue() != -1);

      List cs = (List) csSet.get(chKey);

      double pdiff = 1;
      double csCum = 0;

      byte cumPref = 0;

      boolean isSafeLastHop = false;
      for (int i = 0; i < cs.size(); i++) {
        //log.fatal(cs.get(i));
        // calculate link metric to my neighbors
        NetAddressWithMetric nbInfo = (NetAddressWithMetric) cs.get(i);

        csCum += nbInfo.metric;

        int nbMetric = routeMetric.getLinkMetricOld(src, nbInfo.ip);

        if ((nbInfo.metric == 0) && (nbMetric <= CS_MIN_METRIC_FOR_SAFE_NB))
          isSafeLastHop = true;

        double np = 1 - (100.0 / (double) nbMetric); // 1-p
        pdiff *= np;
      }

      // normiere csCum
      csCum /= cs.size();

      if (isSafeLastHop)
        csCum = 0;

      cumPref /= cs.size();

      double pcs = 1 - pdiff; // wahrscheinlichkeit, dass das paket den cset erreicht.

      //
      // algorithm to enforce channel switching
      //
      pcs = enforceChannelSwitch(chKey, chArray, pcs, routeMetric.getChannels().length);

      csCum = (1 / pcs) * csCum;

      // prefer candidates with the same channel
      if (preferHomeChannel && (myHomeChannel == chKey.intValue())) {
        if (pcs < 0.3)
          log.info(localAddr + "(" + JistAPI.getTime() + ") the prefered cs is quite bad; maybe the network is not dense");
        return chKey;
      }

      if (csCum < currMinValue) {
        currMinValue = (int) csCum;
        bestChannel = chKey;

        if (bestChannel.intValue() == -1)
          log.error("aa");
      }
    }

    // schuffle
    //return shuffleCandidateSets(prioCs, currMinValue);

    return bestChannel;
  }

  private double enforceChannelSwitch(Integer chKey, byte[] chArray, double pcs, int maxAvChannels) {

    if ((chArray == null) || (chArray.length == 0))
      return pcs;

    int nwCh = chKey.intValue();
    int chCount = 0;
    for (int i = chArray.length - 1; i >= 0 && i > chArray.length - maxAvChannels; i--) {
      byte usedCh = chArray[i];

      if (nwCh == usedCh) {
        chCount++;
      }
    }

    if (chCount > 0)
      pcs /= (chCount + 1);
    return pcs;

/*
      final double DOUBLE = 1.5;
      final double TRIPLE = 2.0;
      // A = home channel of the last forwarder
      // B = my home channel
      // C = home channel of the new candidate set
      int A = homeChannelOfLastNode;
      int B = myHomeChannel;
      int C = chKey.intValue();
      if (A != -1) {
        if (A == B) {
          if (B == C) {
            // the same channel will be used threefold
            pcs /= TRIPLE;
          } else { // B != C
            // the same channel will be used twice
            pcs /= DOUBLE;
          }
        } else { // A != B
          if (B == C) {
            // the same channel will be used twice
            pcs /= DOUBLE;
          } else { // B != C
            if (A == C) {
              // the same channel will be used twice
              pcs /= DOUBLE;
            } else {
              // nice run
            }
          }
        }
      }
*/
  }

  /**
   * Estimates the best channel to be used.
   *
   * @param prioCs The map of the csets
   * @return the best channel to be used
   */
  private Integer shuffleCandidateSets(List prioCs, int currMinValue) {

    final double DELTA = 1.3; //TODO
    int cumRange = 0;
    int[] responsibilities = new int[prioCs.size()];
    for (int i = 0; i < prioCs.size(); i++) {
      Tuple cs = (Tuple) prioCs.get(i);
      int m = ((Integer) cs.getY()).intValue();

      if (m > currMinValue * DELTA)
        cumRange += 1;
      else if (m > 0)
        cumRange += INVALID_ROUTE_METRIC / m;
      else
        cumRange += INVALID_ROUTE_METRIC;
      responsibilities[i] = cumRange;
    }

    // search for random number between 0 and cumRange
    int ranNum = Constants.random.nextInt(cumRange);

    int curr = 0;
    for (int i = 0; i < responsibilities.length; i++) {
      int succ = responsibilities[i];
      if ((curr <= ranNum) && (succ > ranNum)) {
        Tuple cs = (Tuple) prioCs.get(i);
        log.info(cs);
        // take this candidate set
        return (Integer) cs.getX();
      }
      curr = responsibilities[i];
    }
    return null;
  }


  /**
   * Helper method groups the potential neighbor nodes according to their home channel.
   *
   * @return a hashtable where the channel is the key and the value the is the candidate set.
   */
  private Hashtable createCsPerChannel(NetAddress src, List candidates) {

    Hashtable /* int (channel) -> List of NetAddressWithMetric */ csSet = new Hashtable();

    //
    // group potential candidates according to their homechannels
    //
    for (int i = 0; i < candidates.size(); i++) {
      NetAddressWithMetric netAddressWithMetric = (NetAddressWithMetric) candidates.get(i);

      NetAddress nb = netAddressWithMetric.ip;
      RadioInterface.RFChannel nbHomeChannel = routeMetric.getHomeChannel(nb);

      if (nbHomeChannel.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL)) {
        log.warn(localAddr + " home ch of nb unknown; lookup flooding cache");
        nbHomeChannel = flooding.getNodeHomeChannel(nb);
      }

      Util.assertion(!nbHomeChannel.equals(RadioInterface.RFChannel.INVALID_RF_CHANNEL));

      List csTmp;
      if (csSet.get(nbHomeChannel) == null) {
        csSet.put(nbHomeChannel, new ArrayList());
      }
      csTmp = (List) csSet.get(nbHomeChannel);
      csTmp.add(netAddressWithMetric);

    }

    //
    // find safe nb for each cs
    //
    int metricToBestNb = INVALID_ROUTE_METRIC;
    int routeMetricOfBestNB = Integer.MAX_VALUE;
    NetAddressWithMetric safeNb = null, safeNbBck = null;

    Enumeration chKeys = csSet.keys();
    while (chKeys.hasMoreElements()) {
      Integer chKey = (Integer) chKeys.nextElement();
      List cs = (List) csSet.get(chKey);

      // calculate for each candidate set the safe neighbor
      for (int i = 0; i < cs.size(); i++) {
        NetAddressWithMetric netAddressWithMetric = (NetAddressWithMetric) cs.get(i);

        NetAddress nb = netAddressWithMetric.ip;
        int routeMetric = netAddressWithMetric.metric;

        // calculate the metric to this neighbor
        int nbMetric = this.routeMetric.getLinkMetricOld(src, nb);

        // remember safe candidate per channel
        if ( (routeMetric < routeMetricOfBestNB)
                && (nbMetric <= CS_MIN_METRIC_FOR_SAFE_NB) ) {
          routeMetricOfBestNB = routeMetric;
          safeNb = netAddressWithMetric;
        }

        if (nbMetric < metricToBestNb) {
          metricToBestNb = nbMetric;
          safeNbBck = netAddressWithMetric;
        }

        // backup algorithm
        if (safeNb == null) {
          safeNb = safeNbBck;
        }
      } // end

      Collections.sort(cs);

      // strip candidates count to CS_SIZE
      ArrayList ncs = new ArrayList();
      int min_size = Math.min(cs.size(), cSetSize/* - 1*/);

      StringBuffer str = new StringBuffer();
      str.append("CS (" + chKey + "): [");
      for (int j = 0; j < min_size; j++) {
        str.append(cs.get(j)).append(", ");
        ncs.add(cs.get(j));
      }
      // check whether the safe nb is in the list, otherwise add
      if ((safeNb != null) && !(ncs.contains(safeNb))) {
        log.info(localAddr + " safe nb added: " + safeNb.ip + " metric to me: " + metricToBestNb);
        str.append(safeNb);
        // place safe nb on the last position
        ncs.set(min_size - 1, safeNb);
      }
      str.append("]");
      log.info(localAddr + "(" + JistAPI.getTime() + "): createCsPerChannel; ch = " + chKey + " cset = " + str);

      //
      // check whether the node in the candidate set are well connected to each other according to their
      // priority; this algorithm tries to prevent duplicates in the network

      if (getCsetSelection() == CSET_SELECTION_BESTPATHS) {
        ncs = chooseCsBestPaths(cs, ncs);
      } else if (getCsetSelection() == CSET_SELECTION_AVERAGING) {
        ncs = chooseCsAveraging(cs, ncs);
      }
      Util.assertion(chKey.intValue() != -1);
      csSet.put(chKey, ncs);

      safeNb = safeNbBck = null;
      metricToBestNb = INVALID_ROUTE_METRIC;
      routeMetricOfBestNB = Integer.MAX_VALUE;
    }

    return csSet;
  }

  private ArrayList chooseCsBestPaths(List cs, ArrayList ncs) {
    if (null == ncs || this.cSetSize < 2 || cs.size() <= this.cSetSize)
      return (ncs);

    NetAddressWithMetric[] nbs = new NetAddressWithMetric[this.cSetSize];
    int[] nbs_metric = new int[this.cSetSize];
    Arrays.fill(nbs, null);
    Arrays.fill(nbs_metric, Integer.MAX_VALUE);

    // iterate over candidate set
    for (int i = 0; i < cs.size(); i++) {
      NetAddressWithMetric node = (NetAddressWithMetric) cs.get(i);

      // calculate the distance between two candidates
      int distance = routeMetric.getLinkMetricOld(this.localAddr, node.ip) + node.metric;

      for (int j = 0; j < nbs_metric.length; j++) {
        if (null == nbs[j]) {
          nbs[j] = node;
          nbs_metric[j] = distance;
          break;
        }
        if (nbs[j].equals(node)) {
          break;
        }
        if (distance < nbs_metric[j]) {
          for (int k=nbs_metric.length-2; k >=j; k--) {
            nbs[k+1] = nbs[k];
            nbs_metric[k+1] = nbs_metric[k];
          }
          nbs[j] = node;
          nbs_metric[j] = distance;
          break;
        }
      }
    }

    ArrayList nncs = new ArrayList();

    for (int j=0; j < nbs.length; j++) {
      if (null != nbs[j] && !nncs.contains(nbs[j]))
        nncs.add(nbs[j]);
    }

    Collections.sort(nncs);
    return (nncs);
  }

  /**
   * TODO remove
   */
  private ArrayList chooseCsAveraging(List cs, ArrayList ncs) {
    if (null == ncs || ncs.size() < 2 || this.cSetSize < 3 || cs.size() <= this.cSetSize)
      return (ncs);

    ArrayList nncs = new ArrayList();

    NetAddressWithMetric nb_highest = (NetAddressWithMetric) ncs.get(0);
    NetAddressWithMetric nb_lowest = (NetAddressWithMetric) ncs.get(ncs.size() - 1);
    nncs.add(nb_highest);
    nncs.add(nb_lowest);

    // initial replacement
    int replacements = this.cSetSize-2;
    NetAddressWithMetric[] replacmentNodes = new NetAddressWithMetric[replacements];
    int minDistReplacement = java.lang.Integer.MAX_VALUE;

    NetAddressWithMetric[] nodes = new NetAddressWithMetric[replacements];
    int[] idx = new int[replacements];
    Arrays.fill(idx, 0);

    // iterate over candidate set
    boolean finished = false;
    while (!finished) {
      boolean cont = false;
      int distance = 0;

      for (int j = 0; j < replacements-1; j++) {
        for (int k = j+1; k < replacements; k++) {
          if (idx[j] == idx[k])
            cont = true;
          break;
        }
        if (cont == true)
          break;
      }

      for (int j = 0; false == cont && j < replacements; j++) {
        nodes[j] = (NetAddressWithMetric) cs.get(idx[j]);
        if (nncs.contains(nodes[j])) {
          cont = true;
          break;
        }
        if (0 == j)
          distance += routeMetric.getLinkMetricOld(nb_lowest.ip, nodes[j].ip);
        else
          distance += routeMetric.getLinkMetricOld(nodes[j-1].ip, nodes[j].ip);
      }

      if (!cont) {
        distance += routeMetric.getLinkMetricOld(nodes[replacements-1].ip, nb_highest.ip);
        if (distance < minDistReplacement) {
          minDistReplacement = distance;
          System.arraycopy(nodes, 0, replacmentNodes, 0, nodes.length);
        }
      }

      idx[0]++;
      for (int i = 0; i < idx.length; i++) {
        if (idx[i] >= cs.size()) {
          idx[i] = 0;
          if (i+1 < idx.length)
            idx[i+1]++;
          else
            finished = true;
        }
      }
    }

    if (null != replacmentNodes) {
      nncs.addAll(Arrays.asList(replacmentNodes));
    }

    Collections.sort(nncs);
    return (nncs);
  }

  /**
   * Helper method calculates for each neighbor node the shortest path to the destination.
   */
  private void calcShortestPathForEachNeighbor(List neighbors, NetAddress src,
      NetAddress dst, int myRouteMetric, List candidates,
      boolean preferHomeChannel, RouteEntry[] fallbackRoute) {
    NetAddress nb;
    List route;

    RadioInterface.RFChannel myHomeChannel = routeMetric.getHomeChannel(localAddr);

    //
    // In the reactive version of the route discovery algorithm it is important
    // that only nodes which are close to the fallback route are selected.
    //

    //
    // 1. estimate all node in the fallback route closer to the final destination than me.
    //
    Set fallbacknodes = new HashSet();
    if ( (version == REACTIVE_VERSION) && (fallbackRoute != null) ) {
      for (int i = 0; i < fallbackRoute.length; i++) {
        NetAddress routeEntry = fallbackRoute[i].addr;

        route = routeMetric.queryRoute(routeEntry, dst, CS_MIN_METRIC); // routeEntry.addr, dst

        // calculate path metric
        int routeMetric = this.routeMetric.getRouteMetric(route,
            INVALID_ROUTE_METRIC);

        if ((routeMetric == -1) || (routeMetric > myRouteMetric)) {
          // skip neighbors with worser route metric to destination
          continue;
        }
        fallbacknodes.add(routeEntry);
      }
    }

    for (int i = 0; i < neighbors.size(); i++) {
      nb = (NetAddress) neighbors.get(i);

      // calculate the metric to this neighbor
      int nbMetric = routeMetric.getLinkMetricOld(src, nb);

      // skip too bad neighbors
      if (nbMetric > CS_MIN_METRIC) {
        continue;
      }

      if ( (version == REACTIVE_VERSION) && (fallbackRoute != null) ) {

        List nbsOfCurrNode = routeMetric.getNeighbors(nb);

        // check if at least one neighbor of this node is adjacent to at least one node in the fallback set
        outer : for (Iterator it = fallbacknodes.iterator(); it.hasNext();) {
          NetAddress fbnode = (NetAddress) it.next();

          for (int j = 0; j < nbsOfCurrNode.size(); j++) {
            NetAddress nbCurrNode = (NetAddress)nbsOfCurrNode.get(j);
            if (fbnode.equals(nbCurrNode)) {
              log.debug("nb " + nb + " is close enough to fallback route ");
              break outer;
            }
          }
        }
      }

      route = routeMetric.queryRoute(nb, dst, CS_MIN_METRIC); // src, dst

      // calculate path metric
      int routeMetric = this.routeMetric.getRouteMetric(route,
          INVALID_ROUTE_METRIC);

      RadioInterface.RFChannel nbHomeChannel = this.routeMetric.getHomeChannel(nb);

      // prefer always candidates with the same channel
      if (preferHomeChannel && (myHomeChannel.equals(nbHomeChannel))) {
        // candidates on the homechannel are always prefered
      } else if ((routeMetric == -1) || (routeMetric > myRouteMetric)) { //TODO >=
        // skip neighbors with worser route metric to destination
        continue;
      }

      // add potential neighbor node
      candidates.add(new NetAddressWithMetric(nb, routeMetric));
    }
  }

  /**
   * Called at start-up time
   */
  public void start() {

    /* schedule linkstat (link probe) */
    long delay = Math.abs(Constants.random.nextLong() % this.floodingPeriod);

    /* schedule first flooding */
    if ((version == PROACTIVE_VERSION) && (floodingEnabled)) {
      delay = flooding.getOffset() + flooding.getJitter(flooding.getPeriod());
      // schedule next timeout
      log.debug("start runFloodingSendHook in " + delay + " millis");
      JistAPI.sleep(Constants.MILLI_SECOND * delay);
      self.runFloodingSendHook();
    }
  }

  /**
   * Sends a flooding packet.
   *
   * @param msg flooding packet
   */
  protected void sendFloodingPacket(Message msg) {

    NetMessage.Ip ipMsg = new NetMessage.Ip(msg, localAddr, NetAddress.ANY,
            Constants.NET_PROTOCOL_FLOODING,
            Constants.NET_PRIORITY_D_BESTEFFORT, (byte) 1);

    MessageAnno anno = new MessageAnno();
    netEntity.send(ipMsg, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno );
  }

  private void handleFloodingPacket(RouteMcExORFlood.McFloodingMsg msgMc) {
    flooding.handleMsg(msgMc);
  }

  /**
   * Sends a Route Reply to a node that recently sent us a Route Request.
   *
   * @param opt the Route Request option
   * @param src the originator of the Route Request
   */
  private void sendRouteReply(RouteMcExORMsg.OptionRouteRequest opt,
                              NetAddress src, int cumMetric) {

    //log.info(localAddr + ": sendRouteReply " + JistAPI.getTime());

    RouteEntry[] routeToHere = new RouteEntry[opt.getNumAddresses() + 2];

    byte m = convertMetricFromInternalToExternal(INVALID_ROUTE_METRIC);
    routeToHere[0] = new RouteEntry(src, m);

    NetAddress prevNode = src;
    for (int i = 1; i < routeToHere.length - 1; i++) {
      routeToHere[i] = opt.getAddress(i - 1);
      prevNode = routeToHere[i].addr;
    }

    int metric = routeMetric.getLinkMetricOld(prevNode, localAddr);
    byte byteMetric = convertMetricFromInternalToExternal(metric);

    routeToHere[routeToHere.length - 1] = new RouteEntry(localAddr, byteMetric);

    // reverse route
    StringBuffer str_route = new StringBuffer();
    RouteEntry[] routeFromHere = new RouteEntry[routeToHere.length - 2];
    for (int i = 0; i < routeFromHere.length; i++) {
      routeFromHere[i] = routeToHere[routeToHere.length - i - 2];
      str_route.append(routeFromHere[i].addr);
      if (i < routeFromHere.length - 1) {
        str_route.append(",");
      }
    }

    // Add a Route Reply option indicating how to get here from the
    // source and a Source Route option indicating how to get to the
    // source from here.
    RouteMcExORMsg reply = new RouteMcExORMsg(null);
    reply.addOption(RouteMcExORMsg.OptionRouteReply.create(routeToHere));

    /*
    if (routeFromHere.length > 0) {
      reply.addOption(RouteMcExORMsg.OptionSourceRouted.create(0,
              routeFromHere.length, routeFromHere));
    }*/
    //
    // reactive ExOR version; add data packet option (no route)
    //TODO what about the id?
    int id = incSeq();
    reply.addOption(RouteMcExORMsg.OptionDataNoRoute.create(id));

    NetMessage.Ip replyMsg = new NetMessage.Ip(reply, localAddr, src,
            Constants.NET_PROTOCOL_MCEXOR, Constants.NET_PRIORITY_D_BESTEFFORT,
            Constants.TTL_DEFAULT);

    JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));

    /*
    List cs = new ArrayList();

    NetAddressWithMetric na = new NetAddressWithMetric(
            routeToHere[routeToHere.length - 2].addr,
            routeToHere[routeToHere.length - 2].metric);

    cs.add(na);

    // estimate RF channel of cs
    int nb_ch = routeMetric.getHomeChannel(na.ip);

    Util.assertion(nb_ch != -1);

    transmit(replyMsg, cs, nb_ch);
    */

    RouteEntry[] route = getRouteFromLinkTable(src);

    // calculate candidate set
    List cs = new ArrayList();
    int ch = calculateCandidateSet(route, localAddr, src, cs, true, null, null, route);

    if (cs.size() < cSetSize)
      log.warn(localAddr + "( " + JistAPI.getTime() + " ): CSSIZE is smaller than optimal: "
              + cs.size() + " < " + cSetSize);

    log.info(localAddr + "( " + JistAPI.getTime() + " ): sendRouteReply (m="
            + cumMetric + ",[" + str_route + "], id=" + id + " ) to=" + cs.get(0) + "ch=" + ch);

    transmit(replyMsg, cs, ch);
  }

  /**
   * Propagates a Route Request to all nodes within range.
   *
   * @param msg        the message containing the Route Request
   * @param opt        the Route Request option
   * @param optBuf     the bytes of the Route Request option
   * @param src        the originator of the Route Request
   * @param dst        the destination of the Route Request (usually broadcast)
   * @param protocol   the IP protocol of the message
   * @param priority   the IP priority of the message
   * @param ttl        the IP time to live of the message
   * @param id         the IP identification of the message
   * @param fragOffset the IP fragmentation offset of the message
   */
  private void forwardRequest(RouteMcExORMsg msg,
                              RouteMcExORMsg.OptionRouteRequest opt, byte[] optBuf, NetAddress src,
                              NetAddress dst, short protocol, byte priority, byte ttl, short id,
                              short fragOffset) {
    // If I've already forwarded this request, ignore it
    for (int i = 0; i < opt.getNumAddresses(); i++) {
      if (localAddr.equals(opt.getAddress(i).addr))
        return;
    }

    // To do in future: Check the Route Cache to see if we know a route to
    // the
    // destination

    NetAddress prevNode = src;

    // Clone the message, add this node's address to the Source Route
    // option,
    // and retransmit it.
    RouteMcExORMsg newRequest = (RouteMcExORMsg) msg.clone();
    List newOptions = newRequest.getOptions();
    newOptions.remove(optBuf);
    RouteEntry[] newAddresses = new RouteEntry[opt.getNumAddresses() + 1];
    for (int i = 0; i < newAddresses.length - 1; i++) {
      newAddresses[i] = opt.getAddress(i);
      prevNode = newAddresses[i].addr;
    }

    int metric = routeMetric.getLinkMetricOld(prevNode, localAddr);

    if (metric > MAX_LINK_METRIC_FOR_RREQ_FORWARDING) {
      log.debug("skip RREQ because of junk link");
      return;
    }
    if (log.isDebugEnabled())
      log.debug(routeMetric);

    // TODO: hack
    if (metric == 0)
      metric = INVALID_ROUTE_METRIC;

    log.debug(localAddr + ": forwardRequest: update metric " + prevNode
            + " " + localAddr + " " + metric + " " + JistAPI.getTime());

    byte byteMetric = convertMetricFromInternalToExternal(metric);

    // TODO Is this the right pos for the metric?
    newAddresses[newAddresses.length - 1] = new RouteEntry(localAddr,
            byteMetric);

    newRequest.addOption(RouteMcExORMsg.OptionRouteRequest.create(
            opt.getId(), opt.getTargetAddress(), newAddresses));

    NetMessage.Ip newRequestIp = new NetMessage.Ip(newRequest, src, dst,
            protocol, priority, (byte) (ttl - 1), id, fragOffset);

//    JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));

//    netEntity.send(newRequestIp, Constants.NET_INTERFACE_DEFAULT,
//            MacAddress.ANY);

    // estimate the used channels
    List chInNBhood = getHomeChannels();

    for (Iterator it = chInNBhood.iterator(); it.hasNext();) {
      RadioInterface.RFChannel ch = (RadioInterface.RFChannel) it.next();

      JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));

      log.info(localAddr + "(" + JistAPI.getTime() + "): send RREQ packet: "
              + newRequestIp.getSrc() + " on ch " + ch);

      MessageAnno anno = new MessageAnno();
      //TODO make the freq dynamic
      anno.put(MessageAnno.ANNO_MAC_RF_CHANNEL, ch);
      netEntity.send(newRequestIp, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno);
    }
  }

  /**
   * Processes an incoming Route Request option. If this request has been seen
   * recently, it is ignored. Otherwise, if this node knows a route to the
   * desired destination, a Route Reply is sent to the originator of the
   * request. Otherwise, the request is propagated to all nodes within range.
   *
   * @param msg        the <code>RouteMcExORMsg</code> containing the request
   * @param opt        the Route Request option
   * @param optBuf     the bytes of the Route Request option
   * @param src        the address of the originator of the Route Request
   * @param dst        the destination address of this request (usually broadcast)
   * @param protocol   the IP protocol of this Route Request (usually ExOR)
   * @param priority   the IP priority of this Route Request
   * @param ttl        the IP time to live of this Route Request
   * @param id         the IP identification of this Route Request
   * @param fragOffset the IP fragmentation offset of this Route Request
   */
  private void handleRequest(RouteMcExORMsg msg,
                             RouteMcExORMsg.OptionRouteRequest opt, byte[] optBuf, NetAddress src,
                             NetAddress dst, short protocol, byte priority, byte ttl, short id,
                             short fragOffset) {

    // learn from this packet; update link table
    int cumMetric = learnFromRreq(opt, src);

    // If this request came from this node, ignore it
    if (localAddr.equals(src))
      return;

    // estimate route metric; do not reply to bad routes
    short rreq_id = opt.getId();

    // If we've seen this request lately, ignore it
    // TODO AZU: permit reply storm
    if (seenRequestLately(src, rreq_id, cumMetric)) {
      log.debug(localAddr + " I have seen the RREQ lately; drop it");
      return;
    }

    if (localAddr.equals(opt.getTargetAddress())) {
      // They're looking for this node, so send a reply
      sendRouteReply(opt, src, cumMetric);
    } else {
      // Otherwise propagate the request
      forwardRequest(msg, opt, optBuf, src, dst, protocol, priority, ttl,
              id, fragOffset);
    }

    // Make a note of this request in the route request table
    addRequestId(src, rreq_id, cumMetric);
  }

  /**
   * @param opt
   */
  private int learnFromRreq(RouteMcExORMsg.OptionRouteRequest opt, NetAddress src) {

    int cumMetric = 0;
    // learn from route request
    RouteEntry curr;
    NetAddress prev = src;
    for (int i = 0; i < opt.getNumAddresses() - 1; i++) {
      curr = opt.getAddress(i);
      //next = opt.getAddress(i + 1);
      if (localAddr.equals(curr.addr))
        break;
      int metric = convertMetricFromExternalToInternal(curr.metric);
      log.debug(localAddr + " learn from rreq: update " + prev + " to " + curr.addr + " with " + metric);

      routeMetric.updateBothLinks(prev, curr.addr, metric, false);
      prev = curr.addr;
      cumMetric += metric;
    }
    return cumMetric;
  }

  /**
   * Processes an incoming Route Reply. The new route is added to the Route
   * Cache if it is useful and not already in the Route Cache.
   *
   * @param msg   the <code>RouteMcExORMsg</code> containing the Route Reply
   * @param reply the Route Reply option
   */
  private RouteEntry[] handleReply(RouteMcExORMsg msg,
                           RouteMcExORMsg.OptionRouteReply reply) {
    NetAddress dest;
    RouteRequestTableEntry entry;

    log.info(localAddr + "( " + JistAPI.getTime() + " ): handleReply: " + JistAPI.getTime() + " " + msg.getSeqNr());

    // Update the Route Request Table
    dest = reply.getAddress(reply.getNumAddresses() - 1).addr;
    entry = (RouteRequestTableEntry) routeRequestTable.get(dest);
    if (entry != null)
      entry.numRequestsSinceLastReply = 0;

    activeRequests.remove(dest);

    RouteEntry[] route = new RouteEntry[reply.getNumAddresses()];
    // Add the route to our Route Cache
    for (int i = 0; i < reply.getNumAddresses(); i++) {
      route[i] = reply.getAddress(i);
    }

    // InsertRouteCache(dest, route);
    addRouteToLinkTable(dest, route);

    return route;
  }

  /**
   * TODO: No we need this???
   * <p/>
   * Determines the intended next recipient of a packet with the given source
   * route option and IP destination.
   *
   * @param sourceRoute the Source Route option (or <code>null</code> if none)
   * @param dst         the destination IP address
   * @return the address of the next recipient of the message. If the Source
   *         Route option is invalid in some way, <code>null</code> can be
   *         returned.
   */
  private NetAddress nextRecipient(RouteMcExORMsg.OptionSourceRouted sourceRoute,
                                   NetAddress dst) {
    if (sourceRoute == null)
      return dst;

    int curSegment = sourceRoute.getNumAddresses()
            - sourceRoute.getNumSegmentsLeft();

    if (curSegment < sourceRoute.getNumAddresses()) {
      return sourceRoute.getAddress(curSegment).addr;
    } else if (curSegment == sourceRoute.getNumAddresses()) {
      return dst;
    } else {
      return null;
    }
  }

  /**
   * Forwards a source routed packet (e.g. route reply)
   */
  private void forwardSourceRoutedPacket(RouteMcExORMsg msg,
                                         RouteMcExORMsg.OptionSourceRouted opt, byte[] optBuf, NetAddress src,
                                         NetAddress dest, short protocol, byte priority, byte ttl, short id,
                                         short fragOffset) {

    log.info(localAddr + ": forward src routed packet (e.g. route reply): " + JistAPI.getTime());

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

    // Check if I am the intended next recipient of this packet
    if (localAddr.equals(nextRecipient(opt, dest))) {
      RouteEntry[] route = new RouteEntry[opt.getNumAddresses()];
      for (int i = 0; i < route.length; i++) {
        route[i] = opt.getAddress(i);
      }

      RouteMcExORMsg newMsg = (RouteMcExORMsg) msg.clone();
      List newOptions = newMsg.getOptions();
      newOptions.remove(optBuf);
      newMsg.addOption(RouteMcExORMsg.OptionSourceRouted.create(opt
              .isFirstHopExternal(), opt.isLastHopExternal(), opt
              .getSalvageCount(), opt.getNumSegmentsLeft() - 1, route));

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

      transmit(ipMsg, dest);
    }
  }

  /**
   * Processes an incoming Route Error option. If this error was intended for
   * this node and indicates that a particular node is unreachable, then the
   * Route Cache will be updated to no longer use the broken links, and new
   * Route Discoveries may be initiated as a result. NODE_UNREACHABLE is the
   * only kind of error that is currently handled.
   *
   * @param opt the Route Error option
   */
  private void handleError(RouteMcExORMsg.OptionRouteError opt) {
    switch (opt.getErrorType()) {
      // This is the only error type I care about
      case RouteMcExORMsg.ERROR_NODE_UNREACHABLE:
        byte[] unreachableAddrBytes = new byte[4];
        opt.getTypeSpecificInfoBytes(unreachableAddrBytes, 4);
        NetAddress unreachableAddr = new NetAddress(unreachableAddrBytes, 0);

        // Remove every path from the route cache that makes use of this
        // link. (How expensive is this?)
        // RemoveCachedLink(opt.getSourceAddress(), unreachableAddr);
        removeLinkFromLinkTable(opt.getSourceAddress(), unreachableAddr);
        break;

      default:
        break;
    }
  }

  /**
   * Handles each of the options in a given ExOR header.
   *
   * @param msg        the message containing the ExOR header
   * @param src        the IP source address of the message
   * @param dst        the IP destination address of the message
   * @param protocol   the IP protocol of the message
   * @param priority   the IP priority of the message
   * @param ttl        the IP time to live of the message
   * @param id         the IP identification of the message
   * @param fragOffset the IP fragmentation offset of the message
   * @param lastHop    the MAC address of the last hop
   */
  private void processOptions(RouteMcExORMsg msg, MessageAnno anno,
      NetAddress src, NetAddress dst, short protocol, byte priority, byte ttl,
      short id, short fragOffset, MacAddress lastHop) {
    Iterator iter = msg.getOptions().iterator();
    RouteMcExORMsg.OptionDataNoRoute data = null;
    RouteMcExORMsg.OptionSourceRouted route = null;

    RouteEntry[] lastFallbackRoute = null;

    while (iter.hasNext()) {
      byte[] optBuf = (byte[]) iter.next();
      RouteMcExORMsg.Option opt = RouteMcExORMsg.Option.create(optBuf, 0);

      if (opt == null) {
        // This should never happen in the simulation
        throw new RuntimeException("Unrecognized ExOR Option");
      }

      switch (opt.getType()) {
        case RouteMcExORMsg.OPT_ROUTE_REQUEST:
          handleRequest(msg, (RouteMcExORMsg.OptionRouteRequest) opt,
                  optBuf, src, dst, protocol, priority, ttl, id,
                  fragOffset);
          break;

        case RouteMcExORMsg.OPT_ROUTE_REPLY:
          lastFallbackRoute = handleReply(msg, (RouteMcExORMsg.OptionRouteReply) opt);
          break;

        case RouteMcExORMsg.OPT_SOURCE_ROUTED: // route reply packets are source routed
          route = (RouteMcExORMsg.OptionSourceRouted) opt;

          forwardSourceRoutedPacket(msg, route, optBuf, src, dst,
                  protocol, priority, ttl, id, fragOffset);
          break;

        case RouteMcExORMsg.OPT_DATA_NO_ROUTE: // data packets are routed opportunistic
          data = (RouteMcExORMsg.OptionDataNoRoute) opt;

          forwardPacket(msg, anno, data, optBuf, src, dst, protocol, priority,
                  ttl, id, fragOffset, lastHop, lastFallbackRoute);

          lastFallbackRoute = null;
          break;

        case RouteMcExORMsg.OPT_ROUTE_ERROR:
          handleError((RouteMcExORMsg.OptionRouteError) opt);
          break;

        //case RouteMcExORMsg.OPT_BACKUP_ROUTE:
        //  break;

          // case RouteMcExORMsg.OPT_PAD1:
        case RouteMcExORMsg.OPT_PADN:
          break;

        default:
          // Possible problem: The processing of unrecognized options
          // should
          // probably occur *before* the processing of any other options.
          // This will never arise in the simulation, though.
          switch ((opt.getType() & 0x60) >> 5) {
            case RouteMcExORMsg.UNRECOGNIZED_OPT_IGNORE:
              // Ignore this option
              break;

            case RouteMcExORMsg.UNRECOGNIZED_OPT_REMOVE: {
              // Remove this option from the packet
              RouteMcExORMsg newMsg = (RouteMcExORMsg) msg.clone();
              List options = newMsg.getOptions();
              options.remove(optBuf);
              msg = newMsg;
              break;
            }

            case RouteMcExORMsg.UNRECOGNIZED_OPT_MARK: {
              // Set a particular bit inside the option
              RouteMcExORMsg newMsg = (RouteMcExORMsg) msg.clone();
              byte[] newOptBuf = new byte[optBuf.length];
              System.arraycopy(optBuf, 0, newOptBuf, 0, optBuf.length);
              newOptBuf[2] |= 0x80;

              List options = newMsg.getOptions();
              options.remove(optBuf);
              options.add(newOptBuf);
              msg = newMsg;
              break;
            }

            case RouteMcExORMsg.UNRECOGNIZED_OPT_DROP:
              // Drop the packet
              return;

            default:
              throw new RuntimeException("Should never reach this point");
          }

          break;
      }
    }
  }

  /**
   * Initiates a Route Discovery for the given address. Messages containing
   * Route Request headers are broadcast to all nodes within range.
   *
   * @param dest      the address to which we desire a route
   * @param requestId the ID number of the request to be performed.
   *                  <code>discoverRoute</code> should always be invoked with a
   *                  unique value in this parameter.
   */
  public void discoverRoute(NetAddress dest, short requestId) {

    RouteRequestTableEntry entry = (RouteRequestTableEntry) routeRequestTable
            .get(dest);

    if (entry == null) {
      entry = new RouteRequestTableEntry();
      routeRequestTable.put(dest, entry);
    }

    // Check to see if we're allowed to make a route request at this time
    if ((entry.numRequestsSinceLastReply == 0)
            || (entry.lastRequestTime + entry.timeout <= JistAPI.getTime())) {
      if (!activeRequests.contains(dest))
        return;

      String discoverstr = "Discover Route";
      if (entry.numRequestsSinceLastReply > 0)
        discoverstr = "Re-Discover Route ( " + entry.numRequestsSinceLastReply + " )";

      log.info(localAddr + "(" + JistAPI.getTime() + "): " + discoverstr + ": " + JistAPI.getTime());

      RouteMcExORMsg routeRequest = new RouteMcExORMsg(null);
      routeRequest.addOption(RouteMcExORMsg.OptionRouteRequest.create(
              requestId, dest, new RouteEntry[0]));

      NetMessage.Ip routeRequestMsg = new NetMessage.Ip(routeRequest,
              localAddr, NetAddress.ANY, Constants.NET_PROTOCOL_MCEXOR,
              Constants.NET_PRIORITY_D_BESTEFFORT, Constants.TTL_DEFAULT);

      // estimate the used channels
      List chInNBhood = getHomeChannels();

      for (Iterator it = chInNBhood.iterator(); it.hasNext();) {
        RadioInterface.RFChannel ch = (RadioInterface.RFChannel) it.next();
        JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));

        log.info(localAddr + "(" + JistAPI.getTime() + "): send RREQ packet: "
                + routeRequestMsg.getSrc() + " on ch " + ch);

        MessageAnno anno = new MessageAnno();
        //TODO: make the freq dynamic
        anno.put(MessageAnno.ANNO_MAC_RF_CHANNEL, ch);
        //msgMc.setNextChannel(channel);
        netEntity.send(routeRequestMsg, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno );
      }

//      netEntity.send(routeRequestMsg, Constants.NET_INTERFACE_DEFAULT,
//              MacAddress.ANY);

      entry.lastRequestTime = JistAPI.getTime();

      // Double timeout and retransmit route request if no response
      // after timeout elapses
      if (entry.numRequestsSinceLastReply > 0)
        entry.timeout *= 2;

      if (entry.timeout < MAX_REQUEST_PERIOD) {
        JistAPI.sleep(entry.timeout);
        //self.discoverRoute(dest, requestId);
        //TODO: we need to increment the id in case of rediscoveries; otherwise the newly created RREQs will not be forwarded.
        self.discoverRoute(dest, nextRequestId++);
      }

      entry.numRequestsSinceLastReply++;
    }
  }

  private List getHomeChannels() {
    List ret = new ArrayList();
    List neighbors = routeMetric.getNeighbors(localAddr);
    for (int i = 0; i < neighbors.size(); i++) {
      NetAddress nb = (NetAddress) neighbors.get(i);
      ret.add(routeMetric.getHomeChannel(nb));
    }
    return ret;
  }

  /**
   * Inserts a new route into the link table.
   *
   * @param route the sequence of nodes (with metric between them) from here to
   *              <code>dest</code>.
   */
  public void addRouteToLinkTable(NetAddress dest, RouteEntry[] route) { // TODO:
    // metric

    for (int i = 0; i < route.length - 1; i++) {

      NetAddress ip1 = route[i].addr;
      NetAddress ip2 = route[i + 1].addr;

      if (ip1.equals(ip2)) // should not be possible
        continue;

      int metric = convertMetricFromExternalToInternal(route[i + 1].metric); // metric
      // starts
      // with
      // offset
      // 1

      routeMetric.updateBothLinks(ip1, ip2, metric, false);

      log.debug("linkTable.updateLink " + route[i].addr + " "
              + route[i + 1].addr + " " + metric);

      log.debug("<" + routeMetric + ">");
    }

    checkBuffer(dest);
  }

  /**
   * Removes the direct link between <code>addr1</code> and
   * <code>addr2</code> from link table.
   *
   * @param addr1 the first address in the link
   * @param addr2 the second address in the link
   */
  public void removeLinkFromLinkTable(NetAddress addr1, NetAddress addr2) {
    // remove all links between nodes bad_src and bad_dst
    routeMetric.updateBothLinks(addr1, addr2,
            INVALID_ROUTE_METRIC, false);

    if (log.isDebugEnabled()) {
      log.debug("linkTable.removeLinkFromLinkTable " + addr1 + " "
              + addr2 + " " + INVALID_ROUTE_METRIC);
      log.debug("<" + routeMetric + ">");
    }
  }

  /**
   * Retrieves a route from the link table (shortest path algorithm).
   *
   * @param dest
   * @return array of RouteEntry
   */
  protected RouteEntry[] getRouteFromLinkTable(NetAddress dest) {

    if (log.isDebugEnabled()) {
      log.debug("<" + routeMetric + ">");
    }

    List routes = routeMetric.queryRoute(localAddr, dest, CS_MIN_METRIC);

    if (routes == null || routes.isEmpty()) {
      // No cached route to this destination
      return null;
    }

    if (log.isInfoEnabled()) {
      int routeMetric = this.routeMetric.getRouteMetric(routes,
          INVALID_ROUTE_METRIC);

      log.info("metric of shortest path is " + routeMetric);

      StringBuffer routeStr = new StringBuffer();
      for (int i = 0; i < routes.size(); i++) {
        routeStr.append(routes.get(i)).append(" ");
      }
      log.info("shortest path: " + routeStr.toString());
    }

    //TODO modifications here
    // strip off first entry (myself)
    //routes.remove(0);
    // strip off last entry (final destination)
    //routes.remove(routes.size() - 1);

    RouteEntry[] entries = new RouteEntry[routes.size()];

    NetAddress prev = null;
    NetAddress curr = null;
    for (int i = 0; i < routes.size(); i++) {
      curr = (NetAddress) routes.get(i);
      // metric to be filled in along the way
      byte byteMetric = Byte.MAX_VALUE;
      if (prev != null) {
        int metric = routeMetric.getLinkMetricOld(prev, curr);
        byteMetric = convertMetricFromInternalToExternal(metric);
      }

      entries[i] = new RouteEntry(curr, byteMetric);
      prev = curr;
    }

    // return the route
    return entries;
  }

  /**
   * Initializes the Send Buffer.
   */
  private void initBuffer() {
    sendBuffer = new LinkedList();
  }

  /**
   * Inserts a new packet into the Send Buffer, annotating it with the current
   * system time.
   *
   * @param msg the message to insert into the buffer
   */
  public void insertBuffer(NetMessage.Ip msg, MessageAnno anno) {
    BufferedPacket packet = new BufferedPacket(msg);
    sendBuffer.add(packet);
    JistAPI.sleep(SEND_BUFFER_TIMEOUT);
    self.deleteBuffer(packet);
  }

  /**
   * Removes the given <code>BufferedPacket</code> from the Send Buffer.
   *
   * @param msg the packet to remove from the Send Buffer
   */
  public void deleteBuffer(Object msg) {
    sendBuffer.remove(msg);
  }

  /**
   * TODO: Why this method is unused??????
   * <p/>
   * Searches the Send Buffer for any packets intended for the given
   * destination and sends any that are found. This is typically called
   * immediately after finding a route to <code>dest</code>.
   *
   * @param dest the destination we now have a route to
   */
  private void checkBuffer(NetAddress dest) {
    ListIterator iter = sendBuffer.listIterator();

    while (iter.hasNext()) {
      BufferedPacket packet = (BufferedPacket) iter.next();

      if (packet.msg.getDst().equals(dest)) {
        log.info(localAddr + "( " + JistAPI.getTime() + " ): Send buffered data packet to dst " + dest);

        RouteEntry[] route = getRouteFromLinkTable(dest);

        // calculate candidate set
        List cs = new ArrayList();
        int ch = calculateCandidateSet(route, localAddr, dest, cs, true, null, null, route);

        if (cs.size() < cSetSize)
          log.warn(localAddr + "( " + JistAPI.getTime() + " ): CSSIZE is smaller than optimal: "
                  + cs.size() + " < " + cSetSize);

        int id = getUDPMsgId(packet.msg.getPayload());

        sendWithCandidateSet(packet.msg, cs, ch, id, route);
        iter.remove();
      }
    }
  }

  /**
   * Initializes the Gratuitous Route Reply Table.
   */
  private void initRouteReplyTable() {
    routeReplyTable = new HashSet();
  }

  /**
   * Adds a new entry to the Gratuitous Route Reply Table.
   *
   * @param originator the originator of the shortened Source Route
   * @param lastHop    the most recent hop address of the shortened Source Route
   */
  public void addRouteReplyEntry(NetAddress originator, NetAddress lastHop) {
    routeReplyTable.add(new RouteReplyTableEntry(originator, lastHop));

    // Remove this entry from the table after the appropriate timeout
    JistAPI.sleep(GRAT_REPLY_HOLDOFF);
    self.deleteRouteReplyEntry(originator, lastHop);
  }

  /**
   * Deletes an entry from the Gratuitous Route Reply Table.
   *
   * @param originator the originator of the shortened Source Route
   * @param lastHop    the most recent hop address of the shortened Source Route
   */
  public void deleteRouteReplyEntry(NetAddress originator, NetAddress lastHop) {
    routeReplyTable.remove(new RouteReplyTableEntry(originator, lastHop));
  }

  /**
   * Initializes the Route Request Table.
   */
  private void initRequestTable() {
    routeRequestTable = new Hashtable();
  }

  private void initFloodingTable() {
    floodingTable = new HashSet();
  }

  private void initDataPacketTable() {
    dataPacketTable = new HashSet();
  }

  /**
   * Enters a new Route Request ID number into the Route Request Table.
   *
   * @param src the address of the originator of the Route Request
   * @param id  the ID number of the Route Request
   */
  private void addRequestId(NetAddress src, short id, int cumMetric) {
    // Do nothing if it's already in the table
    if (seenRequestLately(src, id, cumMetric))
      return;

    // Otherwise add this id to the table
    RouteRequestTableEntry entry = (RouteRequestTableEntry) routeRequestTable
            .get(src);

    if (entry == null) {
      entry = new RouteRequestTableEntry();
      routeRequestTable.put(src, entry);
    }

    entry.ids.addFirst(new Tuple(new Short(id), new Integer(cumMetric)));
    if (entry.ids.size() > MAX_REQUEST_TABLE_IDS) {
      // Make sure the list doesn't grow too large by removing the least
      // recently seen id number
      entry.ids.removeLast();
    }
  }

  /**
   * Checks if we have recently seen the Route Request with the given id
   * coming from the given source. "Recently" here means within the last
   * <code>MAX_REQUEST_TABLE_IDS</code> Route Requests coming from
   * <code>src</code>.
   *
   * @param src the source address of the Route Request
   * @param id  the ID number of the Route Request
   * @return whether the given request has been seen recently.
   */
  private boolean seenRequestLately(NetAddress src, short id, int cumMetric) {
    RouteRequestTableEntry entry = (RouteRequestTableEntry) routeRequestTable
            .get(src);

    if (entry == null) {
      return false;
    }

    ListIterator iter = entry.ids.listIterator();
    while (iter.hasNext()) {
      Tuple item = (Tuple)iter.next();
      short curId = ((Short)item.getX()).shortValue();
      int curMetric = ((Integer)item.getY()).intValue();

      if (curId == id) {
        if (cumMetric >= curMetric) {
          // Move this id to the front of the list
          iter.remove();
          entry.ids.addFirst(new Tuple(new Short(curId), new Integer(curMetric)));
          return true;
        } else if (cumMetric < curMetric) {
          // Move this id to the front of the list
          iter.remove();
          entry.ids.addFirst(new Tuple(new Short(curId), new Integer(cumMetric)));
          return false;
        }
      }
    }
    return false;
  }

  /**
   * Retrieves the Source Route option from the given ExOR message, or
   * <code>null</code> if none exists.
   *
   * @param msg the ExOR message
   * @return the Source Route option from <code>msg</code>, or
   *         <code>null</code> if none exists.
   */
  private RouteMcExORMsg.OptionSourceRouted getSourceRoute(RouteMcExORMsg msg) {
    Iterator iter = msg.getOptions().iterator();

    while (iter.hasNext()) {
      byte[] opt = (byte[]) iter.next();
      if (RouteMcExORMsg.Option.getType(opt) == RouteMcExORMsg.OPT_SOURCE_ROUTED) {
        return (RouteMcExORMsg.OptionSourceRouted) RouteMcExORMsg.Option.create(
                opt, 0);
      }
    }
    return null;
  }

  /**
   * Returns the route collected by the route request.
   */
  private RouteMcExORMsg.OptionRouteRequest getSourceInRouteRequest(RouteMcExORMsg msg) {
    Iterator iter = msg.getOptions().iterator();

    while (iter.hasNext()) {
      byte[] opt = (byte[]) iter.next();
      if (RouteMcExORMsg.Option.getType(opt) == RouteMcExORMsg.OPT_ROUTE_REQUEST) {
        return (RouteMcExORMsg.OptionRouteRequest) RouteMcExORMsg.Option.create(
                opt, 0);
      }
    }
    return null;
  }

  public boolean isDuplicate(RouteMcExORMsg ExORMsg, NetAddress ipAddrSrc) {
    int seqnr = ExORMsg.getSeqNr();

    if (0 <= seqnr) {
      boolean seen = seenDataPacketBefore(ipAddrSrc, seqnr);

      addDataPacketId(ipAddrSrc, seqnr);

      if (seen) {
        // TODO
//        processEvent(Event.RTG_DUPLICATE, new Object[]{this,
//                new Double(seqnr)});

        log.warn(localAddr + "(" + JistAPI.getTime() + "): received "
                + "duplicate packet (" + ipAddrSrc + "," + seqnr + "); drop it.");
      }

      return seen;
    }

    return false;
  }

  /**
   * If the given message uses the ExOR protocol, the ExOR header is examined
   * to see if any actions need to be performed on this packet (such as
   * forwarding it).
   *
   * @param msg     the message to examine
   * @param lastHop the MAC address of the node that sent this message
   */
  public void peek(NetMessage msg, MacAddress lastHop, MessageAnno anno) {
    if (msg instanceof NetMessage.Ip) {
      NetMessage.Ip ipMsg = (NetMessage.Ip) msg;

      if (ipMsg.getProtocol() == Constants.NET_PROTOCOL_MCEXOR) {
        RouteMcExORMsg ExORMsg = null;
        ExORMsg = (RouteMcExORMsg) ipMsg.getPayload();

        //if (log.isDebugEnabled()) {
        log.debug(localAddr + " saw message from " + ipMsg.getSrc()
                + " to " + ipMsg.getDst());

        Iterator iter = ExORMsg.getOptions().iterator();
        while (iter.hasNext()) {
          byte[] optBuf = (byte[]) iter.next();

          switch (RouteMcExORMsg.Option.getType(optBuf)) {
            case RouteMcExORMsg.OPT_SOURCE_ROUTED:
              log.debug("    Source Route");
              break;

            case RouteMcExORMsg.OPT_DATA_NO_ROUTE:
              log.debug("    Data no Route");
              break;

            case RouteMcExORMsg.OPT_ROUTE_REPLY:
              RouteMcExORMsg.OptionSourceRouted sourceRoute = getSourceRoute(ExORMsg);

              StringBuffer strRoute = new StringBuffer();
              if (sourceRoute != null) {
                for (int i = 0; i < sourceRoute.getNumAddresses(); i++) {
                  strRoute.append(sourceRoute.getAddress(i)).append(" ");
//									log.debug("update link " )
                }
              }
              log.debug("    peek: Route Reply" + " [" + ipMsg.getSrc()
                      + " " + strRoute + " " + ipMsg.getDst()
                      + "]");
              break;

            case RouteMcExORMsg.OPT_ROUTE_REQUEST:
              RouteMcExORMsg.OptionRouteRequest routeRequest
                      = (RouteMcExORMsg.OptionRouteRequest) RouteMcExORMsg.Option.create(optBuf, 0);
              log.debug("    Route Request " + routeRequest.getId());

              RouteMcExORMsg.OptionRouteRequest reqRoute = getSourceInRouteRequest(ExORMsg);

              StringBuffer strReqRoute = new StringBuffer();
              if (reqRoute != null) {
                for (int i = 0; i < reqRoute.getNumAddresses(); i++) {
                  strReqRoute.append(reqRoute.getAddress(i)).append(" ");
//									log.debug("update link " )
                }
              }
              log.debug("    Route Request" + " [" + ipMsg.getSrc()
                      + " " + strReqRoute + " " + ipMsg.getDst()
                      + "]");
              break;

            case RouteMcExORMsg.OPT_ROUTE_ERROR:
              log.debug("    Route Error");
              break;

            default:
              log.debug("    Other");
              break;
          }
        }
        //}

        processOptions(ExORMsg, anno, ipMsg.getSrc(), ipMsg.getDst(), ipMsg
                .getProtocol(), ipMsg.getPriority(), ipMsg.getTTL(),
                ipMsg.getId(), ipMsg.getFragOffset(), lastHop);
      } else if (ipMsg.getProtocol() == Constants.NET_PROTOCOL_LINK_PROBE) {
        // log.debug("LINKProbe received.");
      } else if (ipMsg.getProtocol() == Constants.NET_PROTOCOL_FLOODING) {
        RouteMcExORFlood.McFloodingMsg floodMsgMc = (RouteMcExORFlood.McFloodingMsg) ipMsg.getPayload();

        forwardFlooding(floodMsgMc);
      }
    }
  }

  /**
   * Checks if we have recently seen this flooding packet with the given seqNum
   * coming from the given source.
   * *
   *
   * @param src the source address of the flooding packet
   * @param id  the ID number of the Route Request
   * @return whether the given request has been seen recently.
   */
  protected boolean seenFloodingBefore(NetAddress src, int id) {

    PacketId entry = new PacketId(src, id);

    if (floodingTable.contains(entry)) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * Enters a new Flooding ID number into the Flooding Table.
   *
   * @param src the address of the originator of the flooding packet
   * @param id  the ID number of the Route Request
   */
  protected void addFloodingId(NetAddress src, int id) {
    // Do nothing if it's already in the table
    if (seenFloodingBefore(src, id))
      return;

    // Otherwise add this id to the table
    PacketId entry = new PacketId(src, id);

    floodingTable.add(entry);
  }

  /**
   * 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);

    if (dataPacketTable.contains(entry)) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * 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) {
    // Do nothing if it's already in the table
    if (seenDataPacketBefore(src, id))
      return;

    // Otherwise add this id to the table
    PacketId entry = new PacketId(src, id);

    dataPacketTable.add(entry);
  }

  /**
   * Receives a message from the network. This method merely strips off the
   * ExOR header and hands the message off to the transport layer.
   *
   * @param msg      the message being received
   * @param src      the address of the originator of the message
   * @param lastHop  the MAC address of the most recent node to forward the message
   * @param macId    the ID of the MAC interface
   * @param dst      the address of the destination of the message (which should be
   *                 the IP address of this node)
   * @param priority the IP priority of the message
   * @param ttl      the IP time to live of the message
   */
  public void receive(Message msg, NetAddress src, MacAddress lastHop,
      byte macId, NetAddress dst, byte priority, byte ttl, MessageAnno anno) {

    // flooding packet
    if (msg instanceof RouteMcExORFlood.McFloodingMsg) {
      RouteMcExORFlood.McFloodingMsg floodMsgMc = (RouteMcExORFlood.McFloodingMsg) msg;
      handleFloodingPacket(floodMsgMc);
      return;
    }

    if (!(msg instanceof RouteMcExORMsg)) {
      throw new RuntimeException("Non-ExOR message received by ExOR");
    }

    if (log.isInfoEnabled() && localAddr.equals(dst)) {
      // Don't count received broadcast packets?
      log.info("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).

    RouteMcExORMsg ExORMsg = (RouteMcExORMsg) msg;

    // Check for duplicates and filter them out
    if (isDuplicate(ExORMsg, src)) {
      log.info(localAddr + " (" + JistAPI.getTime() + "): duplicate found " + ExORMsg.getSeqNr() );
      return;
    }

    RouteMcExORMsg.OptionSourceRouted sourceRoute = getSourceRoute(ExORMsg);
    if (sourceRoute != null) {
      // Strange as it may seem, we will discard this packet, which is
      // in fact intended for us, if it arrives here before traversing
      // the other links in the intended route. (Route shortening should
      // prevent this from happening too often.)
      if (!localAddr.equals(nextRecipient(sourceRoute, dst)))
        return;
    }

    if (ExORMsg.getContent() != null) {

      // estimate the net address of the last hop
      NetAddress lastIp = rarp(lastHop);
      if (log.isDebugEnabled()) {
        pushFwdLink(lastIp, getUDPMsgId(ExORMsg.getContent()) / 10000);
      }

      if (log.isDebugEnabled()) {
        Iterator iter = ExORMsg.getOptions().iterator();
        while (iter.hasNext()) {
          byte[] optBuf = (byte[]) iter.next();
          RouteMcExORMsg.Option opt = RouteMcExORMsg.Option.create(optBuf, 0);

          if (opt == null) {
            throw new RuntimeException("Unrecognized ExOR Option");
          }
          if (opt.getType() == RouteMcExORMsg.OPT_DATA_NO_ROUTE) { // data packets are routed opportunistic
            RouteMcExORMsg.OptionDataNoRoute data = (RouteMcExORMsg.OptionDataNoRoute) opt;

            byte[] chArray = data.getUsedChannels();
            int chArrLen = (chArray != null) ? chArray.length : 0;
            byte[] nwArary = new byte[chArrLen + 1];
            if (chArray != null)
              System.arraycopy(chArray, 0, nwArary, 0, chArrLen);

            // last hop was on my home channel
            RadioInterface.RFChannel chLastHop = routeMetric.getHomeChannel(localAddr);// routeMetric.getHomeChannel(lastIp);

            nwArary[chArrLen] = (byte) chLastHop.getChannel();

            StringBuffer usedChs = new StringBuffer();

            for (int i = 0; i < nwArary.length; i++) {
              byte b = nwArary[i];
              usedChs.append(b);
              if (i < nwArary.length - 1)
                usedChs.append(" -> ");
            }
            log.info("#PID " + getUDPMsgId(ExORMsg.getContent()) + "(hops: " + nwArary.length + "): " + usedChs.toString());
          }
        }
      }

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

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

      if (log.isInfoEnabled()) {
        StringBuffer strRoute = new StringBuffer();
        if (sourceRoute != null) {
          for (int i = 0; i < sourceRoute.getNumAddresses(); i++) {
            strRoute.append(sourceRoute.getAddress(i)).append(" ");
          }
        }
        log.info(localAddr + "(" + JistAPI.getTime() + "): Received data "
                + "packet (" + src + "," + ExORMsg.getSeqNr() + ") from "
                + src + " at " + dst + " [" + strRoute + "]");
      }
    }
  }

  /**
   * Increment local sequence counter.
   *
   * @return new sequence number.
   */
  protected int incSeq() {
    nextDataPacketId = nextDataPacketId - 1;
    if (nextDataPacketId == 0)
      nextDataPacketId = RouteMcExORMsg.OptionDataNoRoute.MAX_SEQ;
    return nextDataPacketId;
  }

  public RouteMcExORFlood getFlooding() {
    return flooding;
  }

  public String toString() {
    return "RouteExOR(): " + localAddr;
  }

  protected int getUDPMsgId(Message msg) {
    if (!(msg instanceof TransUdp.UdpMessage))
      return -1;

    byte[] msgId = ((MessageBytes) ((TransUdp.UdpMessage) msg).getPayload()).getBytes();

    int pId = Pickle.arrayToInteger(msgId, 0);
    int flowId = Pickle.arrayToInteger(msgId, 4);
    return flowId * 10000 + pId;
  }

  /**
   * Resolves the IP address to a given mac address (reverse arp)
   *
   * @param mac the mac address
   * @return the corresponding netaddress
   */
  private NetAddress rarp(MacAddress mac) {
    Enumeration keys = arp.keys();

    while (keys.hasMoreElements()) {
      NetAddress ip = (NetAddress) keys.nextElement();

      if (arp.get(ip).equals(mac))
        return ip;
    }

    return null;
  }

  public int getCsetSelection() {
    return csetSelection;
  }

  public void setGlobalPositionTable(Hashtable pos_tbl) {
    this.pos_tbl = pos_tbl;
  }

  public void setCsetSelection(int csetSelection) {
    this.csetSelection = csetSelection;

    // TODO
    // configure candidateset selection algorithm
    if (csetSelection == GLOBAL_CSET_SELECTION) {
      //
      // Construct a CSetGraph
      csgraph = new CandidateSetGraph(localAddr, routeMetric, flooding, cSetSize);

//      // register event listener
//      linkStat.getLinkTable().addEventListener(csgraph.getLinkTableEventListener());
    }
  }

  public void enableFlooding() {
    this.floodingEnabled = true;
  }

  public void disableFlooding() {
    this.floodingEnabled = false;
  }

  // --------------------------------------------------------------------------
  // Inner classes
  // --------------------------------------------------------------------------
  public class NodePref {
    public NetAddress addr;
    public byte pref;
    public long timestamp;

    public NodePref(NetAddress addr, byte pref, long timestamp) {
      this.addr = addr;
      this.pref = pref;
      this.timestamp = timestamp;
    }

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

      final NodePref nodePref = (NodePref) o;

      if (pref != nodePref.pref) return false;
      if (timestamp != nodePref.timestamp) return false;
      if (addr != null ? !addr.equals(nodePref.addr) : nodePref.addr != null) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = (addr != null ? addr.hashCode() : 0);
      result = 29 * result + (int) pref;
      result = 29 * result + (int) (timestamp ^ (timestamp >>> 32));
      return result;
    }
  }

  /**
   * An entry in the Route Request Table.
   */
  private class RouteRequestTableEntry {
    /**
     * The IP TTL on the last Route Request for this destination.
     */
    public byte lastRequestTTL;

    /**
     * The time of the last Route Request for this destination.
     */
    public long lastRequestTime;

    /**
     * The number of Route Requests for this destination since we last
     * received a valid Route Reply.
     */
    public int numRequestsSinceLastReply;

    /**
     * The amount of time necessary to wait (starting at lastRequestTime)
     * before sending out another Route Request.
     */
    public long timeout;

    /**
     * Identification values of recently seen requests coming from this
     * node.
     */
    public LinkedList ids;

    /**
     * Creates a new RouteRequestTableEntry.
     */
    public RouteRequestTableEntry() {
      lastRequestTTL = MAX_TTL;
      lastRequestTime = JistAPI.getTime();
      numRequestsSinceLastReply = 0;
      timeout = REQUEST_PERIOD;
      ids = new LinkedList();
    }

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

      final RouteRequestTableEntry that = (RouteRequestTableEntry) o;

      if (lastRequestTTL != that.lastRequestTTL) return false;
      if (lastRequestTime != that.lastRequestTime) return false;
      if (numRequestsSinceLastReply != that.numRequestsSinceLastReply) return false;
      if (timeout != that.timeout) return false;
      if (ids != null ? !ids.equals(that.ids) : that.ids != null) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = (int) lastRequestTTL;
      result = 29 * result + (int) (lastRequestTime ^ (lastRequestTime >>> 32));
      result = 29 * result + numRequestsSinceLastReply;
      result = 29 * result + (int) (timeout ^ (timeout >>> 32));
      result = 29 * result + (ids != null ? ids.hashCode() : 0);
      return result;
    }
  }

  /**
   * An entry in the Gratuitous Route Reply Table.
   */
  private class RouteReplyTableEntry {
    /**
     * The originator of the shortened Source Route.
     */
    public NetAddress originator;

    /**
     * The last hop address of the shortened Source Route before reaching
     * this node.
     */
    public NetAddress lastHop;

    /**
     * Creates a new <code>RouteReplyTableEntry</code>.
     *
     * @param o the originator of the shortened Source Route
     * @param l the last hop address of the shortened Source Route
     */
    public RouteReplyTableEntry(NetAddress o, NetAddress l) {
      originator = o;
      lastHop = l;
    }

    /**
     * {@inheritDoc}
     */
    public int hashCode() {
      return originator.hashCode() + lastHop.hashCode();
    }

    /**
     * {@inheritDoc}
     */
    public boolean equals(Object o) {
      if (o == null || !(o instanceof RouteReplyTableEntry))
        return false;

      RouteReplyTableEntry other = (RouteReplyTableEntry) o;
      return other.originator.equals(originator)
              && other.lastHop.equals(lastHop);
    }
  }

  private 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;
    }
  }

  /**
   * This class represents an entry into a route (used to update the link
   * table)
   */
  public static class RouteEntry {
    public NetAddress addr;

    public byte metric;

    public RouteEntry(NetAddress addr, byte metric) {
      this.addr = addr;
      this.metric = metric;
    }

    public String toString() {
      return "[" + addr + "," + metric + "]";
    }

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

      final RouteEntry that = (RouteEntry) o;

      if (metric != that.metric) return false;
      if (addr != null ? !addr.equals(that.addr) : that.addr != null) return false;

      return true;
    }

    public int hashCode() {
      int result;
      result = (addr != null ? addr.hashCode() : 0);
      result = 29 * result + (int) metric;
      return result;
    }
  }

  /**
   * Contains a packet and the time it was inserted into the buffer.
   */
  public class BufferedPacket {
    /**
     * The buffered packet.
     */
    public NetMessage.Ip msg;

    /**
     * The time it was inserted into the buffer.
     */
    public long bufferTime;

    /**
     * Creates a new BufferedPacket.
     *
     * @param msg the packet to buffer.
     */
    public BufferedPacket(NetMessage.Ip msg) {
      this.msg = msg;
      this.bufferTime = JistAPI.getTime();
    }

  }

  public static byte convertMetricFromInternalToExternal(int internal) {
    // TODO BEGIN Hack
    if (internal >= MAX_ROUTE_METRIC_FOR_TX)
      internal = MAX_ROUTE_METRIC_FOR_TX;

    return (byte) (internal / 8);
    // END HACK
  }

  public static int convertMetricFromExternalToInternal(int external) {
    // TODO BEGIN Hack
    return external * 8;
    // END HACK
  }

  public int hashCode() {
    return 1;
  }
}
