draft-ietf-mpls-traffic-eng-00.txt   draft-ietf-mpls-traffic-eng-01.txt 
Internet Engineering Task Force
Network Working Group Daniel O. Awduche INTERNET-DRAFT
Internet Draft Joe Malcolm MPLS Working Group Daniel O. Awduche
Expiration Date: April, 1999 Johnson Agogbua Category: Informational Joe Malcolm
Expiration Date: December 1999 Johnson Agogbua
Mike O'Dell Mike O'Dell
Jim McManus Jim McManus
UUNET-Worldcom UUNET (MCI Worldcom)
October, 1998 June, 1999
Requirements for Traffic Engineering Over MPLS Requirements for Traffic Engineering Over MPLS
draft-ietf-mpls-traffic-eng-00.txt draft-ietf-mpls-traffic-eng-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft and is in full conformance with
documents of the Internet Engineering Task Force (IETF), its areas, all provisions of Section 10 of RFC2026.
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. 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 Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
To view the entire list of current Internet-Drafts, please check The list of current Internet-Drafts can be accessed at
the "1id-abstracts.txt" listing contained in the Internet-Drafts http://www.ietf.org/ietf/1id-abstracts.txt
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
(Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au The list of Internet-Draft Shadow Directories can be accessed at
(Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu http://www.ietf.org/shadow.html.
(US West Coast).
Abstract Abstract
This document presents a set of requirements for Traffic This document presents a set of requirements for Traffic Engineering
Engineering over Multiprotocol Label Switching (MPLS). It over Multiprotocol Label Switching (MPLS). It identifies the
identifies the functional capabilities required to implement functional capabilities required to implement policies that
policies that facilitate efficient and reliable network operations facilitate efficient and reliable network operations in an MPLS
in an MPLS domain. These capabilities can be used to optimize the domain. These capabilities can be used to optimize the utilization of
utilization of network resources, and enhance traffic oriented network resources and to enhance traffic oriented performance
performance characteristics. characteristics.
Table of Contents Table of Contents
1.0 Introduction .................................... 3 1.0 Introduction .................................... 3
1.1 Terminology .................................... 4
1.2 Document Organization .................................... 4
2.0 Traffic Engineering ...................................... 4 2.0 Traffic Engineering ...................................... 4
2.1 Traffic Engineering Performance Objectives ............... 4 2.1 Traffic Engineering Performance Objectives ............... 5
2.2 Traffic and Resource Control ............................. 6 2.2 Traffic and Resource Control ............................. 6
2.3 Limitations of Current IGP Control Mechanisms ............ 6 2.3 Limitations of Current IGP Control Mechanisms ............ 7
3.0 MPLS and Traffic Engineering ............................. 7 3.0 MPLS and Traffic Engineering ............................. 8
3.1 Induced MPLS Graph ....................................... 8 3.1 Induced MPLS Graph ....................................... 9
3.2 The Fundamental Problem of Traffic Engineering Over MPLS . 9 3.2 The Fundamental Problem of Traffic Engineering Over MPLS . 10
4.0 Augmented Capabilities for Traffic Engineering Over MPLS . 10 4.0 Augmented Capabilities for Traffic Engineering Over MPLS . 10
5.0 Traffic Trunk Attributes and Characteristics ........... 10 5.0 Traffic Trunk Attributes and Characteristics ........... 11
5.1 Bidirectional Traffic Trunks ............................. 11 5.1 Bidirectional Traffic Trunks ............................. 12
5.2 Basic Operations on Traffic Trunks ....................... 12 5.2 Basic Operations on Traffic Trunks ....................... 13
5.3 Accounting and Performance Monitoring .................... 12 5.3 Accounting and Performance Monitoring .................... 13
5.4 Basic Attributes of Traffic Trunks ....................... 13 5.4 Basic Attributes of Traffic Trunks ....................... 13
5.5 Traffic Parameter Attributes ............................ 13 5.5 Traffic Parameter Attributes ............................ 14
5.6 Generic Path Selection and Management Attributes ......... 14 5.6 Generic Path Selection and Management Attributes ......... 15
5.6.1 Administratively Specified Explicit Paths ................ 15 5.6.1 Administratively Specified Explicit Paths ................ 15
5.6.2 Hierarchy of Preference Rules for Multi-paths ............ 15 5.6.2 Hierarchy of Preference Rules for Multi-paths ............ 16
5.6.3 Resource Class Affinity Attributes ....................... 16 5.6.3 Resource Class Affinity Attributes ....................... 16
5.6.4 Adaptivity Attribute ..................................... 16 5.6.4 Adaptivity Attribute ..................................... 17
5.6.5 Load Distribution Across Parallel Traffic Trunks ......... 18 5.6.5 Load Distribution Across Parallel Traffic Trunks ......... 18
5.7 Priority Attribute ....................................... 18 5.7 Priority Attribute ....................................... 19
5.8 Preemption Attribute ..................................... 18 5.8 Preemption Attribute ..................................... 19
5.9 Resilience Attribute ..................................... 19 5.9 Resilience Attribute ..................................... 20
5.10 Policing Attribute ...................................... 20 5.10 Policing Attribute ...................................... 21
6.0 Resource Attributes ...................................... 21 6.0 Resource Attributes ...................................... 22
6.1 Maximum Allocation Multiplier ............................ 21 6.1 Maximum Allocation Multiplier ............................ 22
6.2 Resource Class Attribute ................................ 22 6.2 Resource Class Attribute ................................ 22
7.0 Constraint Based Routing ................................ 22 7.0 Constraint-Based Routing ................................ 23
7.1 Basic Features of Constraint Based Routing ............... 23 7.1 Basic Features of Constraint-Based Routing ............... 24
7.2 Implementation Considerations ............................ 24 7.2 Implementation Considerations ............................ 25
8.0 Conclusions ............................................. 25 8.0 Conclusion ............................................. 26
9.0 References ............................................. 26 9.0 Security Considerations .................................. 27
10.0 Acknowledgments .......................................... 27 10.0 References ............................................. 27
11.0 Author's Address ......................................... 27 11.0 Acknowledgments .......................................... 28
12.0 Author's Address ......................................... 28
1.0 Introduction 1.0 Introduction
Multiprotocol Label Switching (MPLS) [1,2] integrates a label Multiprotocol Label Switching (MPLS) [1,2] integrates a label
swapping framework with network layer routing. The basic idea swapping framework with network layer routing. The basic idea
consists in assigning short fixed length labels to packets at involves assigning short fixed length labels to packets at the
the ingress to an MPLS cloud, based on the concept of forwarding ingress to an MPLS cloud (based on the concept of forwarding
equivalence classes [1,2]. Throughout the interior of the MPLS equivalence classes [1,2]). Throughout the interior of the MPLS
domain, the labels attached to packets are used to make forwarding domain, the labels attached to packets are used to make forwarding
decisions; usually without recourse to the original packet headers. decisions (usually without recourse to the original packet headers).
From this relatively simple paradigm, a set of powerful constructs A set of powerful constructs to address many critical issues in the
can be devised that address a number of critical issues in the emerging differentiated services Internet can be devised from this
emerging differentiated services Internet. One of the most relatively simple paradigm. One of the most significant initial
significant initial applications of MPLS will be in Traffic applications of MPLS will be in Traffic Engineering. The importance
Engineering. This aspect is already well recognized (see [1,2,3,9]). of this application is already well-recognized (see [1,2,3]).
This manuscript focuses exclusively on the Traffic Engineering This manuscript is exclusively focused on the Traffic Engineering
applications of MPLS. Specifically, the goal of this document is to applications of MPLS. Specifically, the goal of this document is to
highlight the issues and requirements for Traffic Engineering in a highlight the issues and requirements for Traffic Engineering in a
large Internet backbone, in the expectation that the MPLS large Internet backbone. The expectation is that the MPLS
specifications, or implementations derived therefrom, will address specifications, or implementations derived therefrom, will address
the realization of these objectives. A description of the basic the realization of these objectives. A description of the basic
capabilities and functionality required of an MPLS implementation to capabilities and functionality required of an MPLS implementation to
accommodate the requirements is also presented. accommodate the requirements is also presented.
It should be noted that even though we focus on Internet backbones, It should be noted that even though the focus is on Internet
the capabilities described here are equally applicable to Traffic backbones, the capabilities described in this document are equally
Engineering in enterprise networks; in short to any label switched applicable to Traffic Engineering in enterprise networks. In general,
network under a single technical administration in which at least the capabilities can be applied to any label switched network under
two paths exist between two nodes. 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 Some recent manuscripts have focused on the considerations pertaining
considerations pertaining to Traffic Engineering and Traffic to Traffic Engineering and Traffic management under MPLS, most
management under MPLS; notably the works of Li and Rekhter [3], and notably the works of Li and Rekhter [3], and others. In [3], an
Vaananen and Ravikanth [9]. In [3], an architecture is proposed architecture is proposed which employs MPLS and RSVP to provide
which employs MPLS and RSVP to provide scalable differentiated scalable differentiated services and Traffic Engineering in the
services and Traffic Engineering in the Internet. In [9], a Internet. The present manuscript complements the aforementioned and
general framework is described that introduces traffic management similar efforts. It reflects the authors' operational experience in
capabilities into MPLS. The present manuscript complements the managing a large Internet backbone.
aforementioned efforts, and reflects the authors' operational
experience in managing a large Internet backbone.
Throughout, the reader is assumed to be familiar with the MPLS 1.1 Terminology
terminology as defined in [1].
The reader is assumed to be familiar with the MPLS terminology as
defined in [1].
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [11].
1.2 Document Organization
The remainder of this document is organized as follows: Section 2 The remainder of this document is organized as follows: Section 2
discusses the basic functions of Traffic Engineering in the discusses the basic functions of Traffic Engineering in the Internet.
Internet. Section 3, gives an overview of the traffic Engineering Section 3, provides an overview of the traffic Engineering potentials
potentials of MPLS. Sections 1 to 3 can be regarded as background of MPLS. Sections 1 to 3 are essentially background material. Section
material. Section 4 presents an overview of the fundamental 4 presents an overview of the fundamental requirements for Traffic
requirements for Traffic Engineering over MPLS. Section 5 describes Engineering over MPLS. Section 5 describes the desirable attributes
the desirable attributes and characteristics of traffic trunks and characteristics of traffic trunks which are pertinent to Traffic
which are pertinent to Traffic Engineering. Section 6 presents a Engineering. Section 6 presents a set of attributes which can be
set of attributes which can be associated with resources to constrain associated with resources to constrain the routability of traffic
the routability of traffic trunks and LSPs through them. Section 7 trunks and LSPs through them. Section 7 advocates
argues in favor of the introduction of a "constraint based routing" the introduction of a "constraint-based routing" framework in MPLS
framework in MPLS domains. Finally, Section 8 contains our domains. Finally, Section 8 contains concluding remarks.
concluding remarks.
2.0 Traffic Engineering 2.0 Traffic Engineering
This section describes the basic functions of Traffic Engineering in This section describes the basic functions of Traffic Engineering in
an Autonomous System in the contemporary Internet. The limitations an Autonomous System in the contemporary Internet. The limitations of
of current IGPs with respect to traffic and resource control are current IGPs with respect to traffic and resource control are
highlighted. This section serves as motivation for the requirements highlighted. This section serves as motivation for the requirements
on MPLS. on MPLS.
Traffic Engineering (TE) is concerned with performance optimization of Traffic Engineering (TE) is concerned with performance optimization
operational networks. Specifically, the goal of Traffic Engineering of operational networks. In general, it encompasses the application
is to facilitate efficient and reliable network operations, and at of technology and scientific principles to the measurement, modeling,
the same time optimize the utilization of network resources. Traffic characterization, and control of Internet traffic, and the
Engineering is becoming an indispensable function in many large application of such knowledge and techniques to achieve specific
Autonomous Systems because of the high cost of network assets, and performance objectives. The aspects of Traffic Engineering that are
the commercial and competitive nature of the Internet. These factors of interest concerning MPLS are measurement and control.
emphasize the need for maximal operational efficiency.
A major goal of Internet Traffic Engineering is to facilitate
efficient and reliable network operations while simultaneously
optimizing network resource utilization and traffic performance.
Traffic Engineering has become 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 2.1 Traffic Engineering Performance Objectives
The key performance objectives associated with traffic engineering The key performance objectives associated with traffic engineering
can be classified as either: can be classified as being either:
1. traffic oriented or 1. traffic oriented or
2. resource oriented. 2. resource oriented.
Traffic oriented performance objectives include those aspects that Traffic oriented performance objectives include the aspects that
enhance the QoS of traffic streams. In a single class, best effort enhance the QoS of traffic streams. In a single class, best effort
Internet service model, the key traffic oriented performance Internet service model, the key traffic oriented performance
objectives include: minimization of packet loss, minimization of objectives include: minimization of packet loss, minimization of
delay, maximization of throughput, and enforcement of service level delay, maximization of throughput, and enforcement of service level
agreements. Under a single class best effort Internet service agreements. Under a single class best effort Internet service model,
model, minimization of packet loss is one of the most important minimization of packet loss is one of the most important traffic
traffic oriented performance objectives. Statistically bounded oriented performance objectives. Statistically bounded traffic
traffic oriented performance objectives (such as peak to peak packet oriented performance objectives (such as peak to peak packet delay
delay variation, loss ratio, and maximum packet transfer delay) might variation, loss ratio, and maximum packet transfer delay) might
become useful in the forthcoming differentiated services Internet. become useful in the forthcoming differentiated services Internet.
Resource oriented performance objectives include those aspects Resource oriented performance objectives include the aspects
that pertain to the optimization of resource utilization. Efficient pertaining to the optimization of resource utilization. Efficient
management of network resources is the vehicle for the attainment management of network resources is the vehicle for the attainment of
of resource oriented performance objectives. In particular, it is resource oriented performance objectives. In particular, it is
generally desirable to ensure that subsets of network resources generally desirable to ensure that subsets of network resources do
do not become over utilized and congested, while other subsets not become over utilized and congested while other subsets along
along alternate feasible paths remain underutilized. Bandwidth alternate feasible paths remain underutilized. Bandwidth is a crucial
is a crucial and scarce resource in contemporary networks. resource in contemporary networks. Therefore, a central function of
Therefor, a central function of Traffic Engineering is Traffic Engineering is to efficiently manage bandwidth resources.
efficient management of bandwidth resources.
Minimizing congestion is a major traffic and resource oriented Minimizing congestion is a primary traffic and resource oriented
performance objective. The interest here is not on transient performance objective. The interest here is on congestion problems
congestion resulting from instantaneous bursts, but rather on that are prolonged rather than on transient congestion resulting from
congestion problems that are more prolonged. Congestion typically instantaneous bursts. Congestion typically manifests under two
manifests under two scenarios: scenarios:
1. When network resources are insufficient or inadequate to 1. When network resources are insufficient or inadequate to
accommodate offered load. accommodate offered load.
2. When traffic streams are inefficiently mapped onto available 2. When traffic streams are inefficiently mapped onto available
resources; causing subsets of network resources to become resources; causing subsets of network resources to become
over-utilized while others remain underutilized. over-utilized while others remain underutilized.
The first type of congestion problem can be addressed through: (i) The first type of congestion problem can be addressed by either: (i)
capacity expansion and (ii) classical congestion control techniques expansion of capacity, or (ii) application of classical congestion
which attempt to regulate the demand, such that it fits onto control techniques, or (iii) both. Classical congestion control
available resources. Classical techniques for congestion control techniques attempt to regulate the demand so that the traffic fits
include: rate limiting, window flow control, router queue onto available resources. Classical techniques for congestion control
management, schedule-based control, and others; (see [8] and the include: rate limiting, window flow control, router queue management,
references therein). schedule-based control, and others; (see [8] and the references
therein).
The second type of congestion problems, namely those resulting from The second type of congestion problems, namely those resulting from
inefficient resource allocation, can usually be addressed through inefficient resource allocation, can usually be addressed through
Traffic Engineering. Traffic Engineering.
In general, congestion resulting from inefficient resource In general, congestion resulting from inefficient resource allocation
allocation can be reduced by adopting load balancing can be reduced by adopting load balancing policies. The objective of
policies. The objective of such strategies is to minimize maximum such strategies is to minimize maximum congestion or alternatively to
congestion or alternatively to minimize maximum resource utilization, minimize maximum resource utilization, through efficient resource
through efficient resource allocation. When congestion is allocation. When congestion is minimized through efficient resource
minimized through efficient resource allocation, packet loss allocation, packet loss decreases, transit delay decreases, and
decreases, and aggregate throughput increases. Thereby, the aggregate throughput increases. Thereby, the perception of network
perception of network service quality experienced by end users service quality experienced by end users becomes significantly
becomes significantly enhanced. enhanced.
Even-though load balancing is an important network performance Clearly, load balancing is an important network performance
optimization policy, the capabilities provided for Traffic optimization policy. Nevertheless, the capabilities provided for
Engineering should be flexible enough, so that network Traffic Engineering should be flexible enough so that network
administrators can implement other policies which take account of administrators can implement other policies which take into account
the prevailing cost structure, and the utility or revenue model. the prevailing cost structure and the utility or revenue model.
2.2 Traffic and Resource Control 2.2 Traffic and Resource Control
Performance optimization of operational networks is fundamentally a Performance optimization of operational networks is fundamentally a
control problem. The Traffic Engineer acts as the controller control problem. In the traffic engineering process model, the
in an adaptive feedback control system, which includes a set of Traffic Engineer, or a suitable automaton, acts as the controller in
an adaptive feedback control system. This system includes a set of
interconnected network elements, a network performance monitoring interconnected network elements, a network performance monitoring
system, and a set of network configuration management tools. The system, and a set of network configuration management tools. The
Traffic Engineer formulates a control policy, observes the state of Traffic Engineer formulates a control policy, observes the state of
the network through the monitoring system, characterizes the the network through the monitoring system, characterizes the traffic,
traffic, and applies control actions to drive the network to a and applies control actions to drive the network to a desired state,
desired state, in accordance with the control policy. This can be in accordance with the control policy. This can be accomplished
done reactively by taking action in response to the current state of reactively by taking action in response to the current state of the
the network, or pro-actively by using forecasting techniques to network, or pro-actively by using forecasting techniques to
anticipate future trends and applying action to obviate predicted anticipate future trends and applying action to obviate the predicted
undesirable future states. undesirable future states.
Ideally, control actions should involve: Ideally, control actions should involve:
1. modifying traffic management parameters, 1. Modification of traffic management parameters,
2. modifying parameters associated with routing, and 2. Modification of parameters associated with routing, and
3. modifying attributes and constraints associated with resources. 3. Modification of attributes and constraints associated with
resources.
To the extent possible, it is desirable to minimize the level of The level of manual intervention involved in the traffic engineering
manual intervention involved in the traffic engineering process. process should be minimized whenever possible. This can be
This can be accomplished by automating aspects of the control accomplished by automating aspects of the control actions described
actions described above, in a distributed and scalable fashion. above, in a distributed and scalable fashion.
2.3 Limitations of Current IGP Control Mechanisms 2.3 Limitations of Current IGP Control Mechanisms
This subsection reviews some of the well known limitations of This subsection reviews some of the well known limitations of current
current IGPs with regard to Traffic Engineering. IGPs with regard to Traffic Engineering.
The control capabilities offered by existing Internet interior The control capabilities offered by existing Internet interior
gateway protocols are quite inadequate for Traffic Engineering. gateway protocols are not adequate for Traffic Engineering. This
This makes it difficult to actualize effective policies that address makes it difficult to actualize effective policies to address network
network performance problems. Indeed, IGPs based on shortest path performance problems. Indeed, IGPs based on shortest path algorithms
algorithms contribute significantly to congestion problems in contribute significantly to congestion problems in Autonomous Systems
Autonomous Systems within the Internet. SPF algorithms generally within the Internet. SPF algorithms generally optimize based on a
optimize based on a simple additive metric. Because these protocols simple additive metric. These protocols are topology driven, so
are topology driven, bandwidth availability and traffic bandwidth availability and traffic characteristics are not factors
characteristics are not taken into account in making routing considered in routing decisions. Consequently, congestion frequently
decisions. Consequently, congestion frequently occurs when: occurs when:
1. the shortest paths of multiple streams converge on specific 1. the shortest paths of multiple traffic streams converge on
links or router interfaces, or specific links or router interfaces, or
2. a given traffic stream is routed through a link or router 2. a given traffic stream is routed through a link or router
interface which does not have enough bandwidth to accommodate interface which does not have enough bandwidth to accommodate
it. it.
These scenarios manifest even when feasible alternate paths with These scenarios manifest even when feasible alternate paths with
excess capacity exist. It is this aspect of congestion problems excess capacity exist. It is this aspect of congestion problems (-- a
(-- a symptom of suboptimal resource allocation) that Traffic symptom of suboptimal resource allocation) that Traffic Engineering
Engineering aims to vigorously obviate. Equal cost path load aims to vigorously obviate. Equal cost path load sharing can be used
sharing can be used to address case (2) with some degree of success, to address the second cause for congestion listed above with some
but generally not case (1), especially in large networks with dense degree of success, however it is generally not helpful in alleviating
topology. congestion due to the first cause listed above and particularly not
in large networks with dense topology.
A popular means of circumventing the inadequacies A popular approach to circumvent the inadequacies of current IGPs is
of current IGPs is through an overlay model, using IP over through the use of an overlay model, such as IP over ATM or IP over
ATM or IP over frame relay. The overlay model extends the design frame relay. The overlay model extends the design space by enabling
space by enabling arbitrary virtual topologies to be provisioned arbitrary virtual topologies to be provisioned atop the network's
atop the network's physical topology. The virtual topology is physical topology. The virtual topology is constructed from virtual
constructed from virtual circuits which appear as physical links to circuits which appear as physical links to the IGP routing protocols.
IGP routing protocols. The overlay model also provides many The overlay model provides additional important services to support
important services which support traffic and resource control, traffic and resource control, including: (1) constraint-based routing
including: (1) constraint based routing at the VC level, (2) support at the VC level, (2) support for administratively configurable
for administratively configurable explicit VC paths, (3) path explicit VC paths, (3) path compression, (4) call admission control
compression, (4) call admission control functions, (5) traffic functions, (5) traffic shaping and traffic policing functions, and
shaping and traffic policing functions, and (6) survivability of (6) survivability of VCs. These capabilities enable the actualization
VCs. These capabilities enable the actualization of a variety of of a variety of Traffic Engineering policies. For example, virtual
Traffic Engineering policies. For example, virtual circuits can circuits can easily be rerouted to move traffic from over-utilized
easily be rerouted to move traffic from over-utilized resources onto resources onto relatively underutilized ones.
relatively underutilized ones.
For Traffic Engineering in large dense networks, it is desirable to For Traffic Engineering in large dense networks, it is desirable to
equip MPLS with a level of functionality at least commensurate with equip MPLS with a level of functionality at least commensurate with
current overlay models. Fortunately, this can be done in a fairly current overlay models. Fortunately, this can be done in a fairly
straight forward manner. straight forward manner.
3.0 MPLS and Traffic Engineering 3.0 MPLS and Traffic Engineering
This section provides an overview of the applicability of MPLS to This section provides an overview of the applicability of MPLS to
Traffic Engineering. Subsequent sections elaborate on the set of Traffic Engineering. Subsequent sections discuss the set of
capabilities required to meet the Traffic Engineering requirements. capabilities required to meet the Traffic Engineering requirements.
MPLS is strategically significant for Traffic Engineering because MPLS is strategically significant for Traffic Engineering because it
it can potentially provide most of the functionality available from can potentially provide most of the functionality available from the
the overlay model, in an integrated manner, and at lower cost than overlay model, in an integrated manner, and at a lower cost than the
competing alternatives. Equally importantly, MPLS offers the currently competing alternatives. Equally importantly, MPLS offers
possibility to automate aspects of the Traffic Engineering the possibility to automate aspects of the Traffic Engineering
function. This later consideration is left for further study and is function. This last consideration requires further investigation and
beyond the scope of this manuscript. is beyond the scope of this manuscript.
A note on terminology: The concept of MPLS traffic trunks is used A note on terminology: The concept of MPLS traffic trunks is used
extensively in the remainder of this document. According to Li and extensively in the remainder of this document. According to Li and
Rekhter [3], a traffic trunk is an aggregation of traffic flows of 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 the same class which are placed inside a Label Switched Path.
useful to view traffic trunks as atomic objects which can be Essentially, a traffic trunk is an abstract representation of traffic
routed; that is, the path through which a traffic trunk traverses to which specific characteristics can be associated. It is useful to
can be changed. In this respect, traffic trunks are similar to view traffic trunks as objects that can be routed; that is, the path
virtual circuits in ATM and Frame Relay networks. It is important through which a traffic trunk traverses can be changed. In this
to emphasize that there is a fundamental distinction between a respect, traffic trunks are similar to virtual circuits in ATM and
traffic trunk and the LSP through which it traverses. Additional Frame Relay networks. It is important, however, to emphasize that
characteristics of traffic trunks as used in this manuscript worth there is a fundamental distinction between a traffic trunk and the
noting are summarized in section 5.0. path, and indeed the LSP, through which it traverses. An LSP is a
specification of the label switched path through which the traffic
traverses. In practice, the terms LSP and traffic trunk are often
used synonymously. Additional characteristics of traffic trunks as
used in this manuscript are summarized in section 5.0.
The attractiveness of MPLS for Traffic Engineering can be The attractiveness of MPLS for Traffic Engineering can be attributed
attributed to the following factors: (1) explicit label switched to the following factors: (1) explicit label switched paths which are
paths which are not constrained by the destination based forwarding not constrained by the destination based forwarding paradigm can be
paradigm can be easily created through manual administrative action easily created through manual administrative action or through
or through automated action by the underlying protocols, (2) LSPs can automated action by the underlying protocols, (2) LSPs can
potentially be efficiently maintained, (3) traffic trunks can be potentially be efficiently maintained, (3) traffic trunks can be
instantiated and mapped onto LSPs, (4) a set of attributes can instantiated and mapped onto LSPs, (4) a set of attributes can be
be associated with traffic trunks which modulate their behavioral associated with traffic trunks which modulate their behavioral
characteristics, (5) a set of attributes can be associated with characteristics, (5) a set of attributes can be associated with
resources which constrain the placement of LSPs and traffic trunks resources which constrain the placement of LSPs and traffic trunks
across them, (6) MPLS allows for both traffic aggregation and across them, (6) MPLS allows for both traffic aggregation and
disaggregation whereas classical destination only based IP disaggregation whereas classical destination only based IP forwarding
forwarding permits only aggregation, (7) it is relatively easy to permits only aggregation, (7) it is relatively easy to integrate a
integrate a "constraint based routing" framework with MPLS, (8) a "constraint-based routing" framework with MPLS, (8) a good
good implementation of MPLS can offer significantly lower overhead implementation of MPLS can offer significantly lower overhead than
than competing alternatives for Traffic Engineering. Furthermore, competing alternatives for Traffic Engineering.
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 Additionally, through explicit label switched paths, MPLS permits a
focus only on the potential to create explicit LSPs. Although this quasi circuit switching capability to be superimposed on the current
capability is fundamental for Traffic Engineering, it is not really Internet routing model. Many of the existing proposals for Traffic
sufficient. Additional augmentations are required to foster the Engineering over MPLS focus only on the potential to create explicit
actualization of policies that lead to performance optimization of LSPs. Although this capability is fundamental for Traffic
large operational networks. Some of the necessary augmentations are Engineering, it is not really sufficient. Additional augmentations
described in this manuscript. are required to foster the actualization of policies leading to
performance optimization of large operational networks. Some of the
necessary augmentations are described in this manuscript.
3.1 Induced MPLS Graph 3.1 Induced MPLS Graph
This subsection introduces the concept of an "induced MPLS graph" This subsection introduces the concept of an "induced MPLS graph"
which is central to Traffic Engineering in MPLS domains. An induced which is central to Traffic Engineering in MPLS domains. An induced
MPLS graph is analogous to a virtual topology in an overlay model, MPLS graph is analogous to a virtual topology in an overlay model. It
and is logically mapped onto the physical network through the is logically mapped onto the physical network through the selection
selection of LSPs for traffic trunks. of LSPs for traffic trunks.
An induced MPLS graph consists of a set of LSRs which comprise the 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 nodes of the graph and a set of LSPs which provide logical point to
point connectivity between the LSRs, and hence serve point connectivity between the LSRs, and hence serve as the links of
as the links of the induced graph. Using the concept of label stacks the induced graph. it may be possible to construct hierarchical
(see [1]), it may be possible to construct hierarchical induced MPLS induced MPLS graphs based on the concept of label stacks (see [1]).
graphs.
Induced MPLS graphs are important because the basic problem of Induced MPLS graphs are important because the basic problem of
bandwidth management in an MPLS domain concerns how to efficiently bandwidth management in an MPLS domain is the issue of how to
map an induced MPLS graph onto the physical network topology. The efficiently map an induced MPLS graph onto the physical network
induced MPLS graph abstraction is formalized below. topology. The induced MPLS graph abstraction is formalized below.
Let G = (V, E, c) be a capacitated graph depicting the physical 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 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 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 (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 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. 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 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 V representing the set of LSRs in the network, or more precisely the
the set of LSRs that are the endpoints of at least one LSP. Here, F set of LSRs that are the endpoints of at least one LSP. Here, F is
is the set of LSPs, so that for x and y in U, the object (x, y) is the set of LSPs, so that for x and y in U, the object (x, y) is in F
in F if there is an LSP with x and y as endpoints. The parameter "d" if there is an LSP with x and y as endpoints. The parameter "d" is
is the set of demands and restrictions associated with F. Evidently, the set of demands and restrictions associated with F. Evidently, H
H is a directed graph. It can be seen that H depends on the is a directed graph. It can be seen that H depends on the
transitivity characteristics of G. transitivity characteristics of G.
3.2 The Fundamental Problem of Traffic Engineering Over MPLS 3.2 The Fundamental Problem of Traffic Engineering Over MPLS
There are basically three fundamental problems that relate to There are basically three fundamental problems that relate to Traffic
Traffic Engineering over MPLS. Engineering over MPLS.
- The first problem concerns how to map packets onto forwarding - The first problem concerns how to map packets onto forwarding
equivalence classes. equivalence classes.
- The second problem concerns how to map forwarding equivalence - The second problem concerns how to map forwarding equivalence
classes onto traffic trunks. classes onto traffic trunks.
- The third problem concerns how to map traffic trunks onto the - The third problem concerns how to map traffic trunks onto the
physical network topology through label switched paths. physical network topology through label switched paths.
Here, we do not concern ourselves with the first two aspects of This document is not focusing on the first two problems listed.
the problem (even-though they are quite important). Instead, the (even-though they are quite important). Instead, the remainder of
remainder of this manuscript will focus on capabilities that this manuscript will focus on the capabilities that permit the third
permit the third mapping function to be performed in a manner that mapping function to be performed in a manner resulting in efficient
results in efficient and reliable network operations. This is really and reliable network operations. This is really the problem of
the problem of mapping an induced MPLS graph (H) onto the "base" mapping an induced MPLS graph (H) onto the "base" network topology
network topology (G). (G).
4.0 Augmented Capabilities for Traffic Engineering Over MPLS 4.0 Augmented Capabilities for Traffic Engineering Over MPLS
The previous sections reviewed the basic functions of Traffic The previous sections reviewed the basic functions of Traffic
Engineering in the contemporary Internet. The applicability of Engineering in the contemporary Internet. The applicability of MPLS
MPLS to that activity was also discussed. The remaining sections of to that activity was also discussed. The remaining sections of this
this manuscript describe the functional capabilities required manuscript describe the functional capabilities required to fully
to fully support Traffic Engineering over MPLS in large networks. support Traffic Engineering over MPLS in large networks.
The proposed capabilities consist of: The proposed capabilities consist of:
1. A set of attributes associated with traffic trunks which 1. A set of attributes associated with traffic trunks which
collectively specify their behavioral characteristics. collectively specify their behavioral characteristics.
Some of these attributes have already been suggested in
[9] within the context of traffic management for MPLS.
2. A set of attributes associated with resources which constrain 2. A set of attributes associated with resources which constrain
the placement of traffic trunks through them. These can also be the placement of traffic trunks through them. These can also be
viewed as topology attribute constraints. viewed as topology attribute constraints.
3. A "constraint based routing" (QoS routing) framework which is 3. A "constraint-based routing" framework which is used to select
used to select paths for traffic trunks subject to constraints paths for traffic trunks subject to constraints imposed by items
imposed by items 1) and 2) above. The constraint based routing 1) and 2) above. The constraint-based routing framework does not
framework need not be part of MPLS. However, the two need to be have to be part of MPLS. However, the two need to be tightly
tightly integrated together. integrated together.
The attributes associated with traffic trunks and resources, as well The attributes associated with traffic trunks and resources, as well
as parameters associated with routing, collectively represent the as parameters associated with routing, collectively represent the
control variables which can be modified either through administrative control variables which can be modified either through administrative
action or automatically to drive the network to a desired state. action or through automated agents to drive the network to a desired
state.
In an operational network, it is highly desirable that these In an operational network, it is highly desirable that these
attributes can be dynamically modified online by an operator attributes can be dynamically modified online by an operator without
without adversely disrupting network operations. adversely disrupting network operations.
5.0 Traffic Trunk Attributes and Characteristics 5.0 Traffic Trunk Attributes and Characteristics
This section describes the desirable attributes which can be This section describes the desirable attributes which can be
associated with traffic trunks to influence their behavioral associated with traffic trunks to influence their behavioral
characteristics. characteristics.
First, the basic properties of traffic trunks as used in this First, the basic properties of traffic trunks (as used in this
manuscript are summarized below: manuscript) are summarized below:
- A traffic trunk is an *aggregate* of traffic flows belonging - A traffic trunk is an *aggregate* of traffic flows belonging
to the same class. to the same class. In some contexts, it may be desirable to
relax this definition and allow traffic trunks to include
multi-class traffic aggregates.
- In a single class service model, such as the current Internet, - In a single class service model, such as the current Internet,
a traffic trunk could encapsulate all the traffic between an a traffic trunk could encapsulate all of the traffic between an
ingress LSR and an egress LSR, or subsets thereof. ingress LSR and an egress LSR, or subsets thereof.
- Traffic trunks are routable objects (similar to ATM VCs) - Traffic trunks are routable objects (similar to ATM VCs).
- A traffic trunk is distinct from the LSP through which it - A traffic trunk is distinct from the LSP through which it
traverses. In operational contexts, a traffic trunk can be traverses. In operational contexts, a traffic trunk can be
moved from one path onto another. moved from one path onto another.
- A traffic trunk is unidirectional. - A traffic trunk is unidirectional.
In practice, a traffic trunk can be characterized by its ingress In practice, a traffic trunk can be characterized by its ingress and
and egress LSRs, the forwarding equivalence class which is egress LSRs, the forwarding equivalence class which is mapped onto
mapped onto it, and a set of attributes which determine its it, and a set of attributes which determine its behavioral
behavioral characteristics. characteristics.
Two basic issues are of particular significance: (1) parameterization Two basic issues are of particular significance: (1) parameterization
of traffic trunks and (2) path placement and maintenance rules for of traffic trunks and (2) path placement and maintenance rules for
traffic trunks. traffic trunks.
5.1 Bidirectional Traffic Trunks 5.1 Bidirectional Traffic Trunks
Although traffic trunks are conceptually unidirectional, in many Although traffic trunks are conceptually unidirectional, in many
practical contexts, it is useful to simultaneously instantiate practical contexts, it is useful to simultaneously instantiate two
two traffic trunks with the same endpoints, but which carry packets traffic trunks with the same endpoints, but which carry packets in
in opposite directions. The two traffic trunks are logically coupled opposite directions. The two traffic trunks are logically coupled
together. That is, one trunk, called the forward trunk, carries together. One trunk, called the forward trunk, carries traffic from
traffic from an originating node to a destination node, while the an originating node to a destination node. The other trunk, called
other trunk, called the backward trunk, carries traffic from the the backward trunk, carries traffic from the destination node to the
destination node to the originating node. We refer to the originating node. We refer to the amalgamation of two such traffic
amalgamation of two such traffic trunks as one bidirectional traffic trunks as one bidirectional traffic trunk (BTT) if the following two
trunk (BTT) if the following two conditions hold: conditions hold:
- Both traffic trunks are instantiated through an atomic action at - Both traffic trunks are instantiated through an atomic action at
one LSR, called the originator node. one LSR, called the originator node, or through an atomic action
at a network management station.
- Neither of the composite traffic trunks can exist without the - Neither of the composite traffic trunks can exist without the
other. That is, both are instantiated and destroyed together. other. That is, both are instantiated and destroyed together.
It is also useful to consider the topological properties of BTTs. A The topological properties of BTTs should also be considered. A BTT
BTT can be topologically symmetric or topologically asymmetric. can be topologically symmetric or topologically asymmetric. A BTT is
A BTT is said to be "topologically symmetric" if its constituent said to be "topologically symmetric" if its constituent traffic
traffic trunks are routed through the same physical path, even-though trunks are routed through the same physical path, even though they
they operate in opposite directions. Otherwise, if the component operate in opposite directions. If, however, the component traffic
traffic trunks are routed through different physical paths, then the trunks are routed through different physical paths, then the BTT is
BTT is said to be "topologically asymmetric." said to be "topologically asymmetric."
It should be noted that bidirectional traffic trunks are merely an It should be noted that bidirectional traffic trunks are merely an
administrative convenience. In practice, most of the traffic administrative convenience. In practice, most traffic engineering
engineering functions can be implemented using only unidirectional functions can be implemented using only unidirectional traffic
traffic trunks. trunks.
5.2 Basic Operations on Traffic Trunks 5.2 Basic Operations on Traffic Trunks
In the following, we summarize the basic operations on traffic The basic operations on traffic trunks significant to Traffic
trunks which are significant for Traffic Engineering purposes. Engineering purposes are summarized below.
- Establish: Create an instance of a traffic trunk. - Establish: To create an instance of a traffic trunk.
- Activate: Cause a traffic trunk to start passing traffic. The - Activate: To cause a traffic trunk to start passing traffic.
establishment and activation of a traffic trunk are logically The establishment and activation of a traffic trunk are
separate events. Although, in practice they can be implemented logically separate events. They may, however, be implemented
or invoked as one atomic action. or invoked as one atomic action.
- Deactivate: Cause a traffic trunk to stop passing traffic. - Deactivate: To cause a traffic trunk to stop passing traffic.
- Modify Attributes: Cause the attributes of a traffic trunk - Modify Attributes: To cause the attributes of a traffic trunk
to be modified. to be modified.
- Reroute: Cause a traffic trunk to change its route. This can be - Reroute: To cause a traffic trunk to change its route. This
done through administrative action or automatically by the can be done through administrative action or automatically
underlying protocols. by the underlying protocols.
- Destroy: Remove an instance of a traffic trunk from the network - Destroy: To remove an instance of a traffic trunk from the
and reclaim all resources allocated to it. Such resources network and reclaim all resources allocated to it. Such
include label space, and possibly available bandwidth. resources include label space and possibly available bandwidth.
The above are considered the basic operations on traffic trunks. The above are considered the basic operations on traffic trunks.
Additional operations are also possible such as policing, traffic Additional operations are also possible such as policing and traffic
shaping, and so forth. shaping.
5.3 Accounting and Performance Monitoring 5.3 Accounting and Performance Monitoring
Accounting capabilities are very important for purposes of billing Accounting and performance monitoring capabilities are very important
and traffic characterization. The billing aspect of accounting was to the billing and traffic characterization functions. Performance
discussed in [9]. From a Traffic Engineering perspective, statistics obtained from accounting and performance monitoring
performance statistics obtained from an accounting system can be systems can be used for traffic characterization, performance
used for traffic characterization, performance optimization, and optimization, and capacity planning within the Traffic Engineering
capacity planning. realm..
The capability to obtain statistics at the traffic trunk level is so The capability to obtain statistics at the traffic trunk level is so
important that it should be considered an essential requirement for important that it should be considered an essential requirement for
Traffic Engineering over MPLS. Traffic Engineering over MPLS.
5.4 Basic Traffic Engineering Attributes of Traffic Trunks 5.4 Basic Traffic Engineering Attributes of Traffic Trunks
An attribute of a traffic trunk is a parameter assigned to it An attribute of a traffic trunk is a parameter assigned to it which
which influences its behavioral characteristics. influences its behavioral characteristics.
Attributes can be explicitly assigned to traffic trunks through Attributes can be explicitly assigned to traffic trunks through
administration action or implicitly assigned by the underlying administration action or they can be implicitly assigned by the
protocols when packets are classified and mapped into equivalence underlying protocols when packets are classified and mapped into
classes at the ingress to an MPLS domain. Regardless of how the equivalence classes at the ingress to an MPLS domain. Regardless of
attributes were originally assigned, for Traffic Engineering how the attributes were originally assigned, for Traffic Engineering
purposes, it should be possible to administratively modify such purposes, it should be possible to administratively modify such
attributes. attributes.
The basic attributes of traffic trunks which are significant for The basic attributes of traffic trunks particularly significant for
Traffic Engineering are itemized below. Some, of these attributes Traffic Engineering are itemized below.
have already been included under the traffic management framework
document [9].
- Traffic parameter attributes - Traffic parameter attributes
- Generic Path selection and maintenance attributes - Generic Path selection and maintenance attributes
- Priority attribute - Priority attribute
- Preemption attribute - Preemption attribute
- Resilience attribute - Resilience attribute
- Policing attribute - Policing attribute
The combination of traffic parameters and policing attributes is The combination of traffic parameters and policing attributes is
analogous to usage parameter control in ATM networks. Also, most analogous to usage parameter control in ATM networks. Most of the
of the above attributes have analogs in well established attributes listed above have analogs in well established
technologies. Consequently, it should be relatively straight technologies. Consequently, it should be relatively straight forward
forward to map the traffic trunk attributes onto many existing to map the traffic trunk attributes onto many existing switching and
switching and routing architectures. routing architectures.
Priority and preemption can be regarded as relational attributes Priority and preemption can be regarded as relational attributes
because they express certain binary relations between traffic because they express certain binary relations between traffic trunks.
trunks. Conceptually, these binary relations determine the manner in Conceptually, these binary relations determine the manner in which
which traffic trunks interact with each other as they compete for traffic trunks interact with each other as they compete for network
network resources during path establishment and path maintenance. resources during path establishment and path maintenance.
5.5 Traffic parameter attributes 5.5 Traffic parameter attributes
Traffic parameters can be used to capture the characteristics of Traffic parameters can be used to capture the characteristics of the
the traffic streams (or more precisely the forwarding equivalence traffic streams (or more precisely the forwarding equivalence class)
class) which are to be transported through the traffic trunk. Such to be transported through the traffic trunk. Such characteristics may
characteristics might include peak rates, average rates, permissible include peak rates, average rates, permissible burst size, etc. From
burst size, etc. From a traffic engineering perspective, the a traffic engineering perspective, the traffic parameters are
traffic parameters are significant because they indicate the significant because they indicate the resource requirements of the
resource requirements of the traffic trunk. This is useful for traffic trunk. This is useful for resource allocation and congestion
resource allocation and congestion avoidance through anticipatory avoidance through anticipatory policies.
policies.
For purposes of bandwidth allocation, a single canonical value of For the purpose of bandwidth allocation, a single canonical value of
bandwidth requirements can be computed from a traffic trunk's bandwidth requirements can be computed from a traffic trunk's traffic
traffic parameters. Techniques for performing such computations parameters. Techniques for performing these computations are well
are already well known; for example the theory of effective known. One example of this is the theory of effective bandwidth.
bandwidth, and such like.
5.6 Generic Path Selection and Management Attributes 5.6 Generic Path Selection and Management Attributes
Generic path selection and management attributes define the rules Generic path selection and management attributes define the rules for
for selecting the route taken by a traffic trunk, and the rules for selecting the route taken by a traffic trunk as well as the rules for
maintenance of paths that are already established. maintenance of paths that are already established.
Paths can either be computed automatically by the underlying Paths can be computed automatically by the underlying routing
routing protocols or defined administratively by a network protocols or they can be defined administratively by a network
operator. If no resource requirements or restrictions are associated operator. If there are no resource requirements or restrictions
with a traffic trunk, then a topology driven protocol can be used to associated with a traffic trunk, then a topology driven protocol can
select its path. However, if there are resource requirements or be used to select its path. However, if resource requirements or
policy restrictions, then a constraint based routing scheme must be policy restrictions exist, then a constraint-based routing scheme
used for path selection. should be used for path selection.
In Section 7, we describe a constraint based routing framework which In Section 7, a constraint-based routing framework which can
can automatically compute paths subject to a set of constraints. automatically compute paths subject to a set of constraints is
Issues that pertain to explicit paths instantiated through described. Issues pertaining to explicit paths instantiated through
administrative action are discussed in Section 5.6.1 below. administrative action are discussed in Section 5.6.1 below.
Path management concerns all aspects that pertain to the maintenance Path management concerns all aspects pertaining to the maintenance of
of paths traversed by traffic trunks. In some operational contexts, paths traversed by traffic trunks. In some operational contexts, it
it is desirable that an MPLS implementation should be able to is desirable that an MPLS implementation can dynamically reconfigure
dynamically reconfigure itself, to adapt to some notion of change in itself, to adapt to some notion of change in "system state."
"system state." Adaptivity and resilience are aspects of dynamic Adaptivity and resilience are aspects of dynamic path management.
path management.
To guide the path selection and management process, a set of To guide the path selection and management process, a set of
attributes are required. In the remainder of this sub-section, attributes are required. The basic attributes and behavioral
we describe the basic attributes and behavioral characteristics characteristics associated with traffic trunk path selection and
associated with traffic trunk path selection and management. management are described in the remainder of this sub-section.
5.6.1 Administratively Specified Explicit Paths 5.6.1 Administratively Specified Explicit Paths
An administratively specified explicit path for a traffic trunk An administratively specified explicit path for a traffic trunk is
is one which is configured through operator action. An one which is configured through operator action. An administratively
administratively specified path can be completely specified or specified path can be completely specified or partially specified. A
partially specified. A path is completely specified if all path is completely specified if all of the required hops between the
required hops between the endpoints are indicated. A path is endpoints are indicated. A path is partially specified if only a
partially specified if only a subset of intermediate hops are subset of intermediate hops are indicated. In this case, the
indicated. In this case, the underlying protocols are required to underlying protocols are required to complete the path. Due to
complete the path. Due to operator errors, an administratively operator errors, an administratively specified path can be
specified path can be inconsistent or illogical. The underlying inconsistent or illogical. The underlying protocols should be able to
protocols should be able to detect such inconsistencies and provide detect such inconsistencies and provide appropriate feedback.
appropriate feedback.
A "path preference rule" attribute should be associated with A "path preference rule" attribute should be associated with
administratively specified explicit paths. A path preference rule administratively specified explicit paths. A path preference rule
attribute is a binary variable which indicates whether the attribute is a binary variable which indicates whether the
administratively configured explicit path is "mandatory" or administratively configured explicit path is "mandatory" or "non-
"non-mandatory." mandatory."
If an administratively specified explicit path is selected with a If an administratively specified explicit path is selected with a
"mandatory attribute, then that path (and only that path) must be "mandatory attribute, then that path (and only that path) must be
used. If a mandatory path is topological infeasible (e.g. the two used. If a mandatory path is topological infeasible (e.g. the two
endpoints are topologically partitioned), or the path cannot be endpoints are topologically partitioned), or if the path cannot be
instantiated because available resources are inadequate, then the instantiated because the available resources are inadequate, then the
path setup process fails. In other words, if a path is specified path setup process fails. In other words, if a path is specified as
as mandatory, then an alternate path cannot be used whatsoever; mandatory, then an alternate path cannot be used regardless of
regardless of prevailing circumstance. A mandatory path which is prevailing circumstance. A mandatory path which is successfully
successfully instantiated is also implicitly pinned. Once the path is instantiated is also implicitly pinned. Once the path is instantiated
instantiated it cannot be changed except through deletion and it cannot be changed except through deletion and instantiation of a
instantiation of a new path. new path.
On the other hand, if an administratively specified explicit path is However, if an administratively specified explicit path is selected
selected with a "non-mandatory" preference rule attribute value, with a "non-mandatory" preference rule attribute value, then the path
then the path should be used if feasible. Otherwise, an alternate should be used if feasible. Otherwise, an alternate path can be
path can be chosen instead by the underlying protocols. chosen instead by the underlying protocols.
5.6.2 Hierarchy of Preference Rules For Multi-Paths 5.6.2 Hierarchy of Preference Rules For Multi-Paths
In some practical contexts, it is useful to be able to In some practical contexts, it can be useful to have the ability to
administratively specify a set of candidate explicit paths for a administratively specify a set of candidate explicit paths for a
given traffic trunk and define a hierarchy of preference relations given traffic trunk and define a hierarchy of preference relations on
on the paths. During path establishment, the preference rules are the paths. During path establishment, the preference rules are
applied to select a suitable path from the candidate list. Also, applied to select a suitable path from the candidate list. Also,
under failure scenarios the preference rules are applied to select under failure scenarios the preference rules are applied to select an
an alternate path from the candidate list. alternate path from the candidate list.
5.6.3 Resource Class Affinity Attributes 5.6.3 Resource Class Affinity Attributes
Resource class affinity attributes associated with a traffic trunk Resource class affinity attributes associated with a traffic trunk
can be used to specify the class of resources (see Section 6) which 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 are to be explicitly included or excluded from the path of the
traffic trunk. These are policy attributes which can be used to traffic trunk. These are policy attributes which can be used to
impose additional constraints on the path traversed by a given impose additional constraints on the path traversed by a given
traffic trunk. Resource class affinity attributes for a traffic can traffic trunk. Resource class affinity attributes for a traffic can
be specified as a sequence of tuples: be specified as a sequence of tuples:
<resource-class, affinity>; <resource-class, affinity>; .. <resource-class, affinity>; <resource-class, affinity>; ..
The resource-class parameter identifies a resource class for which The resource-class parameter identifies a resource class for which an
an affinity relationship is defined with respect to the traffic affinity relationship is defined with respect to the traffic trunk.
trunk. The affinity parameter indicates the affinity relationship; The affinity parameter indicates the affinity relationship; that is,
that is, whether members of the resource class are to be included or whether members of the resource class are to be included or excluded
excluded from the path of the traffic trunk. Specifically, the from the path of the traffic trunk. Specifically, the affinity
affinity parameter is a binary variable which takes one parameter MAY be a binary variable which takes one of the following
of the following values: (1) explicit inclusion, and (2) explicit values: (1) explicit inclusion, and (2) explicit exclusion.
exclusion.
Since the affinity attribute is a binary variable, it is also If the affinity attribute is a binary variable, it may be possible to
possible to use Boolean expressions to specify the resource class use Boolean expressions to specify the resource class affinities
affinities associated with a given traffic trunk. associated with a given traffic trunk.
If no resource class affinity attributes are specified, then a "don't If no resource class affinity attributes are specified, then a "don't
care" affinity relationship is assumed to hold between the care" affinity relationship is assumed to hold between the traffic
traffic trunk and all resources. That is, there is no requirement to trunk and all resources. That is, there is no requirement to
explicitly include or exclude any resources from the traffic trunk's explicitly include or exclude any resources from the traffic trunk's
path. This should be the default in practice. path. This should be the default in practice.
Resource class affinity attributes are very useful and powerful Resource class affinity attributes are very useful and powerful
constructs because they can be used to implement a variety of constructs because they can be used to implement a variety of
policies. For example, they can be used to contain certain policies. For example, they can be used to contain certain traffic
traffic trunks within specific topological regions of the network. trunks within specific topological regions of the network.
A "constraint based routing" framework (see section 7.0) can be used A "constraint-based routing" framework (see section 7.0) can be used
to compute an explicit path for a traffic trunk subject to resource to compute an explicit path for a traffic trunk subject to resource
class affinity constraints in the following manner: class affinity constraints in the following manner:
1. For explicit inclusion, prune all resources which do not belong 1. For explicit inclusion, prune all resources not belonging
to the specified classes prior to performing path computation. to the specified classes prior to performing path computation.
2. For explicit exclusion, prune all resources which belong to the 2. For explicit exclusion, prune all resources belonging to the
specified classes before performing path placement computations. specified classes before performing path placement computations.
5.6.4 Adaptivity Attribute 5.6.4 Adaptivity Attribute
Network characteristics and state change over time. For example, new Network characteristics and state change over time. For example, new
resources become available, failed resources become reactivated, resources become available, failed resources become reactivated, and
allocated resources become deallocated; in general sometimes more allocated resources become deallocated. In general, sometimes more
efficient paths become available. Therefor, from a Traffic efficient paths become available. Therefore, from a Traffic
Engineering perspective, it is necessary to have administrative Engineering perspective, it is necessary to have administrative
control parameters that can be used to specify how traffic trunks control parameters that can be used to specify how traffic trunks
respond to this dynamism. In some scenarios, it might be desirable respond to this dynamism. In some scenarios, it might be desirable to
to dynamically change the paths of some traffic trunks in response dynamically change the paths of certain traffic trunks in response to
to changes in network state. This process is called re-optimization. changes in network state. This process is called re-optimization. In
In many other scenarios, re-optimization might be highly other scenarios, re-optimization might be very undesirable.
undesirable.
An Adaptivity attribute is a part of the path maintenance parameters An Adaptivity attribute is a part of the path maintenance parameters
associated with traffic trunks. The adaptivity attribute associated associated with traffic trunks. The adaptivity attribute associated
with a traffic trunk indicates whether the trunk is subject to with a traffic trunk indicates whether the trunk is subject to re-
re-optimization. That is, an adaptivity attribute is a binary optimization. That is, an adaptivity attribute is a binary variable
variable which takes one of the following values: (1) permit which takes one of the following values: (1) permit re-optimization
re-optimization and (2) disable re-optimization. and (2) disable re-optimization.
If re-optimization is enabled, then a traffic trunk can be rerouted If re-optimization is enabled, then a traffic trunk can be rerouted
through different paths by the underlying protocols in response to through different paths by the underlying protocols in response to
changes in network state (primarily changes in resource changes in network state (primarily changes in resource
availability). Conversely, if re-optimization is disabled, then the availability). Conversely, if re-optimization is disabled, then the
traffic trunk is "pinned" to its established path and cannot be traffic trunk is "pinned" to its established path and cannot be
rerouted in response to changes in network state. rerouted in response to changes in network state.
Stability is a major concern when re-optimization is permitted. To Stability is a major concern when re-optimization is permitted. To
promote stability, an MPLS implementation should not be too reactive promote stability, an MPLS implementation should not be too reactive
to the evolutionary dynamics of the network. At the same time, it 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 must adapt fast enough so that optimal use can be made of network
assets. This necessarily implies that the frequency of assets. This implies that the frequency of re-optimization should be
re-optimization should be administratively configurable to allow for administratively configurable to allow for tuning.
tuning.
It is to be noted that re-optimization is distinct from It is to be noted that re-optimization is distinct from resilience. A
resilience. A different attribute is used to specify the different attribute is used to specify the resilience characteristics
resilience characteristics of a traffic trunk (see section 5.9). of a traffic trunk (see section 5.9). In practice, it would seem
In practice, it would seem reasonable to expect traffic trunks which reasonable to expect traffic trunks subject to re-optimization to be
are subject to re-optimization to be implicitly resilient to failures implicitly resilient to failures along their paths. However, a
along their paths. However, a traffic trunk which is not subject to traffic trunk which is not subject to re-optimization and whose path
re-optimization and whose path is not administratively specified is not administratively specified with a "mandatory" attribute can
with a "mandatory" attribute can also be required to be resilient to also be required to be resilient to link and node failures along its
link and node failures along its established path established path
Formally, it can be stated that adaptivity to state evolution Formally, it can be stated that adaptivity to state evolution through
through re-optimization implies resilience to failures, whereas re-optimization implies resilience to failures, whereas resilience to
resilience to failures does not imply general adaptivity failures does not imply general adaptivity through re-optimization to
through re-optimization to state changes. state changes.
5.6.5 Load Distribution Across Parallel Traffic Trunks 5.6.5 Load Distribution Across Parallel Traffic Trunks
Load distribution across multiple parallel traffic trunks between Load distribution across multiple parallel traffic trunks between two
two nodes is an important consideration. In many practical nodes is an important consideration. In many practical contexts, the
contexts, the aggregate traffic between two nodes might be aggregate traffic between two nodes may be such that no single link
such that no single link (hence no single path) can carry the (hence no single path) can carry the load. However, the aggregate
load. However, the aggregate flow might be less than the maximum flow might be less than the maximum permissible flow across a "min-
permissible flow across a "min-cut" that partitions the two cut" that partitions the two nodes. In this case, the only feasible
nodes. In this case, the only feasible solution is to appropriately solution is to appropriately divide the aggregate traffic into sub-
divide the aggregate traffic into sub-streams and route the streams and route the sub-streams through multiple paths between the
sub-streams through multiple paths between the two nodes. two nodes.
In an MPLS domain, this problem can be addressed by instantiating In an MPLS domain, this problem can be addressed by instantiating
multiple traffic trunks between the two nodes, such that each traffic multiple traffic trunks between the two nodes, such that each traffic
trunk carries a proportion of the aggregate traffic. Therefor, a trunk carries a proportion of the aggregate traffic. Therefore, a
flexible means of load assignment to multiple parallel traffic flexible means of load assignment to multiple parallel traffic trunks
trunks carrying traffic of the same class between a pair of nodes is carrying traffic between a pair of nodes is required.
required.
Specifically, from an operational perspective, in situations where Specifically, from an operational perspective, in situations where
parallel traffic trunks are warranted, it would be useful parallel traffic trunks are warranted, it would be useful to have
to have some attribute that can be used to indicate the relative some attribute that can be used to indicate the relative proportion
proportion of traffic to be carried by each traffic trunk. The of traffic to be carried by each traffic trunk. The underlying
underlying protocols will then map the load onto the traffic protocols will then map the load onto the traffic trunks according to
trunks according to the specified proportions. It is also, generally the specified proportions. It is also, generally desirable to
desirable to maintain packet ordering between packets belong to the maintain packet ordering between packets belong to the same micro-
same micro-flow (same source address, destination address, and port flow (same source address, destination address, and port number).
number).
5.7 Priority attribute 5.7 Priority attribute
The priority attribute defines the relative importance of traffic The priority attribute defines the relative importance of traffic
trunks. If a constraint based routing framework is used with MPLS, trunks. If a constraint-based routing framework is used with MPLS,
then priorities become very important because they can be used to then priorities become very important because they can be used to
determine the order in which path selection is done for traffic determine the order in which path selection is done for traffic
trunks at connection establishment and under fault scenarios. trunks at connection establishment and under fault scenarios.
Priorities are also important in implementations that permit Priorities are also important in implementations permitting
preemption, because they can be used to impose a partial order preemption because they can be used to impose a partial order on the
on the set of traffic trunks according to which preemptive policies set of traffic trunks according to which preemptive policies can be
can be actualized. actualized.
5.8 Preemption attribute 5.8 Preemption attribute
The preemption attribute determines whether a traffic trunk can The preemption attribute determines whether a traffic trunk can
preempt another traffic trunk from a given path, and whether another preempt another traffic trunk from a given path, and whether another
traffic trunk can preempt a specific traffic trunk. Preemption is traffic trunk can preempt a specific traffic trunk. Preemption is
useful for both traffic oriented and resource oriented performance useful for both traffic oriented and resource oriented performance
objectives. Within a differentiated services environment, preemption objectives. Preemption can used to assure that high priority traffic
can used to assure that high priority traffic trunks can always be trunks can always be routed through relatively favorable paths within
routed through relatively favorable paths. a differentiated services environment.
Preemption can also be used to implement various prioritized Preemption can also be used to implement various prioritized
restoration policies following fault events. restoration policies following fault events.
The preemption attribute can be used to specify four preempt modes The preemption attribute can be used to specify four preempt modes
for a traffic trunk: (1) preemptor enabled, (2) non-preemptor, for a traffic trunk: (1) preemptor enabled, (2) non-preemptor, (3)
(3) preemptable, and (4) non-preemptable. A preemptor preemptable, and (4) non-preemptable. A preemptor enabled traffic
enabled traffic trunk can preempt lower priority traffic trunks trunk can preempt lower priority traffic trunks designated as
which are designated as preemptable. A traffic trunk which is preemptable. A traffic specified as non-preemptable cannot be
specified as non-preemptable cannot be preempted by any other preempted by any other trunks, regardless of relative priorities. A
trunks, regardless of relative priorities. A traffic trunk which is traffic trunk designated as preemptable can be preempted by higher
designated as preemptable can be preempted by higher priority trunks priority trunks which are preemptor enabled.
which are preemptor enabled.
It is trivial to see that some of the preempt modes are mutually It is trivial to see that some of the preempt modes are mutually
exclusive. Using the numbering scheme depicted above, the feasible exclusive. Using the numbering scheme depicted above, the feasible
preempt mode combinations for a given traffic trunk are as preempt mode combinations for a given traffic trunk are as follows:
follows: (1, 3), (1, 4), (2, 3), and (2, 4). The (2, 4) combination (1, 3), (1, 4), (2, 3), and (2, 4). The (2, 4) combination should be
should be the default. the default.
A traffic trunk, say "A", can preempt another traffic trunk, say A traffic trunk, say "A", can preempt another traffic trunk, say "B",
"B", only if *all* the following five conditions hold: (i) "A" has only if *all* of the following five conditions hold: (i) "A" has a
a relatively higher priority than "B", (ii) "A" contends for a relatively higher priority than "B", (ii) "A" contends for a resource
resource utilized by "B", (iii) the resource cannot concurrently utilized by "B", (iii) the resource cannot concurrently accommodate
accommodate "A" and "B" based on some decision criteria, (iv) "A" is "A" and "B" based on certain decision criteria, (iv) "A" is preemptor
preemptor enabled, and (v) "B" is preemptable. enabled, and (v) "B" is preemptable.
Although useful, preemption is not considered a mandatory attribute Preemption is not considered a mandatory attribute under the current
under the current best effort Internet service model. However, in best effort Internet service model although it is useful. However, in
a differentiated services scenario, the need for preemption becomes a differentiated services scenario, the need for preemption becomes
more compelling. Moreover, in the emerging optical internetworking more compelling. Moreover, in the emerging optical internetworking
architectures, where some protection and restoration functions architectures, where some protection and restoration functions may be
might be migrated from the optical layer to data network elements migrated from the optical layer to data network elements (such as
(such as gigabit and terabit label switching routers) to reduce gigabit and terabit label switching routers) to reduce costs,
costs, preemption can be used to reduce the restoration time for preemptive strategies can be used to reduce the restoration time for
high priority traffic trunks under fault conditions. high priority traffic trunks under fault conditions.
5.9 Resilience Attribute 5.9 Resilience Attribute
The resilience attribute determines the behavior of a traffic trunk The resilience attribute determines the behavior of a traffic trunk
under fault conditions. That is, when a fault occurs along the path under fault conditions. That is, when a fault occurs along the path
through which the traffic trunk traverses. The following are the through which the traffic trunk traverses. The following basic
basic problems that need to be addressed under such circumstances: problems need to be addressed under such circumstances: (1) fault
(1) fault detection, (2) failure notification, (3) recovery and detection, (2) failure notification, (3) recovery and service
service restoration. Obviously, an MPLS implementation will have restoration. Obviously, an MPLS implementation will have to
to incorporate mechanisms to address these issues. incorporate mechanisms to address these issues.
Many recovery policies can be specified for traffic trunks Many recovery policies can be specified for traffic trunks whose
whose established paths are impacted by faults. The following are a established paths are impacted by faults. The following are examples
few examples of feasible schemes: of feasible schemes:
1. Do not reroute the traffic trunk. For example, a survivability 1. Do not reroute the traffic trunk. For example, a survivability
scheme might already be in place, provisioned through an scheme may already be in place, provisioned through an
alternate mechanism, which guarantees service continuity alternate mechanism, which guarantees service continuity
under failure scenarios without the need to reroute traffic under failure scenarios without the need to reroute traffic
trunks. An example of such an alternate scheme (certainly there trunks. An example of such an alternate scheme (certainly
are many others), is a situation whereby multiple parallel many others exist), is a situation whereby multiple parallel
label switched paths are provisioned between two nodes, and label switched paths are provisioned between two nodes, and
function in a manner such that failure of one LSP causes the function in a manner such that failure of one LSP causes the
traffic trunk placed on it to be dispersed between the traffic trunk placed on it to be mapped onto the remaining LSPs
remaining LSPs. according to some well defined policy.
2. Reroute through a feasible path with enough resources. If none 2. Reroute through a feasible path with enough resources. If none
exists, then do not reroute. exists, then do not reroute.
3. Reroute through any available path regardless of resource 3. Reroute through any available path regardless of resource
constraints. constraints.
4. Many other schemes are possible; some of which might be 4. Many other schemes are possible including some which might be
combinations of the above. combinations of the above.
A "basic" resilience attribute indicates the recovery procedure A "basic" resilience attribute indicates the recovery procedure to be
to be applied to traffic trunks whose paths are impacted by faults. applied to traffic trunks whose paths are impacted by faults.
Specifically, a "basic" resilience attribute is a binary variable Specifically, a "basic" resilience attribute is a binary variable
which determines whether the target traffic trunk is to be rerouted which determines whether the target traffic trunk is to be rerouted
when segments of its path fail. "Extended" resilience attributes can when segments of its path fail. "Extended" resilience attributes can
be used to specify detailed actions be taken under fault scenarios. be used to specify detailed actions to be taken under fault
For example, an extended resilience attribute might specify a set of scenarios. For example, an extended resilience attribute might
alternate paths to use under fault conditions, and the rules that specify a set of alternate paths to use under fault conditions, as
govern the relative preference of each specified path. well as the rules that govern the relative preference of each
specified path.
Resilience attributes mandate close interaction between MPLS Resilience attributes mandate close interaction between MPLS and
and routing. routing.
5.10 Policing attribute 5.10 Policing attribute
The policing attribute determine the actions that should be taken The policing attribute determines the actions that should be taken by
by the underlying protocols when a traffic trunk becomes the underlying protocols when a traffic trunk becomes non-compliant.
non-compliant. That is, when a traffic trunk exceeds its contract That is, when a traffic trunk exceeds its contract as specified in
as specified in the traffic parameters. In general, policing the traffic parameters. Generally, policing attributes can indicate
attributes can indicate whether a non-conformant traffic trunk is to whether a non-conformant traffic trunk is to be rate limited, tagged,
be rate limited, tagged, or simply forwarded without any policing or simply forwarded without any policing action. If policing is
action. This aspect is discussed in the MPLS traffic management used, then adaptations of established algorithms such as the ATM
draft [9]. If policing is used, then adaptations of established Forum's GCRA [11] can be used to perform this function.
algorithms such as the ATM Forum's GCRA [11] can be used to perform
this function.
Policing is necessary in many operational scenarios, but is quite Policing is necessary in many operational scenarios, but is quite
undesirable in many others. In general, it is usually desirable to undesirable in some others. In general, it is usually desirable to
police at the ingress to a network (to enforce compliance with police at the ingress to a network (to enforce compliance with
service level agreements) and to minimize policing within the core, service level agreements) and to minimize policing within the core,
except when capacity constraints dictate otherwise. except when capacity constraints dictate otherwise.
Therefor, from a Traffic Engineering perspective, it is necessary to Therefore, from a Traffic Engineering perspective, it is necessary to
be able to administratively enable or disable traffic policing for be able to administratively enable or disable traffic policing for
each traffic trunk. each traffic trunk.
6.0 Resource Attributes 6.0 Resource Attributes
Resource attributes are part of the topology state parameters, which Resource attributes are part of the topology state parameters, which
are used to constrain the routing of traffic trunks through specific are used to constrain the routing of traffic trunks through specific
resources. resources.
6.1 Maximum Allocation Multiplier 6.1 Maximum Allocation Multiplier
The maximum allocation multiplier (MAM) of a resource is an The maximum allocation multiplier (MAM) of a resource is an
administratively configurable attribute which determines the administratively configurable attribute which determines the
proportion of the resource that is available for allocation to proportion of the resource that is available for allocation to
traffic trunks. This attribute is mostly applicable to link traffic trunks. This attribute is mostly applicable to link
bandwidth. However, in general, it can also be applied to buffer bandwidth. However, it can also be applied to buffer resources on
resources on LSRs. The concept of MAM is analogous to the concepts LSRs. The concept of MAM is analogous to the concepts of subscription
of subscription and booking factors in frame relay and ATM networks. and booking factors in frame relay and ATM networks.
It is possible to choose values of the MAM such that a resource can The values of the MAM can be chosen so that a resource can be under-
be under-allocated or over-allocated. A resource is said to be allocated or over-allocated. A resource is said to be under-
under-allocated if the aggregate demands of all traffic trunks (as allocated if the aggregate demands of all traffic trunks (as
expressed in the trunk traffic parameters) that can be allocated to expressed in the trunk traffic parameters) that can be allocated to
it is always less than the capacity of the resource. A resource is it are always less than the capacity of the resource. A resource is
said to be over-allocated if the aggregate demands of traffic trunks said to be over-allocated if the aggregate demands of all traffic
allocated to it can exceed the capacity of the resource. trunks allocated to it can exceed the capacity of the resource.
Under-allocation can be used to bound the utilization of resources. Under-allocation can be used to bound the utilization of resources.
However,the situation under MPLS is more complex than in circuit However,the situation under MPLS is more complex than in circuit
switched schemes because under MPLS, some flows can be routed via switched schemes because under MPLS, some flows can be routed via
conventional hop by hop protocols (also via explicit paths) conventional hop by hop protocols (also via explicit paths) without
without consideration for resource constraints. consideration for resource constraints.
Over-allocation can be used to take advantage of the statistical Over-allocation can be used to take advantage of the statistical
characteristics of traffic in order to implement more efficient characteristics of traffic in order to implement more efficient
resource allocation policies. In particular, over-allocation resource allocation policies. In particular, over-allocation can be
can be used in situations where the peak demands of traffic trunks used in situations where the peak demands of traffic trunks do not
do not coincide in time. coincide in time.
6.2 Resource Class Attribute 6.2 Resource Class Attribute
Resource class attributes are administratively assigned parameters Resource class attributes are administratively assigned parameters
which express some notion of "class" for resources. Resource class which express some notion of "class" for resources. Resource class
attributes can be viewed as "colors" which are assigned to attributes can be viewed as "colors" assigned to resources such that
resources, such that the set of resources with the same "color" the set of resources with the same "color" conceptually belong to the
conceptually belong to the same class. Resource class same class. Resource class attributes can be used to implement a
attributes can be used to implement a variety of policies. The key variety of policies. The key resources of interest here are links.
resources of interest here are links. When applied to links, the When applied to links, the resource class attribute effectively
resource class attribute effectively becomes become an aspect of becomes an aspect of the "link state" parameters.
the "link state" parameters.
From a Traffic Engineering perspective, the concept of resource The concept of resource class attributes is a powerful abstraction.
class attributes is a powerful abstraction, which can be used to From a Traffic Engineering perspective, it can be used to implement
implement a lot of policies with regard to both traffic and many policies with regard to both traffic and resource oriented
resource oriented performance optimization. Specifically, resource performance optimization. Specifically, resource class attributes can
class attributes can be used to: be used to:
1. Apply uniform policies to a set of resources which need 1. Apply uniform policies to a set of resources that do not need
not be in the same topological region. to be in the same topological region.
2. Specify the relative preference of sets of resources for 2. Specify the relative preference of sets of resources for
path placement of traffic trunks. path placement of traffic trunks.
3. Explicitly restrict the placement of traffic trunks 3. Explicitly restrict the placement of traffic trunks
to specific subsets of resources. to specific subsets of resources.
4. Implement generalized inclusion / exclusion policies. 4. Implement generalized inclusion / exclusion policies.
5. Enforce traffic locality containment policies. That is policies 5. Enforce traffic locality containment policies. That is,
that seek to contain local traffic within specific topological policies that seek to contain local traffic within
regions of the network. specific topological regions of the network.
Additionally, resource class attributes can be used for
identification purposes.
In general, a resource can be assigned more than one resource class In general, a resource can be assigned more than one resource class
attribute. For example, all the OC-48 links in a given network attribute. For example, all of the OC-48 links in a given network may
might be assigned a distinguished resource class attribute, and be assigned a distinguished resource class attribute. The subsets of
subsets of OC-48 links might be assigned additional resource class OC-48 links which exist with a given abstraction domain of the
attributes in order to implement specific containment policies, or network may be assigned additional resource class attributes in order
to architect the network in a certain manner. to implement specific containment policies, or to architect the
network in a certain manner.
7.0 Constraint Based Routing 7.0 Constraint-Based Routing
This section discusses the issues that pertain to constraint based This section discusses the issues pertaining to constraint-based
routing in MPLS domains. In contemporary terminology, constraint routing in MPLS domains. In contemporary terminology, constraint-
based routing is often referred to as "QoS Routing" see [5,6,7,10]. based routing is often referred to as "QoS Routing" see [5,6,7,10].
However, we prefer the term "constraint based routing," as it more This document uses the term "constraint-based routing" however,
aptly captures the envisaged functionality; which in general because it better captures the functionality envisioned, which
encompasses QoS routing as a subset. generally encompasses QoS routing as a subset.
Constraint based routing enables a demand driven, resource constraint-based routing enables a demand driven, resource
reservation aware, routing paradigm to co-exist with current reservation aware, routing paradigm to co-exist with current topology
topology driven hop by hop Internet interior gateway protocols. driven hop by hop Internet interior gateway protocols.
A constraint based routing framework uses the following as input: A constraint-based routing framework uses the following as input:
- The attributes associated with traffic trunks. - The attributes associated with traffic trunks.
- The attributes associated with resources. - The attributes associated with resources.
- Other topology state information. - Other topology state information.
Based on this information, a constraint based routing process Based on this information, a constraint-based routing process on each
on each node automatically computes explicit routes for each node automatically computes explicit routes for each traffic trunk
traffic trunk that originates from the node. In this case, an originating from the node. In this case, an explicit route for each
explicit route for each traffic trunk is a specification of a label traffic trunk is a specification of a label switched path that
switched path that satisfies the demand requirements expressed in satisfies the demand requirements expressed in the trunk's
the trunk's attributes, subject to constraints imposed by resource attributes, subject to constraints imposed by resource availability,
availability and other topology state information. administrative policy, and other topology state information.
A constraint based routing framework can greatly reduce the level A constraint-based routing framework can greatly reduce the level of
of manual configuration required to actualize Traffic Engineering manual configuration and intervention required to actualize Traffic
policies. Engineering policies.
In practice, the Traffic Engineer or an operator will In practice, the Traffic Engineer, an operator, or even an automaton
administratively specify the endpoints of a traffic trunk and assign will specify the endpoints of a traffic trunk and assign a set of
a set of attributes to the trunk which encapsulate the performance attributes to the trunk which encapsulate the performance
expectations and behavioral characteristics of the trunk. The expectations and behavioral characteristics of the trunk. The
constraint based routing framework is then expected to find a constraint-based routing framework is then expected to find a
feasible path that satisfies the expectations. If necessary, the feasible path to satisfy the expectations. If necessary, the Traffic
traffic engineer can then use manually configured explicit routes to Engineer or a traffic engineering support system can then use
perform fine grained optimization. administratively configured explicit routes to perform fine grained
optimization.
7.1 Basic Features of Constraint Based Routing 7.1 Basic Features of Constraint-Based Routing
A constraint based routing framework should be able to at least A constraint-based routing framework should at least have the
automatically obtain a basic feasible solution to the traffic trunk capability to automatically obtain a basic feasible solution to the
path placement problem. traffic trunk path placement problem.
In general, the constraint based routing problem is known to be In general, the constraint-based routing problem is known to be
intractable. However, in practice, a very simple well known intractable for most realistic constraints. However, in practice, a
heuristic (see e.g. [10]) can be used to find a feasible path if very simple well known heuristic (see e.g. [9]) can be used to find a
one exists: feasible path if one exists:
- First prune resources that do not satisfy the requirements of - First prune resources that do not satisfy the requirements of
the traffic trunk attributes. the traffic trunk attributes.
- Next, run a shortest path algorithm on the residual graph. - Next, run a shortest path algorithm on the residual graph.
It is easy to see that if a feasible path exists, then the above Clearly, if a feasible path exists for a single traffic trunk, then
simple procedure will find it. Additional rules can be specified the above simple procedure will find it. Additional rules can be
to break ties, and perform further optimizations. specified to break ties and perform further optimizations. In
general, ties should be broken so that congestion is minimized. When
multiple traffic trunks are to be routed, however, it can be shown
that the above algorithm may not always find a mapping, even when a
feasible mapping exists.
7.2 Implementation Considerations 7.2 Implementation Considerations
Many commercial implementations of frame relay and ATM switches Many commercial implementations of frame relay and ATM switches
already support some notion of constraint based routing. For such already support some notion of constraint-based routing. For such
devices, or novel MPLS centric contraptions devised therefrom, it devices or for the novel MPLS centric contraptions devised therefrom,
should be relatively easy to extend the current constraint based it should be relatively easy to extend the current constraint-based
routing implementations to accommodate the peculiar requirements of routing implementations to accommodate the peculiar requirements of
MPLS. MPLS.
For routers that use topology driven hop by hop IGPs, constraint For routers that use topology driven hop by hop IGPs, constraint-
based routing can be incorporated in at least one of two ways: based routing can be incorporated in at least one of two ways:
1. Extend current IGP protocols such as OSPF and IS-IS to support 1. By extending the current IGP protocols such as OSPF and IS-IS to
constraint based routing. Effort is already underway to provide support constraint-based routing. Effort is already underway to
such extensions to OSPF (see [5,7]). provide such extensions to OSPF (see [5,7]).
2. Add a constraint based routing process to each router which 2. By adding a constraint-based routing process to each router which
can co-exist with current IGPs. This scenario is depicted can co-exist with current IGPs. This scenario is depicted
in Figure 1. in Figure 1.
------------------------------------------ ------------------------------------------
| Management Interface | | Management Interface |
------------------------------------------ ------------------------------------------
| | | | | |
------------ ------------------ -------------- ------------ ------------------ --------------
| MPLS |<->| Constraint Based | | Conventional | | MPLS |<->| Constraint-Based | | Conventional |
| | | Routing Process | | IGP Process | | | | Routing Process | | IGP Process |
------------ ------------------ -------------- ------------ ------------------ --------------
| | | |
----------------------- -------------- ----------------------- --------------
| Resource Attribute | | Link State | | Resource Attribute | | Link State |
| Availability Database | | Database | | Availability Database | | Database |
----------------------- -------------- ----------------------- --------------
Figure 1. Constraint Based Routing Process on Layer 3 LSR Figure 1. Constraint-Based Routing Process on Layer 3 LSR
There are many important details associated with implementing There are many important details associated with implementing
constraint based routing on Layer 3 devices which we do not discuss constraint-based routing on Layer 3 devices which we do not discuss
here. These include the following: here. These include the following:
- Mechanisms for exchange of topology state information (resource - Mechanisms for exchange of topology state information
availability information, link state information, resource (resource availability information, link state information,
attribute information) between constraint based routing resource attribute information) between constraint-based
processes. routing processes.
- Mechanisms for maintenance of topology state information. - Mechanisms for maintenance of topology state information.
- Interaction between constraint based routing processes and - Interaction between constraint-based routing processes and
conventional IGP processes. conventional IGP processes.
- Mechanisms to accommodate the adaptivity requirements of traffic - Mechanisms to accommodate the adaptivity requirements of
trunks. traffic trunks.
- Mechanisms to accommodate the resilience and survivability - Mechanisms to accommodate the resilience and survivability
requirements of traffic trunks. requirements of traffic trunks.
In summary, constraint based routing assists in performance In summary, constraint-based routing assists in performance
optimization of operational networks by automatically finding optimization of operational networks by automatically finding
feasible paths that satisfy a set of constraints for traffic trunks. feasible paths that satisfy a set of constraints for traffic trunks.
It can drastically reduce the amount of manual explicit path It can drastically reduce the amount of administrative explicit path
configurations required to achieve Traffic Engineering objectives. configuration and manual intervention required to achieve Traffic
Engineering objectives.
8.0 Conclusion 8.0 Conclusion
This manuscript presented a set of requirements for Traffic This manuscript presented a set of requirements for Traffic
Engineering over MPLS. A number of capabilities were described Engineering over MPLS. Many capabilities were described aimed at
aimed at enhancing the applicability of MPLS to Traffic Engineering enhancing the applicability of MPLS to Traffic Engineering in the
in the Internet. Internet.
It should be noted that some of the issues described here can be It should be noted that some of the issues described here can be
addressed by incorporating a minimal set of building blocks into MPLS, addressed by incorporating a minimal set of building blocks into
and then using a network management superstructure to extend the MPLS, and then using a network management superstructure to extend
functionality in order to realize the requirements. Also, the the functionality in order to realize the requirements. Also, the
constraint based routing framework need not be part of the core MPLS constraint-based routing framework does not have to be part of the
specifications. However, MPLS does require some interaction with a core MPLS specifications. However, MPLS does require some interaction
constraint based routing framework in order to meet the requirements. with a constraint-based routing framework in order to meet the
requirements.
9.0 References 9.0 Security Considerations
This document does not introduce new security issues beyond those
inherent in MPLS and may use the same mechanisms proposed for this
technology. It is, however, specifically important that manipulation
of administratively configurable parameters be executed in a secure
manner by authorized entities.
10.0 References
[1] E. Rosen, A. Viswanathan, R. Callon, "A Proposed Architecture [1] E. Rosen, A. Viswanathan, R. Callon, "A Proposed Architecture
for MPLS", Work in Progress. for MPLS", Work in Progress.
[2] R. Callon, P. Doolan, N. Feldman, A. Fredette, G. Swallow, [2] R. Callon, P. Doolan, N. Feldman, A. Fredette, G. Swallow,
A. Viswanathan, "A Framework for Multiprotocol Label A. Viswanathan, "A Framework for Multiprotocol Label
Switching", Work in Progress. Switching", Work in Progress.
[3] T. Li and Y. Rekhter, "Provider Architecture for Differentiated [3] T. Li and Y. Rekhter, "Provider Architecture for Differentiated
Services and Traffic Engineering (PASTE)," RFC 2430, Services and Traffic Engineering (PASTE)," RFC 2430,
skipping to change at page 26, line 35 skipping to change at page 27, line 43
[6] E. Crawley, R. Nair, B. Rajagopalan, H. Sandick, "A framework [6] E. Crawley, R. Nair, B. Rajagopalan, H. Sandick, "A framework
for QoS Based Routing in the Internet," RFC 2386, August 1998 for QoS Based Routing in the Internet," RFC 2386, August 1998
[7] R. Guerin, S. Kamat, A. Orda, T. Przygienda, D. Williams, [7] R. Guerin, S. Kamat, A. Orda, T. Przygienda, D. Williams,
"QoS Routing Mechanisms and OSPF Extensions," Work in Progress. "QoS Routing Mechanisms and OSPF Extensions," Work in Progress.
[8] C. Yang and A. Reddy, "A Taxonomy for Congestion Control [8] C. Yang and A. Reddy, "A Taxonomy for Congestion Control
Algorithms in Packet Switching Networks," IEEE Network Algorithms in Packet Switching Networks," IEEE Network
Magazine, Volume 9, Number 5, July/August 1995, Magazine, Volume 9, Number 5, July/August 1995,
[9] P. Vaananen and R. Ravikanth, "A Framework for Traffic [9] W. Lee, M. Hluchyi, and P. Humblet, "Routing Subject to
Management in MPLS Networks," Work in Progress.
[10] W. Lee, M. Hluchyi, and P. Humblet, "Routing Subject to
Quality of Service Constraints in Integrated Communication Quality of Service Constraints in Integrated Communication
Networks," IEEE Network, July 1995, pp 46-55. Networks," IEEE Network, July 1995, pp 46-55.
[11] ATM Forum, "Traffic Management Specification: Version 4.0" [10] ATM Forum, "Traffic Management Specification: Version 4.0"
April 1996. April 1996.
10.0 Acknowledgments [11] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
11.0 Acknowledgments
The authors would like to thank Yakov Rekhter for his review of an The authors would like to thank Yakov Rekhter for his review of an
earlier draft of this document. The authors would also like to thank earlier draft of this document. The authors would also like to thank
Louis Mamakos and Bill Barns for their helpful suggestions, and Louis Mamakos and Bill Barns for their helpful suggestions, and
Curtis Villamizar for providing some useful feedback. Curtis Villamizar for providing some useful feedback.
11.0 AUTHORS' ADDRESSES 12.0 AUTHORS' ADDRESSES
Daniel O. Awduche Joe Malcolm Johnson Agogbua Daniel O. Awduche
UUNET Worldcom UUNET Worldcom UUNET Worldcom UUNET (MCI Worldcom)
3060 Williams Drive 3060 Williams Drive 3060 Williams Drive 3060 Williams Drive
Fairfax, VA 22031 Fairfax, VA 22031 Fairfax, VA 22031 Fairfax, VA 22031
awduche@uu.net jmalcolm@uu.net ja@uu.net Email: awduche@uu.net
703-208-5277 703-206-5895 703-206-5794 Voice: +1 703-208-5277
Mike O'Dell Jim McManus Joe Malcolm
UUNET Worldcom UUNET Worldcom UUNET (MCI Worldcom)
3060 Williams Drive 3060 Williams Drive 3060 Williams Drive
Fairfax, VA 22031 Fairfax, VA 22031 Fairfax, VA 22031
mo@uu.net jmcmanus@uu.net Email: jmalcolm@uu.net
703-206-5890 703-206-5607 Voice: +1 703-206-5895
Johnson Agogbua
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Email: ja@uu.net
Voice: +1 703-206-5794
Mike O'Dell
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Email: mo@uu.net
Voice: +1 703-206-5890
Jim McManus
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
jmcmanus@uu.net
Voice: +1 703-206-5607
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/