A Discrete-Event Network Simulator
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
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  */
28 #ifndef CODEL_H
29 #define CODEL_H
31 #include "ns3/packet.h"
32 #include "ns3/queue-disc.h"
33 #include "ns3/nstime.h"
34 #include "ns3/simulator.h"
35 #include "ns3/string.h"
36 #include "ns3/traced-value.h"
37 #include "ns3/trace-source-accessor.h"
39 class CoDelQueueDiscNewtonStepTest; // Forward declaration for unit test
40 class CoDelQueueDiscControlLawTest; // Forward declaration for unit test
42 namespace ns3 {
48 static const int CODEL_SHIFT = 10;
50 #define DEFAULT_CODEL_LIMIT 1000
51 #define REC_INV_SQRT_BITS (8 * sizeof(uint16_t))
54 class TraceContainer;
62 class CoDelQueueDisc : public QueueDisc
63 {
64 public:
70  static TypeId GetTypeId (void);
77  CoDelQueueDisc ();
79  virtual ~CoDelQueueDisc ();
86  void SetMode (Queue::QueueMode mode);
100  uint32_t GetQueueSize (void);
108  uint32_t GetDropOverLimit (void);
115  uint32_t GetDropCount (void);
122  Time GetTarget (void);
129  Time GetInterval (void);
136  uint32_t GetDropNext (void);
138 private:
139  friend class::CoDelQueueDiscNewtonStepTest; // Test code
140  friend class::CoDelQueueDiscControlLawTest; // Test code
147  virtual bool DoEnqueue (Ptr<QueueDiscItem> item);
158  virtual Ptr<QueueDiscItem> DoDequeue (void);
160  virtual Ptr<const QueueDiscItem> DoPeek (void) const;
161  virtual bool CheckConfig (void);
168  void NewtonStep (void);
179  uint32_t ControlLaw (uint32_t t);
189  bool OkToDrop (Ptr<Packet> p, uint32_t now);
197  bool CoDelTimeAfter (uint32_t a, uint32_t b);
204  bool CoDelTimeAfterEq (uint32_t a, uint32_t b);
211  bool CoDelTimeBefore (uint32_t a, uint32_t b);
218  bool CoDelTimeBeforeEq (uint32_t a, uint32_t b);
224  uint32_t Time2CoDel (Time t);
226  virtual void InitializeParams (void);
228  uint32_t m_maxPackets;
229  uint32_t m_maxBytes;
230  uint32_t m_minBytes;
237  uint16_t m_recInvSqrt;
238  uint32_t m_firstAboveTime;
240  uint32_t m_state1;
241  uint32_t m_state2;
242  uint32_t m_state3;
243  uint32_t m_states;
244  uint32_t m_dropOverLimit;
247 };
249 } // namespace ns3
251 #endif /* CODEL_H */
virtual void InitializeParams(void)
Initialize parameters (if any) before the first packet is enqueued.
virtual Ptr< const QueueDiscItem > DoPeek(void) const
This function returns a copy of the next packet the queue disc will extract.
Queue::QueueMode m_mode
The operating mode (Bytes or packets)
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
virtual bool DoEnqueue(Ptr< QueueDiscItem > item)
Add a packet to the queue.
uint32_t m_maxBytes
Max # of bytes accepted by the queue.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
TracedValue< uint32_t > m_dropCount
Number of dropped packets according CoDel algorithm.
uint32_t m_maxPackets
Max # of packets accepted by the queue.
uint32_t GetDropOverLimit(void)
Get the number of packets dropped when packets arrive at a full queue and cannot be enqueued...
TracedValue< Time > m_sojourn
Time in queue.
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.
virtual bool CheckConfig(void)
Check whether the current configuration is correct.
bool OkToDrop(Ptr< Packet > p, uint32_t now)
Determine whether a packet is OK to be dropped.
Time GetInterval(void)
Get the interval.
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:205
uint32_t ControlLaw(uint32_t t)
Determine the time for next drop CoDel control law is t + m_interval/sqrt(m_count).
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.
Enumeration of the modes supported in the class.
Definition: queue.h:130
uint32_t m_dropOverLimit
The number of packets dropped due to full queue.
Queue::QueueMode GetMode(void)
Get the encapsulation mode of this device.
uint32_t m_states
Total number of times we are in state 1, state 2, or state 3.
uint32_t m_firstAboveTime
Time to declare sojourn time above target.
uint32_t m_state2
Number of times we perform next drop while in dropping state.
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 Constructor.
uint32_t GetQueueSize(void)
Get the current value of the queue in bytes or packets.
uint32_t GetDropCount(void)
Get the number of packets dropped according to CoDel algorithm.
TracedValue< uint32_t > m_lastCount
Last number of packets dropped since entering drop state.
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.
void NewtonStep(void)
Calculate the reciprocal square root of m_count by using Newton'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)
A CoDel packet queue disc.
static const int CODEL_SHIFT
Number of bits discarded from the time representation.
uint32_t m_state3
Number of times we enter drop state and drop the fist packet.
uint32_t Time2CoDel(Time t)
returned unsigned 32-bit integer representation of the input Time object units are microseconds ...
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.
void SetMode(Queue::QueueMode mode)
Set the operating mode of this device.
uint32_t m_state1
Number of times packet sojourn goes above target for interval.
a unique identifier for an interface.
Definition: type-id.h:58
TracedValue< uint32_t > m_dropNext
Time to drop next packet.