| 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 |
| } |