Definitive MPLS Network Designs [Electronic resources] نسخه متنی

Traffic Engineering

The notion of traffic engineering has existed since the first networks were invented. It relates to the art of making efficient use of network resources given a network topology and a set of traffic flows. In other words, the fundamental objective of traffic engineering is to route the traffic so as to avoid network congestion and increase the network's ability to absorb the maximum amount of traffic. To meet such an objective, you can use several traffic engineering techniques, one of which is MPLS-based traffic engineering.

The best way to introduce MPLS Traffic Engineering (called simply MPLS TE in this section) is to start with the well-known illustration called "the fish problem."

IP routing relies on the fundamental concept of destination-based routing. As shown in Figure 2-11, as soon as the two traffic flows originated by routers R1 and R6 towards R5 reach router R2, they follow the same IGP shortest path because IP packets are routed by default based on their destination IP address. In this example, the two flows follow the path R2R3R4R5. If the sum of traffic from these two flows exceeds the network capacity along this path, this inevitably leads to network congestion. This congestion can be avoided by routing some of the traffic along the other available path (R2R7R8R4, where some spare capacity is available).

In such a simple network, it is easy to adjust the IGP metrics so as to load-balance the traffic across the two available paths (which normally must have equal cost). However, networks are obviously significantly more complex, and IGP metric optimization is not that simple and does not always provide the level of granularity required. That being said, this is one of the possibilities for traffic-engineering an IP network. Another option is to employ MPLS Traffic Engineering, which provides a rich set of features with a very high granularity to efficiently traffic-engineer an MPLS/IP network.

This section first reviews the set of constraints (also called attributes) of a TE LSP. Then the method for computing the TE LSP path obeying the set of constraints is discussed, followed by an overview of the signaling aspects to set up a TE LSP. Finally, you will see the method used to route traffic onto TE LSPs.

MPLS Traffic Engineering Components

The fundamental idea of MPLS TE is to use a Traffic-Engineered Label-Switched Path (TE LSP or tunnel) to forward the traffic across the network by taking into account a set of constraints and the network topology and resources available with the objective of making efficient use of the network.

In short, the TE LSP attributes (constraints) determine the desired characteristics of the LSP (between its source and destination).

The traffic engineering LSP attributes are

Destination

Bandwidth

Affinities

Preemption

Protection by Fast Reroute

Optimized metric

Destination

The source of the TE LSP is the headend router where the TE LSP is configured, whereas its destination must be explicitly configured. Note that the source of a TE LSP must also be explicitly specified in case the TE LSP path is computed by some offline tool.

Bandwidth

One of the attributes of a TE LSP is obviously the bandwidth required for the TE LSP. Several methods can be used to estimate the bandwidth requirement. The most obvious way is to obtain a traffic matrix between the routers involved in a mesh of TE LSPs. This can be achieved by [MPLS-MGT] for more details on network management solutions). It is also worth mentioning that some more recent inferring techniques rely on the measurement of link utilization to compute the traffic matrix. However, such methods usually just provide estimates whose accuracy is variable and that vary greatly with the network topology.

The traffic flow pattern between two points is rarely a constant and is usually a function of the time of day, not to mention the traffic growth triggered by the introduction of new services in the network or just an accrued use of existing services. Hence, it is the responsibility of the network administrator to determine the bandwidth requirement between two points and how often it should be reevaluated. You can adopt a very conservative approach by considering the traffic peak, X percent of the peak or averaged bandwidth values. After you determine the bandwidth requirement, you can apply an over/underbooking ratio, depending on the overall objectives. Another approach consists of relying on the routers to compute the required bandwidth based on the observed traffic sent to a particular TE LSP. The TE LSP is set up with a predetermined value (which can be 0), and the router keeps monitoring the amount of traffic sent to the destination on the TE LSP. On a Cisco router, such a capability is called autobandwidth. It provides high flexibility by means of several configurable parameters: the sampling frequency (the frequency at which the bandwidth is sampled), the LSP resize frequency, and the minimum and maximum values that a TE LSP size can take. For example, the router can sample the amount of traffic sent every 30 minutes, select the peak value from among a set of samples, and resize the TE LSP no more frequently than once a day with the constraint of always being between 30 Mbps (the minimum value) and 200 Mbps (the maximum value). This provides high flexibility for the network administrator, who can determine the most appropriate trade-off between reactiveness (adapting the demand to the actual bandwidth requirement) and network stability (how often a TE LSP should be resized).

