Loop prevention techniques using encapsulation manipulation of IP/MPLS field

• US 7,477,593 B2
• Filed: 04/04/2005
• Issued: 01/13/2009
• Est. Priority Date: 04/04/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ward, David D., Filsfils, Clarence, Scudder, John Galen
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Chou; Albert T
• Application Number:
  US11/098,173
• Publication Number:
  US 20060221813A1
• Time in Patent Office: 1,380 Days
• Field of Search: 370/216, 370/225, 370/229, 370/242, 709/239
• US Class Current: 370/217
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service

Abstract

A fast reroute (FRR) technique is implemented at the edge of a computer network. In accordance with the technique, if an edge device detects a node or link failure that prevents it from communicating with a neighboring routing domain, the edge device reroutes at least some data packets addressed to that domain to a backup edge device which, in turn, forwards the packets to the neighboring domain. The rerouted packets are designated as being “protected” (i.e., rerouted) data packets before they are forwarded to the backup edge device. To that end, the edge device incorporates an identifier into the rerouted data packets to indicate that the packets are being FRR rerouted. The identifier may be a predetermined value stored at a known location in the rerouted packets'"'"'encapsulation headers, such as in their MPLS or IP headers. Upon receiving a data packet containing the identifier, the backup edge device is not permitted to reroute the packet a second time.

Claims

1. A method for performing fast reroute (FRR) operations at the edge of a computer network, the network having first and second edge devices coupled to a neighboring routing domain, the method comprising:

detecting a loss of communication between the first edge device and the neighboring routing domain;

receiving a data packet at the first edge device, the received data packet containing a destination address that is reachable via the neighboring routing domain;

determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers, the FRR identifier value indicating that the received packet was previously rerouted in accordance with FRR operations;

if the received data packet does not contain the FRR identifier value, rerouting the received data packet to the second edge device for forwarding to the neighboring routing domain; and

if the received data packet does contain the FRR identifier value, dropping the received packet, to prevent loops from developing at the edge of the computer network.

2. The method of claim 1, wherein the step of determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers further comprises:

locating a field in the received data packet'"'"'s IP header; and

determining whether the located field stores the FRR identifier value.

3. The method of claim 2, wherein the located field in the IP header is a differentiated services code point (DSCP) field.

4. The method of claim 1, wherein the step of determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers further comprises:

locating a field in the received data packet'"'"'s IP tunneling header; and

determining whether the located field stores the FRR identifier value.

5. The method of claim 4, wherein the IP tunneling header is a Layer-2 Tunneling Protocol (L2TP) header.

6. The method of claim 5, wherein the located field is a session identifier (ID) field in the L2TP header.

7. The method of claim 1, wherein the step of determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers further comprises:

locating a field in the received data packet'"'"'s MPLS label stack; and

determining whether the located field stores the FRR identifier value.

8. The method of claim 7, wherein the step of locating the field in the received data packet'"'"'s MPLS label stack further comprises:

locating the field in an interior gateway protocol (IGP) label stored in the label stack.

9. The method of claim 8, wherein the located field is one or more experimental (EXP) bits in the IGP label.

10. The method of claim 7, wherein the step of locating the field in the received data packet'"'"'s MPLS label stack further comprises:

locating the field in a virtual private network (VPN) label stored in the label stack.

11. The method of claim 10, wherein the located field is a time-to-live (TTL) field in the VPN label.

12. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node comprising:

a processor;

a first network interface adapted to communicate with a neighboring routing domain;

a second network interface adapted to receive a data packet containing a destination address that is reachable via the neighboring routing domain; and

a memory adapted to store instructions which are executable by the processor for;

detect a loss of communication over the first network interface;

determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers, the FRR identifier value indicating that the received packet was previously rerouted in accordance with FRR operations;

if the received data packet does not contain the FRR identifier value, reroute the received data packet to the second edge device for forwarding to the neighboring routing domain; and

if the received data packet does contain the FRR identifier value, drop the received packet, to prevent loop from developing at the edge of the computer network.

13. The network node of claim 12, wherein the FRR identifier value is stored in at least one header field located in an IP or MPLS encapsulation prepended to the received data packet.

14. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node comprising:

a first network interface adapted to communicate with a neighboring routing domain;

means for detecting a loss of communication over the first network interface;

a second network interface adapted to receive a data packet containing a destination address that is reachable via the neighboring routing domain;

means for determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers, the FRR identifier value indicating that the received packet was previously rerouted in accordance with FRR operations;

means for rerouting, if the received data packet does not contain the FRR identifier value, the received data packet to the second edge device for forwarding to the neighboring routing domain; and

means for dropping, if the received data packet does contain the FRR identifier value, the received packet, to prevent loops from developing at the edge of the computer network.

15. The network node of claim 14, further comprising:

means for storing the FRR identifier value in at least one header field located in an IP or MPLS encapsulation prepended to the received data packet.

16. A computer network, comprising:

a first edge device coupled to a neighboring routing domain; and

a second edge device coupled to the neighboring routing domain, the second edge device being configured to;

detect a loss of communication with the neighboring routing domain;

receive a data packet containing a destination address that is reachable via the neighboring routing domain;

determine whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers, the FRR identifier value indicating that the received packet was previously rerouted in accordance with FRR operations;

if the received data packet does not contain the FRR identifier value, reroute the received data packet to the first edge device for forwarding to the neighboring routing domain; and

if the received packet does contain the FRR identifier value, drop the received packet to prevent loops from developing.

17. The computer network of claim 16, wherein the FRR identifier value is stored in at least one header field located in an IP or MPLS encapsulation prepended to the received data packet.

18. A computer-readable medium storing instructions for execution on a processor for performing fast reroute (FRR) operations at the edge of a computer network, the network having first and second edge devices coupled to a neighboring routing domain, the method comprising instructions for:

detecting a loss of communication between the first edge device and the neighboring routing domain;

receiving a data packet at the first edge device, the received data packet containing a destination address that is reachable via the neighboring routing domain;

determining whether the received data packet contains a FRR identifier value in at least one of its encapsulation headers, the FRR identifier value indicating that the received packet was previously rerouted in accordance with FRR operations;

if the received data packet does not contain the FRR identifier value, rerouting the received data packet to the second edge device for forwarding to the neighboring routing domain; and

if the received data packet does contain the FRR identifier value, dropping the received packet, to prevent loops from developing at the edge of the computer network.

19. The computer-readable medium of claim 18, wherein the FRR identifier value is stored in at least one header field located in an IP or MPLS encapsulation prepended to the received data packet.