package brn.swans.route;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import jist.runtime.JistAPI;
import jist.swans.Constants;
import jist.swans.mac.MacAddress;
import jist.swans.misc.MessageAnno;
import jist.swans.net.NetAddress;
import jist.swans.net.NetMessage;
import jist.swans.net.NetMessage.Ip;

import org.apache.log4j.Logger;

import brn.swans.route.RouteDsrBrnMsg.OptionSourceRoute;
import brn.swans.route.metric.ArpTableInterface;

class _forwarding {
  public static interface PassiveAck {
    /**
     * Transmits the given packet with a request for a network-level
     * acknowledgement. The packet is retransmitted if no acknowledgement is
     * received before the timeout elapses.
     *
     * @param msg            the message to send
     * @param ackId          the ID number of the acknowledgement request
     * @param timeout        the timeout before retransmitting the packet
     * @param numRetransmits the number of times <code>msg</code> has already been
     *                       retransmitted
     */
    void transmitWithNetworkAck(NetMessage.Ip msg, MessageAnno anno,
                                Short ackId, long timeout, int numRetransmits);

    /**
     * Transmits the given packet and waits for a passive acknowledgement. If no
     * passive acknowledgement is received before a timeout occurs, the packet
     * is retransmitted. If no acknowledgement is received after
     * <code>TRY_PASSIVE_ACKS</code> attempts, the packet is retransmitted
     * with a request for a network-level acknowledgement.
     *
     * @param msg            the message to be sent
     * @param numRetransmits the number of times <code>msg</code> has already been
     *                       retransmitted
     */
    void transmitWithPassiveAck(NetMessage.Ip msg, MessageAnno anno,
                                int numRetransmits);
  }

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

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

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

    /**
     * @param msg
     * @param anno
     * @param ackId
     * @param timeout
     * @param numRetransmits
     * @see brn.swans.route._forwarding.PassiveAck#transmitWithNetworkAck(jist.swans.net.NetMessage.Ip, jist.swans.misc.MessageAnno, java.lang.Short, long, int)
     */
    public void transmitWithNetworkAck(Ip msg, MessageAnno anno, Short ackId,
                                       long timeout, int numRetransmits) {
      dlg.transmitWithNetworkAck(msg, anno, ackId, timeout, numRetransmits);
    }

    /**
     * @param msg
     * @param anno
     * @param numRetransmits
     * @see brn.swans.route._forwarding.PassiveAck#transmitWithPassiveAck(jist.swans.net.NetMessage.Ip, jist.swans.misc.MessageAnno, int)
     */
    public void transmitWithPassiveAck(Ip msg, MessageAnno anno,
                                       int numRetransmits) {
      dlg.transmitWithPassiveAck(msg, anno, numRetransmits);
    }
  }
}

