GENERATING A LOOP-FREE ROUTING TOPOLOGY USING ROUTING ARCS

• US 20150263936A1
• Filed: 05/29/2015
• Published: 09/17/2015
• Est. Priority Date: 05/23/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: THUBERT, Pascal, BELLAGAMBA, Patrice, ANTEUNIS, Dirk, LEVY-ABEGNOLI, Eric Michel
• Granted Patent: US 9,769,057 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/18 Loop-free operations

Abstract

In one embodiment, a method comprises creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination device, each routing arc comprising a first network device as a first end of the routing arc, a second network device as a second end of the routing arc, and at least a third network device configured for routing any network traffic along the routing arc toward the destination device via any one of the first or second ends of the routing arc; and causing the network traffic to be forwarded along at least one of the routing arcs to the destination device.

Claims

1. A method comprising:

creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination device, each routing arc comprising a first network device as a first end of the routing arc, a second network device as a second end of the routing arc, and at least a third network device configured for routing any network traffic along the routing arc toward the destination device and exiting via any one of the first or second ends of the routing arc; and

causing the network traffic to be forwarded along at least one of the routing arcs to the destination device.

2. The method of claim 1, wherein the first and second ends of each routing arc each terminate at one of the destination device, a second network node directly coupled to the destination device, or a junction node of another routing arc and having at least two non-congruent paths for reaching the destination device.

3. The method of claim 2, wherein the creating includes:

creating a first of the routing arcs as an infrastructure arc having the corresponding first end terminating at the destination device; and

creating a second of the routing arcs as an infrastructure arc, after the first of the routing routing arcs and having the corresponding first end terminating at the first of the routing arcs, the second of the routing arcs including network devices that are distinct from any of the network devices of the first of the routing arcs.

4. The method of claim 1, wherein the loop-free routing topology guarantees that any of the network devices in the loop-free routing topology having two data links can reach the destination device via at least one of the routing arcs even if a link failure is encountered in the loop-free routing topology.

5. The method of claim 1, wherein at least a first of the routing arcs further includes a fourth network device identified as an intermediate junction node and adjacent to the corresponding third network device, the intermediate junction node consisting of two reversible links and zero or more inward oriented links from any other network device of the first of the routing arcs, each reversible link being reversible without creating a loop in the loop-free routing topology.

6. The method of claim 5, wherein each routing arc further comprises one and only one arc cursor that provides exclusive control of directing the network traffic along the routing arc and away from any network device having possession of the arc cursor, one of the third or fourth network devices controlling the network traffic along the corresponding routing arc based on possession of the arc cursor.

7. The method of claim 6, wherein the third network device gains possession of the arc cursor, for continued routing of the network traffic in the corresponding routing arc, based on a detected failure in the corresponding routing arc, the possession previously owned by the fourth network device, the continued routing based on the third network device reversing one of the reversible links without creating a loop in the loop-free routing topology.

8. The method of claim 1, wherein the creating includes:

generating a first directed acyclic graph for reaching the destination device;

identifying, within the first directed acyclic graph, two or more junction nodes each having at least two non-congruent paths for reaching the destination device, including identifying one or more reversible links between the junction nodes and that can be reversed along one of the non-congruent paths without introducing a loop into the loop-free topology;

creating a first of the infrastructure arcs comprising two or more of the junction nodes and one or more reversible links, the first of the infrastructure arcs having the corresponding first end terminating at the destination device; and

creating a second of the routing arcs, after the first of the routing arcs and having the corresponding first end terminating at the first of the routing arcs, the loop-free routing topology having the routing arcs and consisting of the destination device, zero or more leaf nodes each having only one data link, and the plurality of junction nodes.

9. The method of claim 8, wherein the creating of the second of the routing arcs includes:

identifying a second directed acyclic graph for reaching a first of the junction nodes in the first directed acyclic graph, the first junction node in the first of the infrastructure nodes a first end of the second of the routing arcs; and

identifying, within the second directed acyclic graph, a new junction node having a new non-congruent path for reaching the destination device and that is distinct from the first of the junction nodes, the new junction node providing the non-congruent path to the second end of the second of the routing arcs.

10. A apparatus comprising:

