congestion

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 12, 2023 License: GPL-3.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// InitialMaxDatagramSize is the default maximum packet size used in QUIC for congestion window computations in bytes.
	InitialMaxDatagramSize        = 1252
	InitialPacketSizeIPv4         = 1252
	InitialPacketSizeIPv6         = 1232
	InitialCongestionWindow       = 32
	DefaultBBRMaxCongestionWindow = 10000
)
View Source 
const (
	// Startup phase of the connection.
	STARTUP = iota
	// After achieving the highest possible bandwidth during the startup, lower
	// the pacing rate in order to drain the queue.
	DRAIN
	// Cruising mode.
	PROBE_BW
	// Temporarily slow down sending in order to empty the buffer and measure
	// the real minimum RTT.
	PROBE_RTT
)
View Source 
const (
	// Do not limit.
	NOT_IN_RECOVERY = iota

	// Allow an extra outstanding byte for each byte acknowledged.
	CONSERVATION

	// Allow two extra outstanding bytes for each byte acknowledged (slow
	// start).
	GROWTH
)
View Source 
const InfDuration = time.Duration(math.MaxInt64)

InfDuration is a duration of infinite length

View Source 
const InvalidPacketNumber congestion.PacketNumber = -1
View Source 
const MaxByteCount = congestion.ByteCount(1<<62 - 1)
View Source 
const MaxCongestionWindowPackets = 20000
View Source 
const MinPacingDelay = time.Millisecond
View Source 
const TimerGranularity = time.Millisecond

Variables

View Source 
var (

	// Default initial rtt used before any samples are received.
	InitialRtt = 100 * time.Millisecond

	// The gain used for the STARTUP, equal to  4*ln(2).
	DefaultHighGain = 2.77

	// The gain used in STARTUP after loss has been detected.
	// 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
	// in measured bandwidth.
	StartupAfterLossGain = 1.5

	// The cycle of gains used during the PROBE_BW stage.
	PacingGain = []float64{1.25, 0.75, 1, 1, 1, 1, 1, 1}

	// The length of the gain cycle.
	GainCycleLength = len(PacingGain)

	// The size of the bandwidth filter window, in round-trips.
	BandwidthWindowSize = GainCycleLength + 2

	// The time after which the current min_rtt value expires.
	MinRttExpiry = 10 * time.Second

	// The minimum time the connection can spend in PROBE_RTT mode.
	ProbeRttTime = time.Millisecond * 200

	// If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
	// within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
	// will exit the STARTUP mode.
	StartupGrowthTarget                         = 1.25
	RoundTripsWithoutGrowthBeforeExitingStartup = int64(3)

	// Coefficient of target congestion window to use when basing PROBE_RTT on BDP.
	ModerateProbeRttMultiplier = 0.75

	// Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
	// we don't need to enter PROBE_RTT.
	SimilarMinRttThreshold = 1.125

	// Congestion window gain for QUIC BBR during PROBE_BW phase.
	DefaultCongestionWindowGainConst = 2.0
)
View Source 
var (
	InfiniteBandwidth = Bandwidth(math.MaxUint64)
)
View Source 
var (
	InfiniteRTT = time.Duration(math.MaxInt64)
)

Functions

func AbsDuration 

func AbsDuration(d time.Duration) time.Duration

AbsDuration returns the absolute value of a time duration

func GetInitialPacketSize 

func GetInitialPacketSize(addr net.Addr) congestion.ByteCount

func Max 

func Max[T cmp.Ordered](a, b T) T

func MaxFilter 

func MaxFilter(a, b int64) bool

Compares two values and returns true if the first is greater than or equal to the second.

func MaxTime 

func MaxTime(a, b time.Time) time.Time

MaxTime returns the later time

func Min 

func Min[T cmp.Ordered](a, b T) T

func MinFilter 

func MinFilter(a, b int64) bool

Compares two values and returns true if the first is less than or equal to the second.

func MinNonZeroDuration 

func MinNonZeroDuration(a, b time.Duration) time.Duration

MinNonZeroDuration return the minimum duration that's not zero.

func MinNonZeroTime 

func MinNonZeroTime(a, b time.Time) time.Time

MinNonZeroTime returns the earlist time that is not time.Time{} If both a and b are time.Time{}, it returns time.Time{}

func MinTime 

func MinTime(a, b time.Time) time.Time

MinTime returns the earlier time

func NewBBRSender 

func NewBBRSender(
	clock Clock,
	initialMaxDatagramSize,
	initialCongestionWindow,
	initialMaxCongestionWindow congestion.ByteCount,
) *bbrSender

func NewCubicSender 

func NewCubicSender(
	clock Clock,
	initialMaxDatagramSize congestion.ByteCount,
	reno bool,
) *cubicSender

NewCubicSender makes a new cubic sender

func SentPacketToSendTimeState 

func SentPacketToSendTimeState(sentPacket *ConnectionStateOnSentPacket, sendTimeState *SendTimeState)

SentPacketToSendTimeState Copy a subset of the (private) ConnectionStateOnSentPacket to the (public) SendTimeState. Always set send_time_state->is_valid to true.

Types

type Bandwidth 

type Bandwidth uint64

Bandwidth of a connection 

const (
	// BitsPerSecond is 1 bit per second
	BitsPerSecond Bandwidth = 1
	// BytesPerSecond is 1 byte per second
	BytesPerSecond = 8 * BitsPerSecond
)

func BandwidthFromDelta 

func BandwidthFromDelta(bytes congestion.ByteCount, delta time.Duration) Bandwidth

BandwidthFromDelta calculates the bandwidth from a number of bytes and a time delta

type BandwidthSample 

type BandwidthSample struct {
	// contains filtered or unexported fields
}

BandwidthSample

func NewBandwidthSample 

func NewBandwidthSample() *BandwidthSample

type BandwidthSampler 

type BandwidthSampler struct {
	// contains filtered or unexported fields
}

BandwidthSampler keeps track of sent and acknowledged packets and outputs a bandwidth sample for every packet acknowledged. The samples are taken for individual packets, and are not filtered; the consumer has to filter the bandwidth samples itself. In certain cases, the sampler will locally severely underestimate the bandwidth, hence a maximum filter with a size of at least one RTT is recommended.

This class bases its samples on the slope of two curves: the number of bytes sent over time, and the number of bytes acknowledged as received over time. It produces a sample of both slopes for every packet that gets acknowledged, based on a slope between two points on each of the corresponding curves. Note that due to the packet loss, the number of bytes on each curve might get further and further away from each other, meaning that it is not feasible to compare byte values coming from different curves with each other.

The obvious points for measuring slope sample are the ones corresponding to the packet that was just acknowledged. Let us denote them as S_1 (point at which the current packet was sent) and A_1 (point at which the current packet was acknowledged). However, taking a slope requires two points on each line, so estimating bandwidth requires picking a packet in the past with respect to which the slope is measured.

For that purpose, BandwidthSampler always keeps track of the most recently acknowledged packet, and records it together with every outgoing packet. When a packet gets acknowledged (A_1), it has not only information about when it itself was sent (S_1), but also the information about the latest acknowledged packet right before it was sent (S_0 and A_0).

Based on that data, send and ack rate are estimated as: 

send_rate = (bytes(S_1) - bytes(S_0)) / (time(S_1) - time(S_0))
ack_rate = (bytes(A_1) - bytes(A_0)) / (time(A_1) - time(A_0))

Here, the ack rate is intuitively the rate we want to treat as bandwidth. However, in certain cases (e.g. ack compression) the ack rate at a point may end up higher than the rate at which the data was originally sent, which is not indicative of the real bandwidth. Hence, we use the send rate as an upper bound, and the sample value is 

rate_sample = min(send_rate, ack_rate)

An important edge case handled by the sampler is tracking the app-limited samples. There are multiple meaning of "app-limited" used interchangeably, hence it is important to understand and to be able to distinguish between them.

Meaning 1: connection state. The connection is said to be app-limited when there is no outstanding data to send. This means that certain bandwidth samples in the future would not be an accurate indication of the link capacity, and it is important to inform consumer about that. Whenever connection becomes app-limited, the sampler is notified via OnAppLimited() method.

Meaning 2: a phase in the bandwidth sampler. As soon as the bandwidth sampler becomes notified about the connection being app-limited, it enters app-limited phase. In that phase, all *sent* packets are marked as app-limited. Note that the connection itself does not have to be app-limited during the app-limited phase, and in fact it will not be (otherwise how would it send packets?). The boolean flag below indicates whether the sampler is in that phase.

Meaning 3: a flag on the sent packet and on the sample. If a sent packet is sent during the app-limited phase, the resulting sample related to the packet will be marked as app-limited.

With the terminology issue out of the way, let us consider the question of what kind of situation it addresses.

