Selective label switched path re-routing

Patent metadata

Field	Value
Publication number	US-9253097-B1
Application number	US-201314042642-A
Country	US
Kind code	B1
Filing date	Sep 30, 2013
Priority date	Dec 28, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

In one example, a method includes establishing a plurality of label switched paths (LSPs) having a common transit network device other than an ingress network device or an egress network device of any of the plurality of LSPs, and, by the transit network device along the plurality of LSPs, detecting a congestion condition on a link along the plurality of LSPs and coupled to the transit network device. The method also includes, responsive to detecting the congestion condition, and by the transit network device, selecting a subset of the plurality of LSPs to evict from the link, wherein the subset comprises less than all of the plurality of LSPs, and updating a forwarding plane of the transit network device to reroute network traffic received for the selected subset of the plurality of the LSPs for forwarding to a next hop on a bypass LSP that avoids the link.

First claim

The invention claimed is:

1. A method comprising:
establishing a plurality of label switched paths (LSPs) having a common transit network device other than an ingress network device or an egress network device of any of the plurality of LSPs;
by the transit network device along the plurality of LSPs, detecting a congestion condition on a link along the plurality of LSPs and coupled to the transit network device;
responsive to detecting the congestion condition, and by the transit network device, selecting a subset of the plurality of LSPs to evict from the link, wherein the subset comprises less than all of the plurality of LSPs;
outputting an error message to one or more ingress network devices associated with the selected subset of the plurality of LSPs to evict from the link, without outputting an error message to the ingress network devices associated with those of the plurality of LSPs not selected to evict from the link, wherein the error message specifies the respective one of the selected subset of LSPs; and
updating a forwarding plane of the transit network device to reroute network traffic received for the selected subset of the plurality of the LSPs for forwarding to a next hop on a bypass LSP that avoids the link.

2. The method of claim 1 , further comprising:
by the transit network device, presenting a plurality of options for selection, wherein each of the plurality of options corresponds to a different algorithm to be used by the transit network device for selecting a subset of the plurality of LSPs to evict from the link, wherein the subset comprises less than all of the plurality of LSPs;
receiving an indication of a selected one of the plurality of options;
wherein selecting the subset comprises in response to detecting the congestion condition, and by the transit network device, invoking executable instruction in a routing component of a network device to execute the algorithm corresponding to the selected one of the plurality of options to select the subset of the plurality of LSPs to evict from the link, wherein the subset comprises less than all of the plurality of LSPs.

3. The method of claim 1 , wherein the next hop of the bypass LSP is previously installed to forwarding information prior to detecting the congestion condition, and wherein updating the forwarding plane comprises making the next hop of the bypass LSP the primary next hop for the selected subset of the plurality of the LSPs.

4. The method of claim 1 , further comprising subsequent to rerouting the network traffic to a next hop on a bypass LSP, deleting a previous primary next hop associated with the selected subset of the plurality of the LSPs.

5. The method of claim 1 , wherein the link is a bundled link composed of two or more component links, and wherein detecting the congestion condition comprises detecting the congestion condition in response to determining that one or more of the component links has become inoperable.

6. The method of claim 5 , further comprising by the transit network device, detecting that one or more of the component links becomes inoperable using a connectivity fault detection protocol.

7. The method of claim 1 , wherein detecting the congestion condition comprises detecting that a bandwidth capacity of the link has become reduced.

8. The method of claim 1 , wherein detecting the congestion condition comprises detecting that the link is experiencing congestion, wherein the congestion is due to un-policed traffic being sent on the link.

9. The method of claim 1 , wherein outputting the error message comprises outputting an Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE) PathErr message.

10. The method of claim 9 , wherein the RSVP-TE PathErr message comprises a Soft Preemption Reroute Request message that requests the ingress network device to which the message is sent to reroute the selected LSP.

11. The method of claim 9 , wherein the RSVP-TE PathErr message specifies an error code that indicates a link congestion condition and requests the ingress network device to reroute the selected LSP to avoid the link.

12. The method of claim 1 , wherein outputting the error message comprises outputting an RSVP-TE Path Tear message initiating teardown of the selected LSP, the method further comprising:
by the transit network device, removing forwarding state associated with the selected LSP prior to receiving a response to the Path Tear message from the associated ingress network device.

13. The method of claim 1 , wherein selecting the subset of the plurality of LSPs to evict from the link comprises selecting based on one or more of hold-priority of the LSPs, ingress device indication of switch-away, and bandwidth protection availability.

14. The method of claim 1 , wherein selecting a subset of the plurality of LSPs to evict from the link comprises one of:
selecting one or more LSPs to evict such that a sum of the reserved bandwidth of those of the plurality of LSPs that were not selected to evict from the link is maximized, and wherein the maximized sum is less than or equal to an amount of reservable bandwidth of the link; and
selecting one or more LSPs to evict so as to minimize a number of LSPs in the subset of the plurality of LSPs to evict from the link, wherein the sum of the reserved bandwidth for each of the plurality of LSPs that were not selected is less than or equal to an amount of reservable bandwidth of the link.

15. The method of claim 1 , wherein selectin a subset of the plurality of LSPs to evict from the link comprises:
sorting LSPs of the plurality of LSPs on the link in decreasing order of reserved bandwidth;
determining a set of the LSPs which of the LSPs have the largest bandwidth and for which the sum of the bandwidth of the set of the LSPs is less than or equal to an amount of reservable bandwidth of the link; and
selecting the subset as those LSPs of the plurality of LSPs that are not members of the determined set.

16. The method of claim 1 , wherein a subset of the plurality of LSPs to evict from the link comprises:
sorting LSPs of the plurality of LSPs on the link in increasing order of reserved bandwidth;
determining a set of the LSPs which of the LSPs have the smallest bandwidth and for which the sum of the bandwidth of the set of the LSPs is less than or equal to an amount of reservable bandwidth of the link; and
selecting the subset as those LSPs of the plurality of LSPs that are not members of the determined set.

17. The method of claim 1 , wherein selecting a subset of the plurality of LSPs to evict from the link comprises randomly selecting the subset of LSPs to evict, wherein the sum of the reserved bandwidth for each of the plurality of LSPs that were not selected is less than or equal to an amount of reservable bandwidth of the link.

18. The method of claim 1 , further comprising:
after the selected subset of the plurality of LSPs have been rerouted to avoid the link, and by the transit network device, forwarding network traffic on the link using those of the plurality of LSPs that were not selected to evict from the link.

19. A network device comprising:
a hardware-based processor;
a Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE) module executing on the hardware-based processor, wherein the RSVP-TE module establishes a plurality of label switched paths (LSPs) having the network device as a common transit network device other than an ingress network device or an egress network device of any of the plurality of LSPs; and

Assignees

• Juniper Networks Inc

Inventors

• Barman Dhiman
• Minei Ina
• Dai Minjie
• Shen Yimin
• Torvi Raveendra
• Bahadur Nitin

Classifications

• H04L45/22 Primary

  Alternate routing · CPC title

• H04L47/122 Primary

  by diverting traffic away from congested entities · CPC title

• H04L45/28

  using route fault recovery · CPC title

• H04L45/50

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