src/surf/ns3/red-queue.h

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