OLD | NEW |
| (Empty) |
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 <queue> | |
32 #include "ns3/packet.h" | |
33 #include "ns3/queue.h" | |
34 #include "ns3/nstime.h" | |
35 #include "ns3/simulator.h" | |
36 #include "ns3/string.h" | |
37 #include "ns3/traced-value.h" | |
38 #include "ns3/trace-source-accessor.h" | |
39 | |
40 class CoDelQueueNewtonStepTest; // Forward declaration for unit test | |
41 class CoDelQueueControlLawTest; // Forward declaration for unit test | |
42 | |
43 namespace ns3 { | |
44 | |
45 /** | |
46 * Number of bits discarded from the time representation. | |
47 * The time is assumed to be in nanoseconds. | |
48 */ | |
49 static const int CODEL_SHIFT = 10; | |
50 | |
51 #define DEFAULT_CODEL_LIMIT 1000 | |
52 #define REC_INV_SQRT_BITS (8 * sizeof(uint16_t)) | |
53 #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS) | |
54 | |
55 class TraceContainer; | |
56 | |
57 /** | |
58 * \ingroup queue | |
59 * | |
60 * \brief A CoDel packet queue | |
61 */ | |
62 | |
63 class CoDelQueue : public Queue | |
64 { | |
65 public: | |
66 /** | |
67 * Get the type ID. | |
68 * \brief Get the type ID. | |
69 * \return the object TypeId | |
70 */ | |
71 static TypeId GetTypeId (void); | |
72 | |
73 /** | |
74 * \brief CoDelQueue Constructor | |
75 * | |
76 * Creates a CoDel queue | |
77 */ | |
78 CoDelQueue (); | |
79 | |
80 virtual ~CoDelQueue (); | |
81 | |
82 /** | |
83 * \brief Set the operating mode of this device. | |
84 * | |
85 * \param mode The operating mode of this device. | |
86 */ | |
87 void SetMode (CoDelQueue::QueueMode mode); | |
88 | |
89 /** | |
90 * \brief Get the encapsulation mode of this device. | |
91 * | |
92 * \returns The encapsulation mode of this device. | |
93 */ | |
94 CoDelQueue::QueueMode GetMode (void); | |
95 | |
96 /** | |
97 * \brief Get the current value of the queue in bytes or packets. | |
98 * | |
99 * \returns The queue size in bytes or packets. | |
100 */ | |
101 uint32_t GetQueueSize (void); | |
102 | |
103 /** | |
104 * \brief Get the number of packets dropped when packets | |
105 * arrive at a full queue and cannot be enqueued. | |
106 * | |
107 * \returns The number of dropped packets | |
108 */ | |
109 uint32_t GetDropOverLimit (void); | |
110 | |
111 /** | |
112 * \brief Get the number of packets dropped according to CoDel algorithm | |
113 * | |
114 * \returns The number of dropped packets | |
115 */ | |
116 uint32_t GetDropCount (void); | |
117 | |
118 /** | |
119 * \brief Get the target queue delay | |
120 * | |
121 * \returns The target queue delay | |
122 */ | |
123 Time GetTarget (void); | |
124 | |
125 /** | |
126 * \brief Get the interval | |
127 * | |
128 * \returns The interval | |
129 */ | |
130 Time GetInterval (void); | |
131 | |
132 /** | |
133 * \brief Get the time for next packet drop while in the dropping state | |
134 * | |
135 * \returns The time for next packet drop | |
136 */ | |
137 uint32_t GetDropNext (void); | |
138 | |
139 private: | |
140 friend class::CoDelQueueNewtonStepTest; // Test code | |
141 friend class::CoDelQueueControlLawTest; // Test code | |
142 /** | |
143 * \brief Add a packet to the queue | |
144 * | |
145 * \param p The packet to be added | |
146 * \returns True if the packet can be added, False if the packet is dropped du
e to full queue | |
147 */ | |
148 virtual bool DoEnqueue (Ptr<Packet> p); | |
149 | |
150 /** | |
151 * \brief Remove a packet from queue based on the current state | |
152 * If we are in dropping state, check if we could leave the dropping state | |
153 * or if we should perform next drop | |
154 * If we are not currently in dropping state, check if we need to enter the st
ate | |
155 * and drop the first packet | |
156 * | |
157 * \returns The packet that is examined | |
158 */ | |
159 virtual Ptr<Packet> DoDequeue (void); | |
160 | |
161 virtual Ptr<const Packet> DoPeek (void) const; | |
162 | |
163 /** | |
164 * \brief Calculate the reciprocal square root of m_count by using Newton's me
thod | |
165 * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_m
ethods_for_reciprocal_square_roots | |
166 * m_recInvSqrt (new) = (m_recInvSqrt (old) / 2) * (3 - m_count * m_recInvSqrt
^2) | |
167 */ | |
168 void NewtonStep (void); | |
169 | |
170 /** | |
171 * \brief Determine the time for next drop | |
172 * CoDel control law is t + m_interval/sqrt(m_count). | |
173 * Here, we use m_recInvSqrt calculated by Newton's method in NewtonStep() to
avoid | |
174 * both sqrt() and divide operations | |
175 * | |
176 * \param t Current next drop time | |
177 * \returns The new next drop time: | |
178 */ | |
179 uint32_t ControlLaw (uint32_t t); | |
180 | |
181 /** | |
182 * \brief Determine whether a packet is OK to be dropped. The packet | |
183 * may not be actually dropped (depending on the drop state) | |
184 * | |
185 * \param p The packet that is considered | |
186 * \param now The current time represented as 32-bit unsigned integer (us) | |
187 * \returns True if it is OK to drop the packet (sojourn time above target for
at least interval) | |
188 */ | |
189 bool OkToDrop (Ptr<Packet> p, uint32_t now); | |
190 | |
191 /** | |
192 * Check if CoDel time a is successive to b | |
193 * @param a left operand | |
194 * @param b right operand | |
195 * @return true if a is greater than b | |
196 */ | |
197 bool CoDelTimeAfter (uint32_t a, uint32_t b); | |
198 /** | |
199 * Check if CoDel time a is successive or equal to b | |
200 * @param a left operand | |
201 * @param b right operand | |
202 * @return true if a is greater than or equal to b | |
203 */ | |
204 bool CoDelTimeAfterEq (uint32_t a, uint32_t b); | |
205 /** | |
206 * Check if CoDel time a is preceding b | |
207 * @param a left operand | |
208 * @param b right operand | |
209 * @return true if a is less than to b | |
210 */ | |
211 bool CoDelTimeBefore (uint32_t a, uint32_t b); | |
212 /** | |
213 * Check if CoDel time a is preceding or equal to b | |
214 * @param a left operand | |
215 * @param b right operand | |
216 * @return true if a is less than or equal to b | |
217 */ | |
218 bool CoDelTimeBeforeEq (uint32_t a, uint32_t b); | |
219 | |
220 /** | |
221 * returned unsigned 32-bit integer representation of the input Time object | |
222 * units are microseconds | |
223 */ | |
224 uint32_t Time2CoDel (Time t); | |
225 | |
226 std::queue<Ptr<Packet> > m_packets; //!< The packet queue | |
227 uint32_t m_maxPackets; //!< Max # of packets accepted by the
queue | |
228 uint32_t m_maxBytes; //!< Max # of bytes accepted by the qu
eue | |
229 TracedValue<uint32_t> m_bytesInQueue; //!< The total number of bytes in queu
e | |
230 uint32_t m_minBytes; //!< Minimum bytes in queue to allow a
packet drop | |
231 Time m_interval; //!< 100 ms sliding minimum time windo
w width | |
232 Time m_target; //!< 5 ms target queue delay | |
233 TracedValue<uint32_t> m_count; //!< Number of packets dropped since e
ntering drop state | |
234 TracedValue<uint32_t> m_dropCount; //!< Number of dropped packets accordi
ng CoDel algorithm | |
235 TracedValue<uint32_t> m_lastCount; //!< Last number of packets dropped si
nce entering drop state | |
236 TracedValue<bool> m_dropping; //!< True if in dropping state | |
237 uint16_t m_recInvSqrt; //!< Reciprocal inverse square root | |
238 uint32_t m_firstAboveTime; //!< Time to declare sojourn time abov
e target | |
239 TracedValue<uint32_t> m_dropNext; //!< Time to drop next packet | |
240 uint32_t m_state1; //!< Number of times packet sojourn go
es above target for interval | |
241 uint32_t m_state2; //!< Number of times we perform next d
rop while in dropping state | |
242 uint32_t m_state3; //!< Number of times we enter drop sta
te and drop the fist packet | |
243 uint32_t m_states; //!< Total number of times we are in s
tate 1, state 2, or state 3 | |
244 uint32_t m_dropOverLimit; //!< The number of packets dropped due
to full queue | |
245 QueueMode m_mode; //!< The operating mode (Bytes or pack
ets) | |
246 TracedValue<Time> m_sojourn; //!< Time in queue | |
247 }; | |
248 | |
249 } // namespace ns3 | |
250 | |
251 #endif /* CODEL_H */ | |
OLD | NEW |