# HG changeset patch
# User Timo Bingmann <timo.bingmann@student.kit.edu>
# Date 1244473563 -7200
# Node ID 29593b083227f9a6b18f69098eeb0c87c47c1156
# Parent  d7b076b76ae354e4815471020263265b81b8e2cc
Correction of DCF collision detection time.

diff -r d7b076b76ae3 -r 29593b083227 src/devices/wifi/dcf-manager-test.cc
--- a/src/devices/wifi/dcf-manager-test.cc	Mon Jun 08 15:11:04 2009 +0200
+++ b/src/devices/wifi/dcf-manager-test.cc	Mon Jun 08 17:06:03 2009 +0200
@@ -32,15 +32,20 @@ class DcfStateTest : public DcfState
 {
 public:
   DcfStateTest (DcfManagerTest *test, uint32_t i);
-  void QueueTx (uint64_t txTime, uint64_t expectedGrantTime);
+  void QueueTx (uint64_t txTime, uint64_t expectedGrantTime, uint32_t nBackoffSlots);
 private:
   friend class DcfManagerTest;
   virtual void DoNotifyAccessGranted (void);
   virtual void DoNotifyInternalCollision (void);
   virtual void DoNotifyCollision (void);
 
-  typedef std::pair<uint64_t,uint64_t> ExpectedGrant;
-  typedef std::list<ExpectedGrant> ExpectedGrants;
+  struct ExpectedGrant {
+    uint64_t m_txTime;
+    uint64_t m_expectedGrantTime;
+    uint32_t m_nBackoffSlots;
+  };
+  typedef std::list<struct ExpectedGrant> ExpectedGrants;
+
   struct ExpectedCollision {
     uint64_t at;
     uint32_t nSlots;
@@ -78,14 +83,14 @@ private:
   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);
+  void AddAccessRequest (uint64_t at, uint64_t txTime, uint64_t expectedGrantTime,
+                         uint32_t nBackoffSlots, uint32_t from);
+  void AddAccessRequestWithAckTimeout (uint64_t at, uint64_t txTime, uint64_t expectedGrantTime,
+                                       uint32_t nBackoffSlots, 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);
+  void AddAccessRequestWithSuccessfullAck (uint64_t at, uint64_t txTime, uint64_t expectedGrantTime,
+                                           uint32_t nBackoffSlots, uint32_t ackDelay, uint32_t from);
+  void DoAccessRequest (uint64_t txTime, uint64_t expectedGrantTime, uint32_t nBackoffSlots, DcfStateTest *state);
   
   typedef std::vector<DcfStateTest *> DcfStates;
 
@@ -101,9 +106,13 @@ DcfStateTest::DcfStateTest (DcfManagerTe
   : m_test (test), m_i(i)
 {}
 void 
-DcfStateTest::QueueTx (uint64_t txTime, uint64_t expectedGrantTime)
+DcfStateTest::QueueTx (uint64_t txTime, uint64_t expectedGrantTime, uint32_t nBackoffSlots)
 {
-  m_expectedGrants.push_back (std::make_pair (txTime, expectedGrantTime));
+  struct ExpectedGrant grant;
+  grant.m_txTime = txTime;
+  grant.m_expectedGrantTime = expectedGrantTime;
+  grant.m_nBackoffSlots = nBackoffSlots;
+  m_expectedGrants.push_back (grant);
 }
 void 
 DcfStateTest::DoNotifyAccessGranted (void)
@@ -133,11 +142,12 @@ DcfManagerTest::NotifyAccessGranted (uin
   DcfStateTest *state = m_dcfStates[i];
   bool result = true;
   NS_TEST_ASSERT (!state->m_expectedGrants.empty ());
-  std::pair<uint64_t, uint64_t> expected = state->m_expectedGrants.front ();
+  struct DcfStateTest::ExpectedGrant expected = state->m_expectedGrants.front ();
   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));
+  NS_TEST_ASSERT_EQUAL (Simulator::Now (), MicroSeconds (expected.m_expectedGrantTime));
+  m_dcfManager->NotifyTxStartNow (MicroSeconds (expected.m_txTime));
+  state->StartBackoffNow (expected.m_nBackoffSlots);
+  m_dcfManager->NotifyAckTimeoutStartNow (MicroSeconds (m_ackTimeoutValue + expected.m_txTime));
   if (!result)
     {
       m_result = result;
@@ -275,33 +285,35 @@ DcfManagerTest::AddAckTimeoutReset (uint
                        &DcfManager::NotifyAckTimeoutResetNow, m_dcfManager);
 }
 void 
-DcfManagerTest::AddAccessRequest (uint64_t at, uint64_t txTime, 
-                                  uint64_t expectedGrantTime, uint32_t from)
+DcfManagerTest::AddAccessRequest (uint64_t at, uint64_t txTime,
+                                  uint64_t expectedGrantTime, uint32_t nBackoffSlots,
+                                  uint32_t from)
 {
-  AddAccessRequestWithSuccessfullAck (at, txTime, expectedGrantTime, 0, from);
+  AddAccessRequestWithSuccessfullAck (at, txTime, expectedGrantTime, 0, nBackoffSlots, from);
 }
 void 
-DcfManagerTest::AddAccessRequestWithAckTimeout (uint64_t at, uint64_t txTime, 
-                                  uint64_t expectedGrantTime, uint32_t from)
+DcfManagerTest::AddAccessRequestWithAckTimeout (uint64_t at, uint64_t txTime, uint64_t expectedGrantTime,
+                                                uint32_t nBackoffSlots, uint32_t from)
 {
   Simulator::Schedule (MicroSeconds (at) - Now (), 
                        &DcfManagerTest::DoAccessRequest, this,
-                       txTime, expectedGrantTime, m_dcfStates[from]);
+                       txTime, expectedGrantTime, nBackoffSlots, m_dcfStates[from]);
 }
 void 
