Internet DRAFT - draft-ash-multi-area-te-compare
draft-ash-multi-area-te-compare
Network Working Group Jerry Ash, Editor
Internet Draft John Strand
<draft-ash-multi-area-te-compare-00.txt> AT&T
Expiration Date: September 2002
Cheng-Yin Lee
Senthil Venkatachalam
Alcatel
Alicja Celer
Nortel Networks
Sudheer Dharanikota
Nayna Networks
Adrian Farrel
Movaz Networks, Inc.
Norihito Fujita
Atsushi Iwata
NEC Corporation
Sudhakar Ganti
Tropic Networks
P. Srisuresh
Kuokoa Networks
Jean Philippe Vasseur
Cisco Systems
March, 2002
Comparison of Multi-Area TE Methods
<draft-ash-multi-area-te-compare-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This draft makes comparisons of various multi-area TE methods, which are
evaluated against specific criteria. Four basic path selection
approaches are compared: a) distributed methods,
b) path-computation-server (PCS) methods (centralized & distributed),
c) interarea-flooding methods, and d) multiple-path-compare methods.
These approaches include needs to support PCS functionality, query
functionality, crankback functionality, summary-te-LSA functionality,
and TE feedback functionality. The target is to converge on a reduced
subset of required multi-area TE methods and protocol extensions.
Table of Contents
1. Introduction
2. Criteria for Comparison of Multi-Area TE Methods
3. Multi-Area TE Needs for Protocol Extensions, Information Exchange
& Topology Data Base Update
4. Comparison of Multi-Area TE Methods
4.1 Distributed Methods
4.2 Path-Computation-Server (PCS) Methods (Centralized &
Distributed)
4.3 Interarea Flooding Methods
4.4 Multiple-Path-Compare Methods
5. Preliminary Observations & Conclusions
6. Security Considerations
7. Acknowledgments
8. References
9. Authors' Addresses
10. Copyright Statement
Appendix A. Multi-Area TE Routing Methods
A.1 State-Dependent Routing (SDR) LSP Selection
A.2 Event-Dependent Routing (EDR) LSP Selection
A.3 Time-Dependent Routing (TDR) LSP Selection
A.4 Inter-AS LSP Selection
1. Introduction
This draft describes comparisons of multi-area TE within the context of
MPLS/GMPLS. Based on the comparisons, the goal is to eventually provide
protocol extensions needed for multi-area TE. Multi-area TE has been
recommended to be supported in the requirements from the Traffic
Engineering Working Group [hierarchy_restoration_requirements]. Various
approaches to multi-area TE are considered, and the philosophies of
different approaches are outlined in Appendix A, and include state
dependent routing (SDR) LSP selection, event dependent routing (EDR) LSP
selection, and time dependent routing (TDR) LSP selection. The focus
initially is on multi-area TE, and not multi-AS TE. IP over optical
(IPO) needs are considered [mp-lambda-s, gmpls], including the unique
routing requirements of the optical plane [strand1, strand2, unique].
Several multi-area TE methods have been proposed, among them
[abarbanel], [kompella], [lee], [sudheer1], [sudheer2] [vdbosch].
Several of these methods propose the use of a path-computation-server
(PCS) capability [kompella, lee, vasseur], query capability [query],
crankback capability [crankback], and others suggest the use of summary
LSAs [summary_lsa]. These multi-area TE methods are evaluated against
various criteria identified in the Section 2. These various approaches
to multi-area TE are related by a common set of protocol needs discussed
in Section 3, which include PCS, query, and crankback. The comparisons
are made in Section 4, and preliminary conclusions are reached. The
target in future releases of this document will be to converge on a
reduced subset of the required multi-area TE methods and protocol
extensions.
2. Criteria for Comparison of Multi-Area TE Methods
There are various criteria to be considered in comparing the multi-area
TE methods, which include the following:
a) optimality -- maximize network utilization and minimize cost,
considering QoS objectives
b) scalability -- minimize routing overhead (includes LSAs, crankbacks,
queries, etc.); impact on IGP; number of active LSPs; number of
simultaneous LSP setups; LSDB state overhead
c) restoration/protection - i) allow multiple paths which satisfy path
diversity needs (may not be possible depending on the approach); ii)
allow LSP restoration/protection to occur separately within each area;
iii) allow multi-area information exchange of link protection types in
networks that support mixed link protection types
d) path selection functionality - i) ability to reoptimize multi-area TE
LSPs, ii) support bi-directional LSPs; iii) incorporate routing
constraints (simple, multiple, resource classes, ...) and unique IPO
requirements; iv) allow multi-area information exchange of link/switch
capabilities in networks that support mixed switching types; v) allow
multi-area GMPLS explicit label control (distributing label availability
information on lambdas and time slots); vi) dynamic
selection/provisioned path
e) path selection performance -- LSP setup time; synchronization impacts
Hence, multi-area TE protocols need to provide good cross-area path
selection and, most importantly, be scalable. As to scalability,
concerns have been raised as to the current scalability of IGPs
[igp-scale], and there is a need to minimize any further extensions in
the complexity of IGP protocols. Multi-area TE protocols need to
satisfy restoration/protection requirements, and also support several
GMPLS-related path selection needs. GMPLS [gmpls] allows the LSP request
to specify the link protection properties required. These are the
protection properties of the underlying link not those of the LSP
itself. Link protection possibilities are none, 1:n, 1:1, 1+1, better
than 1+1. Again, TE can only do this correctly if the link protection
properties are passed around, and this needs to be supported for
multi-area TE.
Note that even if path protection is not used in a network, it may be
required to be able to set up diversely routed TE LSPs. That is,
setting up multiple inter-area TE LSPs between LSRs may be desirable for
load balancing, if there is resource contention, in addition to the
protection/restoration need. For example, a single bandwidth requirement
between a pair of LSRs for X Mbits/s may not be met on a single LSP, but
it may be possible to find a set of TE LSPs between the LSRs whose total
bandwidth is equal to X Mbits/s. In this case, it is desirable to have
diversely routed TE LSPs.
Note that these criteria may or may not be fully satisfied depending on
the multi-area TE method being used. Even though various approaches
will not meet all criteria, they could still be valuable. Therefore
each method is evaluated in Section 5, taking into account the trade-off
between optimization and scalability as well as the other criteria
listed above.
3. Multi-Area TE Needs for Protocol Extensions, Information Exchange &
Topology Data Base Update
As discussed in the Introduction, several multi-area TE methods
[kompella, lee, sudheer1, sudheer2, vdbosch] are evaluated in the next
Section against the criteria, and include various protocol extension
needs (PCS, query, crankback, etc.). The target in future releases of
this document will be to converge on a reduced subset of the required
multi-area TE methods and protocol extensions. Various means of
information exchange, including support for PCS functionality, query
functionality, crankback functionality, TE feedback functionality, and
summary-LSA functionality, are required to build the topology database,
to construct the LSP choices, and to determine and establish a LSP from
the choices.
LSAs [ospf, isis] are flooded within areas to build the topology
database at each LSR by advertising link status, node status, reachable
addresses, and other information. LSAs could also be advertised between
areas; however this could raise scalability issues since areas are
established in the first place to limit LSA flooding to a reasonable
level within the designated areas (more on this later). Summarized LSAs
[summary_lsa] can be flooded between areas to give useful but reduced
information, but need to be scalable.
Query [query] messages are required in some multi-area TE methods, for
example, between an LER and a path computation server (PCS) [kompella,
lee, vasseur], or between an LER and ABR (in this case the ABR plays the
role of an PCS), to determine topology database information needed to
calculate a path for an LSP. A query could also be used to request
that an PCS or ABR compute an LSP path from its topology database, and
return it to the requesting LSR, ABR, or other PCS. Various other means
of using query-response may be proposed, as described in [kompella].
Using the topology database, the LSR or PCS generates the LSP choices
according to a number of different LSP selection methods, such as those
described in Section 3 and Appendix A. Crankback [crankback] can be
used in LSP setup, or modification, to backtrack to an ABR or LER, if a
bottleneck is found in a candidate LSP (e.g., if there is insufficient
bandwidth on a particular link in the LSP). Use of crankback to an ABR
may or may not be more efficient than rerouting from the head-end LSR,
and would depend on the resource requirements and network topology.
One way to view the topology database at each LSR or PCS is to consider
a decomposition into the slow information database (SIDB) and the fast
information database (FIDB).
Information in the SIDB changes slowly, for example
o max link bandwidth
o color
o metric (weight, delay, etc.)
o reachable addresses
o slow available link bandwidth update (e.g., based on >= 5-minute
updates)
Information in the FIDB changes rapidly, for example
o available link bandwidth (e.g., real-time updates)
The LSA overhead to flood information in the SIDB is relatively much
less than the LSA overhead to flood information in the FIDB, because of
the relative rates of change of the database, not because of their
relative sizes. It might well be feasible, for example, to flood the
full SIDB information between areas, whereas it may not be feasible to
flood the full FIDB information (vs. summarized LSA information) between
areas. However, flooding of the full SIDB information may also pose
some scalability issues. The use of SIDB and FIDB information by each
multi-area TE method is detailed in the next section.
Note that the SIDB and FIDB information needs to be identified for each
class type. TE methods are currently being defined for multiple class
types [class] wherein the amount of SIDB/FIDB information will greatly
increase (multiplicative by the number of classes). This will increase
the emphasis on information exchange methods that decrease the routing
overhead in terms of LSAs, crankbacks, queries, etc. In general, SLAs,
PHBs, and class types may not be consistent across domains or areas, and
could be policy specific. In that case, a consistent meaning for class
type needs to be defined.
In summary, protocol support of multi-area TE methods include needs to
support
o path-computation-server (PCS) functionality [kompella, lee, vasseur,
te-qos-routing],
o query functionality [query, vasseur],
o crankback functionality [crankback],
o te-summary-LSA functionality [summary_lsa],
o multi-path-compare signaling functionality [vdbosch],
and, optionally,
o TE feedback functionality [feedback].
Details of the proposed protocol upgrades necessitated by the various
multi-area TE solution approaches are already available in the various
drafts referenced.
4. Comparison of Multi-Area TE Methods
In the previous Sections we gave comparison criteria and needed
information exchange for multi-area TE, which included SDR, EDR, and TDR
methods described in Appendix A. Four generic path selection approaches
are compared: a) distributed methods, b) path-computation-server (PCS)
methods (centralized & distributed), c) interarea-flooding methods, and
d) multiple-path-compare methods. In this Section we classify each
proposed multi-area-te method into one of the 4 generic approaches,
evaluate the 4 approaches against the criteria, identify protocol
extension needs for the 4 approaches (PCS, query, crankback,
te-summary-LSA, etc.), and discuss the relative advantages and
disadvantages of the 4 generic methods. The target is to converge on a
reduced subset of required multi-area TE methods and protocol
extensions.
In each Section we also provide a brief summary each multi-area TE
method. See also Appendix A for explanations of the various approaches
to multi-area TE, and the philosophies of different approaches to SDR,
EDR, and TDR LSP selection. The use of various protocol extensions,
such as crankback and PCS functionality, are also discussed in Appendix
A.
See [te_qos_routing] for more detailed comparisons of these methods on
the basis of performance, network design impacts, and operational
impacts. Multiservice network models are used to evaluate performance,
design, and operation.
4.1 Distributed Methods
a. brief summary of method
- per area path set up
- SIDB/FIDB flooded intra-area
- normal summary-LSAs inter-area for route advertisements
- optionally, use crankback to ABR or LER if LSP setup request fails
- feedback [feedback] can be used to help build LSR TE routing database
b. examples of method
- [kompella]/scenario 1 approach (LSPs selected on per-area basis)
- Success-to-the-top EDR (STT-EDR) [te_qos_routing] (LER determines
CRLSP based on SIDB)
c. protocol extensions required
- none (crankback is optional)
d. relative advantages and disadvantages
- optimality: end-to-end path may not be optimal (LSP choices not based
on whole topology database),
- scalability: no-TE-summary LSA flooding between areas
- restoration/protection: no possibility to compute diversely routed
paths
- path selection functionality: path reoptimization difficult (may not
be possible)
- path selection performance: signaling setup time may not be
negligible, especially with a large number of ABRs and with resource
contention
4.2 Path-Computation-Server (PCS) Methods (Centralized & Distributed)
a. brief summary of method
- PCSs could be separate or combined ABR/PCS
- PCS(s) within area gather intra-area link-state information (reduces
intra-area flooding)
- LER queries a PCS in backbone area for path
- LER does not download TE information from backbone area (reduces
flooding across areas)
- crankback may be used for LSP rerouting
- PCS may try path query to another PCS within area to determine another
LSP
- intra-area SIDB/FIDB flooded only to PCSs
- uses LER-PCS query
b. examples of method
- [kompella/scenario 2&4, lee, vasseur, te-qos-routing] approach
(distributed PCS approach wherein PCSs could be separate or combined
ABR/PCS)
- [kompella]/scenario 5 approach (LER queries central PCS for path)
- TDR [te_framework, te_qos_routing] (LSP selection by centralized
off-line system, based on previously measured traffic, and downloaded
periodically to LSRs)
- D-SDR query approach [te_qos_routing] (LER queries LSRs/ABRs along
candidate LSPs for FIDB information,at time of LSP setup or
modification)
c. protocol extensions required
- PCS
- query
- (crankback is optional)
d. relative advantages and disadvantages
- optimality: end-to-end optimal path (whole topology database used for
LSP determination); global optimization possible (with central PCS or
central TDR computation)
- scalability: possible intra-area LSA flooding reduction (requires no
interarea TE-summary-LSA flooding); signaling overhead for ABR/PCS query
- restoration/protection: possibility to compute diversely routed paths
- path selection functionality: path reoptimization possible; requires
PCS implementation with PCS
- path selection performance:
4.3 Interarea Flooding Methods
a. brief summary of method
- ABRs flood TE-summary-LSA's to other areas
- LER sets up LSP based on topology database, including summary-LSA
information
- transit LSRs may use crankback if LSP setup request fails, ABR or LER
may try another LSP
- SIDB/FIDB flooded intra-area
- summarized SIDB/FIDB flooded inter-area (in TE-summary-LSAs)
- feedback can be used to help build LSR TE routing database
b. examples of method
- [sudheer1] approach (summary-TE-LSAs flooded between areas)
- [kompella]/scenario 3 approach (LER gets TE information from
backbone-area and computes path to tail-end ABR, tail-end ABR computes
rest of path, all backbone TE information is flooded)
- [srisuresh] (TE LSAs are defined to extend OSPF for traffic
engineering)
c. protocol extensions required
- TE-summary-LSA
- (crankback is optional)
d. relative advantages and disadvantages
- optimality: end-to-end path may not be optimal (LSP choices not based
on whole topology database),
- scalability: possible scalability issue in amount of flooded
information (TE-summary-LSA reduces flooded information between areas
compared to methods that flood entire SIDB/FIDB information); may need
to maintain more than one summarized TE link per destination prefix
- restoration/protection: may not be possible to compute diversely
routed paths
- path selection functionality: path reoptimization may be complex; may
not be possible to summarize some constraints
- path selection performance:
4.4 Multiple-Path-Compare Methods
a. brief summary of method
- ingress LER launches multiple LSP set-ups to egress LER
- intermediate LSRs select among multiple LSP set-ups as to which to
selectively forward, based on recorded metrics
- egress LER selects 'best' path based on recorded metrics
- 'best' path signaled in RESV message
b. examples of method
- [vdbosch] (uses branched LSP setup)
c. protocol extensions required
- PATH & RESV message extensions for accumulated metric, delay, etc. and
for sending multiple PATH messages in response to one received PATH
message
d. relative advantages and disadvantages
- optimality: end-to-end optimal path (could be a large number of paths
and large signaling overhead),
- scalability: could be considerable signaling if number of ABRs is
large; no TE-summary-LSA flooding between areas
- restoration/protection: may be difficult to compute diversely routed
paths
- path selection functionality: path reoptimization possible (may
require significant signaling overhead); may need to put many resources
on hold during path selection process (avoids race conditions)
- path selection performance: signaling setup time may not be negligible
5. Preliminary Observations & Conclusions
The distributed methods may be the most scalable, however they may
suffer from a possible lack of optimal LSP selection. The centralized
and PCS methods have the potential to be quite scalable and the
possibility of near optimal LSP selection. The interarea flooding and
multiple path selection methods may not be the most scalable and may
suffer from a possible lack of optimal LSP selection. All the methods
may benefit from the use of crankback.
6. Security Considerations
The multi-area routing extensions for RSVP-TE and CRLDP inherit the same
security mechanisms described in [rsvp_te, crldp] to protect against
spoofing attacks of a session, the privacy of signaling messages, and
the denial of service (DoS) attacks. Different areas may apply distinct
security models and may have different means of signaling security
(especially if one area does not use MPLS). Joining security domains
would introduce security issues that need to be addressed.
7. Acknowledgments
Comments and suggestions from Dan Awduche are much appreciated.
8. References
[abarbanel] Ben Abarbanel, Senthil K. Venkatachalam, "BGP-4 support for
Traffic Engineering," work in progress.
[awduche] D. Awduche, "MPLS and Traffic Engineering in IP Networks,"
IEEE Communications Magazine, December 1999.
[class] Francois Le Faucheur, et. al., "Requirements for support of
Diff-Serv-aware MPLS Traffic Engineering," work in progress.
[crldp] B. Jamoussi, et al., "Constraint-Based LSP Setup using LDP,"
work in progress.
[crankback] Atsushi Iwata, Norihito Fujita, Gerald R. Ash, Adrian
Farrel, "Crankback Routing Extensions for MPLS Signaling,", work in
progress.
[feedback] Peter Ashwood-Smith, Bilel Jamoussi, Don Fedyk, Darek
Skalecki "Improving Topology Data Base Accuracy with LSP Feedback," work
in progress.
[gmpls] P. Ashwood-Smith and L. Berger, et al., "Generalized
MPLS-Signaling Functional Description,", work in progress.
[hierarchy_restoration_requirements] Wai Sum Lai, et. al., "Network
Hierarchy and Multilayer Survivability," work in progress.
[igp-scale] Ash, G., et. al., "Proposed Mechanisms for Congestion
Control/ Failure Recovery in OSPF & ISIS Networks," work in progress.
[isis] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
Environments," RFC1195, December 1990.
[kompella] Kireeti Kompella, Yakov Rekhter, JP Vasseur, "Multi-area MPLS
Traffic Engineering," work in progress.
[lee] Cheng-Yin Lee, Alicja Celer, Neil Gammage, Sudhakar Ganti, Gerald
Ash, "Distributed Route Exchangers," work in progress.
[ldp] L. Andersson, et. al., "LDP Specification," RFC 3036, January
2001.
[mp-lambda-s] D. Awduche, et al., "Multi-Protocol Lambda Switching:
Combining MPLS Traffic Engineering Control with Optical Crossconnects,"
IEEE Communications Magazine, March 2001.
[ospf] J. Moy, "OSPF Version 2," RFC2328, April 1998.
[query] Cheng-Yin Lee, Sudhakar Ganti, "Path Request and Path Reply
Message,", work in progress.
[recovery] S. Makam, et. al., "Framework for MPLS-based Recovery," work
in progress.
[rsvp] R. Braden, et al., "Resource ReSerVation Protocol (RSVP)--Version
1 Functional Specification, RFC2205, September 1997.
[rsvp_te] D. Awduche, et al., "Extensions to RSVP for LSP Tunnels," work
in progress.
[srisuresh] P. Srisuresh, et. al., "TE LSAs to extend OSPF for Traffic
Engineering," work in progress.
[strand1] John Strand, Angela Chiu, Robert Tkach, "Issues for Routing in
the Optical Layer," IEEE Communications Magazine, February 2001.
[strand2] John Strand, Yong Xue, "Routing for Optical Networks With
Multiple Routing Domains," oif2001.046 (for a copy send an email request
to jls@research.att.com).
[sudheer1] Senthil K. Venkatachalam, Sudheer Dharanikota, "A Framework
for the LSP Setup Across IGP Areas for MPLS Traffic Engineering,", work
in progress.
[sudheer2] Senthil K. Venkatachalam, Sudheer Dharanikota, Thomas D.
Nadeau, "OSPF, IS-IS, RSVP, CR-LDP extensions to support inter-area
traffic engineering using MPLS TE," work in progress.
[summary_lsa] Atsushi Iwata, Norihito Fujita, "Traffic Engineering
Extensions to OSPF Summary LSA," work in progress.
[te_qos_routing] G. Ash, "Traffic Engineering & QoS methods for IP-,
ATM-, & TDM-Based Multiservice Networks," work in progress.
[te_framework] D. Awduche, et. al., "Overview & Principles of Internet
Traffic Engineering" work in progress.
[te_requirements] D. Awduche, et al., "Requirements for Traffic
Engineering Over MPLS," RFC2702, September 1999.
[unique] Angela Chiu, John Strand, Robert Tkach, "Unique Features and
Requirements for The Optical Layer Control Plane," work in progress.
[vasseur] JP Vasseur, "RSVP Path Computation Request and Reply
Messages," work in progress.
[vdbosch] S. Van den Bosch, "Multi-area traffic engineering using
branched LSP setup," work in progress.
9. Authors' Addresses
Jerry Ash
AT&T
Room MT D5-2A01
200 Laurel Avenue
Middletown, NJ 07748, USA
Phone: +1-(732)-420-4578
Fax: +1-(732)-368-8659
Email: gash@att.com
Alicja Celer
Nortel Networks
Email: aceler@nortelnetworks.com
Sudheer Dharanikota
Nayna Networks
157 Topaz Drive
Milpitas, CA 95035
Phone: (408)-956-8000 x357
Email: sudheer@nayna.com
Adrian Farrel
Movaz Networks, Inc.
7926 Jones Branch Drive, Suite 615
McLean, VA 22102
Phone: +1-(703)-847-9847
Email: afarrel@movaz.com
Norihito Fujita
NEC Corporation
Networking Research Laboratories
1-1, Miyazaki, 4-Chome, Miyamae-ku,
Kawasaki, Kanagawa, 216-8555, JAPAN
Phone: +81-(44)-856-2123
Fax: +81-(44)-856-2230
Email: n-fujita@bk.jp.nec.com
Sudhakar Ganti
Tropic Networks Inc.
135 Michael Cowpland Drive
Kanata, Ontario, Canada, K2M 2E9
Email: sganti@tropicnetworks.com
Atsushi Iwata
NEC Corporation
Networking Research Laboratories
1-1, Miyazaki, 4-Chome, Miyamae-ku,
Kawasaki, Kanagawa, 216-8555, JAPAN
Phone: +81-(44)-856-2123
Fax: +81-(44)-856-2230
Email: a-iwata@ah.jp.nec.com
Atsushi Iwata
Cheng-Yin Lee
Alcatel
Email: : cheng-yin.lee@alcatel.com
Pyda Srisuresh
Kuokoa Networks, Inc.
2901 Tasman Dr.,
Suite 202
Santa Clara, CA 95054, USA
EMail: srisuresh@yahoo.com
John Strand
AT&T
Room MT A5-1D06
200 Laurel Avenue
Middletown, NJ 07748, USA
Phone: +1-(732)-420-9036
Fax: +1-(732)-368-9433
Email: jstrand@att.com
Jean Philippe Vasseur
Cisco Systems, Inc.
11, rue Camille Desmoulins
92782 Issy les Moulineaux Cedex 9
France
Email: jpv@cisco.com
Senthil K. Venkatachalam
Alcatel USA
45195 Business Court, Suite 400
Dulles, VA 20166
Phone: (703)654-8635
Email: Senthil.Venkatachalam@usa.alcatel.com
9. Copyright Statement
Copyright (C) The Internet Society (1998). 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.
Appendix A. Multi-Area TE Routing Methods
Internet Traffic Engineering is concerned with the performance
optimization of operational networks [awduche]. It encompasses the
measurement, modeling, characterization, and control of Internet
traffic, and the application of techniques to achieve specific
performance objectives, including the reliable and expeditious movement
of traffic through the network, the efficient utilization of network
resources, and the planning of network capacity.
Multi-area or multi-AS topologies are normally used with IP routing
protocols (e.g., OSPF, BGP). Traffic trunks can be defined by LSPs
between LSRs, and are used to allocate the bandwidth of the logical
links to various LSR pairs. TE LSP routing is characterized by the LSP
choices used in the method and rules to select one LSP for a given
connection or bandwidth-allocation request. When an LSP
bandwidth-allocation request is initiated by an LER, the LER
implementing the routing method executes the LSP selection rules to find
an admissible LSP from among the LSPs that satisfy the request. In a
network with source routing, the LER maintains control of the LSP
request, and in the case of multi-area TE, this must be done across
different areas.
With source routing, the LER identifies the entire selected LSP
including all intermediate or via LSRs (VLSRs) and egress LSR (ELSR) in
the LSP in an explicit-route (ER) parameter. Some VLSRs may lie on the
boundary of areas and are area border routers (ABRs). If the QoS or
traffic parameters cannot be realized at any one of the VLSRs in the LSP
setup request, then the VLSR generates a crankback parameter which
allows a VLSR to return control of the bandwidth-allocation request to
the LER or ABR for further alternate routing.
LSPs are determined by (normally proprietary) algorithms based on the
network topology and reachable address information. LSPs can cross
multiple areas within an AS, and also cross multiple ASs. An LER may
select an LSP based on the routing rules and the QoS resource management
criteria, which must be satisfied on each link in the LSP. In addition
to controlling bandwidth allocation, the QoS resource management
procedures can check other QoS parameters, such as end-to-end transfer
delay, delay variation, and transmission quality considerations such as
loss, echo, and noise.
LSP selection methods are categorized into the following three types:
o state-dependent routing (SDR) LSP selection,
o event-dependent routing (EDR) LSP selection, and
o time-dependent routing (TDR) LSP selection
LSP choices can be changed dynamically, either on-line, in real time, as
in SDR or EDR, or in an off-line, preplanned, time-varying manner, as in
TDR. Real-time LSP selection does not depend on precalculated LSP
choices. Rather, the LSR or path computation server (PCS) senses the
immediate traffic load and if necessary searches out new LSPs through
the network. On-line, real-time LSP selection methods include EDR and
SDR. With off-line, pre-planned TDR LSP selection, LSP choices might
change every hour or at least several times a day to respond to measured
hourly shifts in traffic loads, and are periodically recalculated,
perhaps each week. Note that SDR LSP selection is the only method
currently available and deployed.
An LER can fully calculate an ER at the source based on TDR, SDR, or EDR
LSP selection, or the ER can include loose hops which are used at ABRs.
In the latter case, the ER processing rules allow the ABRs to insert a
series of hops to navigate to the next ABR, thus the LSP choice is not
constrained to the LER. This distinction is made in [crankback], but
only after the initial signaling attempt (with the LER-signaled ER) has
failed. The designation of ABRs along the path is a possible method
that may or may not use crankback.
A.1 State-Dependent Routing (SDR) LSP Selection
SDR LSP selection is the only method currently available and deployed.
In SDR, the LSP choices are altered automatically according to the state
of the network. For a given SDR method, the LSP selection rules are
implemented to determine the LSP choices in response to changing network
status, and are used over a relatively short time period. Information
on network status may be collected at a central path computation server
(PCS) processor or distributed to multiple PCSs or the LSRs in the
network.
The information exchange may be performed by
o flooding the information to all the PCSs and/or LSRs in the network
o querying PCSs or LSRs on an on-demand basis for needed information,
o feeding the information back on LSP signaling messages
o a combination of any of the above
SDR methods route LSP bandwidth-allocation requests on the best
available LSP on the basis of network state information. For example,
in the least loaded routing (LLR) method, the residual capacity of
candidate LSPs is calculated, and the LSP having the largest residual
capacity is selected for the bandwidth-allocation request. Various
relative levels of link occupancy can be used to define link load
states, such as lightly-loaded, heavily-loaded, or
bandwidth-not-available states. In general, SDR methods calculate a LSP
cost for each bandwidth-allocation request based on various factors such
as the path metric (IGP or TE metric) or reservation state of the links
in the network.
In SDR, the LSP choices are designed on-line by the LER or an PCS
through the use of network status and topology information obtained
through information exchange with other LSRs and/or other PCSs. There
are various implementations of SDR distinguished by whether the
computation of the LSP choices is
a) distributed among all the LSRs in an AS, or
b) done in a centralized PCS per AS, or perhaps several PCSs (e.g., 1 or
more per AS area).
This leads to two different implementations of SDR:
a) distributed SDR (D-SDR) -- here each LSR in the AS obtains topology
and status information from all the other LSRs. Normally the topology
status information is flooded throughout each area in the AS, and
between areas with summary-LSAs. In another form of D-SDR, rather than
flooding information an LER queries the other LSRs in the candidate LSPs
to obtain topology and status information. To determine an LSP explicit
route, the LER executes a particular routing optimization procedure such
as LLR.
b) path computation server SDR (PCS-SDR) -- here the centralized PCS or
several PCSs obtain topology and status information from the various
LSRs within an AS or within an AS-area. The topology/status information
can be sent on a periodic basis (e.g., every few seconds) or based on
topology/status changes. The PCS performs a computation of the
candidate LSPs on a periodic basis (e.g., every few seconds) or
on-demand (e.g., initiated by a query from an LER). To determine the
LSP explicit route, the PCS computes the constrained route by executing
a particular routing optimization procedure such as LLR. The LSPs are
either transmitted to the LSRs on a periodic basis (e.g., every few
seconds) or provided on demand from an LER.
The essential distinction between D-SDR and PCS-SDR LSP selection is
where the TE routing database is kept and the LSP choices are made. In
the D-SDR case, the database and LSP choices are made at the LSRs
themselves. In the PCS-SDR case, the database and LSP choices are made
at the PCS(s). Note that in PCS-SDR the path computation server may be
a dedicated off-line server or one or several ABR LSRs (see scenarios 2,
4, and 5 of [Kompella]).
In either instance, LSP explicit routes may be determined based on the
constraints specified and analysis of the status data. For example, an
LSP selection method might provide that the primary (shortest) LSP
choice is used if the bandwidth is available. If the bandwidth is
unavailable on one or more links, a second LSP is selected from the list
of feasible LSPs on the basis of having the greatest level of idle
bandwidth at the time. This second LSP may be used to provide bandwidth
capacity in addition to that already provided by the primary LSP between
the LER and egress LSR. The second LSP may be selected from among a
pre-stored list of candidate LSPs or computed on line based on the
constraints and network status information in the TE routing database.
Dynamically activated bandwidth reservation can be used to protect
against inefficient LSP usage, and other controls used to automatically
modify LSP choices during network overloads and failures
[te_qos_routing].
A.2 Event-Dependent Routing (EDR) LSP Selection
EDR LSP selection is an optional method that is not currently available
and deployed. In EDR, the LSP choices are updated locally on the basis
of whether connections succeed or fail on a given LSP choice. In the
EDR learning approaches, the LSP last tried, which is also successful,
is tried again until blocked, at which time another LSP is selected at
random and tried on the next bandwidth-allocation request.
Success-to-the-top (STT) EDR LSP selection is a decentralized, on-line
LSP selection method with update based on random routing. STT-EDR uses
a simplified decentralized learning method: The primary LSP LSP-p is
used first if available, and a currently successful alternate LSP LSP-s
is used until it is blocked. In the case that LSP-s is blocked (e.g.,
bandwidth is not available on one or more links), a new alternate LSP
LSP-n is selected at random as the alternate LSP choice for the next
bandwidth-allocation request overflow from the primary LSP. Dynamically
activated bandwidth reservation is used under congestion conditions to
protect traffic on the primary LSP. STT-EDR uses crankback when an
alternate LSP is blocked at a VLSR, and the bandwidth-allocation request
advances to a new random LSP choice. In STT-EDR, many LSP choices can be
tried by a given bandwidth-allocation request before the request is
blocked.
The main point of EDR is that is does not require a centralized database
of FIDB information, such as is provided in D-SDR at each LSR through
flooding or query, or in PCS-SDR at each PCS. In the case of EDR, the
FIDB information is accessed locally at each LSR as the LSP is set up or
modified. Hence in EDR, the FIDB information is decentralized, however
with SDR the FIDB information is kept in one database, either in the
LSRs or centralized in an PCS.
In the EDR learning approaches, the current alternate LSP choice can be
updated randomly, cyclically, or by some other means, and may be
maintained as long as a connection can be established successfully on
the LSP. Hence the LSP selection is constructed with the information
determined during connection setup, and no additional information is
required by the LER.
A.3 Time-Dependent Routing (TDR) LSP Selection
TDR LSP selection is an optional method that is not currently available
and deployed. With TDR methods the LSP choices are altered at a fixed
point in time during the day or week. TDR LSP choices are determined on
an off-line, preplanned basis and are implemented consistently over a
time period. The TDR LSP choices are determined considering the time
variation of traffic load in the network, for example based on measured
hourly load patterns. Several TDR time periods are used to divide up the
hours into contiguous routing intervals. Typically, the TDR LSP choices
used in the network are coordinated to take advantage of noncoincidence
of busy hours among the traffic loads.
In TDR, the LSP choices are preplanned and designed off-line using a
centralized system, which employs a TDR network design model. The
off-line computation determines the optimal routes from a potentially
very large number of possible alternatives, in order to maximize network
throughput and/or minimize the network cost. The designed LSP choices
are loaded and stored in the various LSRs in the TDR network, and
periodically recomputed and updated (e.g., every week) by the central
system. In this way an LER does not require additional network
information to construct TDR LSP choices, once the LSP choices have been
loaded. This is in contrast to the design of LSP choices on-line in
real time, such as in the SDR and EDR methods described below. LSPs in
the TDR routing table may consist of time varying routing choices and
use a subset of the available LSPs. That is, we can distinguish between
LSP calculation/choice and LSP establishment. In TDR, the LSP choices
are made off line and are changed by a change in time period. In SDR
and EDR, the LSP choices are determined on line and changed by a change
in the network state and/or an event such as a blocked LSP request (a
variant of SDR and EDR could be to have the LSP choices made off line).
LSPs in the TDR routing table may consist of several (possibly
multiple-link) LSPs through multiple VLSRs. If a connection on one link
in a LSP is blocked (e.g., because of insufficient bandwidth), the
bandwidth-allocation request then attempts another complete LSP.
Implementation of such a routing method can be done through control from
the LER or ABR, plus a crankback capability that allows a
bandwidth-allocation request blocked on a link in an LSP to return to
the LER or ABR for further alternate routing on other LSPs.
Changing a TDR LSP should be done, for example, using a make before
break method to avoid traffic disruption. If a TDR LSP change should
fail due to lack of available resources, this would trigger alarms and
the use of the previous TDR LSP could be used in the interim.
A.4 Inter-AS LSP Selection
In selecting LSPs between autonomous systems (ASs), which themselves may
consist of multiple areas, inter-AS routing capabilities such as BGP
[abarbanel] need to be considered. Though not specifically addressed in
this draft, some of the multi-area TE methods described herein can very
well be used to address the needs of multi-AS LSP selection as well.
Details of inter-AS LSP selection are TBD.
