package brn.swans.route;

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 jist.runtime.JistAPI;
import jist.runtime.Main;
import jist.runtime.Util;
import jist.swans.Constants;
import jist.swans.mac.MacAddress;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.misc.Pickle;
import jist.swans.net.NetAddress;
import jist.swans.net.NetMessage;

import org.apache.log4j.Logger;

import brn.swans.route.metric.ArpTableInterface;
import brn.swans.route.metric.RouteMetricInterface;
import brn.swans.route.metric.RouteMetricInterface.NoLinkExistsException;

class _reactive {
  public static interface ReactiveInterface {
    void discoverRoute(NetAddress dest, short requestId);
  }

  public static class Dlg implements ReactiveInterface, JistAPI.Proxiable {
    private ReactiveInterface dlg;

    public Dlg(ReactiveInterface dlg) {
      this.dlg = dlg;
    }

    public ReactiveInterface getProxy() {
      return (ReactiveInterface) JistAPI.proxy(this, ReactiveInterface.class);
    }

    /**
     * @param dest
     * @param requestId
     * @see brn.swans.route._reactive.ReactiveInterface#discoverRoute(jist.swans.net.NetAddress, short)
     */
    public void discoverRoute(NetAddress dest, short requestId) {
      dlg.discoverRoute(dest, requestId);
    }
  }
}

