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 ("MinBytes",
58  "The Cobalt algorithm minbytes parameter.",
59  UintegerValue (1500),
61  MakeUintegerChecker<uint32_t> ())
62  .AddAttribute ("Interval",
63  "The Cobalt algorithm interval",
64  StringValue ("100ms"),
66  MakeTimeChecker ())
67  .AddAttribute ("Target",
68  "The Cobalt algorithm target queue delay",
69  StringValue ("5ms"),
71  MakeTimeChecker ())
72  .AddAttribute ("UseEcn",
73  "True to use ECN (packets are marked instead of being dropped)",
74  BooleanValue (false),
77  .AddAttribute ("Pdrop",
78  "Marking Probability",
79  DoubleValue (0),
81  MakeDoubleChecker<double> ())
82  .AddAttribute ("Increment",
83  "Pdrop increment value",
84  DoubleValue (1. / 256),
86  MakeDoubleChecker<double> ())
87  .AddAttribute ("Decrement",
88  "Pdrop decrement Value",
89  DoubleValue (1. / 4096),
91  MakeDoubleChecker<double> ())
92  .AddTraceSource ("Count",
93  "Cobalt count",
95  "ns3::TracedValueCallback::Uint32")
96  .AddTraceSource ("DropState",
97  "Dropping state",
99  "ns3::TracedValueCallback::Bool")
100  .AddTraceSource ("DropNext",
101  "Time until next packet drop",
103  "ns3::TracedValueCallback::Uint32")
104  ;
105 
106  return tid;
107 }
108 
116 /* borrowed from the linux kernel */
117 static inline uint32_t ReciprocalDivide (uint32_t A, uint32_t R)
118 {
119  return (uint32_t)(((uint64_t)A * R) >> 32);
120 }
121 
122 double min (double x, double y)
123 {
124  return (x < y) ? x : y;
125 }
126 
127 double max (double x, double y)
128 {
129  return (x > y) ? x : y;
130 }
131 
136 static int64_t CoDelGetTime (void)
137 {
138  Time time = Simulator::Now ();
139  int64_t ns = time.GetNanoSeconds ();
140 
141  return ns;
142 }
143 
145  : QueueDisc ()
146 {
147  NS_LOG_FUNCTION (this);
148  InitializeParams ();
149  m_uv = CreateObject<UniformRandomVariable> ();
150 }
151 
153 {
154  return m_Pdrop;
155 }
156 
158 {
159  NS_LOG_FUNCTION (this);
160 }
161 
162 int64_t
164 {
165  NS_LOG_FUNCTION (this << stream);
166  m_uv->SetStream (stream);
167  return 1;
168 }
169 
170 void
172 {
173  // Cobalt parameters
174  NS_LOG_FUNCTION (this);
175  m_recInvSqrtCache[0] = ~0;
176  CacheInit ();
177  m_count = 0;
178  m_dropping = false;
179  m_recInvSqrt = ~0U;
181  m_dropNext = 0;
182 }
183 
184 bool
185 CobaltQueueDisc::CoDelTimeAfter (int64_t a, int64_t b)
186 {
187  return ((int64_t)(a) - (int64_t)(b) > 0);
188 }
189 
190 bool
191 CobaltQueueDisc::CoDelTimeAfterEq (int64_t a, int64_t b)
192 {
193  return ((int64_t)(a) - (int64_t)(b) >= 0);
194 }
195 
196 int64_t
198 {
199  return (t.GetNanoSeconds ());
200 }
201 
202 Time
204 {
205  return m_target;
206 }
207 
208 Time
210 {
211  return m_interval;
212 }
213 
214 int64_t
216 {
217  return m_dropNext;
218 }
219 
220 void
222 {
223  NS_LOG_FUNCTION (this);
224  uint32_t invsqrt = ((uint32_t) m_recInvSqrt);
225  uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
226  uint64_t val = (3ll << 32) - ((uint64_t) m_count * invsqrt2);
227 
228  val >>= 2; /* avoid overflow */
229  val = (val * invsqrt) >> (32 - 2 + 1);
230  m_recInvSqrt = val;
231 }
232 
233 void
235 {
236  m_recInvSqrt = ~0U;
238 
239  for (m_count = 1; m_count < (uint32_t)(REC_INV_SQRT_CACHE); m_count++)
240  {
241  NewtonStep ();
242  NewtonStep ();
243  NewtonStep ();
244  NewtonStep ();
246  }
247 }
248 
249 void
251 {
252  if (m_count < (uint32_t)REC_INV_SQRT_CACHE)
253  {
255  }
256  else
257  {
258  NewtonStep ();
259  }
260 }
261 
262 int64_t
264 {
265  NS_LOG_FUNCTION (this);
267 }
268 
269 void
271 {
272  NS_LOG_FUNCTION (this);
273  m_uv = 0;
275 }
276 
279 {
280  NS_LOG_FUNCTION (this);
281  if (GetInternalQueue (0)->IsEmpty ())
282  {
283  NS_LOG_LOGIC ("Queue empty");
284  return 0;
285  }
286 
287  Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
288 
289  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
290  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
291 
292  return item;
293 }
294 
295 bool
297 {
298  NS_LOG_FUNCTION (this);
299  if (GetNQueueDiscClasses () > 0)
300  {
301  NS_LOG_ERROR ("CobaltQueueDisc cannot have classes");
302  return false;
303  }
304 
305  if (GetNPacketFilters () > 0)
306  {
307  NS_LOG_ERROR ("CobaltQueueDisc cannot have packet filters");
308  return false;
309  }
310 
311  if (GetNInternalQueues () == 0)
312  {
313 
315  ("MaxSize", QueueSizeValue (GetMaxSize ())));
316  }
317 
318 
319  if (GetNInternalQueues () != 1)
320  {
321  NS_LOG_ERROR ("CobaltQueueDisc needs 1 internal queue");
322  return false;
323  }
324  return true;
325 }
326 
327 bool
329 {
330  NS_LOG_FUNCTION (this << item);
331  Ptr<Packet> p = item->GetPacket ();
332  if (GetCurrentSize () + item > GetMaxSize ())
333  {
334  NS_LOG_LOGIC ("Queue full -- dropping pkt");
335  int64_t now = CoDelGetTime ();
336  // Call this to update Blue's drop probability
337  CobaltQueueFull (now);
339  return false;
340  }
341 
342  bool retval = GetInternalQueue (0)->Enqueue (item);
343 
344  // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue
345  // because QueueDisc::AddInternalQueue sets the drop callback
346 
347  NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
348  NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
349 
350  return retval;
351 }
352 
355 {
356  NS_LOG_FUNCTION (this);
357 
358  while (1)
359  {
360  Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
361  if (!item)
362  {
363  // Leave dropping state when queue is empty (derived from Codel)
364  m_dropping = false;
365  NS_LOG_LOGIC ("Queue empty");
366  int64_t now = CoDelGetTime ();
367  // Call this to update Blue's drop probability
368  CobaltQueueEmpty (now);
369  return 0;
370  }
371 
372  int64_t now = CoDelGetTime ();
373 
374  NS_LOG_LOGIC ("Popped " << item);
375  NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
376  NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
377 
378  // Determine if item should be dropped
379  // ECN marking happens inside this function, so it need not be done here
380  bool drop = CobaltShouldDrop (item, now);
381 
382  if (drop)
383  {
385  }
386  else
387  {
388  return item;
389  }
390  }
391 }
392 
393 // Call this when a packet had to be dropped due to queue overflow.
395 {
396  NS_LOG_FUNCTION (this);
397  NS_LOG_LOGIC ("Outside IF block");
399  {
400  NS_LOG_LOGIC ("inside IF block");
401  m_Pdrop = min (m_Pdrop + m_increment, (double)1.0);
402  m_lastUpdateTimeBlue = now;
403  }
404  m_dropping = true;
405  m_dropNext = now;
406  if (!m_count)
407  {
408  m_count = 1;
409  }
410 }
411 
412 // Call this when the queue was serviced but turned out to be empty.
414 {
415  NS_LOG_FUNCTION (this);
417  {
418  m_Pdrop = max (m_Pdrop - m_decrement, (double)0.0);
419  m_lastUpdateTimeBlue = now;
420  }
421  m_dropping = false;
422 
423  if (m_count && CoDelTimeAfterEq ((now - m_dropNext), 0))
424  {
425  m_count--;
426  InvSqrt ();
428  }
429 }
430 
431 // Determines if Cobalt should drop the packet
433 {
434  NS_LOG_FUNCTION (this);
435  bool drop = false;
436 
437  /* Simplified Codel implementation */
438  Time delta = Simulator::Now () - item->GetTimeStamp ();
439  NS_LOG_INFO ("Sojourn time " << delta.GetSeconds ());
440  int64_t sojournTime = Time2CoDel (delta);
441  int64_t schedule = now - m_dropNext;
442  bool over_target = CoDelTimeAfter (sojournTime, Time2CoDel (m_target));
443  bool next_due = m_count && schedule >= 0;
444 
445  if (over_target)
446  {
447  if (!m_dropping)
448  {
449  m_dropping = true;
450  m_dropNext = ControlLaw (now);
451  }
452  if (!m_count)
453  {
454  m_count = 1;
455  }
456  }
457  else if (m_dropping)
458  {
459  m_dropping = false;
460  }
461 
462  if (next_due && m_dropping)
463  {
464  /* Check for marking possibility only if BLUE decides NOT to drop. */
465  /* Check if router and packet, both have ECN enabled. Only if this is true, mark the packet. */
466  drop = !(m_useEcn && Mark (item, FORCED_MARK));
467 
468  m_count = max (m_count, m_count + 1);
469 
470  InvSqrt ();
472  schedule = now - m_dropNext;
473  }
474  else
475  {
476  while (next_due)
477  {
478  m_count--;
479  InvSqrt ();
481  schedule = now - m_dropNext;
482  next_due = m_count && schedule >= 0;
483  }
484  }
485  /* Simple BLUE implementation. Lack of ECN is deliberate. */
486  if (m_Pdrop)
487  {
488  double u = m_uv->GetValue ();
489  drop = drop | (u < m_Pdrop);
490  }
491 
492  /* Overload the drop_next field as an activity timeout */
493  if (!m_count)
494  {
495  m_dropNext = now + Time2CoDel (m_interval);
496  }
497  else if (schedule > 0 && !drop)
498  {
499  m_dropNext = now;
500  }
501 
502  return drop;
503 }
504 
505 } // 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:102
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:84
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:355
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:204
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:280
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.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
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.
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
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
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.
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
Hold an unsigned integer type.
Definition: uinteger.h:44
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.
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
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:367
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.
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
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: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: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
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)
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:256
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.
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
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