Internet DRAFT - draft-ash-pce-problem-statement


Network Working Group                                        Jerry Ash
Internet Draft                                                    AT&T
Category: Informational                                              
Expires: December 2004                                   Adrian Farrel
                                                    Old Dog Consulting
                                                             June 2004

              Path Computation Element Problem Statement

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

   The list of Internet-Draft Shadow Directories can be accessed at


This document provides a problem statement for the proposed Path
Computation Element (PCE).  The PCE is an approach to MPLS traffic
engineering path computation that is particularly applicable in
inter-domain environments.

In this context, a domain may be an IGP area, an Autonomous System, or
some other division of computational responsibility.

An overview of solution alternatives and proposed PCE work group
charter is also provided.

Table of Contents

   1. Introduction                                             
   2. Problem Statement
   3. Overview of Solution Alternatives
   4. Proposed Charter of PCE Working Group
   5. Security Considerations                                 
   6. Acknowledgments                                         
   7. Normative References
   8. Informational References
   9. Authors' Addresses
   10. Intellectual Property Considerations
   11. Full Copyright Statement

1. Introduction

This document provides a problem statement for the proposed path
computation element (PCE) approach to computing MPLS traffic engineering
(TE) paths in multi-domain environments.  A domain may be an IGP area,
an Autonomous System (AS), or some other division of computational
responsibility.  This document covers the cases of multiple ASes
belonging to the same SP and also the inter-SP case.

Information on network status is flooded to the PCEs in the domain, and
the PCEs are queried to supply paths for LSPs.  The PCE responds to the
path computation requests by computing the best available LSP route(s)
satisfying the set of specified constraints based on various factors
such as the path metric, availability state/network status, and topology
information.  Note that the resultant explicit route(s) may be made up
of a set of strict or loose hops, or any combination of strict and loose

Inter-area/AS MPLS TE requirements appear in [inter-area-req,
inter-as-req] and a framework for inter-domain MPLS TE is found in
[ccamp_fw].  Several inter-area and inter-AS MPLS TE methods have been
proposed, among them [kompella, lee, vasseur1, vasseur2], and some of
these methods propose the use of a PCE capability [kompella, lee,
vasseur1, vasseur2], query capability [query, vasseur1], and crankback
capability [crankback].

A problem statement is provided in Section 2, overview of solution
alternatives in Section 3, and proposed charter of the PCE working group
in Section 4.

2.	Problem Statement

Criteria to be considered in applying an inter-domain computation method
are listed below. These criteria are applicable to inter-area, inter-AS
(including multiple ASes belonging to the same SP), and inter-SP.

a. Optimality - maximize network utilization and minimize cost,
considering QoS objectives.
b. Scalability - routing and signaling overhead (includes LSAs,
crankbacks, queries, etc.).
c. Load sharing - allow multiple paths which satisfy load sharing needs.
d. Restoration/protection -
   i)  Allow multiple paths which satisfy path diversity needs
   ii) Allow LSP restoration/protection to occur separately within each
e. Path computation functionality -
   i)  Ability to reoptimize LSPs
   ii) incorporate routing constraints.
f. Path computation performance - Time to compute a path on demand may
affect LSP setup time.
g. Ability to provide a loose path (required in some cases to preserve
confidentiality across domains)

In the light of the above criteria, the problem statement is as follows.

A. Path computation may be a CPU-intensive operation.  In this
situation, it may not be appropriate for a router to perform path 
computation.  Although alternatives exist using loose routes, such 
techniques either force the path computation to be performed at other 
routers in the network (which may be similarly constrained), or reduce 
to hop-by-hop routing which may not be optimal from a TE perspective.  
In order to provide a full explicit path in such circumstances, the use 
of some remote PCE may be appropriate to compute the path (or the set of 
paths) satisfying a particular set of constraints and optimizing some 
specific objectives.

B. The traffic engineering database (TEDB) may be a large drain on the
resources of a router both from a memory perspective and because it may 
require significant CPU activity to maintain it.  The use of a PCE may
be appropriate in such circumstances to establish the TEDB and make it
available for path computation.

C. Some networks do not run adequate IGPs to build a full TEDB. For
example, a network may run OSPF without the OSPF-TE extensions, or some
routers in the network may not support the TE extensions.  In these 
cases, in order to successfully operate MPLS TE signaling in the network, 
the TEDB must be constructed or supplemented through configuration 
action, and updated as LSPs are added or removed.  Such a TEDB could be 
distributed to each router so that each router can perform path 
computation, or held centrally for centralized path computation.

