However,the situation under MPLS is more complex than in circuit
switched schemes because under MPLS, some flows can be routed via
conventional hop by hop protocols (also via explicit paths) without
consideration for resource constraints.
Over-allocation can be used to take advantage of the statistical
characteristics of traffic in order to implement more efficient
resource allocation policies. In particular, over-allocation can be
used in situations where the peak demands of traffic trunks do not
coincide in time.
6.2 Resource Class Attribute
Resource class attributes are administratively assigned parameters
which express some notion of "class" for resources. Resource class
attributes can be viewed as "colors" assigned to resources such that
the set of resources with the same "color" conceptually belong to the
same class. Resource class attributes can be used to implement a
variety of policies. The key resources of interest here are links.
When applied to links, the resource class attribute effectively
becomes an aspect of the "link state" parameters.
The concept of resource class attributes is a powerful abstraction.
From a Traffic Engineering perspective, it can be used to implement
many policies with regard to both traffic and resource oriented
performance optimization. Specifically, resource class attributes can
be used to:
1. Apply uniform policies to a set of resources that do not need
to be in the same topological region.
2. Specify the relative preference of sets of resources for
path placement of traffic trunks.
3. Explicitly restrict the placement of traffic trunks
to specific subsets of resources.
4. Implement generalized inclusion / exclusion policies.
5. Enforce traffic locality containment policies. That is,
policies that seek to contain local traffic within
specific topological regions of the network.
Additionally, resource class attributes can be used for
identification purposes.
In general, a resource can be assigned more than one resource class
attribute. For example, all of the OC-48 links in a given network may
be assigned a distinguished resource class attribute. The subsets of
OC-48 links which exist with a given abstraction domain of the
network may be assigned additional resource class attributes in order
to implement specific containment policies, or to architect the
network in a certain manner.
7.0 Constraint-Based Routing
This section discusses the issues pertaining to constraint-based
routing in MPLS domains. In contemporary terminology, constraint-
based routing is often referred to as "QoS Routing" see [5,6,7,10].
This document uses the term "constraint-based routing" however,
because it better captures the functionality envisioned, which
generally encompasses QoS routing as a subset.
constraint-based routing enables a demand driven, resource
reservation aware, routing paradigm to co-exist with current topology
driven hop by hop Internet interior gateway protocols.
A constraint-based routing framework uses the following as input:
- The attributes associated with traffic trunks.
- The attributes associated with resources.
- Other topology state information.
Based on this information, a constraint-based routing process on each
node automatically computes explicit routes for each traffic trunk
originating from the node. In this case, an explicit route for each
traffic trunk is a specification of a label switched path that
satisfies the demand requirements expressed in the trunk's
attributes, subject to constraints imposed by resource availability,
administrative policy, and other topology state information.
A constraint-based routing framework can greatly reduce the level of
manual configuration and intervention required to actualize Traffic
Engineering policies.
In practice, the Traffic Engineer, an operator, or even an automaton
will specify the endpoints of a traffic trunk and assign a set of
attributes to the trunk which encapsulate the performance
expectations and behavioral characteristics of the trunk. The
constraint-based routing framework is then expected to find a
feasible path to satisfy the expectations. If necessary, the Traffic
Engineer or a traffic engineering support system can then use
administratively configured explicit routes to perform fine grained
optimization.
7.1 Basic Features of Constraint-Based Routing
A constraint-based routing framework should at least have the
capability to automatically obtain a basic feasible solution to the
traffic trunk path placement problem.
In general, the constraint-based routing problem is known to be
intractable for most realistic constraints. However, in practice, a
very simple well known heuristic (see e.g. [9]) can be used to find a
feasible path if one exists:
- First prune resources that do not satisfy the requirements of
the traffic trunk attributes.
- Next, run a shortest path algorithm on the residual graph.
Clearly, if a feasible path exists for a single traffic trunk, then
the above simple procedure will find it. Additional rules can be
specified to break ties and perform further optimizations. In
general, ties should be broken so that congestion is minimized. When
multiple traffic trunks are to be routed, however, it can be shown
that the above algorithm may not always find a mapping, even when a
feasible mapping exists.
7.2 Implementation Considerations
Many commercial implementations of frame relay and ATM switches
already support some notion of constraint-based routing. For such
devices or for the novel MPLS centric contraptions devised therefrom,
it should be relatively easy to extend the current constraint-based
routing implementations to accommodate the peculiar requirements of
MPLS.
For routers that use topology driven hop by hop IGPs, constraint-
based routing can be incorporated in at least one of two ways:
1. By extending the current IGP protocols such as OSPF and IS-IS to
support constraint-based routing. Effort is already underway to
provide such extensions to OSPF (see [5,7]).
2. By adding a constraint-based routing process to each router which
can co-exist with current IGPs. This scenario is depicted
in Figure 1.
------------------------------------------
| Management Interface |
------------------------------------------
| | |
------------ ------------------ --------------
| MPLS |<->| Constraint-Based | | Conventional |
| | | Routing Process | | IGP Process |
------------ ------------------ --------------
| |
----------------------- --------------
| Resource Attribute | | Link State |
| Availability Database | | Database |
----------------------- --------------
Figure 1. Constraint-Based Routing Process on Layer 3 LSR
There are many important details associated with implementing
constraint-based routing on Layer 3 devices which we do not discuss
here. These include the following:
- Mechanisms for exchange of topology state information
(resource availability information, link state information,
resource attribute information) between constraint-based
routing processes.
- Mechanisms for maintenance of topology state information.
- Interaction between constraint-based routing processes and
conventional IGP processes.
- Mechanisms to accommodate the adaptivity requirements of
traffic trunks.
- Mechanisms to accommodate the resilience and survivability
requirements of traffic trunks.
In summary, constraint-based routing assists in performance
optimization of operational networks by automatically finding
feasible paths that satisfy a set of constraints for traffic trunks.
It can drastically reduce the amount of administrative explicit path
configuration and manual intervention required to achieve Traffic
Engineering objectives.
8.0 Conclusion
This manuscript presented a set of requirements for Traffic
Engineering over MPLS. Many capabilities were described aimed at
enhancing the applicability of MPLS to Traffic Engineering in the
Internet.
It should be noted that some of the issues described here can be
addressed by incorporating a minimal set of building blocks into
MPLS, and then using a network management superstructure to extend
the functionality in order to realize the requirements. Also, the
constraint-based routing framework does not have to be part of the
core MPLS specifications. However, MPLS does require some interaction
with a constraint-based routing framework in order to meet the
requirements.
9.0 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] Rosen, E., Viswanathan, A. and R. Callon, "A Proposed
Architecture for MPLS", Work in Progress.
[2] Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G.
and A. Viswanathan, "A Framework for Multiprotocol Label
Switching", Work in Progress.
[3] Li, T. and Y. Rekhter, "Provider Architecture for Differentiated
Services and Traffic Engineering (PASTE)", RFC2430, October
1998.
[4] Rekhter, Y., Davie, B., Katz, D., Rosen, E. and G. Swallow,
"Cisco Systems' Tag Switching Architecture - Overview", RFC
2105, February 1997.
[5] Zhang, Z., Sanchez, C., Salkewicz, B. and E. Crawley "Quality of
Service Extensions to OSPF", Work in Progress.
[6] Crawley, E., Nair, F., Rajagopalan, B. and H. Sandick, "A
Framework for QoS Based Routing in the Internet", RFC2386,
August 1998.
[7] Guerin, R., Kamat, S., Orda, A., Przygienda, T. and D. Williams,
"QoS Routing Mechanisms and OSPF Extensions", RFC2676, August
1999.
[8] C. Yang and A. Reddy, "A Taxonomy for Congestion Control
Algorithms in Packet Switching Networks," IEEE Network Magazine,
Volume 9, Number 5, July/August 1995.
[9] W. Lee, M. Hluchyi, and P. Humblet, "Routing Subject to Quality
of Service Constraints in Integrated Communication Networks,"
IEEE Network, July 1995, pp 46-55.
[10] ATM Forum, "Traffic Management Specification: Version 4.0" April
1996.
11.0 Acknowledgments
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
Louis Mamakos and Bill Barns for their helpful suggestions, and
Curtis Villamizar for providing some useful feedback.
12.0 Authors' Addresses
Daniel O. Awduche
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Phone: +1 703-208-5277
EMail: awduche@uu.net
Joe Malcolm
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Phone: +1 703-206-5895
EMail: jmalcolm@uu.net
Johnson Agogbua
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Phone: +1 703-206-5794
EMail: ja@uu.net
Mike O'Dell
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Phone: +1 703-206-5890
EMail: mo@uu.net
Jim McManus
UUNET (MCI Worldcom)
3060 Williams Drive
Fairfax, VA 22031
Phone: +1 703-206-5607
EMail: jmcmanus@uu.net
13.0 Full Copyright Statement
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.