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// componentIsValid returns false if a floating point value is a NaN or an 76// infinity. 77func componentIsValid(f float64) bool { 78 return !math.IsInf(f, 0) && !math.IsNaN(f) 79} 80 81// IsValid returns false if any component of a coordinate isn't valid, per the 82// componentIsValid() helper above. 83func (c *Coordinate) IsValid() bool { 84 for i := range c.Vec { 85 if !componentIsValid(c.Vec[i]) { 86 return false 87 } 88 } 89 90 return componentIsValid(c.Error) && 91 componentIsValid(c.Adjustment) && 92 componentIsValid(c.Height) 93} 94 95// IsCompatibleWith checks to see if the two coordinates are compatible 96// dimensionally. If this returns true then you are guaranteed to not get 97// any runtime errors operating on them. 98func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool { 99 return len(c.Vec) == len(other.Vec) 100} 101 102// ApplyForce returns the result of applying the force from the direction of the 103// other coordinate. 104func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate { 105 if !c.IsCompatibleWith(other) { 106 panic(DimensionalityConflictError{}) 107 } 108 109 ret := c.Clone() 110 unit, mag := unitVectorAt(c.Vec, other.Vec) 111 ret.Vec = add(ret.Vec, mul(unit, force)) 112 if mag > zeroThreshold { 113 ret.Height = (ret.Height+other.Height)*force/mag + ret.Height 114 ret.Height = math.Max(ret.Height, config.HeightMin) 115 } 116 return ret 117} 118 119// DistanceTo returns the distance between this coordinate and the other 120// coordinate, including adjustments. 121func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration { 122 if !c.IsCompatibleWith(other) { 123 panic(DimensionalityConflictError{}) 124 } 125 126 dist := c.rawDistanceTo(other) 127 adjustedDist := dist + c.Adjustment + other.Adjustment 128 if adjustedDist > 0.0 { 129 dist = adjustedDist 130 } 131 return time.Duration(dist * secondsToNanoseconds) 132} 133 134// rawDistanceTo returns the Vivaldi distance between this coordinate and the 135// other coordinate in seconds, not including adjustments. This assumes the 136// dimensions have already been checked to be compatible. 137func (c *Coordinate) rawDistanceTo(other *Coordinate) float64 { 138 return magnitude(diff(c.Vec, other.Vec)) + c.Height + other.Height 139} 140 141// add returns the sum of vec1 and vec2. This assumes the dimensions have 142// already been checked to be compatible. 143func add(vec1 []float64, vec2 []float64) []float64 { 144 ret := make([]float64, len(vec1)) 145 for i := range ret { 146 ret[i] = vec1[i] + vec2[i] 147 } 148 return ret 149} 150 151// diff returns the difference between the vec1 and vec2. This assumes the 152// dimensions have already been checked to be compatible. 153func diff(vec1 []float64, vec2 []float64) []float64 { 154 ret := make([]float64, len(vec1)) 155 for i := range ret { 156 ret[i] = vec1[i] - vec2[i] 157 } 158 return ret 159} 160 161// mul returns vec multiplied by a scalar factor. 162func mul(vec []float64, factor float64) []float64 { 163 ret := make([]float64, len(vec)) 164 for i := range vec { 165 ret[i] = vec[i] * factor 166 } 167 return ret 168} 169 170// magnitude computes the magnitude of the vec. 171func magnitude(vec []float64) float64 { 172 sum := 0.0 173 for i := range vec { 174 sum += vec[i] * vec[i] 175 } 176 return math.Sqrt(sum) 177} 178 179// unitVectorAt returns a unit vector pointing at vec1 from vec2. If the two 180// positions are the same then a random unit vector is returned. We also return 181// the distance between the points for use in the later height calculation. 182func unitVectorAt(vec1 []float64, vec2 []float64) ([]float64, float64) { 183 ret := diff(vec1, vec2) 184 185 // If the coordinates aren't on top of each other we can normalize. 186 if mag := magnitude(ret); mag > zeroThreshold { 187 return mul(ret, 1.0/mag), mag 188 } 189 190 // Otherwise, just return a random unit vector. 191 for i := range ret { 192 ret[i] = rand.Float64() - 0.5 193 } 194 if mag := magnitude(ret); mag > zeroThreshold { 195 return mul(ret, 1.0/mag), 0.0 196 } 197 198 // And finally just give up and make a unit vector along the first 199 // dimension. This should be exceedingly rare. 200 ret = make([]float64, len(ret)) 201 ret[0] = 1.0 202 return ret, 0.0 203} 204