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 "ns3/log.h"
31 
32 namespace ns3 {
33 
34 NS_LOG_COMPONENT_DEFINE ("TcpIllinois");
35 NS_OBJECT_ENSURE_REGISTERED (TcpIllinois);
36 
37 TypeId
39 {
40  static TypeId tid = TypeId ("ns3::TcpIllinois")
42  .AddConstructor<TcpIllinois> ()
43  .SetGroupName ("Internet")
44  .AddAttribute ("AlphaMin", "Minimum alpha threshold",
45  DoubleValue (0.3),
47  MakeDoubleChecker<double> ())
48  .AddAttribute ("AlphaMax", "Maximum alpha threshold",
49  DoubleValue (10.0),
51  MakeDoubleChecker<double> ())
52  .AddAttribute ("AlphaBase", "Alpha base threshold",
53  DoubleValue (1.0),
55  MakeDoubleChecker<double> ())
56  .AddAttribute ("BetaMin", "Minimum beta threshold",
57  DoubleValue (0.125),
59  MakeDoubleChecker<double> ())
60  .AddAttribute ("BetaMax", "Maximum beta threshold",
61  DoubleValue (0.5),
63  MakeDoubleChecker<double> ())
64  .AddAttribute ("BetaBase", "Beta base threshold",
65  DoubleValue (0.5),
67  MakeDoubleChecker<double> ())
68  .AddAttribute ("WinThresh", "Window threshold",
69  UintegerValue (15),
71  MakeUintegerChecker<uint32_t> ())
72  .AddAttribute ("Theta", "Theta threshold",
73  UintegerValue (5),
75  MakeUintegerChecker<uint32_t> ())
76  ;
77  return tid;
78 }
79 
81  : TcpNewReno (),
82  m_sumRtt (Time (0)),
83  m_cntRtt (0),
84  m_baseRtt (Time::Max ()),
85  m_maxRtt (Time::Min ()),
86  m_endSeq (0),
87  m_rttAbove (false),
88  m_rttLow (0),
89  m_alphaMin (0.3),
90  m_alphaMax (10.0),
91  m_alphaBase (1.0),
92  m_alpha (m_alphaMax),
93  m_betaMin (0.125),
94  m_betaMax (0.5),
95  m_betaBase (0.5),
96  m_beta (m_betaBase),
97  m_winThresh (15),
98  m_theta (5),
99  m_ackCnt (0)
100 {
101  NS_LOG_FUNCTION (this);
102 }
103 
105  : TcpNewReno (sock),
106  m_sumRtt (sock.m_sumRtt),
107  m_cntRtt (sock.m_cntRtt),
108  m_baseRtt (sock.m_baseRtt),
109  m_maxRtt (sock.m_maxRtt),
110  m_endSeq (sock.m_endSeq),
111  m_rttAbove (sock.m_rttAbove),
112  m_rttLow (sock.m_rttLow),
113  m_alphaMin (sock.m_alphaMin),
114  m_alphaMax (sock.m_alphaMax),
115  m_alphaBase (sock.m_alphaBase),
116  m_alpha (sock.m_alpha),
117  m_betaMin (sock.m_betaMin),
118  m_betaMax (sock.m_betaMax),
119  m_betaBase (sock.m_betaBase),
120  m_beta (sock.m_beta),
121  m_winThresh (sock.m_winThresh),
122  m_theta (sock.m_theta),
123  m_ackCnt (sock.m_ackCnt)
124 {
125  NS_LOG_FUNCTION (this);
126 }
127 
129 {
130  NS_LOG_FUNCTION (this);
131 }
132 
133 void
135 {
136  NS_LOG_FUNCTION (this << cWnd);
137 
138  if (cWnd < m_winThresh)
139  {
140  NS_LOG_INFO ("cWnd < winThresh, set alpha & beta to base values");
141 
143  m_beta = m_betaBase;
144  }
145  else if (m_cntRtt > 0)
146  {
147  double dm = static_cast<double> (CalculateMaxDelay ().GetMilliSeconds ());
148  double da = static_cast<double> (CalculateAvgDelay ().GetMilliSeconds ());
149 
150  NS_LOG_INFO ("Updated to dm = " << dm << " da = " << da);
151 
152  CalculateAlpha (da, dm);
153  CalculateBeta (da, dm);
154  }
155 }
156 
157 void
159  const TcpSocketState::TcpCongState_t newState)
160 {
161  NS_LOG_FUNCTION (this << tcb << newState);
162 
163  if (newState == TcpSocketState::CA_LOSS)
164  {
166  m_beta = m_betaBase;
167  m_rttLow = 0;
168  m_rttAbove = false;
169  Reset (tcb->m_nextTxSequence);
170  }
171 }
172 
173 void
175 {
176  NS_LOG_FUNCTION (this << segmentsAcked);
177 
178  if (tcb->m_lastAckedSeq >= m_endSeq)
179  {
180  RecalcParam (tcb->m_cWnd);
181  Reset (tcb->m_nextTxSequence);
182  }
183 
184  if (tcb->m_cWnd < tcb->m_ssThresh)
185  {
186  TcpNewReno::SlowStart (tcb, segmentsAcked);
187  NS_LOG_INFO ("In SlowStart, updated to cwnd " << tcb->m_cWnd <<
188  " ssthresh " << tcb->m_ssThresh);
189  }
190  else
191  {
192  uint32_t segCwnd = tcb->GetCwndInSegments ();
193  uint32_t oldCwnd = segCwnd;
194 
195  if (segmentsAcked > 0)
196  {
197  m_ackCnt += segmentsAcked * m_alpha;
198  }
199 
200  while (m_ackCnt >= segCwnd)
201  {
202  m_ackCnt -= segCwnd;
203  segCwnd += 1;
204  }
205 
206  if (segCwnd != oldCwnd)
207  {
208  tcb->m_cWnd = segCwnd * tcb->m_segmentSize;
209  NS_LOG_INFO ("In CongAvoid, updated to cwnd " << tcb->m_cWnd <<
210  " ssthresh " << tcb->m_ssThresh);
211  }
212  }
213 }
214 
215 void
216 TcpIllinois::PktsAcked (Ptr<TcpSocketState> tcb, uint32_t packetsAcked,
217  const Time &rtt)
218 {
219  NS_LOG_FUNCTION (this << tcb << packetsAcked << rtt);
220 
221  if (rtt.IsZero ())
222  {
223  return;
224  }
225 
226  // Keep track of minimum RTT
227  m_baseRtt = std::min (m_baseRtt, rtt);
228 
229  // Keep track of maximum RTT
230  m_maxRtt = std::max (rtt, m_maxRtt);
231 
232  ++m_cntRtt;
233  m_sumRtt += rtt;
234 
235  NS_LOG_INFO ("Updated baseRtt = " << m_baseRtt << " maxRtt = " << m_maxRtt <<
236  " cntRtt = " << m_cntRtt << " sumRtt = " << m_sumRtt);
237 }
238 
239 uint32_t
241 {
242  NS_LOG_FUNCTION (this << tcb << bytesInFlight);
243 
244  uint32_t segBytesInFlight = bytesInFlight / tcb->m_segmentSize;
245  uint32_t ssThresh = static_cast<uint32_t> (std::max (2.0, (1.0 - m_beta) * segBytesInFlight));
246 
247  NS_LOG_DEBUG ("Calculated ssThresh (in segments) = " << ssThresh);
248 
249  return ssThresh * tcb->m_segmentSize;
250 }
251 
252 void
253 TcpIllinois::CalculateAlpha (double da, double dm)
254 {
255  NS_LOG_FUNCTION (this << da << dm);
256 
257  double d1 = dm / 100;
258 
259  if (da <= d1)
260  {
261  NS_LOG_INFO ("da <= d1");
262 
263  if (!m_rttAbove)
264  { // In case we can't get out of this low delay zone, we use alphaMax
266  }
267  if (++m_rttLow >= m_theta)
268  {
269  /*
270  * da needs to stay below d1 for theta times RTT amount of time
271  * before we can increase alpha to alphaMax
272  */
273  NS_LOG_INFO ("da stays below d1 for theta times RTT amount of time, "
274  "increase alpha to alphaMax");
275 
276  m_rttLow = 0;
277  m_rttAbove = false;
279  }
280  }
281  else
282  {
283  NS_LOG_INFO ("da > d1");
284 
285  m_rttAbove = true;
286  /*
287  * alpha = k1 / (k2 + da), where
288  * k1 = ((dm - d1) * alphaMin * alphaMax) / (alphaMax - alphaMin)
289  * k2 = (((dm - d1) * alphaMin) / (alphaMax - alphaMin)) - d1
290  */
291  dm -= d1;
292  da -= d1;
293  m_alpha = (dm * m_alphaMax) / (dm + (da * (m_alphaMax - m_alphaMin)) / m_alphaMin);
294  }
295 
296  NS_LOG_INFO ("Updated to alpha = " << m_alpha);
297 }
298 
299 void
300 TcpIllinois::CalculateBeta (double da, double dm)
301 {
302  NS_LOG_FUNCTION (this << da << dm);
303 
304  double d2, d3;
305 
306  d2 = dm / 10;
307  d3 = (8 * dm) / 10;
308 
309  if (da <= d2)
310  {
311  NS_LOG_INFO ("da <= d2");
312 
313  m_beta = m_betaMin;
314  }
315 
316  else if (da > d2 && da < d3)
317  {
318  NS_LOG_INFO ("da > d2 && da < d3");
319 
320  /*
321  * beta = k3 + k4 * da, where
322  * k3 = (betaMin * d3 - betaMax * d2) / (d3 - d2)
323  * k4 = (betaMax - betaMin) / (d3 - d2)
324  */
325  m_beta = (m_betaMin * d3 - m_betaMax * d2 + (m_betaMax - m_betaMin) * da) / (d3 - d2);
326 
327  }
328 
329  else if (da >= d3 || d3 <= d2)
330  {
331  NS_LOG_INFO ("da >= d3 || d3 <= d2");
332 
333  m_beta = m_betaMax;
334  }
335 
336  NS_LOG_INFO ("Updated to beta = " << m_beta);
337 }
338 
339 Time
341 {
342  NS_LOG_FUNCTION (this);
343 
344  return (m_sumRtt / m_cntRtt - m_baseRtt);
345 }
346 
347 Time
349 {
350  NS_LOG_FUNCTION (this);
351 
352  return (m_maxRtt - m_baseRtt);
353 }
354 
355 void
356 TcpIllinois::Reset (const SequenceNumber32 &nextTxSequence)
357 {
358  NS_LOG_FUNCTION (this << nextTxSequence);
359 
360  m_endSeq = nextTxSequence;
361  m_cntRtt = 0;
362  m_sumRtt = Time (0);
363 }
364 
367 {
368  NS_LOG_FUNCTION (this);
369 
370  return CopyObject<TcpIllinois> (this);
371 }
372 
373 std::string
375 {
376  NS_LOG_FUNCTION (this);
377 
378  return "TcpIllinois";
379 }
380 
381 } // 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:231
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
double m_beta
Multiplicative decrease factor.
Definition: tcp-illinois.h:243
#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:241
#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:246
bool m_rttAbove
True when da > d1.
Definition: tcp-illinois.h:234
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:204
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:280
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:743
double m_alpha
Additive increase factor.
Definition: tcp-illinois.h:239
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:229
uint32_t m_theta
Number of RTTs required before setting alpha to its max.
Definition: tcp-illinois.h:245
int64x64_t Min(const int64x64_t &a, const int64x64_t &b)
Minimum.
Definition: int64x64.h:197
#define max(a, b)
Definition: 80211b.c:43
double m_alphaBase
Base value of alpha for standard AIMD.
Definition: tcp-illinois.h:238
bool IsZero(void) const
Definition: nstime.h:288
double m_alphaMin
Minimum alpha threshold.
Definition: tcp-illinois.h:236
Hold an unsigned integer type.
Definition: uinteger.h:44
double m_alphaMax
Maximum alpha threshold.
Definition: tcp-illinois.h:237
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:209
Time m_maxRtt
Maximum of all RTT measurements.
Definition: tcp-illinois.h:232
TcpIllinois(void)
Create an unbound tcp socket.
Definition: tcp-illinois.cc:80
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:230
SequenceNumber32 m_endSeq
Right edge of current RTT.
Definition: tcp-illinois.h:233
double m_betaMin
Minimum beta threshold.
Definition: tcp-illinois.h:240
double m_betaBase
Base value of beta for standard AIMD.
Definition: tcp-illinois.h:242
int64_t GetMilliSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:359
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:272
void RecalcParam(uint32_t cWnd)
Recalculate alpha and beta every RTT.
static TypeId GetTypeId(void)
Get the type ID.
Definition: tcp-illinois.cc:38
uint32_t m_winThresh
Window threshold for adaptive sizing.
Definition: tcp-illinois.h:244
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:107
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:915
uint8_t m_rttLow
Number of RTTs da has stayed below d1.
Definition: tcp-illinois.h:235
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.