tcp_yeah.c 6.89 KB
Newer Older
1
2
3
4
5
/*
 *
 *   YeAH TCP
 *
 * For further details look at:
6
 *   https://web.archive.org/web/20080316215752/http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
7
8
 *
 */
9
10
11
12
#include <linux/mm.h>
#include <linux/module.h>
#include <linux/skbuff.h>
#include <linux/inet_diag.h>
13

14
#include <net/tcp.h>
15

16
#include "tcp_vegas.h"
17

18
19
20
21
22
23
24
#define TCP_YEAH_ALPHA       80 /* number of packets queued at the bottleneck */
#define TCP_YEAH_GAMMA        1 /* fraction of queue to be removed per rtt */
#define TCP_YEAH_DELTA        3 /* log minimum fraction of cwnd to be removed on loss */
#define TCP_YEAH_EPSILON      1 /* log maximum fraction to be removed on early decongestion */
#define TCP_YEAH_PHY          8 /* maximum delta from base */
#define TCP_YEAH_RHO         16 /* minimum number of consecutive rtt to consider competition on loss */
#define TCP_YEAH_ZETA        50 /* minimum number of state switches to reset reno_count */
25
26
27
28
29

#define TCP_SCALABLE_AI_CNT	 100U

/* YeAH variables */
struct yeah {
30
	struct vegas vegas;	/* must be first */
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

	/* YeAH */
	u32 lastQ;
	u32 doing_reno_now;

	u32 reno_count;
	u32 fast_count;

	u32 pkts_acked;
};

static void tcp_yeah_init(struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct yeah *yeah = inet_csk_ca(sk);

	tcp_vegas_init(sk);

	yeah->doing_reno_now = 0;
	yeah->lastQ = 0;

	yeah->reno_count = 2;

	/* 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);
}

59
static void tcp_yeah_pkts_acked(struct sock *sk, u32 pkts_acked, s32 rtt_us)
60
61
62
63
64
65
{
	const struct inet_connection_sock *icsk = inet_csk(sk);
	struct yeah *yeah = inet_csk_ca(sk);

	if (icsk->icsk_ca_state == TCP_CA_Open)
		yeah->pkts_acked = pkts_acked;
66

67
	tcp_vegas_pkts_acked(sk, pkts_acked, rtt_us);
68
69
}

70
static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, u32 acked)
71
72
73
74
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct yeah *yeah = inet_csk_ca(sk);

75
	if (!tcp_is_cwnd_limited(sk))
76
77
		return;

78
	if (tp->snd_cwnd <= tp->snd_ssthresh)
79
		tcp_slow_start(tp, acked);
80
81

	else if (!yeah->doing_reno_now) {
82
83
		/* Scalable */

84
		tp->snd_cwnd_cnt += yeah->pkts_acked;
stephen hemminger's avatar
stephen hemminger committed
85
		if (tp->snd_cwnd_cnt > min(tp->snd_cwnd, TCP_SCALABLE_AI_CNT)) {
86
87
88
89
90
91
92
93
94
			if (tp->snd_cwnd < tp->snd_cwnd_clamp)
				tp->snd_cwnd++;
			tp->snd_cwnd_cnt = 0;
		}

		yeah->pkts_acked = 1;

	} else {
		/* Reno */
Neal Cardwell's avatar
Neal Cardwell committed
95
		tcp_cong_avoid_ai(tp, tp->snd_cwnd, 1);
96
97
	}

98
	/* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt.
99
100
101
102
103
	 *
	 * These are so named because they represent the approximate values
	 * of snd_una and snd_nxt at the beginning of the current RTT. More
	 * precisely, they represent the amount of data sent during the RTT.
	 * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt,
104
	 * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding
105
106
107
	 * bytes of data have been ACKed during the course of the RTT, giving
	 * an "actual" rate of:
	 *
108
	 *     (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration)
109
	 *
110
	 * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una,
111
112
113
114
115
116
117
118
119
	 * because delayed ACKs can cover more than one segment, so they
	 * don't line up yeahly with the boundaries of RTTs.
	 *
	 * Another unfortunate fact of life is that delayed ACKs delay the
	 * advance of the left edge of our send window, so that the number
	 * of bytes we send in an RTT is often less than our cwnd will allow.
	 * So we keep track of our cwnd separately, in v_beg_snd_cwnd.
	 */

