METHOD AND APPARATUS FOR RESILIENT ROUTING OF CONTROL TRAFFIC IN A SPLIT-ARCHITECTURE SYSTEM

• US 20130028070A1
• Filed: 11/11/2011
• Published: 01/31/2013
• Est. Priority Date: 07/29/2011
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Beheshti-Zavareh, Neda, Zhang, Ying
• Granted Patent: US 9,185,027 B2
• Time in Patent Office: Days
• US Class Current: 370/217
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

The invention is a routing algorithm characteristic that minimizes the weight, meaning that the probability that a node is disconnected from the controller in case of a failure in the network is minimized. The first algorithm used in the invention is an approximation algorithm for finding the controller routing tree that provides maximum resilience in the network. The algorithm is referred to herein as the Maximum Resilience (MR) algorithm. The heuristic MR algorithm selects a shortest-path tree as a starting point and modifies the tree in order to improve resilience. The output of the MR algorithm is not necessarily a shortest-path tree, but provides more resilience compared to the initial tree. The RASP algorithm provides a shortest-path tree with improved network resilience compared to other possible shortest-path trees.

Claims

1. A method implemented by a network topology design system, the network topology design system including a controller having a microprocessor coupled to a non-transitory machine-readable or computer-readable storage media and operable as a controller routing tree module, the method to determine a controller routing tree T′

for use within a split architecture network represented by network graph G, where control plane components are executed by the controller separate from data plane components executed by a plurality of switches, G=(V, E), where V is the set of nodes in the network, and E is the set of bidirectional edges between nodes traversing each switch to the controller, the controller routing tree T′

representing a non-load balanced control traffic path between switches and the controller, the control traffic representing bi-directional information from each switch to the controller and forwarding decision information from the controller to the switch, the method comprising the steps of;

graphing, by the network topology design system, all possible distances to the controller from each switch in G, each such the distance being comprised of a subset of E;

based on all possible distances, determining a shortest-path to the controller for each such switch, all the shortest-paths from each switch to the controller comprising the shortest-path tree T for the controller;

storing the shortest-path tree T in the non-transitory machine-readable or computer-readable storage media;

based on the shortest-path to the controller for each switch, designating all immediate neighbor nodes of such switch in G as either upstream or downstream;

commencing with the switch(es) that are neighbors to the controller and traversing to each immediate downstream switch until all of the switches in G are processed, determining and assigning, by the network topology design system, a weight for each switch in G;

based on the weight assigned to each switch, modifying the shortest-path tree T to obtain a modified shortest-path tree T′

with improved resilience; and

storing the modified shortest-path tree T′

in the non-transitory machine-readable or computer-readable storage media.

2. The method of claim 1, further comprising communicating to, and storing in, a non-transitory machine-readable or computer-readable storage media in each switch, an outgoing primary link and, as a backup, if any, at least one outgoing secondary link from the switch to an immediate upstream switch based on the paths from the switch to the controller in the shortest-path tree T′

.

3. The method of claim 2, further comprising the steps of:

detecting, by a switch, a failure in an upstream link or node;

changing, by the switch, its route to the controller by changing the outgoing primary link to an outgoing secondary link, if any, serving as a backup.

4. The method of claim 1, wherein the step of graphing is implemented by administrator input, automated discovery processes or any combination thereof.

5. The method of claim 1, wherein the step of calculating and assigning, by the network topology design system, a weight for each switch in G, further comprises the steps of:

calculating and assigning the weight to each switch in V based on whether such switch is protected from upstream node failures and link failures by determining the extent to which there is at least one different path to the controller over at least one outgoing secondary link;

if there exists at least one different path using at least one outgoing secondary link, communicating from the controller to such switch the existence of the at least one outgoing secondary link; and

configuring as a backup the at least one outgoing secondary link in such switch.

6. The method of claim 1, wherein the step of modifying the shortest-path tree T further comprises the steps of:

determining at a first switch if any improvements to resilience of the split architecture network can be obtained by using a different path to the controller taking into account the weight of each other switch traversed to the controller from the first switch;

determining at a second switch immediately downstream from the first switch, if any improvements to resilience can be obtained by using a different path from such second switch to the controller taking into account the weight of each switch traversed to the controller; and

performing the foregoing determining steps at each switch in G until all switches in G have been processed.

7. The method of claim 1, wherein a greater weight is assigned to a switch closer to the controller as a consequence of it having a greater number of downstream switch(es).

8. The method of claim 1, wherein the weight assigned to a switch is proportional or fractional to the number of its downstream switch(es).

9. The method of claim 1, wherein the weight of a switch is based on the number of its downstream switch(es) as scaled by a cost factor assigned by a user.

10. The method of claim 9, wherein the cost factor is 0, if the switch is protected against both its outgoing link and its immediate upstream node failures;

α

, if the switch is only protected against an outgoing link failure;

β

if the switch is only protected against an immediate upstream node failure, otherwise α

+β

.

11. The method of claim 10, further comprising the step of selecting as routing tree T′

, the routing tree having the minimum cumulative weight, hence minimizing the probability that a switch is disconnected from the controller in case of a link or node failure in the network.

12. A controller in a network with a split architecture, comprising:

a microprocessor coupled to a non-transitory machine-readable or computer-readable storage media and operable as a controller routing tree module to determine a controller routing tree T′

, the controller operable to;

