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

/*

 * Copyright (c) 2009 Duy Nguyen 

 *

 * 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: Duy Nguyen <duy@soe.ucsc.edu>

 * 

 * Some Comments: 

 * 

 * 1) Segment Size is declared for completeness but not used  because it has 

 *    to do more with the requirement of the specific hardware.

 *

 * 2) By default, Minstrel applies the multi-rate retry(the core of Minstrel 

 *    algorithm). Otherwise, please use ConstantRateWifiManager instead.

 *

 * http://linuxwireless.org/en/developers/Documentation/mac80211/RateControl/minstrel

 */

#include "minstrel-wifi-manager.h"

#include "wifi-phy.h"

#include "ns3/random-variable.h"

#include "ns3/simulator.h"

#include "ns3/log.h"

#include "ns3/uinteger.h"

#include "ns3/double.h"

#include "ns3/wifi-mac.h"

#include "ns3/assert.h"

#include <vector>

NS_LOG_COMPONENT_DEFINE ("MinstrelWifiManager");

namespace ns3 {

/**

 * A struct to contain all information related to a data rate 

 */

struct RateInfo

{

  /**

   * Perfect transmission time calculation, or frame calculation

   * Given a bit rate and a packet length n bytes 

   */

  Time perfectTxTime;		

  uint32_t retryCount;  ///< retry limit

  uint32_t adjustedRetryCount;  ///< adjust the retry limit for this rate

  uint32_t numRateAttempt;  ///< how many number of attempts so far

    uint32_t numRateSuccess;  ///< number of successful pkts 

  uint32_t prob;  ///< (# pkts success )/(# total pkts)

  /**

   * EWMA calculation

   * ewma_prob =[prob *(100 - ewma_level) + (ewma_prob_old * ewma_level)]/100 

   */

  uint32_t ewmaProb;

  uint32_t prevNumRateAttempt;  ///< from last rate

  uint32_t prevNumRateSuccess;  ///< from last rate

  uint64_t successHist;  ///< aggregate of all successes

  uint64_t attemptHist;  ///< aggregate of all attempts

  uint32_t throughput;  ///< throughput of a rate

};

/**

 * Data structure for a Minstrel Rate table 

 * A vector of a struct RateInfo 

 */

typedef std::vector<struct RateInfo> MinstrelRate;

/**

 * Data structure for a Sample Rate table

 * A vector of a vector uint32_t 

 */

typedef std::vector<std::vector<uint32_t> > SampleRate;

struct MinstrelWifiRemoteStation : public WifiRemoteStation

{

  Time m_nextStatsUpdate;  ///< 10 times every second

  MinstrelRate m_minstrelTable;  ///< minstrel table	

  SampleRate m_sampleTable;  ///< sample table

  /**

   * To keep track of the current position in the our random sample table

   * going row by row from 1st column until the 10th column(Minstrel defines 10)

   * then we wrap back to the row 1 col 1.

   * note: there are many other ways to do this.

   */

  uint32_t m_col, m_index;							

  uint32_t m_maxTpRate;  ///< the current throughput rate 

  uint32_t m_maxTpRate2;  ///< second highest throughput rate

  uint32_t m_maxProbRate;  ///< rate with highest prob of success

  int m_packetCount;  ///< total number of packets as of now

  int m_sampleCount;  ///< how many packets we have sample so far

  bool m_isSampling;  ///< a flag to indicate we are currently sampling

  uint32_t m_sampleRate;  ///< current sample rate

  bool 	m_sampleRateSlower;  ///< a flag to indicate sample rate is slower

  uint32_t m_currentRate;  ///< current rate we are using

  uint32_t m_shortRetry;  ///< short retries such as control packts

  uint32_t m_longRetry;  ///< long retries such as data packets

  uint32_t m_retry;  ///< total retries short + long

  uint32_t m_err;  ///< retry errors

  uint32_t m_txrate;  ///< current transmit rate

