[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 ack, u32 acked)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct hstcp *ca = inet_csk_ca(sk);

	if (!tcp_is_cwnd_limited(sk))
		return;

	if (tcp_in_slow_start(tp))
		tcp_slow_start(tp, acked);
	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);
	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 __read_mostly = {
	.init		= hstcp_init,
	.ssthresh	= hstcp_ssthresh,
	.undo_cwnd	= tcp_reno_undo_cwnd,
	.cong_avoid	= hstcp_cong_avoid,

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