From 04a85497b994b0cb1c702d4ff8b0d2149767ae0e Mon Sep 17 00:00:00 2001 From: Ethan Jackson Date: Mon, 18 Jul 2011 13:50:26 -0700 Subject: [PATCH] bundle: Implement NX_BD_ALG_ACTIVE_BACKUP. I don't expect this bundling algorithm to be particularly useful in software switches. However, hardware switches will probably only support this bundling algorithm, so it's implemented here as an example and a reference. --- lib/bundle.c | 45 ++++++++++++++++++++++------ tests/bundle.at | 71 +++++++++++++++++++++++++++++++++++++++++++++ tests/test-bundle.c | 36 ++++++++++++++++++----- 3 files changed, 136 insertions(+), 16 deletions(-) diff --git a/lib/bundle.c b/lib/bundle.c index e6b1c252..593bd87d 100644 --- a/lib/bundle.c +++ b/lib/bundle.c @@ -32,18 +32,30 @@ VLOG_DEFINE_THIS_MODULE(bundle); -/* Executes 'nab' on 'flow'. Uses 'slave_enabled' to determine if the slave - * designated by 'ofp_port' is up. Returns the chosen slave, or OFPP_NONE if - * none of the slaves are acceptable. */ -uint16_t -bundle_execute(const struct nx_action_bundle *nab, const struct flow *flow, - bool (*slave_enabled)(uint16_t ofp_port, void *aux), void *aux) +static uint16_t +execute_ab(const struct nx_action_bundle *nab, + bool (*slave_enabled)(uint16_t ofp_port, void *aux), void *aux) +{ + size_t i; + + for (i = 0; i < ntohs(nab->n_slaves); i++) { + uint16_t slave = bundle_get_slave(nab, i); + + if (slave_enabled(slave, aux)) { + return slave; + } + } + + return OFPP_NONE; +} + +static uint16_t +execute_hrw(const struct nx_action_bundle *nab, const struct flow *flow, + bool (*slave_enabled)(uint16_t ofp_port, void *aux), void *aux) { uint32_t flow_hash, best_hash; int best, i; - assert(nab->algorithm == htons(NX_BD_ALG_HRW)); - flow_hash = flow_hash_fields(flow, ntohs(nab->fields), ntohs(nab->basis)); best = -1; best_hash = 0; @@ -62,6 +74,20 @@ bundle_execute(const struct nx_action_bundle *nab, const struct flow *flow, return best >= 0 ? bundle_get_slave(nab, best) : OFPP_NONE; } +/* Executes 'nab' on 'flow'. Uses 'slave_enabled' to determine if the slave + * designated by 'ofp_port' is up. Returns the chosen slave, or OFPP_NONE if + * none of the slaves are acceptable. */ +uint16_t +bundle_execute(const struct nx_action_bundle *nab, const struct flow *flow, + bool (*slave_enabled)(uint16_t ofp_port, void *aux), void *aux) +{ + switch (ntohs(nab->algorithm)) { + case NX_BD_ALG_HRW: return execute_hrw(nab, flow, slave_enabled, aux); + case NX_BD_ALG_ACTIVE_BACKUP: return execute_ab(nab, slave_enabled, aux); + default: NOT_REACHED(); + } +} + /* Checks that 'nab' specifies a bundle action which is supported by this * bundle module. Uses the 'max_ports' parameter to validate each port using * ofputil_check_output_port(). Returns 0 if 'nab' is supported, otherwise an @@ -87,7 +113,8 @@ bundle_check(const struct nx_action_bundle *nab, int max_ports) VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, fields); } else if (n_slaves > BUNDLE_MAX_SLAVES) { VLOG_WARN_RL(&rl, "too may slaves"); - } else if (algorithm != NX_BD_ALG_HRW) { + } else if (algorithm != NX_BD_ALG_HRW + && algorithm != NX_BD_ALG_ACTIVE_BACKUP) { VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16, algorithm); } else if (slave_type != NXM_OF_IN_PORT) { VLOG_WARN_RL(&rl, "unsupported slave type %"PRIu16, slave_type); diff --git a/tests/bundle.at b/tests/bundle.at index 063cdd31..8a8cb4f2 100644 --- a/tests/bundle.at +++ b/tests/bundle.at @@ -77,6 +77,77 @@ AT_CHECK([[test-bundle 'symmetric_l4,60,hrw,ofport,slaves:1,2,3,4,5,6']], # 100000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 AT_CLEANUP +AT_SETUP([active_backup bundle link selection]) +AT_CHECK([[test-bundle 'symmetric_l4,60,active_backup,ofport,slaves:1,2,3,4,5,6']], + [0], +[100000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +110000: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +010000: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +011000: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +111000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +101000: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +001000: disruption=1.00 (perfect=1.00) 0.00 0.00 1.00 0.00 0.00 0.00 +001100: disruption=0.00 (perfect=0.00) 0.00 0.00 1.00 0.00 0.00 0.00 +101100: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +111100: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +011100: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +010100: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +110100: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +100100: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +000100: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 1.00 0.00 0.00 +000110: disruption=0.00 (perfect=0.00) 0.00 0.00 0.00 1.00 0.00 0.00 +100110: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +110110: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +010110: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +011110: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +111110: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +101110: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +001110: disruption=1.00 (perfect=1.00) 0.00 0.00 1.00 0.00 0.00 0.00 +001010: disruption=0.00 (perfect=0.00) 0.00 0.00 1.00 0.00 0.00 0.00 +101010: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +111010: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +011010: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +010010: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +110010: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +100010: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +000010: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 0.00 1.00 0.00 +000011: disruption=0.00 (perfect=0.00) 0.00 0.00 0.00 0.00 1.00 0.00 +100011: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +110011: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +010011: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +011011: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +111011: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +101011: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +001011: disruption=1.00 (perfect=1.00) 0.00 0.00 1.00 0.00 0.00 0.00 +001111: disruption=0.00 (perfect=0.00) 0.00 0.00 1.00 0.00 0.00 0.00 +101111: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +111111: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +011111: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +010111: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +110111: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +100111: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +000111: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 1.00 0.00 0.00 +000101: disruption=0.00 (perfect=0.00) 0.00 0.00 0.00 1.00 0.00 0.00 +100101: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +110101: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +010101: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +011101: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +111101: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +101101: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +001101: disruption=1.00 (perfect=1.00) 0.00 0.00 1.00 0.00 0.00 0.00 +001001: disruption=0.00 (perfect=0.00) 0.00 0.00 1.00 0.00 0.00 0.00 +101001: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +111001: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +011001: disruption=1.00 (perfect=1.00) 0.00 1.00 0.00 0.00 0.00 0.00 +010001: disruption=0.00 (perfect=0.00) 0.00 1.00 0.00 0.00 0.00 0.00 +110001: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +100001: disruption=0.00 (perfect=0.00) 1.00 0.00 0.00 0.00 0.00 0.00 +000001: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 0.00 0.00 1.00 +000000: disruption=1.00 (perfect=1.00) 0.00 0.00 0.00 0.00 0.00 0.00 +100000: disruption=1.00 (perfect=1.00) 1.00 0.00 0.00 0.00 0.00 0.00 +]) +AT_CLEANUP + AT_SETUP([hrw bundle single link selection]) AT_CHECK([[test-bundle 'symmetric_l4,60,hrw,ofport,slaves:1']], [0], [ignore]) diff --git a/tests/test-bundle.c b/tests/test-bundle.c index c6c9aec2..fb15faf9 100644 --- a/tests/test-bundle.c +++ b/tests/test-bundle.c @@ -105,6 +105,7 @@ main(int argc, char *argv[]) struct flow *flows; size_t i, n_permute, old_n_enabled; struct slave_group sg; + int old_active; set_program_name(argv[0]); random_init(); @@ -144,12 +145,14 @@ main(int argc, char *argv[]) * skip it by starting at i = 1. We do one extra iteration to cover * transitioning from the final state back to the initial state. */ old_n_enabled = 0; + old_active = -1; n_permute = 1 << sg.n_slaves; for (i = 1; i <= n_permute + 1; i++) { struct slave *slave; size_t j, n_enabled, changed; double disruption, perfect; uint8_t mask; + int active; mask = i % n_permute; @@ -171,6 +174,14 @@ main(int argc, char *argv[]) } } + active = -1; + for (j = 0; j < sg.n_slaves; j++) { + if (sg.slaves[j].enabled) { + active = j; + break; + } + } + changed = 0; for (j = 0; j < N_FLOWS; j++) { struct flow *flow = &flows[j]; @@ -188,15 +199,19 @@ main(int argc, char *argv[]) } } - if (old_n_enabled || n_enabled) { - perfect = 1.0 / MAX(old_n_enabled, n_enabled); + if (nab->algorithm == htons(NX_BD_ALG_ACTIVE_BACKUP)) { + perfect = active == old_active ? 0.0 : 1.0; } else { - /* This will happen when 'sg.n_slaves' is 0. */ - perfect = 0; + if (old_n_enabled || n_enabled) { + perfect = 1.0 / MAX(old_n_enabled, n_enabled); + } else { + /* This will happen when 'sg.n_slaves' is 0. */ + perfect = 0; + } } disruption = changed / (double)N_FLOWS; - printf("%s: disruption=%.2f (perfect=%.2f) ", + printf("%s: disruption=%.2f (perfect=%.2f)", mask_str(mask, sg.n_slaves), disruption, perfect); for (j = 0 ; j < sg.n_slaves; j++) { @@ -204,10 +219,16 @@ main(int argc, char *argv[]) double flow_percent; flow_percent = slave->flow_count / (double)N_FLOWS; - printf("%.2f ", flow_percent); + printf( " %.2f", flow_percent); if (slave->enabled) { - double perfect_fp = 1.0 / n_enabled; + double perfect_fp; + + if (nab->algorithm == htons(NX_BD_ALG_ACTIVE_BACKUP)) { + perfect_fp = j == active ? 1.0 : 0.0; + } else { + perfect_fp = 1.0 / n_enabled; + } if (fabs(flow_percent - perfect_fp) >= .01) { fprintf(stderr, "%s: slave %d: flow_percentage=%.5f for" @@ -232,6 +253,7 @@ main(int argc, char *argv[]) ok = false; } + old_active = active; old_n_enabled = n_enabled; } -- 2.30.2