rto

Documentation

Overview

rto implements adaptive timeout algorithm used in TCP retransmission timeout.

rto implements adaptive timeout algorithm used in TCP retransmission timeout.

Index

• Constants
• Variables
• func DefaultOnIntervalHandler(AdaptoRTOProviderInterface)
• 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()
  • func (arp *AdaptoRTOProvider) State() string
• type AdaptoRTOProviderInterface
• type AdaptoRTOWCQProvider
  • func NewAdaptoRTOWCQProvider(config Config) *AdaptoRTOWCQProvider
  • func (arp *AdaptoRTOWCQProvider) CapacityEstimate() int64
  • func (arp *AdaptoRTOWCQProvider) ComputeNewRTO(rtt time.Duration) time.Duration
  • func (arp *AdaptoRTOWCQProvider) NewTimeout(ctx context.Context) (timeout time.Duration, rttCh chan<- RttSignal, err error)
  • func (arp *AdaptoRTOWCQProvider) OnInterval()
  • func (arp *AdaptoRTOWCQProvider) OnRtt(signal RttSignal)
  • func (arp *AdaptoRTOWCQProvider) StartWithSLO()
  • func (arp *AdaptoRTOWCQProvider) State() string
• type Config
  • func (c *Config) Validate() *ConfigValidationError
• type ConfigValidationError
  • func (c ConfigValidationError) Error() string
• type OverloadDetectionTiming
• type RTOProviderState
• type RTOWCQProviderState
• 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 AdaptoRTOWCQProviders map[string]*AdaptoRTOWCQProvider

var RequestRateLimitExceeded error = requestRateLimitExceeded{}

Functions

func DefaultOnIntervalHandler

func DefaultOnIntervalHandler(AdaptoRTOProviderInterface)

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 If not called in onIntervalHandler, must acquire lock first

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 MUST be called with mu.Lock already acquired

func (*AdaptoRTOProvider) OnRtt

func (arp *AdaptoRTOProvider) OnRtt(signal RttSignal)

OnRtt handles new rtt event 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

func (*AdaptoRTOProvider) State

func (arp *AdaptoRTOProvider) State() string

State returns current state If not called in onIntervalHandler, must acquire lock first

type AdaptoRTOProviderInterface

type AdaptoRTOProviderInterface interface {
	NewTimeout(ctx context.Context) (timeout time.Duration, rttCh chan<- RttSignal, err error)
	CapacityEstimate() int64
	State() string
}

type AdaptoRTOWCQProvider

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

func NewAdaptoRTOWCQProvider

func NewAdaptoRTOWCQProvider(config Config) *AdaptoRTOWCQProvider

func (*AdaptoRTOWCQProvider) CapacityEstimate

func (arp *AdaptoRTOWCQProvider) CapacityEstimate() int64

CapacityEstimate returns current overload estimate If not called in onIntervalHandler, must acquire lock first

func (*AdaptoRTOWCQProvider) ComputeNewRTO

func (arp *AdaptoRTOWCQProvider) 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 (*AdaptoRTOWCQProvider) NewTimeout

func (arp *AdaptoRTOWCQProvider) 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 (*AdaptoRTOWCQProvider) OnInterval

func (arp *AdaptoRTOWCQProvider) OnInterval()

OnInterval calculates failure rate and adjusts margin MUST be called with mu.Lock already acquired

func (*AdaptoRTOWCQProvider) OnRtt

func (arp *AdaptoRTOWCQProvider) OnRtt(signal RttSignal)

OnRtt handles new rtt event MUST be called in thread safe manner as it does not lock mu

func (*AdaptoRTOWCQProvider) StartWithSLO

func (arp *AdaptoRTOWCQProvider) 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

func (*AdaptoRTOWCQProvider) State

func (arp *AdaptoRTOWCQProvider) State() string

State returns current state If not called in onIntervalHandler, must acquire lock first

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(AdaptoRTOProviderInterface) // handler to be called at the end of every interval
	DisableClientQueuing    bool                             //flag for feature gating client queuing

	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 RTOWCQProviderState

type RTOWCQProviderState = int64

const (
	WCQ_CRUISE RTOWCQProviderState = iota
	WCQ_STARTUP
	WCQ_DRAIN
)

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
)