]>
Commit | Line | Data |
---|---|---|
53ddd40a BP |
1 | /* |
2 | * Copyright (c) 2010 Nicira Networks. | |
3 | * | |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | #include <config.h> | |
18 | ||
19 | #include "multipath.h" | |
20 | ||
21 | #include <assert.h> | |
22 | #include <getopt.h> | |
23 | #include <math.h> | |
24 | #include <stdio.h> | |
25 | #include <stdlib.h> | |
26 | ||
27 | #include "flow.h" | |
28 | #include "random.h" | |
29 | #include "util.h" | |
30 | ||
31 | int | |
32 | main(int argc, char *argv[]) | |
33 | { | |
34 | enum { MP_MAX_LINKS = 63 }; | |
35 | struct nx_action_multipath mp; | |
36 | bool ok = true; | |
37 | int n; | |
38 | ||
39 | set_program_name(argv[0]); | |
40 | random_init(); | |
41 | ||
42 | if (argc != 2) { | |
43 | ovs_fatal(0, "usage: %s multipath_action", program_name); | |
44 | } | |
45 | ||
46 | multipath_parse(&mp, argv[1]); | |
47 | for (n = 1; n <= MP_MAX_LINKS; n++) { | |
48 | enum { N_FLOWS = 65536 }; | |
49 | double disruption, perfect, distribution; | |
50 | int histogram[MP_MAX_LINKS]; | |
51 | double sum_dev2, stddev; | |
52 | int changed; | |
53 | int i; | |
54 | ||
55 | changed = 0; | |
56 | memset(histogram, 0, sizeof histogram); | |
57 | for (i = 0; i < N_FLOWS; i++) { | |
58 | int old_link, new_link; | |
59 | struct flow flow; | |
60 | ||
61 | random_bytes(&flow, sizeof flow); | |
62 | ||
63 | mp.max_link = htons(n - 1); | |
64 | multipath_execute(&mp, &flow); | |
65 | old_link = flow.regs[0]; | |
66 | ||
67 | mp.max_link = htons(n); | |
68 | multipath_execute(&mp, &flow); | |
69 | new_link = flow.regs[0]; | |
70 | ||
71 | assert(old_link >= 0 && old_link < n); | |
72 | assert(new_link >= 0 && new_link < n + 1); | |
73 | ||
74 | histogram[old_link]++; | |
75 | changed += old_link != new_link; | |
76 | } | |
77 | ||
78 | sum_dev2 = 0.0; | |
79 | for (i = 0; i < n; i++) { | |
80 | double mean = (double) N_FLOWS / n; | |
81 | double deviation = histogram[i] - mean; | |
82 | ||
83 | sum_dev2 += deviation * deviation; | |
84 | } | |
85 | stddev = sqrt(sum_dev2 / n); | |
86 | ||
87 | disruption = (double) changed / N_FLOWS; | |
88 | perfect = 1.0 / (n + 1); | |
89 | distribution = stddev / ((double) N_FLOWS / n); | |
90 | printf("%2d -> %2d: disruption=%.2f (perfect=%.2f); " | |
91 | "stddev/expected=%.4f\n", | |
92 | n, n + 1, disruption, perfect, distribution); | |
93 | ||
94 | switch (ntohs(mp.algorithm)) { | |
95 | case NX_MP_ALG_MODULO_N: | |
96 | if (disruption < (n < 2 ? .25 : .5)) { | |
97 | fprintf(stderr, "%d -> %d: disruption=%.2f < .5\n", | |
98 | n, n + 1, disruption); | |
99 | ok = false; | |
100 | } | |
101 | break; | |
102 | ||
103 | case NX_MP_ALG_HASH_THRESHOLD: | |
104 | if (disruption < .48 || disruption > .52) { | |
105 | fprintf(stderr, "%d -> %d: disruption=%.2f not approximately " | |
106 | ".5\n", n, n + 1, disruption); | |
107 | ok = false; | |
108 | } | |
109 | break; | |
110 | ||
111 | case NX_MP_ALG_ITER_HASH: | |
112 | if (!(n & (n - 1))) { | |
113 | break; | |
114 | } | |
115 | /* Fall through. */ | |
116 | case NX_MP_ALG_HRW: | |
117 | if (fabs(disruption - perfect) >= .01) { | |
118 | fprintf(stderr, "%d -> %d: disruption=%.5f differs from " | |
119 | "perfect=%.5f by more than .01\n", | |
120 | n, n + 1, disruption, perfect); | |
121 | ok = false; | |
122 | } | |
123 | break; | |
124 | ||
125 | default: | |
126 | NOT_REACHED(); | |
127 | } | |
128 | } | |
129 | ||
130 | return ok ? 0 : 1; | |
131 | } |