1 /* 2 * H-TCP congestion control. The algorithm is detailed in: 3 * R.N.Shorten, D.J.Leith: 4 * "H-TCP: TCP for high-speed and long-distance networks" 5 * Proc. PFLDnet, Argonne, 2004. 6 * http://www.hamilton.ie/net/htcp3.pdf 7 */ 8 9 #include <linux/config.h> 10 #include <linux/mm.h> 11 #include <linux/module.h> 12 #include <net/tcp.h> 13 14 #define ALPHA_BASE (1<<7) /* 1.0 with shift << 7 */ 15 #define BETA_MIN (1<<6) /* 0.5 with shift << 7 */ 16 #define BETA_MAX 102 /* 0.8 with shift << 7 */ 17 18 static int use_rtt_scaling = 1; 19 module_param(use_rtt_scaling, int, 0644); 20 MODULE_PARM_DESC(use_rtt_scaling, "turn on/off RTT scaling"); 21 22 static int use_bandwidth_switch = 1; 23 module_param(use_bandwidth_switch, int, 0644); 24 MODULE_PARM_DESC(use_bandwidth_switch, "turn on/off bandwidth switcher"); 25 26 struct htcp { 27 u16 alpha; /* Fixed point arith, << 7 */ 28 u8 beta; /* Fixed point arith, << 7 */ 29 u8 modeswitch; /* Delay modeswitch until we had at least one congestion event */ 30 u32 last_cong; /* Time since last congestion event end */ 31 u32 undo_last_cong; 32 u16 pkts_acked; 33 u32 packetcount; 34 u32 minRTT; 35 u32 maxRTT; 36 37 u32 undo_maxRTT; 38 u32 undo_old_maxB; 39 40 /* Bandwidth estimation */ 41 u32 minB; 42 u32 maxB; 43 u32 old_maxB; 44 u32 Bi; 45 u32 lasttime; 46 }; 47 48 static inline u32 htcp_cong_time(struct htcp *ca) 49 { 50 return jiffies - ca->last_cong; 51 } 52 53 static inline u32 htcp_ccount(struct htcp *ca) 54 { 55 return htcp_cong_time(ca)/ca->minRTT; 56 } 57 58 static inline void htcp_reset(struct htcp *ca) 59 { 60 ca->undo_last_cong = ca->last_cong; 61 ca->undo_maxRTT = ca->maxRTT; 62 ca->undo_old_maxB = ca->old_maxB; 63 64 ca->last_cong = jiffies; 65 } 66 67 static u32 htcp_cwnd_undo(struct sock *sk) 68 { 69 const struct tcp_sock *tp = tcp_sk(sk); 70 struct htcp *ca = inet_csk_ca(sk); 71 ca->last_cong = ca->undo_last_cong; 72 ca->maxRTT = ca->undo_maxRTT; 73 ca->old_maxB = ca->undo_old_maxB; 74 return max(tp->snd_cwnd, (tp->snd_ssthresh<<7)/ca->beta); 75 } 76 77 static inline void measure_rtt(struct sock *sk) 78 { 79 const struct inet_connection_sock *icsk = inet_csk(sk); 80 const struct tcp_sock *tp = tcp_sk(sk); 81 struct htcp *ca = inet_csk_ca(sk); 82 u32 srtt = tp->srtt>>3; 83 84 /* keep track of minimum RTT seen so far, minRTT is zero at first */ 85 if (ca->minRTT > srtt || !ca->minRTT) 86 ca->minRTT = srtt; 87 88 /* max RTT */ 89 if (icsk->icsk_ca_state == TCP_CA_Open && tp->snd_ssthresh < 0xFFFF && htcp_ccount(ca) > 3) { 90 if (ca->maxRTT < ca->minRTT) 91 ca->maxRTT = ca->minRTT; 92 if (ca->maxRTT < srtt && srtt <= ca->maxRTT+msecs_to_jiffies(20)) 93 ca->maxRTT = srtt; 94 } 95 } 96 97 static void measure_achieved_throughput(struct sock *sk, u32 pkts_acked) 98 { 99 const struct inet_connection_sock *icsk = inet_csk(sk); 100 const struct tcp_sock *tp = tcp_sk(sk); 101 struct htcp *ca = inet_csk_ca(sk); 102 u32 now = tcp_time_stamp; 103 104 if (icsk->icsk_ca_state == TCP_CA_Open) 105 ca->pkts_acked = pkts_acked; 106 107 if (!use_bandwidth_switch) 108 return; 109 110 /* achieved throughput calculations */ 111 if (icsk->icsk_ca_state != TCP_CA_Open && 112 icsk->icsk_ca_state != TCP_CA_Disorder) { 113 ca->packetcount = 0; 114 ca->lasttime = now; 115 return; 116 } 117 118 ca->packetcount += pkts_acked; 119 120 if (ca->packetcount >= tp->snd_cwnd - (ca->alpha>>7? : 1) 121 && now - ca->lasttime >= ca->minRTT 122 && ca->minRTT > 0) { 123 __u32 cur_Bi = ca->packetcount*HZ/(now - ca->lasttime); 124 if (htcp_ccount(ca) <= 3) { 125 /* just after backoff */ 126 ca->minB = ca->maxB = ca->Bi = cur_Bi; 127 } else { 128 ca->Bi = (3*ca->Bi + cur_Bi)/4; 129 if (ca->Bi > ca->maxB) 130 ca->maxB = ca->Bi; 131 if (ca->minB > ca->maxB) 132 ca->minB = ca->maxB; 133 } 134 ca->packetcount = 0; 135 ca->lasttime = now; 136 } 137 } 138 139 static inline void htcp_beta_update(struct htcp *ca, u32 minRTT, u32 maxRTT) 140 { 141 if (use_bandwidth_switch) { 142 u32 maxB = ca->maxB; 143 u32 old_maxB = ca->old_maxB; 144 ca->old_maxB = ca->maxB; 145 146 if (!between(5*maxB, 4*old_maxB, 6*old_maxB)) { 147 ca->beta = BETA_MIN; 148 ca->modeswitch = 0; 149 return; 150 } 151 } 152 153 if (ca->modeswitch && minRTT > msecs_to_jiffies(10) && maxRTT) { 154 ca->beta = (minRTT<<7)/maxRTT; 155 if (ca->beta < BETA_MIN) 156 ca->beta = BETA_MIN; 157 else if (ca->beta > BETA_MAX) 158 ca->beta = BETA_MAX; 159 } else { 160 ca->beta = BETA_MIN; 161 ca->modeswitch = 1; 162 } 163 } 164 165 static inline void htcp_alpha_update(struct htcp *ca) 166 { 167 u32 minRTT = ca->minRTT; 168 u32 factor = 1; 169 u32 diff = htcp_cong_time(ca); 170 171 if (diff > HZ) { 172 diff -= HZ; 173 factor = 1+ ( 10*diff + ((diff/2)*(diff/2)/HZ) )/HZ; 174 } 175 176 if (use_rtt_scaling && minRTT) { 177 u32 scale = (HZ<<3)/(10*minRTT); 178 scale = min(max(scale, 1U<<2), 10U<<3); /* clamping ratio to interval [0.5,10]<<3 */ 179 factor = (factor<<3)/scale; 180 if (!factor) 181 factor = 1; 182 } 183 184 ca->alpha = 2*factor*((1<<7)-ca->beta); 185 if (!ca->alpha) 186 ca->alpha = ALPHA_BASE; 187 } 188 189 /* After we have the rtt data to calculate beta, we'd still prefer to wait one 190 * rtt before we adjust our beta to ensure we are working from a consistent 191 * data. 192 * 193 * This function should be called when we hit a congestion event since only at 194 * that point do we really have a real sense of maxRTT (the queues en route 195 * were getting just too full now). 196 */ 197 static void htcp_param_update(struct sock *sk) 198 { 199 struct htcp *ca = inet_csk_ca(sk); 200 u32 minRTT = ca->minRTT; 201 u32 maxRTT = ca->maxRTT; 202 203 htcp_beta_update(ca, minRTT, maxRTT); 204 htcp_alpha_update(ca); 205 206 /* add slowly fading memory for maxRTT to accommodate routing changes etc */ 207 if (minRTT > 0 && maxRTT > minRTT) 208 ca->maxRTT = minRTT + ((maxRTT-minRTT)*95)/100; 209 } 210 211 static u32 htcp_recalc_ssthresh(struct sock *sk) 212 { 213 const struct tcp_sock *tp = tcp_sk(sk); 214 const struct htcp *ca = inet_csk_ca(sk); 215 htcp_param_update(sk); 216 return max((tp->snd_cwnd * ca->beta) >> 7, 2U); 217 } 218 219 static void htcp_cong_avoid(struct sock *sk, u32 ack, u32 rtt, 220 u32 in_flight, int data_acked) 221 { 222 struct tcp_sock *tp = tcp_sk(sk); 223 struct htcp *ca = inet_csk_ca(sk); 224 225 if (!tcp_is_cwnd_limited(sk, in_flight)) 226 return; 227 228 if (tp->snd_cwnd <= tp->snd_ssthresh) 229 tcp_slow_start(tp); 230 else { 231 232 measure_rtt(sk); 233 234 /* In dangerous area, increase slowly. 235 * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd 236 */ 237 if ((tp->snd_cwnd_cnt * ca->alpha)>>7 >= tp->snd_cwnd) { 238 if (tp->snd_cwnd < tp->snd_cwnd_clamp) 239 tp->snd_cwnd++; 240 tp->snd_cwnd_cnt = 0; 241 htcp_alpha_update(ca); 242 } else 243 tp->snd_cwnd_cnt += ca->pkts_acked; 244 245 ca->pkts_acked = 1; 246 } 247 } 248 249 static void htcp_init(struct sock *sk) 250 { 251 struct htcp *ca = inet_csk_ca(sk); 252 253 memset(ca, 0, sizeof(struct htcp)); 254 ca->alpha = ALPHA_BASE; 255 ca->beta = BETA_MIN; 256 ca->pkts_acked = 1; 257 ca->last_cong = jiffies; 258 } 259 260 static void htcp_state(struct sock *sk, u8 new_state) 261 { 262 switch (new_state) { 263 case TCP_CA_Open: 264 { 265 struct htcp *ca = inet_csk_ca(sk); 266 ca->last_cong = jiffies; 267 } 268 break; 269 case TCP_CA_CWR: 270 case TCP_CA_Recovery: 271 case TCP_CA_Loss: 272 htcp_reset(inet_csk_ca(sk)); 273 break; 274 } 275 } 276 277 static struct tcp_congestion_ops htcp = { 278 .init = htcp_init, 279 .ssthresh = htcp_recalc_ssthresh, 280 .cong_avoid = htcp_cong_avoid, 281 .set_state = htcp_state, 282 .undo_cwnd = htcp_cwnd_undo, 283 .pkts_acked = measure_achieved_throughput, 284 .owner = THIS_MODULE, 285 .name = "htcp", 286 }; 287 288 static int __init htcp_register(void) 289 { 290 BUG_ON(sizeof(struct htcp) > ICSK_CA_PRIV_SIZE); 291 BUILD_BUG_ON(BETA_MIN >= BETA_MAX); 292 return tcp_register_congestion_control(&htcp); 293 } 294 295 static void __exit htcp_unregister(void) 296 { 297 tcp_unregister_congestion_control(&htcp); 298 } 299 300 module_init(htcp_register); 301 module_exit(htcp_unregister); 302 303 MODULE_AUTHOR("Baruch Even"); 304 MODULE_LICENSE("GPL"); 305 MODULE_DESCRIPTION("H-TCP"); 306