xref: /openbmc/linux/net/ipv4/tcp_htcp.c (revision d5cb9783536a41df9f9cba5b0a1d78047ed787f7)
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 	u8	ccount;		/* Number of RTTs since last congestion event */
31 	u8	undo_ccount;
32 	u16	packetcount;
33 	u32	minRTT;
34 	u32	maxRTT;
35 	u32	snd_cwnd_cnt2;
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 void htcp_reset(struct htcp *ca)
49 {
50 	ca->undo_ccount = ca->ccount;
51 	ca->undo_maxRTT = ca->maxRTT;
52 	ca->undo_old_maxB = ca->old_maxB;
53 
54 	ca->ccount = 0;
55 	ca->snd_cwnd_cnt2 = 0;
56 }
57 
58 static u32 htcp_cwnd_undo(struct sock *sk)
59 {
60 	const struct tcp_sock *tp = tcp_sk(sk);
61 	struct htcp *ca = inet_csk_ca(sk);
62 	ca->ccount = ca->undo_ccount;
63 	ca->maxRTT = ca->undo_maxRTT;
64 	ca->old_maxB = ca->undo_old_maxB;
65 	return max(tp->snd_cwnd, (tp->snd_ssthresh<<7)/ca->beta);
66 }
67 
68 static inline void measure_rtt(struct sock *sk)
69 {
70 	const struct inet_connection_sock *icsk = inet_csk(sk);
71 	const struct tcp_sock *tp = tcp_sk(sk);
72 	struct htcp *ca = inet_csk_ca(sk);
73 	u32 srtt = tp->srtt>>3;
74 
75 	/* keep track of minimum RTT seen so far, minRTT is zero at first */
76 	if (ca->minRTT > srtt || !ca->minRTT)
77 		ca->minRTT = srtt;
78 
79 	/* max RTT */
80 	if (icsk->icsk_ca_state == TCP_CA_Open && tp->snd_ssthresh < 0xFFFF && ca->ccount > 3) {
81 		if (ca->maxRTT < ca->minRTT)
82 			ca->maxRTT = ca->minRTT;
83 		if (ca->maxRTT < srtt && srtt <= ca->maxRTT+HZ/50)
84 			ca->maxRTT = srtt;
85 	}
86 }
87 
88 static void measure_achieved_throughput(struct sock *sk, u32 pkts_acked)
89 {
90 	const struct inet_connection_sock *icsk = inet_csk(sk);
91 	const struct tcp_sock *tp = tcp_sk(sk);
92 	struct htcp *ca = inet_csk_ca(sk);
93 	u32 now = tcp_time_stamp;
94 
95 	/* achieved throughput calculations */
96 	if (icsk->icsk_ca_state != TCP_CA_Open &&
97 	    icsk->icsk_ca_state != TCP_CA_Disorder) {
98 		ca->packetcount = 0;
99 		ca->lasttime = now;
100 		return;
101 	}
102 
103 	ca->packetcount += pkts_acked;
104 
105 	if (ca->packetcount >= tp->snd_cwnd - (ca->alpha>>7? : 1)
106 			&& now - ca->lasttime >= ca->minRTT
107 			&& ca->minRTT > 0) {
108 		__u32 cur_Bi = ca->packetcount*HZ/(now - ca->lasttime);
109 		if (ca->ccount <= 3) {
110 			/* just after backoff */
111 			ca->minB = ca->maxB = ca->Bi = cur_Bi;
112 		} else {
113 			ca->Bi = (3*ca->Bi + cur_Bi)/4;
114 			if (ca->Bi > ca->maxB)
115 				ca->maxB = ca->Bi;
116 			if (ca->minB > ca->maxB)
117 				ca->minB = ca->maxB;
118 		}
119 		ca->packetcount = 0;
120 		ca->lasttime = now;
121 	}
122 }
123 
124 static inline void htcp_beta_update(struct htcp *ca, u32 minRTT, u32 maxRTT)
125 {
126 	if (use_bandwidth_switch) {
127 		u32 maxB = ca->maxB;
128 		u32 old_maxB = ca->old_maxB;
129 		ca->old_maxB = ca->maxB;
130 
131 		if (!between(5*maxB, 4*old_maxB, 6*old_maxB)) {
132 			ca->beta = BETA_MIN;
133 			ca->modeswitch = 0;
134 			return;
135 		}
136 	}
137 
138 	if (ca->modeswitch && minRTT > max(HZ/100, 1) && maxRTT) {
139 		ca->beta = (minRTT<<7)/maxRTT;
140 		if (ca->beta < BETA_MIN)
141 			ca->beta = BETA_MIN;
142 		else if (ca->beta > BETA_MAX)
143 			ca->beta = BETA_MAX;
144 	} else {
145 		ca->beta = BETA_MIN;
146 		ca->modeswitch = 1;
147 	}
148 }
149 
150 static inline void htcp_alpha_update(struct htcp *ca)
151 {
152 	u32 minRTT = ca->minRTT;
153 	u32 factor = 1;
154 	u32 diff = ca->ccount * minRTT; /* time since last backoff */
155 
156 	if (diff > HZ) {
157 		diff -= HZ;
158 		factor = 1+ ( 10*diff + ((diff/2)*(diff/2)/HZ) )/HZ;
159 	}
160 
161 	if (use_rtt_scaling && minRTT) {
162 		u32 scale = (HZ<<3)/(10*minRTT);
163 		scale = min(max(scale, 1U<<2), 10U<<3); /* clamping ratio to interval [0.5,10]<<3 */
164 		factor = (factor<<3)/scale;
165 		if (!factor)
166 			factor = 1;
167 	}
168 
169 	ca->alpha = 2*factor*((1<<7)-ca->beta);
170 	if (!ca->alpha)
171 		ca->alpha = ALPHA_BASE;
172 }
173 
174 /* After we have the rtt data to calculate beta, we'd still prefer to wait one
175  * rtt before we adjust our beta to ensure we are working from a consistent
176  * data.
177  *
178  * This function should be called when we hit a congestion event since only at
179  * that point do we really have a real sense of maxRTT (the queues en route
180  * were getting just too full now).
181  */
182 static void htcp_param_update(struct sock *sk)
183 {
184 	struct htcp *ca = inet_csk_ca(sk);
185 	u32 minRTT = ca->minRTT;
186 	u32 maxRTT = ca->maxRTT;
187 
188 	htcp_beta_update(ca, minRTT, maxRTT);
189 	htcp_alpha_update(ca);
190 
191 	/* add slowly fading memory for maxRTT to accommodate routing changes etc */
192 	if (minRTT > 0 && maxRTT > minRTT)
193 		ca->maxRTT = minRTT + ((maxRTT-minRTT)*95)/100;
194 }
195 
196 static u32 htcp_recalc_ssthresh(struct sock *sk)
197 {
198 	const struct tcp_sock *tp = tcp_sk(sk);
199 	const struct htcp *ca = inet_csk_ca(sk);
200 	htcp_param_update(sk);
201 	return max((tp->snd_cwnd * ca->beta) >> 7, 2U);
202 }
203 
204 static void htcp_cong_avoid(struct sock *sk, u32 ack, u32 rtt,
205 			    u32 in_flight, int data_acked)
206 {
207 	struct tcp_sock *tp = tcp_sk(sk);
208 	struct htcp *ca = inet_csk_ca(sk);
209 
210 	if (in_flight < tp->snd_cwnd)
211 		return;
212 
213         if (tp->snd_cwnd <= tp->snd_ssthresh) {
214                 /* In "safe" area, increase. */
215 		if (tp->snd_cwnd < tp->snd_cwnd_clamp)
216 			tp->snd_cwnd++;
217 	} else {
218 		measure_rtt(sk);
219 
220 		/* keep track of number of round-trip times since last backoff event */
221 		if (ca->snd_cwnd_cnt2++ > tp->snd_cwnd) {
222 			ca->ccount++;
223 			ca->snd_cwnd_cnt2 = 0;
224 			htcp_alpha_update(ca);
225 		}
226 
227                 /* In dangerous area, increase slowly.
228 		 * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd
229 		 */
230 		if ((tp->snd_cwnd_cnt++ * ca->alpha)>>7 >= tp->snd_cwnd) {
231 			if (tp->snd_cwnd < tp->snd_cwnd_clamp)
232 				tp->snd_cwnd++;
233 			tp->snd_cwnd_cnt = 0;
234 			ca->ccount++;
235 		}
236 	}
237 }
238 
239 /* Lower bound on congestion window. */
240 static u32 htcp_min_cwnd(struct sock *sk)
241 {
242 	const struct tcp_sock *tp = tcp_sk(sk);
243 	return tp->snd_ssthresh;
244 }
245 
246 
247 static void htcp_init(struct sock *sk)
248 {
249 	struct htcp *ca = inet_csk_ca(sk);
250 
251 	memset(ca, 0, sizeof(struct htcp));
252 	ca->alpha = ALPHA_BASE;
253 	ca->beta = BETA_MIN;
254 }
255 
256 static void htcp_state(struct sock *sk, u8 new_state)
257 {
258 	switch (new_state) {
259 	case TCP_CA_CWR:
260 	case TCP_CA_Recovery:
261 	case TCP_CA_Loss:
262 		htcp_reset(inet_csk_ca(sk));
263 		break;
264 	}
265 }
266 
267 static struct tcp_congestion_ops htcp = {
268 	.init		= htcp_init,
269 	.ssthresh	= htcp_recalc_ssthresh,
270 	.min_cwnd	= htcp_min_cwnd,
271 	.cong_avoid	= htcp_cong_avoid,
272 	.set_state	= htcp_state,
273 	.undo_cwnd	= htcp_cwnd_undo,
274 	.pkts_acked	= measure_achieved_throughput,
275 	.owner		= THIS_MODULE,
276 	.name		= "htcp",
277 };
278 
279 static int __init htcp_register(void)
280 {
281 	BUG_ON(sizeof(struct htcp) > ICSK_CA_PRIV_SIZE);
282 	BUILD_BUG_ON(BETA_MIN >= BETA_MAX);
283 	if (!use_bandwidth_switch)
284 		htcp.pkts_acked = NULL;
285 	return tcp_register_congestion_control(&htcp);
286 }
287 
288 static void __exit htcp_unregister(void)
289 {
290 	tcp_unregister_congestion_control(&htcp);
291 }
292 
293 module_init(htcp_register);
294 module_exit(htcp_unregister);
295 
296 MODULE_AUTHOR("Baruch Even");
297 MODULE_LICENSE("GPL");
298 MODULE_DESCRIPTION("H-TCP");
299