package brn.swans.mac;

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

import jist.runtime.JistAPI;
import jist.runtime.Main;
import jist.swans.Constants;
import jist.swans.mac.Mac802_11;
import jist.swans.mac.Mac802_11Message;
import jist.swans.mac.MacAddress;
import jist.swans.mac.MacDcfMessage;
import jist.swans.mac.MacInfo;
import jist.swans.mac.MacMessage;
import jist.swans.mac.MacMessageFactory;
import jist.swans.mac.MacMessage.AbstractMacMessage;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.misc.Util;
import jist.swans.net.NetAddress;
import jist.swans.net.NetInterface;
import jist.swans.net.NetMessage;
import jist.swans.phy.PhyMessage;
import jist.swans.radio.RadioInfo;
import jist.swans.rate.RateControlAlgorithmIF;

import org.apache.log4j.Logger;

import brn.swans.net.NetTxDORInterface;

/**
 * Mac for tx diversiy opportunistic routing
 *
 * TODO should we promisc store all data and try to support with txdiv,
 * even if we are no candidate? Do we even need candidates or could we operate
 * completely passive?
 *
 * TODO is it possible to share the resposibility of a packet between two or
 * more mac entities? If several nodes send a packet and only the responsible
 * node misses the ack, it will (unnecessarily) try again.
 * workaround NUGGET : if an duplicate rts is received, do not send a cts
 * (and prevent other nodes from sending a cts, i.e. scramble it?). So the
 * sender will not send the data packet and we will send an ack, hoping that
 * this will satisfy the sender.
 *
 * @author kurth
 */
public class MacTxDOR extends Mac802_11 implements MacTxDORInterface {

  /** MAC logger. */
  public static final Logger log = Logger.getLogger(MacTxDOR.class);

  protected static Class classMacTxDORMessage = MacTxDORMessage.class;

  // ////////////////////////////////////////////////
  // helper classes
  //
  
  public static class ForwardBufferKey {

    /** ip packet source address. */
    private NetAddress src;

    /** ip packet identification. */
    private short id;

    /**
     * @param src
     * @param id
     */
    public ForwardBufferKey(NetAddress src, short id) {
      this.src = src;
      this.id = id;
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + id;
      result = prime * result + ((src == null) ? 0 : src.hashCode());
      return result;
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      final ForwardBufferKey other = (ForwardBufferKey) obj;
      if (id != other.id)
        return false;
      if (src == null) {
        if (other.src != null)
          return false;
      } else if (!src.equals(other.src))
        return false;
      return true;
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString() {
      return getSrc().toString() + "/" + getId(); // + "/" + ttl;
    }

    public NetAddress getSrc() {
      return src;
    }

    public short getId() {
      return id;
    }
  }

  /**
   * An ip packet at a certain is identified using src, id and ttl.
   */
  public static class ForwardBufferEntry extends ForwardBufferKey {

    /** ip packet time-to-live. */
    private byte ttl;

    /**
     * address of the responsible forwarder. is needed to distuingish between
     * self forwarded packets and others.
     * NOTE: not included in hashCode etc
     * 
     * Contains all mac address of forwarders which were overheard promiscly. 
     * They are collected and given to the net layer.
     */
    private Set forwarder;

    /** the received data frame, or null */
    private MacTxDORMessage.Data msg;
    /** the received data frame annotation, or null */
    private MessageAnno msgAnno;

    /** whether the net received the packet already */
    private boolean netReceived;
    
    /** whether we have transmitted the frame */
    private boolean transmitted;
    
    /** whether the frame reachted the final destination */ 
    private boolean reachedDst;

    private long lastUpdate;

    /**
     * @param src
     * @param id
     */
    public ForwardBufferEntry(NetAddress src, short id) {
      super(src, id);
      this.ttl = (byte)-1;
      this.forwarder = new HashSet();
      this.msg = null;
      this.msgAnno = null;
      this.netReceived = false;
      this.reachedDst = false;
      this.transmitted = false;
      this.lastUpdate = JistAPI.getTime();
    }
    
    public void update() {
      lastUpdate = JistAPI.getTime();
    }

    public Set getForwarder() {
      return forwarder;
    }

    /**
     * Set forwarder and associated ttl. we remember always the latest forwarder
     * and ttl (i.e. lowest ttl).
     *
     * @param forwarder
     * @param ttl
     */
    public void addForwarder(Set forwarder, byte ttl) {
      this.forwarder.addAll(forwarder);
      if (ttl < this.ttl)
        this.ttl = ttl;
    }

    /**
     * @see #addForwarder(Set, byte)
     */
    public void addForwarder(MacAddress forwarder, byte ttl) {
      this.forwarder.add(forwarder);
      if (ttl < this.ttl)
        this.ttl = ttl;
    }

    /**
     * @return the msg
     */
    public MacTxDORMessage.Data getMsg() {
      return msg;
    }

    /**
     * @param msg the msg to set
     */
    public void setMsg(MacTxDORMessage.Data msg, MessageAnno anno, boolean netReceived) {
      this.msg = msg;
      this.msgAnno = anno;
      this.netReceived = netReceived;
    }

    public MessageAnno getMsgAnno() {
      return msgAnno;
    }

    /**
     * @return the netReceived
     */
    public boolean isNetReceived() {
      return netReceived;
    }

    /**
     * @param netReceived the netReceived to set
     */
    public void setNetReceived(boolean netReceived) {
      this.netReceived = netReceived;
    }

    /**
     * @return the ttl
     */
    public byte getTtl() {
      return ttl;
    }

    /**
     * @return the reachedDst
     */
    public boolean isReachedDst() {
      return reachedDst;
    }

    /**
     * @param reachedDst the reachedDst to set
     */
    public void setReachedDst(boolean reachedDst) {
      this.reachedDst = reachedDst;
    }

    /**
     * @return the transmitted
     */
    public boolean isTransmitted() {
      return transmitted;
    }

