congestion

package
v3.8.0 Latest Latest
Warning

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

 Go to latest Published: Nov 13, 2024 License: GPL-3.0 Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (

	// 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
)

Variables

This section is empty.

Functions

func BandwidthFromBytesAndTimeDelta 

func BandwidthFromBytesAndTimeDelta(bytes int64, duration time.Duration) int64

func MaxFilter 

func MaxFilter[T mathext.Number](lhs, rhs T) int

MaxFilter compares two values and returns 1 if lhs is bigger, -f if lhs is smaller, or 0 if two values are the same.

func MinFilter 

func MinFilter[T mathext.Number](lhs, rhs T) int

MinFilter compares two values and returns 1 if lhs is smaller, -1 if lhs is bigger, or 0 if two values are the same.

Types

type AckedPacketInfo 

type AckedPacketInfo struct {
	PacketNumber     int64
	BytesAcked       int64
	ReceiveTimestamp time.Time
}

func (AckedPacketInfo) String 

func (i AckedPacketInfo) String() string

type BBRSender 

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

func NewBBRSender 

func NewBBRSender(loggingContext string, rttStats *RTTStats) *BBRSender

NewBBRSender constructs a new BBR sender object.

func (*BBRSender) BandwidthEstimate 

func (b *BBRSender) BandwidthEstimate() int64

BandwidthEstimate returns the estimate of maximum bandwidth.

func (*BBRSender) CanSend 

func (b *BBRSender) CanSend(bytesInFlight, bytes int64) bool

CanSend returns true if a packet can be sent based on the congestion window.

func (*BBRSender) OnApplicationLimited 

func (b *BBRSender) OnApplicationLimited(bytesInFlight int64)

OnApplicationLimited updates BBR sender state when there is no application data to send.

func (*BBRSender) OnCongestionEvent 

func (b *BBRSender) OnCongestionEvent(priorInFlight int64, eventTime time.Time, ackedPackets []AckedPacketInfo, lostPackets []LostPacketInfo)

OnCongestionEvent updates BBR sender state from acknowledged and lost packets.

func (*BBRSender) OnPacketSent 

func (b *BBRSender) OnPacketSent(sentTime time.Time, bytesInFlight int64, packetNumber int64, bytes int64, hasRetransmittableData bool)

OnPacketSent updates BBR sender state when a packet is being sent.

type BandwidthSample 

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

BandwidthSample contains a single data point of network bandwidth.

func (BandwidthSample) String 

func (bs BandwidthSample) String() string

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 (*BandwidthSampler) EndOfAppLimitedPhase 

func (bs *BandwidthSampler) EndOfAppLimitedPhase() int64

func (*BandwidthSampler) IsAppLimited 

func (bs *BandwidthSampler) IsAppLimited() bool

func (*BandwidthSampler) OnAppLimited 

func (bs *BandwidthSampler) OnAppLimited()

func (*BandwidthSampler) OnPacketAcknowledged 

func (bs *BandwidthSampler) OnPacketAcknowledged(ackTime time.Time, packetNumber int64) BandwidthSample

func (*BandwidthSampler) OnPacketLost 

func (bs *BandwidthSampler) OnPacketLost(packetNumber int64)

func (*BandwidthSampler) OnPacketSent 

func (bs *BandwidthSampler) OnPacketSent(sentTime time.Time, packetNumber int64, bytes int64, bytesInFlight int64, hasRetransmittableData bool)

func (*BandwidthSampler) RemoveObsoletePackets 

func (bs *BandwidthSampler) RemoveObsoletePackets(leastUnacked int64)

func (*BandwidthSampler) TotalBytesAcked 

func (bs *BandwidthSampler) TotalBytesAcked() int64

type BandwidthSamplerInterface 

type BandwidthSamplerInterface interface {
	// 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.
	OnPacketSent(sentTime time.Time, packetNumber, bytes, bytesInFlight int64, hasRetransmittableData bool)

	// OnPacketAcknowledged notifies the sampler that the packetNumber is acknowledged.
	// Returns a bandwidth sample. If no bandwidth sample is available,
	// zero bandwidth is returned.
	OnPacketAcknowledged(ackTime time.Time, packetNumber int64) BandwidthSample

	// OnPacketLost informs the sampler that a packet is considered lost and
	// it should no longer keep track of it.
	OnPacketLost(packetNumber int64)

	// 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.
	OnAppLimited()

	// RemoveObsoletePackets removes all the packets lower than the specified
	// packet number.
	RemoveObsoletePackets(leastUnacked int64)

	// TotalBytesAcked returns the total number of bytes currently acknowledged
	// by the receiver.
	TotalBytesAcked() int64

	// IsAppLimited returns true if the sampler is in app-limited phase.
	IsAppLimited() bool

	// EndOfAppLimitedPhase returns the last packet number in the
	// app-limited phase.
	EndOfAppLimitedPhase() int64
}