Consider a scenario where we first send packets 1 to 20 at a regular bandwidth, and then immediately run out of data. After a few seconds, we send packets 21 to 60, and only receive ack for 21 between sending packets 40 and 41. In this case, when we sample bandwidth for packets 21 to 40, the S_0/A_0 we use to compute the slope is going to be packet 20, a few seconds apart from the current packet, hence the resulting estimate would be extremely low and not indicative of anything. Only at packet 41 the S_0/A_0 will become 21, meaning that the bandwidth sample would exclude the quiescence.

Based on the analysis of that scenario, we implement the following rule: once OnAppLimited() is called, all sent packets will produce app-limited samples up until an ack for a packet that was sent after OnAppLimited() was called. Note that while the scenario above is not the only scenario when the connection is app-limited, the approach works in other cases too.

func NewBandwidthSampler 

func NewBandwidthSampler() *BandwidthSampler

func (*BandwidthSampler) OnAppLimited 

func (s *BandwidthSampler) OnAppLimited()

OnAppLimited Informs the sampler that the connection is currently app-limited, causing the sampler to enter the app-limited phase. The phase will expire by itself.

func (*BandwidthSampler) OnCongestionEvent 

func (s *BandwidthSampler) OnCongestionEvent(packetNumber congestion.PacketNumber) SendTimeState

OnCongestionEvent Informs the sampler that a packet is considered lost and it should no longer keep track of it.

func (*BandwidthSampler) OnPacketAcked 

func (s *BandwidthSampler) OnPacketAcked(ackTime time.Time, lastAckedPacket congestion.PacketNumber) *BandwidthSample

OnPacketAcked Notifies the sampler that the |lastAckedPacket| is acknowledged. Returns a bandwidth sample. If no bandwidth sample is available, QuicBandwidth::Zero() is returned.

func (*BandwidthSampler) OnPacketSent 

func (s *BandwidthSampler) OnPacketSent(sentTime time.Time, lastSentPacket congestion.PacketNumber, sentBytes, bytesInFlight congestion.ByteCount, hasRetransmittableData bool)

OnPacketSent Inputs the sent packet information into the sampler. Assumes that all packets are sent in order. The information about the packet will not be released from the sampler until it the packet is either acknowledged or declared lost.

type Clock 

type Clock interface {
	Now() time.Time
}

A Clock returns the current time

type ConnectionStateOnSentPacket 

type ConnectionStateOnSentPacket struct {
	// contains filtered or unexported fields
}

ConnectionStateOnSentPacket represents the information about a sent packet and the state of the connection at the moment the packet was sent, specifically the information about the most recently acknowledged packet at that moment.

func NewConnectionStateOnSentPacket 

func NewConnectionStateOnSentPacket(packetNumber congestion.PacketNumber, sentTime time.Time, bytes congestion.ByteCount, sampler *BandwidthSampler) *ConnectionStateOnSentPacket

type ConnectionStates 

type ConnectionStates struct {
	// contains filtered or unexported fields
}

ConnectionStates Record of the connection state at the point where each packet in flight was sent, indexed by the packet number. FIXME: using LinkedList replace map to fast remove all the packets lower than the specified packet number.

func (*ConnectionStates) Get 

func (s *ConnectionStates) Get(packetNumber congestion.PacketNumber) *ConnectionStateOnSentPacket

func (*ConnectionStates) Insert 

func (s *ConnectionStates) Insert(packetNumber congestion.PacketNumber, sentTime time.Time, bytes congestion.ByteCount, sampler *BandwidthSampler) bool

func (*ConnectionStates) Remove 

func (s *ConnectionStates) Remove(packetNumber congestion.PacketNumber) (bool, *ConnectionStateOnSentPacket)

type Cubic 

type Cubic struct {
	// contains filtered or unexported fields
}

Cubic implements the cubic algorithm from TCP

func NewCubic 

func NewCubic(clock Clock) *Cubic

NewCubic returns a new Cubic instance

func (*Cubic) CongestionWindowAfterAck 

func (c *Cubic) CongestionWindowAfterAck(
	ackedBytes congestion.ByteCount,
	currentCongestionWindow congestion.ByteCount,
	delayMin time.Duration,
	eventTime time.Time,
) congestion.ByteCount

CongestionWindowAfterAck computes a new congestion window to use after a received ACK. Returns the new congestion window in packets. The new congestion window follows a cubic function that depends on the time passed since last packet loss.

func (*Cubic) CongestionWindowAfterPacketLoss 

func (c *Cubic) CongestionWindowAfterPacketLoss(currentCongestionWindow congestion.ByteCount) congestion.ByteCount

CongestionWindowAfterPacketLoss computes a new congestion window to use after a loss event. Returns the new congestion window in packets. The new congestion window is a multiplicative decrease of our current window.

