1
2
3
4
5
6
7 package quic
8
9 import (
10 "testing"
11 "time"
12 )
13
14 func TestRenoInitialCongestionWindow(t *testing.T) {
15
16 for _, test := range []struct {
17 maxDatagramSize int
18 wantWindow int
19 }{{
20
21 maxDatagramSize: 1200,
22 wantWindow: 12000,
23 }, {
24
25 maxDatagramSize: 1500,
26 wantWindow: 14720,
27 }, {
28
29 maxDatagramSize: 15000,
30 wantWindow: 30000,
31 }} {
32 c := newReno(test.maxDatagramSize)
33 if got, want := c.congestionWindow, test.wantWindow; got != want {
34 t.Errorf("newReno(max_datagram_size=%v): congestion_window = %v, want %v",
35 test.maxDatagramSize, got, want)
36 }
37 }
38 }
39
40 func TestRenoSlowStartWindowIncreases(t *testing.T) {
41
42
43 test := newRenoTest(t, 1200)
44
45 p0 := test.packetSent(initialSpace, 1200)
46 test.wantVar("congestion_window", 12000)
47 test.packetAcked(initialSpace, p0)
48 test.packetBatchEnd(initialSpace)
49 test.wantVar("congestion_window", 12000+1200)
50
51 p1 := test.packetSent(handshakeSpace, 600)
52 p2 := test.packetSent(handshakeSpace, 300)
53 test.packetAcked(handshakeSpace, p1)
54 test.packetAcked(handshakeSpace, p2)
55 test.packetBatchEnd(handshakeSpace)
56 test.wantVar("congestion_window", 12000+1200+600+300)
57 }
58
59 func TestRenoSlowStartToRecovery(t *testing.T) {
60
61
62
63 test := newRenoTest(t, 1200)
64
65 p0 := test.packetSent(initialSpace, 1200)
66 p1 := test.packetSent(initialSpace, 1200)
67 p2 := test.packetSent(initialSpace, 1200)
68 p3 := test.packetSent(initialSpace, 1200)
69 test.wantVar("congestion_window", 12000)
70
71 t.Logf("# ACK triggers packet loss, sender enters recovery")
72 test.advance(1 * time.Millisecond)
73 test.packetAcked(initialSpace, p3)
74 test.packetLost(initialSpace, p0)
75 test.packetBatchEnd(initialSpace)
76
77
78
79
80 test.wantVar("slow_start_threshold", 6000)
81
82 t.Logf("# packet loss in recovery does not change congestion window")
83 test.packetLost(initialSpace, p1)
84 test.packetBatchEnd(initialSpace)
85
86 t.Logf("# ack of packet from before recovery does not change congestion window")
87 test.packetAcked(initialSpace, p2)
88 test.packetBatchEnd(initialSpace)
89
90 p4 := test.packetSent(initialSpace, 1200)
91 test.packetAcked(initialSpace, p4)
92 test.packetBatchEnd(initialSpace)
93
94
95
96
97 test.wantVar("congestion_window", 6000)
98 }
99
100 func TestRenoRecoveryToCongestionAvoidance(t *testing.T) {
101
102
103
104
105 test := newRenoTest(t, 1200)
106
107 p0 := test.packetSent(initialSpace, 1200)
108 p1 := test.packetSent(initialSpace, 1200)
109 p2 := test.packetSent(initialSpace, 1200)
110 test.advance(1 * time.Millisecond)
111 test.packetAcked(initialSpace, p1)
112 test.packetLost(initialSpace, p0)
113 test.packetBatchEnd(initialSpace)
114
115 p3 := test.packetSent(initialSpace, 1000)
116 test.advance(1 * time.Millisecond)
117 test.packetAcked(initialSpace, p3)
118 test.packetBatchEnd(initialSpace)
119
120 test.wantVar("congestion_window", 6000)
121 test.wantVar("slow_start_threshold", 6000)
122 test.wantVar("congestion_pending_acks", 1000)
123
124 t.Logf("# ack of packet from before recovery does not change congestion window")
125 test.packetAcked(initialSpace, p2)
126 test.packetBatchEnd(initialSpace)
127 test.wantVar("congestion_pending_acks", 1000)
128
129 for i := 0; i < 6; i++ {
130 p := test.packetSent(initialSpace, 1000)
131 test.packetAcked(initialSpace, p)
132 }
133 test.packetBatchEnd(initialSpace)
134 t.Logf("# congestion window increased by max_datagram_size")
135 test.wantVar("congestion_window", 6000+1200)
136 test.wantVar("congestion_pending_acks", 1000)
137 }
138
139 func TestRenoMinimumCongestionWindow(t *testing.T) {
140
141
142 test := newRenoTest(t, 1200)
143
144 p0 := test.packetSent(handshakeSpace, 1200)
145 p1 := test.packetSent(handshakeSpace, 1200)
146 test.advance(1 * time.Millisecond)
147 test.packetAcked(handshakeSpace, p1)
148 test.packetLost(handshakeSpace, p0)
149 test.packetBatchEnd(handshakeSpace)
150 test.wantVar("slow_start_threshold", 6000)
151 test.wantVar("congestion_window", 6000)
152
153 test.advance(1 * time.Millisecond)
154 p2 := test.packetSent(handshakeSpace, 1200)
155 p3 := test.packetSent(handshakeSpace, 1200)
156 test.advance(1 * time.Millisecond)
157 test.packetAcked(handshakeSpace, p3)
158 test.packetLost(handshakeSpace, p2)
159 test.packetBatchEnd(handshakeSpace)
160 test.wantVar("slow_start_threshold", 3000)
161 test.wantVar("congestion_window", 3000)
162
163 p4 := test.packetSent(handshakeSpace, 1200)
164 p5 := test.packetSent(handshakeSpace, 1200)
165 test.advance(1 * time.Millisecond)
166 test.packetAcked(handshakeSpace, p4)
167 test.packetLost(handshakeSpace, p5)
168 test.packetBatchEnd(handshakeSpace)
169 test.wantVar("slow_start_threshold", 1500)
170 test.wantVar("congestion_window", 2400)
171
172 p6 := test.packetSent(handshakeSpace, 1200)
173 p7 := test.packetSent(handshakeSpace, 1200)
174 test.advance(1 * time.Millisecond)
175 test.packetAcked(handshakeSpace, p7)
176 test.packetLost(handshakeSpace, p6)
177 test.packetBatchEnd(handshakeSpace)
178 test.wantVar("slow_start_threshold", 1200)
179 test.wantVar("congestion_window", 2400)
180 }
181
182 func TestRenoSlowStartToCongestionAvoidance(t *testing.T) {
183 test := newRenoTest(t, 1200)
184 test.setRTT(1*time.Millisecond, 0)
185
186 t.Logf("# enter recovery with persistent congestion")
187 p0 := test.packetSent(handshakeSpace, 1200)
188 test.advance(1 * time.Second)
189 p1 := test.packetSent(handshakeSpace, 1200)
190 p2 := test.packetSent(handshakeSpace, 1200)
191 test.advance(1 * time.Millisecond)
192 test.packetAcked(handshakeSpace, p2)
193 test.packetLost(handshakeSpace, p0)
194 test.packetLost(handshakeSpace, p1)
195 test.packetBatchEnd(handshakeSpace)
196 test.wantVar("slow_start_threshold", 6000)
197 test.wantVar("congestion_window", 2400)
198 test.wantVar("congestion_pending_acks", 0)
199
200 t.Logf("# enter slow start on new ack")
201 p3 := test.packetSent(handshakeSpace, 1200)
202 test.packetAcked(handshakeSpace, p3)
203 test.packetBatchEnd(handshakeSpace)
204 test.wantVar("congestion_window", 3600)
205 test.wantVar("congestion_pending_acks", 0)
206
207 t.Logf("# enter congestion avoidance after reaching slow_start_threshold")
208 p4 := test.packetSent(handshakeSpace, 1200)
209 p5 := test.packetSent(handshakeSpace, 1200)
210 p6 := test.packetSent(handshakeSpace, 1200)
211 test.packetAcked(handshakeSpace, p4)
212 test.packetAcked(handshakeSpace, p5)
213 test.packetAcked(handshakeSpace, p6)
214 test.packetBatchEnd(handshakeSpace)
215 test.wantVar("congestion_window", 6000)
216 test.wantVar("congestion_pending_acks", 1200)
217 }
218
219 func TestRenoPersistentCongestionDurationExceeded(t *testing.T) {
220
221
222
223 test := newRenoTest(t, 1200)
224 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
225 test.maxAckDelay = 25 * time.Millisecond
226
227 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
228 p0 := test.packetSent(handshakeSpace, 1200)
229 test.advance(142 * time.Millisecond)
230 p1 := test.packetSent(handshakeSpace, 1200)
231 p2 := test.packetSent(handshakeSpace, 1200)
232 test.packetAcked(handshakeSpace, p2)
233 test.packetLost(handshakeSpace, p0)
234 test.packetLost(handshakeSpace, p1)
235 test.packetBatchEnd(handshakeSpace)
236 test.wantVar("slow_start_threshold", 6000)
237 test.wantVar("congestion_window", 2400)
238 }
239
240 func TestRenoPersistentCongestionDurationNotExceeded(t *testing.T) {
241 test := newRenoTest(t, 1200)
242 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
243 test.maxAckDelay = 25 * time.Millisecond
244
245 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
246 p0 := test.packetSent(handshakeSpace, 1200)
247 test.advance(140 * time.Millisecond)
248 p1 := test.packetSent(handshakeSpace, 1200)
249 p2 := test.packetSent(handshakeSpace, 1200)
250 test.packetAcked(handshakeSpace, p2)
251 test.packetLost(handshakeSpace, p0)
252 test.packetLost(handshakeSpace, p1)
253 test.packetBatchEnd(handshakeSpace)
254 test.wantVar("slow_start_threshold", 6000)
255 test.wantVar("congestion_window", 6000)
256 }
257
258 func TestRenoPersistentCongestionInterveningAck(t *testing.T) {
259
260
261
262 test := newRenoTest(t, 1200)
263
264 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
265 test.maxAckDelay = 25 * time.Millisecond
266
267 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
268 p0 := test.packetSent(handshakeSpace, 1200)
269 test.advance(100 * time.Millisecond)
270 p1 := test.packetSent(handshakeSpace, 1200)
271 test.advance(42 * time.Millisecond)
272 p2 := test.packetSent(handshakeSpace, 1200)
273 p3 := test.packetSent(handshakeSpace, 1200)
274 test.packetAcked(handshakeSpace, p1)
275 test.packetAcked(handshakeSpace, p3)
276 test.packetLost(handshakeSpace, p0)
277 test.packetLost(handshakeSpace, p2)
278 test.packetBatchEnd(handshakeSpace)
279 test.wantVar("slow_start_threshold", 6000)
280 test.wantVar("congestion_window", 6000)
281 }
282
283 func TestRenoPersistentCongestionInterveningLosses(t *testing.T) {
284 test := newRenoTest(t, 1200)
285
286 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
287 test.maxAckDelay = 25 * time.Millisecond
288
289 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
290 p0 := test.packetSent(handshakeSpace, 1200)
291 test.advance(50 * time.Millisecond)
292 p1 := test.packetSent(handshakeSpace, 1200, func(p *sentPacket) {
293 p.inFlight = false
294 p.ackEliciting = false
295 })
296 test.advance(50 * time.Millisecond)
297 p2 := test.packetSent(handshakeSpace, 1200, func(p *sentPacket) {
298 p.ackEliciting = false
299 })
300 test.advance(42 * time.Millisecond)
301 p3 := test.packetSent(handshakeSpace, 1200)
302 p4 := test.packetSent(handshakeSpace, 1200)
303 test.packetAcked(handshakeSpace, p4)
304 test.packetLost(handshakeSpace, p0)
305 test.packetLost(handshakeSpace, p1)
306 test.packetLost(handshakeSpace, p2)
307 test.packetBatchEnd(handshakeSpace)
308 test.wantVar("congestion_window", 6000)
309 test.packetLost(handshakeSpace, p3)
310 test.packetBatchEnd(handshakeSpace)
311 test.wantVar("congestion_window", 2400)
312 }
313
314 func TestRenoPersistentCongestionNoRTTSample(t *testing.T) {
315
316
317 test := newRenoTest(t, 1200)
318
319 t.Logf("first packet sent prior to first RTT sample")
320 p0 := test.packetSent(handshakeSpace, 1200)
321
322 test.advance(1 * time.Millisecond)
323 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
324 test.maxAckDelay = 25 * time.Millisecond
325
326 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
327 test.advance(142 * time.Millisecond)
328 p1 := test.packetSent(handshakeSpace, 1200)
329 p2 := test.packetSent(handshakeSpace, 1200)
330 test.packetAcked(handshakeSpace, p2)
331 test.packetLost(handshakeSpace, p0)
332 test.packetLost(handshakeSpace, p1)
333 test.packetBatchEnd(handshakeSpace)
334 test.wantVar("slow_start_threshold", 6000)
335 test.wantVar("congestion_window", 6000)
336 }
337
338 func TestRenoPersistentCongestionPacketNotAckEliciting(t *testing.T) {
339
340
341 test := newRenoTest(t, 1200)
342
343 t.Logf("first packet set prior to first RTT sample")
344 p0 := test.packetSent(handshakeSpace, 1200)
345
346 test.advance(1 * time.Millisecond)
347 test.setRTT(10*time.Millisecond, 3*time.Millisecond)
348 test.maxAckDelay = 25 * time.Millisecond
349
350 t.Logf("persistent congesion duration is 3 * (10ms + 4*3ms + 25ms) = 141ms")
351 test.advance(142 * time.Millisecond)
352 p1 := test.packetSent(handshakeSpace, 1200)
353 p2 := test.packetSent(handshakeSpace, 1200)
354 test.packetAcked(handshakeSpace, p2)
355 test.packetLost(handshakeSpace, p0)
356 test.packetLost(handshakeSpace, p1)
357 test.packetBatchEnd(handshakeSpace)
358 test.wantVar("slow_start_threshold", 6000)
359 test.wantVar("congestion_window", 6000)
360 }
361
362 func TestRenoCanSend(t *testing.T) {
363 test := newRenoTest(t, 1200)
364 test.wantVar("congestion_window", 12000)
365
366 t.Logf("controller permits sending until congestion window is full")
367 var packets []*sentPacket
368 for i := 0; i < 10; i++ {
369 test.wantVar("bytes_in_flight", i*1200)
370 test.wantCanSend(true)
371 p := test.packetSent(initialSpace, 1200)
372 packets = append(packets, p)
373 }
374 test.wantVar("bytes_in_flight", 12000)
375
376 t.Logf("controller blocks sending when congestion window is consumed")
377 test.wantCanSend(false)
378
379 t.Logf("loss of packet moves to recovery, reduces window")
380 test.packetLost(initialSpace, packets[0])
381 test.packetAcked(initialSpace, packets[1])
382 test.packetBatchEnd(initialSpace)
383 test.wantVar("bytes_in_flight", 9600)
384 test.wantVar("congestion_window", 6000)
385
386 t.Logf("one packet permitted on entry to recovery")
387 test.wantCanSend(true)
388 test.packetSent(initialSpace, 1200)
389 test.wantVar("bytes_in_flight", 10800)
390 test.wantCanSend(false)
391 }
392
393 func TestRenoNonAckEliciting(t *testing.T) {
394 test := newRenoTest(t, 1200)
395 test.wantVar("congestion_window", 12000)
396
397 t.Logf("in-flight packet")
398 p0 := test.packetSent(initialSpace, 1200)
399 test.wantVar("bytes_in_flight", 1200)
400 test.packetAcked(initialSpace, p0)
401 test.packetBatchEnd(initialSpace)
402 test.wantVar("bytes_in_flight", 0)
403 test.wantVar("congestion_window", 12000+1200)
404
405 t.Logf("non-in-flight packet")
406 p1 := test.packetSent(initialSpace, 1200, func(p *sentPacket) {
407 p.inFlight = false
408 p.ackEliciting = false
409 })
410 test.wantVar("bytes_in_flight", 0)
411 test.packetAcked(initialSpace, p1)
412 test.packetBatchEnd(initialSpace)
413 test.wantVar("bytes_in_flight", 0)
414 test.wantVar("congestion_window", 12000+1200)
415 }
416
417 func TestRenoUnderutilizedCongestionWindow(t *testing.T) {
418 test := newRenoTest(t, 1200)
419 test.setUnderutilized(true)
420 test.wantVar("congestion_window", 12000)
421
422 t.Logf("congestion window does not increase when application limited")
423 p0 := test.packetSent(initialSpace, 1200)
424 test.packetAcked(initialSpace, p0)
425 test.wantVar("congestion_window", 12000)
426 }
427
428 func TestRenoDiscardKeys(t *testing.T) {
429 test := newRenoTest(t, 1200)
430
431 p0 := test.packetSent(initialSpace, 1200)
432 p1 := test.packetSent(handshakeSpace, 1200)
433 test.wantVar("bytes_in_flight", 2400)
434
435 test.packetDiscarded(initialSpace, p0)
436 test.wantVar("bytes_in_flight", 1200)
437
438 test.packetDiscarded(handshakeSpace, p1)
439 test.wantVar("bytes_in_flight", 0)
440 }
441
442 type ccTest struct {
443 t *testing.T
444 cc *ccReno
445 rtt rttState
446 maxAckDelay time.Duration
447 now time.Time
448 nextNum [numberSpaceCount]packetNumber
449 }
450
451 func newRenoTest(t *testing.T, maxDatagramSize int) *ccTest {
452 test := &ccTest{
453 t: t,
454 now: time.Date(2000, 1, 1, 0, 0, 0, 0, time.UTC),
455 }
456 test.cc = newReno(maxDatagramSize)
457 return test
458 }
459
460 func (c *ccTest) setRTT(smoothedRTT, rttvar time.Duration) {
461 c.t.Helper()
462 c.t.Logf("set smoothed_rtt=%v rttvar=%v", smoothedRTT, rttvar)
463 c.rtt.smoothedRTT = smoothedRTT
464 c.rtt.rttvar = rttvar
465 if c.rtt.firstSampleTime.IsZero() {
466 c.rtt.firstSampleTime = c.now
467 }
468 }
469
470 func (c *ccTest) setUnderutilized(v bool) {
471 c.t.Helper()
472 c.t.Logf("set underutilized = %v", v)
473 c.cc.setUnderutilized(v)
474 }
475
476 func (c *ccTest) packetSent(space numberSpace, size int, fns ...func(*sentPacket)) *sentPacket {
477 c.t.Helper()
478 num := c.nextNum[space]
479 c.nextNum[space]++
480 sent := &sentPacket{
481 inFlight: true,
482 ackEliciting: true,
483 num: num,
484 size: size,
485 time: c.now,
486 }
487 for _, f := range fns {
488 f(sent)
489 }
490 c.t.Logf("packet sent: num=%v.%v, size=%v", space, sent.num, sent.size)
491 c.cc.packetSent(c.now, space, sent)
492 return sent
493 }
494
495 func (c *ccTest) advance(d time.Duration) {
496 c.t.Helper()
497 c.t.Logf("advance time %v", d)
498 c.now = c.now.Add(d)
499 }
500
501 func (c *ccTest) packetAcked(space numberSpace, sent *sentPacket) {
502 c.t.Helper()
503 c.t.Logf("packet acked: num=%v.%v, size=%v", space, sent.num, sent.size)
504 c.cc.packetAcked(c.now, sent)
505 }
506
507 func (c *ccTest) packetLost(space numberSpace, sent *sentPacket) {
508 c.t.Helper()
509 c.t.Logf("packet lost: num=%v.%v, size=%v", space, sent.num, sent.size)
510 c.cc.packetLost(c.now, space, sent, &c.rtt)
511 }
512
513 func (c *ccTest) packetDiscarded(space numberSpace, sent *sentPacket) {
514 c.t.Helper()
515 c.t.Logf("packet number space discarded: num=%v.%v, size=%v", space, sent.num, sent.size)
516 c.cc.packetDiscarded(sent)
517 }
518
519 func (c *ccTest) packetBatchEnd(space numberSpace) {
520 c.t.Helper()
521 c.t.Logf("(end of batch)")
522 c.cc.packetBatchEnd(c.now, space, &c.rtt, c.maxAckDelay)
523 }
524
525 func (c *ccTest) wantCanSend(want bool) {
526 if got := c.cc.canSend(); got != want {
527 c.t.Fatalf("canSend() = %v, want %v", got, want)
528 }
529 }
530
531 func (c *ccTest) wantVar(name string, want int) {
532 c.t.Helper()
533 var got int
534 switch name {
535 case "bytes_in_flight":
536 got = c.cc.bytesInFlight
537 case "congestion_pending_acks":
538 got = c.cc.congestionPendingAcks
539 case "congestion_window":
540 got = c.cc.congestionWindow
541 case "slow_start_threshold":
542 got = c.cc.slowStartThreshold
543 default:
544 c.t.Fatalf("unknown var %q", name)
545 }
546 if got != want {
547 c.t.Fatalf("ERROR: %v = %v, want %v", name, got, want)
548 }
549 c.t.Logf("# %v = %v", name, got)
550 }
551
View as plain text