-DcfManagerTest::AddAccessRequestWithSuccessfullAck (uint64_t at, uint64_t txTime, 
-                                  uint64_t expectedGrantTime, uint32_t ackDelay, uint32_t from)
+DcfManagerTest::AddAccessRequestWithSuccessfullAck (uint64_t at, uint64_t txTime, uint64_t expectedGrantTime,
+                                                    uint32_t ackDelay, uint32_t nBackoffSlots, uint32_t from)
 {
   NS_ASSERT(ackDelay < m_ackTimeoutValue);
   Simulator::Schedule (MicroSeconds (at) - Now (), 
                        &DcfManagerTest::DoAccessRequest, this,
-                       txTime, expectedGrantTime, m_dcfStates[from]);
+                       txTime, expectedGrantTime, nBackoffSlots, m_dcfStates[from]);
   AddAckTimeoutReset (expectedGrantTime + txTime + ackDelay);
 }
 void
-DcfManagerTest::DoAccessRequest (uint64_t txTime, uint64_t expectedGrantTime, DcfStateTest *state)
+DcfManagerTest::DoAccessRequest (uint64_t txTime, uint64_t expectedGrantTime, uint32_t nBackoffSlots,
+                                 DcfStateTest *state)
 {
-  state->QueueTx (txTime, expectedGrantTime);
+  state->QueueTx (txTime, expectedGrantTime, nBackoffSlots);
   m_dcfManager->RequestAccess (state);
 }
 
@@ -318,8 +330,8 @@ DcfManagerTest::RunTests (void)
   //
   StartTest (1, 3, 10);
   AddDcfState (1);
-  AddAccessRequest (1, 1, 4, 0);
-  AddAccessRequest (10, 2, 10, 0);
+  AddAccessRequest (1, 1, 4, 1, 0);
+  AddAccessRequest (10, 2, 10, 0, 0);
   EndTest ();
 
   // The test below mainly intends to test the case where the medium
@@ -335,7 +347,7 @@ DcfManagerTest::RunTests (void)
   AddDcfState (1);
   AddRxOkEvt (20, 40);
   AddRxOkEvt (80, 20);
-  AddAccessRequest (30, 2, 118, 0);
+  AddAccessRequest (30, 2, 118, 4, 0);
   ExpectCollision (30, 4, 0); // backoff: 4 slots
   EndTest ();
 
@@ -348,10 +360,36 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6 , 10);
   AddDcfState (1);
   AddRxOkEvt (20, 40);
-  AddAccessRequest (30, 2, 70, 0);
+  AddAccessRequest (30, 2, 70, 0, 0);
   ExpectCollision (30, 0, 0); // backoff: 0 slots
   EndTest ();
 
