Method and apparatus using multiprotocol label switching (MPLS) label distribution protocol (LDP) to establish label switching paths (LSPS) for directed forwarding

• US 20070036072A1
• Filed: 08/15/2005
• Published: 02/15/2007
• Est. Priority Date: 08/15/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thomas, Robert, Vaithilingam, Prabhu, Raj, Alex
• Granted Patent: US 7,609,620 B2
• Time in Patent Office: Days
• US Class Current: 370/225
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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]

Abstract

A method and apparatus method for providing fast rerouting in a network is presented. The method and apparatus assign a first local label for a prefix, and assign a second local label for the prefix. The first local label is advertised to an upstream peer and the second local label is advertised to a downstream peer. A forwarding entry from the first local label for a prefix is switched to the second local label for the prefix when a failure of a link or next hop is detected.

Claims

1. A method of providing fast rerouting in a network comprising:

assigning a first local label for a prefix;

assigning a second local label for said prefix;

advertising said first local label to an upstream peer; and

advertising said second local label to a downstream peer.

2. The method of claim 1 further comprising learning a label for said prefix from said upstream peer.

3. The method of claim 2 further comprising learning a label for said prefix from said downstream peer.

4. The method of claim 3 further comprising installing said first local label for a prefix and said label learned from said upstream peer into a forwarding data structure.

5. The method of claim 4 further comprising installing said second local label for a prefix and said label learned from said downstream peer into said forwarding data structure.

6. The method of claim 5 further comprising switching a forwarding entry from said first local label for said prefix to said second local label for said prefix when a failure of a link or next hop is detected.

7. The method of claim 1 wherein said assigning a second local label for said prefix comprises:

determining a set of path vectors having a merge point with a path defined by said first local label; and

selecting, from said set of path vectors, a selected path vector having the fewest number of hops to a destination device.

8. The method of claim 5 further comprising inspecting and correcting looping paths occurring in path vectors for upstream paths.

9. The method of claim 8 wherein said correcting and inspecting looping paths comprises:

inspecting, at a router, the set of path vectors received from upstream routers;

determining if the router appears in more than one path vector;

when said router does not appear in more than one path vector then determining there is no loop; and

when said router appears in more than one path vector then creating a new set of truncated vectors, said creating a new set of vectors comprising;

removing the router and any router that follows said router in the path vector; and

using a marking scheme to trace a path that traffic follows when said router fails.

10. The method of claim 9 wherein said using a marking scheme comprises:

selecting a path vector as a current path vector;

determining if the current path vector is marked as looping and when said current path vector is marked as looping then consideration of the current path vector is complete;

when said current path vector is not marked as looping then determining if a second path vector has a first element equal to the last element of the current path vector;

when said second path vector has a first element equal to the last element of the current path vector, then marking the current path vector as looping and marking the second path vector as looping;

when said second path vector does not have a first element equal to the last element of the current path vector, then marking the second path vector as loopfree and marking the current path vector as loopfree;

determining if all path vectors have a label;

when all path vectors have a label then terminating the marking process; and

when all path vectors do not have a label then designating an unlabeled vector as the current vector and repeating said steps of determining if the current path vector is marked as looping, determining if a second path vector has a first element equal to the last element of the current path vector, and said determining if all path vectors have a label.

11. A computer system comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with an application that when performed on the processor, provides a fast rerouting process for processing information, the process causing the computer system to perform the operations of;

assigning a first local label for a prefix;

assigning a second local label for said prefix;

advertising said first local label to an upstream peer; and

advertising said second local label to a downstream peer.

12. The computer system of claim 11 wherein said system further performs the operation of learning a label for said prefix from said upstream peer.

13. The computer system of claim 12 wherein said system further performs the operation of learning a label for said prefix from said downstream peer.

14. The computer system of claim 13 wherein said system further performs the operation of installing said first local label for a prefix and said label learned from said upstream peer into a forwarding data structure.

15. The computer system of claim 14 wherein said system further performs the operation of installing said second local label for a prefix and said label learned from said downstream peer into said forwarding data structure.

16. The computer system of claim 15 wherein said system further performs the operation of switching a forwarding entry from said first local label for said prefix to said second local label for said prefix when a failure of a link or next hop is detected.

