[linux.git] / net / ipv4 / tcp_highspeed.c

/*
 * Sally Floyd's High Speed TCP (RFC 3649) congestion control
 *
 * See http://www.icir.org/floyd/hstcp.html
 *
 * John Heffner <[email protected]>
 */

#include <linux/module.h>
#include <net/tcp.h>


/* From AIMD tables from RFC 3649 appendix B,
 * with fixed-point MD scaled <<8.
 */
static const struct hstcp_aimd_val {
	unsigned int cwnd;
	unsigned int md;
} hstcp_aimd_vals[] = {
 {     38,  128, /*  0.50 */ },
 {    118,  112, /*  0.44 */ },
 {    221,  104, /*  0.41 */ },
 {    347,   98, /*  0.38 */ },
 {    495,   93, /*  0.37 */ },
 {    663,   89, /*  0.35 */ },
 {    851,   86, /*  0.34 */ },
 {   1058,   83, /*  0.33 */ },
 {   1284,   81, /*  0.32 */ },
 {   1529,   78, /*  0.31 */ },
 {   1793,   76, /*  0.30 */ },
 {   2076,   74, /*  0.29 */ },
 {   2378,   72, /*  0.28 */ },
 {   2699,   71, /*  0.28 */ },
 {   3039,   69, /*  0.27 */ },
 {   3399,   68, /*  0.27 */ },
 {   3778,   66, /*  0.26 */ },
 {   4177,   65, /*  0.26 */ },
 {   4596,   64, /*  0.25 */ },
 {   5036,   62, /*  0.25 */ },
 {   5497,   61, /*  0.24 */ },
 {   5979,   60, /*  0.24 */ },
 {   6483,   59, /*  0.23 */ },
 {   7009,   58, /*  0.23 */ },
 {   7558,   57, /*  0.22 */ },
 {   8130,   56, /*  0.22 */ },
 {   8726,   55, /*  0.22 */ },
 {   9346,   54, /*  0.21 */ },
 {   9991,   53, /*  0.21 */ },
 {  10661,   52, /*  0.21 */ },
 {  11358,   52, /*  0.20 */ },
 {  12082,   51, /*  0.20 */ },
 {  12834,   50, /*  0.20 */ },
 {  13614,   49, /*  0.19 */ },
 {  14424,   48, /*  0.19 */ },
 {  15265,   48, /*  0.19 */ },
 {  16137,   47, /*  0.19 */ },
 {  17042,   46, /*  0.18 */ },
 {  17981,   45, /*  0.18 */ },
 {  18955,   45, /*  0.18 */ },
 {  19965,   44, /*  0.17 */ },
 {  21013,   43, /*  0.17 */ },
 {  22101,   43, /*  0.17 */ },
 {  23230,   42, /*  0.17 */ },
 {  24402,   41, /*  0.16 */ },
 {  25618,   41, /*  0.16 */ },
 {  26881,   40, /*  0.16 */ },
 {  28193,   39, /*  0.16 */ },
 {  29557,   39, /*  0.15 */ },
 {  30975,   38, /*  0.15 */ },
 {  32450,   38, /*  0.15 */ },
 {  33986,   37, /*  0.15 */ },
 {  35586,   36, /*  0.14 */ },
 {  37253,   36, /*  0.14 */ },
 {  38992,   35, /*  0.14 */ },
 {  40808,   35, /*  0.14 */ },
 {  42707,   34, /*  0.13 */ },
 {  44694,   33, /*  0.13 */ },
 {  46776,   33, /*  0.13 */ },
 {  48961,   32, /*  0.13 */ },
 {  51258,   32, /*  0.13 */ },
 {  53677,   31, /*  0.12 */ },
 {  56230,   30, /*  0.12 */ },
 {  58932,   30, /*  0.12 */ },
 {  61799,   29, /*  0.12 */ },
 {  64851,   28, /*  0.11 */ },
 {  68113,   28, /*  0.11 */ },
 {  71617,   27, /*  0.11 */ },
 {  75401,   26, /*  0.10 */ },
 {  79517,   26, /*  0.10 */ },
 {  84035,   25, /*  0.10 */ },
 {  89053,   24, /*  0.10 */ },
};