+  // Test case where two packets are queued at DcaTxop, the first send starts
+  // immediately and the second is also immediately indicated but has to wait
+  // for its backoff.
+  //
+  //  20          60     66      70   80
+  //   | tx        | sifs | aifs  | tx |
+  //   |20: request access for both packets
+  StartTest (4, 6 , 10);
+  AddDcfState (1);
+  AddAccessRequest (20, 40, 20, 0, 0);
+  AddAccessRequest (20, 10, 70, 0, 0);
+  EndTest ();
+
+  // Test case where two packets are queued at DcaTxop, the first send starts
+  // immediately and the second is also immediately indicated but has to wait
+  // for its backoff.
+  //
+  //  20          60     66      70        78   88
+  //   | tx        | sifs | aifs  | backoff | tx |
+  //   |20: request access for both packets
+  StartTest (4, 6 , 10);
+  AddDcfState (1);
+  AddAccessRequest (20, 40, 20, 2, 0);
+  AddAccessRequest (20, 10, 78, 0, 0);
+  EndTest ();
+
   // The test below is subject to some discussion because I am 
   // not sure I understand the intent of the spec here.
   // i.e., what happens if you make a request to get access
@@ -368,7 +406,7 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6 , 10);
   AddDcfState (1);
   AddRxOkEvt (20, 40);
-  AddAccessRequest (62, 2, 70, 0);
+  AddAccessRequest (62, 2, 70, 0, 0);
   EndTest ();
 
 
@@ -381,7 +419,7 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6, 10);
   AddDcfState (1);
   AddRxErrorEvt (20, 40);
-  AddAccessRequest (30, 2, 96, 0);
+  AddAccessRequest (30, 2, 96, 4, 0);
   ExpectCollision (30, 4, 0); // backoff: 4 slots  
   EndTest ();
 
@@ -394,7 +432,7 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6, 10);
   AddDcfState (1);
   AddRxErrorEvt (20, 40);
-  AddAccessRequest (30, 2, 101, 0);
+  AddAccessRequest (30, 2, 101, 4, 0);
   ExpectCollision (30, 4, 0); // backoff: 4 slots  
   AddRxOkEvt (69, 6);
   EndTest ();
@@ -411,10 +449,10 @@ DcfManagerTest::RunTests (void)
   AddDcfState (1); // high priority DCF
   AddDcfState (3); // low priority DCF
   AddRxOkEvt (20, 40);
-  AddAccessRequest (30, 10, 78, 0);
+  AddAccessRequest (30, 10, 78, 2, 0);
   ExpectCollision (30, 2, 0); // backoff: 2 slot
 
-  AddAccessRequest (40, 2, 110, 1);
+  AddAccessRequest (40, 2, 110, 0, 1);
   ExpectCollision (40, 0, 1); // backoff: 0 slot
   ExpectInternalCollision (78, 1, 1); // backoff: 1 slot
   EndTest ();
@@ -429,8 +467,8 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6, 10);
   AddDcfState (2); // high priority DCF
   AddDcfState (0); // low priority DCF
-  AddAccessRequestWithAckTimeout (20, 20, 20, 0);
-  AddAccessRequest (50, 10, 66, 1);
+  AddAccessRequestWithAckTimeout (20, 20, 20, 0, 0);
+  AddAccessRequest (50, 10, 66, 0, 1);
   EndTest ();
 
   // Test of AckTimeout handling: 
@@ -445,8 +483,8 @@ DcfManagerTest::RunTests (void)
   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);
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0, 0);
+  AddAccessRequest (41, 10, 48, 0, 1);
   EndTest ();
 
   //Repeat the same but with one queue:
@@ -455,8 +493,8 @@ DcfManagerTest::RunTests (void)
   //                              ^ request access
   StartTest (4, 6, 10);
   AddDcfState (2);
-  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0);
-  AddAccessRequest (41, 10, 56, 0);
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 0, 0);
+  AddAccessRequest (41, 10, 56, 0, 0);
   EndTest ();
 
   //Repeat the same when ack was delayed:
@@ -466,9 +504,10 @@ DcfManagerTest::RunTests (void)
   //                      ^ 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
+  AddAccessRequestWithSuccessfullAck (20, 20, 20, 2, 2, 0);
+  AddAccessRequest (39, 10, 64, 0, 0);
+  // this situation is not supposed to fire an internal or external collison.
+  // ExpectCollision (39, 2, 0); // backoff: 2 slot
   EndTest ();
 
   //
@@ -482,7 +521,7 @@ DcfManagerTest::RunTests (void)
   AddNavStart (60, 15);
   AddRxOkEvt (66, 5);
   AddNavStart (71, 0);