  bool m_initialized;  ///< for initializing tables

};

NS_OBJECT_ENSURE_REGISTERED (MinstrelWifiManager);

TypeId

MinstrelWifiManager::GetTypeId (void)

{

  static TypeId tid = TypeId ("ns3::MinstrelWifiManager")

    .SetParent<WifiRemoteStationManager> ()

    .AddConstructor<MinstrelWifiManager> ()

    .AddAttribute ("UpdateStatistics",

                   "The interval between updating statistics table ",

                   TimeValue (Seconds (0.1)),

                   MakeTimeAccessor (&MinstrelWifiManager::m_updateStats),

                   MakeTimeChecker ())

    .AddAttribute ("LookAroundRate", 

                   "the percentage to try other rates",

                   DoubleValue (10),

                   MakeDoubleAccessor (&MinstrelWifiManager::m_lookAroundRate),

                   MakeDoubleChecker<double> ())

    .AddAttribute ("EWMA", 

                   "EWMA level",

                   DoubleValue (75),

                   MakeDoubleAccessor (&MinstrelWifiManager::m_ewmaLevel),

                   MakeDoubleChecker<double> ())

    .AddAttribute ("SegmentSize",

                   "The largest allowable segment size packet",

                   DoubleValue (6000),

                   MakeDoubleAccessor (&MinstrelWifiManager::m_segmentSize),

                   MakeDoubleChecker <double> ())

    .AddAttribute ("SampleColumn",

                   "The number of columns used for sampling",

                   DoubleValue (10),

                   MakeDoubleAccessor (&MinstrelWifiManager::m_sampleCol),

                   MakeDoubleChecker <double> ())

    .AddAttribute ("PacketLength",

                   "The packet length used for calculating mode TxTime",

                   DoubleValue (1200),

                   MakeDoubleAccessor (&MinstrelWifiManager::m_pktLen),

                   MakeDoubleChecker <double> ())

    ;

  return tid;

}

MinstrelWifiManager::MinstrelWifiManager ()

{}

MinstrelWifiManager::~MinstrelWifiManager ()

{}

void

MinstrelWifiManager::SetupPhy (Ptr<WifiPhy> phy)

{

  uint32_t nModes = phy->GetNModes ();

  for (uint32_t i = 0; i < nModes; i++)

    {

      WifiMode mode = phy->GetMode (i);

      AddCalcTxTime (mode, phy->CalculateTxDuration (m_pktLen, mode, WIFI_PREAMBLE_LONG));

    }

  WifiRemoteStationManager::SetupPhy (phy);

}

Time

MinstrelWifiManager::GetCalcTxTime (WifiMode mode) const

{

  for (TxTime::const_iterator i = m_calcTxTime.begin (); i != m_calcTxTime.end (); i++)

    {

      if (mode == i->second)

        {

          return i->first;

        }

    }

  NS_ASSERT (false);

  return Seconds (0);

}

void

MinstrelWifiManager::AddCalcTxTime (WifiMode mode, Time t)

{

   m_calcTxTime.push_back (std::make_pair (t, mode));

}

WifiRemoteStation *

MinstrelWifiManager::DoCreateStation (void) const

{

  MinstrelWifiRemoteStation *station = new MinstrelWifiRemoteStation ();

  station->m_nextStatsUpdate = Simulator::Now () + m_updateStats;

  station->m_col = 0;

  station->m_index = 0; 

  station->m_maxTpRate = 0; 

  station->m_maxTpRate2 = 0; 

  station->m_maxProbRate = 0;

  station->m_packetCount = 0; 

  station->m_sampleCount = 0; 

  station->m_isSampling = false; 

  station->m_sampleRate = 0;

  station->m_sampleRateSlower = false;

  station->m_currentRate = 0;

  station->m_shortRetry = 0;

  station->m_longRetry = 0;

  station->m_retry = 0;

  station->m_err = 0;

  station->m_txrate = 0;

  station->m_initialized = false;

  return station;

}

void 

MinstrelWifiManager::CheckInit(MinstrelWifiRemoteStation *station)

{

  if (!station->m_initialized)

    {

      // Note: we appear to be doing late initialization of the table 

      // to make sure that the set of supported rates has been initialized

      // before we perform our own initialization.

      station->m_minstrelTable = MinstrelRate(GetNSupported (station));

      station->m_sampleTable = SampleRate(GetNSupported (station), std::vector<uint32_t> (m_sampleCol));

      InitSampleTable (station);

      RateInit (station);

      station->m_initialized = true;

    }

}

void

MinstrelWifiManager::DoReportRxOk (WifiRemoteStation *st,

                                   double rxSnr, WifiMode txMode)

{

}

void

MinstrelWifiManager::DoReportRtsFailed (WifiRemoteStation *st)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *)st;

  NS_LOG_DEBUG("DoReportRtsFailed m_txrate=" << station->m_txrate);

  station->m_shortRetry++;

}

void

MinstrelWifiManager::DoReportRtsOk (WifiRemoteStation *st, double ctsSnr, WifiMode ctsMode, double rtsSnr)

{

  NS_LOG_DEBUG ("self="<<st<<" rts ok");

}

void

MinstrelWifiManager::DoReportFinalRtsFailed (WifiRemoteStation *st)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *)st;

  UpdateRetry (station);

  station->m_err++;

}

void

