A Discrete-Event Network Simulator
API
codel-queue-disc.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2012 Andrew McGregor
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  * Codel, the COntrolled DELay Queueing discipline
19  * Based on ns2 simulation code presented by Kathie Nichols
20  *
21  * This port based on linux kernel code by
22  * Authors: Dave Täht <d@taht.net>
23  * Eric Dumazet <edumazet@google.com>
24  *
25  * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
26 */
27 
28 #include "ns3/log.h"
29 #include "ns3/enum.h"
30 #include "ns3/uinteger.h"
31 #include "ns3/abort.h"
32 #include "codel-queue-disc.h"
33 #include "ns3/object-factory.h"
34 #include "ns3/drop-tail-queue.h"
35 
36 namespace ns3 {
37 
38 NS_LOG_COMPONENT_DEFINE ("CoDelQueueDisc");
39 
47 /* borrowed from the linux kernel */
48 static inline uint32_t ReciprocalDivide (uint32_t A, uint32_t R)
49 {
50  return (uint32_t)(((uint64_t)A * R) >> 32);
51 }
52 
53 /* end kernel borrowings */
54 
59 static uint32_t CoDelGetTime (void)
60 {
61  Time time = Simulator::Now ();
62  uint64_t ns = time.GetNanoSeconds ();
63 
64  return static_cast<uint32_t>(ns >> CODEL_SHIFT);
65 }
66 
67 
68 NS_OBJECT_ENSURE_REGISTERED (CoDelQueueDisc);
69 
71 {
72  static TypeId tid = TypeId ("ns3::CoDelQueueDisc")
73  .SetParent<QueueDisc> ()
74  .SetGroupName ("TrafficControl")
75  .AddConstructor<CoDelQueueDisc> ()
76  .AddAttribute ("MaxSize",
77  "The maximum number of packets/bytes accepted by this queue disc.",
82  .AddAttribute ("MinBytes",
83  "The CoDel algorithm minbytes parameter.",
84  UintegerValue (1500),
86  MakeUintegerChecker<uint32_t> ())
87  .AddAttribute ("Interval",
88  "The CoDel algorithm interval",
89  StringValue ("100ms"),
91  MakeTimeChecker ())
92  .AddAttribute ("Target",
93  "The CoDel algorithm target queue delay",
94  StringValue ("5ms"),
96  MakeTimeChecker ())
97  .AddTraceSource ("Count",
98  "CoDel count",
100  "ns3::TracedValueCallback::Uint32")
101  .AddTraceSource ("LastCount",
102  "CoDel lastcount",
104  "ns3::TracedValueCallback::Uint32")
105  .AddTraceSource ("DropState",
106  "Dropping state",
108  "ns3::TracedValueCallback::Bool")
109  .AddTraceSource ("DropNext",
110  "Time until next packet drop",
112  "ns3::TracedValueCallback::Uint32")
113  ;
114 
115  return tid;
116 }
117 
120  m_count (0),
121  m_lastCount (0),
122  m_dropping (false),
123  m_recInvSqrt (~0U >> REC_INV_SQRT_SHIFT),
124  m_firstAboveTime (0),
125  m_dropNext (0),
126  m_state1 (0),
127  m_state2 (0),
128  m_state3 (0),
129  m_states (0)
130 {
131  NS_LOG_FUNCTION (this);
132 }
133 
135 {
136  NS_LOG_FUNCTION (this);
137 }
138 
139 void
141 {
142  NS_LOG_FUNCTION (this);
143  uint32_t invsqrt = ((uint32_t) m_recInvSqrt) << REC_INV_SQRT_SHIFT;
144  uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
145  uint64_t val = (3ll << 32) - ((uint64_t) m_count * invsqrt2);
146 
147  val >>= 2; /* avoid overflow */
148  val = (val * invsqrt) >> (32 - 2 + 1);
149  m_recInvSqrt = static_cast<uint16_t>(val >> REC_INV_SQRT_SHIFT);
150 }
151 
152 uint32_t
154 {
155  NS_LOG_FUNCTION (this);
157 }
158 
159 bool
161 {
162  NS_LOG_FUNCTION (this << item);
163 
164  if (GetCurrentSize () + item > GetMaxSize ())
165  {
166  NS_LOG_LOGIC ("Queue full -- dropping pkt");
168  return false;
169  }
170 
171  bool retval = GetInternalQueue (0)->Enqueue (item);
172 
173  // If Queue::Enqueue fails, QueueDisc::DropBeforeEnqueue is called by the
174  // internal queue because QueueDisc::AddInternalQueue sets the trace callback
175 
176  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
177  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
178 
179  return retval;
180 }
181 
182 bool
184 {
185  NS_LOG_FUNCTION (this);
186  bool okToDrop;
187 
188  if (!item)
189  {
190  m_firstAboveTime = 0;
191  return false;
192  }
193 
194  Time delta = Simulator::Now () - item->GetTimeStamp ();
195  NS_LOG_INFO ("Sojourn time " << delta.ToDouble (Time::MS) << "ms");
196  uint32_t sojournTime = Time2CoDel (delta);
197 
198  if (CoDelTimeBefore (sojournTime, Time2CoDel (m_target))
200  {
201  // went below so we'll stay below for at least q->interval
202  NS_LOG_LOGIC ("Sojourn time is below target or number of bytes in queue is less than minBytes; packet should not be dropped");
203  m_firstAboveTime = 0;
204  return false;
205  }
206  okToDrop = false;
207  if (m_firstAboveTime == 0)
208  {
209  /* just went above from below. If we stay above
210  * for at least q->interval we'll say it's ok to drop
211  */
212  NS_LOG_LOGIC ("Sojourn time has just gone above target from below, need to stay above for at least q->interval before packet can be dropped. ");
214  }
215  else if (CoDelTimeAfter (now, m_firstAboveTime))
216  {
217  NS_LOG_LOGIC ("Sojourn time has been above target for at least q->interval; it's OK to (possibly) drop packet.");
218  okToDrop = true;
219  ++m_state1;
220  }
221  return okToDrop;
222 }
223 
226 {
227  NS_LOG_FUNCTION (this);
228 
229  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
230  if (!item)
231  {
232  // Leave dropping state when queue is empty
233  m_dropping = false;
234  NS_LOG_LOGIC ("Queue empty");
235  return 0;
236  }
237  uint32_t now = CoDelGetTime ();
238 
239  NS_LOG_LOGIC ("Popped " << item);
240  NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
241  NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
242 
243  // Determine if item should be dropped
244  bool okToDrop = OkToDrop (item, now);
245 
246  if (m_dropping)
247  { // In the dropping state (sojourn time has gone above target and hasn't come down yet)
248  // Check if we can leave the dropping state or next drop should occur
249  NS_LOG_LOGIC ("In dropping state, check if it's OK to leave or next drop should occur");
250  if (!okToDrop)
251  {
252  /* sojourn time fell below target - leave dropping state */
253  NS_LOG_LOGIC ("Sojourn time goes below target, it's OK to leave dropping state.");
254  m_dropping = false;
255  }
256  else if (CoDelTimeAfterEq (now, m_dropNext))
257  {
258  m_state2++;
259  while (m_dropping && CoDelTimeAfterEq (now, m_dropNext))
260  {
261  // It's time for the next drop. Drop the current packet and
262  // dequeue the next. The dequeue might take us out of dropping
263  // state. If not, schedule the next drop.
264  // A large amount of packets in queue might result in drop
265  // rates so high that the next drop should happen now,
266  // hence the while loop.
267  NS_LOG_LOGIC ("Sojourn time is still above target and it's time for next drop; dropping " << item);
269 
270  ++m_count;
271  NewtonStep ();
272  item = GetInternalQueue (0)->Dequeue ();
273 
274  if (item)
275  {
276  NS_LOG_LOGIC ("Popped " << item);
277  NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
278  NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
279  }
280 
281  if (!OkToDrop (item, now))
282  {
283  /* leave dropping state */
284  NS_LOG_LOGIC ("Leaving dropping state");
285  m_dropping = false;
286  }
287  else
288  {
289  /* schedule the next drop */
290  NS_LOG_LOGIC ("Running ControlLaw for input m_dropNext: " << (double)m_dropNext / 1000000);
292  NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000);
293  }
294  }
295  }
296  }
297  else
298  {
299  // Not in the dropping state
300  // Decide if we have to enter the dropping state and drop the first packet
301  NS_LOG_LOGIC ("Not in dropping state; decide if we have to enter the state and drop the first packet");
302  if (okToDrop)
303  {
304  // Drop the first packet and enter dropping state unless the queue is empty
305  NS_LOG_LOGIC ("Sojourn time goes above target, dropping the first packet " << item << " and entering the dropping state");
307 
308  item = GetInternalQueue (0)->Dequeue ();
309 
310  if (item)
311  {
312  NS_LOG_LOGIC ("Popped " << item);
313  NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
314  NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
315  }
316 
317  OkToDrop (item, now);
318  m_dropping = true;
319  ++m_state3;
320  /*
321  * if min went above target close to when we last went below it
322  * assume that the drop rate that controlled the queue on the
323  * last cycle is a good starting point to control it now.
324  */
325  int delta = m_count - m_lastCount;
326  if (delta > 1 && CoDelTimeBefore (now - m_dropNext, 16 * Time2CoDel (m_interval)))
327  {
328  m_count = delta;
329  NewtonStep ();
330  }
331  else
332  {
333  m_count = 1;
335  }
337  NS_LOG_LOGIC ("Running ControlLaw for input now: " << (double)now);
338  m_dropNext = ControlLaw (now);
339  NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000 << " now " << (double)now / 1000000);
340  }
341  }
342  ++m_states;
343  return item;
344 }
345 
346 Time
348 {
349  return m_target;
350 }
351 
352 Time
354 {
355  return m_interval;
356 }
357 
358 uint32_t
360 {
361  return m_dropNext;
362 }
363 
364 bool
365 CoDelQueueDisc::CoDelTimeAfter (uint32_t a, uint32_t b)
366 {
367  return ((int)(a) - (int)(b) > 0);
368 }
369 
370 bool
371 CoDelQueueDisc::CoDelTimeAfterEq (uint32_t a, uint32_t b)
372 {
373  return ((int)(a) - (int)(b) >= 0);
374 }
375 
376 bool
377 CoDelQueueDisc::CoDelTimeBefore (uint32_t a, uint32_t b)
378 {
379  return ((int)(a) - (int)(b) < 0);
380 }
381 
382 bool
383 CoDelQueueDisc::CoDelTimeBeforeEq (uint32_t a, uint32_t b)
384 {
385  return ((int)(a) - (int)(b) <= 0);
386 }
387 
388 uint32_t
390 {
391  return static_cast<uint32_t>(t.GetNanoSeconds () >> CODEL_SHIFT);
392 }
393 
394 bool
396 {
397  NS_LOG_FUNCTION (this);
398  if (GetNQueueDiscClasses () > 0)
399  {
400  NS_LOG_ERROR ("CoDelQueueDisc cannot have classes");
401  return false;
402  }
403 
404  if (GetNPacketFilters () > 0)
405  {
406  NS_LOG_ERROR ("CoDelQueueDisc cannot have packet filters");
407  return false;
408  }
409 
410  if (GetNInternalQueues () == 0)
411  {
412  // add a DropTail queue
414  ("MaxSize", QueueSizeValue (GetMaxSize ())));
415  }
416 
417  if (GetNInternalQueues () != 1)
418  {
419  NS_LOG_ERROR ("CoDelQueueDisc needs 1 internal queue");
420  return false;
421  }
422 
423  return true;
424 }
425 
426 void
428 {
429  NS_LOG_FUNCTION (this);
430 }
431 
432 } // namespace ns3
433 
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:435
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
Add a packet to the queue.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
Class for representing queue sizes.
Definition: queue-size.h:94
void DropBeforeEnqueue(Ptr< const QueueDiscItem > item, const char *reason)
Perform the actions required when the queue disc is notified of a packet dropped before enqueue...
Definition: queue-disc.cc:721
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Hold variables of type string.
Definition: string.h:41
uint32_t GetDropNext(void)
Get the time for next packet drop while in the dropping state.
TracedValue< uint32_t > m_count
Number of packets dropped since entering drop state.
QueueSize GetCurrentSize(void)
Get the current size of the queue disc in bytes, if operating in bytes mode, or packets, otherwise.
Definition: queue-disc.cc:518
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
Time GetInterval(void)
Get the interval.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:204
double ToDouble(enum Unit unit) const
Get the Time value expressed in a particular unit.
Definition: nstime.h:505
bool CoDelTimeAfterEq(uint32_t a, uint32_t b)
Check if CoDel time a is successive or equal to b.
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:442
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:280
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
uint32_t ControlLaw(uint32_t t)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
bool CoDelTimeAfter(uint32_t a, uint32_t b)
Check if CoDel time a is successive to b.
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
TracedValue< bool > m_dropping
True if in dropping state.
bool OkToDrop(Ptr< QueueDiscItem > item, uint32_t now)
Determine whether a packet is OK to be dropped.
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:576
Ptr< T > CreateObjectWithAttributes(std::string n1="", const AttributeValue &v1=EmptyAttributeValue(), std::string n2="", const AttributeValue &v2=EmptyAttributeValue(), std::string n3="", const AttributeValue &v3=EmptyAttributeValue(), std::string n4="", const AttributeValue &v4=EmptyAttributeValue(), std::string n5="", const AttributeValue &v5=EmptyAttributeValue(), std::string n6="", const AttributeValue &v6=EmptyAttributeValue(), std::string n7="", const AttributeValue &v7=EmptyAttributeValue(), std::string n8="", const AttributeValue &v8=EmptyAttributeValue(), std::string n9="", const AttributeValue &v9=EmptyAttributeValue())
Allocate an Object on the heap and initialize with a set of attributes.
uint32_t m_states
Total number of times we are in state 1, state 2, or state 3.
uint32_t m_firstAboveTime
Time to declare sojourn time above target.
uint32_t m_state2
Number of times we perform next drop while in dropping state.
bool CoDelTimeBefore(uint32_t a, uint32_t b)
Check if CoDel time a is preceding b.
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:596
Hold an unsigned integer type.
Definition: uinteger.h:44
Time m_target
5 ms target queue delay
CoDelQueueDisc()
CoDelQueueDisc Constructor.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
TracedValue< uint32_t > m_lastCount
Last number of packets dropped since entering drop state.
Time m_interval
100 ms sliding minimum time window width
Introspection did not find any typical Config paths.
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
virtual Ptr< QueueDiscItem > DoDequeue(void)
Remove a packet from queue based on the current state If we are in dropping state, check if we could leave the dropping state or if we should perform next drop If we are not currently in dropping state, check if we need to enter the state and drop the first packet.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
uint16_t m_recInvSqrt
Reciprocal inverse square root.
int64_t GetNanoSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:367
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:661
#define REC_INV_SQRT_SHIFT
Time GetTarget(void)
Get the target queue delay.
#define DEFAULT_CODEL_LIMIT
void NewtonStep(void)
Calculate the reciprocal square root of m_count by using Newton&#39;s method http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots m_recInvSqrt (new) = (m_recInvSqrt (old) / 2) * (3 - m_count * m_recInvSqrt^2)
A CoDel packet queue disc.
static const int CODEL_SHIFT
Number of bits discarded from the time representation.
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: nstime.h:1125
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:193
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:449
uint32_t m_state3
Number of times we enter drop state and drop the fist packet.
uint32_t Time2CoDel(Time t)
Return the unsigned 32-bit integer representation of the input Time object.
QueueDiscSizePolicy
Enumeration of the available policies to handle the queue disc size.
Definition: queue-disc.h:103
static TypeId GetTypeId(void)
Get the type ID.
bool CoDelTimeBeforeEq(uint32_t a, uint32_t b)
Check if CoDel time a is preceding or equal to b.
Used by queue discs with single internal queue.
Definition: queue-disc.h:105
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
static uint32_t ReciprocalDivide(uint32_t A, uint32_t R)
Performs a reciprocal divide, similar to the Linux kernel reciprocal_divide function.
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:623
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:477
void DropAfterDequeue(Ptr< const QueueDiscItem > item, const char *reason)
Perform the actions required when the queue disc is notified of a packet dropped after dequeue...
Definition: queue-disc.cc:760
uint32_t m_state1
Number of times packet sojourn goes above target for interval.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:256
static int64_t CoDelGetTime(void)
Returns the current time translated in CoDel time representation.
millisecond
Definition: nstime.h:115
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: uinteger.h:45
Use number of bytes for queue size.
Definition: queue-size.h:45
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
TracedValue< uint32_t > m_dropNext
Time to drop next packet.
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:603