pacer.go

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