MinstrelWifiManager::DoReportDataFailed (WifiRemoteStation *st)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *)st;

  /**

   *

   * Retry Chain table is implemented here

   *

   * Try |         LOOKAROUND RATE              | NORMAL RATE

   *     | random < best    | random > best     |

   * --------------------------------------------------------------

   *  1  | Best throughput  | Random rate       | Best throughput

   *  2  | Random rate      | Best throughput   | Next best throughput

   *  3  | Best probability | Best probability  | Best probability

   *  4  | Lowest Baserate  | Lowest baserate   | Lowest baserate

   *

   * Note: For clarity, multiple blocks of if's and else's are used

   * After a failing 7 times, DoReportFinalDataFailed will be called

   */

  CheckInit(station);

  station->m_longRetry++;

  NS_LOG_DEBUG ("DoReportDataFailed " << station << "\t rate " << station->m_txrate << "\tlongRetry \t" << station->m_longRetry);

  /// for normal rate, we're not currently sampling random rates

  if (!station->m_isSampling)

    {

      /// use best throughput rate

      if (station->m_longRetry < station->m_minstrelTable[station->m_txrate].adjustedRetryCount)

        {

          ;  ///<  there's still a few retries left

        }

      /// use second best throughput rate

      else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount +  

                                        station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))

        {

          station->m_txrate = station->m_maxTpRate2;

        }

      /// use best probability rate

      else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount +  

                                        station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount + 

                                        station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))

        {

          station->m_txrate = station->m_maxProbRate;

        }

      /// use lowest base rate	

      else if (station->m_longRetry > (station->m_minstrelTable[station->m_txrate].adjustedRetryCount +  

                              station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount + 

                              station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))

        {

          station->m_txrate = 0;

        }

    }

  /// for look-around rate, we're currently sampling random rates

  else

    {

      /// current sampling rate is slower than the current best rate

      if (station->m_sampleRateSlower)

        {

          /// use best throughput rate

          if (station->m_longRetry < station->m_minstrelTable[station->m_txrate].adjustedRetryCount)

            {

              ;	///<  there are a few retries left

            }

          ///	use random rate

          else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount + 

                                            station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))

            {

              station->m_txrate = station->m_sampleRate;

            }

          /// use max probability rate

          else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount +  

                                            station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount + 

                                            station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount ))

            {

              station->m_txrate = station->m_maxProbRate;

            }

          /// use lowest base rate

          else if (station->m_longRetry > (station->m_minstrelTable[station->m_txrate].adjustedRetryCount +  

                                           station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount + 

                                           station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))

            {

              station->m_txrate = 0;

            }

        }

        /// current sampling rate is better than current best rate 

        else

          {

            /// use random rate

            if (station->m_longRetry < station->m_minstrelTable[station->m_txrate].adjustedRetryCount)

              {

                ;  ///< keep using it

              }

            /// use the best rate

            else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount + 

                                              station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount))

              {

                station->m_txrate = station->m_maxTpRate;

              }

            /// use the best probability rate

            else if (station->m_longRetry <= (station->m_minstrelTable[station->m_txrate].adjustedRetryCount + 

                                              station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +  

                                              station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount))

              {

                station->m_txrate = station->m_maxProbRate;

              }

            /// use the lowest base rate

            else if (station->m_longRetry > (station->m_minstrelTable[station->m_txrate].adjustedRetryCount + 

                                             station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +  

                                             station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount))

              {

                station->m_txrate = 0;

              }

          }

    }

}

void

MinstrelWifiManager::DoReportDataOk (WifiRemoteStation *st,

                                     double ackSnr, WifiMode ackMode, double dataSnr)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *) st;

  station->m_isSampling = false;

  station->m_sampleRateSlower=false;

  CheckInit (station);

  station->m_minstrelTable[station->m_txrate].numRateSuccess++;

  station->m_minstrelTable[station->m_txrate].numRateAttempt++;

  UpdateRetry (station);

  station->m_minstrelTable[station->m_txrate].numRateAttempt += station->m_retry;

  station->m_packetCount++;

  if (GetNSupported (station) >= 1)

    {

      station->m_txrate = FindRate (station);

    }

}

void

MinstrelWifiManager::DoReportFinalDataFailed (WifiRemoteStation *st)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *) st;

  NS_LOG_DEBUG ("DoReportFinalDataFailed m_txrate=" << station->m_txrate);

  station->m_isSampling = false;

  station->m_sampleRateSlower=false;

  UpdateRetry (station);

  station->m_minstrelTable[station->m_txrate].numRateAttempt += station->m_retry;

  station->m_err++;

  if (GetNSupported (station) >= 1)

    {

      station->m_txrate = FindRate (station);

    }

}

void

MinstrelWifiManager::UpdateRetry (MinstrelWifiRemoteStation *station)

{

  station->m_retry = station->m_shortRetry + station->m_longRetry;

  station->m_shortRetry = 0;

  station->m_longRetry = 0;

}

WifiMode

MinstrelWifiManager::DoGetDataMode (WifiRemoteStation *st,

                                    uint32_t size)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *) st;

  if (!station->m_initialized)

    {

      CheckInit (station);

      /// start the rate at half way

      station->m_txrate = GetNSupported (station) / 2;

    }

  UpdateStats (station);

  return GetSupported (station, station->m_txrate);

}

WifiMode

MinstrelWifiManager::DoGetRtsMode (WifiRemoteStation *st)

{

  MinstrelWifiRemoteStation *station = (MinstrelWifiRemoteStation *) st;

  NS_LOG_DEBUG ("DoGetRtsMode m_txrate=" << station->m_txrate);

  return GetSupported (station, 0);

}

bool 

MinstrelWifiManager::IsLowLatency (void) const

{

  return false;

}

uint32_t 

MinstrelWifiManager::GetNextSample (MinstrelWifiRemoteStation *station)

{

  uint32_t bitrate;

  bitrate = station->m_sampleTable[station->m_index][station->m_col];

  station->m_index++;

  /// bookeeping for m_index and m_col variables

  if (station->m_index > (GetNSupported (station) - 2)) 

    {

      station->m_index =0;

      station->m_col++;

      if (station->m_col >= m_sampleCol)