D. It is possible that the ingress router for an LSP has limited
visibility to the destination.  This limitation may occur because the
destination lies in a separate domain (for example, a different IGP area 
or AS) and so the ingress router does not receive TE information about 
all of the links between the source and destination.  In such cases, it 
is possible to use loose routes to establish the LSP, relying on routers 
at the domain borders to establish the next piece of the path.  However, 
because no node has an overall view of the network, it is not possible 
to guarantee that the optimal path will be used, nor even that a viable 
path will be discovered except, possibly, through repeated trial and 
error using crankback (and still such a solution does not guarantee an 
optimal path).  A PCE solution to this problem allows cooperation 
between the domains so that an optimal path can be computed and used.

E. The issues expressed in point D can be further highlighted in the
context of LSP re-optimization, or the establishment of multiple diverse 
LSPs for protection or load sharing.

F. An LER may not be part of the routing domain for administrative
reasons (for example, a CE device connected to the PE router in the 
context of an MPLS VPN and for which it is desired to provide a CE to CE 
TE LSP path).  Note that this provides a good example of a PCE returning 
a loose path.

The above issues point to a solution that may not involve doing
computation on the ingress router or relying wholly on loose hops.

3. Overview of Solution Alternatives

Solution alternatives discussed here identify approaches on how to
provide support for PCE.  There are two ways of providing a computed

a. The path computation may be provided by the LSR that needs it;
b. The path computation may be done by some other network node on behalf
of the LSR.

In the former case, no extra work is required to achieve the computed
path. In the latter case, the LSR that requires the computation must
find and communicate with the other node that will provide the

In all cases, the computation may be achieved:

c. By a single node;
d. Through cooperation between nodes.

In the case of d, the cooperation may be reflected as:

d1. Loose hops or non-explicit abstract nodes in the path used by the
first LSR.  This forces other LSRs to make further path computations 
using a. or b.
d2. Cooperation between the requesting LSR and multiple other network
nodes to derive the full path.
d3. Cooperation between other network nodes unbeknownst to the
requesting LSR.

Mechanisms for option a. are well-known, and these extend to ac. and
ad1.  The PCE is the network element that supports option b.  Various
mechanisms are required in order to define different ways to support bc,
bd1, bd2, and bd3.

The following structure can be considered for solution alternatives:

3.1 PCE for Inter-Domain TE LSP Path Computation

3.1.1 Distributed PCEs for Inter-Domain TE

i) Single SP case

