A Discrete-Event Network Simulator
API
tcp-illinois.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 ResiliNets, ITTC, University of Kansas
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License version 2 as
6  * published by the Free Software Foundation;
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public License
14  * along with this program; if not, write to the Free Software
15  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16  *
17  * Author: Keerthi Ganta <keerthiganta@ku.edu>
18  * Truc Anh N. Nguyen <annguyen@ittc.ku.edu>
19  *
20  * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
21  * ResiliNets Research Group https://resilinets.org/
22  * Information and Telecommunication Technology Center (ITTC)
23  * and Department of Electrical Engineering and Computer Science
24  * The University of Kansas Lawrence, KS USA.
25  */
26 
27 #include "tcp-illinois.h"
28 
29 #include "tcp-socket-state.h"
30 
31 #include "ns3/log.h"
32 
33 namespace ns3
34 {
35 
36 NS_LOG_COMPONENT_DEFINE("TcpIllinois");
37 NS_OBJECT_ENSURE_REGISTERED(TcpIllinois);
38 
39 TypeId
41 {
42  static TypeId tid = TypeId("ns3::TcpIllinois")
44  .AddConstructor<TcpIllinois>()
45  .SetGroupName("Internet")
46  .AddAttribute("AlphaMin",
47  "Minimum alpha threshold",
48  DoubleValue(0.3),
50  MakeDoubleChecker<double>())
51  .AddAttribute("AlphaMax",
52  "Maximum alpha threshold",
53  DoubleValue(10.0),
55  MakeDoubleChecker<double>())
56  .AddAttribute("AlphaBase",
57  "Alpha base threshold",
58  DoubleValue(1.0),
60  MakeDoubleChecker<double>())
61  .AddAttribute("BetaMin",
62  "Minimum beta threshold",
63  DoubleValue(0.125),
65  MakeDoubleChecker<double>())
66  .AddAttribute("BetaMax",
67  "Maximum beta threshold",
68  DoubleValue(0.5),
70  MakeDoubleChecker<double>())
71  .AddAttribute("BetaBase",
72  "Beta base threshold",
73  DoubleValue(0.5),
75  MakeDoubleChecker<double>())
76  .AddAttribute("WinThresh",
77  "Window threshold",
78  UintegerValue(15),
80  MakeUintegerChecker<uint32_t>())
81  .AddAttribute("Theta",
82  "Theta threshold",
83  UintegerValue(5),
85  MakeUintegerChecker<uint32_t>());
86  return tid;
87 }
88 
90  : TcpNewReno(),
91  m_sumRtt(Time(0)),
92  m_cntRtt(0),
93  m_baseRtt(Time::Max()),
94  m_maxRtt(Time::Min()),
95  m_endSeq(0),
96  m_rttAbove(false),
97  m_rttLow(0),
98  m_alphaMin(0.3),
99  m_alphaMax(10.0),
100  m_alphaBase(1.0),
101  m_alpha(m_alphaMax),
102  m_betaMin(0.125),
103  m_betaMax(0.5),
104  m_betaBase(0.5),
105  m_beta(m_betaBase),
106  m_winThresh(15),
107  m_theta(5),
108  m_ackCnt(0)
109 {
110  NS_LOG_FUNCTION(this);
111 }
112 
114  : TcpNewReno(sock),
115  m_sumRtt(sock.m_sumRtt),
116  m_cntRtt(sock.m_cntRtt),
117  m_baseRtt(sock.m_baseRtt),
118  m_maxRtt(sock.m_maxRtt),
119  m_endSeq(sock.m_endSeq),
120  m_rttAbove(sock.m_rttAbove),
121  m_rttLow(sock.m_rttLow),
122  m_alphaMin(sock.m_alphaMin),
123  m_alphaMax(sock.m_alphaMax),
124  m_alphaBase(sock.m_alphaBase),
125  m_alpha(sock.m_alpha),
126  m_betaMin(sock.m_betaMin),
127  m_betaMax(sock.m_betaMax),
128  m_betaBase(sock.m_betaBase),
129  m_beta(sock.m_beta),
130  m_winThresh(sock.m_winThresh),
131  m_theta(sock.m_theta),
132  m_ackCnt(sock.m_ackCnt)
133 {
134  NS_LOG_FUNCTION(this);
135 }
136 
138 {
139  NS_LOG_FUNCTION(this);
140 }
141 
142 void
144 {
145  NS_LOG_FUNCTION(this << cWnd);
146 
147  if (cWnd < m_winThresh)
148  {
149  NS_LOG_INFO("cWnd < winThresh, set alpha & beta to base values");
150 
152  m_beta = m_betaBase;
153  }
154  else if (m_cntRtt > 0)
155  {
156  double dm = static_cast<double>(CalculateMaxDelay().GetMilliSeconds());
157  double da = static_cast<double>(CalculateAvgDelay().GetMilliSeconds());
158 
159  NS_LOG_INFO("Updated to dm = " << dm << " da = " << da);
160 
161  CalculateAlpha(da, dm);
162  CalculateBeta(da, dm);
163  }
164 }
165 
166 void
168  const TcpSocketState::TcpCongState_t newState)
169 {
170  NS_LOG_FUNCTION(this << tcb << newState);
171 
172  if (newState == TcpSocketState::CA_LOSS)
173  {
175  m_beta = m_betaBase;
176  m_rttLow = 0;
177  m_rttAbove = false;
178  Reset(tcb->m_nextTxSequence);
179  }
180 }
181 
182 void
184 {
185  NS_LOG_FUNCTION(this << segmentsAcked);
186 
187  if (tcb->m_lastAckedSeq >= m_endSeq)
188  {
189  RecalcParam(tcb->m_cWnd);
190  Reset(tcb->m_nextTxSequence);
191  }
192 
193  if (tcb->m_cWnd < tcb->m_ssThresh)
194  {
195  TcpNewReno::SlowStart(tcb, segmentsAcked);
196  NS_LOG_INFO("In SlowStart, updated to cwnd " << tcb->m_cWnd << " ssthresh "
197  << tcb->m_ssThresh);
198  }
199  else
200  {
201  uint32_t segCwnd = tcb->GetCwndInSegments();
202  uint32_t oldCwnd = segCwnd;
203 
204  if (segmentsAcked > 0)
205  {
206  m_ackCnt += segmentsAcked * m_alpha;
207  }
208 
209  while (m_ackCnt >= segCwnd)
210  {
211  m_ackCnt -= segCwnd;
212  segCwnd += 1;
213  }
214 
215  if (segCwnd != oldCwnd)
216  {
217  tcb->m_cWnd = segCwnd * tcb->m_segmentSize;
218  NS_LOG_INFO("In CongAvoid, updated to cwnd " << tcb->m_cWnd << " ssthresh "
219  << tcb->m_ssThresh);
220  }
221  }
222 }
223 
224 void
225 TcpIllinois::PktsAcked(Ptr<TcpSocketState> tcb, uint32_t packetsAcked, const Time& rtt)
226 {
227  NS_LOG_FUNCTION(this << tcb << packetsAcked << rtt);
228 
229  if (rtt.IsZero())
230  {
231  return;
232  }
233 
234  // Keep track of minimum RTT
235  m_baseRtt = std::min(m_baseRtt, rtt);
236 
237  // Keep track of maximum RTT
238  m_maxRtt = std::max(rtt, m_maxRtt);
239 
240  ++m_cntRtt;
241  m_sumRtt += rtt;
242 
243  NS_LOG_INFO("Updated baseRtt = " << m_baseRtt << " maxRtt = " << m_maxRtt
244  << " cntRtt = " << m_cntRtt << " sumRtt = " << m_sumRtt);
245 }
246 
247 uint32_t
249 {
250  NS_LOG_FUNCTION(this << tcb << bytesInFlight);
251 
252  uint32_t segBytesInFlight = bytesInFlight / tcb->m_segmentSize;
253  uint32_t ssThresh = static_cast<uint32_t>(std::max(2.0, (1.0 - m_beta) * segBytesInFlight));
254 
255  NS_LOG_DEBUG("Calculated ssThresh (in segments) = " << ssThresh);
256 
257  return ssThresh * tcb->m_segmentSize;
258 }
259 
260 void
261 TcpIllinois::CalculateAlpha(double da, double dm)
262 {
263  NS_LOG_FUNCTION(this << da << dm);
264 
265  double d1 = dm / 100;
266 
267  if (da <= d1)
268  {
269  NS_LOG_INFO("da <= d1");
270 
271  if (!m_rttAbove)
272  { // In case we can't get out of this low delay zone, we use alphaMax
274  }
275  if (++m_rttLow >= m_theta)
276  {
277  /*
278  * da needs to stay below d1 for theta times RTT amount of time
279  * before we can increase alpha to alphaMax
280  */
281  NS_LOG_INFO("da stays below d1 for theta times RTT amount of time, "
282  "increase alpha to alphaMax");
283 
284  m_rttLow = 0;
285  m_rttAbove = false;
287  }
288  }
289  else
290  {
291  NS_LOG_INFO("da > d1");
292 
293  m_rttAbove = true;
294  /*
295  * alpha = k1 / (k2 + da), where
296  * k1 = ((dm - d1) * alphaMin * alphaMax) / (alphaMax - alphaMin)
297  * k2 = (((dm - d1) * alphaMin) / (alphaMax - alphaMin)) - d1
298  */
299  dm -= d1;
300  da -= d1;
301  m_alpha = (dm * m_alphaMax) / (dm + (da * (m_alphaMax - m_alphaMin)) / m_alphaMin);
302  }
303 
304  NS_LOG_INFO("Updated to alpha = " << m_alpha);
305 }
306 
307 void
308 TcpIllinois::CalculateBeta(double da, double dm)
309 {
310  NS_LOG_FUNCTION(this << da << dm);
311 
312  double d2;
313  double d3;
314 
315  d2 = dm / 10;
316  d3 = (8 * dm) / 10;
317 
318  if (da <= d2)
319  {
320  NS_LOG_INFO("da <= d2");
321 
322  m_beta = m_betaMin;
323  }
324 
325  else if (da > d2 && da < d3)
326  {
327  NS_LOG_INFO("da > d2 && da < d3");
328 
329  /*
330  * beta = k3 + k4 * da, where
331  * k3 = (betaMin * d3 - betaMax * d2) / (d3 - d2)
332  * k4 = (betaMax - betaMin) / (d3 - d2)
333  */
334  m_beta = (m_betaMin * d3 - m_betaMax * d2 + (m_betaMax - m_betaMin) * da) / (d3 - d2);
335  }
336 
337  else if (da >= d3 || d3 <= d2)
338  {
339  NS_LOG_INFO("da >= d3 || d3 <= d2");
340 
341  m_beta = m_betaMax;
342  }
343 
344  NS_LOG_INFO("Updated to beta = " << m_beta);
345 }
346 
347 Time
349 {
350  NS_LOG_FUNCTION(this);
351 
352  return (m_sumRtt / m_cntRtt - m_baseRtt);
353 }
354 
355 Time
357 {
358  NS_LOG_FUNCTION(this);
359 
360  return (m_maxRtt - m_baseRtt);
361 }
362 
363 void
364 TcpIllinois::Reset(const SequenceNumber32& nextTxSequence)
365 {
366  NS_LOG_FUNCTION(this << nextTxSequence);
367 
368  m_endSeq = nextTxSequence;
369  m_cntRtt = 0;
370  m_sumRtt = Time(0);
371 }
372 
375 {
376  NS_LOG_FUNCTION(this);
377 
378  return CopyObject<TcpIllinois>(this);
379 }
380 
381 std::string
383 {
384  NS_LOG_FUNCTION(this);
385 
386  return "TcpIllinois";
387 }
388 
389 } // namespace ns3
#define min(a, b)
Definition: 80211b.c:41
#define max(a, b)
Definition: 80211b.c:42
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition: double.h:42
An implementation of TCP Illinois algorithm.
Definition: tcp-illinois.h:109
double m_alphaBase
Base value of alpha for standard AIMD.
Definition: tcp-illinois.h:237
double m_beta
Multiplicative decrease factor.
Definition: tcp-illinois.h:242
uint32_t m_ackCnt
Number of received ACK.
Definition: tcp-illinois.h:245
void RecalcParam(uint32_t cWnd)
Recalculate alpha and beta every RTT.
Time CalculateMaxDelay() const
Calculate maximum queueing delay.
uint32_t GetSsThresh(Ptr< const TcpSocketState > tcb, uint32_t bytesInFlight) override
Get slow start threshold after congestion event.
bool m_rttAbove
True when da > d1.
Definition: tcp-illinois.h:233
std::string GetName() const override
Get the name of the congestion control algorithm.
static TypeId GetTypeId()
Get the type ID.
Definition: tcp-illinois.cc:40
double m_betaMin
Minimum beta threshold.
Definition: tcp-illinois.h:239
void CalculateAlpha(double da, double dm)
Calculate additive increase factor alpha.
void CongestionStateSet(Ptr< TcpSocketState > tcb, const TcpSocketState::TcpCongState_t newState) override
Reset Illinois parameters to default values upon a loss.
Time m_baseRtt
Minimum of all RTT measurements.
Definition: tcp-illinois.h:230
double m_alphaMin
Minimum alpha threshold.
Definition: tcp-illinois.h:235
uint32_t m_winThresh
Window threshold for adaptive sizing.
Definition: tcp-illinois.h:243
uint32_t m_cntRtt
Number of RTT measurements during last RTT.
Definition: tcp-illinois.h:229
TcpIllinois()
Create an unbound tcp socket.
Definition: tcp-illinois.cc:89
void IncreaseWindow(Ptr< TcpSocketState > tcb, uint32_t segmentsAcked) override
Adjust cwnd following Illinois congestion avoidance algorithm.
uint8_t m_rttLow
Number of RTTs da has stayed below d1.
Definition: tcp-illinois.h:234
void CalculateBeta(double da, double dm)
Calculate multiplicative decrease factor beta.
Time m_maxRtt
Maximum of all RTT measurements.
Definition: tcp-illinois.h:231
double m_alpha
Additive increase factor.
Definition: tcp-illinois.h:238
double m_betaMax
Maximum beta threshold.
Definition: tcp-illinois.h:240
double m_betaBase
Base value of beta for standard AIMD.
Definition: tcp-illinois.h:241
uint32_t m_theta
Number of RTTs required before setting alpha to its max.
Definition: tcp-illinois.h:244
~TcpIllinois() override
Time m_sumRtt
Sum of all RTT measurements during last RTT.
Definition: tcp-illinois.h:228
double m_alphaMax
Maximum alpha threshold.
Definition: tcp-illinois.h:236
Ptr< TcpCongestionOps > Fork() override
Copy the congestion control algorithm across sockets.
void Reset(const SequenceNumber32 &nextTxSequence)
Reset Illinois parameters.
void PktsAcked(Ptr< TcpSocketState > tcb, uint32_t segmentsAcked, const Time &rtt) override
Measure RTT for each ACK Keep track of min and max RTT.
Time CalculateAvgDelay() const
Calculate average queueing delay.
SequenceNumber32 m_endSeq
Right edge of current RTT.
Definition: tcp-illinois.h:232
The NewReno implementation.
virtual uint32_t SlowStart(Ptr< TcpSocketState > tcb, uint32_t segmentsAcked)
Tcp NewReno slow start algorithm.
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< SequenceNumber32 > m_nextTxSequence
Next seqnum to be sent (SND.NXT), ReTx pushes it back.
TracedValue< uint32_t > m_ssThresh
Slow start threshold.
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:105
int64_t GetMilliSeconds() const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:408
bool IsZero() const
Exactly equivalent to t == 0.
Definition: nstime.h:315
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:931
Hold an unsigned integer type.
Definition: uinteger.h:45
int64x64_t Max(const int64x64_t &a, const int64x64_t &b)
Maximum.
Definition: int64x64.h:243
int64x64_t Min(const int64x64_t &a, const int64x64_t &b)
Minimum.
Definition: int64x64.h:229
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#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:275
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:839
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Definition: double.h:43
Ptr< const AttributeAccessor > MakeUintegerAccessor(T1 a1)
Definition: uinteger.h:46