Network Working Group Daniel O. Awduche Internet Draft Joe Malcolm Expiration Date: October, 1998 Johnson Agogbua Mike O'Dell Jim McManus UUNET Technologies, Inc April, 1998 Requirements for Traffic Engineering Over MPLS draft-awduche-mpls-traffic-eng-00.txt Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract This Internet draft 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 enhance traffic oriented performance characteristics. Table of Contents 1.0 Introduction .................................... 2 2.0 Traffic Engineering ...................................... 3 2.1 Traffic Engineering Performance Objectives ............... 4 2.2 Traffic and Resource Control ............................. 5 2.3 Limitations of Current IGP Control Mechanisms ............ 6 3.0 MPLS and Traffic Engineering ............................. 7 Awduche, et al [Page 1] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 3.1 Induced MPLS Graph ....................................... 8 3.2 The Fundamental Problem of Traffic Engineering Over MPLS . 9 4.0 Augmented Capabilities for Traffic Engineering Over MPLS . 9 5.0 Traffic Trunk Attributes and Characteristics ........... 10 5.1 Bidirectional Traffic Trunks ............................. 10 5.2 Basic Operations on Traffic Trunks ....................... 11 5.3 Accounting and Performance Monitoring .................... 12 5.4 Basic Attributes of Traffic Trunks ....................... 12 5.5 Traffic Parameter Attributes ............................ 13 5.6 Generic Path Selection and Management Attributes ......... 13 5.6.1 Administratively Specified Explicit Paths ................ 14 5.6.2 Hierarchy of Preference Rules for Multi-paths ............ 15 5.6.3 Resource Class Affinity Attributes ....................... 15 5.6.4 Adaptivity Attribute ..................................... 16 5.6.5 Load Distribution Across Parallel Traffic Trunks ......... 17 5.7 Priority Attribute ....................................... 17 5.8 Preemption Attribute ..................................... 17 5.9 Resilience Attribute ..................................... 18 5.10 Policing Attribute ...................................... 19 6.0 Resource Attributes ...................................... 19 6.1 Maximum Allocation Multiplier ............................ 19 6.2 Resource Class Attribute ................................ 20 7.0 Constraint Based Routing ................................ 21 7.1 Basic Features of Constraint Based Routing ............... 22 7.2 Implementation Considerations ............................ 22 8.0 Conclusions ............................................. 23 9.0 References ............................................. 24 10.0 Acknowledgements ......................................... 25 11.0 Author's Address ......................................... 25 1.0 Introduction Multiprotocol Label Switching (MPLS) [1,2] integrates a label swapping framework with network layer routing. The basic idea consists in 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. From this relatively simple paradigm, a set of powerful constructs can be devised that address a number of critical issues in the emerging differentiated services Internet (see for example [3,9]). One of the most significant initial applications of MPLS will be in Traffic Engineering. This aspect is already well recognized (see [1,2,3,10]). This manuscript focuses exclusively on the Traffic Engineering Awduche, et al [Page 2] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 applications of MPLS. Specifically, the goal of this document is to highlight the issues and requirements for Traffic Engineering in a large Internet backbone, in the expectation 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 we focus on Internet backbones, the capabilities described here are equally applicable to Traffic Engineering in enterprise networks; in short to any label switched network under a single technical administration in which at least two paths exist between two nodes. There has been a number of recent manuscripts that focus on considerations pertaining to Traffic Engineering and Traffic management under MPLS; notably the works of Li and Rekhter [3], and Vaananen and Ravikanth [10]. In [3], an architecture is proposed which employs MPLS and RSVP to provide scalable differentiated services and Traffic Engineering in the Internet. In [10], a general framework is described that introduces traffic management capabilities into MPLS. The present manuscript compliments the aforementioned efforts, and reflects the authors' operational experience in managing a large Internet backbone. The reader is assumed to be familiar with the MPLS terminology as defined in [1]. The remainder of this document is organized as follows: Section 2 discusses the basic functions of Traffic Engineering in the Internet. Section 3, gives an overview of the traffic Engineering potentials of MPLS. Sections 1 to 3 can be regarded as 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 argues in favor of the introduction of a "constraint based routing" framework in MPLS domains. Finally, Section 8 contains our concluding remarks. 2.0 Traffic Engineering This section describes the basic functions of Traffic Engineering in an Autonomous system in the contemporary Internet. The limitations of current IGPs with respect to traffic and resource control are Awduche, et al [Page 3] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 highlighted. This section serves as motivation for the requirements on MPLS. Traffic Engineering (TE) is concerned with performance optimization of operational networks. Specifically, the goal of Traffic Engineering is to facilitate efficient and reliable network operations, and at the same time optimize the utilization of network resources. Traffic Engineering is becoming an indispensable function in many large Autonomous systems because of the high cost of network assets, and the commercial and competitive nature of the Internet. These factors emphasize the need for maximal operational efficiency. 2.1 Traffic Engineering Performance Objectives The key performance objectives associated with traffic engineering can be classified as either: 1. traffic oriented or 2. resource oriented. Traffic oriented performance objectives include those aspects that enhance the QoS of traffic streams. In the current single class, best effort Internet service model, the key traffic oriented performance objectives include: minimization of packet loss, minimization of delay, maximization of throughput, and enforcement of service level agreements. Under the prevailing Internet service model, minimization of packet loss is one of the most important traffic oriented performance objectives. Statistically bounded traffic oriented performance objectives (such as peak to peak packet delay variation, loss ratio, and maximum packet transfer delay) might become useful in the forthcoming differentiated services Internet. Resource oriented performance objectives include those aspects that pertain to the optimization of resource utilization. Efficient management of network resources is the vehicle for the attainment of 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 and scarce resource in contemporary networks. Therefor, a central function of Traffic Engineering is efficient management of bandwidth resources. Minimizing congestion is a major traffic and resource oriented performance objective. The interest here is not on transient congestion resulting from instantaneous bursts, but rather on congestion problems that are more prolonged. Congestion typically Awduche, et al [Page 4] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 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 through: (i) capacity expansion and (ii) classical congestion control techniques which attempt to regulate the demand, such that it fits onto available resources. Classical techniques for congestion control include: rate limiting, window flow control, router queue management, schedule-based control, and others; (see [8] 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, and aggregate throughput increases. Thereby, the perception of network service quality experienced by end users becomes significantly enhanced. 2.2 Traffic and Resource Control Performance optimization of operational networks is fundamentally a control problem. The Traffic Engineer acts as the controller in an adaptive feedback control system, which includes a set of interconnected network elements, a network performance monitoring system, and a set of network configuration management tools. The Traffic Engineer formulates a control policy, observes the state of the network through the monitoring system, characterizes the traffic, and applies control actions to drive the network to a desired state, in accordance with the control policy. This can be done reactively by taking action in response to the current state of the network, or pro-actively by using forecasting techniques to anticipate future trends and applying action to obviate predicted undesirable future states. Ideally, control actions should involve: Awduche, et al [Page 5] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 1. modifying traffic management parameters, 2. modifying parameters associated with routing, and 3. modifying attributes and constraints associated with resources. 2.3 Limitations of Current IGP Control Mechanisms This subsection reviews some of the well known limitations of current IGPs with regard to Traffic Engineering. The control capabilities offered by current Internet interior gateway protocols are quite inadequate for Traffic Engineering. This makes it difficult to actualize effective policies that address network performance problems. Indeed, IGPs based on shortest path algorithms contribute significantly to congestion problems in Autonomous systems within the Internet. SPF algorithms generally optimize based on a simple additive metric. Because these protocols are topology driven, bandwidth availability and traffic characteristics are not taken into account in making routing decisions. Consequently, congestion frequently occurs when: 1. the shortest paths of multiple streams converge on specific links or router interfaces and 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 case (2) with some degree of success, but generally not case (1), especially in large networks with dense topology. A popular means of circumventing the inadequacies of current IGPs is through an overlay model, using 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 IGP routing protocols. The overlay model also provides many important services which 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 Awduche, et al [Page 6] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 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. 3.0 MPLS and Traffic Engineering This section provides an overview of the applicability of MPLS to Traffic Engineering. Subsequent sections elaborate on the set of capabilities required to meet the Traffic Engineering requirements. MPLS is strategically significant for Traffic Engineering because it can potentially provide most of the functionality available from the overlay model, in an integrated manner, and at lower cost than competing alternatives. Equally importantly, MPLS offers the possibility to automate the Traffic Engineering function. This later aspect is left for further study 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 [3], a traffic trunk is an aggregation of traffic flows of the same class which are placed inside a Label Switched Path. It is useful to view traffic trunks as atomic objects which 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 to emphasize that there is a fundamental distinction between a traffic trunk and the LSP through which it traverses. Additional characteristics of traffic trunks worth noting 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 Awduche, et al [Page 7] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 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. Furthermore, through explicit routes, 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 that lead to performance optimization of large operational networks. Some of the necessary augmentations are described in this manuscript. 3.1 Induced MPLS Graph This subsection introduces the concept of an "induced MPLS graph" which is central to Traffic Engineering in MPLS domains. An induced MPLS graph is analogous to a virtual topology in an overlay model, and is logically mapped onto the physical network through the selection of LSPs for traffic trunks. An induced MPLS graph consists of a set of LSRs which comprise the nodes of the graph and a set of LSPs which provide logical point to point connectivity between the LSRs, and hence serve as the links of the induced graph. Using the concept of label stacks (see [1]), it may be possible to construct hierarchical induced MPLS graphs. Induced MPLS graphs are important because the basic problem of bandwidth management in an MPLS domain concerns 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, Awduche, et al [Page 8] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 H is a directed graph. It can be seen that H depends on the transitivity characteristics of G. 3.2 The Fundamental Problem of Traffic Engineering Over MPLS There are basically three fundamental problems that relate to Traffic Engineering over MPLS. - The first problem concerns how to map packets onto forwarding equivalence classes. - The second problem concerns how to map forwarding equivalence classes onto traffic trunks. - The third problem concerns how to map traffic trunks onto the physical network topology through label switched paths. Here, we do not concern ourselves with the first two aspects of the problem (even-though they are quite important). Instead, the remainder of this manuscript will focus on capabilities that permit the third mapping function to be performed in a manner that results in efficient and reliable network operations. This is really the problem of mapping an induced MPLS graph (H) onto the "base" network topology (G). 4.0 Augmented Capabilities for Traffic Engineering Over MPLS The previous sections reviewed the basic functions of Traffic Engineering in the contemporary Internet. The applicability of MPLS to that activity was also discussed. The remaining sections of this manuscript describe the functional capabilities required to fully support Traffic Engineering over MPLS in large networks. The proposed capabilities consist of: 1. A set of attributes associated with traffic trunks which collectively specify their behavioral characteristics. Some of these attributes have already been suggested in [10] within the context of traffic management for MPLS. 2. A set of attributes associated with resources which constrain the placement of traffic trunks through them. These can also be viewed as topology attribute constraints. 3. A "constraint based routing" (QoS routing) framework which is used to select paths for traffic trunks subject to constraints imposed by items 1) and 2) above. The constraint based routing framework need not be part of MPLS. However, the two need to be Awduche, et al [Page 9] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 tightly integrated together. The attributes associated with traffic trunks and resources, as well as parameters associated with routing, collectively represent the control variables which can be modified through administrative action to drive the network to a desired state. In an operational network, it is highly desirable that these attributes can be dynamically modified online by an operator without adversely disrupting network operations. 5.0 Traffic Trunk Attributes and Characteristics This section describes the desirable attributes which can be associated with traffic trunks to influence their behavioral characteristics. First, the basic properties of traffic trunks are summarized below: - A traffic trunk is an *aggregate* of traffic flows belonging to the same class. - In a single class service model such as the current Internet, a traffic trunk could encapsulate all the traffic between an ingress LSR and an egress LSR. - 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. 5.1 Bidirectional Traffic Trunks Although traffic trunks are conceptually unidirectional, in many practical contexts, it is useful to simultaneously instantiate two traffic trunks with the same endpoints, but which carry packets Awduche, et al [Page 10] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 in opposite directions. The two traffic trunks are logically coupled together. That is, one trunk, called the forward trunk, carries traffic from an originating node to a destination node, while the other trunk, called the backward trunk, carries traffic from the destination node to the originating node. We refer to the amalgamation of two such traffic trunks as one bidirectional traffic trunk (BTT) if the following two conditions hold: - Both traffic trunks are instantiated through an atomic action at one LSR, called the originator node. - Neither of the composite traffic trunks can exist without the other. That is, both are instantiated and destroyed together. It is also useful to consider the topological properties of BTTs. 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. Otherwise, if the component traffic trunks are routed through different physical paths, then the BTT is said to be "topologically asymmetric." 5.2 Basic Operations on Traffic Trunks In the following, we summarize the basic operations on traffic trunks which are significant for Traffic Engineering purposes. - Establish: Create an instance of a traffic trunk. - Activate: Cause a traffic trunk to start passing traffic. The establishment and activation of a traffic trunk are logically separate events. Although, in practice they can be implemented or invoked as one atomic action. - Deactivate: Cause a traffic trunk to stop passing traffic. - Modify Attributes: Cause the attributes of a traffic trunk to be modified. - Reroute: Cause a traffic trunk to change its route. This can be done through administrative action or automatically by the underlying protocols. - Destroy: Remove an instance of a traffic trunk from the network and reclaim all resources allocated to it. Such resources include label space, and possibly available bandwidth. The above are considered the basic operations on traffic trunks. Awduche, et al [Page 11] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 Additional operations are also possible such as policing, traffic shaping, and so forth. 5.3 Accounting and Performance Monitoring Accounting capabilities are very important for purposes of billing and traffic characterization. The billing aspect of accounting was discussed in [10]. From a Traffic Engineering perspective, performance statistics obtained from an accounting system can be used for traffic characterization, performance optimization, and capacity planning. 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. 5.4 Basic Traffic Engineering Attributes of Traffic Trunks An attribute of a traffic trunk is a parameter assigned to it which influences its behavioral characteristics. Attributes can be explicitly assigned to traffic trunks through administration action or implicitly assigned by the underlying protocols when packets are classified and mapped into equivalence classes at the ingress to an MPLS domain. Regardless of how the attributes were originally assigned, for Traffic Engineering purposes, it should be possible to administratively modify such attributes. The basic attributes of traffic trunks which are significant for Traffic Engineering are itemized below. Some, of these attributes have already been included under the traffic management framework document [10]. - Traffic parameter attributes - Generic Path selection and maintenance attributes - Priority attribute - Preemption attribute - Resilience attribute - Policing attribute The combination of traffic parameters and policing attributes is analogous to usage parameter control in ATM networks. Also, most Awduche, et al [Page 12] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 of the above attributes have analogs in well established technologies. Consequently, it should be relatively straight forward to map the traffic trunk attributes onto many existing switching and routing architectures. Priority and preemption can be regarded as relational attributes because they express certain binary relations between traffic trunks. Conceptually, these binary relations determine the manner in which traffic trunks interact with each other as they compete for network resources during path establishment and path maintenance. 5.5 Traffic parameter attributes Traffic parameters can be used to capture the characteristics of the traffic streams (or more precisely the forwarding equivalence class) which are to be transported through the traffic trunk. Such characteristics might include peak rates, average rates, permissible burst size, etc. From a traffic engineering perspective, the traffic parameters are significant because they indicate the resource requirements of the traffic trunk. This is useful for resource allocation and congestion avoidance through anticipatory policies. For purposes of bandwidth allocation, a single canonical value of bandwidth requirements can be computed from a traffic trunk's traffic parameters. Techniques for performing such computations are already well known; for example the theory of effective bandwidth and such like. 5.6 Generic Path Selection and Management Attributes Generic path selection and management attributes define the rules for selecting the route taken by a traffic trunk, and the rules for maintenance of paths that are already established. Paths can either be computed automatically by the underlying routing protocols or defined administratively by a network operator. If no resource requirements or restrictions are associated with a traffic trunk, then a topology driven protocol can be used to select its path. However, if there are resource requirements or restrictions, then a constraint based routing scheme must be used for path selection. In Section 7, we describe a constraint based routing framework which can automatically compute paths subject to a set of constraints. Issues that pertain to explicit paths instantiated through administrative action are discussed in Section 5.6.1 below. Awduche, et al [Page 13] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 Path management concerns all aspects that pertain to the maintenance of paths traversed by traffic trunks. In some operational contexts, it is desirable that an MPLS implementation should be able to 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. In the remainder of this sub-section, we describe the basic attributes and behavioral characteristics associated with traffic trunk path selection and management. 5.6.1 Administratively Specified Explicit Paths An administratively specified explicit path for a traffic trunk is one which is configured through operator action. An administratively specified path can be completely specified or partially specified. A path is completely specified if all required hops between the endpoints are indicated. A path is partially specified if only a subset of intermediate hops are indicated. In this case, the underlying protocols are required to complete the path. Due to operator errors, an administratively specified path can be inconsistent or illogical. The underlying protocols should be able to detect such inconsistencies and provide appropriate feedback. A "path preference rule" attribute should be associated with administratively specified explicit paths. A path preference rule attribute is a binary variable which indicates whether the administratively configured explicit path is "mandatory" or "non-mandatory." If an administratively specified explicit path is selected with a "mandatory attribute, then that path (and only that path) must be used. If a mandatory path is topological infeasible (eg., the two endpoints are topologically partitioned), or the path cannot be instantiated because available resources are inadequate, then the path setup process fails. In other words, if a path is specified as mandatory, then an alternate path cannot be used whatsoever; regardless of prevailing circumstance. A mandatory path which is successfully instantiated is also implicitly pinned. Once the path is instantiated it cannot be changed except through deletion and instantiation of a new path. On the other hand, if an administratively specified explicit path is selected with a "non-mandatory" preference rule attribute value, then the path should be used if feasible. Otherwise, an alternate path can be chosen instead by the underlying protocols. Awduche, et al [Page 14] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 5.6.2 Hierarchy of Preference Rules For Multi-Paths In some practical contexts, it is useful to be able to administratively specify a set of candidate explicit paths for a given traffic trunk and define a hierarchy of preference relations on the paths. During path establishment, the preference rules are applied to select a suitable path from the candidate list. Also, under failure scenarios the preference rules are applied to select an alternate path from the candidate list. 5.6.3 Resource Class Affinity Attributes Resource class affinity attributes associated with a traffic trunk can be used to specify the class of resources (see section 6) which are to be explicitly included or excluded from the path of the traffic trunk. Resource class affinity attributes consist of a sequence of tuples: ; ; .. 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. Specially, the affinity parameter is a binary variable which takes one of the following values: (1) explicit inclusion, and (2) explicit exclusion. 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. Presumably, this will be the default in practice. Resource class affinity attributes 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 which do not belong to the specified classes prior to performing path computation. 2. For explicit exclusion, prune all resources which belong to the specified classes before performing path placement computations. Awduche, et al [Page 15] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 5.6.4 Adaptivity Attribute Network characteristics and state change over time. For example, new resources become available, failed resources become reactivated, allocated resources become deallocated; in general sometimes more efficient paths become available. Therefor, from a Traffic Engineering perspective, it is necessary to have administrative control parameters that can be used to specify how traffic trunks respond to this dynamism. In some scenarios, it might be desirable to dynamically change the paths of some traffic trunks in response to changes in network state. This process is called re-optimization. In many other scenarios, re-optimization might be highly undesirable. An Adaptivity attribute is a part of the path maintenance parameters associated with traffic trunks. The adaptivity attribute associated with a traffic trunk indicates whether the trunk is subject to re-optimization. That is, an adaptivity attribute is a binary variable which takes one of the following values: (1) permit re-optimization and (2) disable re-optimization. If re-optimization is enabled, then a traffic trunk can be rerouted through different paths by the underlying protocols in response to changes in network state (primarily changes in resource availability). Conversely, if re-optimization is disabled, then the traffic trunk is "pinned" to its established path and cannot be rerouted in response to changes in network state. Stability is a major concern when re-optimization is permitted. To promote stability, an MPLS implementation should not be too reactive to the evolutionary dynamics of the network. At the same time, it must adapt fast enough so that optimal use can be made of network assets. It is to be noted that re-optimization is distinct from resilience. A different attribute is used to specify the resilience characteristics of a traffic trunk (see section 5.9). In practice, it would seem reasonable to expect traffic trunks which are 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. Awduche, et al [Page 16] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 5.6.5 Load Distribution Across Parallel Traffic Trunks Load distribution across multiple parallel traffic trunks between two nodes is an important consideration. In many practical contexts, the aggregate traffic between two nodes might be such that no single link (hence no single path) can carry the load. However, the aggregate flow might be less than the maximum permissible flow across a "min-cut" that partitions the two nodes. In this case, the only feasible solution is to appropriately divide the aggregate traffic into sub-streams and route the sub-streams through multiple paths between the two nodes. In an MPLS domain, this problem can be addressed by instantiating multiple traffic trunks between the two nodes, such that each traffic trunk carries a proportion of the aggregate traffic. Therefor, a flexible means of load assignment to multiple parallel traffic trunks carrying traffic of the same class between a pair of nodes is required. Specifically, from an operational perspective, in situations where parallel traffic trunks are warranted, it would be useful to have some attribute that can be used to indicate the relative proportion of traffic to be carried by each traffic trunk. The underlying protocols will then map the load onto the traffic trunks according to the specified proportions. It is also, generally desirable to maintain packet ordering between packets belong to the same micro-flow (same source address, destination address, and port number). 5.7 Priority attribute The priority attribute defines the relative importance of traffic trunks. If a constraint based routing framework is used with MPLS, then priorities become very important because they can be used to determine the order in which path selection is done for traffic trunks at connection establishment and under fault scenarios. Priorities are also important in implementations that permit preemption, because they can be used to impose a partial order on the set of traffic trunks according to which preemptive policies can be actualized. 5.8 Preemption attribute The preemption attribute determines whether a traffic trunk can preempt another traffic trunk from a given path, and whether another traffic trunk can preempt a specific traffic trunk. Preemption is useful for both traffic oriented and resource oriented performance Awduche, et al [Page 17] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 objectives. Within a differentiated services environment, preemption can used to assure that high priority traffic trunks can always be routed through relatively favorable paths. 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 which are designated as preemptable. A traffic trunk which is specified as non-preemptable cannot be preempted by any other trunks, regardless of relative priorities. A traffic trunk which is designated as preemptable can be preempted by higher priority trunks which are preemptor enabled. Although useful, preemption is not considered a mandatory attribute under the current best effort Internet service model. However, in a differentiated services scenario, the need for preemption becomes more compelling. 5.9 Resilience Attribute The resilience attribute determines the behavior of a traffic trunk under fault conditions. That is, when a fault occurs along the path through which the traffic trunk traverses. The following are the basic problems that need to be addressed under such circumstances: (1) fault detection, (2) failure notification, (3) recovery and service restoration. Obviously, an MPLS implementation will have to incorporate mechaisms that address these issues. Many recovery policies can be specified for traffic trunks whose established paths are impacted by faults. The following are a few examples of feasible schemes: 1. Do not reroute the traffic trunk. For example, a survivability scheme might be in place which guarantees service continuity under failure scenarios without the need to reroute traffic trunks. 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; some of which might be combinations of the above. A "basic" resilience attribute indicates the recovery procedure Awduche, et al [Page 18] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 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 be taken under fault scenarios. For example, an extended resilience attribute might specify a set of alternate paths to use under fault conditions, and the rules that govern the relative preference of each specified path. Resilience attributes mandate close interaction between MPLS and routing. 5.10 Policing attribute The policing attribute determine the actions that should be taken by the underlying protocols when a traffic trunk becomes non-compliant. That is, when a traffic trunk exceeds its contract as specified in the traffic parameters. In general, policing attributes can indicate whether a non-conformant traffic trunk is to be rate limited, tagged, or simply forwarded without any policing action. This aspect is discussed in the MPLS traffic management draft [10]. If policing is used, then adaptations of established algorithms such as the ATM Forum's GCRA [12] can be used to perform this function. Policing is necessary in many operational scenarios, but is quite undesirable in many 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. Therefor, from a Traffic Engineering perspective, it is necessary to be able to administratively enable or disable traffic policing for each traffic trunk. 6.0 Resource Attributes Resource attributes are part of the topology state parameters, which are used to constrain the routing of traffic trunks through specific resources. 6.1 Maximum Allocation Multiplier The maximum allocation multiplier (MAM) of a resource is an administratively configurable attribute which determines the proportion of the resource that is available for allocation to traffic trunks. This attribute is mostly applicable to link Awduche, et al [Page 19] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 bandwidth. However, in general, it can also be applied to buffer resources on LSRs. The concept of MAM is analogous to the concepts of subscription and booking factors in frame relay and ATM networks. It is possible to choose values of the MAM such that a resource can be under-allocated or over-allocated. A resource is said to be under-allocated if the aggregate demands of all traffic trunks (as expressed in the trunk traffic parameters) that can be allocated to it is always less than the capacity of the resource. A resource is said to be over-allocated if the aggregate demands of traffic trunks allocated to it can exceed the capacity of the resource. Under-allocation can be used to bound the utilization of resources. However,the situation under MPLS is more complex than in circuit switched schemes because under MPLS, some flows can be routed via conventional hop by hop protocols (also via explicit paths) without consideration for resource constraints. Over-allocation can be used to take advantage of the statistical characteristics of traffic in order to implement more efficient resource allocation policies. In particular, over-allocation can be used in situations where the peak demands of traffic trunks do not coincide in time. 6.2 Resource Class Attribute Resource class attributes are administratively assigned parameters which express some notion of "class" for resources. Resource class attributes can be viewed as "colors" which are assigned to resources, such that the set of resources with the same "color" conceptually belong to the same class. Resource class attributes can be used to implement a variety of policies. The key resources of interest here are links. When applied to links, the resource class attribute effectively becomes become an aspect of the "link state" parameters. From a Traffic Engineering perspective, the concept of resource class attributes is a powerful abstraction, which can be used to implement a lot of policies with regard to both traffic and resource oriented performance optimization. Specifically, resource class attributes can be used to: 1. Apply uniform policies to a set of resources which need not be in the same topological region. 2. Specify the relative preference of sets of resources for path placement of traffic trunks. Awduche, et al [Page 20] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 3. Explicitly restrict the placement of traffic trunks to specific subsets of resources. 4. Implement generalized inclusion / exclusion policies. 5. Enforce traffic locality containment policies. That is policies that seek to contain local traffic within specific topological regions of the network. 7.0 Constraint Based Routing This section discusses the issues that pertain to constraint based routing in MPLS domains. In contemporary terminology, constraint based routing is often referred to as "QoS Routing" see [5,6,7,11]. However, we prefer the term "constraint based routing," as it more aptly captures the envisaged functionality; which in general 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 that originates 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 and other topology state information. A constraint based routing framework can greatly reduce the level of manual configuration required to actualize Traffic Engineering policies. In practice, the Traffic Engineer or an operator will administratively 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 that satisfies the expectations. If necessary, the Awduche, et al [Page 21] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 traffic engineer can then use manually configured explicit routes to perform fine grained optimization. 7.1 Basic Features of Constraint Based Routing A constraint based routing framework should be able to at least automatically obtain a basic feasible solution to the traffic trunk path placement problem. In general the constraint based routing problem is known to be intractable. However, in practice, a very simple well known heuristic (see eg, [11]) 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. It is easy to see that if a feasible path exists, then the above simple procedure will find it. Additional rules can be specified to break ties, and perform further optimizations. 7.2 Implementation Considerations Many commercial implementations of frame relay and ATM switches already support some notion of constraint based routing. For such devices, or novel MPLS centric contraptions devised therefrom, it should be relatively easy to extend the current constraint based routing implementations to accommodate the peculiar requirements of MPLS. For routers that use topology driven hop by hop IGPs, constraint based routing can be incorporated in at least one of two ways: 1. Extend current IGP protocols such as OSPF and ISIS to support constraint based routing. Effort is already underway to provide such extensions to OSPF (see [5,7]). 2. Add a constraint based routing process to each router which can co-exists with current IGPs. This scenario is depicted in Figure 1. Awduche, et al [Page 22] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 ------------------------------------------ | 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 manual explicit path configurations required to achieve Traffic Engineering objectives. 8.0 Conclusion This manuscript presented a set of requirements for Traffic Engineering over MPLS. A number of capabilities were described Awduche, et al [Page 23] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 aimed at enhancing the applicability of MPLS to Traffic Engineering in the Internet. It should be noted that some of the issues described here can be addressed by incorporating a minimal set of building blocks into MPLS, and then using a network management superstructure to extend the functionality in order to realize the requirements. Also, the constraint based routing framework need not be part of the core MPLS specifications. However, MPLS does require some interaction with a constraint based routing framework in order to meet the requirements. 9.0 References [1], "A Proposed Architecture for MPLS", 3/1998, draft-ietf-mpls-arch-01.txt, Rosen, Viswanathan, Callon [2] "A Framework for Multiprotocol Label Switching", 7/1997, draft-ietf-mpls-framework-01.txt, Callon, Doolan, Feldman, Fredette, Swallow, Visanathawan [3] "Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)," 1/1998, draft-li-paste-00.txt, Li, Rekhter. [4] "Tag Switching Architecture - Overview", 7/1997, draft-rekhter-tagswitch-arch-01.txt, Rekhter, Davie, Katz, Rosen, Swallow [5] "Quality of Service Extensions to OSPF", 9/1997 draft-zhang-qos-ospf-01, Zhang, Sanchez, Salkewicz, Crawley [6] "A framework for QoS Based Routing in the Internet" draft-ietf-qosr-framework-02-txt, Crawley, Nair, Rajagopalan, Sandick. [7] "QoS Routing Mechanisms and OSPF Extensions" draft-guerin-qos-routing-ospf-01-txt, Guerin, Kamat, Orda, Przygienda, Williams. [8] "A Taxonomy for Congestion Control Algorithms in Packet Switching Networks," C. Yang and A. Reddy, IEEE Network Magazine, July/August 1995, Volume 9, Number 5 [9] "Use of Label Switching With RSVP," 3/1998, draft-ietf-mpls-rsvp-00.txt, Davie, Rekhter, Rosen, Viswanathan, Srinivasan, Blake. Awduche, et al [Page 24] Internet Draft draft-awduche-mpls-traffic-eng-00.txt April 1998 [10] "A Framework for Traffic Management in MPLS Networks," 3/1998, draft-vaananen-MPLS-TM-framework-00.txt, Vaananen, Ravikanth [11] "Routing Subject to Quality of Service Constraints in Integrated Communication Networks," W. Lee, M. Hluchyi, and P. Humblet, IEEE Network, July 1995, pp 46-55. [12] "Traffic Management Specification: Version 4.0" 4/1996. ATM Forum. 10.0 Acknowledgements The authors would like to thank Yakov Rekhter for his thoughtful and insightful review of an earlier draft of this document. The authors would also like to thank Louis Mamakos for his helpful suggestions, and Curtis Villamizar for providing some useful feedback. 11.0 AUTHORS' ADDRESSES Daniel O. Awduche Joe Malcolm Johnson Agogbua UUNET Technologies UUNET Technologies UUNET Technologies 3060 Williams Drive 3060 Williams Drive 3060 Williams Drive Fairfax, VA 22031 Fairfax, VA 22031 Fairfax, VA 22031 awduche@uu.net jmalcolm@uu.net ja@uu.net 703-208-5277 703-206-5895 703-206-5794 Mike O'Dell Jim McManus UUNET Technologies UUNET Technologies 3060 Williams Drive 3060 Williams Drive Fairfax, VA 22031 Fairfax, VA 22031 mo@uu.net jmcmanus@uu.net 703-206-5890 703-206-5607 Awduche, et al Expires October 1998 [Page 25]