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