Affinities

A 32-bit flag field that must match the set of links a TE LSP traverses represents affinities. In a nutshell, this can be seen as a coloring scheme (with up to 32 colors). Each link of the network can also have up to 32 colors. It might be desirable in certain circumstances to ensure that a TE LSP exclusively traverses links of specified colors. For the sake of illustration, consider a network with a mix of terrestrial and satellite links. They mainly differ by their propagation delays (which are significantly higher for the satellite links). Hence, the network administrator may decide to color those links (by setting up a specific bit of the 32-bit affinity field). For a TE LSP that carries sensitive traffic for which a short propagation delay is desired, the constraint of avoiding links marked with this specific color can be enforced. Conversely, it is also possible to impose the constraint of selecting links that have a specific color. Any combination is possible, offering a high degree of flexibility.

Preemption

[PREEMPT]. Note that a low preemption number indicates a high preemption (preemption 0 corresponds to the highest priority).

A network administrator can have different motivations for using multiple preemptions in the network. For the sake of illustration, we can mention two typical uses of multipreemption schemes. First, you can ensure that the most important/critical TE LSPs take precedence over other less-important and less-critical TE LSPs in case of resource contention. (For example, voice TE LSPs should be able to preempt data LSPs in case of contention provoked by unexpected traffic growth or network failure.) Second, this lets you circumvent the effect of bandwidth fragmentation in distributed path computation environments. (When the bandwidth is fragmented, it is always more challenging to find a path for larger TE LSPs; hence, they can be configured with a higher priority.)

It is worth noting that because multiple preemptions are available, this implies that an announcement of the available bandwidth on a per-preemption basis should occur. In other words, for each pool of bandwidth, a set of eight available bandwidth values is advertised. For example, consider a link L with 100 Mbps of reservable bandwidth traversed by three TE LSPs:

T1 with a bandwidth of 10 Mbps and a preemption of 1

T2 with a bandwidth of 20 Mbps and a preemption of 3

T3 with a bandwidth of 15 Mbps and a preemption of 5

If you make the assumption of a single pool of bandwidth, the corresponding router advertises the following set of available bandwidth for the link:

Available bandwidth for preemption 0 = 100 Mbps

Available bandwidth for preemption 1 = 90 Mbps

Available bandwidth for preemption 2 = 90 Mbps

Available bandwidth for preemption 3 = 70 Mbps

Available bandwidth for preemption 4 = 70 Mbps

Available bandwidth for preemption 5 = 55 Mbps

Available bandwidth for preemption 6 = 55 Mbps

Available bandwidth for preemption 7 = 55 Mbps

For example, 55 Mbps of bandwidth is available for the TE LSPs having a preemption of 5, 6, or 7, whereas TE LSPs with a preemption of 3 or 4 can have up to 70 Mbps and a TE LSP with a preemption of 0 can get 100 Mbps. Of course, in this example if a headend router decides to signal a TE LSP of preemption 3 for 65 Mbps, the TE LSP T3 is preempted to accommodate the higher-priority TE LSP.

Protection by Fast Reroute

MPLS Traffic Engineering provides an efficient local protection scheme called Fast Reroute to quickly reroute TE LSPs to a presignaled backup tunnel within tens of milliseconds (see the "Core Network Availability" section). Such a local protection scheme can be used for some TE LSPs requiring fast rerouting on network failure and is signaled as a TE LSP attribute. In other words, it is possible when setting up a TE LSP to explicitly require the protection by Fast Reroute for the TE LSP whenever Fast Reroute is available on the traversed router. This lets you define different classes of recovery in which some TE LSPs are rerouted according to the normal MPLS Traffic Engineering procedures (as discussed later in this section) and other TE LSPs benefit from fast recovery by means of Fast Reroute. Some additional parameters are detailed in the "Core Network Availability" section.

