coordinate

Documentation

Index

• func GenerateCircle(nodes int, radius time.Duration) [][]time.Duration
• func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration
• func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration
• func GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration
• func GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration
• func Simulate(clients []*Client, truth [][]time.Duration, cycles int)
• type Client
  • func GenerateClients(nodes int, config *Config) ([]*Client, error)
  • func NewClient(config *Config) (*Client, error)
  • func (c *Client) DistanceTo(other *Coordinate) time.Duration
  • func (c *Client) ForgetNode(node string)
  • func (c *Client) GetCoordinate() *Coordinate
  • func (c *Client) SetCoordinate(coord *Coordinate) error
  • func (c *Client) Stats() ClientStats
  • func (c *Client) Update(node string, other *Coordinate, rtt time.Duration) (*Coordinate, error)
• type ClientStats
• type Config
  • func DefaultConfig() *Config
• type Coordinate
  • func NewCoordinate(config *Config) *Coordinate
  • func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate
  • func (c *Coordinate) Clone() *Coordinate
  • func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration
  • func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool
  • func (c *Coordinate) IsValid() bool
• type DimensionalityConflictError
  • func (e DimensionalityConflictError) Error() string
• type Stats
  • func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats)

Functions

func GenerateCircle

func GenerateCircle(nodes int, radius time.Duration) [][]time.Duration

GenerateCircle returns a truth matrix for a set of nodes, evenly distributed around a circle with the given radius. The first node is at the "center" of the circle because it's equidistant from all the other nodes, but we place it at double the radius, so it should show up above all the other nodes in height.

func GenerateGrid

func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration

GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional grid with the given spacing between them.

func GenerateLine

func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration

GenerateLine returns a truth matrix as if all the nodes are in a straight linke with the given spacing between them.

func GenerateRandom

func GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration

GenerateRandom returns a truth matrix for a set of nodes with normally distributed delays, with the given mean and deviation. The RNG is re-seeded so you always get the same matrix for a given size.

func GenerateSplit

func GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration

GenerateSplit returns a truth matrix as if half the nodes are close together in one location and half the nodes are close together in another. The lan factor is used to separate the nodes locally and the wan factor represents the split between the two sides.

func Simulate

func Simulate(clients []*Client, truth [][]time.Duration, cycles int)

Simulate runs the given number of cycles using the given list of clients and truth matrix. On each cycle, each client will pick a random node and observe the truth RTT, updating its coordinate estimate. The RNG is re-seeded for each simulation run to get deterministic results (for this algorithm and the underlying algorithm which will use random numbers for position vectors when starting out with everything at the origin).

Types

type Client

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

Client manages the estimated network coordinate for a given node, and adjusts it as the node observes round trip times and estimated coordinates from other nodes. The core algorithm is based on Vivaldi, see the documentation for Config for more details.

func GenerateClients

func GenerateClients(nodes int, config *Config) ([]*Client, error)

GenerateClients returns a slice with nodes number of clients, all with the given config.

func NewClient

func NewClient(config *Config) (*Client, error)

NewClient creates a new Client and verifies the configuration is valid.

func (*Client) DistanceTo

func (c *Client) DistanceTo(other *Coordinate) time.Duration

DistanceTo returns the estimated RTT from the client's coordinate to other, the coordinate for another node.

func (*Client) ForgetNode

func (c *Client) ForgetNode(node string)

ForgetNode removes any client state for the given node.

func (*Client) GetCoordinate

func (c *Client) GetCoordinate() *Coordinate

GetCoordinate returns a copy of the coordinate for this client.

func (*Client) SetCoordinate

func (c *Client) SetCoordinate(coord *Coordinate) error

SetCoordinate forces the client's coordinate to a known state.

func (*Client) Stats

func (c *Client) Stats() ClientStats

Stats returns a copy of stats for the client.

func (*Client) Update

func (c *Client) Update(node string, other *Coordinate, rtt time.Duration) (*Coordinate, error)

Update takes other, a coordinate for another node, and rtt, a round trip time observation for a ping to that node, and updates the estimated position of the client's coordinate. Returns the updated coordinate.

type ClientStats

type ClientStats struct {
	// Resets is incremented any time we reset our local coordinate because
	// our calculations have resulted in an invalid state.
	Resets int
}

ClientStats is used to record events that occur when updating coordinates.

type Config