#define HSTCP_AIMD_MAX	ARRAY_SIZE(hstcp_aimd_vals)

struct hstcp {
	u32	ai;
};

static void hstcp_init(struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct hstcp *ca = inet_csk_ca(sk);

	ca->ai = 0;

	/* Ensure the MD arithmetic works.  This is somewhat pedantic,
	 * since I don't think we will see a cwnd this large. :) */
	tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128);
}

static void hstcp_cong_avoid(struct sock *sk, u32 adk, u32 in_flight)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct hstcp *ca = inet_csk_ca(sk);

	if (!tcp_is_cwnd_limited(sk, in_flight))
		return;

	if (tp->snd_cwnd <= tp->snd_ssthresh)
		tcp_slow_start(tp);
	else {
		/* Update AIMD parameters.
		 *
		 * We want to guarantee that:
		 *     hstcp_aimd_vals[ca->ai-1].cwnd <
		 *     snd_cwnd <=
		 *     hstcp_aimd_vals[ca->ai].cwnd
		 */
		if (tp->snd_cwnd > hstcp_aimd_vals[ca->ai].cwnd) {
			while (tp->snd_cwnd > hstcp_aimd_vals[ca->ai].cwnd &&
			       ca->ai < HSTCP_AIMD_MAX - 1)
				ca->ai++;
		} else if (ca->ai && tp->snd_cwnd <= hstcp_aimd_vals[ca->ai-1].cwnd) {
			while (ca->ai && tp->snd_cwnd <= hstcp_aimd_vals[ca->ai-1].cwnd)
				ca->ai--;
		}

		/* Do additive increase */
		if (tp->snd_cwnd < tp->snd_cwnd_clamp) {
			/* cwnd = cwnd + a(w) / cwnd */
			tp->snd_cwnd_cnt += ca->ai + 1;
			if (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
				tp->snd_cwnd_cnt -= tp->snd_cwnd;
				tp->snd_cwnd++;
			}
		}
	}
}

static u32 hstcp_ssthresh(struct sock *sk)
{
	const struct tcp_sock *tp = tcp_sk(sk);
	const struct hstcp *ca = inet_csk_ca(sk);

	/* Do multiplicative decrease */
	return max(tp->snd_cwnd - ((tp->snd_cwnd * hstcp_aimd_vals[ca->ai].md) >> 8), 2U);
}


static struct tcp_congestion_ops tcp_highspeed = {
	.init		= hstcp_init,
	.ssthresh	= hstcp_ssthresh,
	.cong_avoid	= hstcp_cong_avoid,
	.min_cwnd	= tcp_reno_min_cwnd,

	.owner		= THIS_MODULE,
	.name		= "highspeed"
};

static int __init hstcp_register(void)
{
	BUILD_BUG_ON(sizeof(struct hstcp) > ICSK_CA_PRIV_SIZE);
	return tcp_register_congestion_control(&tcp_highspeed);
}

static void __exit hstcp_unregister(void)
{
	tcp_unregister_congestion_control(&tcp_highspeed);
}

module_init(hstcp_register);
module_exit(hstcp_unregister);

MODULE_AUTHOR("John Heffner");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("High Speed TCP");
Commit	Line	Data
a628d29b JH	1	/*
	2	* Sally Floyd's High Speed TCP (RFC 3649) congestion control
	3	*
	4	* See http://www.icir.org/floyd/hstcp.html
	5	*
	6	* John Heffner <[email protected]>
	7	*/
	8
