src/surf/ns3/red-queue.h

   1 /* Copyright (c) 2011, 2014. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 /*
   8  * Copyright (c) 2010 Regents of the University of California
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation;
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  *
  23  * Author: Duy Nguyen<duy@soe.ucsc.edu>
  24  *
  25  * Random Early Detection (RED) algorithm.
  26  *
  27  * This implementation uses Bytes as queue size metric by default
  28  * based on the Kuznetsov's implementation of Red in Linux.
  29  * Therefore, only bytes as queue size metric is supported at the moment.
  30  *
  31  * Original RED is from
  32  * Sally Floyd and Van Jacobson, "Random Early Detection Gateways for
  33  * Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking
  34  *
  35  * Description:
  36  *
  37  * Packet arrival:
  38  * avg = (1-W)*avg + W*currentQueueLen
  39  * W is the queue weight( chosen as 2^(-Wlog)).  Decrease W for larger bursts
  40  *
  41  * if ( avg > maxTh) -> mark/drop packets
  42  * if ( avg < minTh) -> allow packets
  43  * if ( minTh < avg < maxTh) -> calculate probability for marking/dropping
  44  *
  45  *
  46  * Pb = maxP*(avg - minTh)/(maxTh - minTh)
  47  * Note: As avg varies from minTh to maxTh, Pb varies 0 to maxP
  48  *
  49  * Pa = Pb /(1 - count*Pb)
  50  * The final marking probability Pa increases slowly as the count increases
  51  * since the last marked packet
  52  *
  53  * maxP can be chosen s/t:
  54  * maxP = (maxTh - minTh )/2^Plog
  55  *
  56  * To allow large bursts of L packets of size S, W can be chosen as:
  57  * (see paper for details)
  58  *
  59  * L + 1 - minTh/S < (1-(1-W)^L)/W
  60  *
  61  *
  62  * Some parameters:
  63  * W = 0.002
  64  * maxP = .02
  65  *
  66  *
  67  */
  68
  69 #ifndef RED_QUEUE_H
  70 #define RED_QUEUE_H
  71
  72 #include <queue>
  73 #include "ns3/packet.h"
  74 #include "ns3/queue.h"
  75 #include "ns3/nstime.h"
  76
  77 namespace ns3 {
  78
  79 class TraceContainer;
  80
  81 /**
  82  * \ingroup queue
  83  *
  84  * \brief A RED packet queue
  85  */
  86 class RedQueue : public Queue
  87 {
  88 public:
  89   typedef std::vector< uint32_t> Uint32tVector;
  90
  91   struct Stats
  92   {
  93     uint32_t probDrop;  ///< Early probability drops
  94     uint32_t probMark;  ///< Early probability marks
  95     uint32_t forcedDrop;  ///< Forced drops, qavg > max threshold
  96     uint32_t forcedMark;  ///< Forced marks, qavg > max threshold
  97     uint32_t pdrop;  ///< Drops due to queue limits
  98     uint32_t other;  ///< Drops due to drop calls
  99     uint32_t backlog;
 100   };
 101
 102   static TypeId GetTypeId (void);
 103   /**
 104    * \brief RedQueue Constructor
 105    *
 106    */
 107   RedQueue ();
 108
 109   virtual ~RedQueue ();
 110
 111   /**
 112    * Enumeration of the modes supported in the class.
 113    *
 114    */
 115   enum Mode
 116   {
 117     ILLEGAL,     /**< Mode not set */
 118     PACKETS,     /**< Use number of packets for maximum queue size */
 119     BYTES,       /**< Use number of bytes for maximum queue size */
 120   };
 121
 122   /**
 123    * Enumeration of RED thresholds
 124    *
 125    */
 126   enum
 127   {
 128     BELOW_MIN_THRESH,
 129     ABOVE_MAX_THRESH,
 130     BETWEEN_THRESH,
 131   };
 132
 133   /**
 134    * Enumeration Marking
 135    *
 136    */
 137   enum
 138   {
 139     DONT_MARK,
 140     PROB_MARK,
 141     HARD_MARK,
 142   };
 143
 144   /**
 145    * Set the operating mode of this device.
 146    *
 147    * \param mode The operating mode of this device.
 148    *
 149    */
 150   void SetMode (RedQueue::Mode mode);
 151
 152   /**
 153    * Get the encapsulation mode of this device.
 154    *
 155    * \returns The encapsulation mode of this device.
 156    */
 157   RedQueue::Mode  GetMode (void);
 158
 159  /**
 160    * Get the average queue size
 161    *
 162    * \returns The average queue size in bytes
 163    */
 164   uint64_t GetAverageQueueSize (void);
 165
 166
 167 private:
 168   void SetParams (uint32_t minTh, uint32_t maxTh,
 169                   uint32_t wLog, uint32_t pLog, uint64_t scellLog );
 170   void StartIdlePeriod ();
 171   void EndIdlePeriod ();
 172   void Restart ();
 173   void printRedOpt ();
 174   void printStats ();
 175   void PrintTable ();
 176
 177   int IsIdling ();
 178   int CheckThresh (uint64_t avg);
 179   int Processing (uint64_t avg);
 180   int MarkProbability (uint64_t avg);
 181   int DropPacket (Ptr<Packet> p);
 182
 183   uint64_t AvgFromIdleTime ();
 184   uint64_t AvgCalc (uint32_t backlog);
 185
 186   ///< Avg = Avg*(1-W) + backlog*W
 187   uint64_t AvgFromNonIdleTime (uint32_t backlog);
 188
 189   ///< burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
 190   ///< this low-pass filter is used to calculate the avg queue size
 191   uint32_t evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt);
 192
 193   ///< Plog = log (prob / (qMax - qMin))
 194   uint32_t evalP (uint32_t minTh, uint32_t maxTh, double prob);
 195
 196   ///< -log(1-W) * t/TxTime
 197   uint32_t evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t rate);
 198
 199   uint32_t Rmask (uint32_t pLog);
 200   uint32_t RedRandom ();
 201
 202   virtual bool DoEnqueue (Ptr<Packet> p);
 203   virtual Ptr<Packet> DoDequeue (void);
 204   virtual Ptr<const Packet> DoPeek (void) const;
 205
 206
 207   std::list<Ptr<Packet> > m_packets;
 208
 209   Mode     m_mode;
 210
 211   uint32_t m_bytesInQueue;
 212
 213   ///< users' configurable options
 214   uint32_t m_maxPackets;
 215   uint32_t m_maxBytes;
 216   uint32_t m_burst;
 217
 218   /**
 219    * in bytes, use with burst to determine the time constant
 220    * for average queue size calculations, for ewma
 221    */
 222   uint32_t m_avPkt;
 223   uint32_t m_minTh; ///> Min avg length threshold (bytes), should be < maxTh/2
 224   uint32_t m_maxTh; ///> Max avg length threshold (bytes), should be >= 2*minTh
 225   uint32_t m_rate; ///> bandwidth in bps
 226   uint32_t m_wLog; ///> log(W) bits
 227   uint32_t m_pLog; ///> random number bits log (P_max/(maxTh - minTh))
 228   uint32_t m_rmask;
 229   uint32_t m_scellLog; ///> cell size for idle damping
 230   uint64_t m_scellMax;
 231   uint32_t m_count;  ///> number of packets since last random number generation
 232   uint32_t m_randNum; ///> a random number 0 ...2^Plog
 233
 234   uint64_t m_qavg; ///> average q length
 235   double m_prob;
 236   bool m_initialized;
 237
 238   Stats m_stats;
 239   Time m_idleStart; ///> start of current idle period
 240   Uint32tVector m_sTable;
 241 };
 242
 243 }; // namespace ns3
 244
 245 #endif /* RED_QUEUE_H */