+++ /dev/null
-/* Copyright (c) 2011, 2014. The SimGrid Team.
- * All rights reserved. */
-
-/* This program is free software; you can redistribute it and/or modify it
- * under the terms of the license (GNU LGPL) which comes with this package. */
-
-/*
- * Copyright (c) 2010 Regents of the University of California
- *
- * 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>
- *
- */
-
-#include "ns3/enum.h"
-#include "ns3/uinteger.h"
-#include "ns3/double.h"
-#include "red-queue.h"
-#include "ns3/simulator.h"
-#include "ns3/nstime.h"
-
-#include <cstdlib>
-
-#define RED_STATS_TABLE_SIZE 256
-#define RED_STATS_MASK (RED_STATS_TABLE_SIZE - 1)
-
-namespace ns3 {
-
-NS_OBJECT_ENSURE_REGISTERED (RedQueue);
-
-TypeId RedQueue::GetTypeId (void)
-{
- ///< Note: these parameters must be worked out beforehand for RED to work correctly
- ///< How these parameters are set up can affect RED performance greatly
- static TypeId tid = TypeId ("ns3::RedQueue")
- .SetParent<Queue> ()
- .AddConstructor<RedQueue> ()
- .AddAttribute ("Mode",
- "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
- EnumValue (BYTES), ///> currently supports BYTES only
- MakeEnumAccessor (&RedQueue::SetMode),
- MakeEnumChecker (BYTES, "Bytes",
- PACKETS, "Packets"))
- .AddAttribute ("MaxPackets",
- "The maximum number of packets accepted by this RedQueue.",
- UintegerValue (100),
- MakeUintegerAccessor (&RedQueue::m_maxPackets),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("MaxBytes",
- "The maximum number of bytes accepted by this RedQueue.",
- UintegerValue (100000),
- MakeUintegerAccessor (&RedQueue::m_maxBytes),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("m_burst",
- "maximum number of m_burst packets accepted by this queue",
- UintegerValue (6), ///> bursts must be > minTh/avpkt
- MakeUintegerAccessor (&RedQueue::m_burst),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("m_avPkt",
- "In bytes, use with m_burst to determine the time constant for average queue size calculations",
- UintegerValue (1024), ///> average packet size
- MakeUintegerAccessor (&RedQueue::m_avPkt),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("m_minTh",
- "Average queue size at which marking becomes a m_prob",
- UintegerValue (5120), ///> in bytes 1024x5
- MakeUintegerAccessor (&RedQueue::m_minTh),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("m_maxTh",
- "Maximal marking m_prob, should be at least twice min to prevent synchronous retransmits",
- UintegerValue (15360), ///> in bytes 1024x15
- MakeUintegerAccessor (&RedQueue::m_maxTh),
- MakeUintegerChecker<uint32_t> ())
- .AddAttribute ("m_rate",
- "this m_rate is used for calculating the average queue size after some idle time.",
- UintegerValue (1500000), ///> in bps, should be set to bandwidth of interface
- MakeUintegerAccessor (&RedQueue::m_rate),
- MakeUintegerChecker<uint64_t> ())
- .AddAttribute ("m_prob",
- "Probability for marking, suggested values are 0.01 and 0.02",
- DoubleValue (0.02),
- MakeDoubleAccessor (&RedQueue::m_prob),
- MakeDoubleChecker <double> ())
- ;
-
- return tid;
-}
-
-RedQueue::RedQueue ()
- : Queue (),
- m_packets (),
- m_bytesInQueue (0),
- m_wLog (0),
- m_pLog (0),
- m_rmask (0),
- m_scellLog (0),
- m_scellMax (0),
- m_count (-1),
- m_randNum (0),
- m_qavg (0),
- m_initialized (false)
-{
-
- m_sTable = Uint32tVector (RED_STATS_TABLE_SIZE);
-
-}
-
-RedQueue::~RedQueue ()
-{
-}
-
-void
-RedQueue::SetMode (enum Mode mode)
-{
- m_mode = mode;
-}
-
-RedQueue::Mode
-RedQueue::GetMode (void)
-{
- return m_mode;
-}
-
-uint64_t
-RedQueue::GetAverageQueueSize (void)
-{
- return m_qavg;
-}
-
-
-/**
- * The paper says:
- * Given minimum threshold min_th and that we wish to allow bursts of L packets
- * Then Wq should be chosen to satisfy avg_L < min_th
- * L + 1 + [(1-Wq)^(L+1) - 1]/ Wq < min_th
- * L + 1 - min_th < [1 - (1-Wq)^(L+1)]/Wq
- * i.e. given min_th 5, L=50, necessary that Wq <= 0.0042
- *
- * Hence
- * burst + 1 - minTh/avPkt < (1-(1-W)^burst)/W
- * this low-pass filter is used to calculate the avg queue size
- *
- */
-uint32_t
-RedQueue::evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt)
-{
- uint32_t wlog = 1;
-
-
- ///< Just a random W
- double W = 0.5;
-
- double temp = 0;
-
- ///< Note: bursts must be larger than minTh/avpkt for it to work
- temp = (double)burst + 1 - (double)minTh / avpkt;
-
-
- if (temp < 1.0)
- {
- return -1;
- }
-
- /**
- * wlog =1 , W = .5
- * wlog =2 , W = .25
- * wlog =3 , W = .125
- * wlog =4 , W = .0625
- * wlog =5 , W = .03125
- * wlog =6 , W = .015625
- * wlog =7 , W = .0078125
- * wlog =8 , W = .00390625
- * wlog =9 , W = .001953125
- * wlog =10, W = .0009765625
- */
- for (wlog = 1; wlog < 32; wlog++, W /= 2)
- {
- if (temp <= (1 - pow (1 - W, burst)) / W )
- {
- return wlog;
- }
- }
-
- return -1;
-}
-
-/**
- *
- * Plog = log (prob / (maxTh -minTh) );
- *
- * Paper says: When a packet arrives at the gateway and the average queue size
- * is between min_th and max_th, the initial packet marking probability is:
- * Pb = C1*avg - C2
- * where,
- * C1 = maxP/(max_th - mint_th)
- * C2 = maxP*min_th/(max_th - mint_th)
- * maxP could be chosen so that C1 a power of two
- */
-uint32_t
-RedQueue::evalP (uint32_t minTh, uint32_t maxTh, double prob)
-{
-
- uint32_t i = maxTh - minTh ;
-
- if (i <= 0)
- {
- return -1;
- }
-
- prob /= i;
-
- ///< It returns the index that makes C1 a power of two
- for (i = 0; i < 32; i++)
- {
- if (prob > 1.0)
- {
- break;
- }
- prob *= 2;
- }
-
- ///< Error checking
- if (i >= 32 )
- {
- //NS_LOG_DEBUG ("i >= 32, this shouldn't happen");
- return -1;
- }
-
- //NS_LOG_DEBUG ("\t i(makes C1 power of two)=" << i);
- return i;
-}
-
-
-/**
- * avg = avg*(1-W)^m where m = t/xmitTime
- *
- * m_sTable[ t/2^cellLog] = -log(1-W) * t/xmitTime
- * m_sTable[ t >> cellLog]= -log(1-W) * t/xmitTime
- *
- * t is converted to t/2^cellLog for storage in the table
- * find out what is cellLog and return it
- *
- */
-uint32_t
-RedQueue::evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t bps)
-{
-
- ///> in microsecond ticks: 1 sec = 1000000 microsecond ticks
- double xmitTime = ((double) avpkt / bps) * 1000000;
-
- ///> -log(1 - 1/2^wLog) / xmitTime
- ///> note W = 1/2^wLog
- double wLogTemp = -log (1.0 - 1.0 / (1 << wLog)) / xmitTime;
-
-
- ///> the maximum allow idle time
- double maxTime = 31 / wLogTemp;
-
- //NS_LOG_DEBUG ("\t xmitTime=" << xmitTime << " wLogTemp=" << wLogTemp
- // << " maxTime=" << maxTime);
-
-
- uint32_t cLog, i;
-
- for (cLog = 0; cLog < 32; cLog++)
- {
-
- ///> maxTime < 512* 2^cLog
- ///> finds the cLog that's able to cover this maxTime
- if (maxTime / (1 << cLog) < 512)
- {
- break;
- }
-
- }
- if (cLog >= 32)
- {
- return -1;
- }
-
- m_sTable[0] = 0;
-
- for (i = 1; i < 255; i++)
- {
- ///> wLogTemp * i * 2^cLog
- m_sTable[i] = (i << cLog) * wLogTemp;
-
-
- if (m_sTable[i] > 31)
- {
- m_sTable[i] = 31;
- }
- }
-
- m_sTable[255] = 31;
-
- //NS_LOG_DEBUG ("\t cLog=" << cLog);
- return cLog;
-}
-
-
-///> red random mask
-uint32_t
-RedQueue::Rmask (uint32_t pLog)
-{
- ///> ~OUL creates a 32 bit mask
- ///> 2^Plog - 1
- return pLog < 32 ? ((1 << pLog) - 1) : (uint32_t) ~0UL;
-
-}
-
-
-void
-RedQueue::SetParams (uint32_t minTh, uint32_t maxTh,
- uint32_t wLog, uint32_t pLog, uint64_t scellLog)
-{
-
- m_qavg = 0;
- m_count = -1;
- m_minTh = minTh;
- m_maxTh = maxTh;
- m_wLog = wLog;
- m_pLog = pLog;
- m_rmask = Rmask (pLog);
- m_scellLog = scellLog;
- m_scellMax = (255 << m_scellLog);
-
- //NS_LOG_DEBUG ("\t m_wLog" << m_wLog << " m_pLog" << m_pLog << " m_scellLog" << m_scellLog
- // << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
- // << " rmask=" << m_rmask << " m_scellMax=" << m_scellMax);
-}
-
-int
-RedQueue::IsIdling ()
-{
- //use IsZero instead
- if ( m_idleStart.GetNanoSeconds () != 0)
- {
- //NS_LOG_DEBUG ("\t IsIdling");
- }
-
- return m_idleStart.GetNanoSeconds () != 0;
-}
-void
-RedQueue::StartIdlePeriod ()
-{
- m_idleStart = Simulator::Now ();
-}
-void
-RedQueue::EndIdlePeriod ()
-{
- m_idleStart = NanoSeconds (0);
-}
-void
-RedQueue::Restart ()
-{
-
- EndIdlePeriod ();
- m_qavg = 0;
- m_count = -1;
-
-}
-
-/**
- * m = idletime / s
- *
- * m is the number of pkts that might have been transmitted by the gateway
- * during the time that the queue was free
- * s is a typical transmission for a packet
- *
- * m = idletime / (average pkt size / bandwidth)
- *
- * avg = avg *(1-W)^m
- *
- * We need to precompute a table for this calculation because of the exp power
- *
- */
-uint64_t
-RedQueue::AvgFromIdleTime ()
-{
- uint64_t idleTime;
- int shift;
-
- idleTime = ns3::Time(Simulator::Now() - m_idleStart).GetMicroSeconds();
- //idleTime = RedTimeToInteger (Simulator::Now() - m_idleStart, Time::US);
-
- if (idleTime > m_scellMax)
- {
- idleTime = m_scellMax;
- }
-
- //NS_LOG_DEBUG ("\t idleTime=" << idleTime);
- //PrintTable ();
-
- shift = m_sTable [(idleTime >> m_scellLog) & RED_STATS_MASK];
-
- if (shift)
- {
- //std::cout << "shift " << m_qavg << "=>" << (m_qavg >> shift) << std::endl;
- return m_qavg >> shift;
- }
- else
- {
- idleTime = (m_qavg * idleTime) >> m_scellLog;
-
-
- // NS_LOG_DEBUG ("\t idleus=" << idleTime);
-
- if (idleTime < (m_qavg / 2))
- {
- //std::cout <<"idleus " << m_qavg << " - " << idleus << " = " << (m_qavg-idleus) << std::endl;
- return m_qavg - idleTime;
- }
- else
- {
- //std:: cout <<"half " << m_qavg << "=>" << (m_qavg/2) << std::endl;
- return (m_qavg / 2) ;
- }
- }
-}
-
-uint64_t
-RedQueue::AvgFromNonIdleTime (uint32_t backlog)
-{
- //NS_LOG_FUNCTION (this << backlog);
-
- //NS_LOG_DEBUG ("qavg " << m_qavg);
- //NS_LOG_DEBUG ("backlog" << backlog);
-
- /**
- * This is basically EWMA
- * m_qavg = q_avg*(1-W) + backlog*W
- * m_qavg = q_avg + W(backlog - q_avg)
- *
- */
- return m_qavg + (backlog - (m_qavg >> m_wLog));
-}
-
-uint64_t
-RedQueue::AvgCalc (uint32_t backlog)
-{
- //NS_LOG_FUNCTION (this << backlog);
-
- uint64_t qtemp;
-
- if ( !IsIdling ())
- {
- qtemp = AvgFromNonIdleTime (backlog);
- //NS_LOG_DEBUG ("NonIdle Avg " << qtemp);
- //std::cout <<"n "<< qtemp << std::endl;
- return qtemp;
- }
- else
- {
- qtemp = AvgFromIdleTime ();
- //NS_LOG_DEBUG ("Idle Avg" << qtemp);
- //std::cout <<"i "<< qtemp << std::endl;
- return qtemp;
- }
-}
-
-int
-RedQueue::CheckThresh (uint64_t avg)
-{
-
- //NS_LOG_FUNCTION (this << avg);
- //NS_LOG_DEBUG ("\t check threshold: min " << m_minTh << " max" << m_maxTh);
-
- if (avg < m_minTh)
- {
- return BELOW_MIN_THRESH;
- }
- else if (avg >= m_maxTh)
- {
- return ABOVE_MAX_THRESH;
- }
- else
- {
- return BETWEEN_THRESH;
- }
-}
-uint32_t
-RedQueue::RedRandom ()
-{
- //NS_LOG_FUNCTION_NOARGS ();
-
- ///> obtain a random u32 number
- ///> return m_rmask & ran.GetInteger ();
- //checkme
- return m_rmask & rand ();
-}
-int
-RedQueue::MarkProbability (uint64_t avg)
-{
- //NS_LOG_FUNCTION (this << avg);
- //NS_LOG_DEBUG ("\t m_randNum " << m_randNum);
- //NS_LOG_DEBUG ("\t right\t" << m_randNum);
- //NS_LOG_DEBUG ("\t left\t" << ((avg - m_minTh)*m_count));
-
- ///> max_P* (qavg - qth_min)/(qth_max-qth_min) < rnd/qcount
- //return !((avg - m_minTh ) * m_count < m_randNum);
- //checkme
- return !((avg - m_minTh )* m_count < m_randNum);
-
-}
-int
-RedQueue::Processing (uint64_t qavg)
-{
-
- //NS_LOG_FUNCTION (this << "qavg" << qavg << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh);
-
- switch (CheckThresh (qavg))
- {
- case BELOW_MIN_THRESH:
- //NS_LOG_DEBUG ("\t below threshold ");
-
- m_count = -1;
- return DONT_MARK;
-
- case BETWEEN_THRESH:
- //NS_LOG_DEBUG ("\t between threshold ");
-
- if (++m_count)
- {
- //NS_LOG_DEBUG ("\t check Mark Prob");
- if (MarkProbability (qavg))
- {
- m_count = 0;
- m_randNum = RedRandom ();
-
- //NS_LOG_DEBUG ("\t Marked Will Drop " << m_qavg);
-
- return PROB_MARK;
- }
- //NS_LOG_DEBUG ("\t Marked Will Save " << m_qavg);
- }
- else
- {
- m_randNum = RedRandom ();
- }
- return DONT_MARK;
-
- case ABOVE_MAX_THRESH:
-
- //NS_LOG_DEBUG ("\t above threshold ");
-
- m_count = -1;
- return HARD_MARK;
- }
-
- //NS_LOG_DEBUG ("BUG HERE\n");
- return DONT_MARK;
-}
-
-
-bool
-RedQueue::DoEnqueue (Ptr<Packet> p)
-{
- //NS_LOG_FUNCTION (this << p);
-
- if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
- {
- //NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
- Drop (p);
- return false;
- }
-
- if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
- {
- //NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
- Drop (p);
- return false;
- }
-
- if (!m_initialized)
- {
- // making sure all the variables are initialized ok
- //NS_LOG_DEBUG ("\t m_maxPackets" << m_maxPackets
- // << " m_maxBytes" << m_maxBytes
- // << " m_burst" << m_burst << " m_avPkt" << m_avPkt
- // << " m_minTh" << m_minTh << " m_maxTh" << m_maxTh
- // << " m_rate" << m_rate << " m_prob" << m_prob);
-
- m_wLog = evalEwma (m_minTh, m_burst, m_avPkt);
- m_pLog = evalP (m_minTh, m_maxTh, m_prob);
- m_scellLog = evalIdleDamping (m_wLog, m_avPkt, m_rate);
-
- SetParams (m_minTh, m_maxTh, m_wLog, m_pLog, m_scellLog);
- EndIdlePeriod ();
-// srand((unsigned)time(0));
- m_initialized = true;
- }
-
-// PrintTable();
-
- if (GetMode () == BYTES)
- {
- m_qavg = AvgCalc (m_bytesInQueue);
- }
- else if (GetMode () == PACKETS)
- {
- //not yet supported
-// m_qavg = AvgCalc (m_packets.size ());
- }
-
- //NS_LOG_DEBUG ("\t bytesInQueue " << m_bytesInQueue << "\tQavg " << m_qavg);
- //NS_LOG_DEBUG ("\t packetsInQueue " << m_packets.size () << "\tQavg " << m_qavg);
-
-
- if (IsIdling ())
- {
- EndIdlePeriod ();
- }
-
- switch (Processing (m_qavg) )
- {
- case DONT_MARK:
- break;
-
- case PROB_MARK:
- //NS_LOG_DEBUG ("\t Dropping due to Prob Mark " << m_qavg);
- m_stats.probDrop++;
- m_stats.probMark++;
- Drop (p);
- return false;
-
- case HARD_MARK:
- //NS_LOG_DEBUG ("\t Dropping due to Hard Mark " << m_qavg);
- m_stats.forcedMark++;
- m_stats.probDrop++;
- Drop (p);
- return false;
- }
-
-
- m_bytesInQueue += p->GetSize ();
- m_packets.push_back (p);
-
- //NS_LOG_LOGIC ("Number packets " << m_packets.size ());
- //NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
-
- return true;
-}
-
-Ptr<Packet>
-RedQueue::DoDequeue (void)
-{
- //NS_LOG_FUNCTION (this);
-
- if (m_packets.empty ())
- {
- //NS_LOG_LOGIC ("Queue empty");
- return 0;
- }
-
- Ptr<Packet> p = m_packets.front ();
- m_packets.pop_front ();
- m_bytesInQueue -= p->GetSize ();
-
- //NS_LOG_LOGIC ("Popped " << p);
-
- //NS_LOG_LOGIC ("Number packets " << m_packets.size ());
- //NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
-
- if (m_bytesInQueue <= 0 && !IsIdling ())
- {
- StartIdlePeriod ();
- }
-
- return p;
-}
-
-///> just for completeness
-/// m_packets.remove (p) also works
-int
-RedQueue::DropPacket (Ptr<Packet> p)
-{
-
- //NS_LOG_FUNCTION (this << p);
-
- //NS_LOG_DEBUG ("\t Dropping Packet p");
-
- std::list<Ptr<Packet> >::iterator iter;
- uint32_t packetSize;
-
- for (iter = m_packets.begin(); iter != m_packets.end(); ++iter)
- {
- if (*iter == p)
- {
- packetSize= p->GetSize ();
- m_packets.erase(iter);
- m_bytesInQueue -= packetSize;
- return 1;
- }
- }
-
- if (!IsIdling ())
- {
- StartIdlePeriod ();
- }
-
- return 0;
-}
-
-Ptr<const Packet>
-RedQueue::DoPeek (void) const
-{
- //NS_LOG_FUNCTION (this);
-
- if (m_packets.empty ())
- {
- //NS_LOG_LOGIC ("Queue empty");
- return NULL;
- }
-
- Ptr<Packet> p = m_packets.front ();
-
- //NS_LOG_LOGIC ("Number packets " << m_packets.size ());
- //NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
-
- return p;
-}
-
-void
-RedQueue::PrintTable ()
-{
- //NS_LOG_FUNCTION_NOARGS ();
-
- for (uint32_t i = 0; i < RED_STATS_TABLE_SIZE; i++)
- {
- std::cout << m_sTable[i] << " ";
- }
- std::cout << std::endl;
-}
-
-
-} // namespace ns3
+++ /dev/null
-/* Copyright (c) 2011, 2014. The SimGrid Team.
- * All rights reserved. */
-
-/* This program is free software; you can redistribute it and/or modify it
- * under the terms of the license (GNU LGPL) which comes with this package. */
-
-/*
- * Copyright (c) 2010 Regents of the University of California
- *
- * 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>
- *
- * Random Early Detection (RED) algorithm.
- *
- * This implementation uses Bytes as queue size metric by default
- * based on the Kuznetsov's implementation of Red in Linux.
- * Therefore, only bytes as queue size metric is supported at the moment.
- *
- * Original RED is from
- * Sally Floyd and Van Jacobson, "Random Early Detection Gateways for
- * Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking
- *
- * Description:
- *
- * Packet arrival:
- * avg = (1-W)*avg + W*currentQueueLen
- * W is the queue weight( chosen as 2^(-Wlog)). Decrease W for larger bursts
- *
- * if ( avg > maxTh) -> mark/drop packets
- * if ( avg < minTh) -> allow packets
- * if ( minTh < avg < maxTh) -> calculate probability for marking/dropping
- *
- *
- * Pb = maxP*(avg - minTh)/(maxTh - minTh)
- * Note: As avg varies from minTh to maxTh, Pb varies 0 to maxP
- *
- * Pa = Pb /(1 - count*Pb)
- * The final marking probability Pa increases slowly as the count increases
- * since the last marked packet
- *
- * maxP can be chosen s/t:
- * maxP = (maxTh - minTh )/2^Plog
- *
- * To allow large bursts of L packets of size S, W can be chosen as:
- * (see paper for details)
- *
- * L + 1 - minTh/S < (1-(1-W)^L)/W
- *
- *
- * Some parameters:
- * W = 0.002
- * maxP = .02
- *
- *
- */
-
-#ifndef RED_QUEUE_H
-#define RED_QUEUE_H
-
-#include <queue>
-#include "ns3/packet.h"
-#include "ns3/queue.h"
-#include "ns3/nstime.h"
-
-namespace ns3 {
-
-class TraceContainer;
-
-/**
- * \ingroup queue
- *
- * \brief A RED packet queue
- */
-class RedQueue : public Queue
-{
-public:
- typedef std::vector< uint32_t> Uint32tVector;
-
- struct Stats
- {
- uint32_t probDrop; ///< Early probability drops
- uint32_t probMark; ///< Early probability marks
- uint32_t forcedDrop; ///< Forced drops, qavg > max threshold
- uint32_t forcedMark; ///< Forced marks, qavg > max threshold
- uint32_t pdrop; ///< Drops due to queue limits
- uint32_t other; ///< Drops due to drop calls
- uint32_t backlog;
- };
-
- static TypeId GetTypeId (void);
- /**
- * \brief RedQueue Constructor
- *
- */
- RedQueue ();
-
- virtual ~RedQueue ();
-
- /**
- * Enumeration of the modes supported in the class.
- *
- */
- enum Mode
- {
- ILLEGAL, /**< Mode not set */
- PACKETS, /**< Use number of packets for maximum queue size */
- BYTES, /**< Use number of bytes for maximum queue size */
- };
-
- /**
- * Enumeration of RED thresholds
- *
- */
- enum
- {
- BELOW_MIN_THRESH,
- ABOVE_MAX_THRESH,
- BETWEEN_THRESH,
- };
-
- /**
- * Enumeration Marking
- *
- */
- enum
- {
- DONT_MARK,
- PROB_MARK,
- HARD_MARK,
- };
-
- /**
- * Set the operating mode of this device.
- *
- * \param mode The operating mode of this device.
- *
- */
- void SetMode (RedQueue::Mode mode);
-
- /**
- * Get the encapsulation mode of this device.
- *
- * \returns The encapsulation mode of this device.
- */
- RedQueue::Mode GetMode (void);
-
- /**
- * Get the average queue size
- *
- * \returns The average queue size in bytes
- */
- uint64_t GetAverageQueueSize (void);
-
-
-private:
- void SetParams (uint32_t minTh, uint32_t maxTh,
- uint32_t wLog, uint32_t pLog, uint64_t scellLog );
- void StartIdlePeriod ();
- void EndIdlePeriod ();
- void Restart ();
- void printRedOpt ();
- void printStats ();
- void PrintTable ();
-
- int IsIdling ();
- int CheckThresh (uint64_t avg);
- int Processing (uint64_t avg);
- int MarkProbability (uint64_t avg);
- int DropPacket (Ptr<Packet> p);
-
- uint64_t AvgFromIdleTime ();
- uint64_t AvgCalc (uint32_t backlog);
-
- ///< Avg = Avg*(1-W) + backlog*W
- uint64_t AvgFromNonIdleTime (uint32_t backlog);
-
- ///< burst + 1 - qmin/avpkt < (1-(1-W)^burst)/W
- ///< this low-pass filter is used to calculate the avg queue size
- uint32_t evalEwma (uint32_t minTh, uint32_t burst, uint32_t avpkt);
-
- ///< Plog = log (prob / (qMax - qMin))
- uint32_t evalP (uint32_t minTh, uint32_t maxTh, double prob);
-
- ///< -log(1-W) * t/TxTime
- uint32_t evalIdleDamping (uint32_t wLog, uint32_t avpkt, uint32_t rate);
-
- uint32_t Rmask (uint32_t pLog);
- uint32_t RedRandom ();
-
- virtual bool DoEnqueue (Ptr<Packet> p);
- virtual Ptr<Packet> DoDequeue (void);
- virtual Ptr<const Packet> DoPeek (void) const;
-
-
- std::list<Ptr<Packet> > m_packets;
-
- Mode m_mode;
-
- uint32_t m_bytesInQueue;
-
- ///< users' configurable options
- uint32_t m_maxPackets;
- uint32_t m_maxBytes;
- uint32_t m_burst;
-
- /**
- * in bytes, use with burst to determine the time constant
- * for average queue size calculations, for ewma
- */
- uint32_t m_avPkt;
- uint32_t m_minTh; ///> Min avg length threshold (bytes), should be < maxTh/2
- uint32_t m_maxTh; ///> Max avg length threshold (bytes), should be >= 2*minTh
- uint32_t m_rate; ///> bandwidth in bps
- uint32_t m_wLog; ///> log(W) bits
- uint32_t m_pLog; ///> random number bits log (P_max/(maxTh - minTh))
- uint32_t m_rmask;
- uint32_t m_scellLog; ///> cell size for idle damping
- uint64_t m_scellMax;
- uint32_t m_count; ///> number of packets since last random number generation
- uint32_t m_randNum; ///> a random number 0 ...2^Plog
-
- uint64_t m_qavg; ///> average q length
- double m_prob;
- bool m_initialized;
-
- Stats m_stats;
- Time m_idleStart; ///> start of current idle period
- Uint32tVector m_sTable;
-};
-
-}; // namespace ns3
-
-#endif /* RED_QUEUE_H */
