idnits 2.17.1 draft-chen-pce-forward-search-p2p-path-computation-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 11, 2011) is 4672 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'RFC2119' is defined on line 539, but no explicit reference was found in the text == Unused Reference: 'RFC3209' is defined on line 542, but no explicit reference was found in the text == Unused Reference: 'RFC5440' is defined on line 546, but no explicit reference was found in the text == Unused Reference: 'RFC6006' is defined on line 550, but no explicit reference was found in the text == Unused Reference: 'RFC4655' is defined on line 558, but no explicit reference was found in the text == Unused Reference: 'RFC5862' is defined on line 561, but no explicit reference was found in the text ** Obsolete normative reference: RFC 6006 (Obsoleted by RFC 8306) Summary: 2 errors (**), 0 flaws (~~), 7 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force H. Chen 3 Internet-Draft Huawei Technologies 4 Intended status: Standards Track July 11, 2011 5 Expires: January 12, 2012 7 A Forward-Search P2P TE LSP Inter-Domain Path Computation 8 draft-chen-pce-forward-search-p2p-path-computation-01.txt 10 Abstract 12 This document presents a forward search procedure for computing 13 Point-to-Point (P2P) Traffic Engineering (TE) Label Switched Paths 14 (LSPs) crossing a number of domains through using multiple Path 15 Computation Elements (PCEs). In addition, extensions to the Path 16 Computation Element Communication Protocol (PCEP) for supporting the 17 forward search procedure are described. 19 Status of this Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on January 12, 2012. 36 Copyright Notice 38 Copyright (c) 2011 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 3. Conventions Used in This Document . . . . . . . . . . . . . . 4 56 4. Forward Search Path Computation . . . . . . . . . . . . . . . 4 57 4.1. Overview of Procedure . . . . . . . . . . . . . . . . . . 4 58 4.2. Description of Procedure . . . . . . . . . . . . . . . . . 6 59 4.3. Comparing to BRPC . . . . . . . . . . . . . . . . . . . . 8 60 5. Extensions to PCEP . . . . . . . . . . . . . . . . . . . . . . 8 61 5.1. RP Object Extension . . . . . . . . . . . . . . . . . . . 8 62 5.2. PCE Object . . . . . . . . . . . . . . . . . . . . . . . . 9 63 5.3. Node Flags Object . . . . . . . . . . . . . . . . . . . . 10 64 5.4. Candidate Node List Object . . . . . . . . . . . . . . . . 10 65 5.5. Request Message Extension . . . . . . . . . . . . . . . . 11 66 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 67 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 68 7.1. Request Parameter Bit Flags . . . . . . . . . . . . . . . 12 69 8. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 13 70 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 71 9.1. Normative References . . . . . . . . . . . . . . . . . . . 13 72 9.2. Informative References . . . . . . . . . . . . . . . . . . 13 73 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13 75 1. Introduction 77 Methods or procedures exist for computing MPLS TE P2P LSP inter- 78 domain paths. They include RFC 5152 "A Per-Domain Path Computation 79 Method for Establishing Inter-Domain Traffic Engineering (TE) Label 80 Switched Paths (LSPs)" and RFC 5441 "A Backward-Recursive PCE-Based 81 Computation (BRPC) Procedure to Compute Shortest Constrained Inter- 82 Domain Traffic Engineering Label Switched Paths". These methods or 83 procedures have some issues. 85 There are a few of issues with the Backward Recursive Path 86 Computation (BRPC) algorithm or procedure for computing an MPLS TE 87 P2P LSP path from a source node to a destination node crossing 88 multiple domains. These issues include: 90 The sequence of domains from the source node to the destination node 91 must be known in advance. 93 Navigating a mesh of domains may be complex. 95 More importantly, the BRPC procedure can not find the optimal path if 96 the optimal path is not in the sequence of domains from the source 97 node to the destination node. Thus the BRPC procedure can not 98 guarantee that the path crossing multiple domains computed by the 99 BRPC procedure is optimal. 101 This document presents a forward search procedure for computing 102 Point-to-Point (P2P) Traffic Engineering (TE) Label Switched Paths 103 (LSPs) crossing a number of domains through using multiple Path 104 Computation Elements (PCEs). This procedure resolves the issues 105 mentioned above. It guarantees that the path found from the source 106 to the destination is optimal. It does not depend on any sequence of 107 domains from the source node to the destination node. Navigating a 108 mesh of domains is simple and efficient. 110 2. Terminology 112 ABR: Area Border Router. Routers used to connect two IGP areas 113 (areas in OSPF or levels in IS-IS). 115 ASBR: Autonomous System Border Router. Routers used to connect 116 together ASes of the same or different service providers via one or 117 more inter-AS links. 119 Boundary Node (BN): a boundary node is either an ABR in the context 120 of inter-area Traffic Engineering or an ASBR in the context of 121 inter-AS Traffic Engineering. 123 Entry BN of domain(n): a BN connecting domain(n-1) to domain(n) along 124 a determined sequence of domains. 126 Exit BN of domain(n): a BN connecting domain(n) to domain(n+1) along 127 a determined sequence of domains. 129 Inter-area TE LSP: A TE LSP that crosses an IGP area boundary. 131 Inter-AS TE LSP: A TE LSP that crosses an AS boundary. 133 LSP: Label Switched Path. 135 LSR: Label Switching Router. 137 PCC: Path Computation Client. Any client application requesting a 138 path computation to be performed by a Path Computation Element. 140 PCE: Path Computation Element. An entity (component, application, or 141 network node) that is capable of computing a network path or route 142 based on a network graph and applying computational constraints. 144 PCE(i) is a PCE with the scope of domain(i). 146 TED: Traffic Engineering Database. 148 This document uses terminologies defined in RFC5440. 150 3. Conventions Used in This Document 152 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 153 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 154 document are to be interpreted as described in RFC2119. 156 4. Forward Search Path Computation 158 This section gives an overview of the forward search path computation 159 procedure and describes the procedure in details. 161 4.1. Overview of Procedure 163 Simply speaking, the idea of the forward search path computation 164 procedure for computing a path for an MPLS TE P2P LSP crossing 165 multiple domains from a source node to a destination node includes: 167 Start from the source node and the source domain. 169 Consider the optimal path segment from the source node to every exit 170 boundary node of the source domain as a special link; 172 Consider the optimal path segment from an entry boundary node to 173 every exit boundary node of a domain as a special link; and the 174 optimal path segment is computed as needed. 176 The whole topology consisting of many domains can be considered as a 177 special topology, which contains those special links, the normal 178 links in the destination domain and the inter-domain links. 180 Compute an optimal path in this special topology from the source node 181 to the destination node using CSPF. 183 The forward search path computation procedure for computing a path 184 for an MPLS TE P2P LSP starts at the source domain, in which the 185 source (or ingress) node of the MPLS TE LSP locates. When a PCE in 186 the source domain receives a PCReq for the path for the MPLS TE LSP, 187 it computes the optimal path from the source node to every exit 188 boundary node of the domain towards the destination node. 190 There are two lists involved in the path computation. One list is 191 called candidate node list, which contains the nodes with brief 192 information about the temporary optimal paths from the source node to 193 each of these nodes currently found. The nodes in the candidate list 194 are ordered by the cost of the path. Initially, the candidate node 195 list contains only source node with cost 0. 197 The other is called result path list or tree, which contains the 198 final optimal paths from the source node to the boundary nodes or the 199 nodes in the destination domain. Initially, the result path list is 200 empty. 202 When a PCE responsible for a domain (called current domain) receives 203 a PCReq for computing the path for the MPLS TE LSP, it removes the 204 node with the minimum cost from the candidate node list and put or 205 graft the node to the result path list or tree. 207 If the destination node is in the current domain, the PCE computes 208 the optimal path from the source node to the destination node and 209 sends a PCRep with the optimal path to the PCE or PCC from which the 210 PCReq is received. 212 Otherwise (i.e., if the destination is not in the domain), the PCE 213 computes the optimal path from the source node to every exit boundary 214 node of the current domain towards the destination node and further 215 to the entry boundary nodes of the domain connected to the current 216 domain, puts the new node into the candidate list in order by path 217 cost, updates the existing node in the candidate node list with the 218 new node with lower cost, and then sends a PCReq with the new 219 candidate node list to the PCE that is responsible for the domain 220 with the first node in the candidate node list. 222 4.2. Description of Procedure 224 Suppose that we have the following variables: 226 A current PCE named as CurrentPCE which is currently computing the 227 path. 229 A candidate node list named as CandidateNodeList, which contains the 230 nodes to each of which the temporary optimal path from the source 231 node is currently found. The information about each node C in 232 CandidateNodeList consists of 234 the cost of the path from the source node to node C, 236 the previous hop node P and the link between P and C, 238 the PCE responsible for C, and 240 the flags for C. The flags include 242 one bit D indicating that node C is a Destination node if it is set; 244 one bit S indicating that C is the Source node if it is set; 246 one bit E indicating that C is an Exit boundary node if it is set; 248 one bit I indicating that C is an entry boundary node if it is set; 249 and 251 one bit N indicating that C is a Node in the destination domain if it 252 is set. 254 The nodes in CandidateNodeList are ordered by path cost. Initially, 255 CandidateNodeList contains only a Source Node, with path cost 0, PCE 256 responsible for the source domain, and flags with S bit set. 258 A result path list or tree named as ResultPathTree, which contains 259 the final optimal paths from the source node to the boundary nodes or 260 the nodes in the destination domain. Initially, ResultPathTree is 261 empty. 263 The Forward Search Path Computation procedure for computing the path 264 for the MPLS TE P2P LSP is described as follows: 266 Initially, a PCC sets ResultPathTree to empty and CandidateNodeList 267 to contain the source node and sends PCE responsible for the source 268 domain a PCReq with the source node, the destination node, 269 CandidateNodeList and ResultPathTree. 271 When the PCE responsible for a domain (called current domain) 272 receives a request for computing the path for the MPLS TE P2MP LSP, 273 it checks whether the current PCE is the PCE responsible for the node 274 C with the minimum cost in the CandidateNodeList. If it is, then 275 remove C from CandidateNodeList and graft it into ResultPathTree; 276 otherwise, a PCReq message is sent to the PCE for node C. 278 Suppose that node C has Flags. The ResultPathTree is built from C in 279 the following steps. 281 If the D (Destination Node) bit in the Flags is set, then the optimal 282 path from the source node to the destination node is found, and a 283 PCRep message with the path is sent to the PCE/PCC which sends the 284 request to the current PCE. 286 If the N (Node in Destination domain) bit in the Flags is set, then 287 for every node N connected to node C and not on ResultPathTree, it is 288 merged into CandidateNodeList. The cost to node N is the sum of the 289 cost to node C and the cost of the link between C and N. The PCE for 290 node N is the current PCE. 292 If the Entry/Incoming Boundary Node (I) bit or the Source Node (S) 293 bit is set), then path segments from node C to every exit boundary 294 node of the current domain that is not on the result path tree are 295 computed through using CSPF and as special links. For every node N 296 connected to node C through a special link (i.e., a path segment), it 297 is merged into CandidateNodeList. The cost to node N is the sum of 298 the cost to node C and the cost of the special link (i.e., path 299 segment ) between C and N. The PCE for node N is the current PCE. 301 If the Exit Boundary Node (E) bit is set and there exist inter-domain 302 links connected to it, then for every node N connected to C and not 303 on the result path tree, it is merged into the candidate node list. 304 The cost to node N is the sum of the cost to node C and the cost of 305 the link between C and N. The PCE for node N is the PCE responsible 306 for node N. 308 If the CurrentPCE is the same as the PCE of the node with the minimum 309 cost in CandidateNodeList, then the node is removed from 310 CandidateNodeList, grafted to ResultPathTree, and the above steps are 311 repeated; otherwise, the CurrentPCE sends the PCE a request with the 312 source node, CandidateNodeList and ResultPathTree. 314 4.3. Comparing to BRPC 316 RFC 5441 describes the Backward Recursive Path Computation (BRPC) 317 algorithm or procedure for computing an MPLS TE P2P LSP path from a 318 source node to a destination node crossing multiple domains. 319 Comparing to BRPC, there are a number of differences between BRPC and 320 the Forward-Search P2P TE LSP Inter-Domain Path Computation. Some of 321 the differences are briefed below. 323 First, for BRPC to compute a shortest path from a source node to a 324 destination node crossing multiple domains, we MUST provide a 325 sequence of domains from the source node to the destination node to 326 BRPC in advance. The Forward-Search P2P TE LSP Inter-Domain Path 327 Computation does not need any sequence of domains for computing a 328 shortest path. 330 Secondly, for a given sequence of domains domain(1), domain(2), ... , 331 domain(n), BRPC searches the shortest path from domain(n), to 332 domain(n-1), until domain(1) along the reverse order of the given 333 sequence of domain. It will get the shortest path within the given 334 domain sesuence. The Forward-Search P2P TE LSP Inter-Domain Path 335 Computation calculates an optimal path in a special topology from the 336 source node to the destination node using CSPF. It will find the 337 shortest path within all the domains. 339 Moreover, if the sequence of domains from the source node to the 340 destination node provided to BRPC does not contain the shortest path 341 from the source to the destionation, then the path computed by BRPC 342 is not optimal. The Forward-Search P2P TE LSP Inter-Domain Path 343 Computation guarantees that the path found is optimal. 345 5. Extensions to PCEP 347 This section describes the extensions to PCEP for Forward Search Path 348 Computation. The extensions include the definition of a new flag in 349 the RP object, a result path list and a candidate node list in the 350 PCReq message. 352 5.1. RP Object Extension 354 The following flag is added into the RP Object: 356 The F bit is added in the flag bits field of the RP object to tell 357 the receiver of the message that the request/reply is for Forward 358 Search Path Computation. 360 o F (Forward search Path Computation bit - 1 bit): 362 0: This indicates that this is not PCReq/PCRep 363 for Forward Search Path Computation. 365 1: This indicates that this is PCReq or PCRep message 366 for Forward Search Path Computation. 368 The IANA request is referenced in Section below (Request Parameter 369 Bit Flags) of this document. 371 This F bit with the N bit defined in RFC6006 can indicate whether the 372 request/reply is for Forward Search Path Computation of an MPLS TE 373 P2P LSP or an MPLS TE P2MP LSP. 375 o F = 1 and N = 0: This indicates that this is a PCReq/PCRep 376 message for Forward Search Path Computation 377 of an MPLS TE P2P LSP. 379 o F = 1 and N = 1: This indicates that this is a PCReq/PCRep 380 message for Forward Search Path Computation 381 of an MPLS TE P2MP LSP. 383 5.2. PCE Object 385 The figure below illustrates a PCE IPv4 object body (Object-Type=2), 386 which comprises a PCE IPv4 address. The PCE IPv4 address object 387 indicates the IPv4 address of a PCE , with which a PCE session may be 388 established and to which a request message may be sent. 390 0 1 2 3 391 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 392 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 393 | PCE IPv4 address | 394 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 396 Figure 1: PCE Object Body for IPv4 398 The format of the PCE object body for IPv6 (Object-Type=2) is as 399 follows: 401 0 1 2 3 402 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 | | 405 | PCE IPv6 address (16 bytes) | 406 | | 407 | | 408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 410 Figure 2: PCE Object Body for IPv6 412 5.3. Node Flags Object 414 The Node Flags object is used to indicate the characteristics of the 415 node in a candidate node list in a request or reply message for 416 Forward Search Inter-domain Path Computation. The Node Flags object 417 comprises a Reserved field, and a number of Flags. 419 The format of the Node Flags object body is as follows: 421 0 1 2 3 422 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 424 |D|S|I|E|N| Flags | Reserved | 425 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 427 Figure 3: Node Flags Object Body 429 where 431 o D = 1: The node is a destination node. 432 o S = 1: The node is a source node. 433 o I = 1: The node is an entry boundary node. 434 o E = 1: The node is an exit boundary node. 435 o N = 1: The node is a node in a destination domain. 437 5.4. Candidate Node List Object 439 The candidate-node-list-obj object contains the nodes in the 440 candidate node list. A new PCEP object class and type are requested 441 for it. The format of the candidate-node-list-obj object body is as 442 follows: 444 0 1 2 3 445 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 | | 448 // (a list of s) // 449 | | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 Figure 4: Candidate Node List Object 454 The following is the definition of candidate node list, which may 455 contain Node Flags. 457 ::= 458 [] 459 ::= 460 462 ::= [] 463 [] 464 [] 466 The ERO in a candidate node contain just the path segment of the last 467 link of the path, which is from the previous hop node of the tail end 468 node of the path to the tail end node. With this information, we can 469 graft the candidate node into the existing result path list or tree. 471 Simply speaking, a candidate node has the same or similar format of a 472 path defined in RFC 5440, but the ERO in the candidate node just 473 contain the tail end node of the path and its previous hop, and the 474 candidate path may contain two new objects PCE and node flags. 476 5.5. Request Message Extension 478 Below is the message format for a request message with the extension 479 of a result path list and a candidate node list: 481 ::= 482 [] 483 484 ::=[] 485 ::= 486 487 [] 488 [] 489 [] 490 [] 491 [[]] 492 [] 493 [] 494 [] 495 [] 497 where: 498 ::=[] 499 ::= 500 ::=[] 501 [] 502 [] 503 [] 505 contains a 507 The definition for the result path list that may be added into a 508 request message is the same as that for the path list in a reply 509 message that is described in RFC5440. 511 6. Security Considerations 513 The mechanism described in this document does not raise any new 514 security issues for the PCEP protocols. 516 7. IANA Considerations 518 This section specifies requests for IANA allocation. 520 7.1. Request Parameter Bit Flags 522 A new RP Object Flag has been defined in this document. IANA is 523 requested to make the following allocation from the "PCEP RP Object 524 Flag Field" Sub-Registry: 526 Bit Description Reference 528 18 Forward Path Computation (F-bit) This I-D 530 8. Acknowledgement 532 The author would like to thank Julien Meuric and others for their 533 valuable comments on this draft. 535 9. References 537 9.1. Normative References 539 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 540 Requirement Levels", BCP 14, RFC 2119, March 1997. 542 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 543 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 544 Tunnels", RFC 3209, December 2001. 546 [RFC5440] Vasseur, JP. and JL. Le Roux, "Path Computation Element 547 (PCE) Communication Protocol (PCEP)", RFC 5440, 548 March 2009. 550 [RFC6006] Zhao, Q., King, D., Verhaeghe, F., Takeda, T., Ali, Z., 551 and J. Meuric, "Extensions to the Path Computation Element 552 Communication Protocol (PCEP) for Point-to-Multipoint 553 Traffic Engineering Label Switched Paths", RFC 6006, 554 September 2010. 556 9.2. Informative References 558 [RFC4655] Farrel, A., Vasseur, J., and J. Ash, "A Path Computation 559 Element (PCE)-Based Architecture", RFC 4655, August 2006. 561 [RFC5862] Yasukawa, S. and A. Farrel, "Path Computation Clients 562 (PCC) - Path Computation Element (PCE) Requirements for 563 Point-to-Multipoint MPLS-TE", RFC 5862, June 2010. 565 Author's Address 567 Huaimo Chen 568 Huawei Technologies 569 Boston, MA 570 USA 572 Email: Huaimochen@huawei.com