-  AddAccessRequest (30, 10, 93, 0);
+  AddAccessRequest (30, 10, 93, 0, 0);
   ExpectCollision (30, 2, 0); // backoff: 2 slot
   EndTest ();
 
@@ -497,7 +536,7 @@ DcfManagerTest::RunTests (void)
   AddNavStart (60, 15);
   AddRxOkEvt (66, 5);
   AddNavReset (71, 2);
-  AddAccessRequest (30, 10, 91, 0);
+  AddAccessRequest (30, 10, 91, 0, 0);
   ExpectCollision (30, 2, 0); // backoff: 2 slot
   EndTest ();
 
@@ -505,7 +544,7 @@ DcfManagerTest::RunTests (void)
   StartTest (4, 6, 10);
   AddDcfState (2);
   AddRxOkEvt (20, 40);
-  AddAccessRequest (80, 10, 80, 0);
+  AddAccessRequest (80, 10, 80, 0, 0);
   EndTest ();
 
 
@@ -513,10 +552,9 @@ DcfManagerTest::RunTests (void)
   AddDcfState (2);
   AddRxOkEvt (20, 40);
   AddRxOkEvt (78, 8);
-  AddAccessRequest (30, 50, 108, 0);
+  AddAccessRequest (30, 50, 108, 0, 0);
   ExpectCollision (30, 3, 0); // backoff: 3 slots
   EndTest ();
- 
 
   return m_result;
 }
diff -r d7b076b76ae3 -r 29593b083227 src/devices/wifi/dcf-manager.cc
--- a/src/devices/wifi/dcf-manager.cc	Mon Jun 08 15:11:04 2009 +0200
+++ b/src/devices/wifi/dcf-manager.cc	Mon Jun 08 17:06:03 2009 +0200
@@ -42,6 +42,7 @@ namespace ns3 {
 DcfState::DcfState ()
   : m_backoffSlots (0),
     m_backoffStart (Seconds (0.0)),
+    m_backoffElapsed (true),
     m_cwMin (0),
     m_cwMax (0),
     m_cw (0),
@@ -101,6 +102,10 @@ DcfState::UpdateBackoffSlotsNow (uint32_
   m_backoffSlots -= nSlots;
   m_backoffStart = backoffUpdateBound;
   MY_DEBUG ("update slots="<<nSlots<<" slots, backoff="<<m_backoffSlots);
+  if (m_backoffSlots == 0)
+    {
+      m_backoffElapsed = true;
+    }
 }
 
 void 
@@ -110,6 +115,7 @@ DcfState::StartBackoffNow (uint32_t nSlo
   MY_DEBUG ("start backoff="<<nSlots<<" slots");
   m_backoffSlots = nSlots;
   m_backoffStart = Simulator::Now ();
+  m_backoffElapsed = false;
 }
 
 uint32_t
@@ -127,6 +133,11 @@ DcfState::GetBackoffStart (void) const
 {
   return m_backoffStart;
 }
+bool
+DcfState::IsBackoffElapsed (void) const
+{
+  return m_backoffElapsed;
+}
 bool 
 DcfState::IsAccessRequested (void) const
 {
@@ -352,8 +363,7 @@ DcfManager::RequestAccess (DcfState *sta
    * If there is a collision, generate a backoff
    * by notifying the collision to the user.
    */
-  if (state->GetBackoffSlots () == 0 && 
-      IsBusy ())
+  if (state->IsBackoffElapsed() && IsBusy ())
     {
       MY_DEBUG ("medium is busy: collision");
       /* someone else has accessed the medium.
diff -r d7b076b76ae3 -r 29593b083227 src/devices/wifi/dcf-manager.h
--- a/src/devices/wifi/dcf-manager.h	Mon Jun 08 15:11:04 2009 +0200
+++ b/src/devices/wifi/dcf-manager.h	Mon Jun 08 17:06:03 2009 +0200
@@ -80,6 +80,10 @@ public:
    */
   void StartBackoffNow (uint32_t nSlots);
   /**
+   * Returns true if the backoff procedure elapsed.
+   */
+  bool IsBackoffElapsed (void) const; 
+  /**
    * \returns the current value of the CW variable. The initial value is
    * minCW.
    */
@@ -137,6 +141,7 @@ private:
   // time at which a backoff was started or the time at which
   // the backoff counter was last updated.
   Time m_backoffStart;
+  bool m_backoffElapsed;
   uint32_t m_cwMin;
   uint32_t m_cwMax;
   uint32_t m_cw;