rto

Documentation

Overview

rto implements adaptive timeout algorithm used in TCP retransmission timeout.

Index

• Constants
• Variables
• func DefaultOnIntervalHandler(*AdaptoRTOProvider)
• func GetTimeout(ctx context.Context, config Config) (timeout time.Duration, rttCh chan<- RttSignal, err error)
• func StateAsString(state RTOProviderState) string
• type AdaptoRTOProvider
  • func NewAdaptoRTOProvider(config Config) *AdaptoRTOProvider
  • func (arp *AdaptoRTOProvider) CapacityEstimate() int64
  • func (arp *AdaptoRTOProvider) ComputeNewRTO(rtt time.Duration) time.Duration
  • func (arp *AdaptoRTOProvider) NewTimeout(ctx context.Context) (timeout time.Duration, rttCh chan<- RttSignal, err error)
  • func (arp *AdaptoRTOProvider) OnInterval()
  • func (arp *AdaptoRTOProvider) OnRtt(signal RttSignal)
  • func (arp *AdaptoRTOProvider) StartWithSLO()
• type Config
  • func (c *Config) Validate() *ConfigValidationError
• type ConfigValidationError
  • func (c ConfigValidationError) Error() string
• type OverloadDetectionTiming
• type RTOProviderState
• type RttSignal
• type SignalType

Constants

const (
	// Configurable parameters
	DEFAULT_K_MARGIN                  int64                   = 1
	DEFAULT_INTERVAL                  time.Duration           = 5 * time.Second
	DEFAULT_OVERLOAD_DETECTION_TIMING OverloadDetectionTiming = MaxTimeoutGenerated

	// Constant parameters. Alpha and Beta for Retransmission Timeout
	// Defined by  V. Jacobson, “Congestion avoidance and control,” SIGCOMM Comput.Commun.
	ALPHA_SCALING int64 = 8
	LOG2_ALPHA    int64 = 3
	BETA_SCALING  int64 = 4
	LOG2_BETA     int64 = 2

	// Tunable parameters
	// The values set for these constant leaves room for tuning
	SLO_SAFETY_MARGIN                float64 = 0.5 // safety margin of 0.5 or division by 2
	MIN_FAILED_SAMPLES               float64 = 1   // minimum failed samples reqruired to compute failure rate
	LOG2_PACING_GAIN                 int64   = 5   // used as pacing gain factor. 1+ 1 >> LOG2_PACING_GAIN
	DEFAULT_OVERLOAD_DRAIN_INTERVALS uint64  = 2   // intervals to choke rto after overload.
	DEFAULT_STARTUP_INTERVALS        uint64  = 4   // intervals to wait for the kMargin to stabilize
)

Variables

var AdaptoRTOProviders map[string]*AdaptoRTOProvider

var RequestRateLimitExceeded error = requestRateLimitExceeded{}

Functions

func DefaultOnIntervalHandler

func DefaultOnIntervalHandler(*AdaptoRTOProvider)

func GetTimeout

func GetTimeout(ctx context.Context, config Config) (timeout time.Duration, rttCh chan<- RttSignal, err error)

GetTimeout retrieves timeout value using provider with given id in config. if no provider with matching id is found, creates a new provider

func StateAsString

func StateAsString(state RTOProviderState) string

Types

type AdaptoRTOProvider

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

func NewAdaptoRTOProvider

func NewAdaptoRTOProvider(config Config) *AdaptoRTOProvider

func (*AdaptoRTOProvider) CapacityEstimate

func (arp *AdaptoRTOProvider) CapacityEstimate() int64

CapacityEstimate returns current overload estimate

func (*AdaptoRTOProvider) ComputeNewRTO

func (arp *AdaptoRTOProvider) ComputeNewRTO(rtt time.Duration) time.Duration

ComputeNewRTO computes new rto based on new rtt new timeout value is returned and can be used to set timeouts or overload detection MUST be called in thread safe manner as it does not lock mu

func (*AdaptoRTOProvider) NewTimeout

func (arp *AdaptoRTOProvider) NewTimeout(ctx context.Context) (timeout time.Duration, rttCh chan<- RttSignal, err error)

NewTimeout returns the current timeout value pseudo client queue / rate limiting suspends timeout creation during overload

func (*AdaptoRTOProvider) OnInterval

func (arp *AdaptoRTOProvider) OnInterval()

OnInterval calculates failure rate and adjusts margin failure rate for the interval is computed only if there were enough samples. if not interval exits. first failure rate for the current interval is computed, then smoothed mean failure rate if the main state machine is in NORMAL state:

• if failure rate is higher than the sloFailureRateAdjusted, kMargin is incremented
• if smoothed failure rate is lower than the sloFailureRateAdjusted, kMargin is decremented

if the main state machine is in OVERLOAD state:

• kMargin is not updated no matter the failure rate
• return immediately if in draining stage.
• if dropped is 0, reset overloadThresholdReq, and set main state to NORMAL
• otherwise check if the failure rate excluding dropped is withing the SLO.
• if yes, attempt to grow the threshold, and increase sending rate
• if not, shrink the threshold

NOTE: this should be the only way margin is mutated NOTE: the state transition NORMAL -> OVERLOAD is not handled here

func (*AdaptoRTOProvider) OnRtt

func (arp *AdaptoRTOProvider) OnRtt(signal RttSignal)

OnRtt handles new rtt event increments counter if max timeout is breached, declares overload for new rtt else computes the new timeout for the rtt MUST be called in thread safe manner as it does not lock mu

func (*AdaptoRTOProvider) StartWithSLO

func (arp *AdaptoRTOProvider) StartWithSLO()

StartWithSLO starts the provider by spawning a goroutine that waits for new rtt or timeout event and updates the timeout value accordingly. timeout calculations are also adjusted to meet the SLO

type Config

type Config struct {
	Id             string
	SLOLatency     time.Duration // max timeout value allowed
	Min            time.Duration // min timeout value allowed
	SLOFailureRate float64       // target failure rate SLO
	Interval       time.Duration // interval for failure rate calculations
	/* KMargin                 int64                    // starting kMargin for with SLO and static kMargin for without SLO */
	OverloadDetectionTiming OverloadDetectionTiming  // timing when to check for overload
	OverloadDrainIntervals  uint64                   // number of intervals to drain overloading requests
	OnIntervalHandler       func(*AdaptoRTOProvider) // handler to be called at the end of every interval

	Logger logger.Logger // optional logger
}

func (*Config) Validate

func (c *Config) Validate() *ConfigValidationError

type ConfigValidationError

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

func (ConfigValidationError) Error

func (c ConfigValidationError) Error() string

type OverloadDetectionTiming

type OverloadDetectionTiming = string

const (
	MaxTimeoutGenerated OverloadDetectionTiming = "maxTimeoutGenerated"
	MaxTimeoutExceeded  OverloadDetectionTiming = "maxTimeoutExceeded"
)

type RTOProviderState

type RTOProviderState = int64

State enum for main state machine

const (
	CRUISE RTOProviderState = iota
	STARTUP
	DRAIN
	OVERLOAD
	FAILURE
)

state transition will be STARTUP -> CRUISE -> DRAIN <-> OVERLOAD <-> FAILURE OVERLOAD -> CRUISE

type RttSignal

type RttSignal struct {
	Duration time.Duration
	Type     SignalType
}

RttSignal is used for reporting rtt.

type SignalType

type SignalType = int64

const (
	Successful SignalType = iota
	// GenericError should be used to signal non-timeout errors.
	// this only counts the failed but do not record rtt
	GenericError
	TimeoutError
)