]>
Commit | Line | Data |
---|---|---|
53ddd40a | 1 | /* |
f25d0cf3 | 2 | * Copyright (c) 2010, 2012 Nicira, Inc. |
53ddd40a BP |
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" | |
f25d0cf3 | 28 | #include "ofp-actions.h" |
53ddd40a BP |
29 | #include "random.h" |
30 | #include "util.h" | |
31 | ||
32 | int | |
33 | main(int argc, char *argv[]) | |
34 | { | |
35 | enum { MP_MAX_LINKS = 63 }; | |
f25d0cf3 | 36 | struct ofpact_multipath mp; |
53ddd40a BP |
37 | bool ok = true; |
38 | int n; | |
39 | ||
40 | set_program_name(argv[0]); | |
41 | random_init(); | |
42 | ||
43 | if (argc != 2) { | |
44 | ovs_fatal(0, "usage: %s multipath_action", program_name); | |
45 | } | |
46 | ||
47 | multipath_parse(&mp, argv[1]); | |
48 | for (n = 1; n <= MP_MAX_LINKS; n++) { | |
49 | enum { N_FLOWS = 65536 }; | |
50 | double disruption, perfect, distribution; | |
51 | int histogram[MP_MAX_LINKS]; | |
52 | double sum_dev2, stddev; | |
53 | int changed; | |
54 | int i; | |
55 | ||
56 | changed = 0; | |
57 | memset(histogram, 0, sizeof histogram); | |
58 | for (i = 0; i < N_FLOWS; i++) { | |
59 | int old_link, new_link; | |
bcd2633a | 60 | struct flow_wildcards wc; |
53ddd40a BP |
61 | struct flow flow; |
62 | ||
63 | random_bytes(&flow, sizeof flow); | |
3b21e387 | 64 | memset(flow.zeros, 0, sizeof flow.zeros); |
b02475c5 | 65 | flow.mpls_depth = 0; |
53ddd40a | 66 | |
f25d0cf3 | 67 | mp.max_link = n - 1; |
bcd2633a | 68 | multipath_execute(&mp, &flow, &wc); |
53ddd40a BP |
69 | old_link = flow.regs[0]; |
70 | ||
f25d0cf3 | 71 | mp.max_link = n; |
bcd2633a | 72 | multipath_execute(&mp, &flow, &wc); |
53ddd40a BP |
73 | new_link = flow.regs[0]; |
74 | ||
75 | assert(old_link >= 0 && old_link < n); | |
76 | assert(new_link >= 0 && new_link < n + 1); | |
77 | ||
78 | histogram[old_link]++; | |
79 | changed += old_link != new_link; | |
80 | } | |
81 | ||
82 | sum_dev2 = 0.0; | |
83 | for (i = 0; i < n; i++) { | |
84 | double mean = (double) N_FLOWS / n; | |
85 | double deviation = histogram[i] - mean; | |
86 | ||
87 | sum_dev2 += deviation * deviation; | |
88 | } | |
89 | stddev = sqrt(sum_dev2 / n); | |
90 | ||
91 | disruption = (double) changed / N_FLOWS; | |
92 | perfect = 1.0 / (n + 1); | |
93 | distribution = stddev / ((double) N_FLOWS / n); | |
94 | printf("%2d -> %2d: disruption=%.2f (perfect=%.2f); " | |
95 | "stddev/expected=%.4f\n", | |
96 | n, n + 1, disruption, perfect, distribution); | |
97 | ||
f25d0cf3 | 98 | switch (mp.algorithm) { |
53ddd40a BP |
99 | case NX_MP_ALG_MODULO_N: |
100 | if (disruption < (n < 2 ? .25 : .5)) { | |
101 | fprintf(stderr, "%d -> %d: disruption=%.2f < .5\n", | |
102 | n, n + 1, disruption); | |
103 | ok = false; | |
104 | } | |
105 | break; | |
106 | ||
107 | case NX_MP_ALG_HASH_THRESHOLD: | |
108 | if (disruption < .48 || disruption > .52) { | |
109 | fprintf(stderr, "%d -> %d: disruption=%.2f not approximately " | |
110 | ".5\n", n, n + 1, disruption); | |
111 | ok = false; | |
112 | } | |
113 | break; | |
114 | ||
115 | case NX_MP_ALG_ITER_HASH: | |
116 | if (!(n & (n - 1))) { | |
117 | break; | |
118 | } | |
119 | /* Fall through. */ | |
120 | case NX_MP_ALG_HRW: | |
121 | if (fabs(disruption - perfect) >= .01) { | |
122 | fprintf(stderr, "%d -> %d: disruption=%.5f differs from " | |
123 | "perfect=%.5f by more than .01\n", | |
124 | n, n + 1, disruption, perfect); | |
125 | ok = false; | |
126 | } | |
127 | break; | |
128 | ||
129 | default: | |
130 | NOT_REACHED(); | |
131 | } | |
132 | } | |
133 | ||
134 | return ok ? 0 : 1; | |
135 | } |