diff options
| -rw-r--r-- | rumba/elements/experimentation.py | 46 |
1 files changed, 42 insertions, 4 deletions
diff --git a/rumba/elements/experimentation.py b/rumba/elements/experimentation.py index 8aa4fe0..67fb2e3 100644 --- a/rumba/elements/experimentation.py +++ b/rumba/elements/experimentation.py @@ -38,6 +38,42 @@ logger = log.get_logger(__name__) tmp_dir = '/tmp/rumba' +def _enrollment_root(adj): + """Pick a graph-central node as the root of the enrollment spanning + tree, so the tree is as shallow as possible. + + Rooting a line at an endpoint forces the upper layer's directory and + routing to converge across the maximum number of hops (e.g. a-b-c + rooted at a leaves c two hops from the bootstrapper); a central root + halves that. *adj* maps node -> [(neighbour, lower_layer), ...]. + The node with minimum eccentricity wins; reachability is maximised + first to stay well-defined on a disconnected graph, and ties fall + back to insertion (node) order. + """ + best = None + best_key = None + + for src in adj: + dist = {src: 0} + queue = [src] + head = 0 + + while head < len(queue): + cur = queue[head] + head += 1 + for nxt, _lower in adj[cur]: + if nxt not in dist: + dist[nxt] = dist[cur] + 1 + queue.append(nxt) + + key = (-len(dist), max(dist.values())) + if best_key is None or key < best_key: + best_key = key + best = src + + return best + + class Testbed(object): """ Base class for every testbed plugin. @@ -334,10 +370,12 @@ class Experiment(object): logger.debug("Layer graph for %s: %s", layer, ', '.join(er)) # To generate the list of minimal enrollments - # and minimal flows, we simulate it, using - # breadth-first traversal. - enrolled = {first} - frontier = {first} + # and minimal flows, we simulate it, using breadth-first + # traversal from a graph-central root (shallow tree). + root = _enrollment_root(layer_graphs[layer]) + + enrolled = {root} + frontier = {root} edges_covered = set() while len(frontier): cur = frontier.pop() |