BandwidthSamplerInterface is an interface common to any class that can provide bandwidth samples from the information per individual acknowledged packet.

func NewBandwidthSampler 

func NewBandwidthSampler() BandwidthSamplerInterface

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 NewConnectionStateOnSentPacketFromSampler 

func NewConnectionStateOnSentPacketFromSampler(sendTime time.Time, size int64, sampler *BandwidthSampler) ConnectionStateOnSentPacket

NewConnectionStateOnSentPacketFromSampler constructs a new ConnectionStateOnSentPacket object from the current state of the bandwidth sampler.

type CubicSendAlgorithm 

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

CubicSendAlgorithm implements cubic congestion algorithm.

func NewCubicSendAlgorithm 

func NewCubicSendAlgorithm(minWindowSize, maxWindowSize uint32) *CubicSendAlgorithm

NewCubicSendAlgorithm initializes a new CubicSendAlgorithm.

func (*CubicSendAlgorithm) CongestionWindowSize 

func (c *CubicSendAlgorithm) CongestionWindowSize() uint32

CongestionWindowSize returns the currect congestion window size.

func (*CubicSendAlgorithm) InSlowStart 

func (c *CubicSendAlgorithm) InSlowStart() bool

InSlowStart returns if cubic is in slow start mode.

func (*CubicSendAlgorithm) OnAck 

func (c *CubicSendAlgorithm) OnAck() uint32

OnAck updates the congestion window size from the received acknowledge.

func (*CubicSendAlgorithm) OnLoss 

func (c *CubicSendAlgorithm) OnLoss() uint32

OnLoss updates the congestion window size from the packet loss.

func (*CubicSendAlgorithm) OnTimeout 

func (c *CubicSendAlgorithm) OnTimeout() uint32

OnTimeout updates the congestion window size from the connection timeout.

type EntryWrapper 

type EntryWrapper[T any] struct {
	// contains filtered or unexported fields
}

EntryWrapper is an element marked as present or not.

type LostPacketInfo 

type LostPacketInfo struct {
	PacketNumber int64
	BytesLost    int64
}

func (LostPacketInfo) String 

func (i LostPacketInfo) String() string

type Pacer 

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

Pacer limits the speed of sending packets. Pacer is not thread safe. The caller should provide synchronization to avoid race condition.

func NewPacer 

func NewPacer(initialBudget, maxBudget, minPacingRate int64) *Pacer

NewPacer returns a new Pacer object.

func (*Pacer) Budget 

func (p *Pacer) Budget(now time.Time, pacingRate int64) int64

Budget returns the maximum number of bytes can be sent right now.

func (*Pacer) CanSend 

func (p *Pacer) CanSend(now time.Time, bytes, pacingRate int64) bool

CanSend returns true if a packet can be sent based on the given pacing rate.

func (*Pacer) OnPacketSent 

func (p *Pacer) OnPacketSent(sentTime time.Time, bytes, pacingRate int64)

OnPacketSent updates the budget and time when a packet is sent.

type PacketNumberIndexedQueue 

type PacketNumberIndexedQueue[T any] struct {
	// contains filtered or unexported fields
}

PacketNumberIndexedQueue is a queue of mostly continuous numbered entries which supports the following operations: - adding elements to the end of the queue, or at some point past the end - removing elements in any order - retrieving elements If all elements are inserted in order, all of the operations above are amortized O(1) time.

Internally, the data structure is a deque where each element is marked as present or not. The deque starts at the lowest present index. Whenever an element is removed, it's marked as not present, and the front of the deque is cleared of elements that are not present.

The tail of the queue is not cleared due to the assumption of entries being inserted in order, though removing all elements of the queue will return it to its initial state.

Note that this data structure is inherently hazardous, since an addition of just two entries will cause it to consume all of the memory available. Because of that, it is not a general-purpose container and should not be used as one.

func NewPacketNumberIndexedQueue 

func NewPacketNumberIndexedQueue[T any]() *PacketNumberIndexedQueue[T]

func (*PacketNumberIndexedQueue[T]) Emplace 

func (p *PacketNumberIndexedQueue[T]) Emplace(packetNumber int64, args T) bool

Emplace inserts data associated packetNumber into (or past) the end of the queue, filling up the missing intermediate entries as necessary. Returns true if the element has been inserted successfully, false if it was already in the queue or inserted out of order.

func (*PacketNumberIndexedQueue[T]) FirstPacket 

func (p *PacketNumberIndexedQueue[T]) FirstPacket() int64

func (*PacketNumberIndexedQueue[T]) GetEntry 

func (p *PacketNumberIndexedQueue[T]) GetEntry(packetNumber int64) *T

