From: Ethan Jackson <ethan@nicira.com>
Date: Mon, 18 Jul 2011 20:50:26 +0000 (-0700)
Subject: bundle: Implement NX_BD_ALG_ACTIVE_BACKUP.
X-Git-Tag: v1.2.0~55
X-Git-Url: http://git.onelab.eu/?p=sliver-openvswitch.git;a=commitdiff_plain;h=04a85497b994b0cb1c702d4ff8b0d2149767ae0e

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

diff --git a/lib/bundle.c b/lib/bundle.c
index e6b1c252e..593bd87d9 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 063cdd312..8a8cb4f2f 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 c6c9aec2a..fb15faf98 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;
     }