# HG changeset patch
# User Mirko Banchi <mk.banchi@gmail.com>
# Date 1265225691 -3600
# Node ID e9918be47f783f2f00dae0d45756a168833eb676
# Parent  10fbe045901e3daaa518d3eb08e5c8765d5c2ea0
MacLow now buffers QoS MPDUs under Block Ack

diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/mac-low.cc
--- a/src/devices/wifi/mac-low.cc	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/mac-low.cc	Wed Feb 03 20:34:51 2010 +0100
@@ -1,6 +1,7 @@
 /* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
 /*
  * Copyright (c) 2005,2006 INRIA
+ * Copyright (c) 2009 MIRKO BANCHI
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as 
@@ -16,6 +17,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  *
  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ * Author: Mirko Banchi <mk.banchi@gmail.com>
  */
 
 #include "ns3/assert.h"
@@ -28,6 +30,7 @@
 #include "mac-low.h"
 #include "wifi-phy.h"
 #include "wifi-mac-trailer.h"
+#include "qos-utils.h"
 
 NS_LOG_COMPONENT_DEFINE ("MacLow");
 
@@ -1298,4 +1301,138 @@
   ForwardDown (packet, &ack, ackTxMode);
 }
 
+bool
+MacLow::StoreMpduIfNeeded (Ptr<Packet> packet, WifiMacHeader hdr)
+{
+  AgreementsI it = m_bAckAgreements.find (std::make_pair (hdr.GetAddr2 (), hdr.GetQosTid ()));
+  if (it != m_bAckAgreements.end ())
+   {
+     WifiMacTrailer fcs;
+     packet->RemoveTrailer (fcs);
+     BufferedPacket bufferedPacket (packet, hdr);
+
+     uint16_t endSequence = ((*it).second.first.GetStartingSequence () + 2047) % 4096;
+     uint16_t mappedSeqControl = QosUtilsMapSeqControlToUniqueInteger (hdr.GetSequenceControl () ,endSequence);
+
+     BufferedPacketI i = (*it).second.second.begin ();
+     for (; i != (*it).second.second.end () &&
+            QosUtilsMapSeqControlToUniqueInteger ((*i).second.GetSequenceControl (), endSequence) < mappedSeqControl; i++);
+     (*it).second.second.insert (i, bufferedPacket);
+     return true;
+   }
+  return false;
+}
+
+void
+MacLow::CreateBlockAckAgreement (const MgtAddBaResponseHeader *respHdr, Mac48Address originator,
+                                 uint16_t startingSeq)
+{
+  BlockAckAgreement agreement (originator, respHdr->GetTid ());
+  if (respHdr->IsImmediateBlockAck ())
+    {
+      agreement.SetImmediateBlockAck ();
+    }
+  else
+    {
+      agreement.SetDelayedBlockAck ();
+    }
+  agreement.SetAmsduSupport (respHdr->IsAmsduSupported ());
+  agreement.SetBufferSize (respHdr->GetBufferSize ());
+  agreement.SetTimeout (respHdr->GetTimeout ());
+  agreement.SetStartingSequence (startingSeq);
+  
+  std::list<BufferedPacket> buffer (0);
+  AgreementKey key (originator, respHdr->GetTid ());
+  AgreementValue value (agreement, buffer);
+  m_bAckAgreements.insert (std::make_pair (key, value));
+}
+
+void
+MacLow::DestroyBlockAckAgreement (Mac48Address originator, uint8_t tid)
+{
+  AgreementsI it = m_bAckAgreements.find (std::make_pair (originator, tid));
+  if (it != m_bAckAgreements.end ())
+    {
+      RxCompleteBufferedPacketsWithSmallerSequence (it->second.first.GetStartingSequence (), originator, tid);
+      RxCompleteBufferedPackets (originator, tid);
+      m_bAckAgreements.erase (it);
+    }
+}
+
+void
+MacLow::RxCompleteBufferedPacketsWithSmallerSequence (uint16_t seq, Mac48Address originator, uint8_t tid)
+{
+  AgreementsI it = m_bAckAgreements.find (std::make_pair (originator, tid));
+  if (it != m_bAckAgreements.end ())
+    {
+      BufferedPacketI i = (*it).second.second.begin ();
+      uint16_t endSequence = ((*it).second.first.GetStartingSequence () + 2047) % 4096;
+      uint16_t mappedStart = QosUtilsMapSeqControlToUniqueInteger (seq, endSequence);
+      uint16_t guard = (*it).second.first.GetStartingSequence ();
+      BufferedPacketI last = (*it).second.second.begin ();
+
+      for (; i != (*it).second.second.end () &&
+             QosUtilsMapSeqControlToUniqueInteger ((*i).second.GetSequenceNumber (), endSequence) < mappedStart;)
+        {
+          while (i != (*it).second.second.end () && guard == (*i).second.GetSequenceControl ())
+            {
+              if (!(*i).second.IsMoreFragments ())
+                {
+                  while (last != i)
+                    {
+                      m_rxCallback ((*last).first, &(*last).second);
+                      last++;
+                    }
+                  m_rxCallback ((*last).first, &(*last).second);
+                  last++;
+                }
+              guard = (*i).second.IsMoreFragments () ? (guard + 1) : ((guard + 16) & 0xfff0);
+            }
+          /* go to next packet */
+          while (i != (*it).second.second.end () && ((guard >> 4) & 0x0fff) == (*i).second.GetSequenceNumber ())
+            {
+              i++;
+            }
+          if (i != (*it).second.second.end ())
+            {
+              guard = (*i).second.GetSequenceControl () & 0xfff0;
+              last = i;
+            }
+        }
+      (*it).second.second.erase ((*it).second.second.begin (), i);
+    }
+}
+
+void
+MacLow::RxCompleteBufferedPackets (Mac48Address originator, uint8_t tid)
+{
+  AgreementsI it = m_bAckAgreements.find (std::make_pair (originator, tid));
+  if (it != m_bAckAgreements.end ())
+    {
+      uint16_t startingSeqCtrl = ((*it).second.first.GetStartingSequence ()<<4) & 0xfff0;
+      uint16_t guard = startingSeqCtrl;
+
+      BufferedPacketI lastComplete = (*it).second.second.begin ();
+      BufferedPacketI i = (*it).second.second.begin ();
+      for (;i != (*it).second.second.end() && guard == (*i).second.GetSequenceControl (); i++)
+        {
+          if (!(*i).second.IsMoreFragments ())
+            {
+              while (lastComplete != i)
+                {
+                  m_rxCallback ((*lastComplete).first, &(*lastComplete).second);
+                  lastComplete++;
+                }
+               m_rxCallback ((*lastComplete).first, &(*lastComplete).second);
+               lastComplete++;
+            }
+          guard = (*i).second.IsMoreFragments () ? (guard + 1) : ((guard + 16) & 0xfff0);
+        }
+      (*it).second.first.SetStartingSequence ((guard>>4)&0x0fff);
+      /* All packets already forwarded to WifiMac must be removed from buffer: 
+      [begin (), lastComplete) */
+      (*it).second.second.erase ((*it).second.second.begin (), lastComplete);
+    }
+}
+
 } // namespace ns3
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/mac-low.h
--- a/src/devices/wifi/mac-low.h	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/mac-low.h	Wed Feb 03 20:34:51 2010 +0100
@@ -1,6 +1,7 @@
 /* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
 /*
  * Copyright (c) 2005, 2006 INRIA
+ * Copyright (c) 2009 MIRKO BANCHI
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as 
@@ -16,6 +17,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  *
  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ * Author: Mirko Banchi <mk.banchi@gmail.com>
  */
 #ifndef MAC_LOW_H
 #define MAC_LOW_H