public class RouteDsrForwardingPassiveAck extends RouteDsrBrn implements 
    _forwarding.PassiveAck {

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

  /**
   * The timeout before retransmitting a packet using network-level
   * acknowledgments.
   */
  public static final long MAINT_PERIOD = 20 * Constants.MILLI_SECOND;

  /**
   * The timeout before retransmitting a packet using passive
   * acknowledgments.
   */
  public static final long PASSIVE_ACK_TIMEOUT = 50 * Constants.MILLI_SECOND;

  /**
   * The number of times to try retransmission using passive acknowledgments.
   */
  public static final int TRY_PASSIVE_ACKS = 6;

  /**
   * The maximum number of times a packet will be retransmitted using
   * network-level acknowledgments.
   */
  public static final int MAX_MAINT_REXMT = 3;

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

  /**
   * Entries in the Maintenance Buffer correspond to messages that have been
   * sent and are currently waiting passive acknowledgments. An overheard
   * message is taken as a passive acknowledgment of a previously sent
   * message if they have equal source addresses, destination addresses,
   * protocol numbers, id numbers, fragmentation offsets, and if the Segments
   * Left field of the Source Route option of the overheard message has a
   * lower value than the corresponding field in the sent message.
   */
  private class MaintenanceBufferEntry {
    /**
     * Source address.
     */
    public NetAddress src;

    /**
     * Destination address.
     */
    public NetAddress dest;

    /**
     * Network protocol.
     */
    public short protocol;

    /**
     * IP Identification number.
     */
    public short id;

    /**
     * IP Fragmentation Offset.
     */
    public short fragOffset;

    /**
     * Creates a new <code>MaintenanceBufferEntry</code>.
     *
     * @param src        source address
     * @param dest       destination address
     * @param protocol   network protocol
     * @param id         IP Identification number
     * @param fragOffset IP Fragmentation Offset
     */
    public MaintenanceBufferEntry(NetAddress src, NetAddress dest,
        short protocol, short id, short fragOffset) {
      this.src = src;
      this.dest = dest;
      this.protocol = protocol;
      this.id = id;
      this.fragOffset = fragOffset;
    }

    /**
     * {@inheritDoc}
     */
    public int hashCode() {
      return src.hashCode() + dest.hashCode() + protocol + id + fragOffset;
    }

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

      MaintenanceBufferEntry other = (MaintenanceBufferEntry) o;

      return other.src.equals(src) && other.dest.equals(dest)
          && other.protocol == protocol && other.id == id
          && other.fragOffset == fragOffset;
    }
  }

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

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

  /**
   * Maintenance Buffer. Only messages awaiting passive acknowledgement (not
   * messages awaiting network-level acknowledgement) are stored in here. It
   * maps <code>MaintenanceBufferEntry</code> s to <code>Integer</code> s
   * representing the Segments Left field of the Source Route option of the
   * corresponding message.
   */
  private Hashtable maintenanceBuffer;

  /**
   * The next ID number to use when sending an acknowledgement request.
   */
  private short nextAckId;

  /**
   * Set of <code>Short</code> s indicating outstanding acknowledgement
   * requests.
   */
  private HashSet activeAcks;

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

  /**
   * Relf-referencing proxy
   */
  protected _forwarding.PassiveAck self;

  /** maps maintenance entries to time, for duplicate detection */
  protected Map duplicateMap = new HashMap();

  /**
   * Constructs a forwarding object using passive and network acks.
   *
   * @param localAddr address of local node.
   * @param arp address resolver.
   */
  public RouteDsrForwardingPassiveAck(NetAddress localAddr, ArpTableInterface arp) {
    super(localAddr, arp);
    this.localAddr = localAddr;

    maintenanceBuffer = new Hashtable();

    nextAckId = 0;
    activeAcks = new HashSet();

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

  /**
   * Processes an incoming Acknowledgement Request option. If the packet
   * containing the Acknowledgement Request is destined for this node, then a
   * packet is returned containing an Acknowledgement option. No
   * retransmission of the acknowledgement is performed.
   *
   * @param msg         the <code>RouteMcExORMsg</code> containing the
   *                    Acknowledgement Request
   * @param anno
   * @param opt         the Acknowledgement Request option
   * @param src         the originator of the Acknowledgement Request
   * @param dst         the destination of the Acknowledgement Request
   * @param sourceRoute the Source Route option that came in the same message as the
   *                    Acknowledgement Request. This parameter can be
   *                    <code>null</code> if there was no Source Route option.
   */
  private void handleAckRequest(RouteDsrBrnMsg msg, MessageAnno anno,
      RouteDsrBrnMsg.OptionAckRequest opt, NetAddress src, NetAddress dst,
      RouteDsrBrnMsg.OptionSourceRoute sourceRoute) {

    if (localAddr.equals(sourceRoute == null ? 
        dst : sourceRoute.nextRecipient(dst))) {
      // The ack request is meant for me, so respond to it
      NetAddress ackDest = sourceRoute == null ? 
          src : sourceRoute.prevRecipient(src);

      RouteDsrBrnMsg mcExORMsg = new RouteDsrBrnMsg();
      mcExORMsg.addOption(new RouteDsrBrnMsg.OptionAck(opt.getId(), localAddr,
          ackDest));

      NetMessage.Ip ipMsg = new NetMessage.Ip(mcExORMsg, localAddr, ackDest,
          Constants.NET_PROTOCOL_MCEXOR, Constants.NET_PRIORITY_D_BESTEFFORT,
          Constants.TTL_DEFAULT);

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

  /**
   * Processes an incoming Acknowledgement option. If this Acknowledgement was
   * intended for this node, then the packet containing the corresponding
   * Acknowledgement Request will not be retransmitted.
   *
   * @param opt  the Acknowledgement option
   * @param dest the destination of the Acknowledgement
   */
  private void handleAck(RouteDsrBrnMsg.OptionAck opt, NetAddress dest) {
    if (localAddr.equals(dest)) {
      activeAcks.remove(new Short(opt.getId()));
    }
  }

  /**
   * 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.
   */
  private void transmit(NetMessage.Ip msg, MessageAnno anno) {
    RouteDsrBrnMsg mcExORMsg = (RouteDsrBrnMsg) msg.getPayload();

    // Remove any old acknowlegement requests from the McExOR header, in
    // the case we are forwarding the packet.
    Iterator iter = mcExORMsg.getOptions().iterator();
    while (iter.hasNext()) {
      RouteDsrBrnMsg.Option option = (RouteDsrBrnMsg.Option) iter.next();
      if (option.getType() == RouteDsrBrnMsg.OPT_ACK_REQUEST) {
        iter.remove();
      }
    }

    RouteDsrBrnMsg.OptionSourceRoute sourceRoute = mcExORMsg.getSourceRoute();
    if (sourceRoute == null || sourceRoute.getNumSegmentsLeft() == 0) {
      // Messages on their last hop must use network-level acknowledgements.
      // Add an Acknowledgement Request to the packet.
      RouteDsrBrnMsg newMsg = (RouteDsrBrnMsg) mcExORMsg.clone();

      Short ackId = new Short(nextAckId++);
      newMsg.addOption(new RouteDsrBrnMsg.OptionAckRequest(ackId.shortValue()));
      activeAcks.add(ackId);

      NetMessage.Ip ipMsg = new NetMessage.Ip(newMsg, msg.getSrc(), 
          msg.getDst(), msg.getProtocol(), msg.getPriority(), msg.getTTL(), 
          msg.getId(), msg.getFragOffset());

      self.transmitWithNetworkAck(ipMsg, anno, ackId, MAINT_PERIOD, 0);
      return;
    }

    // Otherwise add an entry to the Maintenance Buffer and try passive
    // acknolwedgements
    MaintenanceBufferEntry entry = new MaintenanceBufferEntry(msg.getSrc(), 
        msg.getDst(), msg.getProtocol(), msg.getId(), msg.getFragOffset());

    maintenanceBuffer.put(entry, new Integer(sourceRoute.getNumSegmentsLeft()));
    self.transmitWithPassiveAck(msg, anno, 0);
  }

  /**
   * Sends the given message and waits for a passive acknowledgment. If no
   * Acknowledgment is heard, the message will be retransmitted up to
   * <code>TRY_PASSIVE_ACKS</code> times.
   *
   * @param msg            the message to be sent
   * @param numRetransmits the number of times this message has already been
   *                       retransmitted. Callers should usually pass in zero for this.
   */
  public void transmitWithPassiveAck(NetMessage.Ip msg, MessageAnno anno,
      int numRetransmits) {
    RouteDsrBrnMsg mcExORMsg = (RouteDsrBrnMsg) msg.getPayload();
    RouteDsrBrnMsg.OptionSourceRoute sourceRoute = mcExORMsg.getSourceRoute();
    MaintenanceBufferEntry entry = null;

    if (sourceRoute != null && sourceRoute.getNumSegmentsLeft() > 0) {
      entry = new MaintenanceBufferEntry(msg.getSrc(), msg.getDst(), 
          msg.getProtocol(), msg.getId(), msg.getFragOffset());

      // If the maintenance buffer does not contain this entry, then it
      // has already been sent and acknowledged
      if (!maintenanceBuffer.containsKey(entry)) {
        return;
      }

      // If we have exceeded the maximum number of tries on passive
      // Acknowledgment, remove this entry from the maintenance buffer
      if (numRetransmits >= TRY_PASSIVE_ACKS) {
        maintenanceBuffer.remove(entry);
      }
    }

    if (sourceRoute == null || sourceRoute.getNumSegmentsLeft() == 0
        || numRetransmits >= TRY_PASSIVE_ACKS) {
      // Messages on their final hop and messages that have already tried and
      // failed to receive a passive acknowledgment must use network-level
      // acknowledgments
      RouteDsrBrnMsg newMsg = (RouteDsrBrnMsg) mcExORMsg.clone();

      Short ackId = new Short(nextAckId++);
      newMsg.addOption(new RouteDsrBrnMsg.OptionAckRequest(ackId.shortValue()));
      activeAcks.add(ackId);

      NetMessage.Ip ipMsg = new NetMessage.Ip(newMsg, msg.getSrc(), 
          msg.getDst(), msg.getProtocol(), msg.getPriority(), msg.getTTL(), 
          msg.getId(), msg.getFragOffset());

      transmitWithNetworkAck(ipMsg, anno, ackId, MAINT_PERIOD, 0);
      return;
    }

    if (retryEvent.isActive())
      retryEvent.handle(msg, anno, numRetransmits, true);
    
    netEntity.send(msg, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno);
    JistAPI.sleep(PASSIVE_ACK_TIMEOUT
        + (long) (Constants.random.nextDouble() * BROADCAST_JITTER));

    self.transmitWithPassiveAck(msg, anno, numRetransmits + 1);
  }

  /**
   * Sends the given message. The message should be a McExOR packet containing
   * an acknowledgement request with the given id. If no acknowledgement is
   * received within the given timeout, the packet will be retransmitted up to
   * <code>MAX_MAINT_REXMT</code> times.
   *
   * @param msg            the message to be sent
   * @param ackId          the ID number of the Acknowledgement Request
   * @param timeout        the number of clock ticks to wait before retransmitting the
   *                       message
   * @param numRetransmits the number of times this packet has already been transmitted.
   *                       Callers should normally pass in zero for this.
   */
  public void transmitWithNetworkAck(NetMessage.Ip msg, MessageAnno anno,
      Short ackId, long timeout, int numRetransmits) {
    if (!activeAcks.contains(ackId))
      return;

    if (numRetransmits > MAX_MAINT_REXMT) {
      // Max retransmissions exceeded -- must send Route Error to message
      // source
      activeAcks.remove(ackId);

      if (log.isDebugEnabled()) {
        log.debug(JistAPI.getTime() + ":" + this
            + " maximum retransmit couter " + " reached, drop packet from "
            + msg.getSrc() + " to " + msg.getDst() + "!");
      }

      handleTransmitError(msg, anno);
      return;
    }

    if (log.isDebugEnabled()) {
      if (numRetransmits > 0) {
        log.debug(JistAPI.getTime() + ":" + this + " retransmitting from "
            + msg.getSrc() + " to " + msg.getDst() + "!");
      }
    }

    if (retryEvent.isActive())
      retryEvent.handle(msg, anno, numRetransmits, false);

    netEntity.send(msg, Constants.NET_INTERFACE_DEFAULT, MacAddress.ANY, anno);
    JistAPI.sleep(timeout
        + (long) (Constants.random.nextDouble() * BROADCAST_JITTER));
    self.transmitWithNetworkAck(msg, anno, ackId, 2 * timeout,
        numRetransmits + 1);
  }

  /**
   * 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,
      NetAddress src, NetAddress dst, short protocol, byte priority, byte ttl,
      short id, short fragOffset) {
    Iterator iter = msg.getOptions().iterator();
    RouteDsrBrnMsg.OptionAckRequest ackRequest = null;
    RouteDsrBrnMsg.OptionSourceRoute sourceRoute = null;

    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_SOURCE_ROUTE:
        sourceRoute = (RouteDsrBrnMsg.OptionSourceRoute) opt;
        break;

      case RouteDsrBrnMsg.OPT_ACK_REQUEST:
        ackRequest = (RouteDsrBrnMsg.OptionAckRequest) opt;
        break;

      case RouteDsrBrnMsg.OPT_ACK:
        handleAck((RouteDsrBrnMsg.OptionAck) opt, dst);
        break;

      }
    }

    if (ackRequest != null) {
      // The McExOR spec has some contradictory instructions regarding how
      // to handle packets containing both acknowledgements and acknowledgement
      // requests (in section 8.3.3). It doesn't make any sense, so I'm
      // ignoring those instructions.
      handleAckRequest(msg, anno, ackRequest, src, dst, sourceRoute);
    }
  }

  /**
   * Checks the given message to see if it matches any of the messages in the
   * Maintenance Buffer for which we are currently awaiting passive passive
   * acknowledgements. If this message matches a message in the Maintenance
   * Buffer, that message will be removed from the buffer and will not be
   * retransmitted.
   *
   * @param msg        the message that has been overheard
   * @param src        the IP source of the message
   * @param dest       the IP destination of the message
   * @param protocol   the IP protocol of the message
   * @param id         the IP id number of the message
   * @param fragOffset the IP fragmentation offset of the message
   */
  private void checkForPassiveAck(RouteDsrBrnMsg msg, NetAddress src,
      NetAddress dest, short protocol, short id, short fragOffset) {
    RouteDsrBrnMsg.OptionSourceRoute sourceRoute = msg.getSourceRoute();

    if (sourceRoute == null)
      return;

    MaintenanceBufferEntry entry = new MaintenanceBufferEntry(src, dest,
        protocol, id, fragOffset);

    Integer segsLeft = (Integer) maintenanceBuffer.get(entry);
    if (segsLeft == null)
      return;

    if (segsLeft.intValue() > sourceRoute.getNumSegmentsLeft()) {
      maintenanceBuffer.remove(entry);
    }
  }

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

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

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

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

    checkForPassiveAck(mcExORMsg, ipMsg.getSrc(), ipMsg.getDst(), ipMsg
        .getProtocol(), ipMsg.getId(), ipMsg.getFragOffset());

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

  /* (non-Javadoc)
   * @see brn.swans.route.RouteDsrBrn#forwardPacket(brn.swans.route.RouteDsrBrnMsg, jist.swans.misc.MessageAnno, jist.swans.mac.MacAddress, brn.swans.route.RouteDsrBrnMsg.OptionSourceRoute, jist.swans.net.NetAddress, jist.swans.net.NetAddress, short, byte, byte, short, short)
   */
  @Override
  protected void forwardPacket(RouteDsrBrnMsg msg, MessageAnno anno,
      MacAddress lastHop, OptionSourceRoute opt, NetAddress src,
      NetAddress dest, short protocol, byte priority, byte ttl, short id,
      short fragOffset) {
    
    // check for duplicates before any further processing
    MaintenanceBufferEntry entry = new MaintenanceBufferEntry(src, dest, 
        protocol, id, fragOffset);
    if (duplicateMap.containsKey(entry)) {
      if (duplicateEvent.isActive())
        duplicateEvent.handle(msg, anno, arp.getArpEntry(lastHop), localAddr);
      // TODO duplicate handling
      return;
    }
    duplicateMap.put(entry, new Long(JistAPI.getTime()));
    
    super.forwardPacket(msg, anno, lastHop, opt, src, dest, protocol, priority,
        ttl, id, fragOffset);
  }

  /*
   * (non-Javadoc)
   * @see brn.swans.route.RouteDsrBrnInterface#send(jist.swans.net.NetMessage.Ip, int, jist.swans.mac.MacAddress, jist.swans.misc.MessageAnno)
   */
  public void send(Ip msg, int interfaceId, MacAddress nextHop, MessageAnno anno) {
    if (msg.getDst().equals(NetAddress.ANY)) {
      netEntity.send(msg, interfaceId, nextHop, anno);
      return;
    }
    
    if (candSelectedEvent.isActive()) {
      // TODO flow id
      Integer packetId = (Integer) anno.get(MessageAnno.ANNO_RTG_PACKETID);
      List lstMacCandidates = new ArrayList();
      lstMacCandidates.add(nextHop);
      if (null != packetId)
        candSelectedEvent.handle(packetId.intValue(), lstMacCandidates , msg, anno);
    }

    transmit(msg, anno);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.net.NetInterface.RawNetHandler#receive(jist.swans.net.NetMessage, jist.swans.misc.MessageAnno, jist.swans.mac.MacAddress, byte)
   */
  public void receive(NetMessage msg, MessageAnno anno, MacAddress lastHop,
      byte macId) {
    NetMessage.Ip ipmsg = (NetMessage.Ip) msg;
    
    MaintenanceBufferEntry entry = new MaintenanceBufferEntry(ipmsg.getSrc(), 
        ipmsg.getDst(), ipmsg.getProtocol(), ipmsg.getId(), ipmsg.getFragOffset());
    if (duplicateMap.containsKey(entry)) {
      RouteDsrBrnMsg brnMsg = (RouteDsrBrnMsg) ipmsg.getPayload();
      if (duplicateEvent.isActive())
        duplicateEvent.handle(brnMsg, anno, arp.getArpEntry(lastHop), localAddr);
      // TODO duplicate handling
      return;
    }
    duplicateMap.put(entry, new Long(JistAPI.getTime()));

    super.receive(msg, anno, lastHop, macId);
  }
}
