1 /* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */

     2 

     3 #include "ns3/assert.h"

     4 #include "ns3/log.h"

     5 #include "ns3/simulator.h"

     6 #include <math.h>

     7 

     8 #include "dcf-manager.h"

     9 #include "mac-parameters.h"

    10 

    11 NS_LOG_COMPONENT_DEFINE ("DcfManager");

    12 

    13 namespace ns3 {

    14 

    15 /****************************************************************

    16  *      Implement the DCF state holder

    17  ****************************************************************/

    18 

    19 void 

    20 DcfState::SetAifsn (uint32_t aifsn)

    21 {

    22   m_aifsn = aifsn;

    23 }

    24 

    25 void 

    26 DcfState::SetCwBounds (uint32_t minCw, uint32_t maxCw)

    27 {

    28   m_cwMin = minCw;

    29   m_cwMax = maxCw;

    30 }

    31 

    32 void 

    33 DcfState::ResetCw (void)

    34 {

    35   m_cw = m_cwMin;

    36 }

    37 void 

    38 DcfState::UpdateFailedCw (void)

    39 {

    40   uint32_t cw = m_cw;

    41   cw *= 2;

    42   cw = std::min (m_cwMax, cw);

    43   m_cw = cw;

    44 }

    45 void 

    46 DcfState::UpdateBackoffSlotsNow (uint32_t nSlots)

    47 {

    48   uint32_t n = std::min (nSlots, m_backoffSlots);

    49   m_backoffSlots -= n;

    50 }

    51 

    52 void 

    53 DcfState::StartBackoffNow (uint32_t nSlots)

    54 {

    55   NS_ASSERT (m_backoffSlots == 0);

    56   m_backoffSlots = nSlots;

    57   m_backoffStart = Simulator::Now ();

    58 }

    59 

    60 uint32_t 

    61 DcfState::GetAifsn (void) const

    62 {

    63   return m_aifsn;

    64 }

    65 uint32_t

    66 DcfState::GetCw (void) const

    67 {

    68   return m_cw;

    69 }

    70 uint32_t 

    71 DcfState::GetBackoffSlots (void) const

    72 {

    73   return m_backoffSlots;

    74 }

    75 Time 

    76 DcfState::GetBackoffStart (void) const

    77 {

    78   return m_backoffStart;

    79 }

    80 

    81 

    82 /****************************************************************

    83  *      Implement the DCF manager of all DCF state holders

    84  ****************************************************************/

    85 

    86 void 

    87 DcfManager::Add (DcfState *dcf)

    88 {

    89   m_states.push_back (dcf);

    90 }

    91 

    92 Time

    93 DcfManager::MostRecent (Time a, Time b) const

    94 {

    95   return Max (a, b);

    96 }

    97 Time

    98 DcfManager::MostRecent (Time a, Time b, Time c) const

    99 {

   100   Time retval;

   101   retval = Max (a, b);

   102   retval = Max (retval, c);

   103   return retval;

   104 }

   105 Time

   106 DcfManager::MostRecent (Time a, Time b, Time c, Time d) const

   107 {

   108   Time e = Max (a, b);

   109   Time f = Max (c, d);

   110   Time retval = Max (e, f);

   111   return retval;

   112 }

   113 

   114 bool 

   115 DcfManager::IsBusy (void) const

   116 {

   117   // PHY busy

   118   if (m_rxing) 

   119     {

   120       return true;

   121     }

   122   Time lastTxEnd = m_lastTxStart + m_lastTxDuration;

   123   if (lastTxEnd > Simulator::Now ()) 

   124     {

   125       return true;

   126     }

   127   // NAV busy

   128   Time lastNavEnd = m_lastNavStart + m_lastNavDuration;

   129   if (lastNavEnd > Simulator::Now ())

   130     {

   131       return true;

   132     }

   133   return false;

   134 }

   135 

   136 

   137 void 

   138 DcfManager::RequestAccess (DcfState *state)

   139 {

   140   UpdateBackoff ();

   141   if (m_accessTimeout.IsRunning ())

   142     {

   143       /* we don't need to do anything because we have an access

   144        * timer which will expire soon.

   145        */

   146       NS_LOG_DEBUG ("access timer running. will be notified");

   147       return;

   148     }

   149   /**

   150    * Since no access timeout is running, and if we have no

   151    * backoff running for this DcfState, start a new backoff

   152    * if needed.

   153    */ 

   154   if (state->GetBackoffSlots () == 0 && 

   155       IsBusy ())

   156     {

   157       /* someone else has accessed the medium.

   158        * generate a backoff.

   159        */

   160       state->NotifyCollision ();

   161     }

   162 

   163   DoGrantAccess ();

   164   DoRestartAccessTimeoutIfNeeded ();  

   165 }

   166 

   167 void

   168 DcfManager::DoGrantAccess (void)

   169 {

   170   for (States::const_iterator i = m_states.begin (); i != m_states.end (); )

   171     {

   172       DcfState *state = *i;

   173       if (state->GetBackoffSlots () == 0 && state->NeedsAccess ())

   174         {

   175           /**

   176            * This is the first dcf we find with an expired backoff and which

   177            * needs access to the medium. i.e., it has data to send.

   178            */

   179           state->NotifyAccessGranted ();

   180           i++; // go to the next item in the list.

   181           for (States::const_iterator j = i; j != m_states.end (); j++)

   182             {

   183               DcfState *state = *j;

   184               if (state->GetBackoffSlots () == 0 && state->NeedsAccess ())

   185                 {

   186                   /**

   187                    * all other dcfs with a lower priority whose backoff

   188                    * has expired and which needed access to the medium

   189                    * must be notified that we did get an internal collision.

   190                    */

   191                   state->NotifyInternalCollision ();

   192                 }

   193             }

   194           break;

   195         }

   196       i++;

   197     }

   198 }

   199 

   200 void

   201 DcfManager::AccessTimeout (void)

   202 {

   203   UpdateBackoff ();

   204   DoGrantAccess ();

   205   DoRestartAccessTimeoutIfNeeded ();

   206 }

   207 

   208 Time

   209 DcfManager::GetAccessGrantStart (void) const

   210 {

   211   Time rxAccessStart;

   212   if (m_lastRxEnd >= m_lastRxStart) 

   213     {

   214       rxAccessStart = m_lastRxEnd + m_parameters->GetSifs ();

   215       if (!m_lastRxReceivedOk) 

   216         {

   217           rxAccessStart += m_ackTxTime;

   218         } 

   219     } 

   220   else 

   221     {

   222       rxAccessStart = m_lastRxStart + m_lastRxDuration + m_parameters->GetSifs ();

   223     }

   224   Time busyAccessStart = m_lastBusyStart + m_lastBusyDuration + m_parameters->GetSifs ();

   225   Time txAccessStart = m_lastTxStart + m_lastTxDuration + m_parameters->GetSifs ();

   226   Time navAccessStart = m_lastNavStart + m_lastNavDuration + m_parameters->GetSifs ();

   227   Time accessGrantedStart = MostRecent (rxAccessStart, 

   228                                         busyAccessStart,

   229                                         txAccessStart, 

   230                                         navAccessStart);

   231   NS_LOG_DEBUG ("access grant start=" << accessGrantedStart);

   232   return accessGrantedStart;

   233 }

   234 

   235 void

   236 DcfManager::UpdateBackoff (void)

   237 {

   238   for (States::const_iterator i = m_states.begin (); i != m_states.end (); i++)

   239     {

   240       DcfState *state = *i;

   241 

   242       Time mostRecentEvent = MostRecent (state->GetBackoffStart (),

   243                                          GetAccessGrantStart ());

   244       if (mostRecentEvent < Simulator::Now ())

   245         {

   246           Scalar nSlots = (Simulator::Now () - mostRecentEvent) / m_parameters->GetSlotTime ();

   247           uint32_t nIntSlots = lrint (nSlots.GetDouble ());

   248           /**

   249            * For each DcfState, calculate how many backoff slots elapsed since

   250            * the last time its backoff counter was updated. If the number of 

   251            * slots is smaller than its AIFSN, the backoff did not start, so,

   252            * we do not update it.

   253            */

   254           if (nIntSlots > state->GetAifsn ())

   255             {

   256               state->UpdateBackoffSlotsNow (nIntSlots - state->GetAifsn ());

   257             }

   258         }

   259     }

   260 }

   261 

   262 void

   263 DcfManager::DoRestartAccessTimeoutIfNeeded (void)

   264 {

   265   /**

   266    * Is there a DcfState which needs to access the medium, and, 

   267    * if there is one, how many slots for AIFS+backoff does it require ?

   268    */

   269   bool accessTimeoutNeeded = false;

   270   uint32_t minNSlots = 0xffffffff;

   271   Time backoffStart;

   272   for (States::const_iterator i = m_states.begin (); i != m_states.end (); i++)

   273     {

   274       DcfState *state = *i;

   275       if (state->NeedsAccess ())

   276         {

   277           accessTimeoutNeeded = true;

   278           minNSlots = std::min (state->GetAifsn () + state->GetBackoffSlots (), minNSlots);

   279         }

   280     }

   281   if (accessTimeoutNeeded)

   282     {

   283       /**

   284        * If one of the DcfState needs access to the medium, calculate when its

   285        * backoff is expected to end.

   286        */

   287       Time expectedBackoffEnd = GetAccessGrantStart () + Scalar (minNSlots) * m_parameters->GetSlotTime ();

   288       /**

   289        * It is not possible that the backoff was expected to end before now

   290        * because if it were possible, this would mean that we have missed

   291        * a backoff expiration ! And that would be a bug.

   292        */

   293       NS_ASSERT (expectedBackoffEnd >= Simulator::Now ());

   294       if (expectedBackoffEnd > Simulator::Now ())

   295         {

   296           Time expectedBackoffDelay = expectedBackoffEnd - Simulator::Now ();

   297           if (m_accessTimeout.IsRunning () &&

   298               Simulator::GetDelayLeft (m_accessTimeout) > expectedBackoffDelay)

   299             {

   300               m_accessTimeout.Cancel ();

   301             }

   302           if (m_accessTimeout.IsExpired ())

   303             {

   304               m_accessTimeout = Simulator::Schedule (expectedBackoffDelay,

   305                                                      &DcfManager::AccessTimeout, this);

   306             }

   307         }

   308     }

   309 }

   310 

   311 void 

   312 DcfManager::NotifyRxStartNow (Time duration)

   313 {

   314   Time now = Simulator::Now ();

   315   NS_LOG_DEBUG ("rx start at="<<now<<", for="<<duration);

   316   UpdateBackoff ();

   317   m_lastRxStart = now;

   318   m_lastRxDuration = duration;

   319   m_rxing = true;

   320 }

   321 void 

   322 DcfManager::NotifyRxEndOkNow (void)

   323 {

   324   Time now = Simulator::Now ();

   325   NS_LOG_DEBUG ("rx end ok at="<<now);

   326   m_lastRxEnd = now;

   327   m_lastRxReceivedOk = true;

   328   m_rxing = false;

   329 }

   330 void 

   331 DcfManager::NotifyRxEndErrorNow (void)

   332 {

   333   Time now = Simulator::Now ();

   334   NS_LOG_DEBUG ("rx end error at=");

   335   m_lastRxEnd = now;

   336   m_lastRxReceivedOk = false;

   337   m_rxing = false;

   338 }

   339 void 

   340 DcfManager::NotifyTxStartNow (Time duration)

   341 {

   342   Time now = Simulator::Now ();

   343   NS_LOG_DEBUG ("tx start at="<<now<<" for "<<duration);

   344   UpdateBackoff ();

   345   m_lastTxStart = now;

   346   m_lastTxDuration = duration;

   347 }

   348 void 

   349 DcfManager::NotifyCcaBusyStartNow (Time duration)

   350 {

   351   Time now = Simulator::Now ();

   352   NS_LOG_DEBUG ("busy start at="<<now<<" for "<<duration);

   353   UpdateBackoff ();

   354   m_lastBusyStart = now;

   355   m_lastBusyDuration = duration;

   356 }

   357 void 

   358 DcfManager::NotifyNavResetNow (Time duration)

   359 {

   360   Time now = Simulator::Now ();

   361   NS_LOG_DEBUG ("nav reset at="<<now<<", for="<<duration);

   362   UpdateBackoff ();

   363   m_lastNavStart = now;

   364   m_lastNavDuration = duration;

   365   UpdateBackoff ();

   366   /**

   367    * If the nav reset indicates an end-of-nav which is earlier

   368    * than the previous end-of-nav, the expected end of backoff

   369    * might be later than previously thought so, we might need

   370    * to restart a new access timeout.

   371    */

   372   DoRestartAccessTimeoutIfNeeded ();

   373 }

   374 void 

   375 DcfManager::NotifyNavStartNow (Time duration)

   376 {

   377   Time now = Simulator::Now ();

   378   NS_ASSERT (m_lastNavStart < now);

   379   NS_LOG_DEBUG ("nav start at="<<now<<", for="<<duration);

   380   UpdateBackoff ();

   381   // XXX handle 

   382   m_lastNavStart = now;

   383   m_lastNavDuration = duration;

   384 }

   385 

   386 } // namespace ns3