1 // Copyright 2023 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 //go:build go1.21 6 7 package quic 8 9 import ( 10 "math" 11 "time" 12 ) 13 14 // ccReno is the NewReno-based congestion controller defined in RFC 9002. 15 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7 16 type ccReno struct { 17 maxDatagramSize int 18 19 // Maximum number of bytes allowed to be in flight. 20 congestionWindow int 21 22 // Sum of size of all packets that contain at least one ack-eliciting 23 // or PADDING frame (i.e., any non-ACK frame), and have neither been 24 // acknowledged nor declared lost. 25 bytesInFlight int 26 27 // When the congestion window is below the slow start threshold, 28 // the controller is in slow start. 29 slowStartThreshold int 30 31 // The time the current recovery period started, or zero when not 32 // in a recovery period. 33 recoveryStartTime time.Time 34 35 // Accumulated count of bytes acknowledged in congestion avoidance. 36 congestionPendingAcks int 37 38 // When entering a recovery period, we are allowed to send one packet 39 // before reducing the congestion window. sendOnePacketInRecovery is 40 // true if we haven't sent that packet yet. 41 sendOnePacketInRecovery bool 42 43 // underutilized is set if the congestion window is underutilized 44 // due to insufficient application data, flow control limits, or 45 // anti-amplification limits. 46 underutilized bool 47 48 // ackLastLoss is the sent time of the newest lost packet processed 49 // in the current batch. 50 ackLastLoss time.Time 51 52 // Data tracking the duration of the most recently handled sequence of 53 // contiguous lost packets. If this exceeds the persistent congestion duration, 54 // persistent congestion is declared. 55 // 56 // https://www.rfc-editor.org/rfc/rfc9002#section-7.6 57 persistentCongestion [numberSpaceCount]struct { 58 start time.Time // send time of first lost packet 59 end time.Time // send time of last lost packet 60 next packetNumber // one plus the number of the last lost packet 61 } 62 } 63 64 func newReno(maxDatagramSize int) *ccReno { 65 c := &ccReno{ 66 maxDatagramSize: maxDatagramSize, 67 } 68 69 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-1 70 c.congestionWindow = min(10*maxDatagramSize, max(14720, c.minimumCongestionWindow())) 71 72 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.1-1 73 c.slowStartThreshold = math.MaxInt 74 75 for space := range c.persistentCongestion { 76 c.persistentCongestion[space].next = -1 77 } 78 return c 79 } 80 81 // canSend reports whether the congestion controller permits sending 82 // a maximum-size datagram at this time. 83 // 84 // "An endpoint MUST NOT send a packet if it would cause bytes_in_flight [...] 85 // to be larger than the congestion window [...]" 86 // https://www.rfc-editor.org/rfc/rfc9002#section-7-7 87 // 88 // For simplicity and efficiency, we don't permit sending undersized datagrams. 89 func (c *ccReno) canSend() bool { 90 if c.sendOnePacketInRecovery { 91 return true 92 } 93 return c.bytesInFlight+c.maxDatagramSize <= c.congestionWindow 94 } 95 96 // setUnderutilized indicates that the congestion window is underutilized. 97 // 98 // The congestion window is underutilized if bytes in flight is smaller than 99 // the congestion window and sending is not pacing limited; that is, the 100 // congestion controller permits sending data, but no data is sent. 101 // 102 // https://www.rfc-editor.org/rfc/rfc9002#section-7.8 103 func (c *ccReno) setUnderutilized(v bool) { 104 c.underutilized = v 105 } 106 107 // packetSent indicates that a packet has been sent. 108 func (c *ccReno) packetSent(now time.Time, space numberSpace, sent *sentPacket) { 109 if !sent.inFlight { 110 return 111 } 112 c.bytesInFlight += sent.size 113 if c.sendOnePacketInRecovery { 114 c.sendOnePacketInRecovery = false 115 } 116 } 117 118 // Acked and lost packets are processed in batches 119 // resulting from either a received ACK frame or 120 // the loss detection timer expiring. 121 // 122 // A batch consists of zero or more calls to packetAcked and packetLost, 123 // followed by a single call to packetBatchEnd. 124 // 125 // Acks may be reported in any order, but lost packets must 126 // be reported in strictly increasing order. 127 128 // packetAcked indicates that a packet has been newly acknowledged. 129 func (c *ccReno) packetAcked(now time.Time, sent *sentPacket) { 130 if !sent.inFlight { 131 return 132 } 133 c.bytesInFlight -= sent.size 134 135 if c.underutilized { 136 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.8 137 return 138 } 139 if sent.time.Before(c.recoveryStartTime) { 140 // In recovery, and this packet was sent before we entered recovery. 141 // (If this packet was sent after we entered recovery, receiving an ack 142 // for it moves us out of recovery into congestion avoidance.) 143 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2 144 return 145 } 146 c.congestionPendingAcks += sent.size 147 } 148 149 // packetLost indicates that a packet has been newly marked as lost. 150 // Lost packets must be reported in increasing order. 151 func (c *ccReno) packetLost(now time.Time, space numberSpace, sent *sentPacket, rtt *rttState) { 152 // Record state to check for persistent congestion. 153 // https://www.rfc-editor.org/rfc/rfc9002#section-7.6 154 // 155 // Note that this relies on always receiving loss events in increasing order: 156 // All packets prior to the one we're examining now have either been 157 // acknowledged or declared lost. 158 isValidPersistentCongestionSample := (sent.ackEliciting && 159 !rtt.firstSampleTime.IsZero() && 160 !sent.time.Before(rtt.firstSampleTime)) 161 if isValidPersistentCongestionSample { 162 // This packet either extends an existing range of lost packets, 163 // or starts a new one. 164 if sent.num != c.persistentCongestion[space].next { 165 c.persistentCongestion[space].start = sent.time 166 } 167 c.persistentCongestion[space].end = sent.time 168 c.persistentCongestion[space].next = sent.num + 1 169 } else { 170 // This packet cannot establish persistent congestion on its own. 171 // However, if we have an existing range of lost packets, 172 // this does not break it. 173 if sent.num == c.persistentCongestion[space].next { 174 c.persistentCongestion[space].next = sent.num + 1 175 } 176 } 177 178 if !sent.inFlight { 179 return 180 } 181 c.bytesInFlight -= sent.size 182 if sent.time.After(c.ackLastLoss) { 183 c.ackLastLoss = sent.time 184 } 185 } 186 187 // packetBatchEnd is called at the end of processing a batch of acked or lost packets. 188 func (c *ccReno) packetBatchEnd(now time.Time, space numberSpace, rtt *rttState, maxAckDelay time.Duration) { 189 if !c.ackLastLoss.IsZero() && !c.ackLastLoss.Before(c.recoveryStartTime) { 190 // Enter the recovery state. 191 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2 192 c.recoveryStartTime = now 193 c.slowStartThreshold = c.congestionWindow / 2 194 c.congestionWindow = max(c.slowStartThreshold, c.minimumCongestionWindow()) 195 c.sendOnePacketInRecovery = true 196 // Clear congestionPendingAcks to avoid increasing the congestion 197 // window based on acks in a frame that sends us into recovery. 198 c.congestionPendingAcks = 0 199 } else if c.congestionPendingAcks > 0 { 200 // We are in slow start or congestion avoidance. 201 if c.congestionWindow < c.slowStartThreshold { 202 // When the congestion window is less than the slow start threshold, 203 // we are in slow start and increase the window by the number of 204 // bytes acknowledged. 205 d := min(c.slowStartThreshold-c.congestionWindow, c.congestionPendingAcks) 206 c.congestionWindow += d 207 c.congestionPendingAcks -= d 208 } 209 // When the congestion window is at or above the slow start threshold, 210 // we are in congestion avoidance. 211 // 212 // RFC 9002 does not specify an algorithm here. The following is 213 // the recommended algorithm from RFC 5681, in which we increment 214 // the window by the maximum datagram size every time the number 215 // of bytes acknowledged reaches cwnd. 216 for c.congestionPendingAcks > c.congestionWindow { 217 c.congestionPendingAcks -= c.congestionWindow 218 c.congestionWindow += c.maxDatagramSize 219 } 220 } 221 if !c.ackLastLoss.IsZero() { 222 // Check for persistent congestion. 223 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6 224 // 225 // "A sender [...] MAY use state for just the packet number space that 226 // was acknowledged." 227 // https://www.rfc-editor.org/rfc/rfc9002#section-7.6.2-5 228 // 229 // For simplicity, we consider each number space independently. 230 const persistentCongestionThreshold = 3 231 d := (rtt.smoothedRTT + max(4*rtt.rttvar, timerGranularity) + maxAckDelay) * 232 persistentCongestionThreshold 233 start := c.persistentCongestion[space].start 234 end := c.persistentCongestion[space].end 235 if end.Sub(start) >= d { 236 c.congestionWindow = c.minimumCongestionWindow() 237 c.recoveryStartTime = time.Time{} 238 rtt.establishPersistentCongestion() 239 } 240 } 241 c.ackLastLoss = time.Time{} 242 } 243 244 // packetDiscarded indicates that the keys for a packet's space have been discarded. 245 func (c *ccReno) packetDiscarded(sent *sentPacket) { 246 // https://www.rfc-editor.org/rfc/rfc9002#section-6.2.2-3 247 if sent.inFlight { 248 c.bytesInFlight -= sent.size 249 } 250 } 251 252 func (c *ccReno) minimumCongestionWindow() int { 253 // https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-4 254 return 2 * c.maxDatagramSize 255 } 256