A Discrete-Event Network Simulator
API
dynamic-queue-limits.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2016 Universita' degli Studi di Napoli Federico II
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  * Authors: Pasquale Imputato <p.imputato@gmail.com>
19  * Stefano Avallone <stefano.avallone@unina.it>
20  *
21  * This code is a port of the dynamic queue limits library implemented
22  * in the Linux kernel by
23  * Author: Tom Herbert <therbert@google.com>
24  */
25 
26 #include "ns3/log.h"
27 #include "ns3/uinteger.h"
28 #include "ns3/simulator.h"
29 #include "ns3/string.h"
30 #include "dynamic-queue-limits.h"
31 
32 // Set some static maximums
33 static const uint32_t UINTMAX = std::numeric_limits<uint32_t>::max ();
34 static const uint32_t DQL_MAX_OBJECT = UINTMAX / 16;
35 static const uint32_t DQL_MAX_LIMIT = (UINTMAX / 2) - DQL_MAX_OBJECT;
36 
37 namespace ns3 {
38 
39 NS_LOG_COMPONENT_DEFINE ("DynamicQueueLimits");
40 
41 NS_OBJECT_ENSURE_REGISTERED (DynamicQueueLimits);
42 
43 TypeId
45 {
46  static TypeId tid = TypeId ("ns3::DynamicQueueLimits")
47  .SetParent<Object> ()
48  .SetParent<QueueLimits> ()
49  .SetGroupName ("Network")
50  .AddConstructor<DynamicQueueLimits> ()
51  .AddAttribute ("HoldTime",
52  "The DQL algorithm hold time",
53  StringValue ("1s"),
55  MakeTimeChecker ())
56  .AddAttribute ("MaxLimit",
57  "Maximum limit",
60  MakeUintegerChecker<uint32_t> (0, DQL_MAX_LIMIT))
61  .AddAttribute ("MinLimit",
62  "Minimum limit",
63  UintegerValue (0),
65  MakeUintegerChecker<uint32_t> ())
66  .AddTraceSource ("Limit",
67  "Limit value calculated by DQL",
69  "ns3::TracedValueCallback::Uint32")
70  ;
71  return tid;
72 }
73 
75 {
76  NS_LOG_FUNCTION (this);
77  Reset ();
78 }
79 
81 {
82  NS_LOG_FUNCTION (this);
83 }
84 
85 void
87 {
88  NS_LOG_FUNCTION (this);
89  // Reset all dynamic values
90  m_limit = 0;
91  m_numQueued = 0;
92  m_numCompleted = 0;
93  m_lastObjCnt = 0;
94  m_prevNumQueued = 0;
95  m_prevLastObjCnt = 0;
96  m_prevOvlimit = 0;
99 }
100 
101 void
103 {
104  NS_LOG_FUNCTION (this << count);
105  uint32_t inprogress, prevInprogress, limit;
106  uint32_t ovlimit, completed, numQueued;
107  bool allPrevCompleted;
108 
109  numQueued = m_numQueued;
110 
111  // Can't complete more than what's in queue
112  NS_ASSERT (count <= numQueued - m_numCompleted);
113 
114  completed = m_numCompleted + count;
115  limit = m_limit;
116  ovlimit = Posdiff (numQueued - m_numCompleted, limit);
117  inprogress = numQueued - completed;
118  prevInprogress = m_prevNumQueued - m_numCompleted;
119  allPrevCompleted = ((int32_t)(completed - m_prevNumQueued)) >= 0;
120 
121  if ((ovlimit && !inprogress) || (m_prevOvlimit && allPrevCompleted))
122  {
123  NS_LOG_DEBUG ("Queue starved, increase limit");
124  /*
125  * Queue considered starved if:
126  * - The queue was over-limit in the last interval,
127  * and there is no more data in the queue.
128  * OR
129  * - The queue was over-limit in the previous interval and
130  * when enqueuing it was possible that all queued data
131  * had been consumed. This covers the case when queue
132  * may have becomes starved between completion processing
133  * running and next time enqueue was scheduled.
134  *
135  * When queue is starved increase the limit by the amount
136  * of bytes both sent and completed in the last interval,
137  * plus any previous over-limit.
138  */
139  limit += Posdiff (completed, m_prevNumQueued) + m_prevOvlimit;
142  }
143  else if (inprogress && prevInprogress && !allPrevCompleted)
144  {
145  NS_LOG_DEBUG ("Queue not starved, check decrease limit");
146  /*
147  * Queue was not starved, check if the limit can be decreased.
148  * A decrease is only considered if the queue has been busy in
149  * the whole interval (the check above).
150  *
151  * If there is slack, the amount of execess data queued above
152  * the the amount needed to prevent starvation, the queue limit
153  * can be decreased. To avoid hysteresis we consider the
154  * minimum amount of slack found over several iterations of the
155  * completion routine.
156  */
157  uint32_t slack, slackLastObjs;
158 
159  /*
160  * Slack is the maximum of
161  * - The queue limit plus previous over-limit minus twice
162  * the number of objects completed. Note that two times
163  * number of completed bytes is a basis for an upper bound
164  * of the limit.
165  * - Portion of objects in the last queuing operation that
166  * was not part of non-zero previous over-limit. That is
167  * "round down" by non-overlimit portion of the last
168  * queueing operation.
169  */
170  slack = Posdiff (limit + m_prevOvlimit, 2 * (completed - m_numCompleted));
171  slackLastObjs = m_prevOvlimit ? Posdiff (m_prevLastObjCnt, m_prevOvlimit) : 0;
172 
173  slack = std::max (slack, slackLastObjs);
174 
175  if (slack < m_lowestSlack)
176  {
177  m_lowestSlack = slack;
178  }
179 
181  {
182  limit = Posdiff (limit, m_lowestSlack);
185  }
186  }
187 
188  // Enforce bounds on limit
189  limit = std::min ((uint32_t)std::max (limit, m_minLimit), m_maxLimit);
190 
191  if (limit != m_limit)
192  {
193  NS_LOG_DEBUG ("Update limit");
194  m_limit = limit;
195  ovlimit = 0;
196  }
197 
198  m_adjLimit = limit + completed;
199  m_prevOvlimit = ovlimit;
201  m_numCompleted = completed;
202  m_prevNumQueued = numQueued;
203 }
204 
205 int32_t
207 {
208  NS_LOG_FUNCTION (this);
209  return (m_adjLimit - m_numQueued);
210 }
211 
212 void
214 {
215  NS_LOG_FUNCTION (this << count);
216  NS_ASSERT (count <= DQL_MAX_OBJECT);
217 
218  m_lastObjCnt = count;
219  m_numQueued += count;
220 }
221 
222 int32_t
223 DynamicQueueLimits::Posdiff (int32_t a, int32_t b)
224 {
225  NS_LOG_FUNCTION (this << a << b);
226  return std::max ((a - b), 0);
227 }
228 
229 } // namespace ns3
#define min(a, b)
Definition: 80211b.c:42
#define max(a, b)
Definition: 80211b.c:43
DynamicQueueLimits would be used in conjunction with a producer/consumer type queue (possibly a netde...
uint32_t m_adjLimit
limit + num_completed
uint32_t m_numCompleted
Total ever completed.
static TypeId GetTypeId(void)
Get the type ID.
Time m_slackStartTime
Time slacks seen.
uint32_t m_numQueued
Total ever queued.
uint32_t m_prevOvlimit
Previous over limit.
uint32_t m_minLimit
Minimum limit.
Time m_slackHoldTime
Time to measure slack.
virtual int32_t Available() const
Available is called from NotifyTransmittedBytes to calculate the number of bytes that can be passed a...
uint32_t m_prevNumQueued
Previous queue total.
virtual void Queued(uint32_t count)
Record the number of bytes queued.
virtual void Reset()
Reset queue limits state.
uint32_t m_lastObjCnt
Count at last queuing.
uint32_t m_prevLastObjCnt
Previous queuing cnt.
int32_t Posdiff(int32_t a, int32_t b)
Calculates the difference between the two operators and returns the number if positive,...
uint32_t m_lowestSlack
Lowest slack found.
TracedValue< uint32_t > m_limit
Current limit.
uint32_t m_maxLimit
Max limit.
virtual void Completed(uint32_t count)
Record number of completed bytes and recalculate the limit.
A base class which provides memory management and object aggregation.
Definition: object.h:88
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Hold variables of type string.
Definition: string.h:41
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Hold an unsigned integer type.
Definition: uinteger.h:44
static const uint32_t DQL_MAX_LIMIT
static const uint32_t UINTMAX
static const uint32_t DQL_MAX_OBJECT
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:67
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: nstime.h:1309
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: uinteger.h:45
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:522