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.