It's time to recap a few basics of MPLS, and in particular of CSPF. The Constrained Shortest Path First (CSPF) algorithm allow an ingress LSR to compute a Label Switched Path (LSP) out of a Traffic Engineering (TE) database, the latter includes various constraints or requirements on how a LSP must be signaled. As you may wonder, CSPF is widely use for traffic engineering purpose, but it's also a prerequisite for two protection mechanisms, namely Fast Reroute (FRR) and link/node protection. In fact, these two, uses the TE database to compute and later signal backup tunnels (or bypass LSPs). CSPF is therefore an important piece on the MPLS chessboard.
Do I need to enable CSPF to control where to send my traffic? The answer is no. You can manually configure an Explicit Route Objects (ERO) list, and let RSVP doing the job. In the presence of the ERO object, the RSVP Path messages will follow the path specified, thus the Resv messages carrying the labels in the opposite direction.
As the name implies, Constrained Shortest Path First (CSPF) is an extension of the well-known SPF algorithm. We still want to compute the shortest path, but before, we want to take into account various constraints, which could be one or many of the following:
All these information are usually conveyed by a link-state dynamic routing protocol like OSPF (RFC3630) or IS-IS (RFC5305). OSPF implementations use the area-local, Type-10 Opaque LSAs with new-TLVs and sub-TLVs definitions. ISIS also uses sub-CLVs to convey TE attributes, which for the most important are Sub-TLV 3 (Admin Group), Sub-TLV 6 (Tunnel Source), Sub-TLV 8 (Tunnel Destination), Sub-TLV 9 (Maximum Bandwidth), Sub-TLV 10 (Reservable Bandwidth) and finally Sub-TLV 11 (Unreserved Bandwidth). They are included in TLV 22 (Extended IS Reachability) and TLV 135 (Extended IP Reachability) which can also carry wide-metrics.
With both OSPF and ISIS you can limit the propagation scope of your traffic-engineering information, using respectively the OSPF areas and the ISIS levels. Upon reception of the above mentioned IGP's LSA, the MPLS Ingress LSRs store the TE information inside their respective database. They can now compute a traffic-engineered LSP according to the constraints you locally defined. To do so, they run the CSPF algorithm; the following compute traffic paths of candidate LSPs, one at a time, beginning with the highest-priority LSP (the one with the lowest setup priority value). Each LSP is evaluated using the following sequence:
At the end of the evaluation process (step 8), the CSPF algorithm return an ordered-list of links the path must traverse. This is similar to a strict ERO you can manually configure. This time, it's computed by the CSPF algorithm and it's directly returned to RSVP for signaling.
For the purpose of demonstrating how CSPF compute paths, I built a lab reproducing a fictitious European MPLS backbone. The latter includes 13 label switching routers (LSRs), several PEs and a few CEs. The backbone is made of a mix of FastEthernet, GigabitEthernet, Logical Tunnels and ATM links, therefore, the bandwidth capacities may varies significantly. The IGP used is ISIS, with only Level-2 adjacency. I didn't generated much data traffic over the LSPs, because what is important here is how the LSPs are signaled according to the TE information distributed over the network. In fact, the control-plane is not aware of the amount of traffic passing through the data-plane; there's not even any insurance the traffic won't exceed the signaled bandwidth guarantees. There's some mechanisms to specifically address those concerns, but they're outside the scope of this article. As they are important features, they may be however worth a second article.
To start our demonstration. we want to establish two Label Switched Path (LSPs) between our Provider Edge Routers in Paris and Frankfurt. Our LSPs will have a bandwidth guarantee of 80 Mbits each. As the above diagram show, there is three possible traffic paths for the LSPs between the Paris PE and the Frankfurt PE routers. In this lab, I intentionally configured (overridden) the core interfaces IGP costs so all the paths have a cumulative cost of 100 (merely disabling step 4 of the CSPF algorithm). They do have however different numbers of hops, Path B has 2 hops, Path A and C have 3. As we will see, the hop count is very important, because the CSPF algorithm is using it as a tie-breaker when equal-cost paths exists (step 6).
The first sequence of the CSPF algorithm is to prune all links that have insufficient available bandwidth. As we have already several LSPs established across our backbone and they transits the same core links as our candidate LSPs, they will compete with each other. In fact, these pre-established LSPs previously made bandwidth reservations across the core links, as the output below show:
root@lab-m7i-2> show rsvp interface logical-system Paris RSVP interface: 4 active Active Subscr- Static Available Reserved Highwater Interface State resv iption BW BW BW mark fe-0/0/0.602Up 4 100% 100Mbps 100Mbps 0bps 0bps fe-1/3/0.607Up 0 100% 100Mbps 100Mbps 0bps 0bps fe-1/3/1.606Up 5 100% 100Mbps 70Mbps 30Mbps 30Mbps lt-1/2/0.1605 Up 4 100% 800Mbps 770Mbps 30Mbps 30Mbps
As our first LSP between Paris and Frankfurt PE require a bandwidth guarantee of 80 Mbps, the link between Paris and London (fe-1/3/1.606) is pruned. In fact, as you can see on the output above, the available bandwidth is only of 70Mbps. Therefore, Path A cannot be used to signal our LSP. Path B and C do have however enough available bandwidth. In this scenario, the link between Paris and London has been pruned by the CSPF algorithm, thus directly excluding Path A from the computation. In a real network, the bandwidth could also have been insufficient between London and Amsterdam due to other reservations made between these two P routers. The common point here, is that CSPF can figure that out prior to signaling because of the TE database. RSVP can still reject the reservation if not enough resources are available. In fact, the Traffic Engineering (TE) database could hold outdated information.
In MPLS, all LSPs are unidirectional, as the bandwidth reservations. In the reverse direction, the ingress PE Frankfurt has different available bandwidths values:
root@lab-m7i-2> show rsvp interface logical-system Frankfurt RSVP interface: 3 active Active Subscr- Static Available Reserved Highwater Interface State resv iption BW BW BW mark fe-0/0/0.601Up 5 100% 100Mbps 80Mbps 20Mbps 20Mbps fe-1/3/0.611Up 6 100% 100Mbps 100Mbps 0bps 0bps lt-1/2/0.1610 Up 8 100% 800Mbps 780Mbps 20Mbps 20Mbps
This is an important, because in a network as big as this lab, bandwidth reservations between two PEs can be asymmetrical. The two unidirectional LSPs can take different paths, and can even have different bandwidth guarantees. You may want to force symmetric routing across your backbone, to do so, you can use strict ERO and at some extend administrative colors.
Let's configure our candidate LSPs on the Paris and Frankfurt PEs, and then we verify the results.
root@lab-m7i-2# show | compare [edit logical-systems Frankfurt protocols mpls] label-switched-path Frankfurt-To-Milan { ... } + label-switched-path Frankfurt-To-Paris { + to 10.0.255.3; + bandwidth 80m; + } [edit logical-systems Paris protocols mpls] + label-switched-path Paris-To-Frankfurt { + to 10.0.255.7; + bandwidth 80m; + } [edit] root@lab-m7i-2# commit commit complete [edit] root@lab-m7i-2# run show rsvp session logical-system Paris ingress name Paris-To-Frankfurt extensive Ingress RSVP: 1 sessions 10.0.255.7 From: 10.0.255.3, LSPstate: Up, ActiveRoute: 0 LSPname: Paris-To-Frankfurt, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 300144 Resv style: 1 FF, Label in: -, Label out: 300144 Time left: -, Since: Mon Aug 26 14:03:47 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 1 receiver 50777 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.9 (fe-0/0/0.602) 6 pkts RESV rcvfrom: 10.0.0.9 (fe-0/0/0.602) 6 pkts Explct route: 10.0.0.9 10.0.0.6 Record route: <self> 10.0.0.9 10.0.0.6 Total 1 displayed, Up 1, Down 0 [edit] root@lab-m7i-2# run show rsvp session logical-system Frankfurt ingress name Frankfurt-To-Paris extensive Ingress RSVP: 9 sessions 10.0.255.3 From: 10.0.255.7, LSPstate: Up, ActiveRoute: 0 LSPname: Frankfurt-To-Paris, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 300160 Resv style: 1 FF, Label in: -, Label out: 300160 Time left: -, Since: Mon Aug 26 14:03:48 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 1 receiver 65379 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.5 (fe-0/0/0.601) 6 pkts RESV rcvfrom: 10.0.0.5 (fe-0/0/0.601) 6 pkts Explct route: 10.0.0.5 10.0.0.10 Record route: <self> 10.0.0.5 10.0.0.10 Total 1 displayed, Up 1, Down 0
The output above show our ingress LSPs are all in the UP state. The record route lists holds the LSR's core interfaces IP addresses the RSVP's Path messages traversed. The lists here indicates the LSPs are established across Path B.
Someone may ask why Path C has not be picked up. After all, all paths have the same IGP costs. This is because of the step 6 of the algorithm. When equal-cost paths exists, the paths with the least number of hops always win.
Now, let's see how we can make use of administrative coloring (step 2, 3), an inherent feature of MPLS Traffic Engineering. We want to mark all our backbone's core links with one or more of the following colors: Bronze, Silver or Gold. We assume here to each colors correspond to a specific SLA level. As some core links perform better than others (lower delay, better reliability), we want to direct the important traffic on these links.
We start by defining our colors on each LSRs by creating what is called an administrative groups in Junos:
[edit logical-systems Paris protocols mpls] root@lab-m7i-2# set protocols mpls admin-groups gold 1 root@lab-m7i-2# set protocols mpls admin-groups silver 2 root@lab-m7i-2# set protocols mpls admin-groups bronze 3
We then apply the admin-groups to our MPLS interfaces:
[edit logical-systems Paris] root@lab-m7i-2# set protocols mpls interface fe-0/0/0.602 admin-group bronze root@lab-m7i-2# set protocols mpls interface fe-1/3/1.606 admin-group silver root@lab-m7i-2# set protocols mpls interface lt-1/2/0.1605 admin-group [ gold silver ] root@lab-m7i-2# show | compare [edit logical-systems Paris] + admin-groups { + gold 1; + silver 2; + bronze 3; + } [edit logical-systems Paris] interface all { ... } + interface fe-0/0/0.602 { + admin-group bronze; + } + interface fe-1/3/1.606 { + admin-group silver; + } + interface lt-1/2/0.1605 { + admin-group [ gold silver ]; + }
We repeat the last two operations on all LSRs. And, we finally instruct our PE to traffic-engineer their ingress LSPs according to the color(s) or admin-group(s) they belong to, here 'Gold':
[edit logical-systems Frankfurt protocols mpls label-switched-path Frankfurt-To-Paris] + admin-group include-any gold; [edit logical-systems Paris protocols mpls label-switched-path Paris-To-Frankfurt] + admin-group include-any gold; [edit] root@lab-m7i-2# commit commit complete root@lab-m7i-2# top [edit] root@lab-m7i-2# run show rsvp session logical-system Paris ingress name Paris-To-Frankfurt extensive Ingress RSVP: 1 sessions 10.0.255.7 From: 10.0.255.3, LSPstate: Up, ActiveRoute: 0 LSPname: Paris-To-Frankfurt, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 301056 Resv style: 1 FF, Label in: -, Label out: 301056 Time left: -, Since: Tue Aug 27 13:12:29 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 2 receiver 8755 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.21 (lt-1/2/0.1605) 12 pkts RESV rcvfrom: 10.0.0.21 (lt-1/2/0.1605) 11 pkts Explct route: 10.0.0.21 10.0.0.1 10.0.0.6 Record route: <self> 10.0.0.21 10.0.0.1 10.0.0.6 Total 1 displayed, Up 1, Down 0 [edit] root@lab-m7i-2# run show rsvp session logical-system Frankfurt ingress name Frankfurt-To-Paris extensive Ingress RSVP: 9 sessions 10.0.255.3 From: 10.0.255.7, LSPstate: Up, ActiveRoute: 0 LSPname: Frankfurt-To-Paris, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 301600 Resv style: 1 FF, Label in: -, Label out: 301600 Time left: -, Since: Tue Aug 27 13:13:26 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 1 receiver 24554 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.5 (fe-0/0/0.601) 11 pkts RESV rcvfrom: 10.0.0.5 (fe-0/0/0.601) 10 pkts Explct route: 10.0.0.5 10.0.0.2 10.0.0.22 Record route: <self> 10.0.0.5 10.0.0.2 10.0.0.22 Total 1 displayed, Up 1, Down 0
As we can see, the LSPs now take Path C. Path A and B being pruned by Step 2 of the CSPF algorithm.
Now, let's configure our candidate LSPs, so they belong to the 'Silver' color:
root@lab-m7i-2# show | compare [edit logical-systems Frankfurt protocols mpls label-switched-path Frankfurt-To-Paris] - admin-group include-any gold; + admin-group include-any silver; [edit logical-systems Paris protocols mpls label-switched-path Paris-To-Frankfurt] - admin-group include-any gold; + admin-group include-any silver; [edit] root@lab-m7i-2# run show rsvp session logical-system Paris ingress name Paris-To-Frankfurt extensive Ingress RSVP: 1 sessions 10.0.255.7 From: 10.0.255.3, LSPstate: Up, ActiveRoute: 0 LSPname: Paris-To-Frankfurt, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 301024 Resv style: 1 FF, Label in: -, Label out: 301024 Time left: -, Since: Tue Aug 27 14:06:55 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 1 receiver 8756 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.26 (fe-1/3/1.606) 15 pkts RESV rcvfrom: 10.0.0.26 (fe-1/3/1.606) 15 pkts Explct route: 10.0.0.26 10.0.0.34 10.0.0.42 Record route: <self> 10.0.0.26 10.0.0.34 10.0.0.42 Total 1 displayed, Up 1, Down 0 [edit] root@lab-m7i-2# run show rsvp session logical-system Frankfurt ingress name Frankfurt-To-Paris extensive Ingress RSVP: 9 sessions 10.0.255.3 From: 10.0.255.7, LSPstate: Up, ActiveRoute: 0 LSPname: Frankfurt-To-Paris, LSPpath: Primary LSPtype: Static Configured Suggested label received: -, Suggested label sent: - Recovery label received: -, Recovery label sent: 301616 Resv style: 1 FF, Label in: -, Label out: 301616 Time left: -, Since: Tue Aug 27 14:07:24 2013 Tspec: rate 80Mbps size 80Mbps peak Infbps m 20 M 1500 Port number: sender 1 receiver 24557 protocol 0 PATH rcvfrom: localclient Adspec: sent MTU 1500 Path MTU: received 1500 PATH sentto: 10.0.0.5 (fe-0/0/0.601) 15 pkts RESV rcvfrom: 10.0.0.5 (fe-0/0/0.601) 15 pkts Explct route: 10.0.0.5 10.0.0.2 10.0.0.22 Record route: <self> 10.0.0.5 10.0.0.2 10.0.0.22 Total 1 displayed, Up 1, Down 0
We can see the Record Route lists changed, one LSP is now taking Path A and the other Path C. It confirm the fact we can easily have asymmetric routing among LSPs. To understand why Path A and C has been picked up, we must go to the penultimate steps of the CSPF algorithm, at step 7. The latter states when equal-cost paths exists, the path with the highest amount of available bandwidth must be picked (least-fill), the inverse (most-fill) or the path is chosen randomly (random). By default, Juniper Junos use the 'random' load-balancing method. To see what load-balancing method is in effect for a given LSP, use the show mpls lsp detail
command:
root@lab-m7i-2> show mpls lsp logical-system Paris ingress detail Ingress LSP: 1 sessions 10.0.255.7 From: 10.0.255.3, State: Up, ActiveRoute: 0, LSPname: Paris-To-Frankfurt ActivePath: (primary) LSPtype: Static Configured LoadBalance: Random Encoding type: Packet, Switching type: Packet, GPID: IPv4 *Primary State: Up Priorities: 7 0 Bandwidth: 80Mbps SmartOptimizeTimer: 180 Include Any: silver Computed ERO (S [L] denotes strict [loose] hops): (CSPF metric: 100) 10.0.0.26 S 10.0.0.34 S 10.0.0.42 S Received RRO (ProtectionFlag 1=Available 2=InUse 4=B/W 8=Node 10=SoftPreempt 20=Node-ID): 10.0.0.26 10.0.0.34 10.0.0.42 Total 1 displayed, Up 1, Down 0
You can change the default behavior by using the least-fill
, most-fill
or random
knobs in the MPLS label-switched-path configuration.
This conclude this article on the Constrained Shortest Path First (CSPF) algorithm. As previously stated, CSPF is an important piece of the MPLS toolstack. In fact, it allow us to control where our traffic must flow according to the administrative constraints we define and according to the state of the network, as MPLS-TE see it. CSPF is also a prerequisite for some protection mechanisms, because it allow them to achieve very fast re-convergence, even beating the SDH 50ms convergence time.
I hope you enjoyed this article. If you are working with MPLS and CSPF and you have additional information to share (I'm pretty sure I omitted a few things), feel free to leave a comment to this article.
Comments
blog comments powered by Disqus