Traffic Engineering Working Group Don Fedyk Internet Draft Anoop Ghanwani Expiration Date: April 2000 Nortel Networks Corp. October 1999 Metrics and Resource Classes for Traffic Engineering draft-fedyk-mpls-te-metrics-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 obsolete 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract There has recently been a lot of activity in defining the components for MPLS-based traffic engineering. This includes the recent extensions of the Interior Gateway Protocols (IGPs) to carry metrics and resource class information about links. This memo explores additional metrics that are useful for traffic engineering. We also describe some of the subtleties associated with the use of the resource class (or color) vector that has been defined in the IGP extensions. Fedyk, et. al. 1 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 1. Introduction Present-day IP networks do not have much support for traffic engineering features. To address this issue, many of the working groups are working together to define the methodologies that are required for providing traffic engineering features [TEREQ]. Basically, there has been activity in the following areas: - Extension of the IGP routing protocols (OSPF and IS-IS) for carrying additional metrics and resource class information about links [OSPF,ISIS]; and - Providing signaling support for traffic engineering via MPLS [RSVP,CRLDP]. This draft provides a brief overview of different metrics that are useful for traffic engineering. We argue that it is better to allow the advertisement of multiple metrics because they can in fact be used when performing connection-oriented routing as would be the case in a network running MPLS. In the past, there have been attempts to define multiple metric types. However, IP is based on a connectionless routing paradigm and therefore it is difficult to provide a scalable solution that is able to use multiple metrics. One of the reasons for this is that every router in the network would need to maintain separate shortest-path spanning trees, one for each metric type. This is not an issue with a network running MPLS-based traffic engineering. The routes for traffic engineering label switched paths (LSPs) can be computed on demand, and therefore different metrics may be used for each LSP. For example, it may be desirable to minimize the economic cost of the path for one LSP, while for another LSP the goal may be minimizing the end-to-end delay. Note that we are not recommending that the multiple advertised metrics be used simultaneously; the multiple constraint problem is known to be NP-complete. It is simply desirable to use a different metric for path selection depending on the requirements of the LSP. The remainder of this draft is organized as follows. Section 2 discusses different routing metrics. Section 3 discusses the use of metrics in traffic engineering and provides a recommendation for the metrics that should be advertised by routing protocols. Section 4 discusses the use of the resource class vector, a new field that is being advertised by the IGP routing protocols, but about which little has been said so far. 2. Routing Metrics A metric is a weight that is assigned to links in the network to indicate the relative preference of a link during path computation. Usually, metrics are selected so that they allow the computation of paths that meet certain constraints. Metrics for path selection can be classified using the following two criteria: Fedyk, et. al. April 2000 2 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 - Additive/non-additive: This refers to whether or not the path metric is obtained by adding the metric value for all links in the path. Examples of additive constraints include delay and hop count. Bandwidth is an example of a non-additive constraint. On the other hand, it is also possible to look at bandwidth as an additive metric by using link costs that are in inverse proportion to available bandwidth; in such cases, the shortest path corresponds to the path with the most bandwidth. - Static/dynamic: A static metric doesn't change with time. This includes metrics such as hop count and propagation delay of a link. A dynamic metric changes with traffic conditions in the network. An example is bandwidth and queuing delays on a link. Metrics are typically assigned positive numbers. Additive metrics can have a fairly large range of values starting from a small positive number and going all the way up to infinity, which in reality means there is no connection. As long as the additive metric is a positive number the routing systems can converge on loop free paths. In all metric schemes, there is a maximum metric, that means no connection, but there may be other limits due to the dynamic range. It is often challenging to find good ways to efficiently represent the complete dynamic range of metric values. One result of this is that many of the standards-based metrics are simple small integer values with a limited dynamic range. The four factors of bandwidth, delay, delay-jitter and loss or error probability are often driving forces in the determination of metrics. The commonly used metrics include but are not limited to: - Hop count - Bandwidth - Delay - Administrative cost - Economic cost A brief description of each of these metric types follows. 2.1 Hop-based metrics A Hop based metric is used to minimize the number of intermediate switches traversed, thereby minimizing the resources used in the network. It also, therefore maximizes the number of equal cost paths in a network. The hop-based metric is also the degenerative form of many other metric types when the link attributes are considered equal. This type can be used to maximize the number of equal cost paths to a destination for load sharing schemes. 2.2 Bandwidth-based metrics Fedyk, et. al. April 2000 3 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 A Bandwidth based metric is used to find the fewest large pipes to the destination. This metric can be assigned in a relative fashion or it can be algorithmically determined. Algorithmic determination has proven to be a challenge since the dynamic range of links has changed from 10^2 to 10^12 over the years, and is expected to go beyond this in future. This complete range is not usually used at a single time in a domain a range of 10^5 between the highest and lowest link speeds are not uncommon. The formula for determination is usually in the form of the reciprocal of bandwidth. A 16 to 32 bit number is usually required to represent this effectively in an integer format. Bandwidth metrics that are not algorithmically determined use a coarse representation of bandwidth rather than a true value. A bandwidth-based metric is a true minimizing metric since traffic that uses the higher speed links is more likely to get through. 2.2.1 Bandwidth Usage An absolute bandwidth available at holding priority has been added for Traffic Engineering [OSPF,ISIS]. LSPs that specify traffic parameters with bandwidth allocations can use this usage-based metric instead of the bandwidth metric to ensure sufficient bandwidth allocation. In a sense, this is a dynamic metric. 2.3 Delay-based metrics Static delay based metrics have been used for representing the propagation and the emission delay of a link. This metric is used to minimize the end-to-end delay experienced by a packet. The propagation delay is a fixed quantity that is related to the medium and the physical distance that the signal travels. The emission delay is related to the time that it takes to transmit a packet from the fist bit sent to the last bit sent. This is a function of the bandwidth of the link. The combination of emission and propagation delay for a given packet size yields a value that represents the minimum delay that a packet would experience when sent from one node to the other. This is a fixed number. The delay metric represents a number of milliseconds or microseconds. Again the dynamic range of links has some bearing on the emission delay but the propagation delay tends to be stable in the millisecond range. The link speed is a gauge of how reliable the delay metric is since, as link speed increases the emission component becomes negligible. 2.4 Economic cost or expense-based metrics Cost based metrics are assigned based on attributes of links that represent a usage cost for a link. These are not to be confused with administrative weight. With the advent of usage charging for services such as Frame Relay and ATM, and the use of tunnels over Fedyk, et. al. April 2000 4 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 these technologies, a true cost per traffic sent can be calculated. The value of this type of metric is that traffic that does not want to incur charges for using a link or set of links. 2.5 Administrative weight This metric is assigned based on a combination of factors. The administrated weight attempts to meld several of the other metric attributes into a single metric. The weight can be adjusted. This type of metric is commonly used to differentiate links that differ from one another by some characteristic. It is important to realize that this is a significant compromise for traffic engineering since the melding of metric types reduces the ability to differentiate routes. 3. Traffic engineering trends Recently, in the MPLS traffic engineering space, the addition of bandwidth reservation and allocation statistics represents dynamic information that can be used to engineer LSPs that have traffic parameters. 3.1 Multiple traffic engineering (TE) metrics Included with the recent work is the introduction of a new single metric for traffic engineering. However, the introduction of a single metric is limiting since traffic engineering can have the goal of maximizing throughput, minimizing hops, minimizing delay or distance, minimizing cost or minimizing resource usage. In such systems the metric type chosen is a guide to generating paths and will attempt to minimize the metric subject to the other constraints. There is little overhead for advertising multiple metrics for traffic engineering since only the static metrics need to be propagated. 3.2 Bandwidth allocation for MPLS TE Bandwidth allocation of MPLS TE LSPs with traffic parameters represents a usage-based constraint that is dynamic. As bandwidth is consumed on a link, new LSPs must look for other links to satisfy their bandwidth requirements. Interestingly enough, the value of maximizing throughput is not required for paths that specify minimum traffic profiles and allocate bandwidth. 3.3 Metric recommendation Fedyk, et. al. April 2000 5 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 It is recommended that at least four additional metrics be defined for traffic engineering, in addition to the single metric that is used for connectionless IP routing. This would yield the following 5 metrics: - Connectionless Metric (for use with connectionless routing) - Traffic Engineering Metric 1 (32 bits) - Traffic Engineering Metric 2 (32 bits) - Traffic Engineering Metric 3 (32 bits) - Reserved (32 bits) The connectionless metric may be used to route LSPs along routes that would be selected by the IGP for connectionless routing. It is network administrative decision on whether a metric is supported. The dynamic range of 32 is more than sufficient for the metrics. A possible definition of the TE metrics could be: - TE Metric 1: Delay Based Metric (Minimize delay) - TE Metric 2: Cost/Administrative Based Metric (Minimize cost) - TE Metric 3: Hop based Metric (Minimize resource usage) 4. Resource classes The IGPs have recently been extended to carry a resource class or color vector for every link. This vector is 32 bits long and represents certain characteristics that the link satisfies. Little has been said about the expected use of this field. This section describes some of the ways it may be used and the subtleties associated with it. 4.1 Using the resource class or color vector The resource class vector is one of the attributes flooded by the IGP, and is used by routers for computing a constraint-based path that uses only those links that satisfy the required criteria. The flooding scope of this information is a single area in OSPF and level-1 in IS-IS. When computing a constraint-based route that traverses links in a single area, the router computing the path uses this information to determine which links satisfy the requested criteria. In this case, it is not necessary to carry the color vector of the request in the setup message. However, when setting up a hierarchical constraint-based route (i.e. one that traverses multiple areas), it becomes necessary to carry the resource class vector that is desired for the label switched path (LSP). When a router receives a request message during path setup, it would be expected to perform the following logical operation: Fedyk, et. al. April 2000 6 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 ((color vector of request) & (color vector of link)) == (color vector of request) The request gets forwarded only if the above expression evaluates to TRUE. If a suitable link cannot be found, the request is rejected. Using the above operation, there are two basic definitions of bits in the color vector that can be supported: The link attribute is taken from a set of attributes. A given link may match one or more of these attributes requiring a bit to be set in that position. A link satisfies a certain attribute up to a numeric value (e.g. a link has a security level of 5). In that case, all of the bits that correspond to that numeric value or lower must be set high at the time of configuration. Note that in the second case, there is some interdependence between the bits that must be taken into account while creating the color vector for the link. For example, in a system where links are rated with one of 8 levels of a certain attribute, the links at each level would have the following colors: Level 0: 10000000 Level 1: 11000000 Level 2: 11100000 .. Level 8: 11111111 There are two drawbacks to using the simple operation defined above: First, the usage of bits is sub-optimal; n levels of a particular characteristic require n bits in the color vector. While n levels of a certain characteristic can be represented with just lg(n) bits, it would require the capability to perform operations such as _less than_ and _greater than_. Second, the above operation cannot support the case where there are three or more attributes in a set, of which some unordered subset of those is acceptable. For instance, if we have _link type_ as a characteristic and we classify links as terrestrial, low-orbit satellite and high-orbit satellite links, and if we wish to request either terrestrial or low-orbit satellite links, there is no way to do that. However, if the same set was ordered by lower delay, (e.g. terrestrial, low-orbit satellite, high orbit satellite) then as an ordered subset this would still work. 4.2 Link characteristics A few examples of link characteristics that might be desirable to have in the color vector include: Fedyk, et. al. April 2000 7 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 Satellite/terrestrial: A link can be either a satellite link or a terrestrial link. When making a request, the user can specify the use of only terrestrial links, or satellite links, or either. Security level: A link can be rated as being at one of eight security levels ranging from completely insecure to highest security with levels in between. A typical request would be to use only links with a security of 5 or higher for the connection. Link reliability: A link can be rated as being very reliable (possibly a link with automatic protection switching at the link layer) to one which is highly unreliable (i.e. loss characteristics of the link may be subject to weather or solar activity). This factor really is a function of loss rate and availability of a link. Some forms of transmission such as radio-based wireless and microwave are susceptible to weather conditions. These mediums are suitable for certain types of traffic. 4.3 Standardizing resource classes It is worthwhile to explore the demand for standardized resource masks. This will allow requests to propagate seamlessly across areas since the semantics of the bits will have a universal value. One way to do this could be to have global and local subsets of the color mask. The bit semantics of the global portion would be standardized, while the bit semantics for the local portion would be left for definition by the developers/users of the router. The present color vector can be split equally into global and local portions as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Globally significant | Local use | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bits 0-15: Global use Bit 0: satellite Bit 1: terrestrial Bit 2: highest reliability Bit 3: high reliability Bit 4: medium reliability Bit 5: low reliability Bits 6-15: reserved Bits 16-32: Local use 6. Security considerations This document raises no new security issues. Fedyk, et. al. April 2000 8 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 5. Acknowledgements The authors are grateful to Bilel Jamoussi, Peter Ashwood-Smith and Darek Skalecki for their helpful comments on the document. 6. References [TEREQ] D. Awduche et al., "Requirements for traffic engineering over MPLS," RFC 2702, September 1999. [ISIS] H. Smit, T. Lee, "IS-IS extensions for traffic engineering," Internet Draft, draft-ietf-isis-traffic-01.txt, May 1999. [OSPF] D. Katz, D. Yeung, "Traffic engineering extensions to OSPF," Internet Draft, draft-katz-yeung-ospf-traffic-00.txt, April 1999. [CRLDP] B. Jamoussi et al., "Constraint-based LSP setup using LDP," Internet Draft, draft-ietf-mpls-cr-ldp-03.txt, September 1999. [RSVP] D. Awduche et al., "Extensions to RSVP for LSP tunnels," Internet Draft, draft-ietf-mpls-rsvp-lsp-tunnel-04.txt, September 1999. 7. Authors' Addresses Don Fedyk Anoop Ghanwani Nortel Networks Corp. Nortel Networks Corp. 600 Technology Park Drive 600 Technology Park Drive Billerica, MA 01821 Billerica, MA 01821 USA USA Phone: +1-978-288-4506 Phone: +1-978-288-4514 dwfedyk@nortelnetworks.com aghanwan@nortelnetworks.com Full Copyright Statement "Copyright (C) The Internet Society (1999). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of Fedyk, et. al. April 2000 9 Internet Draft draft-fedyk-mpls-te-metrics.00.txt September, 1999 developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. Fedyk, et. al. April 2000 10