A Discrete-Event Network Simulator
API
tcp-cubic.cc
Go to the documentation of this file.
1/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2014 Natale Patriciello <natale.patriciello@gmail.com>
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 */
19
20#define NS_LOG_APPEND_CONTEXT \
21 { std::clog << Simulator::Now ().GetSeconds () << " "; }
22
23#include "tcp-cubic.h"
24#include "ns3/log.h"
25
26NS_LOG_COMPONENT_DEFINE ("TcpCubic");
27
28namespace ns3 {
29
31
32TypeId
34{
35 static TypeId tid = TypeId ("ns3::TcpCubic")
37 .AddConstructor<TcpCubic> ()
38 .SetGroupName ("Internet")
39 .AddAttribute ("FastConvergence", "Enable (true) or disable (false) fast convergence",
40 BooleanValue (true),
43 .AddAttribute ("Beta", "Beta for multiplicative decrease",
44 DoubleValue (0.7),
46 MakeDoubleChecker <double> (0.0))
47 .AddAttribute ("HyStart", "Enable (true) or disable (false) hybrid slow start algorithm",
48 BooleanValue (true),
51 .AddAttribute ("HyStartLowWindow", "Lower bound cWnd for hybrid slow start (segments)",
52 UintegerValue (16),
54 MakeUintegerChecker <uint32_t> ())
55 .AddAttribute ("HyStartDetect", "Hybrid Slow Start detection mechanisms:" \
56 "1: packet train, 2: delay, 3: both",
57 IntegerValue (3),
59 MakeIntegerChecker <int> (1,3))
60 .AddAttribute ("HyStartMinSamples", "Number of delay samples for detecting the increase of delay",
61 UintegerValue (8),
63 MakeUintegerChecker <uint8_t> ())
64 .AddAttribute ("HyStartAckDelta", "Spacing between ack's indicating train",
68 .AddAttribute ("HyStartDelayMin", "Minimum time for hystart algorithm",
72 .AddAttribute ("HyStartDelayMax", "Maximum time for hystart algorithm",
73 TimeValue (MilliSeconds (1000)),
76 .AddAttribute ("CubicDelta", "Delta Time to wait after fast recovery before adjusting param",
80 .AddAttribute ("CntClamp", "Counter value when no losses are detected (counter is used" \
81 " when incrementing cWnd in congestion avoidance, to avoid" \
82 " floating point arithmetic). It is the modulo of the (avoided)" \
83 " division",
84 UintegerValue (20),
86 MakeUintegerChecker <uint8_t> ())
87 .AddAttribute ("C", "Cubic Scaling factor",
88 DoubleValue (0.4),
90 MakeDoubleChecker <double> (0.0))
91 ;
92 return tid;
93}
94
97 m_cWndCnt (0),
98 m_lastMaxCwnd (0),
99 m_bicOriginPoint (0),
100 m_bicK (0.0),
101 m_delayMin (Time::Min ()),
102 m_epochStart (Time::Min ()),
103 m_found (false),
104 m_roundStart (Time::Min ()),
105 m_endSeq (0),
106 m_lastAck (Time::Min ()),
107 m_cubicDelta (Time::Min ()),
108 m_currRtt (Time::Min ()),
109 m_sampleCnt (0)
110{
111 NS_LOG_FUNCTION (this);
112}
113
115 : TcpCongestionOps (sock),
116 m_fastConvergence (sock.m_fastConvergence),
117 m_beta (sock.m_beta),
118 m_hystart (sock.m_hystart),
119 m_hystartDetect (sock.m_hystartDetect),
120 m_hystartLowWindow (sock.m_hystartLowWindow),
121 m_hystartAckDelta (sock.m_hystartAckDelta),
122 m_hystartDelayMin (sock.m_hystartDelayMin),
123 m_hystartDelayMax (sock.m_hystartDelayMax),
124 m_hystartMinSamples (sock.m_hystartMinSamples),
125 m_initialCwnd (sock.m_initialCwnd),
126 m_cntClamp (sock.m_cntClamp),
127 m_c (sock.m_c),
128 m_cWndCnt (sock.m_cWndCnt),
129 m_lastMaxCwnd (sock.m_lastMaxCwnd),
130 m_bicOriginPoint (sock.m_bicOriginPoint),
131 m_bicK (sock.m_bicK),
132 m_delayMin (sock.m_delayMin),
133 m_epochStart (sock.m_epochStart),
134 m_found (sock.m_found),
135 m_roundStart (sock.m_roundStart),
136 m_endSeq (sock.m_endSeq),
137 m_lastAck (sock.m_lastAck),
138 m_cubicDelta (sock.m_cubicDelta),
139 m_currRtt (sock.m_currRtt),
140 m_sampleCnt (sock.m_sampleCnt)
141{
142 NS_LOG_FUNCTION (this);
143}
144
145std::string
147{
148 return "TcpCubic";
149}
150
151void
153{
154 NS_LOG_FUNCTION (this);
155
157 m_endSeq = tcb->m_highTxMark;
158 m_currRtt = Time::Min ();
159 m_sampleCnt = 0;
160}
161
162void
164{
165 NS_LOG_FUNCTION (this << tcb << segmentsAcked);
166
167 if (tcb->m_cWnd < tcb->m_ssThresh)
168 {
169
170 if (m_hystart && tcb->m_lastAckedSeq > m_endSeq)
171 {
172 HystartReset (tcb);
173 }
174
175 // In Linux, the QUICKACK socket option enables the receiver to send
176 // immediate acks initially (during slow start) and then transition
177 // to delayed acks. ns-3 does not implement QUICKACK, and if ack
178 // counting instead of byte counting is used during slow start window
179 // growth, when TcpSocket::DelAckCount==2, then the slow start will
180 // not reach as large of an initial window as in Linux. Therefore,
181 // we can approximate the effect of QUICKACK by making this slow
182 // start phase perform Appropriate Byte Counting (RFC 3465)
183 tcb->m_cWnd += segmentsAcked * tcb->m_segmentSize;
184 segmentsAcked = 0;
185
186 NS_LOG_INFO ("In SlowStart, updated to cwnd " << tcb->m_cWnd <<
187 " ssthresh " << tcb->m_ssThresh);
188 }
189
190 if (tcb->m_cWnd >= tcb->m_ssThresh && segmentsAcked > 0)
191 {
192 m_cWndCnt += segmentsAcked;
193 uint32_t cnt = Update (tcb);
194
195 /* According to RFC 6356 even once the new cwnd is
196 * calculated you must compare this to the number of ACKs received since
197 * the last cwnd update. If not enough ACKs have been received then cwnd
198 * cannot be updated.
199 */
200 if (m_cWndCnt >= cnt)
201 {
202 tcb->m_cWnd += tcb->m_segmentSize;
203 m_cWndCnt -= cnt;
204 NS_LOG_INFO ("In CongAvoid, updated to cwnd " << tcb->m_cWnd);
205 }
206 else
207 {
208 NS_LOG_INFO ("Not enough segments have been ACKed to increment cwnd."
209 "Until now " << m_cWndCnt << " cnd " << cnt);
210 }
211 }
212}
213
216{
217 NS_LOG_FUNCTION (this);
218 Time t;
219 uint32_t delta, bicTarget, cnt = 0;
220 double offs;
221 uint32_t segCwnd = tcb->GetCwndInSegments ();
222
223 if (m_epochStart == Time::Min ())
224 {
225 m_epochStart = Simulator::Now (); // record the beginning of an epoch
226
227 if (m_lastMaxCwnd <= segCwnd)
228 {
229 NS_LOG_DEBUG ("lastMaxCwnd <= m_cWnd. K=0 and origin=" << segCwnd);
230 m_bicK = 0.0;
231 m_bicOriginPoint = segCwnd;
232 }
233 else
234 {
235 m_bicK = std::pow ((m_lastMaxCwnd - segCwnd) / m_c, 1 / 3.);
237 NS_LOG_DEBUG ("lastMaxCwnd > m_cWnd. K=" << m_bicK <<
238 " and origin=" << m_lastMaxCwnd);
239 }
240 }
241
243
244 if (t.GetSeconds () < m_bicK) /* t - K */
245 {
246 offs = m_bicK - t.GetSeconds ();
247 NS_LOG_DEBUG ("t=" << t.GetSeconds () << " <k: offs=" << offs);
248 }
249 else
250 {
251 offs = t.GetSeconds () - m_bicK;
252 NS_LOG_DEBUG ("t=" << t.GetSeconds () << " >= k: offs=" << offs);
253 }
254
255
256 /* Constant value taken from Experimental Evaluation of Cubic Tcp, available at
257 * eprints.nuim.ie/1716/1/Hamiltonpfldnet2007_cubic_final.pdf */
258 delta = m_c * std::pow (offs, 3);
259
260 NS_LOG_DEBUG ("delta: " << delta);
261
262 if (t.GetSeconds () < m_bicK)
263 {
264 // below origin
265 bicTarget = m_bicOriginPoint - delta;
266 NS_LOG_DEBUG ("t < k: Bic Target: " << bicTarget);
267 }
268 else
269 {
270 // above origin
271 bicTarget = m_bicOriginPoint + delta;
272 NS_LOG_DEBUG ("t >= k: Bic Target: " << bicTarget);
273 }
274
275 // Next the window target is converted into a cnt or count value. CUBIC will
276 // wait until enough new ACKs have arrived that a counter meets or exceeds
277 // this cnt value. This is how the CUBIC implementation simulates growing
278 // cwnd by values other than 1 segment size.
279 if (bicTarget > segCwnd)
280 {
281 cnt = segCwnd / (bicTarget - segCwnd);
282 NS_LOG_DEBUG ("target>cwnd. cnt=" << cnt);
283 }
284 else
285 {
286 cnt = 100 * segCwnd;
287 }
288
289 if (m_lastMaxCwnd == 0 && cnt > m_cntClamp)
290 {
291 cnt = m_cntClamp;
292 }
293
294 // The maximum rate of cwnd increase CUBIC allows is 1 packet per
295 // 2 packets ACKed, meaning cwnd grows at 1.5x per RTT.
296 return std::max (cnt, 2U);
297}
298
299void
301 const Time &rtt)
302{
303 NS_LOG_FUNCTION (this << tcb << segmentsAcked << rtt);
304
305 /* Discard delay samples right after fast recovery */
306 if (m_epochStart != Time::Min ()
308 {
309 return;
310 }
311
312 /* first time call or link delay decreases */
313 if (m_delayMin == Time::Min () || m_delayMin > rtt)
314 {
315 m_delayMin = rtt;
316 }
317
318 /* hystart triggers when cwnd is larger than some threshold */
319 if (m_hystart
320 && tcb->m_cWnd <= tcb->m_ssThresh
321 && tcb->m_cWnd >= m_hystartLowWindow * tcb->m_segmentSize)
322 {
323 HystartUpdate (tcb, rtt);
324 }
325}
326
327void
329{
330 NS_LOG_FUNCTION (this << delay);
331
332 if (!(m_found & m_hystartDetect))
333 {
334 Time now = Simulator::Now ();
335
336 /* first detection parameter - ack-train detection */
337 if ((now - m_lastAck) <= m_hystartAckDelta)
338 {
339 m_lastAck = now;
340
341 if ((now - m_roundStart) > m_delayMin)
342 {
344 }
345 }
346
347 /* obtain the minimum delay of more than sampling packets */
349 {
350 if (m_currRtt == Time::Min () || m_currRtt > delay)
351 {
352 m_currRtt = delay;
353 }
354
355 ++m_sampleCnt;
356 }
357 else
358 {
359 if (m_currRtt > m_delayMin +
361 {
362 m_found |= DELAY;
363 }
364 }
365 /*
366 * Either one of two conditions are met,
367 * we exit from slow start immediately.
368 */
370 {
371 NS_LOG_DEBUG ("Exit from SS, immediately :-)");
372 tcb->m_ssThresh = tcb->m_cWnd;
373 }
374 }
375}
376
377Time
379{
380 NS_LOG_FUNCTION (this << t);
381
382 Time ret = t;
383 if (t > m_hystartDelayMax)
384 {
385 ret = m_hystartDelayMax;
386 }
387 else if (t < m_hystartDelayMin)
388 {
389 ret = m_hystartDelayMin;
390 }
391
392 return ret;
393}
394
397{
398 NS_LOG_FUNCTION (this << tcb << bytesInFlight);
399
400 uint32_t segCwnd = tcb->GetCwndInSegments ();
401 NS_LOG_DEBUG ("Loss at cWnd=" << segCwnd << " segments in flight=" << bytesInFlight / tcb->m_segmentSize);
402
403 /* Wmax and fast convergence */
404 if (segCwnd < m_lastMaxCwnd && m_fastConvergence)
405 {
406 m_lastMaxCwnd = (segCwnd * (1 + m_beta)) / 2; // Section 4.6 in RFC 8312
407 }
408 else
409 {
410 m_lastMaxCwnd = segCwnd;
411 }
412
413 m_epochStart = Time::Min (); // end of epoch
414
415 /* Formula taken from the Linux kernel */
416 uint32_t ssThresh = std::max (static_cast<uint32_t> (segCwnd * m_beta ), 2U) * tcb->m_segmentSize;
417
418 NS_LOG_DEBUG ("SsThresh = " << ssThresh);
419
420 return ssThresh;
421}
422
423void
425{
426 NS_LOG_FUNCTION (this << tcb << newState);
427
428 if (newState == TcpSocketState::CA_LOSS)
429 {
430 CubicReset (tcb);
431 HystartReset (tcb);
432 }
433}
434
435void
437{
438 NS_LOG_FUNCTION (this << tcb);
439
440 m_lastMaxCwnd = 0;
442 m_bicK = 0;
444 m_found = false;
445}
446
449{
450 NS_LOG_FUNCTION (this);
451 return CopyObject<TcpCubic> (this);
452}
453
454}
#define max(a, b)
Definition: 80211b.c:43
AttributeValue implementation for Boolean.
Definition: boolean.h:37
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition: double.h:41
Hold a signed integer type.
Definition: integer.h:44
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Congestion control abstract class.
The Cubic Congestion Control Algorithm.
Definition: tcp-cubic.h:71
Time m_currRtt
Current Rtt.
Definition: tcp-cubic.h:135
void HystartReset(Ptr< const TcpSocketState > tcb)
Reset HyStart parameters.
Definition: tcp-cubic.cc:152
Time m_hystartDelayMax
Maximum time for hystart algorithm.
Definition: tcp-cubic.h:114
Time m_cubicDelta
Time to wait after recovery before update.
Definition: tcp-cubic.h:134
uint32_t m_bicOriginPoint
Origin point of bic function.
Definition: tcp-cubic.h:125
uint32_t Update(Ptr< TcpSocketState > tcb)
Cubic window update after a new ack received.
Definition: tcp-cubic.cc:215
uint32_t m_sampleCnt
Count of samples for HyStart.
Definition: tcp-cubic.h:136
virtual Ptr< TcpCongestionOps > Fork()
Copy the congestion control algorithm across sockets.
Definition: tcp-cubic.cc:448
bool m_hystart
Enable or disable HyStart algorithm.
Definition: tcp-cubic.h:109
double m_bicK
Time to origin point from the beginning.
Definition: tcp-cubic.h:126
virtual void IncreaseWindow(Ptr< TcpSocketState > tcb, uint32_t segmentsAcked)
Congestion avoidance algorithm implementation.
Definition: tcp-cubic.cc:163
int m_hystartDetect
Detect way for HyStart algorithm.
Definition: tcp-cubic.h:110
uint32_t m_cWndCnt
cWnd integer-to-float counter
Definition: tcp-cubic.h:123
Time m_hystartDelayMin
Minimum time for hystart algorithm.
Definition: tcp-cubic.h:113
bool m_found
The exit point is found?
Definition: tcp-cubic.h:130
SequenceNumber32 m_endSeq
End sequence of the round.
Definition: tcp-cubic.h:132
double m_beta
Beta for cubic multiplicative increase.
Definition: tcp-cubic.h:107
Time m_lastAck
Last time when the ACK spacing is close.
Definition: tcp-cubic.h:133
Time m_hystartAckDelta
Spacing between ack's indicating train.
Definition: tcp-cubic.h:112
bool m_fastConvergence
Enable or disable fast convergence algorithm.
Definition: tcp-cubic.h:106
Time m_delayMin
Min delay.
Definition: tcp-cubic.h:128
Time m_roundStart
Beginning of each round.
Definition: tcp-cubic.h:131
virtual std::string GetName() const
Get the name of the congestion control algorithm.
Definition: tcp-cubic.cc:146
Time m_epochStart
Beginning of an epoch.
Definition: tcp-cubic.h:129
uint8_t m_cntClamp
Modulo of the (avoided) float division for cWnd.
Definition: tcp-cubic.h:118
virtual void PktsAcked(Ptr< TcpSocketState > tcb, uint32_t segmentsAcked, const Time &rtt)
Timing information on received ACK.
Definition: tcp-cubic.cc:300
void HystartUpdate(Ptr< TcpSocketState > tcb, const Time &delay)
Update HyStart parameters.
Definition: tcp-cubic.cc:328
double m_c
Cubic Scaling factor.
Definition: tcp-cubic.h:120
void CubicReset(Ptr< const TcpSocketState > tcb)
Reset Cubic parameters.
Definition: tcp-cubic.cc:436
static TypeId GetTypeId(void)
Get the type ID.
Definition: tcp-cubic.cc:33
virtual void CongestionStateSet(Ptr< TcpSocketState > tcb, const TcpSocketState::TcpCongState_t newState)
Trigger events/calculations specific to a congestion state.
Definition: tcp-cubic.cc:424
@ DELAY
Detection by delay value.
Definition: tcp-cubic.h:103
@ PACKET_TRAIN
Detection by trains of packet.
Definition: tcp-cubic.h:102
uint32_t m_lastMaxCwnd
Last maximum cWnd.
Definition: tcp-cubic.h:124
virtual uint32_t GetSsThresh(Ptr< const TcpSocketState > tcb, uint32_t bytesInFlight)
Get the slow start threshold after a loss event.
Definition: tcp-cubic.cc:396
Time HystartDelayThresh(const Time &t) const
Clamp time value in a range.
Definition: tcp-cubic.cc:378
uint8_t m_hystartMinSamples
Number of delay samples for detecting the increase of delay.
Definition: tcp-cubic.h:115
uint32_t m_hystartLowWindow
Lower bound cWnd for hybrid slow start (segments)
Definition: tcp-cubic.h:111
A base class for implementation of a stream socket using TCP.
uint32_t m_segmentSize
Segment size.
uint32_t GetCwndInSegments() const
Get cwnd in segments rather than bytes.
TcpCongState_t
Definition of the Congestion state machine.
@ CA_LOSS
CWND was reduced due to RTO timeout or SACK reneging.
SequenceNumber32 m_lastAckedSeq
Last sequence ACKed.
TracedValue< uint32_t > m_cWnd
Congestion window.
TracedValue< uint32_t > m_ssThresh
Slow start threshold.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:379
static Time Min()
Minimum representable Time Not to be confused with Min(Time,Time).
Definition: nstime.h:273
AttributeValue implementation for Time.
Definition: nstime.h:1308
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
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition: boolean.h:85
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Definition: double.h:42
Ptr< const AttributeAccessor > MakeIntegerAccessor(T1 a1)
Definition: integer.h:45
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Definition: nstime.h:1309
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition: uinteger.h:45
int64x64_t Min(const int64x64_t &a, const int64x64_t &b)
Minimum.
Definition: int64x64.h:218
#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_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition: nstime.h:1252
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