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 #ifndef TCPILLINOIS_H 29 #define TCPILLINOIS_H 30 31 #include "tcp-congestion-ops.h" 32 33 namespace ns3 { 34 35 class TcpSocketState; 36 37 /** 38 * \ingroup congestionOps 39 * 40 * \brief An implementation of TCP Illinois algorithm 41 * 42 * TCP Illinois is a hybrid congestion control algorithm designed for 43 * high-speed networks. Illinois implements a Concave-AIMD (or C-AIMD) 44 * algorithm that uses packet loss as the primary congestion signal to 45 * determine the direction of window update and queueing delay as the 46 * secondary congestion signal to determine the amount of change. 47 * 48 * The additive increase and multiplicative decrease factors (denoted as 49 * alpha and beta, respectively) are functions of the current average queueing 50 * delay da as shown in Equations (1) and (2). To improve the protocol 51 * robustness against sudden fluctuations in its delay sampling, 52 * Illinois allows the increment of alpha to alphaMax 53 * only if da stays below d1 for a some (theta) amount of time. 54 * 55 * / alphaMax if da <= d1 56 * alpha = (1) 57 * \ k1 / (k2 + da) otherwise 58 * 59 * / betaMin if da <= d2 60 * beta = k3 + k4da if d2 < da < d3 (2) 61 * \ betaMax otherwise 62 * 63 * where the calculations of k1, k2, k3, and k4 are shown in Equations (3), (4), 64 * (5), and (6). 65 * 66 * k1 = (dm - d1)(alphaMin)alphaMax / (alphaMax - alphaMin) (3) 67 * 68 * k2 = ((dm - d1)alphaMin / (alphaMax - alphaMin)) - d1 (4) 69 * 70 * k3 = ((alphaMin)d3 - (alphaMax)d2) / (d3 - d2) (5) 71 * 72 * k4 = (alphaMax - alphaMin) / (d3 - d2) (6) 73 * 74 * with da the current average queueing delay calculated in Equation (7) where: 75 * Ta is the average RTT (sumRtt / cntRtt in the implementation) and 76 * Tmin (baseRtt in the implementation) is the minimum RTT ever seen 77 * dm the maximum (average) queueing delay calculated in Equation (8) where 78 * Tmax (maxRtt in the implementation) is the maximum RTT ever seen 79 * 80 * da = Ta - Tmin (7) 81 * 82 * dm = Tmax - Tmin (8) 83 * 84 * di (i = 1,2,3) are calculated in Equation (9) (0 <= eta_1 < 1, and 85 * 0 <= eta_2 <= eta_3 <=1) 86 * 87 * di = (eta_i)dm (9) 88 * 89 * Illinois only executes its adaptation of alpha and beta when cwnd exceeds a 90 * threshold called winThresh. Otherwise, it sets alpha and beta to the base 91 * values of 1 and 0.5, respectively. 92 * 93 * Following the implementation of Illinois in the Linux kernel, we use the following 94 * default parameter settings: 95 * 96 * alphaMin = 0.3 (0.1 in the Illinois paper) 97 * alphaMax = 10.0 98 * betaMin = 0.125 99 * betaMax = 0.5 100 * winThresh = 15 (10 in the Illinois paper) 101 * theta = 5 102 * eta1 = 0.01 103 * eta2 = 0.1 104 * eta3 = 0.8 105 * 106 * More information: http://www.doi.org/10.1145/1190095.1190166 107 */ 108 class TcpIllinois : public TcpNewReno 109 { 110 public: 111 /** 112 * \brief Get the type ID. 113 * \return the object TypeId 114 */ 115 static TypeId GetTypeId (void); 116 117 /** 118 * Create an unbound tcp socket. 119 */ 120 TcpIllinois (void); 121 122 /** 123 * \brief Copy constructor 124 * \param sock the object to copy 125 */ 126 TcpIllinois (const TcpIllinois& sock); 127 virtual ~TcpIllinois (void); 128 129 virtual std::string GetName () const; 130 131 /** 132 * \brief Get slow start threshold after congestion event 133 * 134 * \param tcb internal congestion state 135 * \param bytesInFlight bytes in flight 136 * 137 * \return the slow start threshold value 138 */ 139 virtual uint32_t GetSsThresh (Ptr<const TcpSocketState> tcb, 140 uint32_t bytesInFlight); 141 142 virtual Ptr<TcpCongestionOps> Fork (); 143 144 /** 145 * \brief Reset Illinois parameters to default values upon a loss 146 * 147 * \param tcb internal congestion state 148 * \param newState new congestion state to which the TCP is going to switch 149 */ 150 virtual void CongestionStateSet (Ptr<TcpSocketState> tcb, 151 const TcpSocketState::TcpCongState_t newState); 152 153 /** 154 * \brief Adjust cwnd following Illinois congestion avoidance algorithm 155 * 156 * \param tcb internal congestion state 157 * \param segmentsAcked count of segments ACKed 158 */ 159 virtual void IncreaseWindow (Ptr<TcpSocketState> tcb, uint32_t segmentsAcked); 160 161 /** 162 * \brief Measure RTT for each ACK 163 * Keep track of min and max RTT 164 * 165 * \param tcb internal congestion state 166 * \param segmentsAcked count of segments ACKed 167 * \param rtt last RTT 168 */ 169 virtual void PktsAcked (Ptr<TcpSocketState> tcb, uint32_t segmentsAcked, 170 const Time& rtt); 171 172 protected: 173 private: 174 /** 175 * \brief Recalculate alpha and beta every RTT 176 * 177 * \param cWnd current Cwnd (in bytes) 178 */ 179 void RecalcParam (uint32_t cWnd); 180 181 /** 182 * \brief Calculate additive increase factor alpha 183 * 184 * If average queueing delay is at minimum, then alpha is set to alphaMax. 185 * Otherwise, alpha is a decreasing function of average queueing delay. 186 * 187 * \param da current average queueing delay 188 * \param dm maximum average queueing delay 189 * 190 */ 191 void CalculateAlpha (double da, double dm); 192 193 /** 194 * \brief Calculate multiplicative decrease factor beta 195 * 196 * If the current average queueing delay is <= 10% of max. (average) queueing delay, 197 * beta is set to betaMin, which equals to 1/8 by default. 198 * If the current average queueing delay is >= 80% of max. (average) queueing delay, 199 * beta is set to betaMax, which equals to 1/2 by default. 200 * Otherwise, beta is an increasing function of average queueing delay. 201 * 202 * \param da current average queueing delay 203 * \param dm maximum average queueing delay 204 * 205 */ 206 void CalculateBeta (double da, double dm); 207 208 /** 209 * \brief Calculate average queueing delay 210 * 211 * \return average queueing delay da 212 */ 213 Time CalculateAvgDelay () const; 214 215 /** 216 * \brief Calculate maximum queueing delay 217 * 218 * \return maximum average queueing delay dm 219 */ 220 Time CalculateMaxDelay () const; 221 222 /** 223 * \brief Reset Illinois parameters 224 * 225 * \param nextTxSequence Next sequence to transmit 226 */ 227 void Reset (const SequenceNumber32 &nextTxSequence); 228 229 private: 230 Time m_sumRtt; //!< Sum of all RTT measurements during last RTT 231 uint32_t m_cntRtt; //!< Number of RTT measurements during last RTT 232 Time m_baseRtt; //!< Minimum of all RTT measurements 233 Time m_maxRtt; //!< Maximum of all RTT measurements 234 SequenceNumber32 m_endSeq; //!< Right edge of current RTT 235 bool m_rttAbove; //!< True when da > d1 236 uint8_t m_rttLow; //!< Number of RTTs da has stayed below d1 237 double m_alphaMin; //!< Minimum alpha threshold 238 double m_alphaMax; //!< Maximum alpha threshold 239 double m_alphaBase; //!< Base value of alpha for standard AIMD 240 double m_alpha; //!< Additive increase factor 241 double m_betaMin; //!< Minimum beta threshold 242 double m_betaMax; //!< Maximum beta threshold 243 double m_betaBase; //!< Base value of beta for standard AIMD 244 double m_beta; //!< Multiplicative decrease factor 245 uint32_t m_winThresh; //!< Window threshold for adaptive sizing 246 uint32_t m_theta; //!< Number of RTTs required before setting alpha to its max 247 uint32_t m_ackCnt; //!< Number of received ACK 248 249 }; 250 251 } // namespace ns3 252 253 #endif // TCPILLINOIS_H 254