type Config struct {
	// The dimensionality of the coordinate system. As discussed in [2], more
	// dimensions improves the accuracy of the estimates up to a point. Per [2]
	// we chose 8 dimensions plus a non-Euclidean height.
	Dimensionality uint

	// VivaldiErrorMax is the default error value when a node hasn't yet made
	// any observations. It also serves as an upper limit on the error value in
	// case observations cause the error value to increase without bound.
	VivaldiErrorMax float64

	// VivaldiCE is a tuning factor that controls the maximum impact an
	// observation can have on a node's confidence. See [1] for more details.
	VivaldiCE float64

	// VivaldiCC is a tuning factor that controls the maximum impact an
	// observation can have on a node's coordinate. See [1] for more details.
	VivaldiCC float64

	// AdjustmentWindowSize is a tuning factor that determines how many samples
	// we retain to calculate the adjustment factor as discussed in [3]. Setting
	// this to zero disables this feature.
	AdjustmentWindowSize uint

	// HeightMin is the minimum value of the height parameter. Since this
	// always must be positive, it will introduce a small amount error, so
	// the chosen value should be relatively small compared to "normal"
	// coordinates.
	HeightMin float64

	// LatencyFilterSamples is the maximum number of samples that are retained
	// per node, in order to compute a median. The intent is to ride out blips
	// but still keep the delay low, since our time to probe any given node is
	// pretty infrequent. See [2] for more details.
	LatencyFilterSize uint

	// GravityRho is a tuning factor that sets how much gravity has an effect
	// to try to re-center coordinates. See [2] for more details.
	GravityRho float64
}

Config is used to set the parameters of the Vivaldi-based coordinate mapping algorithm.

The following references are called out at various points in the documentation here:

[1] Dabek, Frank, et al. "Vivaldi: A decentralized network coordinate system."

ACM SIGCOMM Computer Communication Review. Vol. 34. No. 4. ACM, 2004.

[2] Ledlie, Jonathan, Paul Gardner, and Margo I. Seltzer. "Network Coordinates

in the Wild." NSDI. Vol. 7. 2007.

[3] Lee, Sanghwan, et al. "On suitability of Euclidean embedding for

host-based network coordinate systems." Networking, IEEE/ACM Transactions
on 18.1 (2010): 27-40.

func DefaultConfig

func DefaultConfig() *Config

DefaultConfig returns a Config that has some default values suitable for basic testing of the algorithm, but not tuned to any particular type of cluster.

type Coordinate

type Coordinate struct {
	// Vec is the Euclidean portion of the coordinate. This is used along
	// with the other fields to provide an overall distance estimate. The
	// units here are seconds.
	Vec []float64

	// Err reflects the confidence in the given coordinate and is updated
	// dynamically by the Vivaldi Client. This is dimensionless.
	Error float64

	// Adjustment is a distance offset computed based on a calculation over
	// observations from all other nodes over a fixed window and is updated
	// dynamically by the Vivaldi Client. The units here are seconds.
	Adjustment float64

	// Height is a distance offset that accounts for non-Euclidean effects
	// which model the access links from nodes to the core Internet. The access
	// links are usually set by bandwidth and congestion, and the core links
	// usually follow distance based on geography.
	Height float64
}

Coordinate is a specialized structure for holding network coordinates for the Vivaldi-based coordinate mapping algorithm. All of the fields should be public to enable this to be serialized. All values in here are in units of seconds.

func NewCoordinate

func NewCoordinate(config *Config) *Coordinate

NewCoordinate creates a new coordinate at the origin, using the given config to supply key initial values.

func (*Coordinate) ApplyForce

func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate

ApplyForce returns the result of applying the force from the direction of the other coordinate.

func (*Coordinate) Clone

func (c *Coordinate) Clone() *Coordinate

Clone creates an independent copy of this coordinate.

func (*Coordinate) DistanceTo

func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration

DistanceTo returns the distance between this coordinate and the other coordinate, including adjustments.

func (*Coordinate) IsCompatibleWith

func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool

IsCompatibleWith checks to see if the two coordinates are compatible dimensionally. If this returns true then you are guaranteed to not get any runtime errors operating on them.

func (*Coordinate) IsValid

func (c *Coordinate) IsValid() bool

IsValid returns false if any component of a coordinate isn't valid, per the componentIsValid() helper above.

type DimensionalityConflictError

type DimensionalityConflictError struct{}

ErrDimensionalityConflict will be panic-d if you try to perform operations with incompatible dimensions.

func (DimensionalityConflictError) Error

func (e DimensionalityConflictError) Error() string

Adds the error interface.

type Stats

type Stats struct {
	ErrorMax float64
	ErrorAvg float64
}

Stats is returned from the Evaluate function with a summary of the algorithm performance.

func Evaluate

func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats)

Evaluate uses the coordinates of the given clients to calculate estimated distances and compares them with the given truth matrix, returning summary stats.