A Discrete-Event Network Simulator
API
codel-queue-disc.h
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 #ifndef CODEL_H
29 #define CODEL_H
30 
31 #include "ns3/queue-disc.h"
32 #include "ns3/nstime.h"
33 #include "ns3/simulator.h"
34 #include "ns3/string.h"
35 #include "ns3/traced-value.h"
36 #include "ns3/trace-source-accessor.h"
37 
38 class CoDelQueueDiscNewtonStepTest; // Forward declaration for unit test
39 class CoDelQueueDiscControlLawTest; // Forward declaration for unit test
40 
41 namespace ns3 {
42 
47 static const int CODEL_SHIFT = 10;
48 
49 #define DEFAULT_CODEL_LIMIT 1000
50 #define REC_INV_SQRT_BITS (8 * sizeof(uint16_t))
51 #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
52 
53 class TraceContainer;
54 
61 class CoDelQueueDisc : public QueueDisc
62 {
63 public:
69  static TypeId GetTypeId (void);
70 
76  CoDelQueueDisc ();
77 
78  virtual ~CoDelQueueDisc ();
79 
85  Time GetTarget (void);
86 
92  Time GetInterval (void);
93 
99  uint32_t GetDropNext (void);
100 
101  // Reasons for dropping packets
102  static constexpr const char* TARGET_EXCEEDED_DROP = "Target exceeded drop";
103  static constexpr const char* OVERLIMIT_DROP = "Overlimit drop";
104  // Reasons for marking packets
105  static constexpr const char* TARGET_EXCEEDED_MARK = "Target exceeded mark";
106  static constexpr const char* CE_THRESHOLD_EXCEEDED_MARK = "CE threshold exceeded mark";
107 
108 private:
109  friend class::CoDelQueueDiscNewtonStepTest; // Test code
110  friend class::CoDelQueueDiscControlLawTest; // Test code
117  virtual bool DoEnqueue (Ptr<QueueDiscItem> item);
118 
128  virtual Ptr<QueueDiscItem> DoDequeue (void);
129 
130  virtual bool CheckConfig (void);
131 
140  static uint16_t NewtonStep (uint16_t recInvSqrt, uint32_t count);
141 
153  static uint32_t ControlLaw (uint32_t t, uint32_t interval, uint32_t recInvSqrt);
154 
163  bool OkToDrop (Ptr<QueueDiscItem> item, uint32_t now);
164 
171  bool CoDelTimeAfter (uint32_t a, uint32_t b);
178  bool CoDelTimeAfterEq (uint32_t a, uint32_t b);
185  bool CoDelTimeBefore (uint32_t a, uint32_t b);
192  bool CoDelTimeBeforeEq (uint32_t a, uint32_t b);
193 
200  uint32_t Time2CoDel (Time t);
201 
202  virtual void InitializeParams (void);
203 
204  bool m_useEcn;
205  bool m_useL4s;
206  uint32_t m_minBytes;
213  uint16_t m_recInvSqrt;
214  uint32_t m_firstAboveTime;
216 };
217 
218 } // namespace ns3
219 
220 #endif /* CODEL_H */
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:103
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
Add a packet to the queue.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
static constexpr const char * TARGET_EXCEEDED_DROP
Sojourn time above target.
static uint32_t ControlLaw(uint32_t t, uint32_t interval, uint32_t recInvSqrt)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
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.
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.
Test 3: NewtonStep unit test - test against explicit port of Linux implementation.
bool CoDelTimeAfterEq(uint32_t a, uint32_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
static uint16_t NewtonStep(uint16_t recInvSqrt, uint32_t count)
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)
bool CoDelTimeAfter(uint32_t a, uint32_t b)
Check if CoDel time a is successive to b.
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.
uint32_t m_firstAboveTime
Time to declare sojourn time above target.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
bool CoDelTimeBefore(uint32_t a, uint32_t b)
Check if CoDel time a is preceding b.
Time m_target
5 ms target queue delay
CoDelQueueDisc()
CoDelQueueDisc Constructor.
TracedValue< uint32_t > m_lastCount
Last number of packets dropped since entering drop state.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
Time m_interval
100 ms sliding minimum time window width
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.
Time GetTarget(void)
Get the target queue delay.
A CoDel packet queue disc.
static const int CODEL_SHIFT
Number of bits discarded from the time representation.
uint32_t Time2CoDel(Time t)
Return the unsigned 32-bit integer representation of the input Time object.
static constexpr const char * TARGET_EXCEEDED_MARK
Sojourn time above target.
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.
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
Test 4: ControlLaw unit test - test against explicit port of Linux implementation.
a unique identifier for an interface.
Definition: type-id.h:58
Time m_ceThreshold
Threshold above which to CE mark.
TracedValue< uint32_t > m_dropNext
Time to drop next packet.