a processor circuit configured for creating, for a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination device, each routing arc comprising a first network device as a first end of the routing arc, a second network device as a second end of the routing arc, and at least a third network device configured for routing any network traffic along the routing arc toward the destination device and exiting via any one of the first or second ends of the routing arc;

a memory circuit configured for storing parameters associated with the routing arcs; and

a device interface circuit configured for outputting at least selected parameters associated with the routing arcs to a second apparatus, for deployment of the loop-free routing topology.

11. The apparatus of claim 10, wherein the first and second ends of each routing arc each terminate at one of the destination device, a second network node directly coupled to the destination device, or a junction node of another routing arc and having at least two non-congruent paths for reaching the destination device.

12. The apparatus of claim 11, wherein the processor circuit is configured for creating the loop-free routing topology based on:

creating a first of the routing arcs as an infrastructure arc having the corresponding first end terminating at the destination device; and

creating a second of the routing arcs as an infrastructure arc, after the first of the routing routing arcs and having the corresponding first end terminating at the first of the routing arcs, the second of the routing arcs including network devices that are distinct from any of the network devices of the first of the routing arcs.

13. The apparatus of claim 10, wherein the loop-free routing topology guarantees that any of the network devices in the loop-free routing topology having two data links can reach the destination device via at least one of the routing arcs even if a link failure is encountered in the loop-free routing topology.

14. The apparatus of claim 10, wherein at least a first of the routing arcs further includes a fourth network device identified as an intermediate junction node and adjacent to the corresponding third network device, the intermediate junction node consisting of two reversible links and zero or more inward oriented links from any other network device of the first of the routing arcs, each reversible link being reversible without creating a loop in the loop-free routing topology.

15. The apparatus of claim 14, wherein each routing arc further comprises one and only one arc cursor that provides exclusive control of directing the network traffic along the routing arc and away from any network device having possession of the arc cursor, one of the third or fourth network devices controlling the network traffic along the corresponding routing arc based on possession of the arc cursor.

16. The apparatus of claim 15, wherein the third network device gains possession of the arc cursor, for continued routing of the network traffic in the corresponding routing arc, based on a detected failure in the corresponding routing arc, the possession previously owned by the fourth network device.

17. The apparatus of claim 10, wherein the processor circuit is configured for generating the loop-free routing topology based on:

generating a first directed acyclic graph for reaching the destination device;

identifying, within the first directed acyclic graph, two or more junction nodes each having at least two non-congruent paths for reaching the destination device, including identifying one or more reversible links between the junction nodes and that can be reversed along one of the non-congruent paths without introducing a loop into the loop-free topology;

creating a first of the infrastructure arcs comprising two or more of the junction nodes and one or more reversible links, the first of the infrastructure arcs having the corresponding first end terminating at the destination device; and

creating a second of the routing arcs, after the first of the routing arcs and having the corresponding first end terminating at the first of the routing arcs, the loop-free routing topology having the routing arcs and consisting of the destination device, zero or more leaf nodes each having only one data link, and the plurality of junction nodes.

18. The apparatus of claim 17, wherein the processor circuit is configured for creating the second of the routing arcs based on:

identifying a second directed acyclic graph for reaching a first of the junction nodes in the first directed acyclic graph, the first junction node in the first of the infrastructure nodes a first end of the second of the routing arcs; and

identifying, within the second directed acyclic graph, a new junction node having a new non-congruent path for reaching the destination device and that is distinct from the first of the junction nodes, the new junction node providing the non-congruent path to the second end of the second of the routing arcs.

19. Logic encoded in one or more non-transitory tangible media for execution by a machine and when executed by the machine performs the operations of:

creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination device, each routing arc comprising a first network device as a first end of the routing arc, a second network device as a second end of the routing arc, and at least a third network device configured for routing any network traffic along the routing arc toward the destination device and exiting via any one of the first or second ends of the routing arc; and

causing the network traffic to be forwarded along at least one of the routing arcs to the destination device.

20. The logic of claim 19, wherein the first and second ends of each routing arc each terminate at one of the destination device, a second network node directly coupled to the destination device, or a junction node of another routing arc and having at least two non-congruent paths for reaching the destination device.