1package coordinate 2 3import ( 4 "math" 5 "math/rand" 6 "time" 7) 8 9// Coordinate is a specialized structure for holding network coordinates for the 10// Vivaldi-based coordinate mapping algorithm. All of the fields should be public 11// to enable this to be serialized. All values in here are in units of seconds. 12type Coordinate struct { 13 // Vec is the Euclidean portion of the coordinate. This is used along 14 // with the other fields to provide an overall distance estimate. The 15 // units here are seconds. 16 Vec []float64 17 18 // Err reflects the confidence in the given coordinate and is updated 19 // dynamically by the Vivaldi Client. This is dimensionless. 20 Error float64 21 22 // Adjustment is a distance offset computed based on a calculation over 23 // observations from all other nodes over a fixed window and is updated 24 // dynamically by the Vivaldi Client. The units here are seconds. 25 Adjustment float64 26 27 // Height is a distance offset that accounts for non-Euclidean effects 28 // which model the access links from nodes to the core Internet. The access 29 // links are usually set by bandwidth and congestion, and the core links 30 // usually follow distance based on geography. 31 Height float64 32} 33 34const ( 35 // secondsToNanoseconds is used to convert float seconds to nanoseconds. 36 secondsToNanoseconds = 1.0e9 37 38 // zeroThreshold is used to decide if two coordinates are on top of each 39 // other. 40 zeroThreshold = 1.0e-6 41) 42 43// ErrDimensionalityConflict will be panic-d if you try to perform operations 44// with incompatible dimensions. 45type DimensionalityConflictError struct{} 46 47// Adds the error interface. 48func (e DimensionalityConflictError) Error() string { 49 return "coordinate dimensionality does not match" 50} 51 52// NewCoordinate creates a new coordinate at the origin, using the given config 53// to supply key initial values. 54func NewCoordinate(config *Config) *Coordinate { 55 return &Coordinate{ 56 Vec: make([]float64, config.Dimensionality), 57 Error: config.VivaldiErrorMax, 58 Adjustment: 0.0, 59 Height: config.HeightMin, 60 } 61} 62 63// Clone creates an independent copy of this coordinate. 64func (c *Coordinate) Clone() *Coordinate { 65 vec := make([]float64, len(c.Vec)) 66 copy(vec, c.Vec) 67 return &Coordinate{ 68 Vec: vec, 69 Error: c.Error, 70 Adjustment: c.Adjustment, 71 Height: c.Height, 72 } 73} 74 75// IsCompatibleWith checks to see if the two coordinates are compatible 76// dimensionally. If this returns true then you are guaranteed to not get 77// any runtime errors operating on them. 78func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool { 79 return len(c.Vec) == len(other.Vec) 80} 81 82// ApplyForce returns the result of applying the force from the direction of the 83// other coordinate. 84func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate { 85 if !c.IsCompatibleWith(other) { 86 panic(DimensionalityConflictError{}) 87 } 88 89 ret := c.Clone() 90 unit, mag := unitVectorAt(c.Vec, other.Vec) 91 ret.Vec = add(ret.Vec, mul(unit, force)) 92 if mag > zeroThreshold { 93 ret.Height = (ret.Height+other.Height)*force/mag + ret.Height 94 ret.Height = math.Max(ret.Height, config.HeightMin) 95 } 96 return ret 97} 98 99// DistanceTo returns the distance between this coordinate and the other 100// coordinate, including adjustments. 101func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration { 102 if !c.IsCompatibleWith(other) { 103 panic(DimensionalityConflictError{}) 104 } 105 106 dist := c.rawDistanceTo(other) 107 adjustedDist := dist + c.Adjustment + other.Adjustment 108 if adjustedDist > 0.0 { 109 dist = adjustedDist 110 } 111 return time.Duration(dist * secondsToNanoseconds) 112} 113 114// rawDistanceTo returns the Vivaldi distance between this coordinate and the 115// other coordinate in seconds, not including adjustments. This assumes the 116// dimensions have already been checked to be compatible. 117func (c *Coordinate) rawDistanceTo(other *Coordinate) float64 { 118 return magnitude(diff(c.Vec, other.Vec)) + c.Height + other.Height 119} 120 121// add returns the sum of vec1 and vec2. This assumes the dimensions have 122// already been checked to be compatible. 123func add(vec1 []float64, vec2 []float64) []float64 { 124 ret := make([]float64, len(vec1)) 125 for i, _ := range ret { 126 ret[i] = vec1[i] + vec2[i] 127 } 128 return ret 129} 130 131// diff returns the difference between the vec1 and vec2. This assumes the 132// dimensions have already been checked to be compatible. 133func diff(vec1 []float64, vec2 []float64) []float64 { 134 ret := make([]float64, len(vec1)) 135 for i, _ := range ret { 136 ret[i] = vec1[i] - vec2[i] 137 } 138 return ret 139} 140 141// mul returns vec multiplied by a scalar factor. 142func mul(vec []float64, factor float64) []float64 { 143 ret := make([]float64, len(vec)) 144 for i, _ := range vec { 145 ret[i] = vec[i] * factor 146 } 147 return ret 148} 149 150// magnitude computes the magnitude of the vec. 151func magnitude(vec []float64) float64 { 152 sum := 0.0 153 for i, _ := range vec { 154 sum += vec[i] * vec[i] 155 } 156 return math.Sqrt(sum) 157} 158 159// unitVectorAt returns a unit vector pointing at vec1 from vec2. If the two 160// positions are the same then a random unit vector is returned. We also return 161// the distance between the points for use in the later height calculation. 162func unitVectorAt(vec1 []float64, vec2 []float64) ([]float64, float64) { 163 ret := diff(vec1, vec2) 164 165 // If the coordinates aren't on top of each other we can normalize. 166 if mag := magnitude(ret); mag > zeroThreshold { 167 return mul(ret, 1.0/mag), mag 168 } 169 170 // Otherwise, just return a random unit vector. 171 for i, _ := range ret { 172 ret[i] = rand.Float64() - 0.5 173 } 174 if mag := magnitude(ret); mag > zeroThreshold { 175 return mul(ret, 1.0/mag), 0.0 176 } 177 178 // And finally just give up and make a unit vector along the first 179 // dimension. This should be exceedingly rare. 180 ret = make([]float64, len(ret)) 181 ret[0] = 1.0 182 return ret, 0.0 183} 184