GetEntry retrieves the entry associated with the packet number. Returns the pointer to the entry in case of success, or nil if the entry does not exist.

func (*PacketNumberIndexedQueue[T]) IsEmpty 

func (p *PacketNumberIndexedQueue[T]) IsEmpty() bool

func (*PacketNumberIndexedQueue[T]) LastPacket 

func (p *PacketNumberIndexedQueue[T]) LastPacket() int64

func (*PacketNumberIndexedQueue[T]) Remove 

func (p *PacketNumberIndexedQueue[T]) Remove(packetNumber int64) bool

Remove removes data associated with packetNumber and frees the slots in the queue as necessary.

type RTTStats 

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

RTTStats provides round-trip statistics

func NewRTTStats 

func NewRTTStats() *RTTStats

NewRTTStats makes a properly initialized RTTStats object

func (*RTTStats) ExpireSmoothedMetrics 

func (r *RTTStats) ExpireSmoothedMetrics()

ExpireSmoothedMetrics causes the smoothed_rtt to be increased to the latest_rtt if the latest_rtt is larger. The mean deviation is increased to the most recent deviation if it's larger.

func (*RTTStats) LatestRTT 

func (r *RTTStats) LatestRTT() time.Duration

LatestRTT returns the most recent rtt measurement. May return Zero if no valid updates have occurred.

func (*RTTStats) MaxAckDelay 

func (r *RTTStats) MaxAckDelay() time.Duration

MaxAckDelay gets the max_ack_delay advertised by the peer

func (*RTTStats) MeanDeviation 

func (r *RTTStats) MeanDeviation() time.Duration

MeanDeviation gets the mean deviation

func (*RTTStats) MinRTT 

func (r *RTTStats) MinRTT() time.Duration

MinRTT Returns the minRTT for the entire connection. May return Zero if no valid updates have occurred.

func (*RTTStats) RTO 

func (r *RTTStats) RTO() time.Duration

RTO gets the retransmission timeout.

func (*RTTStats) Reset 

func (r *RTTStats) Reset()

Reset is called when connection migrates and rtt measurement needs to be reset.

func (*RTTStats) SetInitialRTT 

func (r *RTTStats) SetInitialRTT(t time.Duration)

SetInitialRTT sets the initial RTT. It is used during the 0-RTT handshake when restoring the RTT stats from the session state.

func (*RTTStats) SetMaxAckDelay 

func (r *RTTStats) SetMaxAckDelay(mad time.Duration)

SetMaxAckDelay sets the max_ack_delay

func (*RTTStats) SetRTOMultiplier 

func (r *RTTStats) SetRTOMultiplier(n float64)

SetRTOMultiplier sets the retransmission timeout multiplier.

func (*RTTStats) SmoothedRTT 

func (r *RTTStats) SmoothedRTT() time.Duration

SmoothedRTT returns the smoothed RTT for the connection. May return Zero if no valid updates have occurred.

func (*RTTStats) UpdateRTT 

func (r *RTTStats) UpdateRTT(sample time.Duration)

UpdateRTT updates the RTT based on a new sample.

type Sample 

type Sample[V mathext.Number] struct {
	// contains filtered or unexported fields
}

Sample represents a sample with a value and a timestamp.

type WindowedFilter 

type WindowedFilter[V mathext.Number] struct {
	// contains filtered or unexported fields
}

WindowedFilter implements a windowed filter algorithm for tracking the minimum (or maximum) estimate of a stream of samples over some fixed time interval.

func NewWindowedFilter 

func NewWindowedFilter[V mathext.Number](windowLength int64, zeroValue V, compare func(V, V) int) *WindowedFilter[V]

NewWindowedFilter initializes a new WindowedFilter.

func (*WindowedFilter[T]) GetBest 

func (wf *WindowedFilter[T]) GetBest() T

GetBest returns the best estimate.

func (*WindowedFilter[T]) GetSecondBest 

func (wf *WindowedFilter[T]) GetSecondBest() T

GetSecondBest returns the second best estimate.

func (*WindowedFilter[T]) GetThirdBest 

func (wf *WindowedFilter[T]) GetThirdBest() T

GetThirdBest returns the third best estimate.

func (*WindowedFilter[T]) Reset 

func (wf *WindowedFilter[T]) Reset(newSample T, newTime int64)

Reset resets all estimates to new sample.

func (*WindowedFilter[V]) SetWindowLength 

func (wf *WindowedFilter[V]) SetWindowLength(windowLength int64)

SetWindowLength changes the window length. Does not update any current samples.

func (*WindowedFilter[V]) Update 

func (wf *WindowedFilter[V]) Update(newSample V, newTime int64)

Update updates best estimates with newSample, and expires and updates best estimates as necessary.

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.