khenaidoo | ac63710 | 2019-01-14 15:44:34 -0500 | [diff] [blame] | 1 | package coordinate |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "math" |
| 6 | "math/rand" |
| 7 | "time" |
| 8 | ) |
| 9 | |
| 10 | // GenerateClients returns a slice with nodes number of clients, all with the |
| 11 | // given config. |
| 12 | func GenerateClients(nodes int, config *Config) ([]*Client, error) { |
| 13 | clients := make([]*Client, nodes) |
| 14 | for i, _ := range clients { |
| 15 | client, err := NewClient(config) |
| 16 | if err != nil { |
| 17 | return nil, err |
| 18 | } |
| 19 | |
| 20 | clients[i] = client |
| 21 | } |
| 22 | return clients, nil |
| 23 | } |
| 24 | |
| 25 | // GenerateLine returns a truth matrix as if all the nodes are in a straight linke |
| 26 | // with the given spacing between them. |
| 27 | func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration { |
| 28 | truth := make([][]time.Duration, nodes) |
| 29 | for i := range truth { |
| 30 | truth[i] = make([]time.Duration, nodes) |
| 31 | } |
| 32 | |
| 33 | for i := 0; i < nodes; i++ { |
| 34 | for j := i + 1; j < nodes; j++ { |
| 35 | rtt := time.Duration(j-i) * spacing |
| 36 | truth[i][j], truth[j][i] = rtt, rtt |
| 37 | } |
| 38 | } |
| 39 | return truth |
| 40 | } |
| 41 | |
| 42 | // GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional |
| 43 | // grid with the given spacing between them. |
| 44 | func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration { |
| 45 | truth := make([][]time.Duration, nodes) |
| 46 | for i := range truth { |
| 47 | truth[i] = make([]time.Duration, nodes) |
| 48 | } |
| 49 | |
| 50 | n := int(math.Sqrt(float64(nodes))) |
| 51 | for i := 0; i < nodes; i++ { |
| 52 | for j := i + 1; j < nodes; j++ { |
| 53 | x1, y1 := float64(i%n), float64(i/n) |
| 54 | x2, y2 := float64(j%n), float64(j/n) |
| 55 | dx, dy := x2-x1, y2-y1 |
| 56 | dist := math.Sqrt(dx*dx + dy*dy) |
| 57 | rtt := time.Duration(dist * float64(spacing)) |
| 58 | truth[i][j], truth[j][i] = rtt, rtt |
| 59 | } |
| 60 | } |
| 61 | return truth |
| 62 | } |
| 63 | |
| 64 | // GenerateSplit returns a truth matrix as if half the nodes are close together in |
| 65 | // one location and half the nodes are close together in another. The lan factor |
| 66 | // is used to separate the nodes locally and the wan factor represents the split |
| 67 | // between the two sides. |
| 68 | func GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration { |
| 69 | truth := make([][]time.Duration, nodes) |
| 70 | for i := range truth { |
| 71 | truth[i] = make([]time.Duration, nodes) |
| 72 | } |
| 73 | |
| 74 | split := nodes / 2 |
| 75 | for i := 0; i < nodes; i++ { |
| 76 | for j := i + 1; j < nodes; j++ { |
| 77 | rtt := lan |
| 78 | if (i <= split && j > split) || (i > split && j <= split) { |
| 79 | rtt += wan |
| 80 | } |
| 81 | truth[i][j], truth[j][i] = rtt, rtt |
| 82 | } |
| 83 | } |
| 84 | return truth |
| 85 | } |
| 86 | |
| 87 | // GenerateCircle returns a truth matrix for a set of nodes, evenly distributed |
| 88 | // around a circle with the given radius. The first node is at the "center" of the |
| 89 | // circle because it's equidistant from all the other nodes, but we place it at |
| 90 | // double the radius, so it should show up above all the other nodes in height. |
| 91 | func GenerateCircle(nodes int, radius time.Duration) [][]time.Duration { |
| 92 | truth := make([][]time.Duration, nodes) |
| 93 | for i := range truth { |
| 94 | truth[i] = make([]time.Duration, nodes) |
| 95 | } |
| 96 | |
| 97 | for i := 0; i < nodes; i++ { |
| 98 | for j := i + 1; j < nodes; j++ { |
| 99 | var rtt time.Duration |
| 100 | if i == 0 { |
| 101 | rtt = 2 * radius |
| 102 | } else { |
| 103 | t1 := 2.0 * math.Pi * float64(i) / float64(nodes) |
| 104 | x1, y1 := math.Cos(t1), math.Sin(t1) |
| 105 | t2 := 2.0 * math.Pi * float64(j) / float64(nodes) |
| 106 | x2, y2 := math.Cos(t2), math.Sin(t2) |
| 107 | dx, dy := x2-x1, y2-y1 |
| 108 | dist := math.Sqrt(dx*dx + dy*dy) |
| 109 | rtt = time.Duration(dist * float64(radius)) |
| 110 | } |
| 111 | truth[i][j], truth[j][i] = rtt, rtt |
| 112 | } |
| 113 | } |
| 114 | return truth |
| 115 | } |
| 116 | |
| 117 | // GenerateRandom returns a truth matrix for a set of nodes with normally |
| 118 | // distributed delays, with the given mean and deviation. The RNG is re-seeded |
| 119 | // so you always get the same matrix for a given size. |
| 120 | func GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration { |
| 121 | rand.Seed(1) |
| 122 | |
| 123 | truth := make([][]time.Duration, nodes) |
| 124 | for i := range truth { |
| 125 | truth[i] = make([]time.Duration, nodes) |
| 126 | } |
| 127 | |
| 128 | for i := 0; i < nodes; i++ { |
| 129 | for j := i + 1; j < nodes; j++ { |
| 130 | rttSeconds := rand.NormFloat64()*deviation.Seconds() + mean.Seconds() |
| 131 | rtt := time.Duration(rttSeconds * secondsToNanoseconds) |
| 132 | truth[i][j], truth[j][i] = rtt, rtt |
| 133 | } |
| 134 | } |
| 135 | return truth |
| 136 | } |
| 137 | |
| 138 | // Simulate runs the given number of cycles using the given list of clients and |
| 139 | // truth matrix. On each cycle, each client will pick a random node and observe |
| 140 | // the truth RTT, updating its coordinate estimate. The RNG is re-seeded for |
| 141 | // each simulation run to get deterministic results (for this algorithm and the |
| 142 | // underlying algorithm which will use random numbers for position vectors when |
| 143 | // starting out with everything at the origin). |
| 144 | func Simulate(clients []*Client, truth [][]time.Duration, cycles int) { |
| 145 | rand.Seed(1) |
| 146 | |
| 147 | nodes := len(clients) |
| 148 | for cycle := 0; cycle < cycles; cycle++ { |
| 149 | for i, _ := range clients { |
| 150 | if j := rand.Intn(nodes); j != i { |
| 151 | c := clients[j].GetCoordinate() |
| 152 | rtt := truth[i][j] |
| 153 | node := fmt.Sprintf("node_%d", j) |
| 154 | clients[i].Update(node, c, rtt) |
| 155 | } |
| 156 | } |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | // Stats is returned from the Evaluate function with a summary of the algorithm |
| 161 | // performance. |
| 162 | type Stats struct { |
| 163 | ErrorMax float64 |
| 164 | ErrorAvg float64 |
| 165 | } |
| 166 | |
| 167 | // Evaluate uses the coordinates of the given clients to calculate estimated |
| 168 | // distances and compares them with the given truth matrix, returning summary |
| 169 | // stats. |
| 170 | func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats) { |
| 171 | nodes := len(clients) |
| 172 | count := 0 |
| 173 | for i := 0; i < nodes; i++ { |
| 174 | for j := i + 1; j < nodes; j++ { |
| 175 | est := clients[i].DistanceTo(clients[j].GetCoordinate()).Seconds() |
| 176 | actual := truth[i][j].Seconds() |
| 177 | error := math.Abs(est-actual) / actual |
| 178 | stats.ErrorMax = math.Max(stats.ErrorMax, error) |
| 179 | stats.ErrorAvg += error |
| 180 | count += 1 |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | stats.ErrorAvg /= float64(count) |
| 185 | fmt.Printf("Error avg=%9.6f max=%9.6f\n", stats.ErrorAvg, stats.ErrorMax) |
| 186 | return |
| 187 | } |