VOL-1867 move simulated olt from voltha-go to voltha-simolt-adapter
Sourced from voltha-go commit 251a11c0ffe60512318a644cd6ce0dc4e12f4018
Change-Id: I8e7ee4da1fed739b3c461917301d2729a79307f5
diff --git a/vendor/github.com/hashicorp/serf/coordinate/client.go b/vendor/github.com/hashicorp/serf/coordinate/client.go
new file mode 100644
index 0000000..3582ee4
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/client.go
@@ -0,0 +1,243 @@
+package coordinate
+
+import (
+ "fmt"
+ "math"
+ "sort"
+ "sync"
+ "time"
+
+ "github.com/armon/go-metrics"
+)
+
+// 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.
+type Client struct {
+ // coord is the current estimate of the client's network coordinate.
+ coord *Coordinate
+
+ // origin is a coordinate sitting at the origin.
+ origin *Coordinate
+
+ // config contains the tuning parameters that govern the performance of
+ // the algorithm.
+ config *Config
+
+ // adjustmentIndex is the current index into the adjustmentSamples slice.
+ adjustmentIndex uint
+
+ // adjustment is used to store samples for the adjustment calculation.
+ adjustmentSamples []float64
+
+ // latencyFilterSamples is used to store the last several RTT samples,
+ // keyed by node name. We will use the config's LatencyFilterSamples
+ // value to determine how many samples we keep, per node.
+ latencyFilterSamples map[string][]float64
+
+ // stats is used to record events that occur when updating coordinates.
+ stats ClientStats
+
+ // mutex enables safe concurrent access to the client.
+ mutex sync.RWMutex
+}
+
+// ClientStats is used to record events that occur when updating coordinates.
+type ClientStats struct {
+ // Resets is incremented any time we reset our local coordinate because
+ // our calculations have resulted in an invalid state.
+ Resets int
+}
+
+// NewClient creates a new Client and verifies the configuration is valid.
+func NewClient(config *Config) (*Client, error) {
+ if !(config.Dimensionality > 0) {
+ return nil, fmt.Errorf("dimensionality must be >0")
+ }
+
+ return &Client{
+ coord: NewCoordinate(config),
+ origin: NewCoordinate(config),
+ config: config,
+ adjustmentIndex: 0,
+ adjustmentSamples: make([]float64, config.AdjustmentWindowSize),
+ latencyFilterSamples: make(map[string][]float64),
+ }, nil
+}
+
+// GetCoordinate returns a copy of the coordinate for this client.
+func (c *Client) GetCoordinate() *Coordinate {
+ c.mutex.RLock()
+ defer c.mutex.RUnlock()
+
+ return c.coord.Clone()
+}
+
+// SetCoordinate forces the client's coordinate to a known state.
+func (c *Client) SetCoordinate(coord *Coordinate) error {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ if err := c.checkCoordinate(coord); err != nil {
+ return err
+ }
+
+ c.coord = coord.Clone()
+ return nil
+}
+
+// ForgetNode removes any client state for the given node.
+func (c *Client) ForgetNode(node string) {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ delete(c.latencyFilterSamples, node)
+}
+
+// Stats returns a copy of stats for the client.
+func (c *Client) Stats() ClientStats {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ return c.stats
+}
+
+// checkCoordinate returns an error if the coordinate isn't compatible with
+// this client, or if the coordinate itself isn't valid. This assumes the mutex
+// has been locked already.
+func (c *Client) checkCoordinate(coord *Coordinate) error {
+ if !c.coord.IsCompatibleWith(coord) {
+ return fmt.Errorf("dimensions aren't compatible")
+ }
+
+ if !coord.IsValid() {
+ return fmt.Errorf("coordinate is invalid")
+ }
+
+ return nil
+}
+
+// latencyFilter applies a simple moving median filter with a new sample for
+// a node. This assumes that the mutex has been locked already.
+func (c *Client) latencyFilter(node string, rttSeconds float64) float64 {
+ samples, ok := c.latencyFilterSamples[node]
+ if !ok {
+ samples = make([]float64, 0, c.config.LatencyFilterSize)
+ }
+
+ // Add the new sample and trim the list, if needed.
+ samples = append(samples, rttSeconds)
+ if len(samples) > int(c.config.LatencyFilterSize) {
+ samples = samples[1:]
+ }
+ c.latencyFilterSamples[node] = samples
+
+ // Sort a copy of the samples and return the median.
+ sorted := make([]float64, len(samples))
+ copy(sorted, samples)
+ sort.Float64s(sorted)
+ return sorted[len(sorted)/2]
+}
+
+// updateVivialdi updates the Vivaldi portion of the client's coordinate. This
+// assumes that the mutex has been locked already.
+func (c *Client) updateVivaldi(other *Coordinate, rttSeconds float64) {
+ const zeroThreshold = 1.0e-6
+
+ dist := c.coord.DistanceTo(other).Seconds()
+ if rttSeconds < zeroThreshold {
+ rttSeconds = zeroThreshold
+ }
+ wrongness := math.Abs(dist-rttSeconds) / rttSeconds
+
+ totalError := c.coord.Error + other.Error
+ if totalError < zeroThreshold {
+ totalError = zeroThreshold
+ }
+ weight := c.coord.Error / totalError
+
+ c.coord.Error = c.config.VivaldiCE*weight*wrongness + c.coord.Error*(1.0-c.config.VivaldiCE*weight)
+ if c.coord.Error > c.config.VivaldiErrorMax {
+ c.coord.Error = c.config.VivaldiErrorMax
+ }
+
+ delta := c.config.VivaldiCC * weight
+ force := delta * (rttSeconds - dist)
+ c.coord = c.coord.ApplyForce(c.config, force, other)
+}
+
+// updateAdjustment updates the adjustment portion of the client's coordinate, if
+// the feature is enabled. This assumes that the mutex has been locked already.
+func (c *Client) updateAdjustment(other *Coordinate, rttSeconds float64) {
+ if c.config.AdjustmentWindowSize == 0 {
+ return
+ }
+
+ // Note that the existing adjustment factors don't figure in to this
+ // calculation so we use the raw distance here.
+ dist := c.coord.rawDistanceTo(other)
+ c.adjustmentSamples[c.adjustmentIndex] = rttSeconds - dist
+ c.adjustmentIndex = (c.adjustmentIndex + 1) % c.config.AdjustmentWindowSize
+
+ sum := 0.0
+ for _, sample := range c.adjustmentSamples {
+ sum += sample
+ }
+ c.coord.Adjustment = sum / (2.0 * float64(c.config.AdjustmentWindowSize))
+}
+
+// updateGravity applies a small amount of gravity to pull coordinates towards
+// the center of the coordinate system to combat drift. This assumes that the
+// mutex is locked already.
+func (c *Client) updateGravity() {
+ dist := c.origin.DistanceTo(c.coord).Seconds()
+ force := -1.0 * math.Pow(dist/c.config.GravityRho, 2.0)
+ c.coord = c.coord.ApplyForce(c.config, force, c.origin)
+}
+
+// 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.
+func (c *Client) Update(node string, other *Coordinate, rtt time.Duration) (*Coordinate, error) {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ if err := c.checkCoordinate(other); err != nil {
+ return nil, err
+ }
+
+ // The code down below can handle zero RTTs, which we have seen in
+ // https://github.com/hashicorp/consul/issues/3789, presumably in
+ // environments with coarse-grained monotonic clocks (we are still
+ // trying to pin this down). In any event, this is ok from a code PoV
+ // so we don't need to alert operators with spammy messages. We did
+ // add a counter so this is still observable, though.
+ const maxRTT = 10 * time.Second
+ if rtt < 0 || rtt > maxRTT {
+ return nil, fmt.Errorf("round trip time not in valid range, duration %v is not a positive value less than %v ", rtt, maxRTT)
+ }
+ if rtt == 0 {
+ metrics.IncrCounter([]string{"serf", "coordinate", "zero-rtt"}, 1)
+ }
+
+ rttSeconds := c.latencyFilter(node, rtt.Seconds())
+ c.updateVivaldi(other, rttSeconds)
+ c.updateAdjustment(other, rttSeconds)
+ c.updateGravity()
+ if !c.coord.IsValid() {
+ c.stats.Resets++
+ c.coord = NewCoordinate(c.config)
+ }
+
+ return c.coord.Clone(), nil
+}
+
+// DistanceTo returns the estimated RTT from the client's coordinate to other, the
+// coordinate for another node.
+func (c *Client) DistanceTo(other *Coordinate) time.Duration {
+ c.mutex.RLock()
+ defer c.mutex.RUnlock()
+
+ return c.coord.DistanceTo(other)
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/config.go b/vendor/github.com/hashicorp/serf/coordinate/config.go
new file mode 100644
index 0000000..b85a8ab
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/config.go
@@ -0,0 +1,70 @@
+package coordinate
+
+// 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.
+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
+}
+
+// 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.
+func DefaultConfig() *Config {
+ return &Config{
+ Dimensionality: 8,
+ VivaldiErrorMax: 1.5,
+ VivaldiCE: 0.25,
+ VivaldiCC: 0.25,
+ AdjustmentWindowSize: 20,
+ HeightMin: 10.0e-6,
+ LatencyFilterSize: 3,
+ GravityRho: 150.0,
+ }
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/coordinate.go b/vendor/github.com/hashicorp/serf/coordinate/coordinate.go
new file mode 100644
index 0000000..fbe792c
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/coordinate.go
@@ -0,0 +1,203 @@
+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
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/phantom.go b/vendor/github.com/hashicorp/serf/coordinate/phantom.go
new file mode 100644
index 0000000..6fb033c
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/phantom.go
@@ -0,0 +1,187 @@
+package coordinate
+
+import (
+ "fmt"
+ "math"
+ "math/rand"
+ "time"
+)
+
+// GenerateClients returns a slice with nodes number of clients, all with the
+// given config.
+func GenerateClients(nodes int, config *Config) ([]*Client, error) {
+ clients := make([]*Client, nodes)
+ for i, _ := range clients {
+ client, err := NewClient(config)
+ if err != nil {
+ return nil, err
+ }
+
+ clients[i] = client
+ }
+ return clients, nil
+}
+
+// GenerateLine returns a truth matrix as if all the nodes are in a straight linke
+// with the given spacing between them.
+func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rtt := time.Duration(j-i) * spacing
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional
+// grid with the given spacing between them.
+func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ n := int(math.Sqrt(float64(nodes)))
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ x1, y1 := float64(i%n), float64(i/n)
+ x2, y2 := float64(j%n), float64(j/n)
+ dx, dy := x2-x1, y2-y1
+ dist := math.Sqrt(dx*dx + dy*dy)
+ rtt := time.Duration(dist * float64(spacing))
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// 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 GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ split := nodes / 2
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rtt := lan
+ if (i <= split && j > split) || (i > split && j <= split) {
+ rtt += wan
+ }
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// 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 GenerateCircle(nodes int, radius time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ var rtt time.Duration
+ if i == 0 {
+ rtt = 2 * radius
+ } else {
+ t1 := 2.0 * math.Pi * float64(i) / float64(nodes)
+ x1, y1 := math.Cos(t1), math.Sin(t1)
+ t2 := 2.0 * math.Pi * float64(j) / float64(nodes)
+ x2, y2 := math.Cos(t2), math.Sin(t2)
+ dx, dy := x2-x1, y2-y1
+ dist := math.Sqrt(dx*dx + dy*dy)
+ rtt = time.Duration(dist * float64(radius))
+ }
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// 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 GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration {
+ rand.Seed(1)
+
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rttSeconds := rand.NormFloat64()*deviation.Seconds() + mean.Seconds()
+ rtt := time.Duration(rttSeconds * secondsToNanoseconds)
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// 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).
+func Simulate(clients []*Client, truth [][]time.Duration, cycles int) {
+ rand.Seed(1)
+
+ nodes := len(clients)
+ for cycle := 0; cycle < cycles; cycle++ {
+ for i, _ := range clients {
+ if j := rand.Intn(nodes); j != i {
+ c := clients[j].GetCoordinate()
+ rtt := truth[i][j]
+ node := fmt.Sprintf("node_%d", j)
+ clients[i].Update(node, c, rtt)
+ }
+ }
+ }
+}
+
+// Stats is returned from the Evaluate function with a summary of the algorithm
+// performance.
+type Stats struct {
+ ErrorMax float64
+ ErrorAvg float64
+}
+
+// Evaluate uses the coordinates of the given clients to calculate estimated
+// distances and compares them with the given truth matrix, returning summary
+// stats.
+func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats) {
+ nodes := len(clients)
+ count := 0
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ est := clients[i].DistanceTo(clients[j].GetCoordinate()).Seconds()
+ actual := truth[i][j].Seconds()
+ error := math.Abs(est-actual) / actual
+ stats.ErrorMax = math.Max(stats.ErrorMax, error)
+ stats.ErrorAvg += error
+ count += 1
+ }
+ }
+
+ stats.ErrorAvg /= float64(count)
+ fmt.Printf("Error avg=%9.6f max=%9.6f\n", stats.ErrorAvg, stats.ErrorMax)
+ return
+}