    /**
     * @param transmitted the transmitted to set
     */
    public void setTransmitted(boolean transmitted) {
      this.transmitted = transmitted;
    }

    /**
     * @param ttl the ttl to set
     */
    public void setTtl(byte ttl) {
      this.ttl = ttl;
    }

    /**
     * @return the lastUpdate
     */
    public long getLastUpdate() {
      return lastUpdate;
    }
  }

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

  public static final MacAddress ADDR_ANYCAST = new MacAddress(-3);

  private static final long FWDBUFFER_STALE_TIMEOUT = 3 * Constants.SECOND;


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

  /** stores packets to forward, realized passive forwarder selection */
  protected Map forwardBuffer;

  protected NetTxDORInterface netEntity;

  private MacTxDORMessageFactory msgFactory;

  /** size of the current or last candidate set size, for backoff calculation */
//  private int lastCsSize;

  /** whether to use txdiv for data packets */
  private boolean useDataTxDiv;

  /** whether to ignore nav in rts and cts packets */
  private boolean ignoreRtsCtsNav;

  /**
   * whether to use the ack cancelation shema to prevent the tx of
   * non-innovative packets
   */
  private boolean useAckCancelation;

  /** whether to remember all promisc received packets */
  private boolean promiscStorePackets;

  private boolean sendImmediate;

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