@@ -23,12 +25,15 @@
 #include <vector>
 #include <stdint.h>
 #include <ostream>
+#include <map>
 
 #include "wifi-mac-header.h"
 #include "wifi-mode.h"
 #include "wifi-preamble.h"
 #include "wifi-remote-station-manager.h"
 #include "ctrl-headers.h"
+#include "mgt-headers.h"
+#include "block-ack-agreement.h"
 #include "ns3/mac48-address.h"
 #include "ns3/callback.h"
 #include "ns3/event-id.h"
@@ -411,6 +416,27 @@
    * occurs, pending MAC transmissions (RTS, CTS, DATA and ACK) are cancelled.
    */
   void NotifySwitchingStartNow (Time duration); 
+  /**
+   * \param respHdr Add block ack response from originator (action frame).
+   * \param originator Address of peer station involved in block ack mechanism.
+   * \param startingSeq Sequence number of the first MPDU of all packets for which block ack was negotiated.
+   * 
+   * This function is typically invoked only by ns3::QapWifiMac and ns3::QstaWifiMac.
+   * If we are transmitting an Add block ack response, MacLow must allocate buffers to collect
+   * all correctly received packets belonging to category for which block ack was negotiated.
+   * It's needed in order to send a Block ack after corresponding originator's Block ack request.
+   */
+  void CreateBlockAckAgreement (const MgtAddBaResponseHeader *respHdr, Mac48Address originator,
+                                uint16_t startingSeq);
+  /**
+   * \param originator Address of peer partecipating in Block Ack mechanism.
+   * \param tid TID for which Block Ack was created.
+   *
+   * Checks if exists an established block ack agreement with <i>originator</i>
+   * for tid <i>tid</i>. If the agreement exists, tears down it. This function is typically
+   * invoked when a DELBA frame is received from <i>originator</i>.
+   */
+  void DestroyBlockAckAgreement (Mac48Address originator, uint8_t tid);
 private:
   void CancelAllEvents (void);
   uint32_t GetAckSize (void) const;
