Network Working Group D. Awduche Request for Comments: 2702 J. Malcolm Category: Informational J. Agogbua M. O'Dell J. McManus UUNET (MCI Worldcom) September 1999 Requirements for Traffic Engineering Over MPLS Status of this Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved.
AbstractThis document presents a set of requirements for Traffic Engineering over Multiprotocol Label Switching (MPLS). It identifies the functional capabilities required to implement policies that facilitate efficient and reliable network operations in an MPLS domain. These capabilities can be used to optimize the utilization of network resources and to enhance traffic oriented performance characteristics. 1.0 Introduction ............................................. 2 1.1 Terminology .............................................. 3 1.2 Document Organization .................................... 3 2.0 Traffic Engineering ...................................... 4 2.1 Traffic Engineering Performance Objectives ............... 4 2.2 Traffic and Resource Control ............................. 6 2.3 Limitations of Current IGP Control Mechanisms ............ 6 3.0 MPLS and Traffic Engineering ............................. 7 3.1 Induced MPLS Graph ....................................... 9 3.2 The Fundamental Problem of Traffic Engineering Over MPLS . 9 4.0 Augmented Capabilities for Traffic Engineering Over MPLS . 10 5.0 Traffic Trunk Attributes and Characteristics ........... 10 5.1 Bidirectional Traffic Trunks ............................. 11 5.2 Basic Operations on Traffic Trunks ....................... 12 5.3 Accounting and Performance Monitoring .................... 12
5.4 Basic Attributes of Traffic Trunks ....................... 13 5.5 Traffic Parameter Attributes ............................ 14 5.6 Generic Path Selection and Management Attributes ......... 14 5.6.1 Administratively Specified Explicit Paths ................ 15 5.6.2 Hierarchy of Preference Rules for Multi-paths ............ 15 5.6.3 Resource Class Affinity Attributes ....................... 16 5.6.4 Adaptivity Attribute ..................................... 17 5.6.5 Load Distribution Across Parallel Traffic Trunks ......... 18 5.7 Priority Attribute ....................................... 18 5.8 Preemption Attribute ..................................... 18 5.9 Resilience Attribute ..................................... 19 5.10 Policing Attribute ...................................... 20 6.0 Resource Attributes ...................................... 21 6.1 Maximum Allocation Multiplier ............................ 21 6.2 Resource Class Attribute ................................ 22 7.0 Constraint-Based Routing ................................ 22 7.1 Basic Features of Constraint-Based Routing ............... 23 7.2 Implementation Considerations ............................ 24 8.0 Conclusion ............................................. 25 9.0 Security Considerations .................................. 26 10.0 References ............................................. 26 11.0 Acknowledgments .......................................... 27 12.0 Authors' Addresses ....................................... 28 13.0 Full Copyright Statement ................................. 29 1,2] integrates a label swapping framework with network layer routing. The basic idea involves assigning short fixed length labels to packets at the ingress to an MPLS cloud (based on the concept of forwarding equivalence classes [1,2]). Throughout the interior of the MPLS domain, the labels attached to packets are used to make forwarding decisions (usually without recourse to the original packet headers). A set of powerful constructs to address many critical issues in the emerging differentiated services Internet can be devised from this relatively simple paradigm. One of the most significant initial applications of MPLS will be in Traffic Engineering. The importance of this application is already well-recognized (see [1,2,3]). This manuscript is exclusively focused on the Traffic Engineering applications of MPLS. Specifically, the goal of this document is to highlight the issues and requirements for Traffic Engineering in a large Internet backbone. The expectation is that the MPLS specifications, or implementations derived therefrom, will address
the realization of these objectives. A description of the basic capabilities and functionality required of an MPLS implementation to accommodate the requirements is also presented. It should be noted that even though the focus is on Internet backbones, the capabilities described in this document are equally applicable to Traffic Engineering in enterprise networks. In general, the capabilities can be applied to any label switched network under a single technical administration in which at least two paths exist between two nodes. Some recent manuscripts have focused on the considerations pertaining to Traffic Engineering and Traffic management under MPLS, most notably the works of Li and Rekhter , and others. In , an architecture is proposed which employs MPLS and RSVP to provide scalable differentiated services and Traffic Engineering in the Internet. The present manuscript complements the aforementioned and similar efforts. It reflects the authors' operational experience in managing a large Internet backbone. 1]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 . Section 2 discusses the basic functions of Traffic Engineering in the Internet. Section 3, provides an overview of the traffic Engineering potentials of MPLS. Sections 1 to 3 are essentially background material. Section 4 presents an overview of the fundamental requirements for Traffic Engineering over MPLS. Section 5 describes the desirable attributes and characteristics of traffic trunks which are pertinent to Traffic Engineering. Section 6 presents a set of attributes which can be associated with resources to constrain the routability of traffic trunks and LSPs through them. Section 7 advocates the introduction of a "constraint-based routing" framework in MPLS domains. Finally, Section 8 contains concluding remarks.
resource oriented performance objectives. In particular, it is generally desirable to ensure that subsets of network resources do not become over utilized and congested while other subsets along alternate feasible paths remain underutilized. Bandwidth is a crucial resource in contemporary networks. Therefore, a central function of Traffic Engineering is to efficiently manage bandwidth resources. Minimizing congestion is a primary traffic and resource oriented performance objective. The interest here is on congestion problems that are prolonged rather than on transient congestion resulting from instantaneous bursts. Congestion typically manifests under two scenarios: 1. When network resources are insufficient or inadequate to accommodate offered load. 2. When traffic streams are inefficiently mapped onto available resources; causing subsets of network resources to become over-utilized while others remain underutilized. The first type of congestion problem can be addressed by either: (i) expansion of capacity, or (ii) application of classical congestion control techniques, or (iii) both. Classical congestion control techniques attempt to regulate the demand so that the traffic fits onto available resources. Classical techniques for congestion control include: rate limiting, window flow control, router queue management, schedule-based control, and others; (see  and the references therein). The second type of congestion problems, namely those resulting from inefficient resource allocation, can usually be addressed through Traffic Engineering. In general, congestion resulting from inefficient resource allocation can be reduced by adopting load balancing policies. The objective of such strategies is to minimize maximum congestion or alternatively to minimize maximum resource utilization, through efficient resource allocation. When congestion is minimized through efficient resource allocation, packet loss decreases, transit delay decreases, and aggregate throughput increases. Thereby, the perception of network service quality experienced by end users becomes significantly enhanced. Clearly, load balancing is an important network performance optimization policy. Nevertheless, the capabilities provided for Traffic Engineering should be flexible enough so that network administrators can implement other policies which take into account the prevailing cost structure and the utility or revenue model.
1. the shortest paths of multiple traffic streams converge on specific links or router interfaces, or 2. a given traffic stream is routed through a link or router interface which does not have enough bandwidth to accommodate it. These scenarios manifest even when feasible alternate paths with excess capacity exist. It is this aspect of congestion problems (-- a symptom of suboptimal resource allocation) that Traffic Engineering aims to vigorously obviate. Equal cost path load sharing can be used to address the second cause for congestion listed above with some degree of success, however it is generally not helpful in alleviating congestion due to the first cause listed above and particularly not in large networks with dense topology. A popular approach to circumvent the inadequacies of current IGPs is through the use of an overlay model, such as IP over ATM or IP over frame relay. The overlay model extends the design space by enabling arbitrary virtual topologies to be provisioned atop the network's physical topology. The virtual topology is constructed from virtual circuits which appear as physical links to the IGP routing protocols. The overlay model provides additional important services to support traffic and resource control, including: (1) constraint-based routing at the VC level, (2) support for administratively configurable explicit VC paths, (3) path compression, (4) call admission control functions, (5) traffic shaping and traffic policing functions, and (6) survivability of VCs. These capabilities enable the actualization of a variety of Traffic Engineering policies. For example, virtual circuits can easily be rerouted to move traffic from over-utilized resources onto relatively underutilized ones. For Traffic Engineering in large dense networks, it is desirable to equip MPLS with a level of functionality at least commensurate with current overlay models. Fortunately, this can be done in a fairly straight forward manner.
the possibility to automate aspects of the Traffic Engineering function. This last consideration requires further investigation and is beyond the scope of this manuscript. A note on terminology: The concept of MPLS traffic trunks is used extensively in the remainder of this document. According to Li and Rekhter , a traffic trunk is an aggregation of traffic flows of the same class which are placed inside a Label Switched Path. Essentially, a traffic trunk is an abstract representation of traffic to which specific characteristics can be associated. It is useful to view traffic trunks as objects that can be routed; that is, the path through which a traffic trunk traverses can be changed. In this respect, traffic trunks are similar to virtual circuits in ATM and Frame Relay networks. It is important, however, to emphasize that there is a fundamental distinction between a traffic trunk and the path, and indeed the LSP, through which it traverses. An LSP is a specification of the label switched path through which the traffic traverses. In practice, the terms LSP and traffic trunk are often used synonymously. Additional characteristics of traffic trunks as used in this manuscript are summarized in section 5.0. The attractiveness of MPLS for Traffic Engineering can be attributed to the following factors: (1) explicit label switched paths which are not constrained by the destination based forwarding paradigm can be easily created through manual administrative action or through automated action by the underlying protocols, (2) LSPs can potentially be efficiently maintained, (3) traffic trunks can be instantiated and mapped onto LSPs, (4) a set of attributes can be associated with traffic trunks which modulate their behavioral characteristics, (5) a set of attributes can be associated with resources which constrain the placement of LSPs and traffic trunks across them, (6) MPLS allows for both traffic aggregation and disaggregation whereas classical destination only based IP forwarding permits only aggregation, (7) it is relatively easy to integrate a "constraint-based routing" framework with MPLS, (8) a good implementation of MPLS can offer significantly lower overhead than competing alternatives for Traffic Engineering. Additionally, through explicit label switched paths, MPLS permits a quasi circuit switching capability to be superimposed on the current Internet routing model. Many of the existing proposals for Traffic Engineering over MPLS focus only on the potential to create explicit LSPs. Although this capability is fundamental for Traffic Engineering, it is not really sufficient. Additional augmentations are required to foster the actualization of policies leading to performance optimization of large operational networks. Some of the necessary augmentations are described in this manuscript.
1]). Induced MPLS graphs are important because the basic problem of bandwidth management in an MPLS domain is the issue of how to efficiently map an induced MPLS graph onto the physical network topology. The induced MPLS graph abstraction is formalized below. Let G = (V, E, c) be a capacitated graph depicting the physical topology of the network. Here, V is the set of nodes in the network and E is the set of links; that is, for v and w in V, the object (v,w) is in E if v and w are directly connected under G. The parameter "c" is a set of capacity and other constraints associated with E and V. We will refer to G as the "base" network topology. Let H = (U, F, d) be the induced MPLS graph, where U is a subset of V representing the set of LSRs in the network, or more precisely the set of LSRs that are the endpoints of at least one LSP. Here, F is the set of LSPs, so that for x and y in U, the object (x, y) is in F if there is an LSP with x and y as endpoints. The parameter "d" is the set of demands and restrictions associated with F. Evidently, H is a directed graph. It can be seen that H depends on the transitivity characteristics of G.
This document is not focusing on the first two problems listed. (even-though they are quite important). Instead, the remainder of this manuscript will focus on the capabilities that permit the third mapping function to be performed in a manner resulting in efficient and reliable network operations. This is really the problem of mapping an induced MPLS graph (H) onto the "base" network topology (G).
First, the basic properties of traffic trunks (as used in this manuscript) are summarized below: - A traffic trunk is an *aggregate* of traffic flows belonging to the same class. In some contexts, it may be desirable to relax this definition and allow traffic trunks to include multi-class traffic aggregates. - In a single class service model, such as the current Internet, a traffic trunk could encapsulate all of the traffic between an ingress LSR and an egress LSR, or subsets thereof. - Traffic trunks are routable objects (similar to ATM VCs). - A traffic trunk is distinct from the LSP through which it traverses. In operational contexts, a traffic trunk can be moved from one path onto another. - A traffic trunk is unidirectional. In practice, a traffic trunk can be characterized by its ingress and egress LSRs, the forwarding equivalence class which is mapped onto it, and a set of attributes which determine its behavioral characteristics. Two basic issues are of particular significance: (1) parameterization of traffic trunks and (2) path placement and maintenance rules for traffic trunks.
The topological properties of BTTs should also be considered. A BTT can be topologically symmetric or topologically asymmetric. A BTT is said to be "topologically symmetric" if its constituent traffic trunks are routed through the same physical path, even though they operate in opposite directions. If, however, the component traffic trunks are routed through different physical paths, then the BTT is said to be "topologically asymmetric." It should be noted that bidirectional traffic trunks are merely an administrative convenience. In practice, most traffic engineering functions can be implemented using only unidirectional traffic trunks.
systems can be used for traffic characterization, performance optimization, and capacity planning within the Traffic Engineering realm.. The capability to obtain statistics at the traffic trunk level is so important that it should be considered an essential requirement for Traffic Engineering over MPLS.
Section 7, a constraint-based routing framework which can automatically compute paths subject to a set of constraints is described. Issues pertaining to explicit paths instantiated through administrative action are discussed in Section 5.6.1 below. Path management concerns all aspects pertaining to the maintenance of paths traversed by traffic trunks. In some operational contexts, it is desirable that an MPLS implementation can dynamically reconfigure itself, to adapt to some notion of change in "system state." Adaptivity and resilience are aspects of dynamic path management. To guide the path selection and management process, a set of attributes are required. The basic attributes and behavioral characteristics associated with traffic trunk path selection and management are described in the remainder of this sub-section.
Section 6) which are to be explicitly included or excluded from the path of the traffic trunk. These are policy attributes which can be used to impose additional constraints on the path traversed by a given traffic trunk. Resource class affinity attributes for a traffic can be specified as a sequence of tuples: <resource-class, affinity>; <resource-class, affinity>; .. The resource-class parameter identifies a resource class for which an affinity relationship is defined with respect to the traffic trunk. The affinity parameter indicates the affinity relationship; that is, whether members of the resource class are to be included or excluded from the path of the traffic trunk. Specifically, the affinity parameter may be a binary variable which takes one of the following values: (1) explicit inclusion, and (2) explicit exclusion. If the affinity attribute is a binary variable, it may be possible to use Boolean expressions to specify the resource class affinities associated with a given traffic trunk. If no resource class affinity attributes are specified, then a "don't care" affinity relationship is assumed to hold between the traffic trunk and all resources. That is, there is no requirement to explicitly include or exclude any resources from the traffic trunk's path. This should be the default in practice. Resource class affinity attributes are very useful and powerful constructs because they can be used to implement a variety of policies. For example, they can be used to contain certain traffic trunks within specific topological regions of the network. A "constraint-based routing" framework (see section 7.0) can be used to compute an explicit path for a traffic trunk subject to resource class affinity constraints in the following manner: 1. For explicit inclusion, prune all resources not belonging to the specified classes prior to performing path computation. 2. For explicit exclusion, prune all resources belonging to the specified classes before performing path placement computations.
section 5.9). In practice, it would seem reasonable to expect traffic trunks subject to re-optimization to be implicitly resilient to failures along their paths. However, a traffic trunk which is not subject to re-optimization and whose path is not administratively specified with a "mandatory" attribute can also be required to be resilient to link and node failures along its established path Formally, it can be stated that adaptivity to state evolution through re-optimization implies resilience to failures, whereas resilience to failures does not imply general adaptivity through re-optimization to state changes.
objectives. Preemption can used to assure that high priority traffic trunks can always be routed through relatively favorable paths within a differentiated services environment. Preemption can also be used to implement various prioritized restoration policies following fault events. The preemption attribute can be used to specify four preempt modes for a traffic trunk: (1) preemptor enabled, (2) non-preemptor, (3) preemptable, and (4) non-preemptable. A preemptor enabled traffic trunk can preempt lower priority traffic trunks designated as preemptable. A traffic specified as non-preemptable cannot be preempted by any other trunks, regardless of relative priorities. A traffic trunk designated as preemptable can be preempted by higher priority trunks which are preemptor enabled. It is trivial to see that some of the preempt modes are mutually exclusive. Using the numbering scheme depicted above, the feasible preempt mode combinations for a given traffic trunk are as follows: (1, 3), (1, 4), (2, 3), and (2, 4). The (2, 4) combination should be the default. A traffic trunk, say "A", can preempt another traffic trunk, say "B", only if *all* of the following five conditions hold: (i) "A" has a relatively higher priority than "B", (ii) "A" contends for a resource utilized by "B", (iii) the resource cannot concurrently accommodate "A" and "B" based on certain decision criteria, (iv) "A" is preemptor enabled, and (v) "B" is preemptable. Preemption is not considered a mandatory attribute under the current best effort Internet service model although it is useful. However, in a differentiated services scenario, the need for preemption becomes more compelling. Moreover, in the emerging optical internetworking architectures, where some protection and restoration functions may be migrated from the optical layer to data network elements (such as gigabit and terabit label switching routers) to reduce costs, preemptive strategies can be used to reduce the restoration time for high priority traffic trunks under fault conditions.
Many recovery policies can be specified for traffic trunks whose established paths are impacted by faults. The following are examples of feasible schemes: 1. Do not reroute the traffic trunk. For example, a survivability scheme may already be in place, provisioned through an alternate mechanism, which guarantees service continuity under failure scenarios without the need to reroute traffic trunks. An example of such an alternate scheme (certainly many others exist), is a situation whereby multiple parallel label switched paths are provisioned between two nodes, and function in a manner such that failure of one LSP causes the traffic trunk placed on it to be mapped onto the remaining LSPs according to some well defined policy. 2. Reroute through a feasible path with enough resources. If none exists, then do not reroute. 3. Reroute through any available path regardless of resource constraints. 4. Many other schemes are possible including some which might be combinations of the above. A "basic" resilience attribute indicates the recovery procedure to be applied to traffic trunks whose paths are impacted by faults. Specifically, a "basic" resilience attribute is a binary variable which determines whether the target traffic trunk is to be rerouted when segments of its path fail. "Extended" resilience attributes can be used to specify detailed actions to be taken under fault scenarios. For example, an extended resilience attribute might specify a set of alternate paths to use under fault conditions, as well as the rules that govern the relative preference of each specified path. Resilience attributes mandate close interaction between MPLS and routing.
Policing is necessary in many operational scenarios, but is quite undesirable in some others. In general, it is usually desirable to police at the ingress to a network (to enforce compliance with service level agreements) and to minimize policing within the core, except when capacity constraints dictate otherwise. Therefore, from a Traffic Engineering perspective, it is necessary to be able to administratively enable or disable traffic policing for each traffic trunk.
This document uses the term "constraint-based routing" however, because it better captures the functionality envisioned, which generally encompasses QoS routing as a subset. constraint-based routing enables a demand driven, resource reservation aware, routing paradigm to co-exist with current topology driven hop by hop Internet interior gateway protocols. A constraint-based routing framework uses the following as input: - The attributes associated with traffic trunks. - The attributes associated with resources. - Other topology state information. Based on this information, a constraint-based routing process on each node automatically computes explicit routes for each traffic trunk originating from the node. In this case, an explicit route for each traffic trunk is a specification of a label switched path that satisfies the demand requirements expressed in the trunk's attributes, subject to constraints imposed by resource availability, administrative policy, and other topology state information. A constraint-based routing framework can greatly reduce the level of manual configuration and intervention required to actualize Traffic Engineering policies. In practice, the Traffic Engineer, an operator, or even an automaton will specify the endpoints of a traffic trunk and assign a set of attributes to the trunk which encapsulate the performance expectations and behavioral characteristics of the trunk. The constraint-based routing framework is then expected to find a feasible path to satisfy the expectations. If necessary, the Traffic Engineer or a traffic engineering support system can then use administratively configured explicit routes to perform fine grained optimization. 9]) can be used to find a feasible path if one exists:
- First prune resources that do not satisfy the requirements of the traffic trunk attributes. - Next, run a shortest path algorithm on the residual graph. Clearly, if a feasible path exists for a single traffic trunk, then the above simple procedure will find it. Additional rules can be specified to break ties and perform further optimizations. In general, ties should be broken so that congestion is minimized. When multiple traffic trunks are to be routed, however, it can be shown that the above algorithm may not always find a mapping, even when a feasible mapping exists. 5,7]). 2. By adding a constraint-based routing process to each router which can co-exist with current IGPs. This scenario is depicted in Figure 1. ------------------------------------------ | Management Interface | ------------------------------------------ | | | ------------ ------------------ -------------- | MPLS |<->| Constraint-Based | | Conventional | | | | Routing Process | | IGP Process | ------------ ------------------ -------------- | | ----------------------- -------------- | Resource Attribute | | Link State | | Availability Database | | Database | ----------------------- -------------- Figure 1. Constraint-Based Routing Process on Layer 3 LSR
There are many important details associated with implementing constraint-based routing on Layer 3 devices which we do not discuss here. These include the following: - Mechanisms for exchange of topology state information (resource availability information, link state information, resource attribute information) between constraint-based routing processes. - Mechanisms for maintenance of topology state information. - Interaction between constraint-based routing processes and conventional IGP processes. - Mechanisms to accommodate the adaptivity requirements of traffic trunks. - Mechanisms to accommodate the resilience and survivability requirements of traffic trunks. In summary, constraint-based routing assists in performance optimization of operational networks by automatically finding feasible paths that satisfy a set of constraints for traffic trunks. It can drastically reduce the amount of administrative explicit path configuration and manual intervention required to achieve Traffic Engineering objectives.
 Rosen, E., Viswanathan, A. and R. Callon, "A Proposed Architecture for MPLS", Work in Progress.  Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G. and A. Viswanathan, "A Framework for Multiprotocol Label Switching", Work in Progress.  Li, T. and Y. Rekhter, "Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)", RFC 2430, October 1998.  Rekhter, Y., Davie, B., Katz, D., Rosen, E. and G. Swallow, "Cisco Systems' Tag Switching Architecture - Overview", RFC 2105, February 1997.  Zhang, Z., Sanchez, C., Salkewicz, B. and E. Crawley "Quality of Service Extensions to OSPF", Work in Progress.  Crawley, E., Nair, F., Rajagopalan, B. and H. Sandick, "A Framework for QoS Based Routing in the Internet", RFC 2386, August 1998.  Guerin, R., Kamat, S., Orda, A., Przygienda, T. and D. Williams, "QoS Routing Mechanisms and OSPF Extensions", RFC 2676, August 1999.  C. Yang and A. Reddy, "A Taxonomy for Congestion Control Algorithms in Packet Switching Networks," IEEE Network Magazine, Volume 9, Number 5, July/August 1995.  W. Lee, M. Hluchyi, and P. Humblet, "Routing Subject to Quality of Service Constraints in Integrated Communication Networks," IEEE Network, July 1995, pp 46-55.  ATM Forum, "Traffic Management Specification: Version 4.0" April 1996.
Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.