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
GetTypeId(void)45 TypeId CobaltQueueDisc::GetTypeId (void)
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.",
53 QueueSizeValue (QueueSize (QueueSizeUnit::BYTES, 1500 * DEFAULT_COBALT_LIMIT)),
54 MakeQueueSizeAccessor (&QueueDisc::SetMaxSize,
55 &QueueDisc::GetMaxSize),
56 MakeQueueSizeChecker ())
57 .AddAttribute ("Interval",
58 "The Cobalt algorithm interval",
59 StringValue ("100ms"),
60 MakeTimeAccessor (&CobaltQueueDisc::m_interval),
61 MakeTimeChecker ())
62 .AddAttribute ("Target",
63 "The Cobalt algorithm target queue delay",
64 StringValue ("5ms"),
65 MakeTimeAccessor (&CobaltQueueDisc::m_target),
66 MakeTimeChecker ())
67 .AddAttribute ("UseEcn",
68 "True to use ECN (packets are marked instead of being dropped)",
69 BooleanValue (false),
70 MakeBooleanAccessor (&CobaltQueueDisc::m_useEcn),
71 MakeBooleanChecker ())
72 .AddAttribute ("Pdrop",
73 "Marking Probability",
74 DoubleValue (0),
75 MakeDoubleAccessor (&CobaltQueueDisc::m_pDrop),
76 MakeDoubleChecker<double> ())
77 .AddAttribute ("Increment",
78 "Pdrop increment value",
79 DoubleValue (1. / 256),
80 MakeDoubleAccessor (&CobaltQueueDisc::m_increment),
81 MakeDoubleChecker<double> ())
82 .AddAttribute ("Decrement",
83 "Pdrop decrement Value",
84 DoubleValue (1. / 4096),
85 MakeDoubleAccessor (&CobaltQueueDisc::m_decrement),
86 MakeDoubleChecker<double> ())
87 .AddAttribute ("CeThreshold",
88 "The CoDel CE threshold for marking packets",
89 TimeValue (Time::Max ()),
90 MakeTimeAccessor (&CobaltQueueDisc::m_ceThreshold),
91 MakeTimeChecker ())
92 .AddAttribute ("UseL4s",
93 "True to use L4S (only ECT1 packets are marked at CE threshold)",
94 BooleanValue (false),
95 MakeBooleanAccessor (&CobaltQueueDisc::m_useL4s),
96 MakeBooleanChecker ())
97 .AddAttribute ("BlueThreshold",
98 "The Threshold after which Blue is enabled",
99 TimeValue (MilliSeconds (400)),
100 MakeTimeAccessor (&CobaltQueueDisc::m_blueThreshold),
101 MakeTimeChecker ())
102 .AddTraceSource ("Count",
103 "Cobalt count",
104 MakeTraceSourceAccessor (&CobaltQueueDisc::m_count),
105 "ns3::TracedValueCallback::Uint32")
106 .AddTraceSource ("DropState",
107 "Dropping state",
108 MakeTraceSourceAccessor (&CobaltQueueDisc::m_dropping),
109 "ns3::TracedValueCallback::Bool")
110 .AddTraceSource ("DropNext",
111 "Time until next packet drop",
112 MakeTraceSourceAccessor (&CobaltQueueDisc::m_dropNext),
113 "ns3::TracedValueCallback::Uint32")
114 ;
115
116 return tid;
117 }
118
119 /**
120 * Performs a reciprocal divide, similar to the
121 * Linux kernel reciprocal_divide function
122 * \param A numerator
123 * \param R reciprocal of the denominator B
124 * \return the value of A/B
125 */
126 /* borrowed from the linux kernel */
ReciprocalDivide(uint32_t A,uint32_t R)127 static inline uint32_t ReciprocalDivide (uint32_t A, uint32_t R)
128 {
129 return (uint32_t)(((uint64_t)A * R) >> 32);
130 }
131
min(double x,double y)132 double min (double x, double y)
133 {
134 return (x < y) ? x : y;
135 }
136
max(double x,double y)137 double max (double x, double y)
138 {
139 return (x > y) ? x : y;
140 }
141
142 /**
143 * Returns the current time translated in CoDel time representation
144 * \return the current time
145 */
CoDelGetTime(void)146 static int64_t CoDelGetTime (void)
147 {
148 Time time = Simulator::Now ();
149 int64_t ns = time.GetNanoSeconds ();
150
151 return ns;
152 }
153
CobaltQueueDisc()154 CobaltQueueDisc::CobaltQueueDisc ()
155 : QueueDisc ()
156 {
157 NS_LOG_FUNCTION (this);
158 InitializeParams ();
159 m_uv = CreateObject<UniformRandomVariable> ();
160 }
161
GetPdrop() const162 double CobaltQueueDisc::GetPdrop () const
163 {
164 return m_pDrop;
165 }
166
~CobaltQueueDisc()167 CobaltQueueDisc::~CobaltQueueDisc ()
168 {
169 NS_LOG_FUNCTION (this);
170 }
171
172 int64_t
AssignStreams(int64_t stream)173 CobaltQueueDisc::AssignStreams (int64_t stream)
174 {
175 NS_LOG_FUNCTION (this << stream);
176 m_uv->SetStream (stream);
177 return 1;
178 }
179
180 void
InitializeParams(void)181 CobaltQueueDisc::InitializeParams (void)
182 {
183 // Cobalt parameters
184 NS_LOG_FUNCTION (this);
185 m_recInvSqrtCache[0] = ~0;
186 CacheInit ();
187 m_count = 0;
188 m_dropping = false;
189 m_recInvSqrt = ~0U;
190 m_lastUpdateTimeBlue = 0;
191 m_dropNext = 0;
192 }
193
194 bool
CoDelTimeAfter(int64_t a,int64_t b)195 CobaltQueueDisc::CoDelTimeAfter (int64_t a, int64_t b)
196 {
197 return ((int64_t)(a) - (int64_t)(b) > 0);
198 }
199
200 bool
CoDelTimeAfterEq(int64_t a,int64_t b)201 CobaltQueueDisc::CoDelTimeAfterEq (int64_t a, int64_t b)
202 {
203 return ((int64_t)(a) - (int64_t)(b) >= 0);
204 }
205
206 int64_t
Time2CoDel(Time t) const207 CobaltQueueDisc::Time2CoDel (Time t) const
208 {
209 return (t.GetNanoSeconds ());
210 }
211
212 Time
GetTarget(void) const213 CobaltQueueDisc::GetTarget (void) const
214 {
215 return m_target;
216 }
217
218 Time
GetInterval(void) const219 CobaltQueueDisc::GetInterval (void) const
220 {
221 return m_interval;
222 }
223
224 int64_t
GetDropNext(void) const225 CobaltQueueDisc::GetDropNext (void) const
226 {
227 return m_dropNext;
228 }
229
230 void
NewtonStep(void)231 CobaltQueueDisc::NewtonStep (void)
232 {
233 NS_LOG_FUNCTION (this);
234 uint32_t invsqrt = ((uint32_t) m_recInvSqrt);
235 uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
236 uint64_t val = (3ll << 32) - ((uint64_t) m_count * invsqrt2);
237
238 val >>= 2; /* avoid overflow */
239 val = (val * invsqrt) >> (32 - 2 + 1);
240 m_recInvSqrt = val;
241 }
242
243 void
CacheInit(void)244 CobaltQueueDisc::CacheInit (void)
245 {
246 m_recInvSqrt = ~0U;
247 m_recInvSqrtCache[0] = m_recInvSqrt;
248
249 for (m_count = 1; m_count < (uint32_t)(REC_INV_SQRT_CACHE); m_count++)
250 {
251 NewtonStep ();
252 NewtonStep ();
253 NewtonStep ();
254 NewtonStep ();
255 m_recInvSqrtCache[m_count] = m_recInvSqrt;
256 }
257 }
258
259 void
InvSqrt(void)260 CobaltQueueDisc::InvSqrt (void)
261 {
262 if (m_count < (uint32_t)REC_INV_SQRT_CACHE)
263 {
264 m_recInvSqrt = m_recInvSqrtCache[m_count];
265 }
266 else
267 {
268 NewtonStep ();
269 }
270 }
271
272 int64_t
ControlLaw(int64_t t)273 CobaltQueueDisc::ControlLaw (int64_t t)
274 {
275 NS_LOG_FUNCTION (this);
276 return t + ReciprocalDivide (Time2CoDel (m_interval), m_recInvSqrt);
277 }
278
279 void
DoDispose(void)280 CobaltQueueDisc::DoDispose (void)
281 {
282 NS_LOG_FUNCTION (this);
283 m_uv = 0;
284 QueueDisc::DoDispose ();
285 }
286
287 Ptr<const QueueDiscItem>
DoPeek(void)288 CobaltQueueDisc::DoPeek (void)
289 {
290 NS_LOG_FUNCTION (this);
291 if (GetInternalQueue (0)->IsEmpty ())
292 {
293 NS_LOG_LOGIC ("Queue empty");
294 return 0;
295 }
296
297 Ptr<const QueueDiscItem> item = GetInternalQueue (0)->Peek ();
298
299 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
300 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
301
302 return item;
303 }
304
305 bool
CheckConfig(void)306 CobaltQueueDisc::CheckConfig (void)
307 {
308 NS_LOG_FUNCTION (this);
309 if (GetNQueueDiscClasses () > 0)
310 {
311 NS_LOG_ERROR ("CobaltQueueDisc cannot have classes");
312 return false;
313 }
314
315 if (GetNPacketFilters () > 0)
316 {
317 NS_LOG_ERROR ("CobaltQueueDisc cannot have packet filters");
318 return false;
319 }
320
321 if (GetNInternalQueues () == 0)
322 {
323
324 AddInternalQueue (CreateObjectWithAttributes<DropTailQueue<QueueDiscItem> >
325 ("MaxSize", QueueSizeValue (GetMaxSize ())));
326 }
327
328
329 if (GetNInternalQueues () != 1)
330 {
331 NS_LOG_ERROR ("CobaltQueueDisc needs 1 internal queue");
332 return false;
333 }
334 return true;
335 }
336
337 bool
DoEnqueue(Ptr<QueueDiscItem> item)338 CobaltQueueDisc::DoEnqueue (Ptr<QueueDiscItem> item)
339 {
340 NS_LOG_FUNCTION (this << item);
341 Ptr<Packet> p = item->GetPacket ();
342 if (GetCurrentSize () + item > GetMaxSize ())
343 {
344 NS_LOG_LOGIC ("Queue full -- dropping pkt");
345 int64_t now = CoDelGetTime ();
346 // Call this to update Blue's drop probability
347 CobaltQueueFull (now);
348 DropBeforeEnqueue (item, OVERLIMIT_DROP);
349 return false;
350 }
351
352 bool retval = GetInternalQueue (0)->Enqueue (item);
353
354 // If Queue::Enqueue fails, QueueDisc::Drop is called by the internal queue
355 // because QueueDisc::AddInternalQueue sets the drop callback
356
357 NS_LOG_LOGIC ("Number packets " << GetInternalQueue (0)->GetNPackets ());
358 NS_LOG_LOGIC ("Number bytes " << GetInternalQueue (0)->GetNBytes ());
359
360 return retval;
361 }
362
363 Ptr<QueueDiscItem>
DoDequeue(void)364 CobaltQueueDisc::DoDequeue (void)
365 {
366 NS_LOG_FUNCTION (this);
367
368 while (1)
369 {
370 Ptr<QueueDiscItem> item = GetInternalQueue (0)->Dequeue ();
371 if (!item)
372 {
373 // Leave dropping state when queue is empty (derived from Codel)
374 m_dropping = false;
375 NS_LOG_LOGIC ("Queue empty");
376 int64_t now = CoDelGetTime ();
377 // Call this to update Blue's drop probability
378 CobaltQueueEmpty (now);
379 return 0;
380 }
381
382 int64_t now = CoDelGetTime ();
383
384 NS_LOG_LOGIC ("Popped " << item);
385 NS_LOG_LOGIC ("Number packets remaining " << GetInternalQueue (0)->GetNPackets ());
386 NS_LOG_LOGIC ("Number bytes remaining " << GetInternalQueue (0)->GetNBytes ());
387
388 // Determine if item should be dropped
389 // ECN marking happens inside this function, so it need not be done here
390 bool drop = CobaltShouldDrop (item, now);
391
392 if (drop)
393 {
394 DropAfterDequeue (item, TARGET_EXCEEDED_DROP);
395 }
396 else
397 {
398 return item;
399 }
400 }
401 }
402
403 // Call this when a packet had to be dropped due to queue overflow.
CobaltQueueFull(int64_t now)404 void CobaltQueueDisc::CobaltQueueFull (int64_t now)
405 {
406 NS_LOG_FUNCTION (this);
407 NS_LOG_LOGIC ("Outside IF block");
408 if (CoDelTimeAfter ((now - m_lastUpdateTimeBlue), Time2CoDel (m_target)))
409 {
410 NS_LOG_LOGIC ("inside IF block");
411 m_pDrop = min (m_pDrop + m_increment, (double)1.0);
412 m_lastUpdateTimeBlue = now;
413 }
414 m_dropping = true;
415 m_dropNext = now;
416 if (!m_count)
417 {
418 m_count = 1;
419 }
420 }
421
422 // Call this when the queue was serviced but turned out to be empty.
CobaltQueueEmpty(int64_t now)423 void CobaltQueueDisc::CobaltQueueEmpty (int64_t now)
424 {
425 NS_LOG_FUNCTION (this);
426 if (m_pDrop && CoDelTimeAfter ((now - m_lastUpdateTimeBlue), Time2CoDel (m_target)))
427 {
428 m_pDrop = max (m_pDrop - m_decrement, (double)0.0);
429 m_lastUpdateTimeBlue = now;
430 }
431 m_dropping = false;
432
433 if (m_count && CoDelTimeAfterEq ((now - m_dropNext), 0))
434 {
435 m_count--;
436 InvSqrt ();
437 m_dropNext = ControlLaw (m_dropNext);
438 }
439 }
440
441 // Determines if Cobalt should drop the packet
CobaltShouldDrop(Ptr<QueueDiscItem> item,int64_t now)442 bool CobaltQueueDisc::CobaltShouldDrop (Ptr<QueueDiscItem> item, int64_t now)
443 {
444 NS_LOG_FUNCTION (this);
445 bool drop = false;
446
447 /* Simplified Codel implementation */
448 Time delta = Simulator::Now () - item->GetTimeStamp ();
449 NS_LOG_INFO ("Sojourn time " << delta.As (Time::S));
450 int64_t sojournTime = Time2CoDel (delta);
451 int64_t schedule = now - m_dropNext;
452 bool over_target = CoDelTimeAfter (sojournTime, Time2CoDel (m_target));
453 bool next_due = m_count && schedule >= 0;
454 bool isMarked = false;
455
456 // If L4S mode is enabled then check if the packet is ECT1 or CE and
457 // if sojourn time is greater than CE threshold then the packet is marked.
458 // If packet is marked succesfully then the CoDel steps can be skipped.
459 if (item && m_useL4s)
460 {
461 uint8_t tosByte = 0;
462 if (item->GetUint8Value (QueueItem::IP_DSFIELD, tosByte) && (((tosByte & 0x3) == 1) || (tosByte & 0x3) == 3))
463 {
464 if ((tosByte & 0x3) == 1)
465 {
466 NS_LOG_DEBUG ("ECT1 packet " << static_cast<uint16_t> (tosByte & 0x3));
467 }
468 else
469 {
470 NS_LOG_DEBUG ("CE packet " << static_cast<uint16_t> (tosByte & 0x3));
471 }
472 if (CoDelTimeAfter (sojournTime, Time2CoDel (m_ceThreshold)) && Mark (item, CE_THRESHOLD_EXCEEDED_MARK))
473 {
474 NS_LOG_LOGIC ("Marking due to CeThreshold " << m_ceThreshold.GetSeconds ());
475 }
476 return false;
477 }
478 }
479
480 if (over_target)
481 {
482 if (!m_dropping)
483 {
484 m_dropping = true;
485 m_dropNext = ControlLaw (now);
486 }
487 if (!m_count)
488 {
489 m_count = 1;
490 }
491 }
492 else if (m_dropping)
493 {
494 m_dropping = false;
495 }
496
497 if (next_due && m_dropping)
498 {
499 /* Check for marking possibility only if BLUE decides NOT to drop. */
500 /* Check if router and packet, both have ECN enabled. Only if this is true, mark the packet. */
501 isMarked = (m_useEcn && Mark (item, FORCED_MARK));
502 drop = !isMarked;
503
504 m_count = max (m_count, m_count + 1);
505
506 InvSqrt ();
507 m_dropNext = ControlLaw (m_dropNext);
508 schedule = now - m_dropNext;
509 }
510 else
511 {
512 while (next_due)
513 {
514 m_count--;
515 InvSqrt ();
516 m_dropNext = ControlLaw (m_dropNext);
517 schedule = now - m_dropNext;
518 next_due = m_count && schedule >= 0;
519 }
520 }
521
522 // If CE threshold is enabled then isMarked flag is used to determine whether
523 // packet is marked and if the packet is marked then a second attempt at marking should be suppressed.
524 // If UseL4S attribute is enabled then ECT0 packets should not be marked.
525 if (!isMarked && !m_useL4s && m_useEcn && CoDelTimeAfter (sojournTime, Time2CoDel (m_ceThreshold)) && Mark (item, CE_THRESHOLD_EXCEEDED_MARK))
526 {
527 NS_LOG_LOGIC ("Marking due to CeThreshold " << m_ceThreshold.GetSeconds ());
528 }
529
530 // Enable Blue Enhancement if sojourn time is greater than blueThreshold and its been m_target time until the last time blue was updated
531 if (CoDelTimeAfter (sojournTime, Time2CoDel (m_blueThreshold)) && CoDelTimeAfter ((now - m_lastUpdateTimeBlue), Time2CoDel (m_target)))
532 {
533 m_pDrop = min (m_pDrop + m_increment, (double)1.0);
534 m_lastUpdateTimeBlue = now;
535 }
536
537 /* Simple BLUE implementation. Lack of ECN is deliberate. */
538 if (m_pDrop)
539 {
540 double u = m_uv->GetValue ();
541 drop = drop | (u < m_pDrop);
542 }
543
544 /* Overload the drop_next field as an activity timeout */
545 if (!m_count)
546 {
547 m_dropNext = now + Time2CoDel (m_interval);
548 }
549 else if (schedule > 0 && !drop)
550 {
551 m_dropNext = now;
552 }
553
554 return drop;
555 }
556
557 } // namespace ns3
558