@@ -456,6 +482,35 @@
   void SendCurrentTxPacket (void);
   void StartDataTxTimers (void);
   virtual void DoDispose (void);
+  /**
+   * \param originator Address of peer partecipating in Block Ack mechanism.
+   * \param tid TID for which Block Ack was created.
+   * \param seq Starting sequence
+   *
+   * This function forward up all completed "old" packets with sequence number
+   * smaller than <i>seq</i>. All comparison are performed circularly mod 4096.
+   */
+  void RxCompleteBufferedPacketsWithSmallerSequence (uint16_t seq, Mac48Address originator, uint8_t tid);
+  /**
+   * \param originator Address of peer partecipating in Block Ack mechanism.
+   * \param tid TID for which Block Ack was created.
+   *
+   * This method is typically invoked when a MPDU with ack policy
+   * subfield set to Normal Ack is received and a block ack agreement
+   * for that packet exists.
+   * This happens when the originator of block ack has only few MPDUs to send.
+   * All completed MSDUs starting with starting sequence number of block ack
+   * agreement are forward up to WifiMac until there is an incomplete MSDU.
+   * See section 9.10.4 in IEEE802.11 standard for more details.
+   */
+  void RxCompleteBufferedPackets (Mac48Address originator, uint8_t tid);
+  /* 
+   * This method checks if exists a valid established block ack agreement. 
+   * If there is, store the packet without pass it up to WifiMac. The packet is buffered
+   * in order of increasing sequence control field. All comparison are performed
+   * circularly modulo 2^12.
+   */
+  bool StoreMpduIfNeeded (Ptr<Packet> packet, WifiMacHeader hdr);
 
   void SetupPhyMacLowListener (Ptr<WifiPhy> phy); 
 
@@ -494,6 +549,20 @@
 
   // Listerner needed to monitor when a channel switching occurs. 
   class PhyMacLowListener *m_phyMacLowListener; 