public class RouteDsrDiscoveryReactive extends RouteDsrDiscovery
  implements _reactive.ReactiveInterface {

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

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

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

  /**
   * 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 amount of time a packet can remain in the Send Buffer. */
  public static final long SEND_BUFFER_TIMEOUT = 30 * Constants.SECOND;

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

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

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

  /** forward only route request which came from a link with a better metric of this */
  public final static int MAX_LINK_METRIC_FOR_RREQ_FORWARDING = 5000;

  /**
   * An entry in the Route Request Table.
   */
  private static 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();
    }
  }
  /**
   * An entry in the Gratuitous Route Reply Table.
   */
  private static 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);
    }
  }

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

    /** The buffered annotation. */
    public MessageAnno anno;

    /** 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, MessageAnno anno) {
      this.msg = msg;
      this.anno = anno;
      this.bufferTime = JistAPI.getTime();
    }
  }

  public static interface SendBufferIf {
    void insertBuffer(NetMessage.Ip msg, MessageAnno anno);
    void deleteBuffer(BufferedPacket packet);
  }

  /**
   * Send buffer class, stores packets for later retrieval with timeout.
   */
  public static class SendBuffer implements SendBufferIf, JistAPI.Proxiable {

    protected List buffer;

    protected SendBufferIf self;

    private long timeout;

    /**
     * Constructs a send buffer object
     *
     * @param timeout timeout for queued packets
     */
    public SendBuffer(long timeout) {
      this.timeout = timeout;
      buffer = new LinkedList();
      self = (SendBufferIf) JistAPI.proxy(this, SendBufferIf.class);
    }

    /**
     * returns the self-referencing proxy for this object.
     * @return the self-referencing proxy for this object.
     */
    public SendBufferIf getProxy() {
      return self;
    }

    /**
     * Inserts an packet into the send buffer.
     *
     * @param msg the packet to insert into the send buffer
     */
    public void insertBuffer(NetMessage.Ip msg, MessageAnno anno) {
      BufferedPacket packet = new BufferedPacket(msg, anno);
      buffer.add(packet);
      JistAPI.sleep(timeout);
      self.deleteBuffer(packet);
    }

    /**
     * Removes an entry from the send buffer.
     *
     * @param packet the <code>BufferedPacket</code> to be removed from the send
     *               buffer
     */
    public void deleteBuffer(BufferedPacket packet) {
      buffer.remove(packet);
    }

    /**
     * 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
     * @return list with packets for the given destination
     */
    private List removeAddress(NetAddress dest) {
      Iterator iter = buffer.iterator();
      List ret = new LinkedList();

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

        if (packet.msg.getDst().equals(dest)) {
          if (log.isDebugEnabled())
          log.debug(JistAPI.getTime() + ":" + this + " Send src routed packet to dst " + dest);
          //SendWithRoute(packet.msg, GetCachedRoute(dest));
//          dsr.sendWithRoute(packet.msg, packet.anno, getRouteFromLinkTable(dest));
          ret.add(packet);
          iter.remove();
        }
      }
      return ret;
    }
  }

  public static interface ReplyTableIf {
    void addRouteReplyEntry(NetAddress originator, NetAddress lastHop);
    void deleteRouteReplyEntry(NetAddress originator, NetAddress lastHop);
  }

  /**
   * Reply table class, stores entries for later retrieval with timeout.
   */
  public static class ReplyTable extends HashSet implements ReplyTableIf, JistAPI.Proxiable {
    private static final long serialVersionUID = 1L;

    protected ReplyTableIf self;

    private long timeout;

    /**
     * Constructs a send buffer object
     *
     * @param timeout timeout for queued packets
     */
    public ReplyTable(long timeout) {
      this.timeout = timeout;
      self = (ReplyTableIf) JistAPI.proxy(this, ReplyTableIf.class);
    }

    /**
     * returns the self-referencing proxy for this object.
     * @return the self-referencing proxy for this object.
     */
    public ReplyTableIf getProxy() {
      return self;
    }

    /**
     * Adds an entry into the gratuitous route reply table.
     *
     * @param originator the originator of the packet being replied to
     * @param lastHop    the last-hop address of the packet being replied to
     */
    public void addRouteReplyEntry(NetAddress originator, NetAddress lastHop) {
      add(new RouteReplyTableEntry(originator, lastHop));

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

    /**
     * Removes an entry from the gratuitous route reply table.
     *
     * @param originator the originator of the packet being removed
     * @param lastHop    the last-hop address of the packet being removed
     */
    public void deleteRouteReplyEntry(NetAddress originator, NetAddress lastHop) {
      remove(new RouteReplyTableEntry(originator, lastHop));
    }

    /**
     * Determines whether there is an entry in the Gratuitous Route Reply Table
     * corresponding to the given addresses.
     *
     * @param originator the originator of the shortened Source Route
     * @param lastHop    the most recent hop address of the shortened Source Route
     * @return whether the entry exists in the table.
     */
    protected boolean routeReplyEntryExists(NetAddress originator,
                                          NetAddress lastHop) {
      return contains(new RouteReplyTableEntry(originator, lastHop));
    }

  }


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

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

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

//  /**
//   * 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 ReplyTable routeReplyTable;

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

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

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

  private _reactive.ReactiveInterface self;

  /**
   * Constructs a reactive route discovery object.
   *
   * @param dsr link to the dsr object.
   * @param metric metric to use
   * @param localAddr address of the reactive dsr object.
   */
  public RouteDsrDiscoveryReactive(RouteDsrBrn dsr, RouteMetricInterface metric,
      ArpTableInterface arp, NetAddress localAddr) {
    super(dsr, metric, arp, localAddr);

    nextRequestId = 0;
    activeRequests = new HashSet();

    sendBuffer = new SendBuffer(SEND_BUFFER_TIMEOUT);
    routeRequestTable = new Hashtable();
//    routeReplyTable = new ReplyTable(GRAT_REPLY_HOLDOFF);

    this.self = new _reactive.Dlg(this).getProxy();
  }

  /**
   * 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) {
    // Do nothing if it's already in the table
    if (seenRequestLately(src, id))
      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 Short(id));
    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) {
    RouteRequestTableEntry entry = (RouteRequestTableEntry) routeRequestTable
            .get(src);

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

    ListIterator iter = entry.ids.listIterator();
    while (iter.hasNext()) {
      short curId = ((Short) iter.next()).shortValue();

      if (curId == id) {
        // Move this id to the front of the list
        iter.remove();
        entry.ids.addFirst(new Short(curId));
        return true;
      }
    }

    return false;
  }

  private void checkBuffer(NetAddress dst) {
    List packets = sendBuffer.removeAddress(dst);

    for (int i = 0; i < packets.size(); i++) {
      BufferedPacket packet = (BufferedPacket) packets.get(i);
      RouteDsrBrnMsg.RouteEntry[] routeFromLinkTable = getRouteFromLinkTable(dst);
      if (null == routeFromLinkTable)
        routeFromLinkTable = getRouteFromLinkTable(dst);
      sendWithRoute(packet.msg, packet.anno, routeFromLinkTable);
    }
  }

  /**
     * Handles each of the options in a given McExOR header.
     *
     * @param msg        the message containing the McExOR header
     * @param anno
     * @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
     */
    private void processOptions(RouteDsrBrnMsg msg, MessageAnno anno,
        MacAddress lastHop,  NetAddress src, NetAddress dst, short protocol,
        byte priority, byte ttl, short id, short fragOffset) {
      Iterator iter = msg.getOptions().iterator();

      while (iter.hasNext()) {
        RouteDsrBrnMsg.Option opt = (RouteDsrBrnMsg.Option)iter.next();

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

        switch (opt.getType()) {
          case RouteDsrBrnMsg.OPT_ROUTE_REQUEST:
            handleRequest(msg, anno, lastHop, (RouteDsrBrnMsg.OptionRouteRequest)
                opt, src, dst, protocol, priority, ttl, id, fragOffset);

            break;

          case RouteDsrBrnMsg.OPT_ROUTE_REPLY:
            handleReply(msg, anno, lastHop, (RouteDsrBrnMsg.OptionRouteReply) opt);
            break;

            //TODO should we really do this ???
  //        case RouteDsrEtxMessage.OPT_SOURCE_ROUTE:
  //          sourceRoute = (RouteDsrEtxMessage.OptionSourceRoute) opt;
  //
  //          if (!localAddr.equals(NextRecipient(sourceRoute, dst))) {
  //            PerformRouteShortening(sourceRoute, src, dst);
  //          }
  //          break;

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

        }
      }

    }

  /**
   * 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 anno
   * @param opt        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 McExOR)
   * @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(RouteDsrBrnMsg msg, MessageAnno anno,
      MacAddress lastHop, RouteDsrBrnMsg.OptionRouteRequest opt,
      NetAddress src, NetAddress dst, short protocol, byte priority,
      byte ttl, short id, short fragOffset) {
    // If this request came from this node, ignore it
    if (localAddr.equals(src))
      return;

    // Remember mac address in arp table
    NetAddress prevNode = src;
    if (0 < opt.getNumAddresses())
      prevNode = opt.getAddress(opt.getNumAddresses()-1).addr;
    arp.addArpEntry(prevNode, lastHop);

    // If we've seen this request lately, ignore it
    // TODO AZU: permit reply storm
    if (seenRequestLately(src, opt.getId()))
      return;

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

    // Make a note of this request in the route request table
    addRequestId(src, opt.getId());
  }

  /**
   * 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 anno
   * @param reply the Route Reply option
   */
  private void handleReply(RouteDsrBrnMsg msg, MessageAnno anno,
      MacAddress lastHop, RouteDsrBrnMsg.OptionRouteReply reply) {
    NetAddress dest;
    RouteRequestTableEntry entry;

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

    // Do not remember mac address in arp table, it is done already with the src route

    // Add the route to our Route Cache
    for (int i = 0; i < reply.getNumAddresses() - 1; i++) {
      if (localAddr.equals(reply.getAddress(i).addr)) {
        RouteDsrBrnMsg.RouteEntry[] route = new RouteDsrBrnMsg.RouteEntry[reply.getNumAddresses() - i];
        for (int j = i; j < i + route.length; j++) {
          route[j - i] = reply.getAddress(j);
        }
        if (route.length < 2)
          continue;

        //InsertRouteCache(dest, route);
        addRouteToLinkTable(route);
        checkBuffer(dest);
        break;
      }
    }

  }

  /**
   * 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(RouteDsrBrnMsg.OptionRouteError opt) {
    switch (opt.getErrorType()) {
      // This is the only error type I care about
      case RouteDsrBrnMsg.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;
    }
  }

  /**
   * 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(RouteDsrBrnMsg.OptionRouteRequest opt,
      NetAddress src) {
    RouteDsrBrnMsg.RouteEntry[] routeToHere = new RouteDsrBrnMsg.RouteEntry[opt.getNumAddresses() + 2];

    routeToHere[0] = new RouteDsrBrnMsg.RouteEntry(src, -1);

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

    int metric;
    try {
      metric = this.metric.getLinkMetric(prevNode, localAddr);
    } catch (NoLinkExistsException e) {
      // no link, no reply
      return;
    }

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

    // reverse route
//    StringBuffer str_route = new StringBuffer();
    RouteDsrBrnMsg.RouteEntry[] routeFromHere = new RouteDsrBrnMsg.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.
    RouteDsrBrnMsg reply = new RouteDsrBrnMsg();
    reply.addOption(new RouteDsrBrnMsg.OptionRouteReply(false, routeToHere));

    NetAddress nextHop = src;
    if (routeFromHere.length > 0) {
      RouteDsrBrnMsg.OptionSourceRoute srcRoute = new RouteDsrBrnMsg.
          OptionSourceRoute(false, false, 0, routeFromHere.length, routeFromHere);
      reply.addOption(srcRoute);
      nextHop = srcRoute.nextRecipient(src);
    }

    /** route discovery packets has a higher priority than normal packets ({@link Constants.NET_PRIORITY_D_NETWORKCONTROL}). */
    NetMessage.Ip replyMsg = new NetMessage.Ip(reply, localAddr, src,
        Constants.NET_PROTOCOL_MCEXOR, Constants.NET_PRIORITY_D_NETWORKCONTROL,
        Constants.TTL_DEFAULT);

    JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));
    dsr.send(replyMsg, Constants.NET_INTERFACE_DEFAULT,
        arp.getArpEntry(nextHop), new MessageAnno());
  }

  /**
   * Sends a McExOR message with a Route Error option to <code>src</code>
   * indicating that the next hop in the intended route cannot be reached from
   * this node.
   *
   * @param msg  the <code>RouteMcExORMsg</code> containing the Source Route
   *             option that contains the broken link
   * @param src  the originator of <code>msg</code>
   * @param dest the destination of <code>msg</code>
   */
  private void sendRouteError(RouteDsrBrnMsg msg, NetAddress src,
      NetAddress dest) {
    // Find the Source Route option so we know what the intended next hop
    // was
    Iterator iter = msg.getOptions().iterator();

    while (iter.hasNext()) {
      RouteDsrBrnMsg.Option opt = (RouteDsrBrnMsg.Option) iter.next();

      if (opt.getType() == RouteDsrBrnMsg.OPT_SOURCE_ROUTE) {
        RouteDsrBrnMsg.OptionSourceRoute sourceRoute = (RouteDsrBrnMsg.OptionSourceRoute) opt;

        // Find out the address of the node we couldn't reach
        NetAddress nextAddr = sourceRoute == null ? dest : sourceRoute.nextRecipient(dest);
        byte[] nextAddrBuf = new byte[4];
        Pickle.NetAddressToArray(nextAddr, nextAddrBuf, 0);

        // Create a packet containing a Route Error option
        RouteDsrBrnMsg errorMsg = new RouteDsrBrnMsg();
        NetAddress nextHop = src;

        errorMsg.addOption(new RouteDsrBrnMsg.OptionRouteError(
            RouteDsrBrnMsg.ERROR_NODE_UNREACHABLE,
            sourceRoute.getSalvageCount(), localAddr, src, nextAddrBuf));

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

        if (curSegment > 1) {
          // Need to add a Source Route option to the packet
          RouteDsrBrnMsg.RouteEntry[] route = new RouteDsrBrnMsg.RouteEntry[curSegment - 1];

          while (--curSegment > 0) {
            route[curSegment - 1] = sourceRoute.getAddress(route.length - curSegment);
          }

          RouteDsrBrnMsg.OptionSourceRoute srcRoute = new RouteDsrBrnMsg.
            OptionSourceRoute(false, false, 0, route.length, route);
          errorMsg.addOption(srcRoute);
          nextHop = srcRoute.nextRecipient(src);

          // Might as well add this route to the cache if it isn't
          // already there
          //InsertRouteCache(src, route);
          addRouteToLinkTable(route);
        }

        // Slap an IP header on it and send it off
        /** route discovery packets has a higher priority than normal packets ({@link Constants.NET_PRIORITY_D_NETWORKCONTROL}). */
        NetMessage.Ip ipMsg = new NetMessage.Ip(errorMsg, localAddr,
                src, Constants.NET_PROTOCOL_MCEXOR,
                Constants.NET_PRIORITY_D_NETWORKCONTROL, Constants.TTL_DEFAULT);

        dsr.send(ipMsg, Constants.NET_INTERFACE_DEFAULT,
            arp.getArpEntry(nextHop), new MessageAnno());

        if (log.isInfoEnabled()) {
          log.info(JistAPI.getTime() + ":" + this + " Originated route error from "
              + localAddr + " to " + src + ": Cannot contact " + nextAddr);
        }

        break;
      }
    }
  }

  /**
   * Propagates a Route Request to all nodes within range.
   *
   * @param msg        the message containing the Route Request
   * @param anno
   * @param opt        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(RouteDsrBrnMsg msg, MessageAnno anno,
      RouteDsrBrnMsg.OptionRouteRequest opt,
      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;
    }

    NetAddress prevNode = src;

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

    try {
      int metric = this.metric.getLinkMetric(prevNode, localAddr);

      if (metric > MAX_LINK_METRIC_FOR_RREQ_FORWARDING) {
        if (log.isDebugEnabled())
          log.debug(JistAPI.getTime() + ":" + this + " skip RREQ because of junk link");
        return;
      }
      if (log.isDebugEnabled())
        log.debug(JistAPI.getTime() + ":" + this + " " + this.metric);

      // TODO: hack
      if (Main.ASSERT)
        Util.assertion(metric > 0);
//      if (metric == 0)
//        metric = RouteMetricInterface.INVALID_ROUTE_METRIC;

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

      // TODO Is this the right pos for the metric?
      newAddresses[newAddresses.length - 1] = new RouteDsrBrnMsg.RouteEntry(localAddr, metric);
    } catch (NoLinkExistsException e) {
      return;
    }

    newRequest.addOption(new RouteDsrBrnMsg.OptionRouteRequest(
            opt.getId(), opt.getTargetAddress(), newAddresses));

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

    anno = new MessageAnno();
    JistAPI.sleep((long) (Constants.random.nextDouble() * BROADCAST_JITTER));
    dsr.send(newRequestIp, Constants.NET_INTERFACE_DEFAULT,
            MacAddress.ANY, anno);
  }

  /*
   * (non-Javadoc)
   * @see brn.swans.route.RouteDsrEtx.DiscoveryInterface#peek(jist.swans.net.NetMessage, jist.swans.mac.MacAddress, jist.swans.misc.MessageAnno)
   */
  public void peek(NetMessage msg, MacAddress lastHop, MessageAnno anno) {
    if (!(msg instanceof NetMessage.Ip))
      return;

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

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

    processOptions(mcExORMsg, anno, lastHop, ipMsg.getSrc(), ipMsg.getDst(),
        ipMsg.getProtocol(), ipMsg.getPriority(), ipMsg.getTTL(),
            ipMsg.getId(), ipMsg.getFragOffset());
  }

  /*
   * (non-Javadoc)
   * @see brn.swans.route.RouteDsrEtx.DiscoveryInterface#send(jist.swans.net.NetMessage, jist.swans.misc.MessageAnno)
   */
  public void send(NetMessage msg, MessageAnno anno) {
    NetMessage.Ip ipMsg = (NetMessage.Ip) msg;

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

    if (route == null) {
      sendBuffer.getProxy().insertBuffer(ipMsg, anno);
      activeRequests.add(ipMsg.getDst());
      discoverRoute(ipMsg.getDst(), nextRequestId++);
    } else {
      sendWithRoute(ipMsg, anno, route);
    }
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.net.NetInterface.NetHandler#receive(jist.swans.misc.Message, jist.swans.net.NetAddress, jist.swans.mac.MacAddress, byte, jist.swans.net.NetAddress, byte, byte, jist.swans.misc.MessageAnno)
   */
  public void receive(Message msg, NetAddress src, MacAddress lastHop, byte macId, NetAddress dst, byte priority, byte ttl, MessageAnno anno) {
    // pass ...
  }

  /*
   * (non-Javadoc)
   * @see brn.swans.route.RouteDsrBrnInterface.Discovery#handleTransmitError(jist.swans.net.NetMessage.Ip, jist.swans.misc.MessageAnno)
   */
  public void handleTransmitError(NetMessage.Ip msg, MessageAnno anno) {
    if (msg.getProtocol() != Constants.NET_PROTOCOL_MCEXOR)
      return;
    RouteDsrBrnMsg mcExORMsg = (RouteDsrBrnMsg) msg.getPayload();

    // If this nodle is the source of the message, must simply
    // remove the
    // broken link from the route cache
    if (msg.getSrc().equals(localAddr)) {
      NetAddress unreachableAddress = null;

      // Find out what the unreachable address was
      if (!mcExORMsg.hasOption(RouteDsrBrnMsg.OPT_SOURCE_ROUTE)) {
        unreachableAddress = msg.getDst();
      } else {
        Iterator iter = mcExORMsg.getOptions().iterator();
        while (iter.hasNext()) {
          RouteDsrBrnMsg.Option opt = (RouteDsrBrnMsg.Option) iter.next();
          if (opt.getType() == RouteDsrBrnMsg.OPT_SOURCE_ROUTE) {
            RouteDsrBrnMsg.OptionSourceRoute srcRoute =
              (RouteDsrBrnMsg.OptionSourceRoute) opt;

            unreachableAddress = srcRoute == null ? msg.getDst() :
              srcRoute.nextRecipient(msg.getDst());
            break;
          }
        }
      }

      // Remove the broken link from the cache, then try to
      // retransmit the
      // message if we know any other routes to the destination
      //RemoveCachedLink(localAddr, unreachableAddress);
      removeLinkFromLinkTable(localAddr, unreachableAddress);

      if (getRouteFromLinkTable(msg.getDst()) != null)
        checkBuffer(msg.getDst());
    } else {
      // Otherwise, must send Route Error message to the
      // originator
      // of this message
      sendRouteError(mcExORMsg, msg.getSrc(), msg.getDst());
    }
  }

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

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

      /** route discovery packets has a higher priority than normal packets ({@link Constants.NET_PRIORITY_D_NETWORKCONTROL}). */
      NetMessage.Ip routeRequestMsg = new NetMessage.Ip(routeRequest,
              localAddr, NetAddress.ANY, Constants.NET_PROTOCOL_MCEXOR,
              Constants.NET_PRIORITY_D_NETWORKCONTROL, Constants.TTL_DEFAULT);

      dsr.send(routeRequestMsg, Constants.NET_INTERFACE_DEFAULT,
              MacAddress.ANY, new MessageAnno());
      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);
      }

      entry.numRequestsSinceLastReply++;
    }
  }

}
