A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
codel-queue-disc.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2012 Andrew McGregor
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Codel, the COntrolled DELay Queueing discipline
7 * Based on ns2 simulation code presented by Kathie Nichols
8 *
9 * This port based on linux kernel code by
10 * Authors:
11 * Dave Täht <d@taht.net>
12 * Eric Dumazet <edumazet@google.com>
13 *
14 * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
15 */
16
17#ifndef CODEL_H
18#define CODEL_H
19
20#include "queue-disc.h"
21
22#include "ns3/nstime.h"
23#include "ns3/simulator.h"
24#include "ns3/string.h"
25#include "ns3/trace-source-accessor.h"
26#include "ns3/traced-value.h"
27
28class CoDelQueueDiscNewtonStepTest; // Forward declaration for unit test
29class CoDelQueueDiscControlLawTest; // Forward declaration for unit test
30
31namespace ns3
32{
33
34/**
35 * Number of bits discarded from the time representation.
36 * The time is assumed to be in nanoseconds.
37 */
38static const int CODEL_SHIFT = 10;
39
40#define DEFAULT_CODEL_LIMIT 1000
41#define REC_INV_SQRT_BITS (8 * sizeof(uint16_t))
42#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
43
44class TraceContainer;
45
46/**
47 * \ingroup traffic-control
48 *
49 * \brief A CoDel packet queue disc
50 */
51
53{
54 public:
55 /**
56 * Get the type ID.
57 * \brief Get the type ID.
58 * \return the object TypeId
59 */
60 static TypeId GetTypeId();
61
62 /**
63 * \brief CoDelQueueDisc Constructor
64 *
65 * Creates a CoDel queue
66 */
68
69 ~CoDelQueueDisc() override;
70
71 /**
72 * \brief Get the target queue delay
73 *
74 * \returns The target queue delay
75 */
77
78 /**
79 * \brief Get the interval
80 *
81 * \returns The interval
82 */
84
85 /**
86 * \brief Get the time for next packet drop while in the dropping state
87 *
88 * \returns The time for next packet drop
89 */
91
92 // Reasons for dropping packets
93 static constexpr const char* TARGET_EXCEEDED_DROP =
94 "Target exceeded drop"; //!< Sojourn time above target
95 static constexpr const char* OVERLIMIT_DROP = "Overlimit drop"; //!< Overlimit dropped packet
96 // Reasons for marking packets
97 static constexpr const char* TARGET_EXCEEDED_MARK =
98 "Target exceeded mark"; //!< Sojourn time above target
99 static constexpr const char* CE_THRESHOLD_EXCEEDED_MARK =
100 "CE threshold exceeded mark"; //!< Sojourn time above CE threshold
101
102 private:
103 friend class ::CoDelQueueDiscNewtonStepTest; // Test code
104 friend class ::CoDelQueueDiscControlLawTest; // Test code
105 /**
106 * \brief Add a packet to the queue
107 *
108 * \param item The item to be added
109 * \returns True if the packet can be added, False if the packet is dropped due to full queue
110 */
111 bool DoEnqueue(Ptr<QueueDiscItem> item) override;
112
113 /**
114 * \brief Remove a packet from queue based on the current state
115 * If we are in dropping state, check if we could leave the dropping state
116 * or if we should perform next drop
117 * If we are not currently in dropping state, check if we need to enter the state
118 * and drop the first packet
119 *
120 * \returns The packet that is examined
121 */
122 Ptr<QueueDiscItem> DoDequeue() override;
123
124 bool CheckConfig() override;
125
126 /**
127 * \brief Calculate the reciprocal square root of m_count by using Newton's method
128 * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
129 * m_recInvSqrt (new) = (m_recInvSqrt (old) / 2) * (3 - m_count * m_recInvSqrt^2)
130 * \param recInvSqrt reciprocal value of sqrt (count)
131 * \param count count value
132 * \return The new recInvSqrt value
133 */
134 static uint16_t NewtonStep(uint16_t recInvSqrt, uint32_t count);
135
136 /**
137 * \brief Determine the time for next drop
138 * CoDel control law is t + m_interval/sqrt(m_count).
139 * Here, we use m_recInvSqrt calculated by Newton's method in NewtonStep() to avoid
140 * both sqrt() and divide operations
141 *
142 * \param t Current next drop time (in units of CoDel time)
143 * \param interval interval (in units of CoDel time)
144 * \param recInvSqrt reciprocal value of sqrt (count)
145 * \return The new next drop time (in units of CoDel time)
146 */
147 static uint32_t ControlLaw(uint32_t t, uint32_t interval, uint32_t recInvSqrt);
148
149 /**
150 * \brief Determine whether a packet is OK to be dropped. The packet
151 * may not be actually dropped (depending on the drop state)
152 *
153 * \param item The packet that is considered
154 * \param now The current time represented as 32-bit unsigned integer (us)
155 * \returns True if it is OK to drop the packet (sojourn time above target for at least
156 * interval)
157 */
158 bool OkToDrop(Ptr<QueueDiscItem> item, uint32_t now);
159
160 /**
161 * Check if CoDel time a is successive to b
162 * @param a left operand
163 * @param b right operand
164 * @return true if a is greater than b
165 */
167 /**
168 * Check if CoDel time a is successive or equal to b
169 * @param a left operand
170 * @param b right operand
171 * @return true if a is greater than or equal to b
172 */
174 /**
175 * Check if CoDel time a is preceding b
176 * @param a left operand
177 * @param b right operand
178 * @return true if a is less than to b
179 */
181 /**
182 * Check if CoDel time a is preceding or equal to b
183 * @param a left operand
184 * @param b right operand
185 * @return true if a is less than or equal to b
186 */
188
189 /**
190 * Return the unsigned 32-bit integer representation of the input Time
191 * object. Units are microseconds
192 * @param t the input Time Object
193 * @return the unsigned 32-bit integer representation
194 */
196
197 void InitializeParams() override;
198
199 bool m_useEcn; //!< True if ECN is used (packets are marked instead of being dropped)
200 bool m_useL4s; //!< True if L4S is used (ECT1 packets are marked at CE threshold)
201 uint32_t m_minBytes; //!< Minimum bytes in queue to allow a packet drop
202 Time m_interval; //!< 100 ms sliding minimum time window width
203 Time m_target; //!< 5 ms target queue delay
204 Time m_ceThreshold; //!< Threshold above which to CE mark
205 TracedValue<uint32_t> m_count; //!< Number of packets dropped since entering drop state
206 TracedValue<uint32_t> m_lastCount; //!< Last number of packets dropped since entering drop state
207 TracedValue<bool> m_dropping; //!< True if in dropping state
208 uint16_t m_recInvSqrt; //!< Reciprocal inverse square root
209 uint32_t m_firstAboveTime; //!< Time to declare sojourn time above target
210 TracedValue<uint32_t> m_dropNext; //!< Time to drop next packet
211};
212
213} // namespace ns3
214
215#endif /* CODEL_H */
Test 4: ControlLaw unit test - test against explicit port of Linux implementation.
Test 3: NewtonStep unit test - test against explicit port of Linux implementation.
A CoDel packet queue disc.
bool CheckConfig() override
Check whether the current configuration is correct.
uint32_t GetDropNext()
Get the time for next packet drop while in the dropping state.
static uint16_t NewtonStep(uint16_t recInvSqrt, uint32_t count)
Calculate the reciprocal square root of m_count by using Newton's method http://en....
static constexpr const char * OVERLIMIT_DROP
Overlimit dropped packet.
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 * TARGET_EXCEEDED_DROP
Sojourn time above target.
uint16_t m_recInvSqrt
Reciprocal inverse square root.
bool CoDelTimeBeforeEq(uint32_t a, uint32_t b)
Check if CoDel time a is preceding or equal to b.
void InitializeParams() override
Initialize parameters (if any) before the first packet is enqueued.
Time m_ceThreshold
Threshold above which to CE mark.
Time GetInterval()
Get the interval.
Ptr< QueueDiscItem > DoDequeue() override
Remove a packet from queue based on the current state If we are in dropping state,...
uint32_t m_minBytes
Minimum bytes in queue to allow a packet drop.
bool CoDelTimeAfterEq(uint32_t a, uint32_t b)
Check if CoDel time a is successive or equal to b.
static constexpr const char * CE_THRESHOLD_EXCEEDED_MARK
Sojourn time above CE threshold.
TracedValue< uint32_t > m_count
Number of packets dropped since entering drop state.
bool m_useL4s
True if L4S is used (ECT1 packets are marked at CE threshold)
bool OkToDrop(Ptr< QueueDiscItem > item, uint32_t now)
Determine whether a packet is OK to be dropped.
TracedValue< uint32_t > m_lastCount
Last number of packets dropped since entering drop state.
Time m_target
5 ms target queue delay
uint32_t Time2CoDel(Time t)
Return the unsigned 32-bit integer representation of the input Time object.
CoDelQueueDisc()
CoDelQueueDisc Constructor.
uint32_t m_firstAboveTime
Time to declare sojourn time above target.
Time GetTarget()
Get the target queue delay.
bool m_useEcn
True if ECN is used (packets are marked instead of being dropped)
TracedValue< bool > m_dropping
True if in dropping state.
bool CoDelTimeAfter(uint32_t a, uint32_t b)
Check if CoDel time a is successive to b.
bool CoDelTimeBefore(uint32_t a, uint32_t b)
Check if CoDel time a is preceding b.
bool DoEnqueue(Ptr< QueueDiscItem > item) override
Add a packet to the queue.
static constexpr const char * TARGET_EXCEEDED_MARK
Sojourn time above target.
Time m_interval
100 ms sliding minimum time window width
TracedValue< uint32_t > m_dropNext
Time to drop next packet.
static TypeId GetTypeId()
Get the type ID.
Smart pointer class similar to boost::intrusive_ptr.
QueueDisc is an abstract base class providing the interface and implementing the operations common to...
Definition queue-disc.h:173
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
Trace classes with value semantics.
a unique identifier for an interface.
Definition type-id.h:48
Every class exported by the ns3 library is enclosed in the ns3 namespace.
static const int CODEL_SHIFT
Number of bits discarded from the time representation.