120
	if (after(ack, yeah->vegas.beg_snd_nxt)) {
121
122
123
124
125
126
127
128
129
		/* We do the Vegas calculations only if we got enough RTT
		 * samples that we can be reasonably sure that we got
		 * at least one RTT sample that wasn't from a delayed ACK.
		 * If we only had 2 samples total,
		 * then that means we're getting only 1 ACK per RTT, which
		 * means they're almost certainly delayed ACKs.
		 * If  we have 3 samples, we should be OK.
		 */

130
		if (yeah->vegas.cntRTT > 2) {
Stephen Hemminger's avatar
Stephen Hemminger committed
131
132
			u32 rtt, queue;
			u64 bw;
133
134
135
136
137
138
139
140
141
142
143
144

			/* We have enough RTT samples, so, using the Vegas
			 * algorithm, we determine if we should increase or
			 * decrease cwnd, and by how much.
			 */

			/* Pluck out the RTT we are using for the Vegas
			 * calculations. This is the min RTT seen during the
			 * last RTT. Taking the min filters out the effects
			 * of delayed ACKs, at the cost of noticing congestion
			 * a bit later.
			 */
145
			rtt = yeah->vegas.minRTT;
146

Stephen Hemminger's avatar
Stephen Hemminger committed
147
148
149
150
			/* Compute excess number of packets above bandwidth
			 * Avoid doing full 64 bit divide.
			 */
			bw = tp->snd_cwnd;
151
			bw *= rtt - yeah->vegas.baseRTT;
Stephen Hemminger's avatar
Stephen Hemminger committed
152
153
154
155
			do_div(bw, rtt);
			queue = bw;

			if (queue > TCP_YEAH_ALPHA ||
156
			    rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) {
157
158
				if (queue > TCP_YEAH_ALPHA &&
				    tp->snd_cwnd > yeah->reno_count) {
Stephen Hemminger's avatar
Stephen Hemminger committed
159
160
					u32 reduction = min(queue / TCP_YEAH_GAMMA ,
							    tp->snd_cwnd >> TCP_YEAH_EPSILON);
161
162
163

					tp->snd_cwnd -= reduction;

Stephen Hemminger's avatar
Stephen Hemminger committed
164
165
					tp->snd_cwnd = max(tp->snd_cwnd,
							   yeah->reno_count);
166
167

					tp->snd_ssthresh = tp->snd_cwnd;
Stephen Hemminger's avatar
Stephen Hemminger committed
168
				}
169
170

				if (yeah->reno_count <= 2)
Stephen Hemminger's avatar
Stephen Hemminger committed
171
					yeah->reno_count = max(tp->snd_cwnd>>1, 2U);
172
173
174
				else
					yeah->reno_count++;

Stephen Hemminger's avatar
Stephen Hemminger committed
175
176
				yeah->doing_reno_now = min(yeah->doing_reno_now + 1,
							   0xffffffU);
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
			} else {
				yeah->fast_count++;

				if (yeah->fast_count > TCP_YEAH_ZETA) {
					yeah->reno_count = 2;
					yeah->fast_count = 0;
				}

				yeah->doing_reno_now = 0;
			}

			yeah->lastQ = queue;
		}

		/* Save the extent of the current window so we can use this
		 * at the end of the next RTT.
		 */
194
195
196
		yeah->vegas.beg_snd_una  = yeah->vegas.beg_snd_nxt;
		yeah->vegas.beg_snd_nxt  = tp->snd_nxt;
		yeah->vegas.beg_snd_cwnd = tp->snd_cwnd;
197
198

		/* Wipe the slate clean for the next RTT. */
199
200
		yeah->vegas.cntRTT = 0;
		yeah->vegas.minRTT = 0x7fffffff;
201
202
203
	}
}

stephen hemminger's avatar
stephen hemminger committed
204
205
static u32 tcp_yeah_ssthresh(struct sock *sk)
{
206
207
208
209
210
211
212
	const struct tcp_sock *tp = tcp_sk(sk);
	struct yeah *yeah = inet_csk_ca(sk);
	u32 reduction;

	if (yeah->doing_reno_now < TCP_YEAH_RHO) {
		reduction = yeah->lastQ;

213
		reduction = min(reduction, max(tp->snd_cwnd>>1, 2U));
214

215
		reduction = max(reduction, tp->snd_cwnd >> TCP_YEAH_DELTA);
216
	} else
217
		reduction = max(tp->snd_cwnd>>1, 2U);
218
219
220
221

	yeah->fast_count = 0;
	yeah->reno_count = max(yeah->reno_count>>1, 2U);

222
	return max_t(int, tp->snd_cwnd - reduction, 2);
223
224
}

225
static struct tcp_congestion_ops tcp_yeah __read_mostly = {
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
	.init		= tcp_yeah_init,
	.ssthresh	= tcp_yeah_ssthresh,
	.cong_avoid	= tcp_yeah_cong_avoid,
	.set_state	= tcp_vegas_state,
	.cwnd_event	= tcp_vegas_cwnd_event,
	.get_info	= tcp_vegas_get_info,
	.pkts_acked	= tcp_yeah_pkts_acked,

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

static int __init tcp_yeah_register(void)
{
	BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE);
	tcp_register_congestion_control(&tcp_yeah);
	return 0;
}

static void __exit tcp_yeah_unregister(void)
{
	tcp_unregister_congestion_control(&tcp_yeah);
}

module_init(tcp_yeah_register);
module_exit(tcp_yeah_unregister);

MODULE_AUTHOR("Angelo P. Castellani");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("YeAH TCP");