Disjoint Path Computation Algorithm
First Claim
1. A method performed on a network element implementing Multiprotocol Label Switching (MPLS) to automatically create an optimal deterministic back-up Label Switch Path (LSP) that is maximally disjointed from a primary LSP to provide a reliable back up to the primary LSP, the method comprising the steps of:
- receiving a request for a generation of an LSP by the network element via a signaling protocol;
determining that the request for the generation of the LSP is for the back-up LSP;
locating each link of the primary LSP in a traffic engineering database in response to determining that the request is for the back-up LSP;
modifying each link of the primary LSP in the traffic engineering database to have a link cost other than an actual link cost to discourage use of each link of the primary LSP in the back-up LSP;
executing a Constrained Shortest Path First (CSPF) algorithm on the traffic engineering database to obtain the back-up LSP, wherein the back-up LSP has a maximum disjointedness from the primary LSP due to a modified cost of each link of the primary LSP in the traffic engineering database; and
returning the back-up LSP via the signaling protocol.
2 Assignments
0 Petitions
Accused Products
Abstract
A network element implementing Multiprotocol Label Switching to automatically create an optimal deterministic back-up Label Switch Path (LSP) that is maximally disjointed from a primary LSP to provide a reliable back up to the primary LSP. The network element receives a request for a generation of an LSP, determines that the request for the generation of the LSP is for the back-up LSP, locates each link of the primary LSP in a traffic engineering database, modifies each link of the primary LSP to have a link cost significantly greater than an actual link cost to discourage use of each link of the primary LSP in the back-up LSP, executes a Constrained Shortest Path First algorithm to obtain the back-up LSP, wherein the back-up LSP has a maximum disjointedness from the primary LSP due to a modified cost of each link of the primary LSP, and returns the back-up LSP.
26 Citations
18 Claims
-
1. A method performed on a network element implementing Multiprotocol Label Switching (MPLS) to automatically create an optimal deterministic back-up Label Switch Path (LSP) that is maximally disjointed from a primary LSP to provide a reliable back up to the primary LSP, the method comprising the steps of:
-
receiving a request for a generation of an LSP by the network element via a signaling protocol; determining that the request for the generation of the LSP is for the back-up LSP; locating each link of the primary LSP in a traffic engineering database in response to determining that the request is for the back-up LSP; modifying each link of the primary LSP in the traffic engineering database to have a link cost other than an actual link cost to discourage use of each link of the primary LSP in the back-up LSP; executing a Constrained Shortest Path First (CSPF) algorithm on the traffic engineering database to obtain the back-up LSP, wherein the back-up LSP has a maximum disjointedness from the primary LSP due to a modified cost of each link of the primary LSP in the traffic engineering database; and returning the back-up LSP via the signaling protocol. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system for implementing Multiprotocol Label Switching (MPLS) to automatically create an optimal deterministic back-up Label Switch Path (LSP) that is maximally disjointed from a primary LSP to provide a reliable back up to the primary LSP, the system comprising:
-
a label switch router adapted to receive a request for a generation of an LSP and adapted to call a path computation element to obtain the LSP and to return the LSP to a requestor; and the path computation element (PCE) coupled to the label switch router, the PCE adapted to determine whether the request for the generation of the LSP is for a back-up LSP, wherein the PCE is adapted to locate each link of the primary LSP in a traffic engineering database, wherein the PCE is adapted to modify each link of the primary LSP in the traffic engineering database to have a modified cost, wherein the modified cost discourages use of a link of the primary LSP in the back-up LSP, wherein the PCE is adapted to execute a Constrained Shortest Path First (CSPF) algorithm on the traffic engineering database to obtain the back-up LSP, wherein the back-up LSP has a maximum disjointedness from the primary LSP due to the modified cost of each link of the primary LSP used in the back-up LSP calculation and wherein the PCE is adapted to return the back-up LSP to the first label switch router. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A network element for implementing Multiprotocol Label Switching (MPLS) to create an optimal deterministic back-up Label Switch Path (LSP) that is maximally disjointed from a primary LSP to provide a reliable back up to the primary LSP, the network element comprising:
-
a traffic engineering database adapted to store link state information for a network topology including link state information for a primary LSP; a back-up path calculation module coupled to the traffic engineering database and adapted to process a request for the back-up LSP, the back-up path calculation module is adapted to locate each link of the primary LSP in a traffic engineering database and to modify each link of the primary LSP in the traffic engineering database to have a cost other than an actual cost to discourage use of each link of the primary LSP in the back-up LSP; and a best path determination module coupled to the back-up path calculation module to determine a best path to a destination node using the link state information from the traffic engineering database. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification