QPID-4967 - work in progress on multi-router networks

 - Added computation of valid origins for destinations
 - Modified the forwarding algorithm to ensure that only one copy of a message is sent on
   a given inter-router link
 - Added test coverage for valid origins


git-svn-id: https://svn.apache.org/repos/asf/qpid/trunk@1529242 13f79535-47bb-0310-9956-ffa450edef68

3 files changed, 53 insertions, 7 deletions

diff --git a/qpid/extras/dispatch/python/qpid/dispatch/router/path.py b/qpid/extras/dispatch/python/qpid/dispatch/router/path.py
index 9357ed1847..da04474e75 100644
--- a/qpid/extras/dispatch/python/qpid/dispatch/router/path.py
+++ b/qpid/extras/dispatch/python/qpid/dispatch/router/path.py
@@ -49,7 +49,7 @@ class PathEngine(object):
     def _calculate_tree_from_root(self, root):
         ##
         ## Make a copy of the current collection of link-states that contains
-        ## an empty link-state for nodes that are known-peers but are not in the
+        ## a fake link-state for nodes that are known-peers but are not in the
         ## collection currently.  This is needed to establish routes to those nodes
         ## so we can trade link-state information with them.
         ##
@@ -58,7 +58,7 @@ class PathEngine(object):
             link_states[_id] = ls.peers
             for p in ls.peers:
                 if p not in link_states:
-                    link_states[p] = []
+                    link_states[p] = [_id]
 
         ##
         ## Setup Dijkstra's Algorithm
@@ -102,11 +102,42 @@ class PathEngine(object):
         return prev
 
 
+    def _calculate_valid_origins(self, nodeset):
+        ##
+        ## Calculate the tree from each origin, determine the set of origins-per-dest
+        ## for which the path from origin to dest passes through us.  This is the set
+        ## of valid origins for forwarding to the destination.
+        ##
+        valid_origin = {}         # Map of destination => List of Valid Origins
+        for node in nodeset:
+            if node != self.id:
+                valid_origin[node] = []
+
+        for root in valid_origin.keys():
+            prev  = self._calculate_tree_from_root(root)
+            nodes = prev.keys()
+            while len(nodes) > 0:
+                u = nodes[0]
+                path = [u]
+                nodes.remove(u)
+                v = prev[u]
+                while v != root:
+                    if v in nodes:
+                        if v != self.id:
+                            path.append(v)
+                        nodes.remove(v)
+                    if v == self.id:
+                        valid_origin[root].extend(path)
+                    u = v
+                    v = prev[u]
+        return valid_origin
+
+
     def _calculate_routes(self):
         ##
         ## Generate the shortest-path tree with the local node as root
         ##
-        prev = self._calculate_tree_from_root(self.id)
+        prev  = self._calculate_tree_from_root(self.id)
         nodes = prev.keys()
 
         ##
@@ -127,12 +158,14 @@ class PathEngine(object):
             for w in path:        # mark each node in the path as reachable via the next hop
                 next_hops[w] = u
 
+        self.container.next_hops_changed(next_hops)
+
         ##
-        ## TODO - Calculate the tree from each origin, determine the set of origins-per-dest
-        ##        for which the path from origin to dest passes through us.  This is the set
-        ##        of valid origins for forwarding to the destination.
+        ## Calculate the valid origins for remote routers
         ##
-        self.container.next_hops_changed(next_hops)
+        valid_origin = self._calculate_valid_origins(prev.keys())
+        self.container.valid_origins_changed(valid_origin)
+
 
 
 class NodeSet(object):
diff --git a/qpid/extras/dispatch/python/qpid/dispatch/router/router_engine.py b/qpid/extras/dispatch/python/qpid/dispatch/router/router_engine.py
index c2c623f980..02f0315104 100644
--- a/qpid/extras/dispatch/python/qpid/dispatch/router/router_engine.py
+++ b/qpid/extras/dispatch/python/qpid/dispatch/router/router_engine.py
@@ -247,6 +247,10 @@ class RouterEngine:
         self.routing_table_engine.next_hops_changed(next_hop_table)
         self.binding_engine.next_hops_changed()
 
+    def valid_origins_changed(self, valid_origins):
+        self.log(LOG_DEBUG, "Event: valid_origins_changed: %r" % valid_origins)
+        self.routing_table_engine.valid_origins_changed(valid_origins)
+
     def mobile_sequence_changed(self, mobile_seq):
         self.log(LOG_DEBUG, "Event: mobile_sequence_changed: %d" % mobile_seq)
         self.link_state_engine.set_mobile_sequence(mobile_seq)
diff --git a/qpid/extras/dispatch/python/qpid/dispatch/router/routing.py b/qpid/extras/dispatch/python/qpid/dispatch/router/routing.py
index af974b402a..1097d8fbba 100644
--- a/qpid/extras/dispatch/python/qpid/dispatch/router/routing.py
+++ b/qpid/extras/dispatch/python/qpid/dispatch/router/routing.py
@@ -48,6 +48,15 @@ class RoutingTableEngine(object):
             self.container.router_adapter.set_next_hop(mb_id, mb_nh)
 
 
+    def valid_origins_changes(self, valid_origins):
+        for _id, vo in valid_origins.items():
+            mb_id = self.node_tracker.maskbit_for_node(_id)
+            mb_vo = []
+            for o in vo:
+                mb_vo.append(self.node_tracker.maskbit_for_node(o))
+            self.container.router_adapted.set_valid_origins(mb_id, mb_vo)
+
+
     def get_next_hops(self):
         return self.next_hops