# HG changeset patch
# User Kirill V. Andreev <kirillano@yandex.ru>
# Date 1244461050 -7200
# Node ID b2654e0f071d125939f46b0cf40f6ca782867c5e
# Parent  3135a5c2435866f96846b6b413e8efd5918fd765
bug 556: DcfManager does not handle AckTimeout properly when there are multiple queues

diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/dcf-manager-test.cc
--- a/src/devices/wifi/dcf-manager-test.cc	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/dcf-manager-test.cc	Mon Jun 08 13:37:30 2009 +0200
@@ -68,7 +68,7 @@
 
 
 private:
-  void StartTest (uint64_t slotTime, uint64_t sifs, uint64_t eifsNoDifsNoSifs);
+  void StartTest (uint64_t slotTime, uint64_t sifs, uint64_t eifsNoDifsNoSifs, uint32_t ackTimeoutValue = 20);
   void AddDcfState (uint32_t aifsn);
   void EndTest (void);
   void ExpectInternalCollision (uint64_t time, uint32_t from, uint32_t nSlots);
@@ -77,14 +77,21 @@
   void AddRxErrorEvt (uint64_t at, uint64_t duration);
   void AddNavReset (uint64_t at, uint64_t duration);
   void AddNavStart (uint64_t at, uint64_t duration);
+  void AddAckTimeoutReset (uint64_t at);
   void AddAccessRequest (uint64_t at, uint64_t txTime, 
                          uint64_t expectedGrantTime, uint32_t from);
+  void AddAccessRequestWithAckTimeout (uint64_t at, uint64_t txTime, 
+                                  uint64_t expectedGrantTime, uint32_t from);
+  ///\param ackDelay is delay of the ack after txEnd
+  void AddAccessRequestWithSuccessfullAck (uint64_t at, uint64_t txTime, 
+                                  uint64_t expectedGrantTime, uint32_t ackDelay, uint32_t from);
   void DoAccessRequest (uint64_t txTime, uint64_t expectedGrantTime, DcfStateTest *state);
   
   typedef std::vector<DcfStateTest *> DcfStates;
 
   DcfManager *m_dcfManager;
   DcfStates m_dcfStates;
+  uint32_t m_ackTimeoutValue;
   bool m_result;
 };
 
@@ -130,6 +137,7 @@
   state->m_expectedGrants.pop_front ();
   NS_TEST_ASSERT_EQUAL (Simulator::Now (), MicroSeconds (expected.second));
   m_dcfManager->NotifyTxStartNow (MicroSeconds (expected.first));
+  m_dcfManager->NotifyAckTimeoutStartNow (MicroSeconds (m_ackTimeoutValue + expected.first));
   if (!result)
     {
       m_result = result;
@@ -187,12 +195,13 @@
 }
 
 void
-DcfManagerTest::StartTest (uint64_t slotTime, uint64_t sifs, uint64_t eifsNoDifsNoSifs)
+DcfManagerTest::StartTest (uint64_t slotTime, uint64_t sifs, uint64_t eifsNoDifsNoSifs, uint32_t ackTimeoutValue)
 {
   m_dcfManager = new DcfManager ();
   m_dcfManager->SetSlot (MicroSeconds (slotTime));
   m_dcfManager->SetSifs (MicroSeconds (sifs));
   m_dcfManager->SetEifsNoDifs (MicroSeconds (eifsNoDifsNoSifs+sifs));
+  m_ackTimeoutValue = ackTimeoutValue;
 }
 
 void
@@ -260,14 +269,35 @@
                        MicroSeconds (duration));
 }
 void 
