Hierarchal label distribution and route installation in a loop-free routing topology using routing arcs at multiple hierarchal levels for ring topologies

Patent metadata

Field	Value
Publication number	US-9338086-B2
Application number	US-201213620677-A
Country	US
Kind code	B2
Filing date	Sep 14, 2012
Priority date	Sep 14, 2012
Publication date	May 10, 2016
Grant date	May 10, 2016

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 network node, each routing arc comprising a first network node as a first end of the routing arc, a second network node as a second end of the routing arc, and at least a third network node configured for routing any network traffic along the routing arc toward the destination node via any one of the first or second ends of the routing arc, at least one of the first, second, or third network nodes are implemented as a ring-based network having a prescribed ring topology; and establishing loop-free label switched paths for reaching the destination network node via the routing arcs of the loop-free routing topology, the label switched paths independent and distinct from any attribute of the prescribed ring topology.

First claim

What is claimed is:

1. A method comprising:
creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node, each routing arc comprising a first network node as a first end of the routing arc, a second network node as a second end of the routing arc, and at least a third network node configured for routing any network traffic along the routing arc toward the destination network node and exiting via any one of the first or second ends of the routing arc for non-congruent paths that do not share a common data link to the destination network node, at least one of the first, second, or third network nodes are implemented as a ring-based network having a prescribed ring topology; and
establishing loop-free label switched paths for reaching the destination network node via the routing arcs of the loop-free routing topology, the label switched paths independent and distinct from any attribute of the prescribed ring topology;
wherein the prescribed ring topology includes a first ring of routers, a second ring of routers that is concentric to the first ring, and at least one link between the first ring and the second ring, the prescribed ring topology providing a sequential path of arcs for reaching the at least one destination network node.

2. The method of claim 1 , wherein the routing arcs for reaching the destination network node are identified as primary routing arcs in a primary hierarchal level of the loop-free routing topology and the respective label switched paths are identified as primary hierarchal level label switched paths, the method further comprising:
creating a second hierarchal level of secondary routing arcs having secondary hierarchal level label switched paths within the ring-based network of the at least one network node, each secondary routing arc within the ring-based network of the at least one network node providing reachability from the ring-based network to an adjacent network node in the primary hierarchal level.

3. The method of claim 2 , further comprising creating a third hierarchal level of tertiary routing arcs, having tertiary hierarchal level label switched paths, within at least one of the secondary routing arcs, the tertiary hierarchal level label switched paths independent and distinct from any of the secondary hierarchal level label switched paths, the tertiary routing arcs providing reachability within the at least one secondary routing arc to the adjacent network node.

4. The method of claim 3 , wherein the third hierarchal level of tertiary routing arcs provides the sequential path of arcs for reaching the at least one destination network node.

5. The method of claim 3 , further comprising:
adding, by a first router in the at least one network node, a primary hierarchal level switching label in response to detecting a data packet destined for the destination network node, for reaching the destination network node via the primary hierarchal level;
adding, by the first router, a secondary hierarchal label switched label to the data packet for reaching the adjacent network node in the primary hierarchal level via a corresponding one of the secondary routing arcs in a first direction;
adding, by the first router, a tertiary hierarchal level switching label to the data packet for reaching a second router along the one secondary routing arc via a corresponding first of the tertiary routing arcs.

6. The method of claim 2 , wherein the creating of the second hierarchal level of secondary routing arcs includes creating the secondary routing arcs between contiguous intersections between the at least one network node and the adjacent network node.

7. The method of claim 2 , further comprising a router along one of the secondary routing arcs swapping a secondary hierarchal label switched label, in a received data packet traversing along the one secondary routing arc in a first direction, with an alternate secondary hierarchal label for one of an alternate direction of the one secondary routing arc, or another secondary routing arc in the ring-based network, based on a determined unreachability of the adjacent network node along the one secondary routing arc in the first direction.

8. The method of claim 1 , further comprising:
receiving, by a first router in the first network node, a data packet from the corresponding routing arc, the data packet specifying a primary hierarchal level switching label for the first router in the loop-free routing topology for reaching the destination network node;
swapping, by the first router, the primary hierarchal level switching label in the data packet with a second primary hierarchal level switching label for a downstream network node coupled to the first router and having a distinct ring topology;
in response to the first router determining the second network node is unreachable, successively swapping the second primary hierarchal level switching label with another primary hierarchal level switching label for another downstream network node coupled to the first router and having a distinct ring topology;
if none of the downstream network nodes coupled to the first router are reachable, swapping the primary hierarchal level switching label with a primary hierarchal level fast reroute switching label for transmitting the data packet toward the destination via the corresponding routing arc in an alternate direction.

9. A method comprising:
receiving, by a router, a data packet destined for a destination network node in a loop-free routing topology in a computing network, the loop-free routing topology comprising a plurality of routing arcs for reaching the destination network node, each routing arc comprising a first network node as a first end of the routing arc, a second network node as a second end of the routing arc, and at least a third network node configured for routing any network traffic along the routing arc toward the destination network node and exiting via any one of the first or second ends of the routing arc for non-congruent paths that do not share a common data link to the destination network node, at least one of the first, second, or third network nodes implemented as a ring-based network having a prescribed ring topology containing the router; and
the router adding to the data packet a primary hierarchal level switching label providing a loop-free label switched path for reaching the destination network node via the routing arcs of the loop-free routing topology, each of the label switched paths in the loop-free routing topology independent and distinct from any attribute of the prescribed ring topology;
wherein the prescribed ring topology includes a first ring of routers, a second ring of routers that is concentric to the first ring, and at least one link between the first ring and the second ring, the prescribed ring topology providing a sequential path of arcs for reaching the at least one destination network node.

10. The method of claim 9 , wherein the routing arcs for reaching the destination network node are identified as primary routing arcs in a primary hierarchal level in the loop-free routing topology and the respective label switched paths are identified as primary hierarchal level label switched paths, the method further comprising:
the router adding to the data packet a secondary hierarchal level switching label for a second hierarchal level of a secondary routing arc having a secondary hierarchal level label switched path within the ring-based network, the secondary routing arc providing reachability from the router in the ring-based network to an adjacent network node in the primary hierarchal level.

11. The method of claim

Assignees

• Thubert Pascal
• Bellagamba Patrice
• Anteunis Dirk
• Cisco Tech Inc

Inventors

• Thubert Pascal
• Bellagamba Patrice
• Anteunis Dirk

Classifications

• H04L45/18 Primary

  Loop-free operations · CPC title

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L2012/421

  Interconnected ring systems · CPC title

• H04L45/28

  using route fault recovery · CPC title

• H04L12/4637

  Interconnected ring systems · CPC title