1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2009 Duy Nguyen
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17  *
18  * Authors: Duy Nguyen <duy@soe.ucsc.edu>
19  *          Matías Richart <mrichart@fing.edu.uy>
20  *
21  * Some Comments:
22  *
23  * 1) Segment Size is declared for completeness but not used  because it has
24  *    to do more with the requirement of the specific hardware.
25  *
26  * 2) By default, Minstrel applies the multi-rate retry (the core of Minstrel
27  *    algorithm). Otherwise, please use ConstantRateWifiManager instead.
28  *
29  * http://linuxwireless.org/en/developers/Documentation/mac80211/RateControl/minstrel
30  */
31 
32 #include <iomanip>
33 #include "ns3/packet.h"
34 #include "ns3/random-variable-stream.h"
35 #include "ns3/simulator.h"
36 #include "ns3/log.h"
37 #include "minstrel-wifi-manager.h"
38 #include "ns3/wifi-mac.h"
39 #include "ns3/wifi-phy.h"
40 
41 #define Min(a,b) ((a < b) ? a : b)
42 
43 namespace ns3 {
44 
45 NS_LOG_COMPONENT_DEFINE ("MinstrelWifiManager");
46 
47 NS_OBJECT_ENSURE_REGISTERED (MinstrelWifiManager);
48 
49 TypeId
GetTypeId(void)50 MinstrelWifiManager::GetTypeId (void)
51 {
52   static TypeId tid = TypeId ("ns3::MinstrelWifiManager")
53     .SetParent<WifiRemoteStationManager> ()
54     .SetGroupName ("Wifi")
55     .AddConstructor<MinstrelWifiManager> ()
56     .AddAttribute ("UpdateStatistics",
57                    "The interval between updating statistics table ",
58                    TimeValue (Seconds (0.1)),
59                    MakeTimeAccessor (&MinstrelWifiManager::m_updateStats),
60                    MakeTimeChecker ())
61     .AddAttribute ("LookAroundRate",
62                    "The percentage to try other rates",
63                    UintegerValue (10),
64                    MakeUintegerAccessor (&MinstrelWifiManager::m_lookAroundRate),
65                    MakeUintegerChecker<uint8_t> ())
66     .AddAttribute ("EWMA",
67                    "EWMA level",
68                    UintegerValue (75),
69                    MakeUintegerAccessor (&MinstrelWifiManager::m_ewmaLevel),
70                    MakeUintegerChecker<uint8_t> ())
71     .AddAttribute ("SampleColumn",
72                    "The number of columns used for sampling",
73                    UintegerValue (10),
74                    MakeUintegerAccessor (&MinstrelWifiManager::m_sampleCol),
75                    MakeUintegerChecker <uint8_t> ())
76     .AddAttribute ("PacketLength",
77                    "The packet length used for calculating mode TxTime",
78                    UintegerValue (1200),
79                    MakeUintegerAccessor (&MinstrelWifiManager::m_pktLen),
80                    MakeUintegerChecker <uint32_t> ())
81     .AddAttribute ("PrintStats",
82                    "Print statistics table",
83                    BooleanValue (false),
84                    MakeBooleanAccessor (&MinstrelWifiManager::m_printStats),
85                    MakeBooleanChecker ())
86     .AddAttribute ("PrintSamples",
87                    "Print samples table",
88                    BooleanValue (false),
89                    MakeBooleanAccessor (&MinstrelWifiManager::m_printSamples),
90                    MakeBooleanChecker ())
91     .AddTraceSource ("Rate",
92                      "Traced value for rate changes (b/s)",
93                      MakeTraceSourceAccessor (&MinstrelWifiManager::m_currentRate),
94                      "ns3::TracedValueCallback::Uint64")
95   ;
96   return tid;
97 }
98 
MinstrelWifiManager()99 MinstrelWifiManager::MinstrelWifiManager ()
100   : WifiRemoteStationManager (),
101     m_currentRate (0)
102 {
103   NS_LOG_FUNCTION (this);
104   m_uniformRandomVariable = CreateObject<UniformRandomVariable> ();
105 }
106 
~MinstrelWifiManager()107 MinstrelWifiManager::~MinstrelWifiManager ()
108 {
109   NS_LOG_FUNCTION (this);
110 }
111 
112 void
SetupPhy(const Ptr<WifiPhy> phy)113 MinstrelWifiManager::SetupPhy (const Ptr<WifiPhy> phy)
114 {
115   NS_LOG_FUNCTION (this << phy);
116   for (const auto & mode : phy->GetModeList ())
117     {
118       WifiTxVector txVector;
119       txVector.SetMode (mode);
120       txVector.SetPreambleType (WIFI_PREAMBLE_LONG);
121       AddCalcTxTime (mode, phy->CalculateTxDuration (m_pktLen, txVector, phy->GetPhyBand ()));
122     }
123   WifiRemoteStationManager::SetupPhy (phy);
124 }
125 
126 void
SetupMac(const Ptr<WifiMac> mac)127 MinstrelWifiManager::SetupMac (const Ptr<WifiMac> mac)
128 {
129   NS_LOG_FUNCTION (this << mac);
130   WifiRemoteStationManager::SetupMac (mac);
131 }
132 
133 void
DoInitialize()134 MinstrelWifiManager::DoInitialize ()
135 {
136   NS_LOG_FUNCTION (this);
137   if (GetHtSupported ())
138     {
139       NS_FATAL_ERROR ("WifiRemoteStationManager selected does not support HT rates");
140     }
141   if (GetVhtSupported ())
142     {
143       NS_FATAL_ERROR ("WifiRemoteStationManager selected does not support VHT rates");
144     }
145   if (GetHeSupported ())
146     {
147       NS_FATAL_ERROR ("WifiRemoteStationManager selected does not support HE rates");
148     }
149 }
150 
151 int64_t
AssignStreams(int64_t stream)152 MinstrelWifiManager::AssignStreams (int64_t stream)
153 {
154   NS_LOG_FUNCTION (this << stream);
155   m_uniformRandomVariable->SetStream (stream);
156   return 1;
157 }
158 
159 Time
GetCalcTxTime(WifiMode mode) const160 MinstrelWifiManager::GetCalcTxTime (WifiMode mode) const
161 {
162   NS_LOG_FUNCTION (this << mode);
163   auto it = m_calcTxTime.find (mode);
164   NS_ASSERT (it != m_calcTxTime.end ());
165   return it->second;
166 }
167 
168 void
AddCalcTxTime(WifiMode mode,Time t)169 MinstrelWifiManager::AddCalcTxTime (WifiMode mode, Time t)
170 {
171   NS_LOG_FUNCTION (this << mode << t);
172   m_calcTxTime.insert (std::make_pair (mode, t));
173 }
174 
175 WifiRemoteStation *
DoCreateStation(void) const176 MinstrelWifiManager::DoCreateStation (void) const
177 {
178   NS_LOG_FUNCTION (this);
179   MinstrelWifiRemoteStation *station = new MinstrelWifiRemoteStation ();
180 
181   station->m_nextStatsUpdate = Simulator::Now () + m_updateStats;
182   station->m_col = 0;
183   station->m_index = 0;
184   station->m_maxTpRate = 0;
185   station->m_maxTpRate2 = 0;
186   station->m_maxProbRate = 0;
187   station->m_nModes = 0;
188   station->m_totalPacketsCount = 0;
189   station->m_samplePacketsCount = 0;
190   station->m_isSampling = false;
191   station->m_sampleRate = 0;
192   station->m_sampleDeferred = false;
193   station->m_shortRetry = 0;
194   station->m_longRetry = 0;
195   station->m_retry = 0;
196   station->m_txrate = 0;
197   station->m_initialized = false;
198 
199   return station;
200 }
201 
202 void
CheckInit(MinstrelWifiRemoteStation * station)203 MinstrelWifiManager::CheckInit (MinstrelWifiRemoteStation *station)
204 {
205   NS_LOG_FUNCTION (this << station);
206   if (!station->m_initialized && GetNSupported (station) > 1)
207     {
208       //Note: we appear to be doing late initialization of the table
209       //to make sure that the set of supported rates has been initialized
210       //before we perform our own initialization.
211       station->m_nModes = GetNSupported (station);
212       station->m_minstrelTable = MinstrelRate (station->m_nModes);
213       station->m_sampleTable = SampleRate (station->m_nModes, std::vector<uint8_t> (m_sampleCol));
214       InitSampleTable (station);
215       RateInit (station);
216       station->m_initialized = true;
217     }
218 }
219 
220 /**
221  *
222  * Retry Chain table is implemented here
223  *
224  * Try |         LOOKAROUND RATE              | NORMAL RATE
225  *     | random < best    | random > best     |
226  * --------------------------------------------------------------
227  *  1  | Best throughput  | Random rate       | Best throughput
228  *  2  | Random rate      | Best throughput   | Next best throughput
229  *  3  | Best probability | Best probability  | Best probability
230  *  4  | Lowest base rate | Lowest base rate  | Lowest base rate
231  *
232  * Note: For clarity, multiple blocks of if's and else's are used
233  * After failing max retry times, DoReportFinalDataFailed will be called
234  */
235 void
UpdateRate(MinstrelWifiRemoteStation * station)236 MinstrelWifiManager::UpdateRate (MinstrelWifiRemoteStation *station)
237 {
238   NS_LOG_FUNCTION (this << station);
239   station->m_longRetry++;
240   station->m_minstrelTable[station->m_txrate].numRateAttempt++;
241 
242   NS_LOG_DEBUG ("DoReportDataFailed " << station << " rate " << station->m_txrate << " longRetry " << station->m_longRetry);
243 
244   //for normal rate, we're not currently sampling random rates
245   if (!station->m_isSampling)
246     {
247       NS_LOG_DEBUG ("Failed with normal rate: current=" << station->m_txrate << ", sample=" << station->m_sampleRate << ", maxTp=" << station->m_maxTpRate << ", maxTp2=" << station->m_maxTpRate2 << ", maxProb=" << station->m_maxProbRate);
248       //use best throughput rate
249       if (station->m_longRetry < station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount)
250         {
251           NS_LOG_DEBUG (" More retries left for the maximum throughput rate.");
252           station->m_txrate = station->m_maxTpRate;
253         }
254 
255       //use second best throughput rate
256       else if (station->m_longRetry <= (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
257                                         station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount))
258         {
259           NS_LOG_DEBUG (" More retries left for the second maximum throughput rate.");
260           station->m_txrate = station->m_maxTpRate2;
261         }
262 
263       //use best probability rate
264       else if (station->m_longRetry <= (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
265                                         station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount +
266                                         station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount))
267         {
268           NS_LOG_DEBUG (" More retries left for the maximum probability rate.");
269           station->m_txrate = station->m_maxProbRate;
270         }
271 
272       //use lowest base rate
273       else if (station->m_longRetry > (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
274                                        station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount +
275                                        station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount))
276         {
277           NS_LOG_DEBUG (" More retries left for the base rate.");
278           station->m_txrate = 0;
279         }
280     }
281 
282   //for look-around rate, we're currently sampling random rates
283   else
284     {
285       NS_LOG_DEBUG ("Failed with look around rate: current=" << station->m_txrate << ", sample=" << station->m_sampleRate << ", maxTp=" << station->m_maxTpRate << ", maxTp2=" << station->m_maxTpRate2 << ", maxProb=" << station->m_maxProbRate);
286       //current sampling rate is slower than the current best rate
287       if (station->m_sampleDeferred)
288         {
289           NS_LOG_DEBUG ("Look around rate is slower than the maximum throughput rate.");
290           //use best throughput rate
291           if (station->m_longRetry < station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount)
292             {
293               NS_LOG_DEBUG (" More retries left for the maximum throughput rate.");
294               station->m_txrate = station->m_maxTpRate;
295             }
296 
297           //use random rate
298           else if (station->m_longRetry <= (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
299                                             station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount))
300             {
301               NS_LOG_DEBUG (" More retries left for the sampling rate.");
302               station->m_txrate = station->m_sampleRate;
303             }
304 
305           //use max probability rate
306           else if (station->m_longRetry <= (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
307                                             station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
308                                             station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount ))
309             {
310               NS_LOG_DEBUG (" More retries left for the maximum probability rate.");
311               station->m_txrate = station->m_maxProbRate;
312             }
313 
314           //use lowest base rate
315           else if (station->m_longRetry > (station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
316                                            station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
317                                            station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount))
318             {
319               NS_LOG_DEBUG (" More retries left for the base rate.");
320               station->m_txrate = 0;
321             }
322         }
323       //current sampling rate is better than current best rate
324       else
325         {
326           NS_LOG_DEBUG ("Look around rate is faster than the maximum throughput rate.");
327           //use random rate
328           if (station->m_longRetry < station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount)
329             {
330               NS_LOG_DEBUG (" More retries left for the sampling rate.");
331               station->m_txrate = station->m_sampleRate;
332             }
333 
334           //use the best throughput rate
335           else if (station->m_longRetry <= (station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
336                                             station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))
337             {
338               NS_LOG_DEBUG (" More retries left for the maximum throughput rate.");
339               station->m_txrate = station->m_maxTpRate;
340             }
341 
342           //use the best probability rate
343           else if (station->m_longRetry <= (station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
344                                             station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
345                                             station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount))
346             {
347               NS_LOG_DEBUG (" More retries left for the maximum probability rate.");
348               station->m_txrate = station->m_maxProbRate;
349             }
350 
351           //use the lowest base rate
352           else if (station->m_longRetry > (station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
353                                            station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
354                                            station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount))
355             {
356               NS_LOG_DEBUG (" More retries left for the base rate.");
357               station->m_txrate = 0;
358             }
359         }
360     }
361 }
362 
363 WifiTxVector
GetDataTxVector(MinstrelWifiRemoteStation * station)364 MinstrelWifiManager::GetDataTxVector (MinstrelWifiRemoteStation *station)
365 {
366   NS_LOG_FUNCTION (this << station);
367   uint16_t channelWidth = GetChannelWidth (station);
368   if (channelWidth > 20 && channelWidth != 22)
369     {
370       channelWidth = 20;
371     }
372   if (!station->m_initialized)
373     {
374       CheckInit (station);
375     }
376   WifiMode mode = GetSupported (station, station->m_txrate);
377   if (m_currentRate != mode.GetDataRate (channelWidth) && !station->m_isSampling)
378     {
379       NS_LOG_DEBUG ("New datarate: " << mode.GetDataRate (channelWidth));
380       m_currentRate = mode.GetDataRate (channelWidth);
381     }
382   return WifiTxVector (mode, GetDefaultTxPowerLevel (), GetPreambleForTransmission (mode.GetModulationClass (), GetShortPreambleEnabled ()), 800, 1, 1, 0, channelWidth, GetAggregation (station));
383 }
384 
385 WifiTxVector
GetRtsTxVector(MinstrelWifiRemoteStation * station)386 MinstrelWifiManager::GetRtsTxVector (MinstrelWifiRemoteStation *station)
387 {
388   NS_LOG_FUNCTION (this << station);
389   NS_LOG_DEBUG ("DoGetRtsMode m_txrate=" << station->m_txrate);
390   uint16_t channelWidth = GetChannelWidth (station);
391   if (channelWidth > 20 && channelWidth != 22)
392     {
393       channelWidth = 20;
394     }
395   WifiTxVector rtsTxVector;
396   WifiMode mode;
397   if (GetUseNonErpProtection () == false)
398     {
399       mode = GetSupported (station, 0);
400     }
401   else
402     {
403       mode = GetNonErpSupported (station, 0);
404     }
405   rtsTxVector = WifiTxVector (mode, GetDefaultTxPowerLevel (), GetPreambleForTransmission (mode.GetModulationClass (), GetShortPreambleEnabled ()), 800, 1, 1, 0, channelWidth, GetAggregation (station));
406   return rtsTxVector;
407 }
408 
409 uint32_t
CountRetries(MinstrelWifiRemoteStation * station)410 MinstrelWifiManager::CountRetries (MinstrelWifiRemoteStation *station)
411 {
412   if (!station->m_isSampling)
413     {
414       return station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
415              station->m_minstrelTable[station->m_maxTpRate2].adjustedRetryCount +
416              station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount +
417              station->m_minstrelTable[0].adjustedRetryCount;
418     }
419   else
420     {
421       return station->m_minstrelTable[station->m_sampleRate].adjustedRetryCount +
422              station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount +
423              station->m_minstrelTable[station->m_maxProbRate].adjustedRetryCount +
424              station->m_minstrelTable[0].adjustedRetryCount;
425     }
426 }
427 
428 uint16_t
FindRate(MinstrelWifiRemoteStation * station)429 MinstrelWifiManager::FindRate (MinstrelWifiRemoteStation *station)
430 {
431   NS_LOG_FUNCTION (this << station);
432 
433   if (station->m_totalPacketsCount == 0)
434     {
435       return 0;
436     }
437 
438   uint16_t idx = 0;
439   NS_LOG_DEBUG ("Total: " << station->m_totalPacketsCount << "  Sample: " << station->m_samplePacketsCount << "  Deferred: " << station->m_numSamplesDeferred);
440 
441   int delta = (station->m_totalPacketsCount * m_lookAroundRate / 100) - (station->m_samplePacketsCount + station->m_numSamplesDeferred / 2);
442 
443   NS_LOG_DEBUG ("Decide sampling. Delta: " << delta << " lookAroundRatio: " <<  m_lookAroundRate);
444 
445   /* delta < 0: no sampling required */
446   if (delta >= 0)
447     {
448       NS_LOG_DEBUG ("Search next sampling rate");
449       uint8_t ratesSupported = station->m_nModes;
450       if (delta > ratesSupported * 2)
451         {
452           /* From Linux implementation:
453            * With multi-rate retry, not every planned sample
454            * attempt actually gets used, due to the way the retry
455            * chain is set up - [max_tp,sample,prob,lowest] for
456            * sample_rate < max_tp.
457            *
458            * If there's too much sampling backlog and the link
459            * starts getting worse, minstrel would start bursting
460            * out lots of sampling frames, which would result
461            * in a large throughput loss. */
462           station->m_samplePacketsCount += (delta - ratesSupported * 2);
463         }
464 
465       //now go through the table and find an index rate
466       idx = GetNextSample (station);
467 
468       NS_LOG_DEBUG ("Sample rate = " << idx << "(" << GetSupported (station, idx) << ")");
469 
470       //error check
471       if (idx >= station->m_nModes)
472         {
473           NS_LOG_DEBUG ("ALERT!!! ERROR");
474         }
475 
476       //set the rate that we're currently sampling
477       station->m_sampleRate = idx;
478 
479       /* From Linux implementation:
480        * Decide if direct ( 1st MRR stage) or indirect (2nd MRR stage)
481        * rate sampling method should be used.
482        * Respect such rates that are not sampled for 20 iterations.
483        */
484       if ((station->m_minstrelTable[idx].perfectTxTime > station->m_minstrelTable[station->m_maxTpRate].perfectTxTime)
485           && (station->m_minstrelTable[idx].numSamplesSkipped < 20))
486         {
487           // If the rate is slower and we have sample it enough, defer to second stage
488           station->m_sampleDeferred = true;
489           station->m_numSamplesDeferred++;
490 
491           //set flag that we are currently sampling
492           station->m_isSampling = true;
493         }
494       else
495         {
496           // if samplieLimit is zero, then don't sample this rate
497           if (!station->m_minstrelTable[idx].sampleLimit)
498             {
499               idx = station->m_maxTpRate;
500               station->m_isSampling = false;
501             }
502           else
503             {
504               //set flag that we are currently sampling
505               station->m_isSampling = true;
506               if (station->m_minstrelTable[idx].sampleLimit > 0)
507                 {
508                   station->m_minstrelTable[idx].sampleLimit--;
509                 }
510             }
511         }
512 
513       //using the best rate instead
514       if (station->m_sampleDeferred)
515         {
516           NS_LOG_DEBUG ("The next look around rate is slower than the maximum throughput rate, continue with the maximum throughput rate: " << station->m_maxTpRate << "(" << GetSupported (station, station->m_maxTpRate) << ")");
517           idx = station->m_maxTpRate;
518         }
519     }
520   //continue using the best rate
521   else
522     {
523       NS_LOG_DEBUG ("Continue using the maximum throughput rate: " << station->m_maxTpRate << "(" << GetSupported (station, station->m_maxTpRate) << ")");
524       idx = station->m_maxTpRate;
525     }
526 
527   NS_LOG_DEBUG ("Rate = " << idx << "(" << GetSupported (station, idx) << ")");
528 
529   return idx;
530 }
531 
532 void
UpdateStats(MinstrelWifiRemoteStation * station)533 MinstrelWifiManager::UpdateStats (MinstrelWifiRemoteStation *station)
534 {
535   NS_LOG_FUNCTION (this << station);
536   if (Simulator::Now () <  station->m_nextStatsUpdate)
537     {
538       return;
539     }
540 
541   if (!station->m_initialized)
542     {
543       return;
544     }
545   NS_LOG_FUNCTION (this);
546   station->m_nextStatsUpdate = Simulator::Now () + m_updateStats;
547   NS_LOG_DEBUG ("Next update at " << station->m_nextStatsUpdate);
548   NS_LOG_DEBUG ("Currently using rate: " << station->m_txrate << " (" << GetSupported (station, station->m_txrate) << ")");
549 
550   Time txTime;
551   uint32_t tempProb;
552 
553   NS_LOG_DEBUG ("Index-Rate\t\tAttempt\tSuccess");
554   for (uint8_t i = 0; i < station->m_nModes; i++)
555     {
556 
557       //calculate the perfect TX time for this rate
558       txTime = station->m_minstrelTable[i].perfectTxTime;
559 
560       //just for initialization
561       if (txTime.GetMicroSeconds () == 0)
562         {
563           txTime = Seconds (1);
564         }
565 
566       NS_LOG_DEBUG (+i << " " << GetSupported (station, i) <<
567                     "\t" << station->m_minstrelTable[i].numRateAttempt <<
568                     "\t" << station->m_minstrelTable[i].numRateSuccess);
569 
570       //if we've attempted something
571       if (station->m_minstrelTable[i].numRateAttempt)
572         {
573           station->m_minstrelTable[i].numSamplesSkipped = 0;
574           /**
575            * calculate the probability of success
576            * assume probability scales from 0 to 18000
577            */
578           tempProb = (station->m_minstrelTable[i].numRateSuccess * 18000) / station->m_minstrelTable[i].numRateAttempt;
579 
580           //bookkeeping
581           station->m_minstrelTable[i].prob = tempProb;
582 
583           if (station->m_minstrelTable[i].successHist == 0)
584             {
585               station->m_minstrelTable[i].ewmaProb = tempProb;
586             }
587           else
588             {
589               //EWMA probability (cast for gcc 3.4 compatibility)
590               tempProb = ((tempProb * (100 - m_ewmaLevel)) + (station->m_minstrelTable[i].ewmaProb * m_ewmaLevel) ) / 100;
591 
592               station->m_minstrelTable[i].ewmaProb = tempProb;
593             }
594 
595           //calculating throughput
596           station->m_minstrelTable[i].throughput = tempProb * static_cast<uint32_t> ((1000000 / txTime.GetMicroSeconds ()));
597         }
598       else
599         {
600           station->m_minstrelTable[i].numSamplesSkipped++;
601         }
602 
603       //bookkeeping
604       station->m_minstrelTable[i].successHist += station->m_minstrelTable[i].numRateSuccess;
605       station->m_minstrelTable[i].attemptHist += station->m_minstrelTable[i].numRateAttempt;
606       station->m_minstrelTable[i].prevNumRateSuccess = station->m_minstrelTable[i].numRateSuccess;
607       station->m_minstrelTable[i].prevNumRateAttempt = station->m_minstrelTable[i].numRateAttempt;
608       station->m_minstrelTable[i].numRateSuccess = 0;
609       station->m_minstrelTable[i].numRateAttempt = 0;
610 
611       //Sample less often below 10% and  above 95% of success
612       if ((station->m_minstrelTable[i].ewmaProb > 17100) || (station->m_minstrelTable[i].ewmaProb < 1800))
613         {
614           /**
615            * See: http://wireless.kernel.org/en/developers/Documentation/mac80211/RateControl/minstrel/
616            *
617            * Analysis of information showed that the system was sampling too hard at some rates.
618            * For those rates that never work (54mb, 500m range) there is no point in retrying 10 sample packets (< 6 ms time).
619            * Consequently, for the very low probability rates, we try at most twice when fails and not sample more than 4 times.
620            */
621           if (station->m_minstrelTable[i].retryCount > 2)
622             {
623               station->m_minstrelTable[i].adjustedRetryCount = 2;
624             }
625           station->m_minstrelTable[i].sampleLimit = 4;
626         }
627       else
628         {
629           // no sampling limit.
630           station->m_minstrelTable[i].sampleLimit = -1;
631           station->m_minstrelTable[i].adjustedRetryCount = station->m_minstrelTable[i].retryCount;
632         }
633 
634       //if it's 0 allow two retries.
635       if (station->m_minstrelTable[i].adjustedRetryCount == 0)
636         {
637           station->m_minstrelTable[i].adjustedRetryCount = 2;
638         }
639     }
640 
641   NS_LOG_DEBUG ("Attempt/success reset to 0");
642 
643   uint32_t max_tp = 0;
644   uint8_t index_max_tp = 0, index_max_tp2 = 0;
645 
646   //go find max throughput, second maximum throughput, high probability of success
647   NS_LOG_DEBUG ("Finding the maximum throughput, second maximum throughput, and highest probability");
648   NS_LOG_DEBUG ("Index-Rate\t\tT-put\tEWMA");
649   for (uint8_t i = 0; i < station->m_nModes; i++)
650     {
651       NS_LOG_DEBUG (+i << " " << GetSupported (station, i) <<
652                     "\t" << station->m_minstrelTable[i].throughput <<
653                     "\t" << station->m_minstrelTable[i].ewmaProb);
654 
655       if (max_tp < station->m_minstrelTable[i].throughput)
656         {
657           index_max_tp = i;
658           max_tp = station->m_minstrelTable[i].throughput;
659         }
660     }
661 
662   max_tp = 0;
663   //find the second highest max
664   for (uint8_t i = 0; i < station->m_nModes; i++)
665     {
666       if ((i != index_max_tp) && (max_tp < station->m_minstrelTable[i].throughput))
667         {
668           index_max_tp2 = i;
669           max_tp = station->m_minstrelTable[i].throughput;
670         }
671     }
672 
673   uint32_t max_prob = 0;
674   uint8_t index_max_prob = 0;
675   for (uint8_t i = 0; i < station->m_nModes; i++)
676     {
677       if ((station->m_minstrelTable[i].ewmaProb >= 95 * 180) && (station->m_minstrelTable[i].throughput >= station->m_minstrelTable[index_max_prob].throughput))
678         {
679           index_max_prob = i;
680           max_prob = station->m_minstrelTable[i].ewmaProb;
681         }
682       else if (station->m_minstrelTable[i].ewmaProb >= max_prob)
683         {
684           index_max_prob = i;
685           max_prob = station->m_minstrelTable[i].ewmaProb;
686         }
687     }
688 
689   station->m_maxTpRate = index_max_tp;
690   station->m_maxTpRate2 = index_max_tp2;
691   station->m_maxProbRate = index_max_prob;
692 
693   if (index_max_tp > station->m_txrate)
694     {
695       station->m_txrate = index_max_tp;
696     }
697 
698   NS_LOG_DEBUG ("max throughput=" << +index_max_tp << "(" << GetSupported (station, index_max_tp) <<
699                 ")\tsecond max throughput=" << +index_max_tp2 << "(" << GetSupported (station, index_max_tp2) <<
700                 ")\tmax prob=" << +index_max_prob << "(" << GetSupported (station, index_max_prob) << ")");
701   if (m_printStats)
702     {
703       PrintTable (station);
704     }
705   if (m_printSamples)
706     {
707       PrintSampleTable (station);
708     }
709 }
710 
711 void
DoReportRxOk(WifiRemoteStation * st,double rxSnr,WifiMode txMode)712 MinstrelWifiManager::DoReportRxOk (WifiRemoteStation *st, double rxSnr, WifiMode txMode)
713 {
714   NS_LOG_FUNCTION (this << st << rxSnr << txMode);
715   NS_LOG_DEBUG ("DoReportRxOk m_txrate=" << static_cast<MinstrelWifiRemoteStation*> (st)->m_txrate);
716 }
717 
718 void
DoReportRtsFailed(WifiRemoteStation * st)719 MinstrelWifiManager::DoReportRtsFailed (WifiRemoteStation *st)
720 {
721   NS_LOG_FUNCTION (this << st);
722   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
723   NS_LOG_DEBUG ("DoReportRtsFailed m_txrate=" << station->m_txrate);
724   station->m_shortRetry++;
725 }
726 
727 void
DoReportRtsOk(WifiRemoteStation * st,double ctsSnr,WifiMode ctsMode,double rtsSnr)728 MinstrelWifiManager::DoReportRtsOk (WifiRemoteStation *st, double ctsSnr, WifiMode ctsMode, double rtsSnr)
729 {
730   NS_LOG_FUNCTION (this << st << ctsSnr << ctsMode << rtsSnr);
731 }
732 
733 void
DoReportFinalRtsFailed(WifiRemoteStation * st)734 MinstrelWifiManager::DoReportFinalRtsFailed (WifiRemoteStation *st)
735 {
736   NS_LOG_FUNCTION (this << st);
737   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
738   UpdateRetry (station);
739 }
740 
741 void
DoReportDataFailed(WifiRemoteStation * st)742 MinstrelWifiManager::DoReportDataFailed (WifiRemoteStation *st)
743 {
744   NS_LOG_FUNCTION (this << st);
745   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
746   NS_LOG_DEBUG ("DoReportDataFailed " << station << "\t rate " << station->m_txrate << "\tlongRetry \t" << station->m_longRetry);
747   CheckInit (station);
748   if (!station->m_initialized)
749     {
750       return;
751     }
752 
753   UpdateRate (station);
754 }
755 
756 void
DoReportDataOk(WifiRemoteStation * st,double ackSnr,WifiMode ackMode,double dataSnr,uint16_t dataChannelWidth,uint8_t dataNss)757 MinstrelWifiManager::DoReportDataOk (WifiRemoteStation *st, double ackSnr, WifiMode ackMode,
758                                      double dataSnr, uint16_t dataChannelWidth, uint8_t dataNss)
759 {
760   NS_LOG_FUNCTION (this << st << ackSnr << ackMode << dataSnr << dataChannelWidth << +dataNss);
761   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
762 
763   CheckInit (station);
764   if (!station->m_initialized)
765     {
766       return;
767     }
768 
769   NS_LOG_DEBUG ("DoReportDataOk m_txrate = " << station->m_txrate << ", attempt = " << station->m_minstrelTable[station->m_txrate].numRateAttempt << ", success = " << station->m_minstrelTable[station->m_txrate].numRateSuccess << " (before update).");
770 
771   station->m_minstrelTable[station->m_txrate].numRateSuccess++;
772   station->m_minstrelTable[station->m_txrate].numRateAttempt++;
773 
774   UpdatePacketCounters (station);
775 
776   NS_LOG_DEBUG ("DoReportDataOk m_txrate = " << station->m_txrate << ", attempt = " << station->m_minstrelTable[station->m_txrate].numRateAttempt << ", success = " << station->m_minstrelTable[station->m_txrate].numRateSuccess << " (after update).");
777 
778   UpdateRetry (station);
779   UpdateStats (station);
780 
781   if (station->m_nModes >= 1)
782     {
783       station->m_txrate = FindRate (station);
784     }
785   NS_LOG_DEBUG ("Next rate to use TxRate = " << station->m_txrate);
786 }
787 
788 void
DoReportFinalDataFailed(WifiRemoteStation * st)789 MinstrelWifiManager::DoReportFinalDataFailed (WifiRemoteStation *st)
790 {
791   NS_LOG_FUNCTION (this << st);
792   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
793 
794   CheckInit (station);
795   if (!station->m_initialized)
796     {
797       return;
798     }
799 
800   NS_LOG_DEBUG ("DoReportFinalDataFailed m_txrate = " << station->m_txrate << ", attempt = " << station->m_minstrelTable[station->m_txrate].numRateAttempt << ", success = " << station->m_minstrelTable[station->m_txrate].numRateSuccess << " (before update).");
801 
802   UpdatePacketCounters (station);
803 
804   UpdateRetry (station);
805   UpdateStats (station);
806 
807   NS_LOG_DEBUG ("DoReportFinalDataFailed m_txrate = " << station->m_txrate << ", attempt = " << station->m_minstrelTable[station->m_txrate].numRateAttempt << ", success = " << station->m_minstrelTable[station->m_txrate].numRateSuccess << " (after update).");
808 
809   if (station->m_nModes >= 1)
810     {
811       station->m_txrate = FindRate (station);
812     }
813   NS_LOG_DEBUG ("Next rate to use TxRate = " << station->m_txrate);
814 }
815 
816 void
UpdatePacketCounters(MinstrelWifiRemoteStation * station)817 MinstrelWifiManager::UpdatePacketCounters (MinstrelWifiRemoteStation *station)
818 {
819   NS_LOG_FUNCTION (this << station);
820 
821   station->m_totalPacketsCount++;
822   // If it is a sampling frame and the sampleRate was used, increase counter
823   if (station->m_isSampling && (!station->m_sampleDeferred || station->m_longRetry >= station->m_minstrelTable[station->m_maxTpRate].adjustedRetryCount))
824     {
825       station->m_samplePacketsCount++;
826     }
827 
828   if (station->m_numSamplesDeferred > 0)
829     {
830       station->m_numSamplesDeferred--;
831     }
832 
833   if (station->m_totalPacketsCount == ~0)
834     {
835       station->m_numSamplesDeferred = 0;
836       station->m_samplePacketsCount = 0;
837       station->m_totalPacketsCount = 0;
838     }
839   station->m_isSampling = false;
840   station->m_sampleDeferred = false;
841 }
842 
843 void
UpdateRetry(MinstrelWifiRemoteStation * station)844 MinstrelWifiManager::UpdateRetry (MinstrelWifiRemoteStation *station)
845 {
846   NS_LOG_FUNCTION (this << station);
847   station->m_retry = station->m_shortRetry + station->m_longRetry;
848   station->m_shortRetry = 0;
849   station->m_longRetry = 0;
850 }
851 
852 WifiTxVector
DoGetDataTxVector(WifiRemoteStation * st)853 MinstrelWifiManager::DoGetDataTxVector (WifiRemoteStation *st)
854 {
855   NS_LOG_FUNCTION (this << st);
856   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
857   return GetDataTxVector (station);
858 }
859 
860 WifiTxVector
DoGetRtsTxVector(WifiRemoteStation * st)861 MinstrelWifiManager::DoGetRtsTxVector (WifiRemoteStation *st)
862 {
863   NS_LOG_FUNCTION (this << st);
864   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
865   return GetRtsTxVector (station);
866 }
867 
868 bool
DoNeedRetransmission(WifiRemoteStation * st,Ptr<const Packet> packet,bool normally)869 MinstrelWifiManager::DoNeedRetransmission (WifiRemoteStation *st, Ptr<const Packet> packet, bool normally)
870 {
871   NS_LOG_FUNCTION (this << st << packet << normally);
872   MinstrelWifiRemoteStation *station = static_cast<MinstrelWifiRemoteStation*> (st);
873 
874   CheckInit (station);
875   if (!station->m_initialized)
876     {
877       return normally;
878     }
879   if (station->m_longRetry >= CountRetries (station))
880     {
881       NS_LOG_DEBUG ("No re-transmission allowed. Retries: " <<  station->m_longRetry << " Max retries: " << CountRetries (station));
882       return false;
883     }
884   else
885     {
886       NS_LOG_DEBUG ("Re-transmit. Retries: " <<  station->m_longRetry << " Max retries: " << CountRetries (station));
887       return true;
888     }
889 }
890 
891 uint16_t
GetNextSample(MinstrelWifiRemoteStation * station)892 MinstrelWifiManager::GetNextSample (MinstrelWifiRemoteStation *station)
893 {
894   NS_LOG_FUNCTION (this << station);
895   uint16_t bitrate;
896   bitrate = station->m_sampleTable[station->m_index][station->m_col];
897   station->m_index++;
898 
899   //bookkeeping for m_index and m_col variables
900   NS_ABORT_MSG_IF (station->m_nModes < 2, "Integer overflow detected");
901   if (station->m_index > station->m_nModes - 2)
902     {
903       station->m_index = 0;
904       station->m_col++;
905       if (station->m_col >= m_sampleCol)
906         {
907           station->m_col = 0;
908         }
909     }
910   return bitrate;
911 }
912 
913 void
RateInit(MinstrelWifiRemoteStation * station)914 MinstrelWifiManager::RateInit (MinstrelWifiRemoteStation *station)
915 {
916   NS_LOG_FUNCTION (this << station);
917   for (uint8_t i = 0; i < station->m_nModes; i++)
918     {
919       NS_LOG_DEBUG ("Initializing rate index " << +i << " " << GetSupported (station, i));
920       station->m_minstrelTable[i].numRateAttempt = 0;
921       station->m_minstrelTable[i].numRateSuccess = 0;
922       station->m_minstrelTable[i].prevNumRateSuccess = 0;
923       station->m_minstrelTable[i].prevNumRateAttempt = 0;
924       station->m_minstrelTable[i].successHist = 0;
925       station->m_minstrelTable[i].attemptHist = 0;
926       station->m_minstrelTable[i].numSamplesSkipped = 0;
927       station->m_minstrelTable[i].prob = 0;
928       station->m_minstrelTable[i].ewmaProb = 0;
929       station->m_minstrelTable[i].throughput = 0;
930       station->m_minstrelTable[i].perfectTxTime = GetCalcTxTime (GetSupported (station, i));
931       NS_LOG_DEBUG (" perfectTxTime = " << station->m_minstrelTable[i].perfectTxTime);
932       station->m_minstrelTable[i].retryCount = 1;
933       station->m_minstrelTable[i].adjustedRetryCount = 1;
934       //Emulating minstrel.c::ath_rate_ctl_reset
935       //We only check from 2 to 10 retries. This guarantee that
936       //at least one retry is permitted.
937       Time totalTxTimeWithGivenRetries = Seconds (0.0); //tx_time in minstrel.c
938       NS_LOG_DEBUG (" Calculating the number of retries");
939       for (uint32_t retries = 2; retries < 11; retries++)
940         {
941           NS_LOG_DEBUG ("  Checking " << retries << " retries");
942           totalTxTimeWithGivenRetries = CalculateTimeUnicastPacket (station->m_minstrelTable[i].perfectTxTime, 0, retries);
943           NS_LOG_DEBUG ("   totalTxTimeWithGivenRetries = " << totalTxTimeWithGivenRetries);
944           if (totalTxTimeWithGivenRetries > MilliSeconds (6))
945             {
946               break;
947             }
948           station->m_minstrelTable[i].sampleLimit = -1;
949           station->m_minstrelTable[i].retryCount = retries;
950           station->m_minstrelTable[i].adjustedRetryCount = retries;
951         }
952     }
953   UpdateStats (station);
954 }
955 
956 Time
CalculateTimeUnicastPacket(Time dataTransmissionTime,uint32_t shortRetries,uint32_t longRetries)957 MinstrelWifiManager::CalculateTimeUnicastPacket (Time dataTransmissionTime, uint32_t shortRetries, uint32_t longRetries)
958 {
959   NS_LOG_FUNCTION (this << dataTransmissionTime << shortRetries << longRetries);
960   //See rc80211_minstrel.c
961 
962   //First transmission (Data + Ack timeout)
963   Time tt = dataTransmissionTime + GetPhy ()->GetSifs () + GetPhy ()->GetAckTxTime ();
964 
965   uint32_t cwMax = 1023;
966   uint32_t cw = 31;
967   for (uint32_t retry = 0; retry < longRetries; retry++)
968     {
969       //Add one re-transmission (Data + Ack timeout)
970       tt += dataTransmissionTime + GetPhy ()->GetSifs () + GetPhy ()->GetAckTxTime ();
971 
972       //Add average back off (half the current contention window)
973       tt += (cw / 2.0) * GetPhy ()->GetSlot ();
974 
975       //Update contention window
976       cw = std::min (cwMax, (cw + 1) * 2);
977     }
978 
979   return tt;
980 }
981 
982 void
InitSampleTable(MinstrelWifiRemoteStation * station)983 MinstrelWifiManager::InitSampleTable (MinstrelWifiRemoteStation *station)
984 {
985   NS_LOG_FUNCTION (this << station);
986   station->m_col = station->m_index = 0;
987 
988   //for off-setting to make rates fall between 0 and nModes
989   uint8_t numSampleRates = station->m_nModes;
990 
991   uint16_t newIndex;
992   for (uint8_t col = 0; col < m_sampleCol; col++)
993     {
994       for (uint8_t i = 0; i < numSampleRates; i++ )
995         {
996           /**
997            * The next two lines basically tries to generate a random number
998            * between 0 and the number of available rates
999            */
1000           int uv = m_uniformRandomVariable->GetInteger (0, numSampleRates);
1001           NS_LOG_DEBUG ("InitSampleTable uv: " << uv);
1002           newIndex = (i + uv) % numSampleRates;
1003 
1004           //this loop is used for filling in other uninitialized places
1005           while (station->m_sampleTable[newIndex][col] != 0)
1006             {
1007               newIndex = (newIndex + 1) % station->m_nModes;
1008             }
1009           station->m_sampleTable[newIndex][col] = i;
1010         }
1011     }
1012 }
1013 
1014 void
PrintSampleTable(MinstrelWifiRemoteStation * station)1015 MinstrelWifiManager::PrintSampleTable (MinstrelWifiRemoteStation *station)
1016 {
1017   uint8_t numSampleRates = station->m_nModes;
1018   std::stringstream table;
1019   for (uint8_t i = 0; i < numSampleRates; i++)
1020     {
1021       for (uint8_t j = 0; j < m_sampleCol; j++)
1022         {
1023           table << station->m_sampleTable[i][j] << "\t";
1024         }
1025       table << std::endl;
1026     }
1027   NS_LOG_DEBUG (table.str ());
1028 }
1029 
1030 void
PrintTable(MinstrelWifiRemoteStation * station)1031 MinstrelWifiManager::PrintTable (MinstrelWifiRemoteStation *station)
1032 {
1033   if (!station->m_statsFile.is_open ())
1034     {
1035       std::ostringstream tmp;
1036       tmp << "minstrel-stats-" << station->m_state->m_address << ".txt";
1037       station->m_statsFile.open (tmp.str ().c_str (), std::ios::out);
1038     }
1039 
1040   station->m_statsFile << "best   _______________rate________________    ________statistics________    ________last_______    ______sum-of________\n" <<
1041     "rate  [      name       idx airtime max_tp]  [avg(tp) avg(prob) sd(prob)]  [prob.|retry|suc|att]  [#success | #attempts]\n";
1042 
1043   uint16_t maxTpRate = station->m_maxTpRate;
1044   uint16_t maxTpRate2 = station->m_maxTpRate2;
1045   uint16_t maxProbRate = station->m_maxProbRate;
1046 
1047   for (uint8_t i = 0; i < station->m_nModes; i++)
1048     {
1049       RateInfo rate = station->m_minstrelTable[i];
1050 
1051       if (i == maxTpRate)
1052         {
1053           station->m_statsFile << 'A';
1054         }
1055       else
1056         {
1057           station->m_statsFile << ' ';
1058         }
1059       if (i == maxTpRate2)
1060         {
1061           station->m_statsFile << 'B';
1062         }
1063       else
1064         {
1065           station->m_statsFile << ' ';
1066         }
1067       if (i == maxProbRate)
1068         {
1069           station->m_statsFile << 'P';
1070         }
1071       else
1072         {
1073           station->m_statsFile << ' ';
1074         }
1075 
1076       float tmpTh = rate.throughput / 100000.0f;
1077       station->m_statsFile << "   " <<
1078         std::setw (17) << GetSupported (station, i) << "  " <<
1079         std::setw (2) << i << "  " <<
1080         std::setw (4) << rate.perfectTxTime.GetMicroSeconds () <<
1081         std::setw (8) << "    -----    " <<
1082         std::setw (8) << tmpTh << "    " <<
1083         std::setw (3) << rate.ewmaProb / 180 <<
1084         std::setw (3) << "       ---      " <<
1085         std::setw (3) << rate.prob / 180 << "     " <<
1086         std::setw (1) << rate.adjustedRetryCount << "   " <<
1087         std::setw (3) << rate.prevNumRateSuccess << " " <<
1088         std::setw (3) << rate.prevNumRateAttempt << "   " <<
1089         std::setw (9) << rate.successHist << "   " <<
1090         std::setw (9) << rate.attemptHist << "\n";
1091     }
1092   station->m_statsFile << "\nTotal packet count:    ideal " << station->m_totalPacketsCount - station->m_samplePacketsCount
1093                        << "      lookaround " << station->m_samplePacketsCount << "\n\n";
1094 
1095   station->m_statsFile.flush ();
1096 }
1097 
1098 } //namespace ns3
1099