dcf-manager.cc

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2005,2006 INRIA
 *
 * 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
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 */

#include "ns3/assert.h"
#include "ns3/log.h"
#include "ns3/simulator.h"
#include <cmath>

#include "dcf-manager.h"
#include "wifi-phy.h"
#include "wifi-mac.h"
#include "mac-low.h"

NS_LOG_COMPONENT_DEFINE ("DcfManager");

#define MY_DEBUG(x) \
  NS_LOG_DEBUG (Simulator::Now () << " " << this << " " << x)

namespace ns3 {

/****************************************************************
 *      Implement the DCF state holder
 ****************************************************************/

DcfState::DcfState ()
  : m_backoffSlots (0),
    m_backoffStart (Seconds (0.0)),
    m_cwMin (0),
    m_cwMax (0),
    m_cw (0),
    m_accessRequested (false)
{
}

DcfState::~DcfState ()
{
}

void
DcfState::SetAifsn (uint32_t aifsn)
{
  m_aifsn = aifsn;
}
void
DcfState::SetCwMin (uint32_t minCw)
{
  m_cwMin = minCw;
  ResetCw ();
}
void
DcfState::SetCwMax (uint32_t maxCw)
{
  m_cwMax = maxCw;
  ResetCw ();
}
uint32_t
DcfState::GetAifsn (void) const
{
  return m_aifsn;
}
uint32_t
DcfState::GetCwMin (void) const
{
  return m_cwMin;
}
uint32_t
DcfState::GetCwMax (void) const
{
  return m_cwMax;
}

void
DcfState::ResetCw (void)
{
  m_cw = m_cwMin;
}
void
DcfState::UpdateFailedCw (void)
{
  // see 802.11-2007, section 9.9.1.5
  m_cw = std::min ( 2 * (m_cw + 1) - 1, m_cwMax);
}
void
DcfState::UpdateBackoffSlotsNow (uint32_t nSlots, Time backoffUpdateBound)
{
  m_backoffSlots -= nSlots;
  m_backoffStart = backoffUpdateBound;
  MY_DEBUG ("update slots=" << nSlots << " slots, backoff=" << m_backoffSlots);
}

void
DcfState::StartBackoffNow (uint32_t nSlots)
{
  NS_ASSERT (m_backoffSlots == 0);
  MY_DEBUG ("start backoff=" << nSlots << " slots");
  m_backoffSlots = nSlots;
  m_backoffStart = Simulator::Now ();
}

uint32_t
DcfState::GetCw (void) const
{
  return m_cw;
}
uint32_t
DcfState::GetBackoffSlots (void) const
{
  return m_backoffSlots;
}
Time
DcfState::GetBackoffStart (void) const
{
  return m_backoffStart;
}
bool
DcfState::IsAccessRequested (void) const
{
  return m_accessRequested;
}
void
DcfState::NotifyAccessRequested (void)
{
  m_accessRequested = true;
}
void
DcfState::NotifyAccessGranted (void)
{
  NS_ASSERT (m_accessRequested);
  m_accessRequested = false;
  DoNotifyAccessGranted ();
}
void
DcfState::NotifyCollision (void)
{
  DoNotifyCollision ();
}
void
DcfState::NotifyInternalCollision (void)
{
  DoNotifyInternalCollision ();
}
void
DcfState::NotifyChannelSwitching (void)
{
  DoNotifyChannelSwitching ();
}


/***************************************************************
 *         Listener for Nav events. Forwards to DcfManager
 ***************************************************************/

class LowDcfListener : public ns3::MacLowDcfListener
{
public:
  LowDcfListener (ns3::DcfManager *dcf)
    : m_dcf (dcf)
  {
  }
  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;
};

/***************************************************************
 *         Listener for PHY events. Forwards to DcfManager
 ***************************************************************/

class PhyListener : public ns3::WifiPhyListener
{
public:
  PhyListener (ns3::DcfManager *dcf)
    : m_dcf (dcf)
  {
  }
  virtual ~PhyListener ()
  {
  }
  virtual void NotifyRxStart (Time duration)
  {
    m_dcf->NotifyRxStartNow (duration);
  }
  virtual void NotifyRxEndOk (void)
  {
    m_dcf->NotifyRxEndOkNow ();
  }
  virtual void NotifyRxEndError (void)
  {
    m_dcf->NotifyRxEndErrorNow ();
  }
  virtual void NotifyTxStart (Time duration)
  {
    m_dcf->NotifyTxStartNow (duration);
  }
  virtual void NotifyMaybeCcaBusyStart (Time duration)
  {
    m_dcf->NotifyMaybeCcaBusyStartNow (duration);
  }
  virtual void NotifySwitchingStart (Time duration)
  {
    m_dcf->NotifySwitchingStartNow (duration);
  }
private:
  ns3::DcfManager *m_dcf;
};

/****************************************************************
 *      Implement the DCF manager of all DCF state holders
 ****************************************************************/

DcfManager::DcfManager ()
  : m_lastAckTimeoutEnd (MicroSeconds (0)),
    m_lastCtsTimeoutEnd (MicroSeconds (0)),
    m_lastNavStart (MicroSeconds (0)),
    m_lastNavDuration (MicroSeconds (0)),
    m_lastRxStart (MicroSeconds (0)),
    m_lastRxDuration (MicroSeconds (0)),
    m_lastRxReceivedOk (true),
    m_lastRxEnd (MicroSeconds (0)),
    m_lastTxStart (MicroSeconds (0)),
    m_lastTxDuration (MicroSeconds (0)),
    m_lastBusyStart (MicroSeconds (0)),
    m_lastBusyDuration (MicroSeconds (0)),
    m_lastSwitchingStart (MicroSeconds (0)),
    m_lastSwitchingDuration (MicroSeconds (0)),
    m_rxing (false),
    m_slotTimeUs (0),
    m_sifs (Seconds (0.0)),
    m_phyListener (0),
    m_lowListener (0)
{
}

DcfManager::~DcfManager ()
{
  delete m_phyListener;
  delete m_lowListener;
  m_phyListener = 0;
  m_lowListener = 0;
}

void
DcfManager::SetupPhyListener (Ptr<WifiPhy> phy)
{
  m_phyListener = new PhyListener (this);
  phy->RegisterListener (m_phyListener);
}
void
DcfManager::SetupLowListener (Ptr<MacLow> low)
{
  m_lowListener = new LowDcfListener (this);
  low->RegisterDcfListener (m_lowListener);
}

void
DcfManager::SetSlot (Time slotTime)
{
  m_slotTimeUs = slotTime.GetMicroSeconds ();
}
void
DcfManager::SetSifs (Time sifs)
{
  m_sifs = sifs;
}
void
DcfManager::SetEifsNoDifs (Time eifsNoDifs)
{
  m_eifsNoDifs = eifsNoDifs;
}
Time
DcfManager::GetEifsNoDifs () const
{
  return m_eifsNoDifs;
}

void
DcfManager::Add (DcfState *dcf)
{
  m_states.push_back (dcf);
}

Time
DcfManager::MostRecent (Time a, Time b) const
{
  return Max (a, b);
}
Time
DcfManager::MostRecent (Time a, Time b, Time c) const
{
  Time retval;
  retval = Max (a, b);
  retval = Max (retval, c);
  return retval;
}
Time
DcfManager::MostRecent (Time a, Time b, Time c, Time d) const
{
  Time e = Max (a, b);
  Time f = Max (c, d);
  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;
}

Time
DcfManager::MostRecent (Time a, Time b, Time c, Time d, Time e, Time f, Time g) const
{
  Time h = Max (a, b);
  Time i = Max (c, d);
  Time j = Max (e, f);
  Time k = Max (h, i);
  Time l = Max (j, g);
  Time retval = Max (k, l);
  return retval;
}

bool
DcfManager::IsBusy (void) const
{
  // PHY busy
  if (m_rxing)
    {
      return true;
    }
  Time lastTxEnd = m_lastTxStart + m_lastTxDuration;
  if (lastTxEnd > Simulator::Now ())
    {
      return true;
    }
  // NAV busy
  Time lastNavEnd = m_lastNavStart + m_lastNavDuration;
  if (lastNavEnd > Simulator::Now ())
    {
      return true;
    }
  return false;
}


void
DcfManager::RequestAccess (DcfState *state)
{
  UpdateBackoff ();
  NS_ASSERT (!state->IsAccessRequested ());
  state->NotifyAccessRequested ();
  if (state->GetBackoffSlots () == 0
      && IsBusy ())
    {
      MY_DEBUG ("medium is busy: collision");
      /* someone else has accessed the medium.
       * generate a backoff.
       */
      state->NotifyCollision ();
    }
  DoGrantAccess ();
  DoRestartAccessTimeoutIfNeeded ();
}

void
DcfManager::DoGrantAccess (void)
{
  uint32_t k = 0;
  for (States::const_iterator i = m_states.begin (); i != m_states.end (); k++)
    {
      DcfState *state = *i;
      if (state->IsAccessRequested ()
          && GetBackoffEndFor (state) <= Simulator::Now () )
        {
          MY_DEBUG ("dcf " << k << " needs access. backoff expired. access granted. slots=" << state->GetBackoffSlots ());
          i++; // go to the next item in the list.
          k++;
          std::vector<DcfState *> internalCollisionStates;
          for (States::const_iterator j = i; j != m_states.end (); j++, k++)
            {
              DcfState *otherState = *j;
              if (otherState->IsAccessRequested ()
                  && GetBackoffEndFor (otherState) <= Simulator::Now ())
                {
                  MY_DEBUG ("dcf " << k << " needs access. backoff expired. internal collision. slots=" <<
                            otherState->GetBackoffSlots ());
                  internalCollisionStates.push_back (otherState);
                }
            }

          state->NotifyAccessGranted ();
          for (std::vector<DcfState *>::const_iterator k = internalCollisionStates.begin ();
               k != internalCollisionStates.end (); k++)
            {
              (*k)->NotifyInternalCollision ();
            }
          break;
        }
      i++;
    }
}

void
DcfManager::AccessTimeout (void)
{
  UpdateBackoff ();
  DoGrantAccess ();
  DoRestartAccessTimeoutIfNeeded ();
}

Time
DcfManager::GetAccessGrantStart (void) const
{
  Time rxAccessStart;
  if (!m_rxing)
    {
      rxAccessStart = m_lastRxEnd + m_sifs;
      if (!m_lastRxReceivedOk)
        {
          rxAccessStart += m_eifsNoDifs;
        }
    }
  else
    {
      rxAccessStart = m_lastRxStart + m_lastRxDuration + m_sifs;
    }
  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 switchingAccessStart = m_lastSwitchingStart + m_lastSwitchingDuration + m_sifs;
  Time accessGrantedStart = MostRecent (rxAccessStart,
                                        busyAccessStart,
                                        txAccessStart,
                                        navAccessStart,
                                        ackTimeoutAccessStart,
                                        ctsTimeoutAccessStart,
                                        switchingAccessStart
                                        );
  NS_LOG_INFO ("access grant start=" << accessGrantedStart <<
               ", rx access start=" << rxAccessStart <<
               ", busy access start=" << busyAccessStart <<
               ", tx access start=" << txAccessStart <<
               ", nav access start=" << navAccessStart);
  return accessGrantedStart;
}

Time
DcfManager::GetBackoffStartFor (DcfState *state)
{
  Time mostRecentEvent = MostRecent (state->GetBackoffStart (),
                                     GetAccessGrantStart () + MicroSeconds (state->GetAifsn () * m_slotTimeUs));

  return mostRecentEvent;
}

Time
DcfManager::GetBackoffEndFor (DcfState *state)
{
  return GetBackoffStartFor (state) + MicroSeconds (state->GetBackoffSlots () * m_slotTimeUs);
}

void
DcfManager::UpdateBackoff (void)
{
  uint32_t k = 0;
  for (States::const_iterator i = m_states.begin (); i != m_states.end (); i++, k++)
    {
      DcfState *state = *i;

      Time backoffStart = GetBackoffStartFor (state);
      if (backoffStart <= Simulator::Now ())
        {
          uint32_t nus = (Simulator::Now () - backoffStart).GetMicroSeconds ();
          uint32_t nIntSlots = nus / m_slotTimeUs;
          uint32_t n = std::min (nIntSlots, state->GetBackoffSlots ());
          MY_DEBUG ("dcf " << k << " dec backoff slots=" << n);
          Time backoffUpdateBound = backoffStart + MicroSeconds (n * m_slotTimeUs);
          state->UpdateBackoffSlotsNow (n, backoffUpdateBound);
        }
    }
}

void
DcfManager::DoRestartAccessTimeoutIfNeeded (void)
{
  bool accessTimeoutNeeded = false;
  Time expectedBackoffEnd = Simulator::GetMaximumSimulationTime ();
  for (States::const_iterator i = m_states.begin (); i != m_states.end (); i++)
    {
      DcfState *state = *i;
      if (state->IsAccessRequested ())
        {
          Time tmp = GetBackoffEndFor (state);
          if (tmp > Simulator::Now ())
            {
              accessTimeoutNeeded = true;
              expectedBackoffEnd = std::min (expectedBackoffEnd, tmp);
            }
        }
    }
  if (accessTimeoutNeeded)
    {
      MY_DEBUG ("expected backoff end=" << expectedBackoffEnd);
      Time expectedBackoffDelay = expectedBackoffEnd - Simulator::Now ();
      if (m_accessTimeout.IsRunning ()
          && Simulator::GetDelayLeft (m_accessTimeout) > expectedBackoffDelay)
        {
          m_accessTimeout.Cancel ();
        }
      if (m_accessTimeout.IsExpired ())
        {
          m_accessTimeout = Simulator::Schedule (expectedBackoffDelay,
                                                 &DcfManager::AccessTimeout, this);
        }
    }
}

void
DcfManager::NotifyRxStartNow (Time duration)
{
  MY_DEBUG ("rx start for=" << duration);
  UpdateBackoff ();
  m_lastRxStart = Simulator::Now ();
  m_lastRxDuration = duration;
  m_rxing = true;
}
void
DcfManager::NotifyRxEndOkNow (void)
{
  MY_DEBUG ("rx end ok");
  m_lastRxEnd = Simulator::Now ();
  m_lastRxReceivedOk = true;
  m_rxing = false;
}
void
DcfManager::NotifyRxEndErrorNow (void)
{
  MY_DEBUG ("rx end error");
  m_lastRxEnd = Simulator::Now ();
  m_lastRxReceivedOk = false;
  m_rxing = false;
}
void
DcfManager::NotifyTxStartNow (Time duration)
{
  if (m_rxing)
    {
      //this may be caused only if PHY has started to receive a packet
      //inside SIFS, so, we check that lastRxStart was maximum a SIFS
      //ago
      NS_ASSERT (Simulator::Now () - m_lastRxStart <= m_sifs);
      m_lastRxEnd = Simulator::Now ();
      m_lastRxDuration = m_lastRxEnd - m_lastRxStart;
      m_lastRxReceivedOk = true;
      m_rxing = false;
    }
  MY_DEBUG ("tx start for " << duration);
  UpdateBackoff ();
  m_lastTxStart = Simulator::Now ();
  m_lastTxDuration = duration;
}
void
DcfManager::NotifyMaybeCcaBusyStartNow (Time duration)
{
  MY_DEBUG ("busy start for " << duration);
  UpdateBackoff ();
  m_lastBusyStart = Simulator::Now ();
  m_lastBusyDuration = duration;
}


void
DcfManager::NotifySwitchingStartNow (Time duration)
{
  Time now = Simulator::Now ();
  NS_ASSERT (m_lastTxStart + m_lastTxDuration <= now);
  NS_ASSERT (m_lastSwitchingStart + m_lastSwitchingDuration <= now);

  if (m_rxing)
    {
      // channel switching during packet reception
      m_lastRxEnd = Simulator::Now ();
      m_lastRxDuration = m_lastRxEnd - m_lastRxStart;
      m_lastRxReceivedOk = true;
      m_rxing = false;
    }
  if (m_lastNavStart + m_lastNavDuration > now)
    {
      m_lastNavDuration = now - m_lastNavStart;
    }
  if (m_lastBusyStart + m_lastBusyDuration > now)
    {
      m_lastBusyDuration = now - m_lastBusyStart;
    }
  if (m_lastAckTimeoutEnd > now)
    {
      m_lastAckTimeoutEnd = now;
    }
  if (m_lastCtsTimeoutEnd > now)
    {
      m_lastCtsTimeoutEnd = now;
    }

  // Cancel timeout
  if (m_accessTimeout.IsRunning ())
    {
      m_accessTimeout.Cancel ();
    }

  // Reset backoffs
  for (States::iterator i = m_states.begin (); i != m_states.end (); i++)
    {
      DcfState *state = *i;
      uint32_t remainingSlots = state->GetBackoffSlots ();
      if (remainingSlots > 0)
        {
          state->UpdateBackoffSlotsNow (remainingSlots, now);
          NS_ASSERT (state->GetBackoffSlots () == 0);
        }
      state->ResetCw ();
      state->m_accessRequested = false;
      state->NotifyChannelSwitching ();
    }

  MY_DEBUG ("switching start for " << duration);
  m_lastSwitchingStart = Simulator::Now ();
  m_lastSwitchingDuration = duration;

}

void
DcfManager::NotifyNavResetNow (Time duration)
{
  MY_DEBUG ("nav reset for=" << duration);
  UpdateBackoff ();
  m_lastNavStart = Simulator::Now ();
  m_lastNavDuration = duration;
  UpdateBackoff ();
  DoRestartAccessTimeoutIfNeeded ();
}
void
DcfManager::NotifyNavStartNow (Time duration)
{
  NS_ASSERT (m_lastNavStart < Simulator::Now ());
  MY_DEBUG ("nav start for=" << duration);
  UpdateBackoff ();
  Time newNavEnd = Simulator::Now () + duration;
  Time lastNavEnd = m_lastNavStart + m_lastNavDuration;
  if (newNavEnd > lastNavEnd)
    {
      m_lastNavStart = Simulator::Now ();
      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