Generating a loop-free routing topology using routing arcs

• US 10,348,611 B2
• Filed: 07/18/2016
• Issued: 07/09/2019
• 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
• Primary Examiner(s): Sloms, Nicholas
• Application Number:
  US15/212,639
• Publication Number:
  US 20160330105A1
• Time in Patent Office: 1,086 Days
• Field of Search: None
• 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, by an apparatus in a computing network, a loop-free routing topology for reaching a destination device, the loop-free routing topology comprising a plurality of routing arcs, the routing arcs created by the apparatus and including a first routing arc terminating at the destination device and a second routing arc configured for supplying network traffic to the first routing arc, the network traffic originated by at least one source network node, each routing arc comprising a first network device as a corresponding first end of the routing arc, a second network device as a corresponding second end of the routing arc, and at least a third network device distinct from the source network node and configured for routing any network traffic along the routing arc toward the destination device via any one of the first or second available ends of the routing arc, wherein the creating of said each routing arc by the apparatus includes the apparatus providing both the first end and the second end for exiting of the corresponding any network traffic from the corresponding routing arc toward the destination device, the routing arcs of the loop-free routing topology guaranteeing that each network device in the loop-free routing topology has at least two non-congruent paths, that do not share any common data link, for reaching the destination device; and

causing, by the apparatus, the network traffic to be forwarded along at least the first and second of the routing arcs to the destination device, the causing including causing network traffic in at least one of the routing arcs to be selectively instantaneously redirected, without creating a loop, based on reversing a reversible link in the at least one routing arc, wherein;

the first and second ends of the first routing arc connected to the destination device;

the first end of the second routing arc terminates at the first routing arc and the second end of the second routing arc terminates at one of the first routing arc, the destination device, or another routing arc;

wherein at least the first routing arc 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 one or more inward oriented links from any other network device of the first routing arc, each reversible link being reversible without creating a loop in the loop-free routing topology.

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 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.

4. The method of claim 1, 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.

5. The method of claim 4, 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.

6. 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;

the first routing arc comprising two or more of the junction nodes and one or more reversible links; and

the second routing arc created after the first routing arc, 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.

7. The method of claim 6, wherein the creating of the second routing arc 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 routing arc a first end of the second routing arc; 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 routing arc.

8. An apparatus comprising:

a processor circuit configured for creating, for a computing network, a loop-free routing topology for reaching a destination device, the loop-free routing topology comprising a plurality of routing arcs, the routing arcs created by the processor circuit including a first routing arc terminating at the destination device and a second routing arc configured for supplying network traffic to the first routing arc, the network traffic originated by at least one source network node, each routing arc comprising a first network device as a corresponding first end of the routing arc, a second network device as a corresponding second end of the routing arc, and at least a third network device distinct from the source network node and configured for routing any network traffic along the routing arc toward the destination device via any one of the first or second available ends of the routing arc, wherein the creating of said each routing arc includes providing both the first end and the second end for exiting of the corresponding any network traffic from the corresponding routing arc toward the destination device;

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, the routing arcs of the loop-free routing topology guaranteeing that each network device in the loop-free routing topology has at least two non-congruent paths, that do not share any common data link, for reaching the destination device;

the processor circuit configured for causing network traffic to be forwarded along at least the first and second of the routing arcs to the destination device, the processor circuit further configured for causing network traffic in at least one of the routing arcs to be selectively instantaneously redirected, without creating a loop, based on reversing a reversible link in the at least one routing arc, wherein;

the first and second ends of the first routing arc connected to the destination device;

the first end of the second routing arc terminates at the first routing arc and the second end of the second routing arc terminates at one of the first routing arc, the destination device, or another routing arc;

wherein at least the first routing arc 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 one or more inward oriented links from any other network device of the first routing arc, each reversible link being reversible without creating a loop in the loop-free routing topology.

9. The apparatus of claim 8, 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.

10. The apparatus of claim 8, 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.

11. The apparatus of claim 8, 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.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 8, 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.

14. The apparatus of claim 13, 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 arcs 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.

15. One or more non-transitory tangible media for execution by a machine, having logic stored thereon that, when executed by the machine, performs the operations of:

creating, in a computing network, a loop-free routing topology for reaching a destination device, the loop-free routing topology comprising a plurality of routing arcs, the routing arcs including a first routing arc terminating at the destination device and a second routing arc configured for supplying network traffic to the first routing arc, the network traffic originated by at least one source network node, each routing arc comprising a first network device as a corresponding first end of the routing arc, a second network device as a corresponding second end of the routing arc, and at least a third network device distinct from the source network node and configured for routing any network traffic along the routing arc toward the destination device via any one of the first or second available ends of the routing arc, wherein the creating of said each routing arc by the machine includes the machine providing both the first end and the second end for exiting of the corresponding any network traffic from the corresponding routing arc toward the destination device, the routing arcs of the loop-free routing topology guaranteeing that each network device in the loop-free routing topology has at least two non-congruent paths, that do not share any common data link, for reaching the destination device; and

causing the network traffic to be forwarded along at least the first and second of the routing arcs to the destination device, the causing including causing network traffic in at least one of the routing arcs to be selectively instantaneously redirected, without creating a loop, based on reversing a reversible link in the at least one routing arc, wherein;

the first and second ends of the first routing arc connected to the destination device;

the first end of the second routing arc terminates at the first routing arc and the second end of the second routing arc terminates at one of the first routing arc, the destination device, or another routing arc;

wherein at least the first routing arc 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 one or more inward oriented links from any other network device of the first routing arc, each reversible link being reversible without creating a loop in the loop-free routing topology.

16. The one or more non-transitory tangible media of claim 15, 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.

17. The one or more non-transitory tangible media of claim 16, 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;

the first routing arc comprising two or more of the junction nodes and one or more reversible links; and

the second routing arc created after the first routing arc, 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 one or more non-transitory tangible media of claim 17, wherein the creating of the second routing arc 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 routing arc a first end of the second routing arc; 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 routing arc.