congestion_reno.go

Documentation: golang.org/x/net/quic

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