Generating a loop-free routing topology based on merging buttressing arcs into routing arcs

• US 9,413,638 B2
• Filed: 05/09/2012
• Issued: 08/09/2016
• Est. Priority Date: 05/09/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Bellagamba, Patrice
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): CHOWDHURY, HARUN UR R
• Application Number:
  US13/467,603
• Publication Number:
  US 20130301470A1
• Time in Patent Office: 1,553 Days
• Field of Search: 370/217, 370/218, 370/228, 370254-258, 370/222, 370/238, 709/239, 709/241
• US Class Current: 1/1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath

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 routing any network traffic along the routing arc toward the destination device via any one of first or second ends of the corresponding routing arc, the creating including forming a buttressing arc having an originating end joined to a first of the routing arcs and a terminating end joined to a second of the routing arcs, the buttressing arc inheriting from the first routing arc a first height to the destination device, the first height of the first routing arc higher than a corresponding second height of the second routing arc; and causing the network traffic to be forwarded, to the destination device, via the buttressing arc and at least one of the first routing arc or the second routing arc.

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 routing any network traffic along the routing arc toward the destination device and exiting via any one of first or second ends of the corresponding routing arc for non-congruent paths to the destination device, the creating including forming a multipath routing arc based on merging a first of the routing arcs with a buttressing arc having an originating end joined to the first routing arc and a terminating end joined to a second of the routing arcs, the buttressing arc inheriting from the first routing arc a first height to the destination device, the first height of the first routing arc higher than a corresponding second height of the second routing arc, the multipath routing arc having three or more distinct routing paths for reaching the destination based on exiting via the first end of the first routing arc, the second end of the first routing arc, or the terminating end of the buttressing arc; and

causing the network traffic to be forwarded, to the destination device, via the buttressing arc and at least one of the first routing arc or the second routing arc.

2. The method of claim 1, wherein the multipath routing arc includes at least two junction nodes coupled by a reversible link.

3. The method of claim 2, wherein the merging is based on a junction node in the first arc detecting itself as the originating end of the buttressing arc.

4. The method of claim 3, wherein each routing arc comprises one and only one arc cursor that provides exclusive control for directing network traffic away from any network device having possession of the arc cursor, the merging includes a network device of the buttressing arc surrendering a corresponding arc cursor of the buttressing arc to become a first of the junction nodes and to enable control by the corresponding arc cursor of the first arc, enabling a second of the junction nodes to selectively pass the corresponding arc cursor of the first arc to the first junction node for reversal of the reversible link.

5. The method of claim 2, further comprising:

forming a second buttressing arc having a corresponding originating end joined to one of the junction nodes of the multipath routing arc and a corresponding terminating end joined to any routing arc having the corresponding height less than the first height; and

merging the second buttressing arc to the multipath routing arc, enabling addition of another junction node to the multipath routing arc.

6. The method of claim 5, wherein the merging of the second buttressing arc into the multipath routing arc enables movement of an arc cursor, providing exclusive control of directing the network traffic along the multipath routing arc away from any network device having possession thereof, to any of the junction nodes of the multipath routing arc.

7. The method of claim 2, further comprising adding to the multipath routing arc, by at least one of the junction nodes, a buttressing path as one of the distinct routing paths in response to an advertising junction node of another one of the routing arcs advertising a corresponding height less than the corresponding height of the multipath routing arc.

8. The method of claim 1, wherein the buttressing arc is formed based on:

a network device detecting a first network device of the first routing arc advertising the first height;

the network device detecting a second network device of the second routing arc advertising the second height; and

the network device designating the first network device as the originating end based on the first routing arc having the first height greater than the second height, and designating the second network device as the terminating end, enabling the network traffic to be forwarded via the network device to one of the originating end or the terminating end.

9. The method of claim 1, wherein each routing arc comprises 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 of the network traffic along the routing arc toward the destination device via any one of the first or second ends of the routing arc.

10. An apparatus comprising:

a network interface circuit configured for receiving advertisement messages from network devices in a computing network, the advertisement messages advertising respective costs for reaching a destination device; and

