Understanding MPLS CSPF

I explained in the previous post how the RSVP-TE Explicit Route Object (ERO) specifies the path of an MPLS LSP by means of a sequenced list of Label Switching Routers (LSRs) that the LSP must pass through between the ingress and egress LSRs. RSVP-TE uses the path described in the ERO to signal and set up the LSP. That’s the foundation of MPLS traffic engineering: The ability to set up a path that is different from what the local IGP considers the optimum path between the ingress and egress, as shown in Figure 1.

In fact, different LSPs between the same two endpoints can take different paths. It all depends on what constraints you place on each LSP. For example, each LSP might require different amounts of reserved bandwidth or might be constrained by the types of links they can use.

The question we were left with at the end of the previous post was: How is the ERO created at the ingress?

You can of course manually configure the ERO for each LSP at each ingress router, but this is administratively challenging. Not only because of the number of LSPs you might have to configure, but also because a sizeable network changes regularly. The constraints you require of an LSP will remain the same, but when the network circumstances change the best path meeting those constraints might change. You don’t want to have to recalculate all of your EROs, for example, every time the available bandwidth on a link somewhere in your network core changes.

As a problem statement, all of this should sound familiar to you.

You use a routing protocol to automatically calculate the best path from each router to each destination. If the network changes, the routing protocol takes the change into account and recalculates paths as necessary.

The routing protocol determines the best path according to constraints. In the case of RIP, OSPF, and IS-IS, the constraint is a simple sum of interface metrics. In the case of EIGRP the constraints can be based on multiple link characteristics: bandwidth, delay, load, and reliability. BGP constrains its path selection based on a prioritization of characteristics called path attributes.

While the distance vector protocols (RIP, EIGRP, and BGP) perform distributed hop-by-hop calculations based on local interface information, the link state protocols (OSPF and IS-IS) perform individual, local calculations based on distributed interface information.

It’s that local calculation of distributed interface information that gets us where we need to be to automatically compute EROs at ingress LSRs, so let’s look more closely at link state protocols.

Each link state router creates a protocol data unit that identifies the router, its directly connected neighbors, and the local interface costs to the neighbors. The data unit is then flooded throughout the defined protocol area. Each router within the area stores all of the data units in a database, and uses the database as the input to a Shortest Path First (SPF) calculation. The output of the SPF calculation is the shortest path to every other router in the area, and that information is used to make entries in the local routing table indicating the optimum next hop to the prefixes attached to those routers.

A link state protocol can be easily extended to include other local information in the protocol data unit it floods. So to support MPLS traffic engineering, both OSPF and IS-IS have extensions that enable each router to flood extra information about each of its interfaces:

·      Maximum bandwidth

·      Maximum reservable bandwidth (the portion of the maximum bandwidth that can be reserved for exclusive use by an individual LSP)

·      Unreserved bandwidth (the percentage of the maximum reservable bandwidth not yet reserved by any LSP)

·      An interface metric that can be used separately from the IGP interface metric

·      The administrative groups to which the interface belongs (Commonly called “link color,” an administrative group allows the formation of policies that dictate what links an individual LSP can or cannot traverse.)

When this information is flooded, each LSR stores the information in a database called the traffic engineering database. When you configure an LSP at an ingress router, you can specify constraints based on any or all of that flooded information: The amount of bandwidth the LSP requires, the cost of the path, and the link “colors” the LSP must or must not use.

The ingress LSR then runs a special version of SPF called Constrained Shortest Path First (CSPF) that takes as its input both the information in the traffic engineering database and the constraints you configure.

Figure 2 shows the relationships between the link state database and the traffic engineering database, SPF and CSPF, and the outputs of each. Where the results of the SPF calculation are used to make entries in the unicast routing table, RSVP-TE takes the ERO resulting from the CSPF calculation and sends PATH messages to the egress to reserve resources for the LSP. As explained in the previous post, the egress LSP sends RESV messages back to the ingress to distribute the labels; this is what actually sets up the LSP. Once this process is complete, RSVP can make entries into the unicast routing table that indicates the LSP as a virtual link to the egress LSR.

The bottom line is, if you understand the operation of link state protocols it is an easy jump to understanding how RSVP-TE and MPLS traffic engineering work.

Having taken several posts to explain RSVP, I’ll probably move on to a few other topics; but I’ll soon post another entry discussing Label Distribution Protocol (LDP) and its differences from RSVP-TE.

Rocky Mountain IPv6 Summit

The Rocky Mountain IPv6 Task Force will be holding its first Rocky Mountain IPv6 Summit in Denver on April 9^th. We’re lining up a good group of speakers and a very informative agenda; if you’re in the Colorado-Wyoming-New Mexico region and want to know more about IPv6, I hope to see you there!

You can get more information, and sign up, at:

http://www.rmv6tf.org/SpringEvent.htm