graph all possible distances to the controller from each switch in G, each such the distance being comprised of a subset of E, wherein G=(V, E), where V is the set of nodes in the network, and E is the set of bidirectional edges between nodes traversing each switch to the controller;

based on all of the possible distances, determine a shortest-path to the controller for each switch in the network, all the shortest-paths from each switch to the controller comprising the shortest-path tree T for the controller;

store the shortest-path tree T in the non-transitory machine-readable or computer-readable storage media;

based on the shortest-path to the controller for each switch, designate all immediate neighbor nodes of such switch in G as either upstream or downstream;

commencing with the switch(es) that are neighbors to the controller, traverse each immediately downstream switch until all of the switches in G are processed, so as to determine and assign, by the network topology design system, a weight for each switch in G;

based on the weight of each switch, modify the shortest-path tree T to obtain a modified shortest-path tree T′

with improved resilience; and

store the modified shortest-path tree T′

in the non-transitory machine-readable or computer-readable storage media.

13. The controller of claim 12, in combination with a switch, wherein the controller communicates to, and the switch stores in a non-transitory machine-readable or computer-readable storage media, an outgoing primary link and, as a backup, if any, at least one outgoing secondary link from the switch to an immediate upstream switch based on the paths from the switch to the controller in the shortest-path tree T′

as determined by the controller routing tree module.

14. The controller and switch combination of claim 13, wherein the switch is configured to detect a failure in an upstream link or node and change, by the switch, its route to the controller by changing the outgoing primary link to an outgoing secondary link, if any, serving as a backup.

15. A method implemented by a network topology design system, the network topology design system including a controller having a microprocessor coupled to a non-transitory machine-readable or computer-readable storage media and operable as a controller routing tree module, the method to determine a controller routing tree T′

for use within a split architecture network represented by network graph G, where control plane components are executed by the controller separate from data plane components executed by a plurality of switches, G=(V, E), where V is the set of nodes in the network, and E is the set of bidirectional edges between nodes traversing each switch to the controller, the controller routing tree T′

representing a non-load balanced control traffic path between each switch and the controller, the control traffic representing bi-directional information from each switch to the controller and forwarding decision information from the controller to the switch, the method comprising the steps of;

graphing, by the network topology design system, all possible distances to the controller from each switch in G, each such the distance being comprised of a subset of E;

based on all of the possible distances, determining a shortest-path to the controller for each such switch, all of the shortest-paths from each switch to the controller comprising the shortest-path tree T for the controller;

storing the shortest-path tree T in the non-transitory machine-readable or computer-readable storage media;

based on the shortest-path to the controller for each switch, designating all immediate neighbor nodes of such switch in G as either upstream or downstream;

establishing an edge weight parameter for each link between each switch and each of the switches traversed along each path to the controller;

determining if there are more than one equal-length, shortest-paths between the controller and the switch;

if there is not more than one equal-length, shortest-path between the controller and the switch, selecting such shortest-path and storing it in the non-transitory machine-readable or computer-readable storage media; and

if there is more than one equal-length, shortest-path from the switch to the controller, selecting as the shortest-path the path having the most resilience compared to the other shortest-paths and storing the selected shortest-path in the non-transitory machine-readable or computer-readable storage media.

16. The method of claim 15, further comprising calculating the initial shortest path tree(s) using a Bellman-Ford algorithm.

17. A controller in a network with a split architecture, comprising:

a microprocessor coupled to a non-transitory machine-readable or computer-readable storage media and operable as a controller routing tree module to determine a controller routing tree T′

, the controller operable to;

graph all possible distances to the controller from each switch in G, each such the distance being comprised of a subset of E, wherein G=(V, E), where V is the set of nodes in the network, and E is the set of bidirectional edges between nodes traversing each switch to the controller;

based on all of the possible distances, determine an initial shortest-path to the controller for each switch in the network, all the shortest-paths from each switch to the controller comprising the shortest-path tree T for the controller;

store the shortest-path tree T in the non-transitory machine-readable or computer-readable storage media;

based on the shortest-path to the controller for each switch, designate all immediate neighbor nodes of such switch in G as either upstream or downstream;

establish an edge weight parameter for each link between each switch and each of the switches traversed along each path to the controller;

determine if there are more than one equal-length, shortest-paths between the controller and the switch;

if there is not more than one equal-length, shortest-path between the controller and the switch, select such shortest-path and storing it in the non-transitory machine-readable or computer-readable storage media; and

if there is more than one equal-length, shortest-path from the switch to the controller, select as the shortest-path the one having the most resilience compared to the other shortest-paths; and

store the selected shortest-path in the non-transitory machine-readable or computer-readable storage media.

18. The controller of claim 17, in combination with a switch, wherein the controller communicates to, and the switch stores in a non-transitory machine-readable or computer-readable storage media, an outgoing primary link and, as a backup, if any, at least one outgoing secondary link from the switch to an immediate upstream switch based on the paths from the switch to the controller in the shortest-path tree as determined by the controller routing tree module.

19. The controller and switch combination of claim 18, wherein the switch is configured to detect a failure in an upstream link or node;

and

change, by the switch, its path to the controller by changing the outgoing primary link to an outgoing secondary link, if any, serving as a backup.

20. The controller of claim 17, wherein the initial shortest path tree(s) are calculated using a Bellman-Ford algorithm.