1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//go:build go1.21
package quic
import (
"time"
)
// A pacerState controls the rate at which packets are sent using a leaky-bucket rate limiter.
//
// The pacer limits the maximum size of a burst of packets.
// When a burst exceeds this limit, it spreads subsequent packets
// over time.
//
// The bucket is initialized to the maximum burst size (ten packets by default),
// and fills at the rate:
//
// 1.25 * congestion_window / smoothed_rtt
//
// A sender can send one congestion window of packets per RTT,
// since the congestion window consumed by each packet is returned
// one round-trip later by the responding ack.
// The pacer permits sending at slightly faster than this rate to
// avoid underutilizing the congestion window.
//
// The pacer permits the bucket to become negative, and permits
// sending when non-negative. This biases slightly in favor of
// sending packets over limiting them, and permits bursts one
// packet greater than the configured maximum, but permits the pacer
// to be ignorant of the maximum packet size.
//
// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.7
type pacerState struct {
bucket int // measured in bytes
maxBucket int
timerGranularity time.Duration
lastUpdate time.Time
nextSend time.Time
}
func (p *pacerState) init(now time.Time, maxBurst int, timerGranularity time.Duration) {
// Bucket is limited to maximum burst size, which is the initial congestion window.
// https://www.rfc-editor.org/rfc/rfc9002#section-7.7-2
p.maxBucket = maxBurst
p.bucket = p.maxBucket
p.timerGranularity = timerGranularity
p.lastUpdate = now
p.nextSend = now
}
// pacerBytesForInterval returns the number of bytes permitted over an interval.
//
// rate = 1.25 * congestion_window / smoothed_rtt
// bytes = interval * rate
//
// https://www.rfc-editor.org/rfc/rfc9002#section-7.7-6
func pacerBytesForInterval(interval time.Duration, congestionWindow int, rtt time.Duration) int {
bytes := (int64(interval) * int64(congestionWindow)) / int64(rtt)
bytes = (bytes * 5) / 4 // bytes *= 1.25
return int(bytes)
}
// pacerIntervalForBytes returns the amount of time required for a number of bytes.
//
// time_per_byte = (smoothed_rtt / congestion_window) / 1.25
// interval = time_per_byte * bytes
//
// https://www.rfc-editor.org/rfc/rfc9002#section-7.7-8
func pacerIntervalForBytes(bytes int, congestionWindow int, rtt time.Duration) time.Duration {
interval := (int64(rtt) * int64(bytes)) / int64(congestionWindow)
interval = (interval * 4) / 5 // interval /= 1.25
return time.Duration(interval)
}
// advance is called when time passes.
func (p *pacerState) advance(now time.Time, congestionWindow int, rtt time.Duration) {
elapsed := now.Sub(p.lastUpdate)
if elapsed < 0 {
// Time has gone backward?
elapsed = 0
p.nextSend = now // allow a packet through to get back on track
if p.bucket < 0 {
p.bucket = 0
}
}
p.lastUpdate = now
if rtt == 0 {
// Avoid divide by zero in the implausible case that we measure no RTT.
p.bucket = p.maxBucket
return
}
// Refill the bucket.
delta := pacerBytesForInterval(elapsed, congestionWindow, rtt)
p.bucket = min(p.bucket+delta, p.maxBucket)
}
// packetSent is called to record transmission of a packet.
func (p *pacerState) packetSent(now time.Time, size, congestionWindow int, rtt time.Duration) {
p.bucket -= size
if p.bucket < -congestionWindow {
// Never allow the bucket to fall more than one congestion window in arrears.
// We can only fall this far behind if the sender is sending unpaced packets,
// the congestion window has been exceeded, or the RTT is less than the
// timer granularity.
//
// Limiting the minimum bucket size limits the maximum pacer delay
// to RTT/1.25.
p.bucket = -congestionWindow
}
if p.bucket >= 0 {
p.nextSend = now
return
}
// Next send occurs when the bucket has refilled to 0.
delay := pacerIntervalForBytes(-p.bucket, congestionWindow, rtt)
p.nextSend = now.Add(delay)
}
// canSend reports whether a packet can be sent now.
// If it returns false, next is the time when the next packet can be sent.
func (p *pacerState) canSend(now time.Time) (canSend bool, next time.Time) {
// If the next send time is within the timer granularity, send immediately.
if p.nextSend.After(now.Add(p.timerGranularity)) {
return false, p.nextSend
}
return true, time.Time{}
}
|