a processor circuit configured for operating the apparatus as one of the network devices in the computing network, the processor circuit configured for communicating with the network devices for creating, in the computing network based on the advertisement messages, a loop-free routing topology comprising a plurality of routing arcs for reaching the destination device, each routing arc routing any network traffic along the routing arc toward the destination device and exiting via any one of first or second ends of the corresponding routing arc for non-congruent paths to the destination device, the processor circuit further configured for forming a multipath routing arc based on merging a first of the routing arcs with a buttressing arc having an originating end joined to the first routing arc and a terminating end joined to a second of the routing arcs, the buttressing arc inheriting from the first routing arc a first height to the destination device, the first height of the first routing arc higher than a corresponding second height of the second routing arc, the multipath routing arc having three or more distinct routing paths for reaching the destination based on exiting via the first end of the first routing arc, the second end of the first routing arc, or the terminating end of the buttressing arc;

wherein the network traffic can be forwarded, to the destination device, via the buttressing arc and at least one of the first routing arc or the second routing arc.

11. The apparatus of claim 10, wherein the processor circuit is configured for including in the multipath routing arc at least two junction nodes coupled by a reversible link, the apparatus operating as a first of the junction nodes.

12. The apparatus of claim 11, wherein the merging is based on the apparatus in the first arc detecting itself as the originating end of the buttressing arc.

13. The apparatus of claim 12, wherein each routing arc comprises one and only one arc cursor that provides exclusive control for directing network traffic away from any network device having possession of the arc cursor, the merging includes a network device of the buttressing arc surrendering a corresponding arc cursor of the buttressing arc to become a second of the junction nodes and to enable control by the corresponding arc cursor of the first arc, enabling the apparatus as the first junction node to selectively pass the corresponding arc cursor of the first arc to the second junction node for reversal of the reversible link.

14. The apparatus of claim 11, wherein the processing circuit further is configured for:

forming a second buttressing arc having a corresponding originating end joined to the apparatus as a first the junction nodes of the multipath routing arc and a corresponding terminating end joined to any routing arc having the corresponding height less than the first height; and

merging the second buttressing arc to the multipath routing arc, enabling addition of another junction node to the multipath routing arc.

15. The apparatus of claim 14, wherein the merging of the second buttressing arc into the multipath routing arc enables movement of an arc cursor, providing exclusive control of directing the network traffic along the multipath routing arc away from any network device having possession thereof, to any of the junction nodes of the multipath routing arc.

16. The apparatus of claim 11, wherein the processor circuit is configured for adding to the multipath routing arc a buttressing path as one of the distinct routing paths in response to an advertising junction node of another one of the routing arcs advertising a corresponding height less than the corresponding height of the multipath routing arc.

17. The apparatus of claim 10, wherein the processor circuit is configured for forming the buttressing arc based on:

detecting a first network device of the first routing arc advertising the first height;

detecting a second network device of the second routing arc advertising the second height; and

designating the first network device as the originating end based on the first routing arc having the first height greater than the second height, and designating the second network device as the terminating end, enabling the network traffic to be forwarded by the apparatus to one of the originating end or the terminating end.

18. The apparatus of claim 10, wherein each routing arc comprises 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 of the network traffic along the routing arc toward the destination device via any one of the first or second ends of the routing arc.

19. Logic encoded in one or more non-transitory tangible media and when executed causes a processor to:

create, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination device, each routing arc routing any network traffic along the routing arc toward the destination device and exiting via any one of first or second ends of the corresponding routing arc for non-congruent paths to the destination device, the creating including forming a multipath routing arc based on merging a first of the routing arcs with a buttressing arc having an originating end joined to the first routing arc and a terminating end joined to a second of the routing arcs, the buttressing arc inheriting from the first routing arc a first height to the destination device, the first height of the first routing arc higher than a corresponding second height of the second routing arc, the multipath routing arc having three or more distinct routing paths for reaching the destination based on exiting via the first end of the first routing arc, the second end of the first routing arc, or the terminating end of the buttressing arc; and

cause the network traffic to be forwarded, to the destination device, via the buttressing arc and at least one of the first routing arc or the second routing arc.

20. The logic of claim 19, wherein the multipath routing arc includes at least two junction nodes coupled by a reversible link.