func (*Cubic) OnApplicationLimited 

func (c *Cubic) OnApplicationLimited()

OnApplicationLimited is called on ack arrival when sender is unable to use the available congestion window. Resets Cubic state during quiescence.

func (*Cubic) Reset 

func (c *Cubic) Reset()

Reset is called after a timeout to reset the cubic state

func (*Cubic) SetNumConnections 

func (c *Cubic) SetNumConnections(n int)

SetNumConnections sets the number of emulated connections

type DefaultClock 

type DefaultClock struct{}

DefaultClock implements the Clock interface using the Go stdlib clock.

func (DefaultClock) Now 

func (DefaultClock) Now() time.Time

Now gets the current time

type HybridSlowStart 

type HybridSlowStart struct {
	// contains filtered or unexported fields
}

HybridSlowStart implements the TCP hybrid slow start algorithm

func (*HybridSlowStart) IsEndOfRound 

func (s *HybridSlowStart) IsEndOfRound(ack congestion.PacketNumber) bool

IsEndOfRound returns true if this ack is the last packet number of our current slow start round.

func (*HybridSlowStart) OnPacketAcked 

func (s *HybridSlowStart) OnPacketAcked(ackedPacketNumber congestion.PacketNumber)

OnPacketAcked gets invoked after ShouldExitSlowStart, so it's best to end the round when the final packet of the burst is received and start it on the next incoming ack.

func (*HybridSlowStart) OnPacketSent 

func (s *HybridSlowStart) OnPacketSent(packetNumber congestion.PacketNumber)

OnPacketSent is called when a packet was sent

func (*HybridSlowStart) Restart 

func (s *HybridSlowStart) Restart()

Restart the slow start phase

func (*HybridSlowStart) ShouldExitSlowStart 

func (s *HybridSlowStart) ShouldExitSlowStart(latestRTT time.Duration, minRTT time.Duration, congestionWindow congestion.ByteCount) bool

ShouldExitSlowStart should be called on every new ack frame, since a new RTT measurement can be made then. rtt: the RTT for this ack packet. minRTT: is the lowest delay (RTT) we have seen during the session. congestionWindow: the congestion window in packets.

func (*HybridSlowStart) StartReceiveRound 

func (s *HybridSlowStart) StartReceiveRound(lastSent congestion.PacketNumber)

StartReceiveRound is called for the start of each receive round (burst) in the slow start phase.

func (*HybridSlowStart) Started 

func (s *HybridSlowStart) Started() bool

Started returns true if started

type Sample 

type Sample struct {
	// contains filtered or unexported fields
}

type SendTimeState 

type SendTimeState struct {
	// contains filtered or unexported fields
}

SendTimeState is a subset of ConnectionStateOnSentPacket which is returned to the caller when the packet is acked or lost.

type WindowedFilter 

type WindowedFilter struct {
	// contains filtered or unexported fields
}

WindowedFilter Use the following to construct a windowed filter object of type T. For example, a min filter using QuicTime as the time type: 

WindowedFilter<T, MinFilter<T>, QuicTime, QuicTime::Delta> ObjectName;

A max filter using 64-bit integers as the time type: 

WindowedFilter<T, MaxFilter<T>, uint64_t, int64_t> ObjectName;

Specifically, this template takes four arguments:

  1. T -- type of the measurement that is being filtered.
  2. Compare -- MinFilter<T> or MaxFilter<T>, depending on the type of filter desired.
  3. TimeT -- the type used to represent timestamps.
  4. TimeDeltaT -- the type used to represent continuous time intervals between two timestamps. Has to be the type of (a - b) if both |a| and |b| are of type TimeT.

func NewWindowedFilter 

func NewWindowedFilter(windowLength int64, comparator func(int64, int64) bool) *WindowedFilter

func (*WindowedFilter) GetBest 

func (f *WindowedFilter) GetBest() int64

func (*WindowedFilter) GetSecondBest 

func (f *WindowedFilter) GetSecondBest() int64

func (*WindowedFilter) GetThirdBest 

func (f *WindowedFilter) GetThirdBest() int64

func (*WindowedFilter) Reset 

func (f *WindowedFilter) Reset(newSample int64, newTime int64)

func (*WindowedFilter) SetWindowLength 

func (f *WindowedFilter) SetWindowLength(windowLength int64)

Changes the window length. Does not update any current samples.

func (*WindowedFilter) Update 

func (f *WindowedFilter) Update(sample int64, time int64)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.