A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
dynamic-queue-limits.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016 Universita' degli Studi di Napoli Federico II
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Authors: Pasquale Imputato <p.imputato@gmail.com>
7 * Stefano Avallone <stefano.avallone@unina.it>
8 *
9 * This code is a port of the dynamic queue limits library implemented
10 * in the Linux kernel by
11 * Author: Tom Herbert <therbert@google.com>
12 */
13
15
16#include "ns3/log.h"
17#include "ns3/simulator.h"
18#include "ns3/string.h"
19#include "ns3/uinteger.h"
20
21// Set some static maximums
22static const uint32_t UINTMAX = std::numeric_limits<uint32_t>::max();
23static const uint32_t DQL_MAX_OBJECT = UINTMAX / 16;
25
26namespace ns3
27{
28
29NS_LOG_COMPONENT_DEFINE("DynamicQueueLimits");
30
31NS_OBJECT_ENSURE_REGISTERED(DynamicQueueLimits);
32
33TypeId
35{
36 static TypeId tid = TypeId("ns3::DynamicQueueLimits")
38 .SetParent<QueueLimits>()
39 .SetGroupName("Network")
40 .AddConstructor<DynamicQueueLimits>()
41 .AddAttribute("HoldTime",
42 "The DQL algorithm hold time",
43 StringValue("1s"),
46 .AddAttribute("MaxLimit",
47 "Maximum limit",
51 .AddAttribute("MinLimit",
52 "Minimum limit",
56 .AddTraceSource("Limit",
57 "Limit value calculated by DQL",
59 "ns3::TracedValueCallback::Uint32");
60 return tid;
61}
62
68
73
74void
76{
77 NS_LOG_FUNCTION(this);
78 // Reset all dynamic values
79 m_limit = 0;
80 m_numQueued = 0;
82 m_lastObjCnt = 0;
85 m_prevOvlimit = 0;
88}
89
90void
92{
93 NS_LOG_FUNCTION(this << count);
94 uint32_t inprogress;
95 uint32_t prevInprogress;
96 uint32_t limit;
97 uint32_t ovlimit;
98 uint32_t completed;
99 uint32_t numQueued;
100 bool allPrevCompleted;
101
102 numQueued = m_numQueued;
103
104 // Can't complete more than what's in queue
105 NS_ASSERT(count <= numQueued - m_numCompleted);
106
107 completed = m_numCompleted + count;
108 limit = m_limit;
109 ovlimit = Posdiff(numQueued - m_numCompleted, limit);
110 inprogress = numQueued - completed;
111 prevInprogress = m_prevNumQueued - m_numCompleted;
112 allPrevCompleted = ((int32_t)(completed - m_prevNumQueued)) >= 0;
113
114 if ((ovlimit && !inprogress) || (m_prevOvlimit && allPrevCompleted))
115 {
116 NS_LOG_DEBUG("Queue starved, increase limit");
117 /*
118 * Queue considered starved if:
119 * - The queue was over-limit in the last interval,
120 * and there is no more data in the queue.
121 * OR
122 * - The queue was over-limit in the previous interval and
123 * when enqueuing it was possible that all queued data
124 * had been consumed. This covers the case when queue
125 * may have becomes starved between completion processing
126 * running and next time enqueue was scheduled.
127 *
128 * When queue is starved increase the limit by the amount
129 * of bytes both sent and completed in the last interval,
130 * plus any previous over-limit.
131 */
132 limit += Posdiff(completed, m_prevNumQueued) + m_prevOvlimit;
135 }
136 else if (inprogress && prevInprogress && !allPrevCompleted)
137 {
138 NS_LOG_DEBUG("Queue not starved, check decrease limit");
139 /*
140 * Queue was not starved, check if the limit can be decreased.
141 * A decrease is only considered if the queue has been busy in
142 * the whole interval (the check above).
143 *
144 * If there is slack, the amount of execess data queued above
145 * the the amount needed to prevent starvation, the queue limit
146 * can be decreased. To avoid hysteresis we consider the
147 * minimum amount of slack found over several iterations of the
148 * completion routine.
149 */
150 uint32_t slack;
151 uint32_t slackLastObjs;
152
153 /*
154 * Slack is the maximum of
155 * - The queue limit plus previous over-limit minus twice
156 * the number of objects completed. Note that two times
157 * number of completed bytes is a basis for an upper bound
158 * of the limit.
159 * - Portion of objects in the last queuing operation that
160 * was not part of non-zero previous over-limit. That is
161 * "round down" by non-overlimit portion of the last
162 * queueing operation.
163 */
164 slack = Posdiff(limit + m_prevOvlimit, 2 * (completed - m_numCompleted));
165 slackLastObjs = m_prevOvlimit ? Posdiff(m_prevLastObjCnt, m_prevOvlimit) : 0;
166
167 slack = std::max(slack, slackLastObjs);
168
169 if (slack < m_lowestSlack)
170 {
171 m_lowestSlack = slack;
172 }
173
175 {
176 limit = Posdiff(limit, m_lowestSlack);
179 }
180 }
181
182 // Enforce bounds on limit
183 limit = std::min((uint32_t)std::max(limit, m_minLimit), m_maxLimit);
184
185 if (limit != m_limit)
186 {
187 NS_LOG_DEBUG("Update limit");
188 m_limit = limit;
189 ovlimit = 0;
190 }
191
192 m_adjLimit = limit + completed;
193 m_prevOvlimit = ovlimit;
195 m_numCompleted = completed;
196 m_prevNumQueued = numQueued;
197}
198
201{
202 NS_LOG_FUNCTION(this);
203 return (m_adjLimit - m_numQueued);
204}
205
206void
208{
209 NS_LOG_FUNCTION(this << count);
210 NS_ASSERT(count <= DQL_MAX_OBJECT);
211
212 m_lastObjCnt = count;
213 m_numQueued += count;
214}
215
218{
219 NS_LOG_FUNCTION(this << a << b);
220 return std::max((a - b), 0);
221}
222
223} // namespace ns3
DynamicQueueLimits would be used in conjunction with a producer/consumer type queue (possibly a netde...
uint32_t m_adjLimit
limit + num_completed
void Reset() override
Reset queue limits state.
uint32_t m_numCompleted
Total ever completed.
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.
uint32_t m_prevNumQueued
Previous queue total.
uint32_t m_lastObjCnt
Count at last queuing.
uint32_t m_prevLastObjCnt
Previous queuing cnt.
static TypeId GetTypeId()
Get the type ID.
void Completed(uint32_t count) override
Record number of completed bytes and recalculate the limit.
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.
int32_t Available() const override
Available is called from NotifyTransmittedBytes to calculate the number of bytes that can be passed a...
TracedValue< uint32_t > m_limit
Current limit.
void Queued(uint32_t count) override
Record the number of bytes queued.
uint32_t m_maxLimit
Max limit.
A base class which provides memory management and object aggregation.
Definition object.h:78
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
Hold variables of type string.
Definition string.h:45
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
Hold an unsigned integer type.
Definition uinteger.h:34
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:55
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#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:35
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 > MakeUintegerChecker()
Definition uinteger.h:85
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition nstime.h:1396
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition uinteger.h:35
Ptr< const AttributeChecker > MakeTimeChecker()
Helper to make an unbounded Time checker.
Definition nstime.h:1416