  /**
   * Creates a mac object
   *
   * @param addr
   * @param radioInfo
   * @param macInfo
   * @param rateSelection
   */
  public MacTxDOR(MacAddress addr, RadioInfo radioInfo,
      MacInfo macInfo, RateControlAlgorithmIF rateSelection) {
    super(addr, radioInfo, macInfo, rateSelection);

    this.forwardBuffer = new HashMap();
    this.sendImmediate = false;

    //    this.lastCsSize = 0;
    this.useDataTxDiv = true;
    this.ignoreRtsCtsNav = false;
    this.useAckCancelation = true;
    this.promiscStorePackets = false;

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


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

  /**
   * @return the useDataTxDiv
   */
  public boolean isUseDataTxDiv() {
    return useDataTxDiv;
  }

  /**
   * @param useDataTxDiv the useDataTxDiv to set
   */
  public void setUseDataTxDiv(boolean useDataTxDiv) {
    this.useDataTxDiv = useDataTxDiv;
  }

  /**
   * @return the ignoreRtsCtsNav
   */
  public boolean isIgnoreRtsCtsNav() {
    return ignoreRtsCtsNav;
  }

  /**
   * @param ignoreRtsCtsNav the ignoreRtsCtsNav to set
   */
  public void setIgnoreRtsCtsNav(boolean ignoreRtsCtsNav) {
    this.ignoreRtsCtsNav = ignoreRtsCtsNav;
  }

  public boolean isUseAckCancelation() {
    return useAckCancelation;
  }

  public void setUseAckCancelation(boolean useAckCancelation) {
    this.useAckCancelation = useAckCancelation;
  }

  /**
   * @return the promiscStorePackets
   */
  public boolean isPromiscStorePackets() {
    return promiscStorePackets;
  }

  /**
   * @param promiscStorePackets the promiscStorePackets to set
   */
  public void setPromiscStorePackets(boolean promiscStorePackets) {
    this.promiscStorePackets = promiscStorePackets;
  }

  /**
   * sets member msgFactory
   */
  public void setMsgFactory(MacMessageFactory.Dcf msgFactory) {
    this.msgFactory = (MacTxDORMessageFactory)msgFactory;
    super.setMsgFactory(msgFactory);
    this.msgFactory.setMac(this);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#setNetEntity(jist.swans.net.NetInterface, byte)
   */
  public void setNetEntity(NetInterface net, byte netid) {
    this.netEntity = (NetTxDORInterface) net;
    super.setNetEntity(net, netid);
  }

  public int getMode() {
    return mode;
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.Mac802_11#getRetry()
   */
  public byte getRetry() {
    return super.getRetry();
  }

  public short getSeq() {
    return this.seq;
  }

  // ////////////////////////////////////////////////
  // implementation
  //

  /**
   * Checks whether the packet is for this mac entity.
   * @param msg the packet with candidate set.
   * @return whether the packet is for this mac entity.
   */
  private boolean isForMe(MacTxDORMessage msg) {
    MacMessage.HasCandidates msgAnycast = (MacMessage.HasCandidates)
      msg.getAdapter(AbstractMacMessage.classHasCandidates);

    if (null != msgAnycast)
      return msgAnycast.getCandidates().contains(localAddr);

    return localAddr.equals(msg.getDst());
  }

  /**
   * Convert to conventional message
   *
   * @param packet the message to convert
   * @param anno associated message anno
   * @param dst the destination to set into the generated packet
   * @return the conventional message that corresponds to the given message.
   */
  private MacDcfMessage convertMessage(MacTxDORMessage packet, MessageAnno anno,
      MacAddress dst) {
    MacDcfMessage ret = null;

    if (packet.getType() == MacDcfMessage.TYPE_DATA) {
      MacTxDORMessage.Data msg = (MacTxDORMessage.Data) packet;
      NetMessage.Ip ipMsg = (NetMessage.Ip) msg.getBody();

      // Transform into an ordinary mac message
      ret = msgFactory.createDataUnicast(dst,
          msg.getSrc(), msg.getDuration(), msg.getSeq(), msg.getRetry(),
          msg.getBody(), anno);

      // put information for ack creation in annotations
      anno.put(MessageAnno.ANNO_MAC_NETSRC, ipMsg.getSrc());
      anno.put(MessageAnno.ANNO_MAC_NETID, new Short(ipMsg.getId()));
      anno.put(MessageAnno.ANNO_MAC_NETTTL, new Byte(ipMsg.getTTL()));

      // remember candidates and own index in annotations
      anno.put(MessageAnno.ANNO_MAC_CANDIDATES, msg.getCandidates());
      anno.put(MessageAnno.ANNO_MAC_FINALDST_IDX, new Byte(msg.getIdxFinalDst()));
      if (Main.ASSERT)
        Util.assertion(msg.getIdxFinalDst() < msg.getCandidates().size());

      if (isForMe(packet))
        anno.put(MessageAnno.ANNO_MAC_CAND_IDX,
            new Integer(msg.getCandidates().indexOf(localAddr)));
    }
    else if (packet.getType() == Mac802_11Message.TYPE_RTS) {
      MacTxDORMessage.Rts msg = (MacTxDORMessage.Rts) packet;

      // Transform into an ordinary mac message
      ret = msgFactory.createRts(dst, msg.getSrc(), msg.getDuration(), null, null);

      // remember candidates in annotations
      anno.put(MessageAnno.ANNO_MAC_CANDIDATES, msg.getCandidates());
      anno.put(MessageAnno.ANNO_MAC_FINALDST_IDX, new Byte(msg.getIdxFinalDst()));
      anno.put(MessageAnno.ANNO_MAC_NETSRC, msg.getNetSrc());
      anno.put(MessageAnno.ANNO_MAC_NETID, new Short(msg.getNetId()));
      anno.put(MessageAnno.ANNO_MAC_NETTTL, new Byte(msg.getNetTTL()));
      anno.put(MessageAnno.ANNO_MAC_SEQNO, new Short(msg.getSeqNo()));
      anno.put(MessageAnno.ANNO_MAC_RETRY, new Boolean(msg.isRetry()));

      if (isForMe(packet))
        anno.put(MessageAnno.ANNO_MAC_CAND_IDX,
            new Integer(msg.getCandidates().indexOf(localAddr)));
    }
    else if (packet.getType() == MacDcfMessage.TYPE_ACK) {
      ret = packet;
    }
    else if (packet.getType() == Mac802_11Message.TYPE_CTS) {
      ret = packet;
    }

    return ret;
  }


  /**
   * Passively scan incoming packets to select the forwarder for a particular
   * packet. Only data and ack packets are considered.
   *
   * @param msg the incoming data or ack packet.
   * @param anno the corresponding anno.
   */
  private void selectForwarder(MacTxDORMessage msg, MessageAnno anno) {
    ForwardBufferEntry entry = null;
    List dsts = new ArrayList();
    MacAddress src = MacAddress.NULL;

    // remember message to be able to scan for it passively
    if (msg.getType() == MacDcfMessage.TYPE_DATA) {
      MacTxDORMessage.Data msgData = (MacTxDORMessage.Data) msg;
      NetMessage.Ip ipMsg = (NetMessage.Ip) msgData.getBody();
      src = msgData.getSrc();
      entry = new ForwardBufferEntry(ipMsg.getSrc(), ipMsg.getId());
      entry.setTtl(ipMsg.getTTL());
      entry.addForwarder(msgData.getSrc(), ipMsg.getTTL());
      if (this.promiscStorePackets || isForMe(msg))
        entry.setMsg(msgData, anno, isForMe(msg));
    }
    else if (msg.getType() == MacDcfMessage.TYPE_ACK) {
      MacTxDORMessage.Ack msgAck = (MacTxDORMessage.Ack) msg;
      dsts.add(msgAck.getDst());
      entry = new ForwardBufferEntry(msgAck.getNetSrc(), msgAck.getNetId());
      entry.setTtl(msgAck.getNetTTL());
      entry.addForwarder(msgAck.getDst(), msgAck.getNetTTL());
      entry.setReachedDst(msgAck.isFromFinalDst());
    }
    else
      return;

    // update forward buffer
    ForwardBufferKey key = new ForwardBufferKey(entry.getSrc(), entry.getId());
    ForwardBufferEntry tmp = (ForwardBufferEntry) forwardBuffer.get(key);
    if (null == tmp) {
      forwardBuffer.put(key, entry);
      tmp = entry;
    } else {
      tmp.update();
      if (entry.isTransmitted()) tmp.setTransmitted(true);
      if (entry.isReachedDst())  tmp.setReachedDst(true);
      tmp.addForwarder(entry.getForwarder(), entry.getTtl());
      if (null != entry.getMsg())
        tmp.setMsg(entry.getMsg(), entry.getMsgAnno(),
            tmp.isNetReceived() || entry.isNetReceived());
    }
    anno.put(MessageAnno.ANNO_MAC_FORWARDER, tmp.getForwarder());

    /*
     * cancel our own transmission if we received an passive ack.
     * NUGGET: cancel only if incoming message is an ack or data.
     * in the case of rts or cts, we could additionally use txdiv!
     */
    if (msg.getType() == MacDcfMessage.TYPE_ACK
        || msg.getType() == MacDcfMessage.TYPE_DATA) {

      /*
       * case 1: an ack contains our address. do not cancel if we are the
       * recipient of the ack, since we have to case about the packet. Otherwise
       * we wont recognize our own acks.
       *
       * case 2: we did not hear the cts, but another station did and sent the
       * packet. in this case we should not give up the responsibility for
       * the packet.
       */
      if (!dsts.contains(localAddr) && !src.equals(localAddr)) {
        if (null != packet
            && alreadyForwarded((NetMessage.Ip) packet)) {
          // inform about packet cancelation
          netEntity.endSend(packet, netId, anno);
          cancelTimer();
          incSeq(); // inc seq so that we do not use a seq number twice!
          resetRetry();
          decCW();
          this.packet = null;
          this.anno = null;
          this.packetNextHop = null;
          // reset fsm, otherwise fsm will not recover from state wf_ack
          setMode(MAC_MODE_SIDLE);
        }
      }
    }
  }

  /**
   * Check if the packet will be innovative or redundant. In the latter case,
   * do not send an cts, but send an ack instead (actually, send two acks: the
   * first in place of the cts, the second in place of the data packet).
   * NOTE: here we are using txdiv, too. If not all candidates agree on the
   * innovation point, some will send an cts and some will send an ack. Hopefully
   * the result will be scrambled at the rts sender. The sender will not start
   * to transmit the data packet.
   * Using the nav protection all nodes with a non-innovative decision will
   * send a second ack using txdiv which should cancel the transmission at
   * the sender.
   *
   * auf last hop nur ack cancelation von final destination, und
   * nur wenn ack von final dst gesehen machen andere mit
   *
   * @param msgRts
   * @param anno
   */
  private boolean isInnovative(MacTxDORMessage.Rts msgRts, MessageAnno anno) {
    boolean isFinalDst = false;
    
    // if the final destination is contained, do not cancel the transmission
    if (Main.ASSERT)
      Util.assertion(msgRts.getIdxFinalDst() < msgRts.getCandidates().size());
    MacAddress finalDst = (msgRts.getIdxFinalDst() < 0 ? null :
      (MacAddress)msgRts.getCandidates().get(msgRts.getIdxFinalDst()));
    if (null != finalDst && !finalDst.equals(localAddr))
      isFinalDst = true;

    ForwardBufferEntry entry = (ForwardBufferEntry) forwardBuffer.get(
        new ForwardBufferKey(msgRts.getNetSrc(), msgRts.getNetId()));

    if (isFinalDst 
        && (null == entry || !entry.isReachedDst()))
      return true;

    // if we have a forwarder, the ack was lost or the packet was faster using
    // a different way. Anyway, the transmission is not innovative.
    // We have to inspect the source field, we will sometimes lose packets
    if (null != entry) {
      // ignore packets with lower ttl which we do not intend to forward 
      // (e.g. retransmissions)
      if (!entry.isReachedDst() 
          && entry.isTransmitted() 
          && entry.getTtl() > msgRts.getNetTTL()) {
        log.error(this + "(" + JistAPI.getTime() + "): received packet id=" 
            + msgRts.getNetId() + " twice, error in candidate selection.");
      }

      // isTransmitted should be redundant
      if (null != entry.getMsg()
          || entry.isTransmitted()
          || entry.isReachedDst()) {
        return false;
      }
    }

    return true;
  }

  /**
   * @see MacTxDOR#isInnovative(MacTxDORMessage.Rts, MessageAnno)
   */
  private void cancelNonInnovativeTx(MacTxDORMessage.Rts msgRts, MessageAnno anno) {
    if (nav.waitingNav() || mode == MAC_MODE_SWFACK || mode == MAC_MODE_SWFCTS)
      return;
    
    checkForPassiveReceive(msgRts, anno);

    // we must not be in a receive process
    if (Main.ASSERT)
      Util.assertion(null == dataRcvd);
    this.rtsRcvd = null;
    this.rtsRcvdAnno = null;

    if (sendAckCancelationEvent.isActive())
      sendAckCancelationEvent.handle(msgRts, anno);

    // convert to conventional message
    Mac802_11Message.Rts msg = (Mac802_11Message.Rts)
      convertMessage(msgRts, anno, localAddr);

    long dataTxStartTime = JistAPI.getTime()
      + getSifs()
      + transmitTime(msgFactory.getSize(Mac802_11Message.TYPE_CTS, msg, anno), controlRate)
      + Constants.PROPAGATION
      + getTxSifs();

    // send ack instead of cts
    cancelTimer();
    setMode(MAC_MODE_SIFS);
    JistAPI.sleep(getTxSifs());
    sendAckFromRts(msg, anno);

    // send second ack at start of data
    if (Main.ASSERT)
      Util.assertion(dataTxStartTime - JistAPI.getTime() > 0);
    cancelTimer();
    setMode(MAC_MODE_SIFS);
    JistAPI.sleep(dataTxStartTime - JistAPI.getTime());
    sendAckFromRts(msg, anno);

    self.cfDone(false, false);

    /*
     * treat as ordinary transmission: the previous node was forwarder and
     * we have to forward further. update forward buffer and cancel own 
     * transmission if necessary.
     */
    if (null != packet
        && alreadyForwarded((NetMessage.Ip) packet)) {
      // inform about packet cancelation
      netEntity.endSend(packet, netId, anno);
      resetRetry();
      decCW();
      this.packet = null;
      this.anno = null;
      this.packetNextHop = null;
    }
  }


  
  
  
  /**
   * Check the forward buffer if we promisc received the packet already, but have
   * not given it to the network layer. if so, give it to the mac and mark the
   * packet appropreately.
   *
   * @param msgRts the incoming rts packet
   * @param annoRts the annotation belonging to the rts
   * @return true if the packet has been given to the net, false otherwise
   */
  private boolean checkForPassiveReceive(MacTxDORMessage.Rts msgRts, MessageAnno annoRts) {
    // check if we have already given the packet to the net, and do so if not
    ForwardBufferEntry entry = (ForwardBufferEntry) forwardBuffer.get(
        new ForwardBufferKey(msgRts.getNetSrc(), msgRts.getNetId()));
    if (entry.isNetReceived() && entry.getTtl() <= msgRts.getNetTTL()) {
      return false;
    }
    if (entry.isTransmitted() || entry.isReachedDst()) {
      return false;
    }

    MacDcfMessage.Data newMsg;
    MessageAnno newAnno = (MessageAnno) entry.getMsgAnno().clone();
    { // convert to conventional message
      MacTxDORMessage.Data msg = (MacTxDORMessage.Data) entry.getMsg();
      NetMessage.Ip ipMsg = (NetMessage.Ip) msg.getBody();

      // NOTE: we must set the correct ttl here
      if(ipMsg.isFrozen()) ipMsg = ipMsg.copy();
      ipMsg.setTTL(msgRts.getNetTTL());
      ipMsg = ipMsg.freeze();

      // Transform into an ordinary mac message
      newMsg = msgFactory.createDataUnicast(localAddr,
          msgRts.getSrc(), msg.getDuration(), msgRts.getSeqNo(), msgRts.isRetry(),
          ipMsg, newAnno);

      // put information for ack creation in annotations
      newAnno.put(MessageAnno.ANNO_MAC_NETSRC, ipMsg.getSrc());
      newAnno.put(MessageAnno.ANNO_MAC_NETID, new Short(ipMsg.getId()));
      newAnno.put(MessageAnno.ANNO_MAC_NETTTL, new Byte(ipMsg.getTTL()));

      // remember candidates and own index in annotations
      newAnno.put(MessageAnno.ANNO_MAC_CANDIDATES, msgRts.getCandidates());
      newAnno.put(MessageAnno.ANNO_MAC_FINALDST_IDX, new Byte(msgRts.getIdxFinalDst()));
      newAnno.put(MessageAnno.ANNO_MAC_CAND_IDX,
            new Integer(msgRts.getCandidates().indexOf(localAddr)));
      if (Main.ASSERT)
        Util.assertion(0 <= msgRts.getCandidates().indexOf(localAddr)
            && msgRts.getCandidates().indexOf(localAddr) < msgRts.getCandidates().size());

      entry.addForwarder(msgRts.getSrc(), msgRts.getNetTTL());
      newAnno.put(MessageAnno.ANNO_MAC_FORWARDER, entry.getForwarder());
    }

    if (forwarderEvent.isActive())
      forwarderEvent.handle(newMsg, newAnno, localAddr);
    if (receiveEvent.isActive())
      receiveEvent.handle(newMsg, newAnno, null == newAnno ? -1 :
        ((Long)newAnno.get(MessageAnno.ANNO_MAC_DURATION)).longValue() + getRxTxTurnaround());
    // TODO put packet id in message annotations
    if (promiscReceiveEvent.isActive())
      promiscReceiveEvent.handle(newMsg, newAnno);

    entry.setNetReceived(true);
    updateSeqEntry(newMsg.getSrc(), newMsg.getSeq());
    netEntity.receive(newMsg.getBody(), newMsg.getSrc(),
        this.netId, false, newAnno);

    /*
     * NUGGET: set backoff according to own candidate priority.
     * Otherwise forwarded packets will collide with high proability.
     */
    if (!hasBackoff()) {
      bo = msgRts.getCandidates().indexOf(localAddr) * getSlotTime();
      if (Main.ASSERT) Util.assertion(boStart == 0);
      if (Main.ASSERT) Util.assertion(bo >= 0);
      if (Main.ASSERT) Util.assertion(bo < 1 * Constants.SECOND);
    }

    return true;
  }


  /**
   * Sends an ack as answer to an rts message.
   *
   * @param msgRts
   * @param anno
   */
  private void sendAckFromRts(Mac802_11Message.Rts msgRts, MessageAnno anno) {
    // Do bit-rate selection according to algorithm.
    adjustBitrates(msgRts, anno, msgRts.getSrc(), false,
        msgFactory.getSize(MacDcfMessage.TYPE_ACK));

    // create ack
    MacDcfMessage.Ack ack = msgFactory.createAck(msgRts.getSrc(), 0, msgRts, anno);

    // Add PHY layer information to the MAC message
    // Use control rate for now; but could use higher (=data) rate in unicast scenario!
    PhyMessage phyMessage = new PhyMessage(ack, controlRate, phy);
    long delay = getRxTxTurnaround(); // already waited txSifs
    long duration = phyMessage.txDuration();

    if (sendEvent.isActive())
      sendEvent.handle(ack, anno, delay + duration + Constants.EPSILON_DELAY, controlRate, false);

    radioEntity.transmit(phyMessage, delay, duration, anno);

    // wait for EOT, check for outgoing packet
    JistAPI.sleep(delay);
    setMode(MAC_MODE_XACK);
    JistAPI.sleep(duration);
  }

  /**
   * Queries the forward buffer if another node did already forward the ip packet.
   *
   * TODO must we match exact ttls or could we use <= ttl??
   *
   * @param msg the ip message to query for.
   */
  private boolean alreadyForwarded(NetMessage.Ip msg) {
    return alreadyForwarded(msg.getSrc(), msg.getId(), msg.getTTL());
  }

  private boolean alreadyForwarded(NetAddress src, short id, byte ttl) {
    ForwardBufferEntry entry = (ForwardBufferEntry)
        forwardBuffer.get(new ForwardBufferKey(src, id));

    // if we are responsible, do not return true
    // if we've seen a younger packet with a smaller ttl or the same ttl, but
    // with another forwarder, the packet was already forwarded.
    if (null != entry
        && (entry.isTransmitted()
          || entry.isReachedDst()
          || ttl > entry.getTtl()
          || ttl == entry.getTtl()
            && !entry.getForwarder().contains(localAddr)))
      return true;

    return false;
  }

  /**
   * Informs the net about an rts/cts packet. If an appropriate packet is
   * queued in the net queue, the net will instantly pump this packet to enable
   * transmit diversity.
   *
   * @param msg
   */
  private void prepareTxDiv(MacDcfMessage msg, MessageAnno anno) {
    if (!useDataTxDiv
        || mode == MAC_MODE_SWFACK
        || mode == MAC_MODE_SWFCTS
        || mode == MAC_MODE_SWFDATA)
      return;

    /*
     * NUGGET:
     * we also use txdiv (send the packet) in the case the packet was
     * already forwarded. the sender takes responsibility and we will forget
     * everything about the packet right after the txdiv transmission.
     */

    MacAddress src;
    List candidates;
    NetAddress netSrc;
    short netId;
    short seqNo;
    boolean retry;
    byte netTtl;
    byte idxFinalDst;
    long timeToSend = JistAPI.getTime() + getSifs();

    /*
     * NUGGET
     * use only cts for txdiv prepare since we should not violate the rts/cts contract
     */

    {
      MacTxDORMessage.Cts txdCts = (MacTxDORMessage.Cts) msg;
      src         = txdCts.getDst();
      candidates  = txdCts.getCandidates();
      netSrc      = txdCts.getNetSrc();
      netId       = txdCts.getNetId();
      netTtl      = txdCts.getNetTTL();
      seqNo       = txdCts.getSeqNo();
      retry       = txdCts.isRetry();
      idxFinalDst = txdCts.getIdxFinalDst();
    }

    // check current packet if it is the one...
    // NOTE: only if incoming ttl is le,
    // TODO otherwise we hear a duplicate and have to forward our packet
    NetMessage.Ip ipMsg = (NetMessage.Ip) packet;
    if (null != ipMsg
        && netSrc.equals(ipMsg.getSrc())
        && ipMsg.getId() == netId
        && ipMsg.getTTL() >= netTtl) {

      // make both packets equal!!
      MessageAnno ipAnno = (MessageAnno) this.anno.clone();
      if(ipMsg.isFrozen()) ipMsg = ipMsg.copy();
      ipMsg.setTTL(netTtl);
      ipMsg = ipMsg.freeze();

      // clear internal buffer to get not confused
      this.packet = null;
      this.anno = null;

      // redirects to sendImmediate without any time consumption ...
      ((MacTxDORInterface)self).sendWithTxDiv(ipMsg, ipAnno, candidates,
          timeToSend, src, seqNo, retry, idxFinalDst);
      return;
    }

    // give information to net
    netEntity.instantPump(this.netId, src, candidates, seqNo, retry, timeToSend,
        netSrc, netId, netTtl, idxFinalDst);
  }


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

  /*
   * (non-Javadoc)
   * @see brn.swans.mac.MacTxDORInterface#sendWithTxDiv(jist.swans.misc.Message, jist.swans.misc.MessageAnno, java.util.List, long, jist.swans.mac.MacAddress, short, boolean, byte)
   */
  public void sendWithTxDiv(Message msg, MessageAnno anno, List candidates,
      long timeToSend, MacAddress src, short seqNo, boolean retry, byte idxFinalDst) {
    if (Main.ASSERT)
      Util.assertion(((NetMessage.Ip) msg).isFrozen());

    long delay = timeToSend - JistAPI.getTime() - getRxTxTurnaround();
    if (Main.ASSERT) {
      Util.assertion(!isTransmitting());
      Util.assertion(MAC_MODE_SIDLE == mode || MAC_MODE_DIFS == mode
          || MAC_MODE_SBO == mode || MAC_MODE_SIFS == mode
          || MAC_MODE_SNAV == mode || MAC_MODE_SWFDATA == mode);

      if (null != dataRcvd)
        log.error(this+"("+JistAPI.getTime()+"): dataRcvd="+dataRcvd.toString());
      Util.assertion(null == dataRcvd);

      // special case: we have the packet already and are candidate, too
      // in this case, we forward the packet instead of listening
      Util.assertion(MAC_MODE_SWFDATA != mode
          || (rtsRcvdAnno != null
              && ((List)rtsRcvdAnno.get(MessageAnno.ANNO_MAC_CANDIDATES)).contains(localAddr)));
    }

    if (sendImmediateEvent.isActive())
      sendImmediateEvent.handle(msg, anno, delay);

    if (delay < 0) {
      log.warn(this + "(" + JistAPI.getTime() + "): too late for sendWithTxDiv "
          + delay);
      return;
    }

    anno.put(MessageAnno.ANNO_MAC_CANDIDATES, candidates);
    anno.put(MessageAnno.ANNO_MAC_FINALDST_IDX, new Byte(idxFinalDst));
    anno.put(MessageAnno.ANNO_MAC_SOURCE, src);
    anno.put(MessageAnno.ANNO_MAC_SEQNO, new Short(seqNo));
    anno.put(MessageAnno.ANNO_MAC_RETRY, new Boolean(retry));

    // cancel current packet and inform net
    if (hasPacket())
      netEntity.reenqueuePacket(netId, this.packet, this.packetNextHop, this.anno);
    resetRetry();

    this.sendImmediate = true;
    this.packet = msg;
    this.anno = anno;
    this.packetNextHop = MacTxDOR.ADDR_ANYCAST;

    // prevents all other interruptions...
    cancelTimer();
    setMode(MAC_MODE_SNAV);

    // schedule packet at the specified time
    JistAPI.sleep(delay);
    sendDataUnicast(false);

    NetMessage.Ip ipMsg = (NetMessage.Ip) msg;
    ForwardBufferKey key = new ForwardBufferKey(ipMsg.getSrc(), ipMsg.getId());
    ForwardBufferEntry entry = (ForwardBufferEntry) forwardBuffer.get(key);
    if (null == entry) {
      entry = new ForwardBufferEntry(ipMsg.getSrc(), ipMsg.getId());
      forwardBuffer.put(key, entry);
    }
    entry.addForwarder(src, ipMsg.getTTL());

    // NUGGET: send ack directly after data packet, if we are candidate
    if (null != this.rtsRcvd) {
      NetAddress netSrc = (NetAddress) anno.get(MessageAnno.ANNO_MAC_NETSRC);
      Short netId = (Short) anno.get(MessageAnno.ANNO_MAC_NETID);

      if (src.equals(rtsRcvd.getSrc())
          && ipMsg.getSrc().equals(netSrc)
          && ipMsg.getId() == netId.shortValue()) {
        setMode(MAC_MODE_SIFS);
        JistAPI.sleep(getTxSifs());
        sendAckFromRts(this.rtsRcvd, this.rtsRcvdAnno);

        this.rtsRcvdAnno.put(MessageAnno.ANNO_MAC_FORWARDER, entry.getForwarder());

        /*
         * NOTE if we send an ack, we must care about the packet and could not
         * forget it!
         */
        netEntity.receive(msg, rtsRcvd.getSrc(), this.netId, false, this.rtsRcvdAnno);
      }
      this.rtsRcvd = null;
      this.rtsRcvdAnno = null;
    }

    decCW();
    resetRetry();
    self.cfDone(false, true);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#send(jist.swans.misc.Message, jist.swans.mac.MacAddress, jist.swans.misc.MessageAnno)
   */
  public void send(Message msg, MacAddress nextHop, MessageAnno anno) {
    // it is possible that a sendImmediate packet is faster than a 'normal
    // because of the random jitter. anyway, put it back to net and ignore.
    if (sendImmediate) {
      netEntity.reenqueuePacket(netId, msg, nextHop, anno);
      return;
    }
    
    NetMessage.Ip ipMsg = (NetMessage.Ip) msg;
    if (Main.ASSERT) {
      Util.assertion(ipMsg.isFrozen());
      Util.assertion(!hasPacket());
    }

    // scan forward buffer if we should forward the packet...
    if (alreadyForwarded(ipMsg)) {
      // gather next packet from net
      netEntity.endSend(msg, netId, anno);
      return;
    }

    List lstCandidates = (List) anno.get(MessageAnno.ANNO_MAC_CANDIDATES);
    if (Main.ASSERT)
      Util.assertion(null == lstCandidates || !lstCandidates.contains(localAddr));

    super.send(msg, nextHop, anno);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#receivePacket(jist.swans.mac.MacDcfMessage, jist.swans.misc.MessageAnno)
   */
  protected void receivePacket(MacDcfMessage msg, MessageAnno anno) {
    needEifs = false;
    
    // check if it is a txdor message
    MacTxDORMessage msgAnycast = (MacTxDORMessage)
      msg.getAdapter(classMacTxDORMessage);

    if (null != msgAnycast) {
      // check for innovation
      if (useAckCancelation
          && msg.getType() == Mac802_11Message.TYPE_RTS
          && isForMe(msgAnycast)
          && !isInnovative((MacTxDORMessage.Rts) msg, anno)) {
        cancelNonInnovativeTx((MacTxDORMessage.Rts) msg, anno);
        return;
      }

      // remember forwarded packets in forward buffer, prevent duplicate creation
      selectForwarder(msgAnycast, anno);

      // inform the net about the cts
      if (/*Mac802_11Message.TYPE_RTS == msg.getType() || */
          Mac802_11Message.TYPE_CTS == msg.getType()) {
        prepareTxDiv(msg, anno);
      }

      // convert to conventional message
      msg = convertMessage(msgAnycast, anno,
          isForMe(msgAnycast) ? localAddr : MacAddress.NULL);
    }

    // let the 802.11 mac handle the packet.
    super.receivePacket(msg, anno);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.Mac802_11#receiveData(jist.swans.mac.MacDcfMessage.Data, jist.swans.misc.MessageAnno)
   */
  protected void receiveData(MacDcfMessage.Data msg, MessageAnno anno) {
    Integer idx = (Integer) anno.get(MessageAnno.ANNO_MAC_CAND_IDX);
    if (null != idx) {
      /*
       * NUGGET: set backoff according to own candidate priority.
       * Otherwise forwarded packets will collide with high proability.
       */
      if (!hasBackoff()) {
        bo = idx.intValue() * getSlotTime();
        if (Main.ASSERT) Util.assertion(boStart == 0);
        if (Main.ASSERT) Util.assertion(bo >= 0);
        if (Main.ASSERT) Util.assertion(bo < 1 * Constants.SECOND);
      }
    }

    super.receiveData(msg, anno);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#receiveForeign(jist.swans.mac.MacDcfMessage, jist.swans.misc.MessageAnno)
   */
  protected void receiveForeign(MacDcfMessage msg, MessageAnno anno) {
    // if we missed the rts, learn from cts ...
    if (Mac802_11Message.TYPE_CTS == msg.getType()) {
      MacTxDORMessage.Cts cts = (MacTxDORMessage.Cts) msg;

      // TODO count number of passive rts/cts

      // if we could, go into the state 'waiting for data'
      // NOTE due to the return, we do not advance our nav
      if (cts.getCandidates().contains(localAddr) && !nav.waitingNav()
          && mode != MAC_MODE_SWFACK && mode != MAC_MODE_SWFCTS
          && mode != MAC_MODE_SWFDATA) {
        cancelTimer();

        // TODO correct values for rts
        rtsRcvd = msgFactory.createRts(localAddr, cts.getDst(), 0, null, null);
        rtsRcvdAnno = (MessageAnno) anno.clone();
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_CANDIDATES, cts.getCandidates());
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_FINALDST_IDX, new Byte(cts.getIdxFinalDst()));
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_CAND_IDX,
            new Integer(cts.getCandidates().indexOf(localAddr)));
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_NETSRC, cts.getNetSrc());
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_NETID, new Short(cts.getNetId()));
        rtsRcvdAnno.put(MessageAnno.ANNO_MAC_NETTTL, new Byte(cts.getNetTTL()));

        self.startTimer(cts.getDuration()
            - transmitTime(msgFactory.getSize(Mac802_11Message.TYPE_ACK), controlRate)
            - (Constants.PROPAGATION + getSifs()) + getSlotTime()
            + Constants.EPSILON_DELAY, MAC_MODE_SWFDATA);

        if (null != dataRcvd)
          log.error(this+"("+JistAPI.getTime()+"): dataRcvd="+dataRcvd.toString());

        return;
      }
    }

    // check if this is a premature ack and we are candidate and waiting for data
    if (MacDcfMessage.TYPE_ACK == msg.getType() && null != rtsRcvd) {
      MacTxDORMessage.Ack ack = (MacTxDORMessage.Ack) msg;

      NetAddress netSrc = (NetAddress)rtsRcvdAnno.get(MessageAnno.ANNO_MAC_NETSRC);
      Short netId = (Short) rtsRcvdAnno.get(MessageAnno.ANNO_MAC_NETID);
      Byte netTTL = (Byte) rtsRcvdAnno.get(MessageAnno.ANNO_MAC_NETTTL);

      if (rtsRcvd.getSrc().equals(ack.getDst())
          && netSrc.equals(ack.getNetSrc())
          && netId.shortValue() == ack.getNetId()
          && netTTL.byteValue() == ack.getNetTTL()) {
        rtsRcvd = null;
        rtsRcvdAnno = null;
        self.cfDone(false, false);
      }
    }

    // check if this is a premature ack and we could shorten our nav
    if (useAckCancelation
        && MacDcfMessage.TYPE_ACK == msg.getType()) {
      MacTxDORMessage.Ack ack = (MacTxDORMessage.Ack) msg;

      // shorten nav, e.g. if it is a premature ack we could content for
      // the medium access a bit earlier
      boolean changed = nav.shortenNav(ack.getDuration() + JistAPI.getTime(), ack.getDst());

      if (changed) {
        if (isRadioIdle() && hasPacket() || mode == MAC_MODE_SNAV) {
          startTimer(nav.waitingNav() ? nav.getNav() - JistAPI.getTime()
              : Constants.EPSILON_DELAY, MAC_MODE_SNAV);
        }
      }
    }

    if (ignoreRtsCtsNav
        && (msg.getType()==Mac802_11Message.TYPE_RTS
            ||msg.getType()==Mac802_11Message.TYPE_CTS)) {
      Util.assertion(!promisc);
      return;
    }

    super.receiveForeign(msg, anno);
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#receiveAck(jist.swans.mac.MacDcfMessage.Ack, jist.swans.misc.MessageAnno)
   */
  protected void receiveAck(MacDcfMessage.Ack msg, MessageAnno anno) {
    /*
     * NUGGET:
     * if the station sent the rts and missed the cts, and other stations
     *  used txdiv to send the data (and got the cts in advance), be prepared
     *   for an ack (without actually having sent the data).
     *
     * NOTE: increment the seq no to be sure that we do not use a number twice
     */
    if (mode != MAC_MODE_SWFACK && hasPacket()) {
      MacTxDORMessage.Ack ack = (MacTxDORMessage.Ack) msg;
      NetMessage.Ip data = (NetMessage.Ip) this.packet;

      if (data.getId() == ack.getNetId()
          &&data.getSrc().equals(ack.getNetSrc())
          &&data.getTTL() == ack.getNetTTL()) {
        setMode(MAC_MODE_SWFACK);
        // increment the seq no to be sure that we do not use a number twice
        // If the node sends an rts for the first time, but not the data packet
        // the sequence number will not get incremented, which leads to duplicates.
        incSeq();
      }
    }

    if (mode != MAC_MODE_SWFACK
        && macIgnoredAcks.isActive())
      macIgnoredAcks.handle(msg, anno);

    super.receiveAck(msg, anno);
  }


  /* (non-Javadoc)
   * @see jist.swans.mac.MacDcf#sendAck()
   */
  protected void sendAck() {
    /*
     * NUGGET: ack suppression on the last hop
     *
     * If we received a data packet and the final destination (dst) is within the
     * candidate set (and there is a high propability that the dst got the
     * packet), do not send an ack. Instead, listen for an incoming ack from
     * dst. If the ack arrives, the forwarding of the received frame is canceled
     * (forward buffer). If the ack not arrives (dst did not get the packet or
     * the ack is lost), the former sender (or one of the candidates?) will
     * initiate a (re-)transmission and we will hear the cts from dst.
     *
     * If we would send an ack here, we would not know whether dst got the data
     * packet. This would lead to a routing duplicate. Using the way described
     * above reduces the risk of a routing duplicate.
     */

    // remember candidates and own index in annotations
    List candidates = (List) dataRcvdAnno.get(MessageAnno.ANNO_MAC_CANDIDATES);
    Byte idxFinalDst = (Byte) dataRcvdAnno.get(MessageAnno.ANNO_MAC_FINALDST_IDX);
    if (Main.ASSERT)
      Util.assertion(idxFinalDst.intValue() < candidates.size());
    MacAddress finalDst = (idxFinalDst.intValue() < 0 ? null :
      (MacAddress)candidates.get(idxFinalDst.intValue()));

    if (null != finalDst && !finalDst.equals(localAddr)) {
      dataRcvd = null;
      dataRcvdAnno = null;

      self.cfDone(false, false);
    } else {
      super.sendAck();
    }
  }

  /*
   * (non-Javadoc)
   * @see jist.swans.mac.MacDcf#cfDone(boolean, boolean)
   */
  public void cfDone(boolean backoff, boolean delPacket) {
    if (delPacket && this.packet != null) {
      this.sendImmediate = false;
      MacAddress src = (MacAddress) anno.get(MessageAnno.ANNO_MAC_SOURCE);
      if (!isBroadcast() && (null == src || localAddr.equals(src))) {
        NetMessage.Ip ipMsg = (NetMessage.Ip) packet;
        ForwardBufferKey key = new ForwardBufferKey(ipMsg.getSrc(), ipMsg.getId());
        ForwardBufferEntry entry = (ForwardBufferEntry) forwardBuffer.get(key);
        if (null == entry) {
          entry = new ForwardBufferEntry(ipMsg.getSrc(), ipMsg.getId());
          forwardBuffer.put(key, entry);
        }
        entry.addForwarder(localAddr, ipMsg.getTTL());
        entry.setTransmitted(true);
      }
    }
    super.cfDone(backoff, delPacket);
  }


  public void cleanUpFwdBuffer() {
    Iterator iter = forwardBuffer.values().iterator();
    
    long timeout = JistAPI.getTime() - FWDBUFFER_STALE_TIMEOUT;
    while (null != iter && iter.hasNext()) {
      ForwardBufferEntry entry = (ForwardBufferEntry) iter.next();
      if (entry.getLastUpdate() < timeout )
        iter.remove();
    }
    
    JistAPI.sleep(FWDBUFFER_STALE_TIMEOUT);
    ((MacTxDORInterface)self).cleanUpFwdBuffer();
  }

}
