US 7,889,641 B2 · Path flow formulation for fast reroute bypass tunnels in MPLS networks

Abstract

A path-flow formulation of defining MPLS FRR bypass LSPs is presented. The path-flow formulation comprises first identifying a set of candidate bypass LSPs, each of which meets various network constraints and has an explicit route around a network facility to be protected. The constraints may include Quality of Service (QoS) guarantees, implementation requirements, network element resource limitations, and resiliency requirements. The constraints may be user-selected, and may be non-linear. The set of candidate bypass LSPs form a linear programming (LP) problem, or an integer linear programming (ILP) problem if the allowable number of bypass LSPs is constrained. In an optimization step, LP solutions are used to select the bypass LSPs from among the candidate bypass LSPs by allocating bandwidth to them.

Claims25

Dependent claims

A method of defining Fast Reroute (FRR) bypass tunnels on a Multi-Protocol Label Switching (MPLS) network using a path-flow formulation, comprising:

specifying a network facility to protect;
computing, using a path-flow formulation, a plurality of candidate bypass Label-Switched Paths (LSP) that protect one or more routes through the facility, satisfy predetermined path and bandwidth constraints, and have explicit routes, to carry traffic flows in the event of a failure of the protected facility;
and
selecting from among the candidate bypass LSPs one or more bypass LSPs by allocating protection bandwidth to the bypass LSPs.

1 more element

A non-transitory computer readable medium including one or more computer programs operative to cause a computer to define Fast Reroute (FRR) bypass Label-Switched Paths (LSP) for a Multi-Protocol Label Switching (MPLS) network using a path-flow formulation, the computer programs operative to cause the computer to perform the steps of:

receiving network topology information;
receiving identification of a network facility to protect;
receiving predetermined path and bandwidth constraints;
computing, using a path-flow formulation, a plurality of candidate bypass LSPs that protect one or more routes through the facility, satisfy the predetermined path and bandwidth constraints, and have explicit routes, to carry traffic flows in the event of a failure of the protected facility;
selecting from among the candidate bypass LSPs one or more bypass LSPs by allocating protection bandwidth to the bypass LSPs;
and
outputting the bypass LSPs.

4 more elements

Dependencies are inferred from the claim text.

Path flow formulation for fast reroute bypass tunnels in MPLS networks

Life of this patent

Path flow formulation for fast reroute bypass tunnels in MPLS networks

Life of this patent

Abstract

Claims25