a628d29b JH	9	#include <linux/module.h>
	10	#include <net/tcp.h>
	11
	12
	13	/* From AIMD tables from RFC 3649 appendix B,
	14	* with fixed-point MD scaled <<8.
	15	*/
	16	static const struct hstcp_aimd_val {
e905a9ed YH	17	unsigned int cwnd;
e905a9ed YH	18	unsigned int md;
a628d29b JH	19	} hstcp_aimd_vals[] = {
	20	{ 38, 128, /* 0.50 */ },
	21	{ 118, 112, /* 0.44 */ },
	22	{ 221, 104, /* 0.41 */ },
	23	{ 347, 98, /* 0.38 */ },
	24	{ 495, 93, /* 0.37 */ },
	25	{ 663, 89, /* 0.35 */ },
	26	{ 851, 86, /* 0.34 */ },
	27	{ 1058, 83, /* 0.33 */ },
	28	{ 1284, 81, /* 0.32 */ },
	29	{ 1529, 78, /* 0.31 */ },
	30	{ 1793, 76, /* 0.30 */ },
	31	{ 2076, 74, /* 0.29 */ },
	32	{ 2378, 72, /* 0.28 */ },
	33	{ 2699, 71, /* 0.28 */ },
	34	{ 3039, 69, /* 0.27 */ },
	35	{ 3399, 68, /* 0.27 */ },
	36	{ 3778, 66, /* 0.26 */ },
	37	{ 4177, 65, /* 0.26 */ },
	38	{ 4596, 64, /* 0.25 */ },
	39	{ 5036, 62, /* 0.25 */ },
	40	{ 5497, 61, /* 0.24 */ },
	41	{ 5979, 60, /* 0.24 */ },
	42	{ 6483, 59, /* 0.23 */ },
	43	{ 7009, 58, /* 0.23 */ },
	44	{ 7558, 57, /* 0.22 */ },
	45	{ 8130, 56, /* 0.22 */ },
	46	{ 8726, 55, /* 0.22 */ },
	47	{ 9346, 54, /* 0.21 */ },
	48	{ 9991, 53, /* 0.21 */ },
	49	{ 10661, 52, /* 0.21 */ },
	50	{ 11358, 52, /* 0.20 */ },
	51	{ 12082, 51, /* 0.20 */ },
	52	{ 12834, 50, /* 0.20 */ },
	53	{ 13614, 49, /* 0.19 */ },
	54	{ 14424, 48, /* 0.19 */ },
	55	{ 15265, 48, /* 0.19 */ },
	56	{ 16137, 47, /* 0.19 */ },
	57	{ 17042, 46, /* 0.18 */ },
	58	{ 17981, 45, /* 0.18 */ },
	59	{ 18955, 45, /* 0.18 */ },
	60	{ 19965, 44, /* 0.17 */ },
	61	{ 21013, 43, /* 0.17 */ },
	62	{ 22101, 43, /* 0.17 */ },
	63	{ 23230, 42, /* 0.17 */ },
	64	{ 24402, 41, /* 0.16 */ },
	65	{ 25618, 41, /* 0.16 */ },
	66	{ 26881, 40, /* 0.16 */ },
	67	{ 28193, 39, /* 0.16 */ },
	68	{ 29557, 39, /* 0.15 */ },
	69	{ 30975, 38, /* 0.15 */ },
	70	{ 32450, 38, /* 0.15 */ },
	71	{ 33986, 37, /* 0.15 */ },
	72	{ 35586, 36, /* 0.14 */ },
	73	{ 37253, 36, /* 0.14 */ },
	74	{ 38992, 35, /* 0.14 */ },
	75	{ 40808, 35, /* 0.14 */ },
	76	{ 42707, 34, /* 0.13 */ },
	77	{ 44694, 33, /* 0.13 */ },
	78	{ 46776, 33, /* 0.13 */ },
	79	{ 48961, 32, /* 0.13 */ },
	80	{ 51258, 32, /* 0.13 */ },
	81	{ 53677, 31, /* 0.12 */ },
	82	{ 56230, 30, /* 0.12 */ },
83	{ 58932, 30, /* 0.12 */ },
84	{ 61799, 29, /* 0.12 */ },
85	{ 64851, 28, /* 0.11 */ },
86	{ 68113, 28, /* 0.11 */ },
87	{ 71617, 27, /* 0.11 */ },
88	{ 75401, 26, /* 0.10 */ },
89	{ 79517, 26, /* 0.10 */ },
90	{ 84035, 25, /* 0.10 */ },
91	{ 89053, 24, /* 0.10 */ },
92	};
93
94	#define HSTCP_AIMD_MAX ARRAY_SIZE(hstcp_aimd_vals)
95
96	struct hstcp {
97	u32 ai;
98	};
99
6687e988	100	static void hstcp_init(struct sock *sk)
a628d29b	101	{
6687e988 ACM	102	struct tcp_sock *tp = tcp_sk(sk);
6687e988 ACM	103	struct hstcp *ca = inet_csk_ca(sk);
a628d29b JH	104
	105	ca->ai = 0;
	106
	107	/* Ensure the MD arithmetic works. This is somewhat pedantic,
	108	* since I don't think we will see a cwnd this large. :) */
	109	tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128);
	110	}
	111
