From 9cc5dac9b02b2bf4f7a01e27642b0e6060877dd1 Mon Sep 17 00:00:00 2001 From: Navarrop Date: Wed, 28 Sep 2011 17:26:34 +0200 Subject: [PATCH] Implement RED module for ns3 into simgrid code. --- buildtools/Cmake/DefinePackages.cmake | 17 +- buildtools/Cmake/MakeLib.cmake | 5 - buildtools/Cmake/Modules/FindNS3.cmake | 24 +- src/surf/ns3/ns3_interface.cc | 13 +- src/surf/ns3/ns3_simulator.h | 2 - src/surf/ns3/red-queue.cc | 769 +++++++++++++++++++++++++ src/surf/ns3/red-queue.h | 240 ++++++++ 7 files changed, 1016 insertions(+), 54 deletions(-) create mode 100644 src/surf/ns3/red-queue.cc create mode 100644 src/surf/ns3/red-queue.h diff --git a/buildtools/Cmake/DefinePackages.cmake b/buildtools/Cmake/DefinePackages.cmake index ea1f093367..994ef8372e 100644 --- a/buildtools/Cmake/DefinePackages.cmake +++ b/buildtools/Cmake/DefinePackages.cmake @@ -104,6 +104,7 @@ set(EXTRA_DIST src/surf/ns3/ns3_interface.h src/surf/ns3/ns3_simulator.h src/surf/ns3/my-point-to-point-helper.h + src/surf/ns3/red-queue.h ) set(XBT_RL_SRC @@ -201,20 +202,10 @@ set(NS3_SRC src/surf/network_ns3.c src/surf/ns3/ns3_interface.cc src/surf/ns3/ns3_simulator.cc - ) + src/surf/ns3/red-queue.cc + src/surf/ns3/my-point-to-point-helper.cc +) -if(HAVE_RED_QUEUE_H) - set(NS3_SRC - ${NS3_SRC} - src/surf/ns3/my-point-to-point-helper.cc - ) -else(HAVE_RED_QUEUE_H) - set(EXTRA_DIST - ${EXTRA_DIST} - src/surf/ns3/my-point-to-point-helper.cc - ) -endif(HAVE_RED_QUEUE_H) - set(SURF_SRC src/surf/surf_model.c src/surf/surf_action.c diff --git a/buildtools/Cmake/MakeLib.cmake b/buildtools/Cmake/MakeLib.cmake index 9640ac49b6..45b347dd60 100644 --- a/buildtools/Cmake/MakeLib.cmake +++ b/buildtools/Cmake/MakeLib.cmake @@ -124,11 +124,6 @@ if(HAVE_NS3) endif(${NS3_VERSION} EQUAL 310) endif(HAVE_NS3) -if(HAVE_NS3 AND HAVE_RED_QUEUE_H) - set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -D_HAVE_NS3_RED") - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D_HAVE_NS3_RED") -endif(HAVE_NS3 AND HAVE_RED_QUEUE_H) - if(HAVE_POSIX_GETTIME) SET(SIMGRID_DEP "${SIMGRID_DEP} -lrt") endif(HAVE_POSIX_GETTIME) diff --git a/buildtools/Cmake/Modules/FindNS3.cmake b/buildtools/Cmake/Modules/FindNS3.cmake index 7b04300b9e..c8e34bbc8d 100644 --- a/buildtools/Cmake/Modules/FindNS3.cmake +++ b/buildtools/Cmake/Modules/FindNS3.cmake @@ -42,20 +42,6 @@ find_path(HAVE_CORE_MODULE_H ${ns3_path} ) -find_path(HAVE_RED_QUEUE_H - NAME ns3/red-queue.h - HINTS - $ENV{HOME} - PATH_SUFFIXES include ns3/include - PATHS - /opt - /opt/local - /opt/csw - /sw - /usr - ${ns3_path} -) - message(STATUS "Looking for core-module.h") if(HAVE_CORE_MODULE_H) message(STATUS "Looking for core-module.h - found") @@ -64,14 +50,6 @@ message(STATUS "Looking for core-module.h - not found") endif(HAVE_CORE_MODULE_H) mark_as_advanced(HAVE_CORE_MODULE_H) -message(STATUS "Looking for red-queue.h") -if(HAVE_RED_QUEUE_H) -message(STATUS "Looking for red-queue.h - found") -else(HAVE_RED_QUEUE_H) -message(STATUS "Looking for red-queue.h - not found") -endif(HAVE_RED_QUEUE_H) -mark_as_advanced(HAVE_RED_QUEUE_H) - message(STATUS "Looking for lib ns3") if(HAVE_NS3_LIB) message(STATUS "Looking for lib ns3 - found") @@ -97,7 +75,7 @@ if(HAVE_CORE_MODULE_H) string(REPLACE "/libns3.${LIB_EXE}" "" HAVE_NS3_LIB "${HAVE_NS3_LIB}") endif(HAVE_NS3_LIB) if(HAVE_NS3_CORE_LIB) - message(STATUS "Warning: NS-3 version > 3.10") + message(STATUS "NS-3 version > 3.10") set(HAVE_NS3 1) set(NS3_VERSION 312) string(REPLACE "/libns3-core.${LIB_EXE}" "" HAVE_NS3_LIB "${HAVE_NS3_CORE_LIB}") diff --git a/src/surf/ns3/ns3_interface.cc b/src/surf/ns3/ns3_interface.cc index 50d724cc3c..21eb92ad15 100644 --- a/src/surf/ns3/ns3_interface.cc +++ b/src/surf/ns3/ns3_interface.cc @@ -102,9 +102,6 @@ int ns3_initialize(const char* TcpProtocol){ Config::SetDefault ("ns3::TcpSocket::SegmentSize", UintegerValue (1024)); // 1024-byte packet for easier reading Config::SetDefault ("ns3::TcpSocket::DelAckCount", UintegerValue (1)); -#ifdef _HAVE_NS3_RED - XBT_DEBUG("Using RED version of ns3"); -#endif if(!strcmp(TcpProtocol,"default")){ return 0; } @@ -237,11 +234,9 @@ void * ns3_add_link(int src, e_ns3_network_element_type_t type_src, LogComponentEnable("UdpEchoServerApplication", LOG_LEVEL_INFO); } -#ifdef _HAVE_NS3_RED + MyPointToPointHelper pointToPoint; -#else - PointToPointHelper pointToPoint; -#endif + NetDeviceContainer netA; Ipv4AddressHelper address; @@ -253,11 +248,7 @@ void * ns3_add_link(int src, e_ns3_network_element_type_t type_src, pointToPoint.SetChannelAttribute ("Delay", StringValue (lat)); //pointToPoint.EnablePcapAll("test_ns3_trace"); //DEBUG -#ifdef _HAVE_NS3_RED netA.Add(pointToPoint.Install (a, type_src, b, type_dst)); -#else - netA.Add(pointToPoint.Install (a, b)); -#endif char * adr = bprintf("%d.%d.0.0",number_of_networks,number_of_links); address.SetBase (adr, "255.255.0.0"); diff --git a/src/surf/ns3/ns3_simulator.h b/src/surf/ns3/ns3_simulator.h index 503a7d593f..aab3a04981 100644 --- a/src/surf/ns3/ns3_simulator.h +++ b/src/surf/ns3/ns3_simulator.h @@ -10,9 +10,7 @@ #ifdef __cplusplus #include "ns3/core-module.h" -#ifdef _HAVE_NS3_RED #include "my-point-to-point-helper.h" -#endif #ifdef _NS3_3_10 /*NS3 3.10*/ diff --git a/src/surf/ns3/red-queue.cc b/src/surf/ns3/red-queue.cc new file mode 100644 index 0000000000..ca26c5e46a --- /dev/null +++ b/src/surf/ns3/red-queue.cc @@ -0,0 +1,769 @@ +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ +/* + * 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 + * + */ + +#include "ns3/log.h" +#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 "ns3/random-variable.h" + +#include + +NS_LOG_COMPONENT_DEFINE ("red"); + +#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 paramemters 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 () + .AddConstructor () + .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 ()) + .AddAttribute ("MaxBytes", + "The maximum number of bytes accepted by this RedQueue.", + UintegerValue (100000), + MakeUintegerAccessor (&RedQueue::m_maxBytes), + MakeUintegerChecker ()) + .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 ()) + .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 ()) + .AddAttribute ("m_minTh", + "Average queue size at which marking becomes a m_prob", + UintegerValue (5120), ///> in bytes 1024x5 + MakeUintegerAccessor (&RedQueue::m_minTh), + MakeUintegerChecker ()) + .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 ()) + .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 ()) + .AddAttribute ("m_prob", + "Probability for marking, suggested values are 0.01 and 0.02", + DoubleValue (0.02), + MakeDoubleAccessor (&RedQueue::m_prob), + MakeDoubleChecker ()) + ; + + 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 () +{ + NS_LOG_FUNCTION_NOARGS (); +} + +void +RedQueue::SetMode (enum Mode mode) +{ + NS_LOG_FUNCTION (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) +{ + NS_LOG_FUNCTION (this); + 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; + + NS_LOG_DEBUG ( "\t temp =" << temp); + + if (temp < 1.0) + { + NS_LOG_DEBUG ("\tFailed to calculate EWMA constant"); + 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 ) + { + NS_LOG_DEBUG ("\t wlog=" << wlog); + return wlog; + } + } + + NS_LOG_DEBUG ("\tFailed to calculate EWMA constant"); + 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) +{ + NS_LOG_FUNCTION (this); + + uint32_t i = maxTh - minTh ; + + if (i <= 0) + { + NS_LOG_DEBUG ("maxTh - minTh = 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) +{ + NS_LOG_FUNCTION (this); + + ///> 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) : ~0UL; + +} + + +void +RedQueue::SetParams (uint32_t minTh, uint32_t maxTh, + uint32_t wLog, uint32_t pLog, uint64_t scellLog) +{ + NS_LOG_FUNCTION (this); + + 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 () +{ + NS_LOG_FUNCTION_NOARGS (); + + //use IsZero instead + if ( m_idleStart.GetNanoSeconds () != 0) + { + NS_LOG_DEBUG ("\t IsIdling"); + } + + return m_idleStart.GetNanoSeconds () != 0; +} +void +RedQueue::StartIdlePeriod () +{ + NS_LOG_FUNCTION_NOARGS (); + + m_idleStart = Simulator::Now (); +} +void +RedQueue::EndIdlePeriod () +{ + NS_LOG_FUNCTION_NOARGS (); + + m_idleStart = NanoSeconds (0); +} +void +RedQueue::Restart () +{ + + NS_LOG_FUNCTION_NOARGS (); + + 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 () +{ + NS_LOG_FUNCTION_NOARGS (); + + 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 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 +RedQueue::DoDequeue (void) +{ + NS_LOG_FUNCTION (this); + + if (m_packets.empty ()) + { + NS_LOG_LOGIC ("Queue empty"); + return 0; + } + + Ptr 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 p) +{ + + NS_LOG_FUNCTION (this << p); + + NS_LOG_DEBUG ("\t Dropping Packet p"); + + std::list >::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 +RedQueue::DoPeek (void) const +{ + NS_LOG_FUNCTION (this); + + if (m_packets.empty ()) + { + NS_LOG_LOGIC ("Queue empty"); + return NULL; + } + + Ptr 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 diff --git a/src/surf/ns3/red-queue.h b/src/surf/ns3/red-queue.h new file mode 100644 index 0000000000..1adece9d59 --- /dev/null +++ b/src/surf/ns3/red-queue.h @@ -0,0 +1,240 @@ +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ +/* + * 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 + * + * 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 +#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 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 p); + virtual Ptr DoDequeue (void); + virtual Ptr DoPeek (void) const; + + + std::list > 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 */ -- 2.20.1