ofproto/bond: simplify rebalancing logic

The current bond relancing logic is more complicated than necessary.
When considering a bucket for rebalancing, we just need to make sure
post rebalancing traffic will be closer to the ideal traffic split
than before. This patch implements the simplification.

There is a bug is current algorithm that causes a heavyly loaded bucket
to ping-pong for each reblancing interval. The simplied loigc also fixes
this bug.

Though not the main motivation for the change, computations are now
done with integer math rather than floating math.

Reported-by: Gregory Smith <gasmith@nutanix.com>
tested-by: Gregory Smith <gasmith@nutanix.com>
Signed-off-by: Andy Zhou <azhou@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

diff --git a/AUTHORS b/AUTHORS
index 1ccbf15..3f01a0f 100644 (file)
--- a/AUTHORS
+++ b/AUTHORS
@@ -267,6 +267,7 @@ Giuseppe de Candia      giuseppe.decandia@gmail.com
 Gordon Good             ggood@nicira.com
 Greg Dahlman            gdahlman@hotmail.com
 Gregor Schaffrath       grsch@net.t-labs.tu-berlin.de
+Gregory Smith           gasmith@nutanix.com
 Guolin Yang             gyang@vmware.com
 Gur Stavi               gstavi@mrv.com
 Hari Sasank Bhamidipalli hbhamidi@cisco.com

diff --git a/ofproto/bond.c b/ofproto/bond.c
index d7a7d30..1dbf8f1 100644 (file)
--- a/ofproto/bond.c
+++ b/ofproto/bond.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -1065,23 +1065,24 @@ choose_entry_to_migrate(const struct bond_slave *from, uint64_t to_tx_bytes)
     }
 
     LIST_FOR_EACH (e, list_node, &from->entries) {
-        double old_ratio, new_ratio;
-        uint64_t delta;
-
-        if (to_tx_bytes == 0) {
-            /* Nothing on the new slave, move it. */
-            return e;
-        }
-
-        delta = e->tx_bytes;
-        old_ratio = (double)from->tx_bytes / to_tx_bytes;
-        new_ratio = (double)(from->tx_bytes - delta) / (to_tx_bytes + delta);
-        if (old_ratio - new_ratio > 0.1
-            && fabs(new_ratio - 1.0) < fabs(old_ratio - 1.0)) {
-            /* We're aiming for an ideal ratio of 1, meaning both the 'from'
-               and 'to' slave have the same load.  Therefore, we only move an
-               entry if it decreases the load on 'from', and brings us closer
-               to equal traffic load. */
+        uint64_t delta = e->tx_bytes;  /* The amount to rebalance.  */
+        uint64_t ideal_tx_bytes = (from->tx_bytes + to_tx_bytes)/2;
+                             /* Note, the ideal traffic is the mid point
+                              * between 'from' and 'to'. This value does
+                              * not change by rebalancing.  */
+        uint64_t new_low;    /* The lower bandwidth between 'to' and 'from'
+                                after rebalancing. */
+
+        new_low = MIN(from->tx_bytes - delta, to_tx_bytes + delta);
+
+        if ((new_low > to_tx_bytes) &&
+            (new_low - to_tx_bytes >= (ideal_tx_bytes - to_tx_bytes) / 10)) {
+            /* Only rebalance if the new 'low' is closer to to the mid point,
+             * and the improvement exceeds 10% of current traffic
+             * deviation from the ideal split.
+             *
+             * The improvement on the 'high' side is always the same as the
+             * 'low' side. Thus consider 'low' side is sufficient.  */
             return e;
         }
     }