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

/*

 * Copyright (c) 2005 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 <math.h>

#include "ns3/simulator.h"

#include "ns3/assert.h"

#include "ns3/log.h"

#include "dcf.h"

#include "random-stream.h"

#include "mac-parameters.h"

NS_LOG_COMPONENT_DEFINE ("Dcf");

namespace ns3 {

DcfAccessListener::DcfAccessListener ()

{}

DcfAccessListener::~DcfAccessListener ()

{}

Dcf::Dcf (uint32_t min, uint32_t max)

  : m_accessTimerEvent (),

    m_cwMin (min),

    m_cwMax (max),

    m_backoffStart (MicroSeconds (0)),

    m_backoffLeft (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_rxing (false)

{

  ResetCw ();

  m_rng = new RealRandomStream ();

}

Dcf::~Dcf ()

{

  delete m_rng;

}

void 

Dcf::ResetRngForTest (RandomStream *stream)

{

  delete m_rng;

  m_rng = stream;

}

void

Dcf::SetParameters (MacParameters const*parameters)

{

  m_parameters = parameters;

}

void 

Dcf::SetDifs (Time difs)

{

  m_difs = difs;

}

void 

Dcf::SetEifs (Time eifs)

{

  m_eifs = eifs;

}

void 

Dcf::SetCwBounds (uint32_t min, uint32_t max)

{

  m_cwMin = min;

  m_cwMax = max;

  m_cw = min;

}

void 

Dcf::RegisterAccessListener (DcfAccessListener *listener)

{

  m_listener = listener;

}

/***************************************************************

 *     public API.

 ***************************************************************/ 

void 

Dcf::RequestAccess (void)

{

  Time delayUntilAccessGranted = GetDelayUntilAccessGranted (Now ());

  if (m_listener->AccessingAndWillNotify ()) 

    {

      /* don't do anything. We will start a backoff and maybe

       * a timer when the txop notifies us of the end-of-access.

       */

      NS_LOG_DEBUG ("accessing. will be notified.");

    } 

  else if (m_accessTimerEvent.IsRunning ()) 

    {

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

       * timer which will expire soon.

       */

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

    } 

  else if (IsBackoffNotCompleted (Now ()) && m_accessTimerEvent.IsExpired ()) 

    {

      /* start timer for ongoing backoff.

       */

      NS_LOG_DEBUG ("request access X delayed for="<<delayUntilAccessGranted);

      m_accessTimerEvent = Simulator::Schedule (delayUntilAccessGranted, 

                                                &Dcf::AccessTimeout, this);

    } 

  else if (IsPhyBusy () || IsNavBusy ()) 

    {

      /* someone else has accessed the medium.

       * generate a backoff, start timer.

       */

      StartBackoff ();

    } 

  else if (delayUntilAccessGranted.IsStrictlyPositive ()) 

    {

      /* medium is IDLE, we have no backoff running but we 

       * need to wait a bit before accessing the medium.

       */

      NS_LOG_DEBUG ("request access Y delayed for="<< delayUntilAccessGranted);

      NS_ASSERT (m_accessTimerEvent.IsExpired ());

      m_accessTimerEvent = Simulator::Schedule (delayUntilAccessGranted, 

                                                &Dcf::AccessTimeout, this);

    } 

  else 

    {

      /* we can access the medium now.

       */

      NS_LOG_DEBUG ("access granted immediatly");

      m_listener->AccessGrantedNow ();

    }

}

/***************************************************************

 *     Timeout method. Notifies when Access is Granted.

 ***************************************************************/ 

void 

Dcf::AccessTimeout ()

{

  UpdateBackoff (Now ());

  if (m_backoffLeft.IsZero ()) 

    {

      NS_LOG_DEBUG ("timeout access granted");

      m_listener->AccessGrantedNow ();

    } 

  else 

    {

      Time delayUntilAccessGranted  = GetDelayUntilAccessGranted (Now ());

      NS_LOG_DEBUG ("timeout access delayed for "<< delayUntilAccessGranted);

      m_accessTimerEvent = Simulator::Schedule (delayUntilAccessGranted, 

                                                &Dcf::AccessTimeout, this);

    }

}

/***************************************************************

 *     Random trivial helper methods.

 ***************************************************************/ 

Time

Dcf::PickBackoffDelay (void)

