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-9929938-B2
Application number	US-201615087919-A
Country	US
Kind code	B2
Filing date	Mar 31, 2016
Priority date	Sep 14, 2012
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

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 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;
wherein the prescribed ring topology includes a first ring of routers and a second ring of routers having two or more interconnections with at least the first ring, the prescribed ring topology providing a sequential path of routing arcs for reaching the 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 , 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.

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

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

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

8. The method of claim 1 , wherein the prescribed ring topology includes a sequence of rings of routers for reaching the destination network node.

9. One or more non-transitory tangible media encoded with logic for execution and when executed operable for:
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 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;
wherein the prescribed ring topology includes a first ring of routers and a second ring of routers having two or more interconnections with at least the first ring, the prescribed ring topology providing a sequential path of routing arcs for reaching the destination network node.

10. The one or more non-transitory tangible media of claim 9 , 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 logic further including instructions for:
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.

11. The one or more non-transitory tangible media of claim 10 , further including instructions for:
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 reac

Assignees

• Cisco Tech Inc

Inventors

• Thubert Pascal
• Bellagamba Patrice
• Anteunis Dirk

Classifications

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/18 Primary

  Loop-free operations · CPC title

• H04L2012/421

  Interconnected ring systems · CPC title

• H04L45/28

  using route fault recovery · CPC title

• H04L45/50

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