A Discrete-Event Network Simulator
API
cobalt-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) 2019 NITK Surathkal
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  * Cobalt, the CoDel - BLUE - Alternate Queueing discipline
19  * Based on linux code.
20  *
21  * Ported to ns-3 by: Vignesh Kannan <vignesh2496@gmail.com>
22  * Harsh Lara <harshapplefan@gmail.com>
23  * Jendaipou Palmei <jendaipoupalmei@gmail.com>
24  * Shefali Gupta <shefaligups11@gmail.com>
25  * Mohit P. Tahiliani <tahiliani@nitk.edu.in>
26  */
27 
28 #include "ns3/log.h"
29 #include "ns3/enum.h"
30 #include "ns3/uinteger.h"
31 #include "ns3/abort.h"
32 #include "cobalt-queue-disc.h"
33 #include "ns3/object-factory.h"
34 #include "ns3/drop-tail-queue.h"
35 #include "ns3/net-device-queue-interface.h"
36 #include <climits>
37 
38 
39 namespace ns3 {
40 
41 NS_LOG_COMPONENT_DEFINE ("CobaltQueueDisc");
42 
43 NS_OBJECT_ENSURE_REGISTERED (CobaltQueueDisc);
44 
46 {
47  static TypeId tid = TypeId ("ns3::CobaltQueueDisc")
48  .SetParent<QueueDisc> ()
49  .SetGroupName ("TrafficControl")
50  .AddConstructor<CobaltQueueDisc> ()
51  .AddAttribute ("MaxSize",
52  "The maximum number of packets/bytes accepted by this queue disc.",
57  .AddAttribute ("Interval",
58  "The Cobalt algorithm interval",
59  StringValue ("100ms"),
61  MakeTimeChecker ())
62  .AddAttribute ("Target",
63  "The Cobalt algorithm target queue delay",
64  StringValue ("5ms"),
66  MakeTimeChecker ())
67  .AddAttribute ("UseEcn",
68  "True to use ECN (packets are marked instead of being dropped)",
69  BooleanValue (false),
72  .AddAttribute ("Pdrop",
73  "Marking Probability",
74  DoubleValue (0),
76  MakeDoubleChecker<double> ())
77  .AddAttribute ("Increment",
78  "Pdrop increment value",
79  DoubleValue (1. / 256),
81  MakeDoubleChecker<double> ())
82  .AddAttribute ("Decrement",
83  "Pdrop decrement Value",
84  DoubleValue (1. / 4096),
86  MakeDoubleChecker<double> ())
87  .AddTraceSource ("Count",
88  "Cobalt count",
90  "ns3::TracedValueCallback::Uint32")
91  .AddTraceSource ("DropState",
92  "Dropping state",
94  "ns3::TracedValueCallback::Bool")
95  .AddTraceSource ("DropNext",
96  "Time until next packet drop",
98  "ns3::TracedValueCallback::Uint32")
99  ;
100 
101  return tid;
102 }
103 
111 /* borrowed from the linux kernel */
112 static inline uint32_t ReciprocalDivide (uint32_t A, uint32_t R)
113 {
114  return (uint32_t)(((uint64_t)A * R) >> 32);
115 }
116 
117 double min (double x, double y)
118 {
119  return (x < y) ? x : y;
120 }
121 
122 double max (double x, double y)
123 {
124  return (x > y) ? x : y;
125 }
126 
131 static int64_t CoDelGetTime (void)
132 {
133  Time time = Simulator::Now ();
134  int64_t ns = time.GetNanoSeconds ();
135 
136  return ns;
137 }
138 
140  : QueueDisc ()
141 {
142  NS_LOG_FUNCTION (this);
143  InitializeParams ();
144  m_uv = CreateObject<UniformRandomVariable> ();
145 }
146 
148 {
149  return m_Pdrop;
150 }
151 
153 {
154  NS_LOG_FUNCTION (this);
155 }
156 
157 int64_t
159 {
160  NS_LOG_FUNCTION (this << stream);
161  m_uv->SetStream (stream);
162  return 1;
163 }
164 
165 void
167 {
168  // Cobalt parameters
169  NS_LOG_FUNCTION (this);
170  m_recInvSqrtCache[0] = ~0;
171  CacheInit ();
172  m_count = 0;
173  m_dropping = false;
174  m_recInvSqrt = ~0U;
176  m_dropNext = 0;
177 }
178 
179 bool
180 CobaltQueueDisc::CoDelTimeAfter (int64_t a, int64_t b)
181 {
182  return ((int64_t)(a) - (int64_t)(b) > 0);
183 }
184 
185 bool
186 CobaltQueueDisc::CoDelTimeAfterEq (int64_t a, int64_t b)
187 {
188  return ((int64_t)(a) - (int64_t)(b) >= 0);
189 }
190 
191 int64_t
193 {
194  return (t.GetNanoSeconds ());
195 }
196 
197 Time
199 {
200  return m_target;
201 }
202 
203 Time
205 {
206  return m_interval;
207 }
208 
209 int64_t
211 {
212  return m_dropNext;
213 }
214 
215 void
217 {
218  NS_LOG_FUNCTION (this);
219  uint32_t invsqrt = ((uint32_t) m_recInvSqrt);
220  uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
221  uint64_t val = (3ll << 32) - ((uint64_t) m_count * invsqrt2);
222 
223  val >>= 2; /* avoid overflow */
224  val = (val * invsqrt) >> (32 - 2 + 1);
225  m_recInvSqrt = val;
226 }
227 
228 void
230 {
231  m_recInvSqrt = ~0U;
233 
234  for (m_count = 1; m_count < (uint32_t)(REC_INV_SQRT_CACHE); m_count++)
235  {
236  NewtonStep ();
237  NewtonStep ();
238  NewtonStep ();
239  NewtonStep ();
241  }
242 }
243 
244 void
246 {
247  if (m_count < (uint32_t)REC_INV_SQRT_CACHE)
248  {
250  }
251  else
252  {
253  NewtonStep ();
254  }
255 }
256 
257 int64_t
259 {
260  NS_LOG_FUNCTION (this);
262 }
263 
264 void
266 {
267  NS_LOG_FUNCTION (this);
268  m_uv = 0;
270 }
271 
274 {
275  NS_LOG_FUNCTION (this);
276  if (GetInternalQueue (0)->IsEmpty ())
277  {
278  NS_LOG_LOGIC ("Queue empty");
279  return 0;
280  }
281 
282  Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
283 
284  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
285  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
286 
287  return item;
288 }
289 
290 bool
292 {
293  NS_LOG_FUNCTION (this);
294  if (GetNQueueDiscClasses () > 0)
295  {
296  NS_LOG_ERROR ("CobaltQueueDisc cannot have classes");
297  return false;
298  }
299 
300  if (GetNPacketFilters () > 0)
301  {
302  NS_LOG_ERROR ("CobaltQueueDisc cannot have packet filters");
303  return false;
304  }
305 
306  if (GetNInternalQueues () == 0)
307  {
308 
310  ("MaxSize", QueueSizeValue (GetMaxSize ())));
311  }
312 
313 
314  if (GetNInternalQueues () != 1)
315  {
316  NS_LOG_ERROR ("CobaltQueueDisc needs 1 internal queue");
317  return false;
318  }
319  return true;
320 }
321 
322 bool
324 {
325  NS_LOG_FUNCTION (this << item);
326  Ptr<Packet> p = item->GetPacket ();
327  if (GetCurrentSize () + item > GetMaxSize ())
328  {
329  NS_LOG_LOGIC ("Queue full -- dropping pkt");
330  int64_t now = CoDelGetTime ();
331  // Call this to update Blue's drop probability
332  CobaltQueueFull (now);
334  return false;
335  }
336 
337  bool retval = GetInternalQueue (0)->Enqueue (item);
338 
339  // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue
340  // because QueueDisc::AddInternalQueue sets the drop callback
341 
342  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
343  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
344 
345  return retval;
346 }
347 
350 {
351  NS_LOG_FUNCTION (this);
352 
353  while (1)
354  {
355  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
356  if (!item)
357  {
358  // Leave dropping state when queue is empty (derived from Codel)
359  m_dropping = false;
360  NS_LOG_LOGIC ("Queue empty");
361  int64_t now = CoDelGetTime ();
362  // Call this to update Blue's drop probability
363  CobaltQueueEmpty (now);
364  return 0;
365  }
366 
367  int64_t now = CoDelGetTime ();
368 
369  NS_LOG_LOGIC ("Popped " << item);
370  NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
371  NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
372 
373  // Determine if item should be dropped
374  // ECN marking happens inside this function, so it need not be done here
375  bool drop = CobaltShouldDrop (item, now);
376 
377  if (drop)
378  {
380  }
381  else
382  {
383  return item;
384  }
385  }
386 }
387 
388 // Call this when a packet had to be dropped due to queue overflow.
390 {
391  NS_LOG_FUNCTION (this);
392  NS_LOG_LOGIC ("Outside IF block");
394  {
395  NS_LOG_LOGIC ("inside IF block");
396  m_Pdrop = min (m_Pdrop + m_increment, (double)1.0);
397  m_lastUpdateTimeBlue = now;
398  }
399  m_dropping = true;
400  m_dropNext = now;
401  if (!m_count)
402  {
403  m_count = 1;
404  }
405 }
406 
407 // Call this when the queue was serviced but turned out to be empty.
409 {
410  NS_LOG_FUNCTION (this);
412  {
413  m_Pdrop = max (m_Pdrop - m_decrement, (double)0.0);
414  m_lastUpdateTimeBlue = now;
415  }
416  m_dropping = false;
417 
418  if (m_count && CoDelTimeAfterEq ((now - m_dropNext), 0))
419  {
420  m_count--;
421  InvSqrt ();
423  }
424 }
425 
426 // Determines if Cobalt should drop the packet
428 {
429  NS_LOG_FUNCTION (this);
430  bool drop = false;
431 
432  /* Simplified Codel implementation */
433  Time delta = Simulator::Now () - item->GetTimeStamp ();
434  NS_LOG_INFO ("Sojourn time " << delta.GetSeconds ());
435  int64_t sojournTime = Time2CoDel (delta);
436  int64_t schedule = now - m_dropNext;
437  bool over_target = CoDelTimeAfter (sojournTime, Time2CoDel (m_target));
438  bool next_due = m_count && schedule >= 0;
439 
440  if (over_target)
441  {
442  if (!m_dropping)
443  {
444  m_dropping = true;
445  m_dropNext = ControlLaw (now);
446  }
447  if (!m_count)
448  {
449  m_count = 1;
450  }
451  }
452  else if (m_dropping)
453  {
454  m_dropping = false;
455  }
456 
457  if (next_due && m_dropping)
458  {
459  /* Check for marking possibility only if BLUE decides NOT to drop. */
460  /* Check if router and packet, both have ECN enabled. Only if this is true, mark the packet. */
461  drop = !(m_useEcn && Mark (item, FORCED_MARK));
462 
463  m_count = max (m_count, m_count + 1);
464 
465  InvSqrt ();
467  schedule = now - m_dropNext;
468  }
469  else
470  {
471  while (next_due)
472  {
473  m_count--;
474  InvSqrt ();
476  schedule = now - m_dropNext;
477  next_due = m_count && schedule >= 0;
478  }
479  }
480  /* Simple BLUE implementation. Lack of ECN is deliberate. */
481  if (m_Pdrop)
482  {
483  double u = m_uv->GetValue ();
484  drop = drop | (u < m_Pdrop);
485  }
486 
487  /* Overload the drop_next field as an activity timeout */
488  if (!m_count)
489  {
490  m_dropNext = now + Time2CoDel (m_interval);
491  }
492  else if (schedule > 0 && !drop)
493  {
494  m_dropNext = now;
495  }
496 
497  return drop;
498 }
499 
500 } // namespace ns3
bool CoDelTimeAfter(int64_t a, int64_t b)
Check if CoDel time a is successive to b.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
uint32_t GetNPackets(void) const
Get the number of packets stored by the queue disc.
Definition: queue-disc.cc:440
double m_Pdrop
Drop Probability.
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 "...
void SetStream(int64_t stream)
Specifies the stream number for the RngStream.
AttributeValue implementation for Boolean.
Definition: boolean.h:36
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:729
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
CobaltQueueDisc()
CobaltQueueDisc Constructor.
Hold variables of type string.
Definition: string.h:41
bool Mark(Ptr< QueueDiscItem > item, const char *reason)
Marks the given packet and, if successful, updates the counters associated with the given reason...
Definition: queue-disc.cc:818
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:523
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: boolean.h:85
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:379
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
int64_t Time2CoDel(Time t)
Return the unsigned 32-bit integer representation of the input Time object.
uint32_t GetNBytes(void) const
Get the amount of bytes stored by the queue disc.
Definition: queue-disc.cc:447
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
int64_t AssignStreams(int64_t stream)
Assign a fixed random variable stream number to the random variables used by this model...
static TypeId GetTypeId(void)
Get the type ID.
bool CoDelTimeAfterEq(int64_t a, int64_t b)
Check if CoDel time a is successive or equal to b.
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition: queue-disc.h:181
void CobaltQueueFull(int64_t now)
Called when the queue becomes full to alter the drop probabilities of Blue.
Time GetInterval(void)
Get the interval.
TracedValue< int64_t > m_dropNext
Time to drop next packet.
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
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)
#define DEFAULT_COBALT_LIMIT
int64_t GetDropNext(void)
Get the time for next packet drop while in the dropping state.
virtual ~CobaltQueueDisc()
Destructor.
void AddInternalQueue(Ptr< InternalQueue > queue)
Add an internal queue to the tail of the list of queues.
Definition: queue-disc.cc:581
int64_t ControlLaw(int64_t t)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
void CobaltQueueEmpty(int64_t now)
Called when the queue becomes empty to alter the drop probabilities of Blue.
Ptr< InternalQueue > GetInternalQueue(std::size_t i) const
Get the i-th internal queue.
Definition: queue-disc.cc:601
static constexpr const char * FORCED_MARK
forced marks by Codel on ECN-enabled
double m_increment
increment value for marking probability
Cobalt packet queue disc.
Ptr< const AttributeAccessor > MakeQueueSizeAccessor(T1 a1)
Definition: queue-size.h:221
TracedValue< uint32_t > m_count
Number of packets dropped since entering drop state.
virtual void DoDispose(void)
Dispose of the object.
Definition: queue-disc.cc:383
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
Introspection did not find any typical Config paths.
Ptr< const AttributeChecker > MakeQueueSizeChecker(void)
Definition: queue-size.cc:29
Ptr< T > CreateObjectWithAttributes(Args... args)
Allocate an Object on the heap and initialize with a set of attributes.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< UniformRandomVariable > m_uv
Rng stream.
int64_t GetNanoSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:391
std::size_t GetNQueueDiscClasses(void) const
Get the number of queue disc classes.
Definition: queue-disc.cc:669
TracedValue< bool > m_dropping
True if in dropping state.
double GetValue(double min, double max)
Get the next random value, as a double in the specified range .
virtual void DoDispose(void)
Dispose of the object.
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:1343
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
QueueSize GetMaxSize(void) const
Get the maximum size of the queue disc.
Definition: queue-disc.cc:454
uint32_t m_recInvSqrtCache[REC_INV_SQRT_CACHE]
Cache to maintain some initial values of InvSqrt.
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method...
Definition: double.h:42
double max(double x, double y)
virtual Ptr< const QueueDiscItem > DoPeek(void)
Return a copy of the next packet the queue disc will extract.
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
This function actually enqueues a packet into the queue disc.
Time m_target
5 ms target queue delay
virtual void InitializeParams(void)
Initialize the queue parameters.
static uint32_t ReciprocalDivide(uint32_t A, uint32_t R)
Performs a reciprocal divide, similar to the Linux kernel reciprocal_divide function.
bool CobaltShouldDrop(Ptr< QueueDiscItem > item, int64_t now)
Called to decide whether the current packet should be dropped based on decisions taken by Blue and Co...
std::size_t GetNPacketFilters(void) const
Get the number of packet filters.
Definition: queue-disc.cc:628
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
bool SetMaxSize(QueueSize size)
Set the maximum size of the queue disc.
Definition: queue-disc.cc:482
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:768
double min(double x, double y)
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:449
double m_decrement
decrement value for marking probability
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Definition: log.h:257
double GetPdrop()
Get the drop probability of Blue.
uint32_t m_lastUpdateTimeBlue
Blue&#39;s last update time for drop probability.
static int64_t CoDelGetTime(void)
Returns the current time translated in CoDel time representation.
virtual Ptr< QueueDiscItem > DoDequeue(void)
This function actually extracts a packet from the queue disc.
#define REC_INV_SQRT_CACHE
This class can be used to hold variables of floating point type such as &#39;double&#39; or &#39;float&#39;...
Definition: double.h:41
Time GetTarget(void)
Get the target queue delay.
uint32_t m_recInvSqrt
Reciprocal inverse square root.
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:923
std::size_t GetNInternalQueues(void) const
Get the number of internal queues.
Definition: queue-disc.cc:608
void CacheInit(void)
There is a big difference in timing between the accurate values placed in the cache and the approxima...
Time m_interval
100 ms sliding minimum time window width