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