PCE Working Group Z. Ali
T. Saad
Internet Draft Cisco Systems, Inc.
Kenji Kumaki
KDDI R&D Labs
Intended status: Standard Track July 12, 2009
Expires: January 11, 2010
BRPC Extensions for Point-to-Multipoint Path Computation
draft-ali-pce-brpc-p2mp-ext-01.txt
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance
with the provisions of BCP 78 and BCP 79. This document may
contain material from IETF Documents or IETF Contributions
published or made publicly available before November 10,
2008. The person(s) controlling the copyright in some of
this material may not have granted the IETF Trust the right
to allow modifications of such material outside the IETF
Standards Process. Without obtaining an adequate license
from the person(s) controlling the copyright in such
materials, this document may not be modified outside the
IETF Standards Process, and derivative works of it may not
be created outside the IETF Standards Process, except to
format it for publication as an RFC or to translate it into
languages other than English.
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.
This Internet-Draft will expire on September 03, 2009.
Expires January 2010 [Page 1]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
Abstract
The ability to compute constrained Traffic Engineering Label
Switched Paths (TE LSPs) for point-to-multipoint (P2MP) LSPs
in Multiprotocol Label Switching (MPLS) and Generalized MPLS
(GMPLS) networks across multiple domains (where a domain is
a collection of network elements within a common sphere of
address management or path computational responsibility such
as an IGP area or an Autonomous Systems) has been identified
as a key requirement [PCEP-P2MP-REQ]. This document addresses
this requirement by extending backward recursive path
computation (BRPC) technique proposed for Point-to-Point
(P2P) LSPs in [P2P-BRPC] for P2MP LSP path computation in a
multiple domains network.
Conventions used in this document
In examples, "C:" and "S:" indicate lines sent by the client
and server respectively.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY",
and "OPTIONAL" in this document are to be interpreted as
described in RFC-2119 0.
Table of Contents
1. Introduction...............................................3
2. Terminology................................................4
3. General Assumptions........................................5
4. Extension to BRPC Procedure for Path Computation for P2MP
LSP...........................................................5
4.1. Definition of X-VSPT(i)...............................5
4.2. Definition of X-VSPT(i, d)............................6
4.3. P2MP-BRPC procedure...................................6
4.4. P2MP-BRPC Procedure Completion Failure................8
4.5. Example...............................................8
5. VSPT Encoding..............................................9
Expires January 2010 [Page 2]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
6. IANA Considerations........................................9
7. Security Considerations....................................9
8. References.................................................9
8.1. Normative References..................................9
8.2. Informative References................................9
Author's Addresses...........................................10
1. Introduction
The ability to compute constrained Traffic Engineering Label
Switched Paths (TE LSPs) for point-to-multipoint (P2MP) LSPs
in Multiprotocol Label Switching (MPLS) and Generalized MPLS
(GMPLS) networks across multiple domains (where a domain is
a collection of network elements within a common sphere of
address management or path computational responsibility such
as an IGP area or an Autonomous Systems) has been identified
as a key requirement [PCEP-P2MP-REQ]. [P2P-BRPC] specifies a
procedure for inter-domain shortest constrained paths
computation for point-to-point (P2P) LSPs, using backward
recursive path computation (BRPC) technique. This draft
extends the technique specified in [P2P-BRPC] for P2MP LSP
path computation. Just like [P2P-BRPC], its P2MP-TE
extension preserves confidentiality across domains, which is
sometimes required when domains are managed by different
Service Providers.
A P2MP tree is a graphical representation of all TE links
that are committed for a particular P2MP LSP. In other
words, a P2MP tree is a representation of the corresponding
tunnel on the TE network topology. A sub-tree is a part of
the P2MP tree describing how the root or an intermediate
P2MP LSPs minimizes packet duplication when P2P TE sub-LSPs
traverse common links. The computation of a P2MP tree
requires three major pieces of information. The first is the
path from the ingress LSR of a P2MP LSP to each of the
egress LSRs, the second is the traffic engineering related
parameters, and the third is the branch capability
information.
Generally, inter-domain P2MP tree (i.e. whose source and
destinations of the P2MP LSP reside in a multiple different
domains) is particularly difficult to compute even for a
distributed PCE architecture. For instance, while the BRPC
recursive path computation may be well-suited for P2P paths,
P2MP path computation involves multiple branching path
segments from the source to the multiple destinations. As
such, inter-domain P2MP path computation may result in a
plurality of per-domain path options that may be difficult
to coordinate efficiently and effectively between domains.
That is, when one or more domains have a multiple ingress
and/or egress border nodes, there is currently no known
technique for one domain to determine which border routers
another domain will utilize for the inter-domain P2MP tree,
Expires January 2010 [Page 3]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
and to limit the computation of the P2MP tree to those
utilized border nodes.
A trivial solution to computation of inter-domain P2MP tree
would be to compute shortest inter-domain P2P paths from
source to each destination and then combine them to generate
an inter-domain Steiner P2MP tree. This, however, may
require replication of incoming packets to all the P2P LSPs
at the ingress PE to accommodate multipoint communication.
Obviously, this solution is very inefficient for a couple of
reasons. First, it places more replication burden on the
ingress PE and hence has poor scaling characteristics, and
second it does not make use of bandwidth sharing when one or
more S2L LSPs share links along their paths, hence wasting
bandwidth resources, memory and MPLS label space in the
network.
Apart from path computation difficulties faced due to the
inter-domain topology visibility issues, the computation of
the minimum P2MP Steiner tree, i.e. one which guarantees the
least cost resulting tree, is an NP-complete problem.
Moreover, adding and/or removing a single destination
to/from the tree may result in an entirely different tree.
In this case, the frequent Steiner tree computation process
may prove computationally intensive, and the resulting
frequent tunnel reconfiguration may even cause network
destabilization. There are several heuristic algorithms
presented in the literature that approximate the result
within polynomial time that are applicable within the
context of a single-domain. This draft extends the technique
specified in [P2P-BRPC] for P2MP LSP path computation in an
inter-domain environment using PCE [RFC4655].
2. Terminology
This document borrows terminology from [P2P-BRPC], which is
repeated here for quick reference.
ABR: Area Border Routers. Routers used to connect two IGP
areas (areas in OSPF or levels in IS-IS).
ASBR: Autonomous System Border Routers. Routers used to
connect together ASes of the same or different Service
Providers via one or more Inter-AS links.
Boundary Node (BN): a boundary node is either an ABR in the
context of inter-area Traffic Engineering or an ASBR in the
context of inter-AS Traffic Engineering.
Entry BN of domain(n): a BN connecting domain(n-1) to
domain(n) along a determined sequence of domains.
Expires January 2010 [Page 4]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
Exit BN of domain(n): a BN connecting domain(n) to
domain(n+1) along a determined sequence of domains.
Inter-AS TE LSP: A TE LSP that crosses an AS boundary.
Inter-area TE LSP: A TE LSP that crosses an IGP area
boundary.
LSR: Label Switching Router.
LSP: Label Switched Path.
PCC: Path Computation Client. Any client application
requesting a path computation to be performed by the Path
Computation Element.
PCE (Path Computation Element): an entity (component,
application or network node) that is capable of computing a
network path or route based on a network graph and applying
computational constraints.
PCE(i) is a PCE with the scope of domain(i).
TED: Traffic Engineering Database.
VSPT: Virtual Shortest Path Tree.
X-VSPT: Extended Virtual Shortest Path Tree.
3. General Assumptions
This document makes the same assumptions as outlined in
[P2P-BRPC] and will not be repeated here.
4. Extension to BRPC Procedure for Path Computation for P2MP LSP
This section describes the extension to BRPC procedure defined
in [P2P-BRPC]. It also details procedure on how extended BRPC
can be used for path computation of a P2MP LSP.
4.1. Definition of X-VSPT(i)
Definition of X-VSPT(i) is similar to definition of VSPT(i)
in [P2P-BRPC], with a few exceptions outlined in the
following.
In the case of computation of VSPT(i), PCE(i) only considers
the entry BNs of domain(i). That is only the BNs that
provide connectivity from domain(i-1). This works well in
P2P case as there is only one destination and there is no
added value in knowing connectivity from BNs that do not
Expires January 2010 [Page 5]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
provide connectivity from domain(i-1). However, for the case
of P2MP tree path computation, and since there is usually
more than one destination per P2MP LSP (some residing in
different destination domains) knowing the connectivity from
BNs that are not connected with domain(i-1) is useful.
Specifically, it improves the ability of the ingress PCE to
compute lower cost P2MP trees by favoring paths for new
destination that branch off existing sub-tree as opposed to
shortest end-to-end P2P path from source to destination. The
set of BN-ex of domain remains the same as defined in [P2P-
BRPC].
X-VSPT(i) is defined as follows-
In each domain (i),
o There is a set of X-en(i) all entry BNs, such that BN-
en(k,i) is the kth entry BN of domain(i).
o There is a set of Y-ex(i) exit BNs, such that BN-
ex(k,i) is the kth exit BN of domain(i).
VSPT(i), as defined in [P2P-BRPC], for P2P LSP is a tree
that provides a list of shortest paths from BN-en(1,i), BN-
en(2,i), ... BN-en(j,i) to destination such that j <= [X-
en(i)], where [X-en(i)] is the number of entry BNs in
domain(i).
The X-VSPT(i), in addition to VSPT(i), includes shortest
paths from the BN-en(k,i) to all BN-ex(i), such that k is
the BN that is along the shortest path to destination, and
BN-ex(i) is an exit BN in domain (i). Nonetheless, the X-
VSPT(i) may exclude some BN-ex(i) according to policy
constraints (either due to local policy or policies signaled
in the path computation request). Also, when more than one
BN-ex(i) connect to the same neighboring domain (domain
(i+1)), the X-VSPT(i) only includes the BN-ex along the
least cost path to domain (i+1). In the presence of inter-AS
link, the X-VSPT includes the path of the inter-AS TE links
connecting domain(i) to domain(i+1).
For destination domain, the X-VSPT(i) includes shortest
paths from the destination node to the set of BN-ex nodes.
4.2. Definition of X-VSPT(i, d)
X-VSPT(i, d) is defined as X-VSPT at domain(i) to reach
destination d of a P2MP tree.
4.3. P2MP-BRPC procedure
In the following we outline steps of the P2MP-BRPC
procedure.
Expires January 2010 [Page 6]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
Given a set of destinations D = 1, 2, ... d, where |D| is
the total number of destinations in the P2MP LSP. This
draft assumes that the ingress PCE, PCE(1), has a mechanism
to determine the set of PCEs (i.e. PCE-chain) to be
traversed for the computation of the inter-domain path on
per destination basis. The said mechanism is outside the
scope of this document.
Note, it is possible for the ingress PCE, PCE(1), to request
path computation for destinations sequentially (one-by-one),
or simultaneously (in-parallel). In the former case, the
computation burden in P2MP-BRPC can be further reduced.
PCE(1) can include the P2MP sub-tree(d-1), which includes X-
VSPT(1, 1), X-VSPT(1, 2), ..., X-VSPT(1, d-1), i.e. that
for destinations up to (d-1), in the PCE request for
destination (d). By doing so, it is possible for PCE(n^d, d)
to immediately compute a best path for (d) by computing a
path from (d) to the closest branching node within the P2MP
sub-tree(d-1). However, in this version of the draft only
parallel requests for computation of XVSPT(n^d, d) for d =
1, 2, . . . D are considered.
Denote by PCE(n^d, d) the PCE in the destination domain(n)
of destination (d). A PCC discovers a PCE, PCE(1), that is
capable of serving its path computation request and forwards
to it the P2MP path computation request.
PCE(1) will then iteratively send P2MP path requests to all
destinations d = 1, 2, ... D, in the P2MP tree, as follows:
Start of iteration(d):
Step (1, d): PCE(1) forwards the P2MP path computation
Request such that it traveses a set of PCE(s) until it
reaches PCE(n^d, d).
Step (2, d): PCE(n^d, d) computes X-VSPT(n^d, d) by
including, in addition to VSPT(i), constraints shortest
paths from the destination node (d) to all exit BNs BN-
ex(i), as described earlier. When multiple BN-ex(n^d)
connect to the same neighboring domain (domain (n^d +1)),
the X-VSPT(n^d) only includes the BN-ex along the least
cost path to domain (n^d +1). In the presence of inter-AS
link, the X-VSPT includes the path of the inter-AS TE
links connecting domain(n^d) to domain(n^d+1).
Step (3, d): X-VSPT(n^d) is forwarded to PCE((n-1)^d,d).
According to [P2P-BRPC], PCE((n-1)^d) computes VSPT((n-
1)^d) by finding constrained shortest paths from all BN-
en((n-1)^d) to the destination (d) using VSPT((n)^d).
When this step is completed, only a sub-set of BN-
en((n)^d) are selected. At this point, PCE((n-1)^d,d) can
prune X-VSPT(n-1) to exclude those BN-en (and the
respective X-VSPT((n)^d) branches attached to them) that
were not considered in computation
Expires January 2010 [Page 7]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
of VSPT((n-1)^d), and the respective X-VSPT((n)^d)
branches attached to them.
PCE((n-1)^d,d) appends to VSPT((n-1)^d) the X-VSPT((n-
1)^d) by by finding constrained shortest paths from all
BN-en((n-1)^d) to all other BN-ex((n-1)^d). When multiple
BN-ex((n-1)^d) connect to the same neighboring domain,
the X-VSPT((n-1)^d) only includes the BN-ex along the
least cost path to that domain.
Step(i,d): the previous procedure is repeated PCE(i^d,d)
where i= n-1 ... 2.
End of iteration
When PCE(1) receives replies with X-VSPTs(2,d) for all
destinations, it forms a virtual graph composed of the
source node, BNs included in the X-VSPTs, and the
destinations. PCE(1) can then use a suitable heuristic to
compute a feasible P2MP tree.
Note, an X-VSPT(i, d) tree may be returned in the form of an
explicit path (in which case all the hops along the path
segment are listed) or a loose path (in which case only the
BN is specified) so as to preserve confidentiality along
with the respective cost. In the later case, various
techniques can be used in order to retrieve the computed
explicit paths on a per domain basis during the signaling
process thanks to the use of path keys as described in [I-
D.ietf-pce-path-key].
4.4. P2MP-BRPC Procedure Completion Failure
TBA in a later version of the document.
4.5. Example
TBA in a later version of the document.
5. PCEP Protocol Extensions
The X-BRPC procedure proposed in this document requires
the specification of a new flag of the RP object carried
within the PCReq message (defined in [PCEP]), as follows
X-VSPT Flag
Bit Number Name Flag
TBD X-VSPT
When set, the VSPT Flag indicates that the PCC requests
the computation of an inter-domain P2MP-TE TE LSP using the
X-BRPC procedure
Expires January 2010 [Page 8]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
defined in this document.
5.1 VSPT Encoding
Similar to the VSPT, the X-VSPT can be returned within a
PCRep message. The encoding may consist of non-ordered
lists of EROs where each ERO represents a path segment from
a entry BN to the exit BNs, or from destination to an exit
BN as described earlier in Section 4.3.
Encoding using SERO is to be considered in the later version
of this document.
6. IANA Considerations
A new flag of the RP object (specified in [PCEP]) is defined in
this document.
X-VSPT Flag
Bit Number Name Flag Reference
TBD X-VSPT This document.
7. Security Considerations
TBA in a later version of the document.
8. References
8.1. Normative References
[P2P-BRPC] JP. Vasseur, et al, A Backward Recursive PCE-based
Computation (BRPC) Procedure To Compute Shortest
Constrained Inter-domain Traffic Engineering Label
Switched Paths, draft-ietf-pce-brpc-09.txt,
work in progress.
[PCEP] Vasseur, JP., Ed. and JL. Le Roux, Ed., "Path
Computation Element (PCE) communication Protocol
(PCEP)", draft-ietf-pce-pcep, work in progress.
8.2. Informative References
[PCEP-P2MP-REQ] S. Yasukawa, A. Farrel," PCC-PCE
Communication Requirements for Point to Multipoint
Multiprotocol Label Switching Traffic Engineering
(MPLS TE)".
[RFC4655] Farrel, A., Vasseur, J., and J. Ash, "A Path
Computation Element (PCE)-Based Architecture", RFC 4655,
August 2006.
Expires January 2010 [Page 9]
Internet-Draft draft-ali-pce-brpc-p2mp-ext-01.txt
Author's Addresses
Zafar Ali
Cisco Systems, Inc.
Email: zali@cisco.com
Tarek Saad
Cisco Systems, Inc.
Email: tsaad@cisco.com
Kenji Kumaki
KDDI R&D Laboratories, Inc.
Email: ke-kumaki@kddi.com
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as
the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's
Legal Provisions Relating to IETF Documents in effect on the
date of publication of this document
(http://trustee.ietf.org/license-info). Please review these
documents carefully, as they describe your rights and
restrictions with respect to this document.
Legal
This documents and the information contained therein are provided
on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE
IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL
WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY
WARRANTY THAT THE USE OF THE INFORMATION THEREIN WILL NOT INFRINGE
ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS
FOR A PARTICULAR PURPOSE.
Expires January 2010 [Page 10]