c3a05c60	112	static void hstcp_cong_avoid(struct sock *sk, u32 adk, u32 in_flight)
a628d29b	113	{
6687e988 ACM	114	struct tcp_sock *tp = tcp_sk(sk);
6687e988 ACM	115	struct hstcp *ca = inet_csk_ca(sk);
a628d29b	116
f4805ede	117	if (!tcp_is_cwnd_limited(sk, in_flight))
a628d29b JH	118	return;
a628d29b JH	119
03fba047 IJ	120	if (tp->snd_cwnd <= tp->snd_ssthresh)
	121	tcp_slow_start(tp);
	122	else {
6150c22e XDW	123	/* Update AIMD parameters.
	124	*
	125	* We want to guarantee that:
	126	* hstcp_aimd_vals[ca->ai-1].cwnd <
	127	* snd_cwnd <=
	128	* hstcp_aimd_vals[ca->ai].cwnd
	129	*/
a628d29b JH	130	if (tp->snd_cwnd > hstcp_aimd_vals[ca->ai].cwnd) {
a628d29b JH	131	while (tp->snd_cwnd > hstcp_aimd_vals[ca->ai].cwnd &&
4a1ff6e2	132	ca->ai < HSTCP_AIMD_MAX - 1)
a628d29b	133	ca->ai++;
6150c22e XDW	134	} else if (ca->ai && tp->snd_cwnd <= hstcp_aimd_vals[ca->ai-1].cwnd) {
6150c22e XDW	135	while (ca->ai && tp->snd_cwnd <= hstcp_aimd_vals[ca->ai-1].cwnd)
a628d29b JH	136	ca->ai--;
	137	}
	138
	139	/* Do additive increase */
	140	if (tp->snd_cwnd < tp->snd_cwnd_clamp) {
fb80a6e1 SH	141	/* cwnd = cwnd + a(w) / cwnd */
fb80a6e1 SH	142	tp->snd_cwnd_cnt += ca->ai + 1;
a628d29b	143	if (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
a628d29b	144	tp->snd_cwnd_cnt -= tp->snd_cwnd;
5528e568	145	tp->snd_cwnd++;
a628d29b JH	146	}
	147	}
	148	}
	149	}
	150
6687e988	151	static u32 hstcp_ssthresh(struct sock *sk)
a628d29b	152	{
6687e988 ACM	153	const struct tcp_sock *tp = tcp_sk(sk);
6687e988 ACM	154	const struct hstcp *ca = inet_csk_ca(sk);
a628d29b JH	155
	156	/* Do multiplicative decrease */
	157	return max(tp->snd_cwnd - ((tp->snd_cwnd * hstcp_aimd_vals[ca->ai].md) >> 8), 2U);
	158	}
	159
	160
	161	static struct tcp_congestion_ops tcp_highspeed = {
	162	.init = hstcp_init,
	163	.ssthresh = hstcp_ssthresh,
	164	.cong_avoid = hstcp_cong_avoid,
	165	.min_cwnd = tcp_reno_min_cwnd,
	166
	167	.owner = THIS_MODULE,
	168	.name = "highspeed"
	169	};
	170
	171	static int __init hstcp_register(void)
	172	{
74975d40	173	BUILD_BUG_ON(sizeof(struct hstcp) > ICSK_CA_PRIV_SIZE);
a628d29b JH	174	return tcp_register_congestion_control(&tcp_highspeed);
	175	}
	176
	177	static void __exit hstcp_unregister(void)
	178	{
	179	tcp_unregister_congestion_control(&tcp_highspeed);
	180	}
	181
	182	module_init(hstcp_register);
	183	module_exit(hstcp_unregister);
	184
	185	MODULE_AUTHOR("John Heffner");
	186	MODULE_LICENSE("GPL");
	187	MODULE_DESCRIPTION("High Speed TCP");