README
¶
TODO - I'll beef this up as I implement each of the enhancements.
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
- type Config
- type Coordinate
- type DimensionalityConflictError
- type Stats
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GenerateCircle ¶
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 ¶
GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional grid with the given spacing between them.
func GenerateLine ¶
GenerateLine returns a truth matrix as if all the nodes are in a straight linke with the given spacing between them.
func GenerateRandom ¶
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 ¶
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 ¶
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 ¶
GenerateClients returns a slice with nodes number of clients, all with the given config.
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 ¶
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)
SetCoordinate forces the client's coordinate to a known state.
func (*Client) Update ¶
func (c *Client) Update(node string, other *Coordinate, rtt time.Duration) *Coordinate
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 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 4 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.
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.
Source Files