+
+  /*
+   * BlockAck data structures.
+   */
+  typedef std::pair<Ptr<Packet>, WifiMacHeader> BufferedPacket;
+  typedef std::list<BufferedPacket>::iterator BufferedPacketI;
+
+  typedef std::pair<Mac48Address, uint8_t> AgreementKey;
+  typedef std::pair<BlockAckAgreement, std::list<BufferedPacket> > AgreementValue;
+
+  typedef std::map<AgreementKey, AgreementValue> Agreements;
+  typedef std::map<AgreementKey, AgreementValue>::iterator AgreementsI;
+
+  Agreements m_bAckAgreements;
 };
 
 } // namespace ns3
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/qadhoc-wifi-mac.cc
--- a/src/devices/wifi/qadhoc-wifi-mac.cc	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/qadhoc-wifi-mac.cc	Wed Feb 03 20:34:51 2010 +0100
@@ -528,7 +528,7 @@
   packet->AddHeader (actionHdr);
   
   /* ns3::MacLow have to buffer all correctly received packet for this block ack session */
-  //m_low->CreateIngoingAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
+  m_low->CreateBlockAckAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
 
   //Better a management queue? 
   m_queues[QosUtilsMapTidToAc (reqHdr->GetTid ())]->PushFront (packet, hdr);
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/qap-wifi-mac.cc
--- a/src/devices/wifi/qap-wifi-mac.cc	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/qap-wifi-mac.cc	Wed Feb 03 20:34:51 2010 +0100
@@ -881,7 +881,7 @@
   packet->AddHeader (actionHdr);
   
   /* ns3::MacLow have to buffer all correctly received packet for this block ack session */
-  //m_low->CreateIngoingAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
+  m_low->CreateBlockAckAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
 
   //Better a management queue? 
   m_queues[QosUtilsMapTidToAc (reqHdr->GetTid ())]->PushFront (packet, hdr);
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/qos-utils.cc
--- a/src/devices/wifi/qos-utils.cc	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/qos-utils.cc	Wed Feb 03 20:34:51 2010 +0100
@@ -16,6 +16,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  *
  * Author: Mirko Banchi <mk.banchi@gmail.com>
+ * Author: Cecchi Niccolò <insa@igeek.it>
  */
 #include "qos-utils.h"
 #include "qos-tag.h"
@@ -69,4 +70,16 @@
   return tid;
 }
 
+uint32_t
+QosUtilsMapSeqControlToUniqueInteger (uint16_t seqControl, uint16_t endSequence)
+{
+  uint32_t integer = 0;
+  uint16_t numberSeq = (seqControl>>4) & 0x0fff;
+  integer = (4096 - (endSequence + 1) + numberSeq) % 4096;
+  integer *= 16;
+  integer += (seqControl & 0x000f);
+  return integer; 
+}
+
+
 } //namespace ns3
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/qos-utils.h
--- a/src/devices/wifi/qos-utils.h	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/qos-utils.h	Wed Feb 03 20:34:51 2010 +0100
@@ -45,6 +45,13 @@
  */
 uint8_t QosUtilsGetTidForPacket (Ptr<const Packet> packet);
 
+/*
+ * Next function is useful to correctly sort buffered packets under block ack.
+ * When an BAR is received from originator station, completed "old"
+ * (see section 9.10.3 in IEEE802.11e) packets must be forwarded up before "new" packets.
+ */
+uint32_t QosUtilsMapSeqControlToUniqueInteger (uint16_t seqControl, uint16_t endSequence);
+
 } //namespace ns3
 
 #endif /* QOS_UTILS_H */
diff -r 10fbe045901e -r e9918be47f78 src/devices/wifi/qsta-wifi-mac.cc
--- a/src/devices/wifi/qsta-wifi-mac.cc	Wed Feb 03 20:34:50 2010 +0100
+++ b/src/devices/wifi/qsta-wifi-mac.cc	Wed Feb 03 20:34:51 2010 +0100
@@ -857,7 +857,7 @@
   packet->AddHeader (actionHdr);
   
   /* ns3::MacLow have to buffer all correctly received packet for this block ack session */
-  //m_low->CreateIngoingAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
+  m_low->CreateBlockAckAgreement (&respHdr, originator, reqHdr->GetStartingSequence ());
 
   //Better a management queue? 
   m_queues[QosUtilsMapTidToAc (reqHdr->GetTid ())]->PushFront (packet, hdr);