Optimized Metric

The notion of shortest path is always related to a particular metric. Typically, in an IP network, each link has a metric, and the shortest path is the path such that the sum of the link metrics along the path is minimal.

MPLS TE also uses metrics to pick the shortest path for a tunnel that satisfies the constraints specified. MPLS TE has introduced its own metric. When MPLS TE is configured on a link, the router can flood two metrics for a particular link: the IGP and TE metrics (which may or may not be the same).

To illustrate a potential application, consider the case of links having different bandwidth and propagation delay characteristics. Given this, it might be advantageous to reflect each property by means of a different metric. The IGP metric could, for instance, reflect the link bandwidth, whereas the TE metric would be a function of the propagation delay. Consequently, the IETF specification named [SECOND-METRIC] proposed to have the ability to specify the metric that should be optimized when computing the shortest TE LSP path. On a Cisco router, when a TE LSP is configured, the metric to optimize can also be specified. For instance, the shortest path for a TE LSP carrying voice traffic could be the path offering the shortest propagation delay. Conversely, the path computed for TE LSPs carrying large amounts of data traffic would be determined with the objective of traversing high-speed links. Note that the current Constraint Shortest Path First (CSPF) implementation tries to compute the shortest path based on one of the two metrics (IGP or TE). Dual-metric optimization is an NP-complete problem that would make the path computation significantly more CPU-intensive.

Hierarchy of Attributes (Set of Ordered Path Option)

As you saw previously, when configuring a TE LSP, a set of attributes are specified that must be satisfied when computing the TE LSP path. But what happens if no path satisfying the set of constraints can be found? The answer is straightforward: the TE LSP is not set up. The solution is to relax the constraint that cannot be satisfied and retry at regular intervals to see whether a path satisfying the preferred set of attributes can be found.

The Cisco MPLS TE implementation provides such functionality in a very granular fashion. For each TE LSP, the network administrator can specify multiple sets of attributes with an order or preference. For instance, the most preferred set of attributes could be to get 50 Mbps of bandwidth, a specific affinity constraint (such as avoid all the "red" links), and a preemption of 5. If not all of these constraints can be specified, the user can decide to simply relax the affinity constraint or reduce the bandwidth, for instance. This provides great flexibility to ensure that the TE LSP can always be established along with an important control on the hierarchy among the set of constraints. (For instance, first relax the affinity constraint and then reduce the bandwidth as a last resort, or try to reduce the bandwidth first.)

A good common practice consists of always explicitly configuring a fallback option with no constraint. In such a case the TE LSP path is identical to the IGP shortest path, and the TE LSP could always be set up, provided that some connectivity exists between the source and the destination. Furthermore, the multiple sets of attributes can be ordered by preference, with the ability for the headend router to regularly try to reoptimize a TE LSP to find a path that satisfies a preferred set of attributes. For instance, suppose that a TE LSP is configured with 10 Mbps of bandwidth with a fallback option of 1 Mbps. The TE LSP is successfully set up along the path R1R2R3R4R5. If the link R3R4 fails and no other path offering a bandwidth of 10 Mbps can be found in the network, the headend router tries to find a path with 1 Mbps of available bandwidth. Then, when a reoptimization is triggered, the headend router first tries to evaluate whether a path for 10 Mbps can be found.

TE LSP Path Computation

There are two options for computing a TE LSP path: offline and online path computation. With offline path computation, an offline tool is used to compute the path of each TE LSP, taking into account the constraints and attributes (such as bandwidth, affinities, optimized metrics, preemption, and so on), the network topology, and resources. Because the computation is simultaneously performed for all the TE LSPs in the network, offline tools try to achieve a global network optimization with multiple criteria such as maximum link utilization, minimized propagation delay, and so on, and with the objective of maximizing the amount of traffic the network can carry. This can be achieved thanks to the global view of the network characteristics and traffic demands. Then the TE LSP paths are downloaded on each corresponding headend router.

