It's easy to implement "connected components" in raw DDlog, but it takes N**2 time and space in the number of elements in a component. This was a huge waste for a test case supplied by Dumitru Ceara that had over 8000 logical routers. This commit solves the problem by using the "graph" transformer built in DDlog, which efficiently implements connected components.
Signed-off-by: Ben Pfaff <[email protected]> Reported-by: Dumitru Ceara <[email protected]> Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html --- All the tests pass with this for me now, as long as https://patchwork.ozlabs.org/project/ovn/patch/[email protected]/ and https://patchwork.ozlabs.org/project/ovn/patch/[email protected]/ are applied to fix pre-existing issues. northd/lrouter.dl | 39 ++++++++++++++++++++++----------------- northd/ovn_northd.dl | 4 +++- 2 files changed, 25 insertions(+), 18 deletions(-) diff --git a/northd/lrouter.dl b/northd/lrouter.dl index 6c25b1ca9a93..85c07716bb12 100644 --- a/northd/lrouter.dl +++ b/northd/lrouter.dl @@ -14,6 +14,7 @@ import OVN_Northbound as nb import OVN_Southbound as sb +import graph as graph import multicast import ovsdb import ovn @@ -95,27 +96,31 @@ LogicalSwitchRouterPort(lsp, lsp_router_port, ls) :- &nb::Logical_Switch_Port(._uuid = lsp, .__type = "router", .options = options), Some{var lsp_router_port} = options.get("router-port"). +/* Undirected edges connecting one router and another. + * This is a building block for ConnectedLogicalRouter. */ +relation LogicalRouterEdge(a: uuid, b: uuid) +LogicalRouterEdge(a, b) :- + FirstHopLogicalRouter(a, ls), + FirstHopLogicalRouter(b, ls), + a <= b. +LogicalRouterEdge(a, b) :- PeerLogicalRouter(a, b). +function edge_from(e: LogicalRouterEdge): uuid = { e.a } +function edge_to(e: LogicalRouterEdge): uuid = { e.b } + /* - * Reachable routers. + * Sets of routers such that packets can transit directly or indirectly among + * any of the routers in a set. Any given router is in exactly one set. * - * Each row in the relation indicates that routers 'a' and 'b' can reach each - * other directly or indirectly through any chain of logical routers and - * switches. + * Each row (set, elem) identifes the membership of router with UUID 'elem' in + * set 'set', where 'set' is the minimum UUID across all its elements. * - * This relation is symmetric: if (a,b) then (b,a). - * This relation is reflexive: (a,a) is always true. + * We implement this using the graph transformer because there is no + * way to implement "connected components" in raw DDlog that avoids O(n**2) + * blowup in the number of nodes in a component. */ -relation ReachableLogicalRouter(a: uuid, b: uuid) -ReachableLogicalRouter(a, b) :- - PeerLogicalRouter(a, c), - ReachableLogicalRouter(c, b). -ReachableLogicalRouter(a, b) :- - FirstHopLogicalRouter(a, ls), - FirstHopLogicalRouter(b, ls). -ReachableLogicalRouter(a, b) :- - ReachableLogicalRouter(a, c), - ReachableLogicalRouter(c, b). -ReachableLogicalRouter(a, a) :- ReachableLogicalRouter(a, _). +relation ConnectedLogicalRouter[(uuid, uuid)] +apply graph::ConnectedComponents(LogicalRouterEdge, edge_from, edge_to) + -> (ConnectedLogicalRouter) // ha_chassis_group and gateway_chassis may not both be present. Warning[message] :- diff --git a/northd/ovn_northd.dl b/northd/ovn_northd.dl index 9f18ace1c8b5..bd3c7f891f2e 100644 --- a/northd/ovn_northd.dl +++ b/northd/ovn_northd.dl @@ -498,7 +498,9 @@ sb::Out_Port_Binding(._uuid = pbinding._uuid, * chassis. RefChassisSet has a row for every logical router. */ relation RefChassis(lr_uuid: uuid, chassis_uuid: uuid) RefChassis(lr_uuid, chassis_uuid) :- - ReachableLogicalRouter(lr_uuid, lr2_uuid), + LogicalRouterHAChassisGroup(lr_uuid, _), + ConnectedLogicalRouter[(lr_uuid, set_uuid)], + ConnectedLogicalRouter[(lr2_uuid, set_uuid)], FirstHopLogicalRouter(lr2_uuid, ls_uuid), LogicalSwitchPort(lsp_uuid, ls_uuid), &nb::Logical_Switch_Port(._uuid = lsp_uuid, .name = lsp_name), -- 2.31.1 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
