Side_1_360

The standard link-state IGP flooding algorithm
distributes these additional link attributes to all
routers in the routing domain. The edge routers,
usually ingress LSRs, use this information,
together with traditional topology information
and administrative input, for online calculation
of LSP paths (see 4.2).

4.2 Path Selection

Paths can be computed automatically by the
underlying routing protocols, or they can be
defined administratively by a network operator.
If there are no resource requirements or restric-
tions associated with an LSP, then a topology
driven protocol can be used to select its path.
LSPs routed in this manner are called control-
driven or hop-by-hop LSPs. However, if re-
source requirements or policy restrictions exist,
then a constraint-based routing scheme should
be used for path selection.

There are a number of ways to route an LSP:

1 The full path for the LSP may be calculated
offline;

2 A partial path for the LSP may be calculated
offline, permitting online calculation in the
ingress router to determine the full path;

3 The full path for the LSP may be calculated
online, based on the input of LSP constraints;

4 The full path for the LSP may be calculated
online, with no input of LSP constraints.

Cases 1 and 2 are described in 4.2.3, while case
3 is described in 4.2.2. Case 4 above results in
normal IGP shortest-path routing for the LSP,
and no further description is given here.

4.2.1 The CSPF Algorithm
Constrained shortest path first (CSPF) is a short-
est path first (SPF) algorithm that has been mod-
ified to take into account specific restriction
when calculating the shortest path across the net-
work. Constraint-based routing becomes rela-
tively simple when this algorithm is used. The
algorithm seems to be convenient for online path
selection, where one LSP path is calculated at a
time. However, when multiple LSPs are to be
routed, CSPF may have difficulty finding feasi-
ble routes even if they exist.

The CSPF algorithm requires input of the type:

• Topology link-state information;


• Attributes associated with the state of network
  resources (link attributes, see 4.1);
  
  
  • Administrative attributes required to support
    traffic traversing the LSP (e.g. bandwidth
    requirements, maximum hop count, adminis-
    trative policy requirements).
  
  
  
  

All candidate nodes and links for a new LSP are

considered. CSPF rejects all path components

that do not meet the route requirements (con-

straints). The output of the CSPF calculation is

an explicit route consisting of a sequence of LSR

addresses that provides the shortest path that

meets the constraints.

[JUNOS] presents the CSPF implementation

from Juniper Networks. Since a description of

such detail is lacking from other material that

has been studied, their solution may be studied

to get a more detailed impression of the CSPF

concept.

4.2.2 Online Path Selection

Each router maintains network link attributes

and topology information in a database. The in-

formation is placed in the database after being

flooded by the IGP.

Each ingress router uses this database to calcu-

late the paths for its own set of LSPs across the

MPLS domain. The path for each LSP can be

represented by either a strict or loose explicit

route. If the ingress router specifies all the LSRs

in the LSP, the LSP is identified by a strict ex-

plicit route. If the ingress router specifies only

some of the LSRs in the LSP, the LSP is de-

scribed by a looseexplicit route.

The ingress router may apply a CSPF algorithm

(see 4.2.1) to the information in the database to

determine the LSP paths.

4.2.3 Offline Path Selection

An administratively specified explicit path for an

LSP is configured through operator action. The

path may be completely specified or partially

specified. The path is completely specified if all

the hops between the LSP endpoints are identi-

fied. The path is partly specified if only some of

the hops are identified, leaving the completion of

the path selection to online route calculation.

When a path has been fully calculated offline,

the LSP may be instantiated in two ways. Each

router in the LSP may be individually config-

ured with the necessary static forwarding state.

Alternatively, the ingress router may be config-

ured with the full path. The ingress router then

uses [CR-LDP] or [RSVP-TE] as a dynamic sig-

nalling protocol to install forwarding state in

each router along the LSP. The resulting LSP

is termed a strict ER-LSP.