{

  uint32_t pickedCw = m_rng->GetNext (0, m_cw);

  NS_LOG_DEBUG ("cw="<<GetCwMin ()<<

         "<"<<m_cw<<"<"<<GetCwMax ()<<

         ", picked="<<pickedCw); 

  Time delay = Scalar (pickedCw) * m_parameters->GetSlotTime ();

  return delay;

}

void

Dcf::ResetCw (void)

{

  m_cw = GetCwMin ();

}

void

Dcf::UpdateFailedCw (void)

{

  uint32_t cw = m_cw;

  cw *= 2;

  if (cw > GetCwMax ()) 

    {

      cw = GetCwMax ();

    }

  m_cw = cw;

}

Time

Dcf::MostRecent (Time a, Time b) const

{

  return Max (a, b);

}

Time

Dcf::MostRecent (Time a, Time b, Time c) const

{

  Time retval;

  retval = Max (a, b);

  retval = Max (retval, c);

  return retval;

}

Time

Dcf::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

Dcf::GetDifs (void) const

{

  return m_difs;

}

Time

Dcf::GetEifs (void) const

{

  return m_eifs;

}

uint32_t 

Dcf::GetCwMin (void) const

{

  return m_cwMin;

}

uint32_t 

Dcf::GetCwMax (void) const

{

  return m_cwMax;

}

/***************************************************************

 *     Complicated timekeeping backoff methods.

 ***************************************************************/ 

bool 

Dcf::IsPhyBusy (void) const

{

  if (m_rxing) 

    {

      return true;

    }

  Time lastTxEnd = m_lastTxStart + m_lastTxDuration;

  if (lastTxEnd > Simulator::Now ()) 

    {

      return true;

    }

  return false;

}

bool 

Dcf::IsNavBusy (void) const

{

  Time lastNavEnd = m_lastNavStart + m_lastNavDuration;

  if (lastNavEnd > Simulator::Now ())

    {

      return true;

    }

  return false;

}

void

Dcf::StartBackoff (void)

{

  Time backoffStart = Now ();

  Time backoffDuration = PickBackoffDelay ();

  m_backoffTrace (backoffDuration);

  NS_ASSERT (m_backoffStart <= backoffStart);

  m_backoffStart = backoffStart;

  m_backoffLeft = backoffDuration;

  if (m_listener->AccessNeeded () && m_accessTimerEvent.IsExpired ()) 

    {

      Time delayUntilAccessGranted  = GetDelayUntilAccessGranted (Now ());

      if (delayUntilAccessGranted.IsStrictlyPositive ()) 

        {

          NS_LOG_DEBUG ("start at "<<backoffStart<<", for "<<backoffDuration);

          m_accessTimerEvent = Simulator::Schedule (delayUntilAccessGranted,

                                                    &Dcf::AccessTimeout, this);

        } 

      else 

        {

          NS_LOG_DEBUG ("access granted now");

          m_listener->AccessGrantedNow ();

        }

    } 

  else 

    {

      if (m_accessTimerEvent.IsRunning ()) 

        {

          NS_LOG_DEBUG ("no access needed because timer running.");

        } 

      if (!m_listener->AccessNeeded ()) 

        {

          NS_LOG_DEBUG ("no access needed.");

        }

      NS_LOG_DEBUG ("no access needed for now.");

    }

}

Time

Dcf::GetAccessGrantedStart (void) const

{

  /* This method evaluates the time where access to the

   * medium is allowed. The return value could be 

   * somewhere in the past or in the future.

   */

  Time rxAccessStart;

  if (m_lastRxEnd >= m_lastRxStart) 

    {

      if (m_lastRxReceivedOk) 

        {

          rxAccessStart = m_lastRxEnd + GetDifs ();

        } 

      else

        {

          rxAccessStart = m_lastRxEnd + GetEifs ();

        }

    } 

  else 

    {

      rxAccessStart = m_lastRxStart + m_lastRxDuration + GetDifs ();

    }

  Time busyAccessStart = m_lastBusyStart + m_lastBusyDuration + GetDifs ();

  Time txAccessStart = m_lastTxStart + m_lastTxDuration + GetDifs ();

  Time navAccessStart = m_lastNavStart + m_lastNavDuration + GetDifs ();

  Time accessGrantedStart = MostRecent (rxAccessStart, 

                                        busyAccessStart,

                                        txAccessStart, 

                                        navAccessStart);

  NS_LOG_DEBUG ("access granted start=" << accessGrantedStart);

  return accessGrantedStart;

}

bool

Dcf::IsBackoffNotCompleted (Time now)

{

  UpdateBackoff (now);

  if (m_backoffLeft.IsStrictlyPositive ()) 

    {

      return true;

    } 

  else 

    {

      return false;

    }

}

Time

Dcf::GetDelayUntilAccessGranted (Time now)

{

  Time deltaTo = GetAccessGrantedStart () - now;

  Time retval = Max (deltaTo, Seconds (0));

  UpdateBackoff (now);

  retval += m_backoffLeft;

  return retval;

}

void

Dcf::UpdateBackoff (Time time)

{

  if (m_backoffLeft.IsZero ()) 

    {

      return;

    }

  //NS_LOG_DEBUG ("time: %f, backoffstart: %f\n", time, m_backoffStart);

  NS_ASSERT (time >= m_backoffStart);

  Time mostRecentEvent = MostRecent (m_backoffStart,

                                     GetAccessGrantedStart ());

  if (mostRecentEvent < time) 

    {

      Time newBackoffLeft = m_backoffLeft - (time - mostRecentEvent);

      m_backoffLeft = Max (newBackoffLeft, Seconds (0)); 

      m_backoffStart = time;

    }

  NS_LOG_DEBUG ("backoff at="<<m_backoffStart<<", left="<< m_backoffLeft);

}

/***************************************************************

 *     Notification methods.

 ***************************************************************/ 

void

Dcf::NotifyNavReset (Time navStart, Time duration)

{

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

  m_lastNavStart = navStart;

  m_lastNavDuration = duration;

  Time navEnd = navStart + duration;

  Time newDelayUntilAccessGranted = GetDelayUntilAccessGranted (navEnd);

  NS_ASSERT (newDelayUntilAccessGranted.IsStrictlyPositive ());

  /* This is quite unfortunate but we need to cancel the access timer

   * because this nav reset might have brought the time of

   * possible access closer to us than expected.

   */

  if (m_accessTimerEvent.IsRunning ()) 

    {

      m_accessTimerEvent.Cancel ();

      m_accessTimerEvent = Simulator::Schedule (newDelayUntilAccessGranted,

                                                &Dcf::AccessTimeout, this);

    }

}

void

Dcf::NotifyNavStart (Time navStart, Time duration)

{

  NS_ASSERT (m_lastNavStart < navStart);

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

  UpdateBackoff (navStart);

  m_lastNavStart = navStart;

  m_lastNavDuration = duration;

}

void

Dcf::NotifyNavContinue (Time navStart, Time duration)

{

  NotifyNavStart (navStart, duration);

}

void 

Dcf::NotifyRxStartNow (Time duration)

{

  Time now = Now ();

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

  UpdateBackoff (now);

  m_lastRxStart = now;

  m_lastRxDuration = duration;

  m_rxing = true;

}

void 

Dcf::NotifyRxEndOkNow (void)

{

  Time now = Now ();

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

  m_lastRxEnd = now;

  m_lastRxReceivedOk = true;

  m_rxing = false;

}

void 

Dcf::NotifyRxEndErrorNow (void)

{

  Time now = Now ();

  NS_LOG_DEBUG ("rx end error at=");

  m_lastRxEnd = now;

  m_lastRxReceivedOk = false;

  m_rxing = false;

}

void 

Dcf::NotifyTxStartNow (Time duration)

{

  Time now = Now ();

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

  UpdateBackoff (now);

  m_lastTxStart = now;

  m_lastTxDuration = duration;

}

void 

Dcf::NotifyCcaBusyStartNow (Time duration)

{

  Time now = Now ();

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

  UpdateBackoff (now);

  m_lastBusyStart = now;

  m_lastBusyDuration = duration;

}

} // namespace ns3

#ifdef RUN_SELF_TESTS

#include "ns3/test.h"

#include <list>

namespace ns3 {

class DcfTest : public Test {

public:

  DcfTest ();

  virtual bool RunTests (void);

  // callback from DcfListener

  void AccessGrantedNow (void);

  bool AccessNeeded (void);

  bool AccessingAndWillNotify (void);

private:

  void AddRxOkEvt (uint64_t at, uint64_t duration);

  void AddRxErrorEvt (uint64_t at, uint64_t duration);

  void AddTxEvt (uint64_t at, uint64_t duration);

  void AddNavReset (uint64_t at, uint64_t start, uint64_t duration);

  void AddNavStart (uint64_t at, uint64_t start, uint64_t duration);

  void AddNavContinue (uint64_t at, uint64_t start, uint64_t duration);