Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1248)

Unified Diff: src/internet/model/codel-queue.cc

Issue 284530043: Introduce the traffic control layer (Closed)
Patch Set: Use DoInitialize to check config and initialize queue discs Created 8 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: src/internet/model/codel-queue.cc
===================================================================
deleted file mode 100644
--- a/src/internet/model/codel-queue.cc
+++ /dev/null
@@ -1,606 +0,0 @@
-/* -*- 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"
-
-namespace ns3 {
-
-NS_LOG_COMPONENT_DEFINE ("CoDelQueue");
-
-/**
- * Performs a reciprocal divide, similar to the
- * Linux kernel reciprocal_divide function
- * \param A numerator
- * \param R reciprocal of the denominator B
- * \return the value of A/B
- */
-/* borrowed from the linux kernel */
-static inline uint32_t ReciprocalDivide (uint32_t A, uint32_t R)
-{
- return (uint32_t)(((uint64_t)A * R) >> 32);
-}
-
-/* end kernel borrowings */
-
-/**
- * Returns the current time translated in CoDel time representation
- * \return the current time
- */
-static uint32_t CoDelGetTime (void)
-{
- Time time = Simulator::Now ();
- uint64_t ns = time.GetNanoSeconds ();
-
- return ns >> CODEL_SHIFT;
-}
-
-/**
- * CoDel time stamp, used to carry CoDel time informations.
- */
-class CoDelTimestampTag : public Tag
-{
-public:
- CoDelTimestampTag ();
- /**
- * \brief Get the type ID.
- * \return the object TypeId
- */
- 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;
-
- /**
- * Gets the Tag creation time
- * @return the time object stored in the tag
- */
- Time GetTxTime (void) const;
-private:
- uint64_t m_creationTime; //!< Tag creation time
-};
-
-CoDelTimestampTag::CoDelTimestampTag ()
- : m_creationTime (Simulator::Now ().GetTimeStep ())
-{
-}
-
-TypeId
-CoDelTimestampTag::GetTypeId (void)
-{
- static TypeId tid = TypeId ("ns3::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> ()
- .SetGroupName ("Internet")
- .AddConstructor<CoDelQueue> ()
- .AddAttribute ("Mode",
- "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
- EnumValue (QUEUE_MODE_BYTES),
- MakeEnumAccessor (&CoDelQueue::SetMode),
- MakeEnumChecker (QUEUE_MODE_BYTES, "QUEUE_MODE_BYTES",
- QUEUE_MODE_PACKETS, "QUEUE_MODE_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 ())
- .AddTraceSource ("Count",
- "CoDel count",
- MakeTraceSourceAccessor (&CoDelQueue::m_count),
- "ns3::TracedValueCallback::Uint32")
- .AddTraceSource ("DropCount",
- "CoDel drop count",
- MakeTraceSourceAccessor (&CoDelQueue::m_dropCount),
- "ns3::TracedValueCallback::Uint32")
- .AddTraceSource ("LastCount",
- "CoDel lastcount",
- MakeTraceSourceAccessor (&CoDelQueue::m_lastCount),
- "ns3::TracedValueCallback::Uint32")
- .AddTraceSource ("DropState",
- "Dropping state",
- MakeTraceSourceAccessor (&CoDelQueue::m_dropping),
- "ns3::TracedValueCallback::Bool")
- .AddTraceSource ("BytesInQueue",
- "Number of bytes in the queue",
- MakeTraceSourceAccessor (&CoDelQueue::m_bytesInQueue),
- "ns3::TracedValueCallback::Uint32")
- .AddTraceSource ("Sojourn",
- "Time in the queue",
- MakeTraceSourceAccessor (&CoDelQueue::m_sojourn),
- "ns3::Time::TracedValueCallback")
- .AddTraceSource ("DropNext",
- "Time until next packet drop",
- MakeTraceSourceAccessor (&CoDelQueue::m_dropNext),
- "ns3::TracedValueCallback::Uint32")
- ;
-
- return tid;
-}
-
-CoDelQueue::CoDelQueue ()
- : Queue (),
- m_packets (),
- m_maxBytes (),
- m_bytesInQueue (0),
- m_count (0),
- m_dropCount (0),
- m_lastCount (0),
- m_dropping (false),
- m_recInvSqrt (~0U >> REC_INV_SQRT_SHIFT),
- m_firstAboveTime (0),
- m_dropNext (0),
- m_state1 (0),
- m_state2 (0),
- m_state3 (0),
- m_states (0),
- m_dropOverLimit (0),
- m_sojourn (0)
-{
- NS_LOG_FUNCTION (this);
-}
-
-CoDelQueue::~CoDelQueue ()
-{
- NS_LOG_FUNCTION (this);
-}
-
-void
-CoDelQueue::NewtonStep (void)
-{
- NS_LOG_FUNCTION (this);
- uint32_t invsqrt = ((uint32_t) m_recInvSqrt) << REC_INV_SQRT_SHIFT;
- uint32_t invsqrt2 = ((uint64_t) invsqrt * invsqrt) >> 32;
- uint64_t val = (3ll << 32) - ((uint64_t) m_count * invsqrt2);
-
- val >>= 2; /* avoid overflow */
- val = (val * invsqrt) >> (32 - 2 + 1);
- m_recInvSqrt = val >> REC_INV_SQRT_SHIFT;
-}
-
-uint32_t
-CoDelQueue::ControlLaw (uint32_t t)
-{
- NS_LOG_FUNCTION (this);
- return t + ReciprocalDivide (Time2CoDel (m_interval), m_recInvSqrt << REC_INV_SQRT_SHIFT);
-}
-
-void
-CoDelQueue::SetMode (CoDelQueue::QueueMode mode)
-{
- NS_LOG_FUNCTION (mode);
- m_mode = mode;
-}
-
-CoDelQueue::QueueMode
-CoDelQueue::GetMode (void)
-{
- NS_LOG_FUNCTION (this);
- return m_mode;
-}
-
-bool
-CoDelQueue::DoEnqueue (Ptr<Packet> p)
-{
- NS_LOG_FUNCTION (this << p);
-
- if (m_mode == QUEUE_MODE_PACKETS && (m_packets.size () + 1 > m_maxPackets))
- {
- NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
- Drop (p);
- ++m_dropOverLimit;
- return false;
- }
-
- if (m_mode == QUEUE_MODE_BYTES && (m_bytesInQueue + p->GetSize () > m_maxBytes))
- {
- NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
- Drop (p);
- ++m_dropOverLimit;
- return false;
- }
-
- // Tag packet with current time for DoDequeue() to compute sojourn time
- CoDelTimestampTag tag;
- p->AddPacketTag (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::OkToDrop (Ptr<Packet> p, uint32_t now)
-{
- NS_LOG_FUNCTION (this);
- CoDelTimestampTag tag;
- bool okToDrop;
-
- bool found = p->RemovePacketTag (tag);
- NS_ASSERT_MSG (found, "found a packet without an input timestamp tag");
- NS_UNUSED (found); //silence compiler warning
- Time delta = Simulator::Now () - tag.GetTxTime ();
- NS_LOG_INFO ("Sojourn time " << delta.GetSeconds ());
- m_sojourn = delta;
- uint32_t sojournTime = Time2CoDel (delta);
-
- if (CoDelTimeBefore (sojournTime, Time2CoDel (m_target))
- || m_bytesInQueue < m_minBytes)
- {
- // went below so we'll stay below for at least q->interval
- NS_LOG_LOGIC ("Sojourn time is below target or number of bytes in queue is less than minBytes; packet should not be dropped");
- m_firstAboveTime = 0;
- return false;
- }
- okToDrop = false;
- if (m_firstAboveTime == 0)
- {
- /* just went above from below. If we stay above
- * for at least q->interval we'll say it's ok to drop
- */
- NS_LOG_LOGIC ("Sojourn time has just gone above target from below, need to stay above for at least q->interval before packet can be dropped. ");
- m_firstAboveTime = now + Time2CoDel (m_interval);
- }
- else
- if (CoDelTimeAfter (now, m_firstAboveTime))
- {
- NS_LOG_LOGIC ("Sojourn time has been above target for at least q->interval; it's OK to (possibly) drop packet.");
- okToDrop = true;
- ++m_state1;
- }
- return okToDrop;
-}
-
-Ptr<Packet>
-CoDelQueue::DoDequeue (void)
-{
- NS_LOG_FUNCTION (this);
-
- if (m_packets.empty ())
- {
- // Leave dropping state when queue is empty
- m_dropping = false;
- m_firstAboveTime = 0;
- NS_LOG_LOGIC ("Queue empty");
- return 0;
- }
- uint32_t now = CoDelGetTime ();
- Ptr<Packet> p = m_packets.front ();
- m_packets.pop ();
- m_bytesInQueue -= p->GetSize ();
-
- NS_LOG_LOGIC ("Popped " << p);
- NS_LOG_LOGIC ("Number packets remaining " << m_packets.size ());
- NS_LOG_LOGIC ("Number bytes remaining " << m_bytesInQueue);
-
- // Determine if p should be dropped
- bool okToDrop = OkToDrop (p, now);
-
- if (m_dropping)
- { // In the dropping state (sojourn time has gone above target and hasn't come down yet)
- // Check if we can leave the dropping state or next drop should occur
- NS_LOG_LOGIC ("In dropping state, check if it's OK to leave or next drop should occur");
- if (!okToDrop)
- {
- /* sojourn time fell below target - leave dropping state */
- NS_LOG_LOGIC ("Sojourn time goes below target, it's OK to leave dropping state.");
- m_dropping = false;
- }
- else
- if (CoDelTimeAfterEq (now, m_dropNext))
- {
- m_state2++;
- while (m_dropping && CoDelTimeAfterEq (now, m_dropNext))
- {
- // 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 amount of packets in queue might result in drop
- // rates so high that the next drop should happen now,
- // hence the while loop.
- NS_LOG_LOGIC ("Sojourn time is still above target and it's time for next drop; dropping " << p);
- Drop (p);
-
- // p was in queue, trace dequeue and update stats manually
- m_traceDequeue (p);
- m_nBytes -= p->GetSize ();
- m_nPackets--;
-
- ++m_dropCount;
- ++m_count;
- NewtonStep ();
- 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 remaining " << m_packets.size ());
- NS_LOG_LOGIC ("Number bytes remaining " << m_bytesInQueue);
-
- if (!OkToDrop (p, now))
- {
- /* leave dropping state */
- NS_LOG_LOGIC ("Leaving dropping state");
- m_dropping = false;
- }
- else
- {
- /* schedule the next drop */
- NS_LOG_LOGIC ("Running ControlLaw for input m_dropNext: " << (double)m_dropNext / 1000000);
- m_dropNext = ControlLaw (m_dropNext);
- NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000);
- }
- }
- }
- }
- else
- {
- // Not in the dropping state
- // Decide if we have to enter the dropping state and drop the first packet
- NS_LOG_LOGIC ("Not in dropping state; decide if we have to enter the state and drop the first packet");
- if (okToDrop)
- {
- // Drop the first packet and enter dropping state unless the queue is empty
- NS_LOG_LOGIC ("Sojourn time goes above target, dropping the first packet " << p << " and entering the dropping state");
- ++m_dropCount;
- Drop (p);
-
- // p was in queue, trace the dequeue and update stats manually
- m_traceDequeue (p);
- m_nBytes -= p->GetSize ();
- m_nPackets--;
-
- if (m_packets.empty ())
- {
- m_dropping = false;
- okToDrop = false;
- NS_LOG_LOGIC ("Queue empty");
- ++m_states;
- }
- else
- {
- p = m_packets.front ();
- m_packets.pop ();
- m_bytesInQueue -= p->GetSize ();
-
- NS_LOG_LOGIC ("Popped " << p);
- NS_LOG_LOGIC ("Number packets remaining " << m_packets.size ());
- NS_LOG_LOGIC ("Number bytes remaining " << m_bytesInQueue);
-
- okToDrop = OkToDrop (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.
- */
- int delta = m_count - m_lastCount;
- if (delta > 1 && CoDelTimeBefore (now - m_dropNext, 16 * Time2CoDel (m_interval)))
- {
- m_count = delta;
- NewtonStep ();
- }
- else
- {
- m_count = 1;
- m_recInvSqrt = ~0U >> REC_INV_SQRT_SHIFT;
- }
- m_lastCount = m_count;
- NS_LOG_LOGIC ("Running ControlLaw for input now: " << (double)now);
- m_dropNext = ControlLaw (now);
- NS_LOG_LOGIC ("Scheduled next drop at " << (double)m_dropNext / 1000000 << " now " << (double)now / 1000000);
- }
- }
- ++m_states;
- return p;
-}
-
-uint32_t
-CoDelQueue::GetQueueSize (void)
-{
- NS_LOG_FUNCTION (this);
- if (GetMode () == QUEUE_MODE_BYTES)
- {
- return m_bytesInQueue;
- }
- else if (GetMode () == QUEUE_MODE_PACKETS)
- {
- return m_packets.size ();
- }
- else
- {
- NS_ABORT_MSG ("Unknown mode.");
- }
-}
-
-uint32_t
-CoDelQueue::GetDropOverLimit (void)
-{
- return m_dropOverLimit;
-}
-
-uint32_t
-CoDelQueue::GetDropCount (void)
-{
- return m_dropCount;
-}
-
-Time
-CoDelQueue::GetTarget (void)
-{
- return m_target;
-}
-
-Time
-CoDelQueue::GetInterval (void)
-{
- return m_interval;
-}
-
-uint32_t
-CoDelQueue::GetDropNext (void)
-{
- return m_dropNext;
-}
-
-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;
-}
-
-bool
-CoDelQueue::CoDelTimeAfter (uint32_t a, uint32_t b)
-{
- return ((int)(a) - (int)(b) > 0);
-}
-
-bool
-CoDelQueue::CoDelTimeAfterEq (uint32_t a, uint32_t b)
-{
- return ((int)(a) - (int)(b) >= 0);
-}
-
-bool
-CoDelQueue::CoDelTimeBefore (uint32_t a, uint32_t b)
-{
- return ((int)(a) - (int)(b) < 0);
-}
-
-bool
-CoDelQueue::CoDelTimeBeforeEq (uint32_t a, uint32_t b)
-{
- return ((int)(a) - (int)(b) <= 0);
-}
-
-uint32_t
-CoDelQueue::Time2CoDel (Time t)
-{
- return (t.GetNanoSeconds () >> CODEL_SHIFT);
-}
-
-
-} // namespace ns3
-

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b