+DcfManagerTest::AddAckTimeoutReset (uint64_t at)
+{
+  Simulator::Schedule (MicroSeconds (at) - Now (), 
+                       &DcfManager::NotifyAckTimeoutResetNow, m_dcfManager);
+}
+void 
 DcfManagerTest::AddAccessRequest (uint64_t at, uint64_t txTime, 
                                   uint64_t expectedGrantTime, uint32_t from)
 {
+  AddAccessRequestWithSuccessfullAck (at, txTime, expectedGrantTime, 0, from);
+}
+void 
+DcfManagerTest::AddAccessRequestWithAckTimeout (uint64_t at, uint64_t txTime, 
+                                  uint64_t expectedGrantTime, uint32_t from)
+{
   Simulator::Schedule (MicroSeconds (at) - Now (), 
                        &DcfManagerTest::DoAccessRequest, this,
                        txTime, expectedGrantTime, m_dcfStates[from]);
 }
-
+void 
+DcfManagerTest::AddAccessRequestWithSuccessfullAck (uint64_t at, uint64_t txTime, 
+                                  uint64_t expectedGrantTime, uint32_t ackDelay, uint32_t from)
+{
+  NS_ASSERT(ackDelay < m_ackTimeoutValue);
+  Simulator::Schedule (MicroSeconds (at) - Now (), 
+                       &DcfManagerTest::DoAccessRequest, this,
+                       txTime, expectedGrantTime, m_dcfStates[from]);
+  AddAckTimeoutReset (expectedGrantTime + txTime + ackDelay);
+}
 void
 DcfManagerTest::DoAccessRequest (uint64_t txTime, uint64_t expectedGrantTime, DcfStateTest *state)
 {
@@ -301,7 +331,7 @@
   //   |    rx     | sifs | aifsn | bslot0  | bslot1  |   | rx   | sifs  |  aifsn | bslot2 | bslot3 | tx  |
   //        |
   //       30 request access. backoff slots: 4
-  StartTest (4, 6 , 10);
+  StartTest (4, 6, 10);
   AddDcfState (1);
   AddRxOkEvt (20, 40);
   AddRxOkEvt (80, 20);
@@ -388,7 +418,58 @@
   ExpectCollision (40, 0, 1); // backoff: 0 slot
   ExpectInternalCollision (78, 1, 1); // backoff: 1 slot
   EndTest ();
+  
+  // Test of AckTimeout handling: First queue requests access and ack procedure fails,
+  // inside the ack timeout second queue with higher priority requests access.
+  //
+  //            20           40      50     60  66      76
+  // DCF0 - low  |     tx     | ack timeout |sifs|       |
+  // DCF1 - high |                    |     |sifs|  tx   |
+  //                                  ^ request access
+  StartTest (4, 6, 10);
+  AddDcfState (2); // high priority DCF
+  AddDcfState (0); // low priority DCF
+  AddAccessRequestWithAckTimeout (20, 20, 20, 0);
+  AddAccessRequest (50, 10, 66, 1);
+  EndTest ();
 
+  // Test of AckTimeout handling: 
+  //
+  // First queue requests access and ack is 2 us delayed (got ack interval at the picture),
+  // inside this interval second queue with higher priority requests access.
+  //
+  //            20           40  41   42    48      58
+  // DCF0 - low  |     tx     |got ack |sifs|       |
+  // DCF1 - high |                |    |sifs|  tx   |
+  //                              ^ request access
+  StartTest (4, 6, 10);
+  AddDcfState (2); // high priority DCF
+  AddDcfState (0); // low priority DCF
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0);
+  AddAccessRequest (41, 10, 48, 1);
+  EndTest ();
+
+  //Repeat the same but with one queue:
+  //            20           40  41   42    48      58
+  // DCF0 - low  |     tx     |got ack |sifs|       |
+  //                              ^ request access
+  StartTest (4, 6, 10);
+  AddDcfState (2);
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0);
+  AddAccessRequest (41, 10, 56, 0);
+  EndTest ();
+
+  //Repeat the same when ack was delayed:
+  //and request the next access before previous tx end:
+  //            20       39  40       42              64      74
+  // DCF0 - low  |     tx     |got ack |sifs + 4 * slot|       |
+  //                      ^ request access
+  StartTest (4, 6, 10);
+  AddDcfState (2);
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0);
+  AddAccessRequest (39, 10, 64, 0);
+  ExpectCollision (39, 2, 0); // backoff: 2 slot
+  EndTest ();
 
   //
   // test simple NAV count. This scenario modelizes a simple DATA+ACK handshake
@@ -405,7 +486,6 @@
   ExpectCollision (30, 2, 0); // backoff: 2 slot
   EndTest ();
 
-
   //
   // test more complex NAV handling by a CF-poll. This scenario modelizes a 
   // simple DATA+ACK handshake interrupted by a CF-poll which resets the
diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/dcf-manager.cc
--- a/src/devices/wifi/dcf-manager.cc	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/dcf-manager.cc	Mon Jun 08 13:37:30 2009 +0200
@@ -160,17 +160,29 @@
  *         Listener for Nav events. Forwards to DcfManager
  ***************************************************************/
 
-class LowNavListener : public ns3::MacLowNavListener {
+class LowDcfListener : public ns3::MacLowDcfListener {
 public:
-  LowNavListener (ns3::DcfManager *dcf)
+  LowDcfListener (ns3::DcfManager *dcf)
     : m_dcf (dcf) {}
-  virtual ~LowNavListener () {}
+  virtual ~LowDcfListener () {}
   virtual void NavStart (Time duration) {
     m_dcf->NotifyNavStartNow (duration);
   }
   virtual void NavReset (Time duration) {
     m_dcf->NotifyNavResetNow (duration);
   }
+  virtual void AckTimeoutStart (Time duration) {
+    m_dcf->NotifyAckTimeoutStartNow (duration);
+  }
+  virtual void AckTimeoutReset () {
+    m_dcf->NotifyAckTimeoutResetNow ();
+  }
+  virtual void CtsTimeoutStart (Time duration) {
+    m_dcf->NotifyCtsTimeoutStartNow (duration);
+  }
+  virtual void CtsTimeoutReset () {
+    m_dcf->NotifyCtsTimeoutResetNow ();
+  }
 private:
   ns3::DcfManager *m_dcf;
 };
@@ -208,7 +220,9 @@
  ****************************************************************/
 
 DcfManager::DcfManager ()
-  : m_lastNavStart (MicroSeconds (0)),
+  : m_lastAckTimeoutEnd (MicroSeconds (0)),
+    m_lastCtsTimeoutEnd (MicroSeconds (0)),
+    m_lastNavStart (MicroSeconds (0)),
     m_lastNavDuration (MicroSeconds (0)),
     m_lastRxStart (MicroSeconds (0)),
     m_lastRxDuration (MicroSeconds (0)),
@@ -242,8 +256,8 @@
 void 
 DcfManager::SetupLowListener (Ptr<MacLow> low)
 {
-  m_lowListener = new LowNavListener (this);
-  low->RegisterNavListener (m_lowListener);
+  m_lowListener = new LowDcfListener (this);
+  low->RegisterDcfListener (m_lowListener);
 }
 
 void 
@@ -294,6 +308,16 @@
   Time retval = Max (e, f);
   return retval;
 }
+Time
+DcfManager::MostRecent (Time a, Time b, Time c, Time d, Time e, Time f) const
+{
+  Time g = Max (a, b);
+  Time h = Max (c, d);
+  Time i = Max (e, f);
+  Time k = Max (g, h);
+  Time retval = Max (k, i);
+  return retval;
+}
 
 bool 
 DcfManager::IsBusy (void) const