17. The computer system of claim 11 wherein said assigning a second local label for said prefix comprises:

determining a set of path vectors having a merge point with a path defined by said first local label; and

selecting, from said set of path vectors, a selected path vector having the fewest number of hops to a destination device.

18. The computer system of claim 15 wherein said system further performs the operation of inspecting and correcting looping paths occurring in path vectors for upstream paths.

19. The computer system of claim 18 wherein said correcting and inspecting looping paths comprises said system performing the operation of:

inspecting, at a router, the set of path vectors received from upstream routers;

determining if the router appears in more than one path vector;

when said router does not appear in more than one path vector then determining there is no loop; and

when said router appears in more than one path vector then creating a new set of truncated vectors, said creating a new set of vectors comprising;

removing the router and any router that follows said router in the path vector; and

using a marking scheme to trace a path that traffic follows when said router fails.

20. The computer system of claim 19 wherein said using a marking scheme comprises said system performing the operations of:

selecting a path vector as a current path vector;

determining if the current path vector is marked as looping and when said current path vector is marked as looping then consideration of the current path vector is complete;

when said current path vector is not marked as looping then determining if a second path vector has a first element equal to the last element of the current path vector;

when said second path vector has a first element equal to the last element of the current path vector, then marking the current path vector as looping and marking the second path vector as looping;

when said second path vector does not have a first element equal to the last element of the current path vector, then marking the second path vector as loopfree and marking the current path vector as loopfree;

determining if all path vectors have a label;

when all path vectors have a label then terminating the marking process; and

when all path vectors do not have a label then designating an unlabeled vector as the current vector and repeating said steps of determining if the current path vector is marked as looping, determining if a second path vector has a first element equal to the last element of the current path vector, and said determining if all path vectors have a label.

21. A system providing fast rerouting in a network comprising:

means for assigning a first local label for a prefix;

means for assigning a second local label for said prefix;

means for advertising said first local label to an upstream peer;

means for advertising said second local label to a downstream peer; and

means for switching a forwarding entry from said first local label for said prefix to said second local label for said prefix when a failure of a link or next hop is detected.

22. The system of claim 21 further comprising:

means for assigning a first local label for a prefix;

means for assigning a second local label for said prefix;

means for advertising said first local label to an upstream peer;

means for advertising said second local label to a downstream peer;

means for switching a forwarding entry from said first local label for said prefix to said second local label for said prefix when a failure of a link or next hop is detected;

means for learning a label for said prefix from said upstream peer;

means for a label for said prefix from said downstream peer;

means for installing said first local label for a prefix and said label learned from said upstream peer into a forwarding data structure;

means for installing said second local label for a prefix and said label learned from said downstream peer into said forwarding data structure; and

means for inspecting and correcting looping paths occurring in path vectors for upstream paths.

23. The system of claim 22 wherein said means for correcting and inspecting looping paths comprises:

means for inspecting at a router the set of path vectors received from upstream routers;

means for determining if the router appears in more than one path vector;

means for when said router does not appear in more than one path vector then determining there is no loop; and

means for when said router appears in more than one path vector then creating a new set of truncated vectors, said creating a new set of vectors comprising;

means for removing the router and any router that follows said router in the path vector; and

means for using a marking scheme to trace a path that traffic follows when said router fails.

24. The system of claim 23 wherein said means for using a marking scheme comprises:

means for selecting a path vector as a current path vector;

means for determining if the current path vector is marked as looping and when said current path vector is marked as looping then consideration of the current path vector is complete;

when said current path vector is not marked as looping then means for determining if a second path vector has a first element equal to the last element of the current path vector;

when said second path vector has a first element equal to the last element of the current path vector, then means for marking the current path vector as looping and marking the second path vector as looping;

when said second path vector does not have a first element equal to the last element of the current path vector, then means for marking the second path vector as loopfree and marking the current path vector as loopfree;

means for determining if all path vectors have a label;

when all paths vectors have a label then means for terminating the marking process; and

when all path vectors do not have a label then means for designating an unlabeled vector as the current vector and means for repeating said determining if the current path vector is marked as looping, said determining if a second path vector has a first element equal to the last element of the current path vector, and said determining if all path vectors have a label.