- PCEs are provided at each of n domain boundary nodes (such as
ABRs/ASBRs) in each domain
- Assumes dynamic PCE discovery (with load balancing, primary/secondary
- Shortest end-to-end path built by backward recursive computation


- Requires more complex protocol extensions (LSR/PCE signaling, PCE
- Optimal end-to-end path is computed (where optimal means shortest
- Diverse path computation is possible

ii) Inter-SP case

- Same path computation technique as above
- Confidentiality/security aspects need to be considered

3.1.2 Centralized PCEs for Inter-Domain TE

This technique applies only to inter-domain TE within a single SP.

- Similar to scenario 5 described in [kompella].

3.2 PCE for Intra-area TE LSP Path Computation

There is no assumption that PCE services should be limited to
inter-domain LSPs. PCE might be required for the more CPU intensive TE
LSP path computation, typically multiple-constraints optimization
techniques.  Examples might be:

- Non-PSC TE LSP path computation where significant optical constraints
might be applied
- Point-to-multipoint path computation

4. Proposed Charter of PCE Working Group

The PCE working group coordinates the work within the IETF of defining
the operation of path computation elements within the Internet. Path
computation elements are responsible for computing paths through IP
networks for uses such as traffic engineering so that a prime consumer
of such paths might be an MPLS-TE LSR. Areas of responsibility will 
include the collection of attributes relevant to the computation of 
paths, the discovery by LSRs of available path computation elements, 
the communication with LSRs for the request of path computation, the 
collaboration between path computation elements within the network, 
and analysis of path computation algorithms with a view to ensuring 
consistency between computed paths. The working group will work 
closely with many working groups in the Routing Area including the 
OSPF, IS-IS, IDR, MPLS and CCAMP working groups.

The PCE working group scope includes:

a. Definition of Generalized Traffic Engineered LSP paths computation
techniques involving Path Computation Element(s). This includes the
intra IGP area, inter IGP area, inter-AS and inter-provider TE LSPs 
path computation for Point-to-Point, Point-to-Multipoint and
Multipoint-to-Multipoint TE LSPs.
b. Definition of protocol-independent metrics and constraints defining
path quality measurement criteria, algorithm complexity and 
scalability criteria related to path computation techniques.
c. Definition of requirements for communication between LSRs and PCEs
including routing extensions in support of PCE discovery techniques
within an IGP area and across multiple IGP areas, ASes and Provider 
networks, and including the development of new protocols or protocol 
extensions for requesting path computation and supplying responses. 
Any protocol extensions will developed in conjunction with the 
working groups in charge of the specific protocols.
d. Specification of routing (OSPF, ISIS, BGP) and signaling extensions
(RSVP-TE) required by PCE-based path computation techniques. The
extensions will developed in conjunction with the working groups in 
charge of the specific protocols.
e. Specification of requirements and protocol extensions related to the
policy, security and confidentiality aspects of PCE-based path
computation techniques involving PCEs of multiple Providers.
f. Definition of MIBs, management procedures related to the protocol
extensions defined by the WG

In doing this work, the WG will closely work with at least the following
other WGs: CCAMP, MPLS, ISIS, OSPF, IDR. The WG will also cooperate with
the ITU-T and OIF.

5. Security Considerations

This is an informational problem statement and introduces no security
considerations in its own right.

However, it should be observed that the use of a PCE does introduce
additional security issues above those already present in MPLS signaling
and routing. Most notable amongst these are:

- Interception of PCE requests or responses
- Impersonation of PCE
- Denial of service attacks on PCE or PCE communication mechanisms.

It is expected that PCE solutions will address these issues in detail

Additionally, certain confidentiality issues may arise where domains
desire to keep private their topology or optimal paths. For example,
when LSPs traverse networks maintained by different SPs. PCE solutions
in these cases are expected to provide suitable confidentiality.

6. Acknowledgments

The authors would like to thank JP Vasseur for many helpful comments and

7. Normative References

[ccamp_fw] Farrel, A., et. al., "A Framework for Inter-Domain MPLS
Traffic Engineering," work in progress.

[inter-as-req] Zhang, R, Vasseur, JP, et. al., "MPLS Inter-AS Traffic
Engineering requirements", work in progress.

[inter-area-req] Le Roux, JL, et. al., "Requirements for Inter-area MPLS
Traffic Engineering," work in progress.

8. Informational References

[kompella] Kompella, K., et. al., Rekhter, Y., Vasseur, JP, "Multi-area
MPLS Traffic Engineering," work in progress.

[lee] Lee, C-Y, et. al., "Distributed Route Exchangers," work in

[query] Lee, C-Y, Ganti, S., "Path Request and Path Reply Message,"
work in progress.

[vasseur1] Vasseur, JP, "RSVP Path Computation Request and Reply
Messages," work in progress.

[vasseur2] Vasseur, JP, et. al., "Inter-area and Inter-AS MPLS Traffic
Engineering," work in progress.

9. Authors' Addresses

Jerry Ash  (editor)
Room MT D5-2A01
200 Laurel Avenue
Middletown, NJ 07748, USA
Phone: +1-(732)-420-4578
Fax:   +1-(732)-368-8659

Adrian Farrel
Old Dog Consulting
Phone: +44 (0) 1978 860944

10. Intellectual Property Considerations

The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in this
document or the extent to which any license under such rights might or
might not be available; nor does it represent that it has made any
independent effort to identify any such rights. Information on the
procedures with respect to rights in RFC documents can be found in BCP
78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an attempt
made to obtain a general license or permission for the use of such
proprietary rights by implementers or users of this specification can be
obtained from the IETF on-line IPR repository at

The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary rights
that may cover technology that may be required to implement this
standard. Please address the information to the IETF at

10.1. IPR Disclosure Acknowledgement

By submitting this Internet-Draft, I certify that any applicable patent
or other IPR claims of which I am aware have been disclosed, and any of
which I become aware will be disclosed, in accordance with RFC 3668.

11. Full Copyright Statement

Copyright (C) The Internet Society (2004). This document is subject to
the rights, licenses and restrictions contained in BCP 78, and except as
set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an