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

A method of providing fast rerouting in a label switch router in a network comprising:

• assigning a first local label for an address prefix;
• assigning a second local label for said address prefix;
• advertising said first local label to an upstream peer;
• advertising said second local label to a downstream peer;
• learning a label for said address prefix from said upstream peer;
• learning a label for said address prefix from said downstream peer;
• installing said first local label for an address prefix and said label learned from said upstream peer into a forwarding data structure;
• installing said second local label for an address prefix and said label learned from said downstream peer into said forwarding data structure;
• and
• inspecting and correcting looping paths occurring in path vectors for upstream paths;
• wherein said correcting and inspecting looping paths comprises:
• inspecting, at said label switch router, the set of path vectors received from upstream routers;
• determining if said label switch router appears in more than one path vector;
• when said label switch router does not appear in more than one path vector then determining there is no loop;
• and
• when said label switch router appears in more than one path vector then creating a set of truncated vectors, said creating a set of vectors comprising:
• removing the router and any router that follows said label switch router in the path vector;
• and
• using a marking scheme to trace a path that traffic follows when said label switch router fails.

A computer system for label switch routing 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 an address prefix;
• assigning a second local label for said address prefix;
• advertising said first local label to an upstream peer;
• and
• advertising said second local label to a downstream peer;
• wherein the first local label and the second local label are distinct;
• and
• wherein the first local label designates a normal path towards a destination router indicated by said address prefix, while the second local label indicates an alternate path towards the destination router indicated by said address prefix.

A computer system for label switch routing comprising:

• a memory;
• a processor;
• a communications interface;
• and
• an interconnection mechanism coupling the memory, the processor and the communications interface;
• 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 an address prefix;
• assigning a second local label for said address prefix;
• advertising said first local label to an upstream peer;
• and
• advertising said second local label to a downstream peer;
• wherein said system further performs the operation of learning a label for said address prefix from said upstream peer;
• wherein said system further performs the operation of learning a label for said address prefix from said downstream peer;
• wherein said system further performs the operation of installing said first local label for an address prefix and said label learned from said upstream peer into a forwarding data structure;
• wherein said system further performs the operation of installing said second local label for an address prefix and said label learned from said downstream peer into said forwarding data structure;
• wherein said system further performs the operation of inspecting and correcting looping paths occurring in path vectors for upstream paths;
• and
• 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 set of truncated vectors, said creating a 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.

A system for label switch routing providing fast rerouting in a network comprising:

• means for assigning a first local label for an address prefix;
• means for assigning a second local label for said address 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 address prefix prefix to said second local label for said address prefix when a failure of a link or next hop is detected;
• wherein the first local label and the second local label are distinct;
• and
• wherein the first local label designates a normal path towards a destination router indicated by said address prefix, while the second local label indicates an alternate path towards the destination router indicated by said address prefix.