@@ -351,7 +375,7 @@
     {
       DcfState *state = *i;
       if (state->IsAccessRequested () && 
-          GetBackoffEndFor (state) <= Simulator::Now ())
+          GetBackoffEndFor (state) <= Simulator::Now () )
         {
           /**
            * This is the first dcf we find with an expired backoff and which
@@ -428,10 +452,15 @@
   Time busyAccessStart = m_lastBusyStart + m_lastBusyDuration + m_sifs;
   Time txAccessStart = m_lastTxStart + m_lastTxDuration + m_sifs;
   Time navAccessStart = m_lastNavStart + m_lastNavDuration + m_sifs;
+  Time ackTimeoutAccessStart = m_lastAckTimeoutEnd + m_sifs;
+  Time ctsTimeoutAccessStart = m_lastCtsTimeoutEnd + m_sifs;
   Time accessGrantedStart = MostRecent (rxAccessStart, 
                                         busyAccessStart,
                                         txAccessStart, 
-                                        navAccessStart);
+                                        navAccessStart,
+                                        ackTimeoutAccessStart,
+                                        ctsTimeoutAccessStart
+                                        );
   NS_LOG_INFO ("access grant start=" << accessGrantedStart <<
                ", rx access start=" << rxAccessStart <<
                ", busy access start=" << busyAccessStart <<
@@ -586,5 +615,27 @@
       m_lastNavDuration = duration;
     }
 }
-
+void
+DcfManager::NotifyAckTimeoutStartNow (Time duration)
+{
+  NS_ASSERT(m_lastAckTimeoutEnd < Simulator::Now ());
+  m_lastAckTimeoutEnd = Simulator::Now () + duration;
+}
+void
+DcfManager::NotifyAckTimeoutResetNow ()
+{
+  m_lastAckTimeoutEnd = Simulator::Now ();
+  DoRestartAccessTimeoutIfNeeded ();
+}
+void
+DcfManager::NotifyCtsTimeoutStartNow (Time duration)
+{
+  m_lastCtsTimeoutEnd = Simulator::Now () + duration;
+}
+void
+DcfManager::NotifyCtsTimeoutResetNow ()
+{
+  m_lastCtsTimeoutEnd = Simulator::Now ();
+  DoRestartAccessTimeoutIfNeeded ();
+}
 } // namespace ns3
diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/dcf-manager.h
--- a/src/devices/wifi/dcf-manager.h	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/dcf-manager.h	Mon Jun 08 13:37:30 2009 +0200
@@ -238,12 +238,16 @@
    * Called at end of rx
    */
   void NotifyNavStartNow (Time duration);
-
+  void NotifyAckTimeoutStartNow (Time duration);
+  void NotifyAckTimeoutResetNow ();
+  void NotifyCtsTimeoutStartNow (Time duration);
+  void NotifyCtsTimeoutResetNow ();
 private:
   void UpdateBackoff (void);
   Time MostRecent (Time a, Time b) const;
   Time MostRecent (Time a, Time b, Time c) const;
   Time MostRecent (Time a, Time b, Time c, Time d) const;
+  Time MostRecent (Time a, Time b, Time c, Time d, Time e, Time f) const;
   /**
    * Access will never be granted to the medium _before_
    * the time returned by this method.
@@ -262,6 +266,8 @@
   typedef std::vector<DcfState *> States;
 
   States m_states;
+  Time m_lastAckTimeoutEnd;
+  Time m_lastCtsTimeoutEnd;
   Time m_lastNavStart;
   Time m_lastNavDuration;
   Time m_lastRxStart;
@@ -279,7 +285,7 @@
   Time m_slotTime;
   Time m_sifs;
   class PhyListener *m_phyListener;
-  class LowNavListener *m_lowListener;
+  class LowDcfListener *m_lowListener;
 };
 
 } // namespace ns3
diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/mac-low.cc
--- a/src/devices/wifi/mac-low.cc	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/mac-low.cc	Mon Jun 08 13:37:30 2009 +0200
@@ -110,9 +110,9 @@
 {}
 MacLowTransmissionListener::~MacLowTransmissionListener ()
 {}
-MacLowNavListener::MacLowNavListener ()
+MacLowDcfListener::MacLowDcfListener ()
 {}
-MacLowNavListener::~MacLowNavListener ()
+MacLowDcfListener::~MacLowDcfListener ()
 {}
 
 MacLowTransmissionParameters::MacLowTransmissionParameters ()
@@ -423,9 +423,9 @@
   m_rxCallback = callback;
 }
 void 
-MacLow::RegisterNavListener (MacLowNavListener *listener)
+MacLow::RegisterDcfListener (MacLowDcfListener *listener)
 {
-  m_navListeners.push_back (listener);
+  m_dcfListeners.push_back (listener);
 }
 
 
@@ -543,6 +543,7 @@
       station->ReportRtsOk (rxSnr, txMode, tag.Get ());
       
       m_ctsTimeoutEvent.Cancel ();
+      NotifyCtsTimeoutResetNow ();
       m_listener->GotCts (rxSnr, txMode);
       NS_ASSERT (m_sendDataEvent.IsExpired ());
       m_sendDataEvent = Simulator::Schedule (GetSifs (), 
@@ -569,12 +570,14 @@
           m_normalAckTimeoutEvent.IsRunning ()) 
         {
           m_normalAckTimeoutEvent.Cancel ();
+          NotifyAckTimeoutResetNow ();
           gotAck = true;
         }
       if (m_txParams.MustWaitFastAck () &&
           m_fastAckTimeoutEvent.IsRunning ()) 
         {
           m_fastAckTimeoutEvent.Cancel ();
+          NotifyAckTimeoutResetNow ();
           gotAck = true;
         }
       if (gotAck) 
@@ -796,7 +799,7 @@
 void
 MacLow::DoNavResetNow (Time duration)
 {
-  for (NavListenersCI i = m_navListeners.begin (); i != m_navListeners.end (); i++) 
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
     {
       (*i)->NavReset (duration);
     }
@@ -806,7 +809,7 @@
 bool
 MacLow::DoNavStartNow (Time duration)
 {
-  for (NavListenersCI i = m_navListeners.begin (); i != m_navListeners.end (); i++) 
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
     {
       (*i)->NavStart (duration);
     }
@@ -820,6 +823,38 @@
     }
   return false;
 }
+void
+MacLow::NotifyAckTimeoutStartNow (Time duration)
+{
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
+    {
+      (*i)->AckTimeoutStart (duration);
+    }
+}
+void
+MacLow::NotifyAckTimeoutResetNow ()
+{
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
+    {
+      (*i)->AckTimeoutReset ();
+    }
+}
+void
+MacLow::NotifyCtsTimeoutStartNow (Time duration)
+{
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
+    {
+      (*i)->CtsTimeoutStart (duration);
+    }
+}
+void
+MacLow::NotifyCtsTimeoutResetNow ()
+{
+  for (DcfListenersCI i = m_dcfListeners.begin (); i != m_dcfListeners.end (); i++) 
+    {
+      (*i)->CtsTimeoutReset ();
+    }
+}
 
 void
 MacLow::ForwardDown (Ptr<const Packet> packet, WifiMacHeader const* hdr, 
@@ -945,6 +980,7 @@
   Time timerDelay = txDuration + GetCtsTimeout ();
 
   NS_ASSERT (m_ctsTimeoutEvent.IsExpired ());
+  NotifyCtsTimeoutStartNow (timerDelay);
   m_ctsTimeoutEvent = Simulator::Schedule (timerDelay, &MacLow::CtsTimeout, this);
 
   Ptr<Packet> packet = Create<Packet> ();
@@ -964,18 +1000,21 @@
     {
       Time timerDelay = txDuration + GetAckTimeout ();
       NS_ASSERT (m_normalAckTimeoutEvent.IsExpired ());
+      NotifyAckTimeoutStartNow (timerDelay);
       m_normalAckTimeoutEvent = Simulator::Schedule (timerDelay, &MacLow::NormalAckTimeout, this);
     } 
   else if (m_txParams.MustWaitFastAck ()) 
     {
       Time timerDelay = txDuration + GetPifs ();
       NS_ASSERT (m_fastAckTimeoutEvent.IsExpired ());
+      NotifyAckTimeoutStartNow (timerDelay);
       m_fastAckTimeoutEvent = Simulator::Schedule (timerDelay, &MacLow::FastAckTimeout, this);
     } 
   else if (m_txParams.MustWaitSuperFastAck ()) 
     {
       Time timerDelay = txDuration + GetPifs ();
       NS_ASSERT (m_superFastAckTimeoutEvent.IsExpired ());
+      NotifyAckTimeoutStartNow (timerDelay);
       m_superFastAckTimeoutEvent = Simulator::Schedule (timerDelay, 
                                                         &MacLow::SuperFastAckTimeout, this);
     } 
diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/mac-low.h
--- a/src/devices/wifi/mac-low.h	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/mac-low.h	Mon Jun 08 13:37:30 2009 +0200
@@ -100,10 +100,10 @@
  * and calls to its methods are forwards to the corresponding
  * ns3::Dcf methods.
  */
-class MacLowNavListener {
+class MacLowDcfListener {
 public:
-  MacLowNavListener ();
-  virtual ~MacLowNavListener ();
+  MacLowDcfListener ();
+  virtual ~MacLowDcfListener ();
   /**
    * \param duration duration of NAV timer
    */
@@ -112,6 +112,10 @@
    * \param duration duration of NAV timer
    */
   virtual void NavReset (Time duration) = 0;
+  virtual void AckTimeoutStart (Time duration) = 0;
+  virtual void AckTimeoutReset () = 0;
+  virtual void CtsTimeoutStart (Time duration) = 0;
+  virtual void CtsTimeoutReset () = 0;
 };
 
 /**
@@ -306,7 +310,7 @@
    * \param listener listen to NAV events for every incoming
    *        and outgoing packet.
    */
-  void RegisterNavListener (MacLowNavListener *listener);
+  void RegisterDcfListener (MacLowDcfListener *listener);
 
   /**
    * \param packet to send (does not include the 802.11 MAC header and checksum)
@@ -375,6 +379,10 @@
   void DoNavResetNow (Time duration);
   bool DoNavStartNow (Time duration);
   bool IsNavZero (void) const;
+  void NotifyAckTimeoutStartNow (Time duration);
+  void NotifyAckTimeoutResetNow ();
+  void NotifyCtsTimeoutStartNow (Time duration);
+  void NotifyCtsTimeoutResetNow ();
   void MaybeCancelPrevious (void);
   
   void NavCounterResetCtsMissed (Time rtsEndRxTime);
@@ -397,9 +405,9 @@
   Ptr<WifiPhy> m_phy;
   Ptr<WifiRemoteStationManager> m_stationManager;
   MacLowRxCallback m_rxCallback;
-  typedef std::vector<MacLowNavListener *>::const_iterator NavListenersCI;
-  typedef std::vector<MacLowNavListener *> NavListeners;
-  NavListeners m_navListeners;
+  typedef std::vector<MacLowDcfListener *>::const_iterator DcfListenersCI;
+  typedef std::vector<MacLowDcfListener *> DcfListeners;
+  DcfListeners m_dcfListeners;
 
   EventId m_normalAckTimeoutEvent;
   EventId m_fastAckTimeoutEvent;
diff -r 3135a5c24358 -r b2654e0f071d src/devices/wifi/wifi-mac.cc
--- a/src/devices/wifi/wifi-mac.cc	Mon Jun 08 09:43:47 2009 +0200
+++ b/src/devices/wifi/wifi-mac.cc	Mon Jun 08 13:37:30 2009 +0200
@@ -63,7 +63,7 @@
   */
   Time ctsTimeout = GetDefaultSifs ();
   ctsTimeout += GetDefaultCtsAckDelay ();
-  ctsTimeout += GetDefaultMaxPropagationDelay () * Scalar (2);
+  ctsTimeout += MicroSeconds (GetDefaultMaxPropagationDelay ().GetMicroSeconds () * 2);
   ctsTimeout += GetDefaultSlot ();
   return ctsTimeout;
 }