The second path computation method relies on distributed path computation, whereby each router is responsible for computing the path(s) of the TE LSP(s) it is the headend for. No central server computes the TE LSP's path in the network. A very well-known algorithm for computing the TE LSPs is the CSPF algorithm(s). Although a multitude of variants exist, it is worth describing its most commonly used version variant. CSPF computes the shortest path(s) (in a similar fashion as the SPF algorithm used by link-state protocols such as OSPF and IS-IS) that satisfies the set of specified constraints. For instance, all the links that do not satisfy the bandwidth requirement or the affinity constraint (if present) for the TE LSP in question are pruned from the network topology. Then the Dijkstra algorithm computes the shortest path over the resulting subgraph.

We could probably devote an entire book to the respective strengths and weaknesses of each approach. In a nutshell, online path computation is more dynamic, more reactive to network and traffic changes, and more robust (it does not rely on a single centralized server) because of its distributed nature. It also yields less-optimal paths. In contrast, the offline approach usually allows for a higher degree of optimality at the price of less dynamicity, scalability, and increased management overhead.

MPLS TE IGP Routing Extensions

The path computation module needs to learn the available bandwidth on each link to compute a TE LSP path. This is achieved via specific routing protocol extensions, as defined in [OSPF-TE] and [ISIS-TE]. Each link is originally configured with reservable bandwidth (which may or may not be equal to the actual link speed if the network administrator is willing to make any under/oversubscription). As TE LSPs are set up and torn down, the amount of reserved bandwidth varies on each link and is reflected by the IGP. Note that the available bandwidth is provided for each preemption level.

Of course, it would be undesirable to flood a new IGP Link-State Advertisement (LSA) each time the available bandwidth changes. Hence, a nonlinear threshold mechanism is used such that small changes do not trigger the flooding of an IGP LSA update. The downside of such an approach is the potential inaccuracy between the available bandwidth flooded by the IGP and the actual reservation state. Consequently, a headend router may compute a path even though the required bandwidth is not actually available at some hop. In this case, the router that can't accommodate this request rejects the TE LSP set up and immediately triggers the flooding of an IGP LSA update to inform the headend router (and all the routers in the network) of the actual reservation state. The headend router in turn computes a new TE LSP path, this time taking into account up-to-date information.

The threshold scheme is made nonlinear to ensure more frequent updates (closer thresholds) as the available bandwidth for the link gets closer to 0. Ensuring more accurate bandwidth reservation states allows the operator to reduce the risk of unsuccessful TE LSP setup. In practice, such a scheme works extremely well and provides a very efficient trade-off between IGP flooding frequency and up-to-date reservation state dissemination.

Note also that the receipt of an IGP LSA reflecting a bandwidth reservation state never triggers a routing table computation. It is worth mentioning that even in large networks the IGP overhead related to the announcement of the reservable bandwidth along with other TE-related links attributes does not affect the IGP scalability.

Signaling of a Traffic Engineering LSP

[RSVP-TE]). RSVP-TE uses the RSVP messages defined in [RSVP] to set up, maintain (refresh), signal an error condition, and tear down a TE LSP. These messages are Path, Resv, Path Error, and Resv Error. Each message contains a variable set of objects. As mentioned earlier, several new objects in addition to the existing objects defined for IPv4 flows have been specified for use by MPLS TE. Those objects are related to TE LSP attributes such as the computed path (also called ERO), bandwidth, preemption, Fast Reroute requirements, and affinities, to mention a few.

When initiating a TE LSP setup, the headend router starts sending an RSVP Path message that specifies the TE LSP attributes. The Path message is processed at each hop up to the final destination. Then, on the reverse path, RSVP Resv messages are sent to the headend router. Each hop along the path checks whether the TE LSP constraints can effectively be satisfied. If they can, each router sends a Resv message to its upstream neighbor along the TE LSP path to confirm the successful setup. Note that it also provides the label to be used for the corresponding TE LSP. This messaging sequence is shown in Figure 2-12.