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 (*ConnectionStates) Insert

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

func (*ConnectionStates) Remove

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)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL