* [Codel] CoDel for ns3
@ 2012-05-07 3:31 Andrew McGregor
2012-05-07 6:35 ` Andrew McGregor
0 siblings, 1 reply; 2+ messages in thread
From: Andrew McGregor @ 2012-05-07 3:31 UTC (permalink / raw)
To: codel
[-- Attachment #1.1: Type: text/plain, Size: 801 bytes --]
Based on Eric and Dave's kernel code, here's a patch that adds CoDel to ns3. This uses the same approximations as v8 of the kernel code, so it should behave very similarly in terms of which packets get dropped. It may have some issues with headers if you haven't built ns3 before applying the patch, I will try to address that next.
The patch doesn't do anything with CoDel, but you can replace droptail on any point-to-point in any of the examples by doing something like this:
bottleneckchannel.SetQueue ("ns3::CoDelQueue",
"Interval", StringValue("100ms"),
"Target", StringValue("5ms"),
"MinBytes", UintegerValue(1500)
);
Andrew McGregor
[-- Attachment #1.2: ns3-codel.patch --]
[-- Type: application/octet-stream, Size: 17742 bytes --]
diff -r 2a669a0c452e -r 4cc58164a9c9 src/internet/model/tcp-socket-base.cc
--- a/src/internet/model/tcp-socket-base.cc Sun Apr 08 23:03:34 2012 -0700
+++ b/src/internet/model/tcp-socket-base.cc Mon May 07 15:23:05 2012 +1200
@@ -22,6 +22,7 @@
#define NS_LOG_APPEND_CONTEXT \
if (m_node) { std::clog << Simulator::Now ().GetSeconds () << " [node " << m_node->GetId () << "] "; }
+#include <cstdlib>
#include "ns3/abort.h"
#include "ns3/node.h"
#include "ns3/inet-socket-address.h"
diff -r 2a669a0c452e -r 4cc58164a9c9 src/network/utils/codel-queue.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.cc Mon May 07 15:23:05 2012 +1200
@@ -0,0 +1,461 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors: Dave Täht <d@taht.net>
+ * Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+*/
+
+#include "ns3/log.h"
+#include "ns3/enum.h"
+#include "ns3/uinteger.h"
+#include "codel-queue.h"
+
+NS_LOG_COMPONENT_DEFINE ("CoDelQueue");
+
+namespace ns3 {
+
+#define BITS_PER_LONG (8 * sizeof (unsigned long))
+/* borrowed from the linux kernel */
+/**
+ * int_sqrt - rough approximation to sqrt
+ * @x: integer of which to calculate the sqrt
+ *
+ * A very rough approximation to the sqrt() function.
+ */
+static unsigned long int_sqrt(unsigned long x)
+{
+ unsigned long op, res, one;
+
+ op = x;
+ res = 0;
+
+ one = 1UL << (BITS_PER_LONG - 2);
+ while (one > op)
+ one >>= 2;
+
+ while (one != 0) {
+ if (op >= res + one) {
+ op = op - (res + one);
+ res = res + 2 * one;
+ }
+ res /= 2;
+ one /= 4;
+ }
+ return res;
+}
+
+#define do_div(n,base) \
+({ \
+ int __res; \
+ __res = ((unsigned long)n) % (unsigned int)base; \
+ n = ((unsigned long)n) / (unsigned int)base; \
+ __res; \
+})
+
+static codel_time_t codel_get_time(void)
+{
+ Time time = Simulator::Now ();
+ uint64_t ns = time.GetNanoSeconds ();
+
+ return ns >> CODEL_SHIFT;
+}
+
+#define codel_time_after(a, b) ((int)(a) - (int)(b) > 0)
+#define codel_time_after_eq(a, b) ((int)(a) - (int)(b) >= 0)
+#define codel_time_before(a, b) ((int)(a) - (int)(b) < 0)
+#define codel_time_before_eq(a, b) ((int)(a) - (int)(b) >= 0)
+
+#define NSEC_PER_MSEC 1000000
+#define NSEC_PER_USEC 1000
+#define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
+#define US2TIME(a) ((a * NSEC_PER_USEC) >> CODEL_SHIFT)
+#define NS2TIME(a) ((a) >> CODEL_SHIFT)
+#define TIME2CODEL(a) NS2TIME(a.GetNanoSeconds())
+
+#define DEFAULT_CODEL_LIMIT 1000
+
+/*
+ * return interval/sqrt(x) with good precision
+ */
+static uint32_t calc(uint32_t _interval, uint32_t _x)
+{
+ uint64_t interval = _interval;
+ unsigned long x = _x;
+
+ /* scale operands for max precision
+ * On 64bit arches, we can prescale x by 32bits
+ */
+ if (BITS_PER_LONG == 64) {
+ x <<= 32;
+ interval <<= 16;
+ }
+ while (x < (1UL << (BITS_PER_LONG - 2))) {
+ x <<= 2;
+ interval <<= 1;
+ }
+ do_div(interval, int_sqrt(x));
+ return (uint32_t)interval;
+}
+
+
+class CoDelTimestampTag : public Tag
+{
+public:
+ CoDelTimestampTag ();
+ static TypeId GetTypeId (void);
+ virtual TypeId GetInstanceTypeId (void) const;
+
+ virtual uint32_t GetSerializedSize (void) const;
+ virtual void Serialize (TagBuffer i) const;
+ virtual void Deserialize (TagBuffer i);
+ virtual void Print (std::ostream &os) const;
+
+ Time GetTxTime (void) const;
+private:
+ uint64_t m_creationTime;
+};
+
+CoDelTimestampTag::CoDelTimestampTag ()
+ : m_creationTime (Simulator::Now ().GetTimeStep ())
+{
+}
+
+TypeId
+CoDelTimestampTag::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("anon::CoDelTimestampTag")
+ .SetParent<Tag> ()
+ .AddConstructor<CoDelTimestampTag> ()
+ .AddAttribute ("CreationTime",
+ "The time at which the timestamp was created",
+ StringValue ("0.0s"),
+ MakeTimeAccessor (&CoDelTimestampTag::GetTxTime),
+ MakeTimeChecker ())
+ ;
+ return tid;
+}
+TypeId
+CoDelTimestampTag::GetInstanceTypeId (void) const
+{
+ return GetTypeId ();
+}
+
+uint32_t
+CoDelTimestampTag::GetSerializedSize (void) const
+{
+ return 8;
+}
+void
+CoDelTimestampTag::Serialize (TagBuffer i) const
+{
+ i.WriteU64 (m_creationTime);
+}
+void
+CoDelTimestampTag::Deserialize (TagBuffer i)
+{
+ m_creationTime = i.ReadU64 ();
+}
+void
+CoDelTimestampTag::Print (std::ostream &os) const
+{
+ os << "CreationTime=" << m_creationTime;
+}
+Time
+CoDelTimestampTag::GetTxTime (void) const
+{
+ return TimeStep (m_creationTime);
+}
+
+NS_OBJECT_ENSURE_REGISTERED (CoDelQueue);
+
+TypeId CoDelQueue::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::CoDelQueue")
+ .SetParent<Queue> ()
+ .AddConstructor<CoDelQueue> ()
+ .AddAttribute ("Mode",
+ "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
+ EnumValue (PACKETS),
+ MakeEnumAccessor (&CoDelQueue::SetMode),
+ MakeEnumChecker (BYTES, "Bytes",
+ PACKETS, "Packets"))
+ .AddAttribute ("MaxPackets",
+ "The maximum number of packets accepted by this CoDelQueue.",
+ UintegerValue (DEFAULT_CODEL_LIMIT),
+ MakeUintegerAccessor (&CoDelQueue::m_maxPackets),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("MaxBytes",
+ "The maximum number of bytes accepted by this CoDelQueue.",
+ UintegerValue (1500*DEFAULT_CODEL_LIMIT),
+ MakeUintegerAccessor (&CoDelQueue::m_maxBytes),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("MinBytes",
+ "The CoDel algorithm minbytes parameter.",
+ UintegerValue (1500),
+ MakeUintegerAccessor (&CoDelQueue::m_minbytes),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("Interval",
+ "The CoDel algorithm interval",
+ StringValue ("100ms"),
+ MakeTimeAccessor (&CoDelQueue::m_Interval),
+ MakeTimeChecker ())
+ .AddAttribute ("Target",
+ "The CoDel algorithm target queue delay",
+ StringValue ("5ms"),
+ MakeTimeAccessor (&CoDelQueue::m_Target),
+ MakeTimeChecker ())
+ ;
+
+ return tid;
+}
+
+CoDelQueue::CoDelQueue () :
+ Queue (),
+ m_packets (),
+ m_maxBytes(),
+ m_bytesInQueue(0),
+ m_count(0),
+ m_drop_count(0),
+ m_dropping(false),
+ m_first_above_time(0),
+ m_drop_next(0),
+ m_state1(0),
+ m_state2(0),
+ m_state3(0),
+ m_states(0),
+ m_drop_overlimit(0)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+CoDelQueue::~CoDelQueue ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+codel_time_t
+CoDelQueue::ControlLaw(codel_time_t t)
+{
+ return t + calc(TIME2CODEL(m_Interval), m_count);
+}
+
+void
+CoDelQueue::SetMode (enum Mode mode)
+{
+ NS_LOG_FUNCTION (mode);
+ m_mode = mode;
+}
+
+CoDelQueue::Mode
+CoDelQueue::GetMode (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_mode;
+}
+
+bool
+CoDelQueue::DoEnqueue (Ptr<Packet> p)
+{
+ NS_LOG_FUNCTION (this << p);
+
+ if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
+ {
+ NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
+ Drop (p);
+ ++m_drop_overlimit;
+ return false;
+ }
+
+ if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
+ {
+ NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
+ Drop (p);
+ ++m_drop_overlimit;
+ return false;
+ }
+
+ CoDelTimestampTag tag;
+ p->AddByteTag (tag);
+ m_bytesInQueue += p->GetSize ();
+ m_packets.push (p);
+
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ return true;
+}
+
+bool
+CoDelQueue::ShouldDrop(Ptr<Packet> p, codel_time_t now)
+{
+ CoDelTimestampTag tag;
+ bool found;
+ bool drop;
+ found = p->FindFirstMatchingByteTag (tag);
+ Time delta = Simulator::Now () - tag.GetTxTime ();
+ codel_time_t sojourn_time = NS2TIME(delta.GetNanoSeconds ());
+
+ if (codel_time_before(sojourn_time, TIME2CODEL(m_Target)) ||
+ m_bytesInQueue < m_minbytes)
+ {
+ /* went below so we'll stay below for at least q->interval */
+ m_first_above_time = 0;
+ return false;
+ }
+ drop = false;
+ if (m_first_above_time == 0)
+ {
+ /* just went above from below. If we stay above
+ * for at least q->interval we'll say it's ok to drop
+ */
+ m_first_above_time = now + TIME2CODEL(m_Interval);
+ }
+ else
+ if (codel_time_after(now, m_first_above_time))
+ {
+ drop = true;
+ ++m_state1;
+ }
+ return drop;
+}
+
+Ptr<Packet>
+CoDelQueue::DoDequeue (void)
+{
+ NS_LOG_FUNCTION (this);
+
+ if (m_packets.empty ())
+ {
+ m_dropping = false;
+ NS_LOG_LOGIC ("Queue empty");
+ return 0;
+ }
+ codel_time_t now = codel_get_time();
+ Ptr<Packet> p = m_packets.front ();
+ m_packets.pop ();
+ m_bytesInQueue -= p->GetSize ();
+
+ NS_LOG_LOGIC ("Popped " << p);
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ bool drop = ShouldDrop(p, now);
+ if (m_dropping)
+ {
+ if (!drop)
+ {
+ /* sojourn time below target - leave dropping state */
+ m_dropping = false;
+ }
+ else
+ if (codel_time_after_eq(now, m_drop_next))
+ {
+ m_state2++;
+ /* It's time for the next drop. Drop the current
+ * packet and dequeue the next. The dequeue might
+ * take us out of dropping state.
+ * If not, schedule the next drop.
+ * A large backlog might result in drop rates so high
+ * that the next drop should happen now,
+ * hence the while loop.
+ */
+ while (m_dropping &&
+ codel_time_after_eq(now, m_drop_next)) {
+ Drop(p);
+ ++m_drop_count;
+ ++m_count;
+ p = m_packets.front ();
+ m_packets.pop ();
+ m_bytesInQueue -= p->GetSize ();
+
+ NS_LOG_LOGIC ("Popped " << p);
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ if (!ShouldDrop(p, now))
+ {
+ /* leave dropping state */
+ m_dropping = false;
+ }
+ else
+ {
+ /* and schedule the next drop */
+ m_drop_next = ControlLaw(m_drop_next);
+ }
+ }
+ }
+ }
+ else
+ if (drop &&
+ (codel_time_before(now - m_drop_next,
+ 16 * TIME2CODEL(m_Interval)) ||
+ codel_time_after_eq(now - m_first_above_time,
+ 2 * TIME2CODEL(m_Interval))))
+ {
+ Drop(p);
+ ++m_drop_count;
+ drop = ShouldDrop(p, now);
+ m_dropping = true;
+ ++m_state3;
+ /*
+ * if min went above target close to when we last went below it
+ * assume that the drop rate that controlled the queue on the
+ * last cycle is a good starting point to control it now.
+ */
+ if (codel_time_after(now - m_drop_next, 16 * TIME2CODEL(m_Interval)))
+ {
+ //uint32_t c = min(m_count - 1, m_count - (m_count >> 4));
+ uint32_t c = m_count - 1;
+ m_count = std::max(1U, c);
+ }
+ else
+ {
+ m_count = 1;
+ }
+ m_drop_next = ControlLaw(now);
+ }
+ ++m_states;
+ return p;
+}
+
+Ptr<const Packet>
+CoDelQueue::DoPeek (void) const
+{
+ NS_LOG_FUNCTION (this);
+
+ if (m_packets.empty ())
+ {
+ NS_LOG_LOGIC ("Queue empty");
+ return 0;
+ }
+
+ Ptr<Packet> p = m_packets.front ();
+
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ return p;
+}
+
+} // namespace ns3
+
diff -r 2a669a0c452e -r 4cc58164a9c9 src/network/utils/codel-queue.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.h Mon May 07 15:23:05 2012 +1200
@@ -0,0 +1,117 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors: Dave Täht <d@taht.net>
+ * Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+ */
+
+#ifndef CODEL_H
+#define CODEL_H
+
+#include <queue>
+#include "ns3/core-module.h"
+#include "ns3/packet.h"
+#include "ns3/queue.h"
+#include "ns3/nstime.h"
+
+
+namespace ns3 {
+
+typedef uint32_t codel_time_t;
+
+#define CODEL_SHIFT 10
+
+class TraceContainer;
+
+/**
+ * \ingroup queue
+ *
+ * \brief A FIFO packet queue that drops tail-end packets on overflow
+ */
+class CoDelQueue : public Queue {
+public:
+ static TypeId GetTypeId (void);
+ /**
+ * \brief CoDelQueue Constructor
+ *
+ * Creates a codel queue with a maximum size of 100 packets by default
+ */
+ CoDelQueue ();
+
+ virtual ~CoDelQueue();
+
+ /**
+ * Enumeration of the modes supported in the class.
+ *
+ */
+ enum Mode {
+ ILLEGAL, /**< Mode not set */
+ PACKETS, /**< Use number of packets for maximum queue size */
+ BYTES, /**< Use number of bytes for maximum queue size */
+ };
+
+ /**
+ * Set the operating mode of this device.
+ *
+ * \param mode The operating mode of this device.
+ *
+ */
+ void SetMode (CoDelQueue::Mode mode);
+
+ /**
+ * Get the encapsulation mode of this device.
+ *
+ * \returns The encapsulation mode of this device.
+ */
+ CoDelQueue::Mode GetMode (void);
+
+private:
+ virtual bool DoEnqueue (Ptr<Packet> p);
+ virtual Ptr<Packet> DoDequeue (void);
+ virtual Ptr<const Packet> DoPeek (void) const;
+ codel_time_t ControlLaw(codel_time_t t);
+ bool ShouldDrop(Ptr<Packet> p, codel_time_t now);
+
+ std::queue<Ptr<Packet> > m_packets;
+ uint32_t m_maxPackets;
+ uint32_t m_maxBytes;
+ uint32_t m_bytesInQueue;
+ uint32_t m_minbytes;
+ Time m_Interval;
+ Time m_Target;
+ uint32_t m_count;
+ uint32_t m_drop_count;
+ bool m_dropping;
+ codel_time_t m_first_above_time;
+ codel_time_t m_drop_next;
+ uint32_t m_state1;
+ uint32_t m_state2;
+ uint32_t m_state3;
+ uint32_t m_states;
+ uint32_t m_drop_overlimit;
+ Mode m_mode;
+};
+
+} // namespace ns3
+
+#endif /* CODEL_H */
diff -r 2a669a0c452e -r 4cc58164a9c9 src/network/wscript
--- a/src/network/wscript Sun Apr 08 23:03:34 2012 -0700
+++ b/src/network/wscript Mon May 07 15:23:05 2012 +1200
@@ -24,6 +24,7 @@
'model/tag-buffer.cc',
'model/trailer.cc',
'utils/address-utils.cc',
+ 'utils/codel-queue.cc',
'utils/data-rate.cc',
'utils/drop-tail-queue.cc',
'utils/error-model.cc',
@@ -93,6 +94,7 @@
'model/tag-buffer.h',
'model/trailer.h',
'utils/address-utils.h',
+ 'utils/codel-queue.h',
'utils/data-rate.h',
'utils/drop-tail-queue.h',
'utils/error-model.h',
[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2330 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [Codel] CoDel for ns3
2012-05-07 3:31 [Codel] CoDel for ns3 Andrew McGregor
@ 2012-05-07 6:35 ` Andrew McGregor
0 siblings, 0 replies; 2+ messages in thread
From: Andrew McGregor @ 2012-05-07 6:35 UTC (permalink / raw)
To: codel
[-- Attachment #1.1: Type: text/plain, Size: 1093 bytes --]
This is a new version of the patch. It fixes a couple of bugs, adds a little extra logging, and adds a GetQueueSize method for the benefit of round-robin queueing (which I am still working on).
On 7/05/2012, at 3:31 PM, Andrew McGregor wrote:
> Based on Eric and Dave's kernel code, here's a patch that adds CoDel to ns3. This uses the same approximations as v8 of the kernel code, so it should behave very similarly in terms of which packets get dropped. It may have some issues with headers if you haven't built ns3 before applying the patch, I will try to address that next.
>
> The patch doesn't do anything with CoDel, but you can replace droptail on any point-to-point in any of the examples by doing something like this:
>
> bottleneckchannel.SetQueue ("ns3::CoDelQueue",
> "Interval", StringValue("100ms"),
> "Target", StringValue("5ms"),
> "MinBytes", UintegerValue(1500)
> );
>
> Andrew McGregor
>
> <ns3-codel.patch>
[-- Attachment #1.2: ns3-codel.patch --]
[-- Type: application/octet-stream, Size: 17922 bytes --]
diff -r 2a669a0c452e src/network/utils/codel-queue.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.cc Mon May 07 18:31:41 2012 +1200
@@ -0,0 +1,491 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors: Dave Täht <d@taht.net>
+ * Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+*/
+
+#include "ns3/log.h"
+#include "ns3/enum.h"
+#include "ns3/uinteger.h"
+#include "ns3/abort.h"
+#include "codel-queue.h"
+
+NS_LOG_COMPONENT_DEFINE ("CoDelQueue");
+
+namespace ns3 {
+
+#define BITS_PER_LONG (8 * sizeof (unsigned long))
+/* borrowed from the linux kernel */
+/**
+ * int_sqrt - rough approximation to sqrt
+ * @x: integer of which to calculate the sqrt
+ *
+ * A very rough approximation to the sqrt() function.
+ */
+static unsigned long int_sqrt(unsigned long x)
+{
+ unsigned long op, res, one;
+
+ op = x;
+ res = 0;
+
+ one = 1UL << (BITS_PER_LONG - 2);
+ while (one > op)
+ one >>= 2;
+
+ while (one != 0) {
+ if (op >= res + one) {
+ op = op - (res + one);
+ res = res + 2 * one;
+ }
+ res /= 2;
+ one /= 4;
+ }
+ return res;
+}
+
+#define do_div(n,base) \
+({ \
+ int __res; \
+ __res = ((unsigned long)n) % (unsigned int)base; \
+ n = ((unsigned long)n) / (unsigned int)base; \
+ __res; \
+})
+
+static codel_time_t codel_get_time(void)
+{
+ Time time = Simulator::Now ();
+ uint64_t ns = time.GetNanoSeconds ();
+
+ return ns >> CODEL_SHIFT;
+}
+
+#define codel_time_after(a, b) ((int)(a) - (int)(b) > 0)
+#define codel_time_after_eq(a, b) ((int)(a) - (int)(b) >= 0)
+#define codel_time_before(a, b) ((int)(a) - (int)(b) < 0)
+#define codel_time_before_eq(a, b) ((int)(a) - (int)(b) <= 0)
+
+#define NSEC_PER_MSEC 1000000
+#define NSEC_PER_USEC 1000
+#define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
+#define US2TIME(a) ((a * NSEC_PER_USEC) >> CODEL_SHIFT)
+#define NS2TIME(a) ((a) >> CODEL_SHIFT)
+#define TIME2CODEL(a) NS2TIME(a.GetNanoSeconds())
+
+#define DEFAULT_CODEL_LIMIT 1000
+
+/*
+ * return interval/sqrt(x) with good precision
+ */
+static uint32_t calc(uint32_t _interval, uint32_t _x)
+{
+ uint64_t interval = _interval;
+ unsigned long x = _x;
+
+ /* scale operands for max precision
+ * On 64bit arches, we can prescale x by 32bits
+ */
+ if (BITS_PER_LONG == 64) {
+ x <<= 32;
+ interval <<= 16;
+ }
+ while (x < (1UL << (BITS_PER_LONG - 2))) {
+ x <<= 2;
+ interval <<= 1;
+ }
+ do_div(interval, int_sqrt(x));
+ return (uint32_t)interval;
+}
+
+
+class CoDelTimestampTag : public Tag
+{
+public:
+ CoDelTimestampTag ();
+ static TypeId GetTypeId (void);
+ virtual TypeId GetInstanceTypeId (void) const;
+
+ virtual uint32_t GetSerializedSize (void) const;
+ virtual void Serialize (TagBuffer i) const;
+ virtual void Deserialize (TagBuffer i);
+ virtual void Print (std::ostream &os) const;
+
+ Time GetTxTime (void) const;
+private:
+ uint64_t m_creationTime;
+};
+
+CoDelTimestampTag::CoDelTimestampTag ()
+ : m_creationTime (Simulator::Now ().GetTimeStep ())
+{
+}
+
+TypeId
+CoDelTimestampTag::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("anon::CoDelTimestampTag")
+ .SetParent<Tag> ()
+ .AddConstructor<CoDelTimestampTag> ()
+ .AddAttribute ("CreationTime",
+ "The time at which the timestamp was created",
+ StringValue ("0.0s"),
+ MakeTimeAccessor (&CoDelTimestampTag::GetTxTime),
+ MakeTimeChecker ())
+ ;
+ return tid;
+}
+TypeId
+CoDelTimestampTag::GetInstanceTypeId (void) const
+{
+ return GetTypeId ();
+}
+
+uint32_t
+CoDelTimestampTag::GetSerializedSize (void) const
+{
+ return 8;
+}
+void
+CoDelTimestampTag::Serialize (TagBuffer i) const
+{
+ i.WriteU64 (m_creationTime);
+}
+void
+CoDelTimestampTag::Deserialize (TagBuffer i)
+{
+ m_creationTime = i.ReadU64 ();
+}
+void
+CoDelTimestampTag::Print (std::ostream &os) const
+{
+ os << "CreationTime=" << m_creationTime;
+}
+Time
+CoDelTimestampTag::GetTxTime (void) const
+{
+ return TimeStep (m_creationTime);
+}
+
+NS_OBJECT_ENSURE_REGISTERED (CoDelQueue);
+
+TypeId CoDelQueue::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::CoDelQueue")
+ .SetParent<Queue> ()
+ .AddConstructor<CoDelQueue> ()
+ .AddAttribute ("Mode",
+ "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
+ EnumValue (PACKETS),
+ MakeEnumAccessor (&CoDelQueue::SetMode),
+ MakeEnumChecker (BYTES, "Bytes",
+ PACKETS, "Packets"))
+ .AddAttribute ("MaxPackets",
+ "The maximum number of packets accepted by this CoDelQueue.",
+ UintegerValue (DEFAULT_CODEL_LIMIT),
+ MakeUintegerAccessor (&CoDelQueue::m_maxPackets),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("MaxBytes",
+ "The maximum number of bytes accepted by this CoDelQueue.",
+ UintegerValue (1500*DEFAULT_CODEL_LIMIT),
+ MakeUintegerAccessor (&CoDelQueue::m_maxBytes),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("MinBytes",
+ "The CoDel algorithm minbytes parameter.",
+ UintegerValue (1500),
+ MakeUintegerAccessor (&CoDelQueue::m_minbytes),
+ MakeUintegerChecker<uint32_t> ())
+ .AddAttribute ("Interval",
+ "The CoDel algorithm interval",
+ StringValue ("100ms"),
+ MakeTimeAccessor (&CoDelQueue::m_Interval),
+ MakeTimeChecker ())
+ .AddAttribute ("Target",
+ "The CoDel algorithm target queue delay",
+ StringValue ("5ms"),
+ MakeTimeAccessor (&CoDelQueue::m_Target),
+ MakeTimeChecker ())
+ ;
+
+ return tid;
+}
+
+CoDelQueue::CoDelQueue () :
+ Queue (),
+ m_packets (),
+ m_maxBytes(),
+ m_bytesInQueue(0),
+ m_count(1),
+ m_drop_count(0),
+ m_dropping(false),
+ m_first_above_time(0),
+ m_drop_next(0),
+ m_state1(0),
+ m_state2(0),
+ m_state3(0),
+ m_states(0),
+ m_drop_overlimit(0)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+CoDelQueue::~CoDelQueue ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+codel_time_t
+CoDelQueue::ControlLaw(codel_time_t t)
+{
+ return t + calc(TIME2CODEL(m_Interval), m_count);
+}
+
+void
+CoDelQueue::SetMode (enum Mode mode)
+{
+ NS_LOG_FUNCTION (mode);
+ m_mode = mode;
+}
+
+CoDelQueue::Mode
+CoDelQueue::GetMode (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_mode;
+}
+
+bool
+CoDelQueue::DoEnqueue (Ptr<Packet> p)
+{
+ NS_LOG_FUNCTION (this << p);
+
+ if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
+ {
+ NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
+ Drop (p);
+ ++m_drop_overlimit;
+ return false;
+ }
+
+ if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
+ {
+ NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
+ Drop (p);
+ ++m_drop_overlimit;
+ return false;
+ }
+
+ CoDelTimestampTag tag;
+ p->AddByteTag (tag);
+ m_bytesInQueue += p->GetSize ();
+ m_packets.push (p);
+
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ return true;
+}
+
+bool
+CoDelQueue::ShouldDrop(Ptr<Packet> p, codel_time_t now)
+{
+ CoDelTimestampTag tag;
+ bool found;
+ bool drop;
+ found = p->FindFirstMatchingByteTag (tag);
+ Time delta = Simulator::Now () - tag.GetTxTime ();
+ codel_time_t sojourn_time = NS2TIME(delta.GetNanoSeconds ());
+
+ if (codel_time_before(sojourn_time, TIME2CODEL(m_Target)) ||
+ m_bytesInQueue < m_minbytes)
+ {
+ /* went below so we'll stay below for at least q->interval */
+ m_first_above_time = 0;
+ return false;
+ }
+ drop = false;
+ if (m_first_above_time == 0)
+ {
+ /* just went above from below. If we stay above
+ * for at least q->interval we'll say it's ok to drop
+ */
+ m_first_above_time = now + TIME2CODEL(m_Interval);
+ }
+ else
+ if (codel_time_after(now, m_first_above_time))
+ {
+ drop = true;
+ ++m_state1;
+ }
+ return drop;
+}
+
+Ptr<Packet>
+CoDelQueue::DoDequeue (void)
+{
+ NS_LOG_FUNCTION (this);
+
+ if (m_packets.empty ())
+ {
+ m_dropping = false;
+ NS_LOG_LOGIC ("Queue empty");
+ return 0;
+ }
+ codel_time_t now = codel_get_time();
+ Ptr<Packet> p = m_packets.front ();
+ m_packets.pop ();
+ m_bytesInQueue -= p->GetSize ();
+
+ NS_LOG_LOGIC ("Popped " << p);
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ bool drop = ShouldDrop(p, now);
+ if (m_dropping)
+ {
+ if (!drop)
+ {
+ /* sojourn time below target - leave dropping state */
+ m_dropping = false;
+ }
+ else
+ if (codel_time_after_eq(now, m_drop_next))
+ {
+ m_state2++;
+ /* It's time for the next drop. Drop the current
+ * packet and dequeue the next. The dequeue might
+ * take us out of dropping state.
+ * If not, schedule the next drop.
+ * A large backlog might result in drop rates so high
+ * that the next drop should happen now,
+ * hence the while loop.
+ */
+ while (m_dropping &&
+ codel_time_after_eq(now, m_drop_next)) {
+ Drop(p);
+ ++m_drop_count;
+ ++m_count;
+ if (m_packets.empty ())
+ {
+ m_dropping = false;
+ NS_LOG_LOGIC ("Queue empty");
+ ++m_states;
+ return 0;
+ }
+ p = m_packets.front ();
+ m_packets.pop ();
+ m_bytesInQueue -= p->GetSize ();
+
+ NS_LOG_LOGIC ("Popped " << p);
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ if (!ShouldDrop(p, now))
+ {
+ /* leave dropping state */
+ m_dropping = false;
+ }
+ else
+ {
+ /* and schedule the next drop */
+ m_drop_next = ControlLaw(m_drop_next);
+ }
+ }
+ }
+ }
+ else
+ if (drop &&
+ (codel_time_before(now - m_drop_next,
+ 16 * TIME2CODEL(m_Interval)) ||
+ codel_time_after_eq(now - m_first_above_time,
+ 2 * TIME2CODEL(m_Interval))))
+ {
+ Drop(p);
+ ++m_drop_count;
+
+ NS_LOG_LOGIC ("Popped " << p);
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ drop = ShouldDrop(p, now);
+ m_dropping = true;
+ ++m_state3;
+ /*
+ * if min went above target close to when we last went below it
+ * assume that the drop rate that controlled the queue on the
+ * last cycle is a good starting point to control it now.
+ */
+ if (codel_time_after(now - m_drop_next, 16 * TIME2CODEL(m_Interval)))
+ {
+ uint32_t c = m_count - 1;
+ m_count = std::max(1U, c);
+ }
+ else
+ {
+ m_count = 1;
+ }
+ m_drop_next = ControlLaw(now);
+ }
+ ++m_states;
+ return p;
+}
+
+uint32_t
+CoDelQueue::GetQueueSize (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ if (GetMode () == BYTES)
+ {
+ return m_bytesInQueue;
+ }
+ else if (GetMode () == PACKETS)
+ {
+ return m_packets.size ();
+ }
+ else
+ {
+ NS_ABORT_MSG ("Unknown mode.");
+ }
+}
+
+Ptr<const Packet>
+CoDelQueue::DoPeek (void) const
+{
+ NS_LOG_FUNCTION (this);
+
+ if (m_packets.empty ())
+ {
+ NS_LOG_LOGIC ("Queue empty");
+ return 0;
+ }
+
+ Ptr<Packet> p = m_packets.front ();
+
+ NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+ NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+ return p;
+}
+
+} // namespace ns3
+
diff -r 2a669a0c452e src/network/utils/codel-queue.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.h Mon May 07 18:31:41 2012 +1200
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors: Dave Täht <d@taht.net>
+ * Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+ */
+
+#ifndef CODEL_H
+#define CODEL_H
+
+#include <queue>
+#include "ns3/packet.h"
+#include "ns3/queue.h"
+#include "ns3/nstime.h"
+#include "ns3/simulator.h"
+#include "ns3/string.h"
+
+namespace ns3 {
+
+typedef uint32_t codel_time_t;
+
+#define CODEL_SHIFT 10
+
+class TraceContainer;
+
+/**
+ * \ingroup queue
+ *
+ * \brief A FIFO packet queue that drops tail-end packets on overflow
+ */
+class CoDelQueue : public Queue {
+public:
+ static TypeId GetTypeId (void);
+ /**
+ * \brief CoDelQueue Constructor
+ *
+ * Creates a codel queue with a maximum size of 100 packets by default
+ */
+ CoDelQueue ();
+
+ virtual ~CoDelQueue();
+
+ /**
+ * Enumeration of the modes supported in the class.
+ *
+ */
+ enum Mode {
+ ILLEGAL, /**< Mode not set */
+ PACKETS, /**< Use number of packets for maximum queue size */
+ BYTES, /**< Use number of bytes for maximum queue size */
+ };
+
+ /**
+ * Set the operating mode of this device.
+ *
+ * \param mode The operating mode of this device.
+ *
+ */
+ void SetMode (CoDelQueue::Mode mode);
+
+ /**
+ * Get the encapsulation mode of this device.
+ *
+ * \returns The encapsulation mode of this device.
+ */
+ CoDelQueue::Mode GetMode (void);
+
+ uint32_t GetQueueSize (void);
+
+private:
+ virtual bool DoEnqueue (Ptr<Packet> p);
+ virtual Ptr<Packet> DoDequeue (void);
+ virtual Ptr<const Packet> DoPeek (void) const;
+ codel_time_t ControlLaw(codel_time_t t);
+ bool ShouldDrop(Ptr<Packet> p, codel_time_t now);
+
+ std::queue<Ptr<Packet> > m_packets;
+ uint32_t m_maxPackets;
+ uint32_t m_maxBytes;
+ uint32_t m_bytesInQueue;
+ uint32_t m_minbytes;
+ Time m_Interval;
+ Time m_Target;
+ uint32_t m_count;
+ uint32_t m_drop_count;
+ bool m_dropping;
+ codel_time_t m_first_above_time;
+ codel_time_t m_drop_next;
+ uint32_t m_state1;
+ uint32_t m_state2;
+ uint32_t m_state3;
+ uint32_t m_states;
+ uint32_t m_drop_overlimit;
+ Mode m_mode;
+};
+
+} // namespace ns3
+
+#endif /* CODEL_H */
diff -r 2a669a0c452e src/network/wscript
--- a/src/network/wscript Sun Apr 08 23:03:34 2012 -0700
+++ b/src/network/wscript Mon May 07 18:31:41 2012 +1200
@@ -24,6 +24,7 @@
'model/tag-buffer.cc',
'model/trailer.cc',
'utils/address-utils.cc',
+ 'utils/codel-queue.cc',
'utils/data-rate.cc',
'utils/drop-tail-queue.cc',
'utils/error-model.cc',
@@ -93,6 +94,7 @@
'model/tag-buffer.h',
'model/trailer.h',
'utils/address-utils.h',
+ 'utils/codel-queue.h',
'utils/data-rate.h',
'utils/drop-tail-queue.h',
'utils/error-model.h',
[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2330 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2012-05-07 6:35 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-05-07 3:31 [Codel] CoDel for ns3 Andrew McGregor
2012-05-07 6:35 ` Andrew McGregor
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox