| package coordinate |
| |
| import ( |
| "math" |
| "math/rand" |
| "time" |
| ) |
| |
| // 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. |
| 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 |
| } |
| |
| const ( |
| // secondsToNanoseconds is used to convert float seconds to nanoseconds. |
| secondsToNanoseconds = 1.0e9 |
| |
| // zeroThreshold is used to decide if two coordinates are on top of each |
| // other. |
| zeroThreshold = 1.0e-6 |
| ) |
| |
| // ErrDimensionalityConflict will be panic-d if you try to perform operations |
| // with incompatible dimensions. |
| type DimensionalityConflictError struct{} |
| |
| // Adds the error interface. |
| func (e DimensionalityConflictError) Error() string { |
| return "coordinate dimensionality does not match" |
| } |
| |
| // NewCoordinate creates a new coordinate at the origin, using the given config |
| // to supply key initial values. |
| func NewCoordinate(config *Config) *Coordinate { |
| return &Coordinate{ |
| Vec: make([]float64, config.Dimensionality), |
| Error: config.VivaldiErrorMax, |
| Adjustment: 0.0, |
| Height: config.HeightMin, |
| } |
| } |
| |
| // Clone creates an independent copy of this coordinate. |
| func (c *Coordinate) Clone() *Coordinate { |
| vec := make([]float64, len(c.Vec)) |
| copy(vec, c.Vec) |
| return &Coordinate{ |
| Vec: vec, |
| Error: c.Error, |
| Adjustment: c.Adjustment, |
| Height: c.Height, |
| } |
| } |
| |
| // componentIsValid returns false if a floating point value is a NaN or an |
| // infinity. |
| func componentIsValid(f float64) bool { |
| return !math.IsInf(f, 0) && !math.IsNaN(f) |
| } |
| |
| // IsValid returns false if any component of a coordinate isn't valid, per the |
| // componentIsValid() helper above. |
| func (c *Coordinate) IsValid() bool { |
| for i := range c.Vec { |
| if !componentIsValid(c.Vec[i]) { |
| return false |
| } |
| } |
| |
| return componentIsValid(c.Error) && |
| componentIsValid(c.Adjustment) && |
| componentIsValid(c.Height) |
| } |
| |
| // 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 (c *Coordinate) IsCompatibleWith(other *Coordinate) bool { |
| return len(c.Vec) == len(other.Vec) |
| } |
| |
| // ApplyForce returns the result of applying the force from the direction of the |
| // other coordinate. |
| func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate { |
| if !c.IsCompatibleWith(other) { |
| panic(DimensionalityConflictError{}) |
| } |
| |
| ret := c.Clone() |
| unit, mag := unitVectorAt(c.Vec, other.Vec) |
| ret.Vec = add(ret.Vec, mul(unit, force)) |
| if mag > zeroThreshold { |
| ret.Height = (ret.Height+other.Height)*force/mag + ret.Height |
| ret.Height = math.Max(ret.Height, config.HeightMin) |
| } |
| return ret |
| } |
| |
| // DistanceTo returns the distance between this coordinate and the other |
| // coordinate, including adjustments. |
| func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration { |
| if !c.IsCompatibleWith(other) { |
| panic(DimensionalityConflictError{}) |
| } |
| |
| dist := c.rawDistanceTo(other) |
| adjustedDist := dist + c.Adjustment + other.Adjustment |
| if adjustedDist > 0.0 { |
| dist = adjustedDist |
| } |
| return time.Duration(dist * secondsToNanoseconds) |
| } |
| |
| // rawDistanceTo returns the Vivaldi distance between this coordinate and the |
| // other coordinate in seconds, not including adjustments. This assumes the |
| // dimensions have already been checked to be compatible. |
| func (c *Coordinate) rawDistanceTo(other *Coordinate) float64 { |
| return magnitude(diff(c.Vec, other.Vec)) + c.Height + other.Height |
| } |
| |
| // add returns the sum of vec1 and vec2. This assumes the dimensions have |
| // already been checked to be compatible. |
| func add(vec1 []float64, vec2 []float64) []float64 { |
| ret := make([]float64, len(vec1)) |
| for i := range ret { |
| ret[i] = vec1[i] + vec2[i] |
| } |
| return ret |
| } |
| |
| // diff returns the difference between the vec1 and vec2. This assumes the |
| // dimensions have already been checked to be compatible. |
| func diff(vec1 []float64, vec2 []float64) []float64 { |
| ret := make([]float64, len(vec1)) |
| for i := range ret { |
| ret[i] = vec1[i] - vec2[i] |
| } |
| return ret |
| } |
| |
| // mul returns vec multiplied by a scalar factor. |
| func mul(vec []float64, factor float64) []float64 { |
| ret := make([]float64, len(vec)) |
| for i := range vec { |
| ret[i] = vec[i] * factor |
| } |
| return ret |
| } |
| |
| // magnitude computes the magnitude of the vec. |
| func magnitude(vec []float64) float64 { |
| sum := 0.0 |
| for i := range vec { |
| sum += vec[i] * vec[i] |
| } |
| return math.Sqrt(sum) |
| } |
| |
| // unitVectorAt returns a unit vector pointing at vec1 from vec2. If the two |
| // positions are the same then a random unit vector is returned. We also return |
| // the distance between the points for use in the later height calculation. |
| func unitVectorAt(vec1 []float64, vec2 []float64) ([]float64, float64) { |
| ret := diff(vec1, vec2) |
| |
| // If the coordinates aren't on top of each other we can normalize. |
| if mag := magnitude(ret); mag > zeroThreshold { |
| return mul(ret, 1.0/mag), mag |
| } |
| |
| // Otherwise, just return a random unit vector. |
| for i := range ret { |
| ret[i] = rand.Float64() - 0.5 |
| } |
| if mag := magnitude(ret); mag > zeroThreshold { |
| return mul(ret, 1.0/mag), 0.0 |
| } |
| |
| // And finally just give up and make a unit vector along the first |
| // dimension. This should be exceedingly rare. |
| ret = make([]float64, len(ret)) |
| ret[0] = 1.0 |
| return ret, 0.0 |
| } |