[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Internet Engineering Task Force                                  H. Chen
Internet-Draft                                       Huawei Technologies
Intended status: Standards Track                           March 7, 2011
Expires: September 8, 2011


      A Fordward-Search P2MP TE LSP Inter-Domain Path Computation
             draft-chen-pce-forward-search-p2mp-path-00.txt

Abstract

   This document presents a forward search procedure for computing
   Point-to-MultiPoint (P2MP) Traffic Engineering (TE) Label Switched
   Paths (LSPs) crossing a number of domains through using multiple Path
   Computation Elements (PCEs).  In addition, extensions to the Path
   Computation Element Communication Protocol (PCEP) for supporting the
   forward search procedure are described.

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on September 8, 2011.

Copyright Notice

   Copyright (c) 2011 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
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as



Chen                    Expires September 8, 2011               [Page 1]


Internet-Draft          Forward Search P2MP Path              March 2011


   described in the Simplified BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  Conventions Used in This Document  . . . . . . . . . . . . . .  4
   4.  Forward Search P2MP Path Computation . . . . . . . . . . . . .  4
     4.1.  Overview of Procedure  . . . . . . . . . . . . . . . . . .  4
     4.2.  Description of Procedure . . . . . . . . . . . . . . . . .  5
   5.  Extensions to PCEP . . . . . . . . . . . . . . . . . . . . . .  7
     5.1.  RP Object Extension  . . . . . . . . . . . . . . . . . . .  7
     5.2.  PCE Object . . . . . . . . . . . . . . . . . . . . . . . .  8
     5.3.  Candidate Node List Object . . . . . . . . . . . . . . . .  8
     5.4.  Node Flags Object  . . . . . . . . . . . . . . . . . . . .  9
     5.5.  Rest Destination Nodes Object  . . . . . . . . . . . . . . 10
     5.6.  Request Message Extension  . . . . . . . . . . . . . . . . 10
   6.  Security  Considerations . . . . . . . . . . . . . . . . . . . 11
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 12
     7.1.  Request Parameter Bit Flags  . . . . . . . . . . . . . . . 12
   8.  Acknowledgement  . . . . . . . . . . . . . . . . . . . . . . . 12
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 12
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 13
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13

























Chen                    Expires September 8, 2011               [Page 2]


Internet-Draft          Forward Search P2MP Path              March 2011


1.  Introduction

   This document describes a new method called "Forward Search Shortest
   P2MP LSP Path Crossing Domains".  The major characteristics of this
   method for computing an MPLS TE P2MP LSP path from a source node to a
   number of destination nodes crossing multiple domains include the
   following three ones.

   (1) It guarantees that the path computed from the source node to the
   destination nodes is shortest.

   (2) It does not depend on any domain path tree or domain sequences
   from the source node to the destination nodes.

   (3) Navigating a mesh of domains is simple and efficient.


2.  Terminology

   ABR: Area Border Router.  Routers used to connect two IGP areas
   (areas in OSPF or levels in IS-IS).

   ASBR: Autonomous System Border Router.  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.

   Exit BN of domain(n): a BN connecting domain(n) to domain(n+1) along
   a determined sequence of domains.

   Inter-area TE LSP: A TE LSP that crosses an IGP area boundary.

   Inter-AS TE LSP: A TE LSP that crosses an AS boundary.

   LSP: Label Switched Path.

   LSR: Label Switching Router.

   PCC: Path Computation Client.  Any client application requesting a
   path computation to be performed by a Path Computation Element.

   PCE: Path Computation Element.  An entity (component, application, or



Chen                    Expires September 8, 2011               [Page 3]


Internet-Draft          Forward Search P2MP Path              March 2011


   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.

   This document uses terminologies defined in RFC5440.


3.  Conventions Used in This Document

   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 RFC2119.


4.  Forward Search P2MP Path Computation

   This section gives an overview of the forward search P2MP path
   computation procedure and describes the procedure in details.

4.1.  Overview of Procedure

   Simply speaking, the idea of the Forward Search P2MP inter-domain
   path computation method for computing a path for an MPLS TE P2MP LSP
   crossing multiple domains from a source node to a number of
   destination nodes includes:

   Start from the source node and the source domain.

   Consider the optimal path segment from the source node to every exit
   boundary node of the source domain as a special link;

   Consider the optimal path segment from an entry boundary node to
   every exit boundary node of a domain as a special link; and the
   optimal path segment is computed as needed.

   The whole topology consisting of many domains can be considered as a
   special topology, which contains those special links, the normal
   links in the destination domains and the inter-domain links.

   Compute a shortest path in this special topology from the source node
   to the multiple destination nodes using CSPF.

   Forward Search P2MP inter-domain path computation method running at
   any PCE just grows the result path list/tree in the same way as
   normal CSPF on the special topology.  When the result path list/tree



Chen                    Expires September 8, 2011               [Page 4]


Internet-Draft          Forward Search P2MP Path              March 2011


   reaches all the destination nodes, the shortest path from the source
   node to the destination nodes is found and a PCRep message with the
   shortest path is sent to the PCE/PCC that sends the PCReq message
   eventually.

4.2.  Description of Procedure

   Suppose that we have the following variables:

   A current PCE named as CurrentPCE which is currently computing the
   path.

   A number of rest destination nodes named as RestDestinationNodes,
   which is the number of destination nodes to which shortest paths are
   to be found.  RestDestinationNodes is initially the number of all the
   destination nodes of an MPLS TE P2MP LSP.

   A candidate node list named as CandidateNodeList, which contains the
   nodes through which the shortest path from the source node to a
   destination node may be.  Each node C in CandidateNodeList has the
   following information:

   the cost of the path from the source node to node C,

   the previous hop node P and the link between P and C,

   the PCE responsible for C, and

   the flags for C. The flags include:

   one bit D indicating that node C is a Destination node if it is set;

   one bit S indicating that C is the Source node if it is set;

   one bit E indicating that C is an Exit boundary node if it is set;

   one bit I indicating that C is an entry boundary node if it is set;
   and

   one bit N indicating that C is a Node in the destination domains if
   it is set.

   The nodes in CandidateNodeList are ordered by path cost.  Initially,
   CandidateNodeList contains only a Source Node, with path cost 0, PCE
   responsible for the source domain, and flags with S bit set.

   A result path list or tree named as ResultPathTree, which contains
   the shortest paths from the source node to the boundary nodes or the



Chen                    Expires September 8, 2011               [Page 5]


Internet-Draft          Forward Search P2MP Path              March 2011


   nodes in the destination domains.  Initially, ResultPathTree is
   empty.

   The Forward Search path computation method for computing a path for
   an MPLS TE P2MP LSP crossing a number of domains from a source node
   to a number of destination nodes can be described as follows:

   Initially, a PCC sets RestDestinationNodes to the number of all the
   destination nodes of the MPLS TE P2MP LSP, ResultPathTree to empty
   and CandidateNodeList to contain the source node and sends a PCE
   responsible for the source domain a request with the source node,
   RestDestinationNodes, CandidateNodeList and ResultPathTree.

   When the PCE responsible for a domain (called current domain)
   receives a request for computing the path for the MPLS TE P2MP LSP,
   it checks whether the current PCE is the PCE responsible for the node
   C with the minimum cost in the CandidateNodeList.  If it is, then
   remove C from CandidateNodeList and graft it into ResultPathTree;
   otherwise, a PCReq message is sent to the PCE for node C.

   Suppose that node C has Flags.  The ResultPathTree is built from C in
   the following steps.

   If node C is a destination node (i.e., the Destination Node (D) bit
   in the Flags is set), then RestDestinationNodes is decreased by one.
   If RestDestinationNodes is zero (i.e., all the destinations are on
   the result path tree), then the shortest path is found and a PCRep
   message with the path is sent to the PCE/PCC which sends the request
   to the current PCE.

   If node C is in the destination domain (i.e., the Node in Destination
   domain (N) bit in the Flags is set), then for every node N connected
   to node C and not on ResultPathTree, it is merged into
   CandidateNodeList.  The cost to node N is the sum of the cost to node
   C and the cost of the link between C and N. The PCE for node N is the
   current PCE.

   If node C is an Entry Boundary Node or Source Node (i.e., the Entry/
   Incoming Boundary Node (I) bit or the Source Node (S) bit is set),
   then path segments from node C to every exit boundary node of the
   current domain that is not on the result path tree are computed
   through using CSPF and as special links.  For every node N connected
   to node C through a special link (i.e., a path segment), it is merged
   into CandidateNodeList.  The cost to node N is the sum of the cost to
   node C and the cost of the special link (i.e., path segment) between
   C and N. The PCE for node N is the current PCE.

   If node C is an Exit Boundary Node (i.e., the Exit Boundary Node (E)



Chen                    Expires September 8, 2011               [Page 6]


Internet-Draft          Forward Search P2MP Path              March 2011


   bit is set) and there exist inter-domain links connected to it, then
   for every node N connected to C and not on the result path tree, it
   is merged into the candidate node list.  The cost to node N is the
   sum of the cost to node C and the cost of the link between C and N.
   The PCE for node N is the PCE responsible for node N.

   If the CurrentPCE is the same as the PCE of the node with the minimum
   cost in CandidateNodeList, then the node is removed from
   CandidateNodeList, grafted to ResultPathTree, and the above steps are
   repeated; otherwise, the CurrentPCE sends the PCE a request with the
   source node, RestDestinationNodes, CandidateNodeList and
   ResultPathTree.


5.  Extensions to PCEP

   The extensions to PCEP for Forward Search P2MP Inter-domain Path
   Computation include the definition of a new flag in the RP object, a
   result path list/tree and a candidate node list in a request message.

5.1.  RP Object Extension

   The following flag is added into the RP Object:

   The F bit is added in the flag bits field of the RP object to tell
   the receiver of the message that the request/reply is for Forward
   Search Path Computation.

       o F (Forward search Path Computation bit - 1 bit):

           0: This indicates that this is not PCReq/PCRep
              for Forward Search Path Computation.

           1: This indicates that this is PCReq or PCRep message
              for Forward Search Path Computation.


   The IANA request is referenced in Section below (Request Parameter
   Bit Flags) of this document.

   This F bit with the N bit defined in RFC6006 can indicate whether the
   request/reply is for Forward Search Path Computation of an MPLS TE
   P2MP LSP or an MPLS TE P2P LSP.








Chen                    Expires September 8, 2011               [Page 7]


Internet-Draft          Forward Search P2MP Path              March 2011


       o F = 1 and N = 1: This indicates that this is a PCReq/PCRep
                          message for Forward Search Path Computation
                          of an MPLS TE P2MP LSP.

       o F = 1 and N = 0: This indicates that this is a PCReq/PCRep
                          message for Forward Search Path Computation
                          of an MPLS TE P2P LSP.


5.2.  PCE Object

   The figure below illustrates a PCE IPv4 object body (Object-Type=2),
   which comprises a PCE IPv4 address.  The PCE IPv4 address object
   indicates the IPv4 address of a PCE , with which a PCE session may be
   established and to which a request message may be sent.


        0                   1                   2                   3
        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       PCE  IPv4 address                       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   The format of the PCE object body for IPv6 (Object-Type=2) is as
   follows:


        0                   1                   2                   3
        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                 PCE  IPv6 address (16 bytes)                  |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


5.3.  Candidate Node List Object

   The candidate-node-list-obj object contains a list of candidate
   nodes.  A new PCEP object class and type are requested for it.  The
   format of the candidate-node-list-obj object body is as follows:








Chen                    Expires September 8, 2011               [Page 8]


Internet-Draft          Forward Search P2MP Path              March 2011


       0                   1                   2                   3
       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      //                     <candidate-node-list>                   //
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   The following is the definition of the candidate node list.


         <candidate-node-list>::= <candidate-node>
                                  [<candidate-node-list>]
         <candidate-node>::= <ERO>
                             <candidate-attribute-list>

         <candidate-attribute-list>::= [<attribute-list>]
                                       [<PCE>]
                                       [<Node-Flags>]



   The ERO in a candidate node contain just the path segment of the last
   link of the path, which is from the previous hop node of the tail end
   node of the path to the tail end node.  With this information, we can
   graft the candidate node into the existing result path list or tree.

   Simply speaking, a candidate node has the same or similar format of a
   path defined in RFC 5440, but the ERO in the candidate node just
   contain the tail end node of the path and its previous hop, and the
   candidate node may contain two new objects PCE and node flags.

5.4.  Node Flags Object

   The Node Flags object is used to indicate the characteristics of the
   node in a candidate node list in a request or reply message for
   Forward Search Inter-domain Path Computation.  The Node Flags object
   comprises a Reserved field, and a number of Flags.

   The format of the Node Flags object body is as follows:


       0                   1                   2                   3
       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |D|S|I|E|N|          Flags      |         Reserved              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



Chen                    Expires September 8, 2011               [Page 9]


Internet-Draft          Forward Search P2MP Path              March 2011


   where


       o D = 1:  The node is a destination node.
       o S = 1:  The node is a source node.
       o I = 1:  The node is an entry boundary node.
       o E = 1:  The node is an exit boundary node.
       o N = 1:  The node is a node in a destination domain.


5.5.  Rest Destination Nodes Object

   The figure below is an illustration of an object called a number of
   destinations not in path tree/list , which comprises an Object Length
   field, a Class-num field, a C-type filed, and a number of
   destinations not in path.  As shown, the value of Object Length field
   in the object may be 8, which is a length of the object in bytes; the
   value of Class-num field and the value of C-type field will be
   assigned by Internet Assigned Numbers Authority (IANA); and the value
   of the number of destinations not in path tree field comprises a
   number, which is the number of destinations that are not in the final
   path computed yet.


       0                   1                   2                   3
       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |       Object Length (8)       |    Class-num    |   C-type    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |            Numbe of Destinations not in path tree             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


5.6.  Request Message Extension

   Below is the message format for a request message with the extension
   of a result path list and a candidate node list:














Chen                    Expires September 8, 2011              [Page 10]


Internet-Draft          Forward Search P2MP Path              March 2011


           <PCReq Message>::= <Common Header>
                              [<svec-list>]
                              <request-list>
           <request-list>::=<request>[<request-list>]
           <request>::= <RP>
                        <END-POINTS>
                        [<OF>]
                        [<LSPA>]
                        [<BANDWIDTH>]
                        [<metric-list>]
                        [<RRO>[<BANDWIDTH>]]
                        [<IRO>]
                        [<LOAD-BALANCING>]
                        [<result-path-list>]
                        [<candidate-node-list-obj>]
                        [<rest-destination-nodes>]

        where:
           <result-path-list>::=<path>[<result-path-list>]
           <path>::= <ERO><attribute-list>
           <attribute-list>::=[<LSPA>]
                              [<BANDWIDTH>]
                              [<metric-list>]
                              [<IRO>]

           <candidate-node-list-obj> contains a <candidate-node-list>

           <candidate-node-list>::= <candidate-node>
                                    [<candidate-node-list>]
           <candidate-node>::= <ERO>
                               <candidate-attribute-list>

           <candidate-attribute-list>::= [<attribute-list>]
                                         [<PCE>]
                                         [<Node-Flags>]



                Figure 1: The Format for a Request Message

   The definition for the result path list that may be added into a
   request message is the same as that for the path list in a reply
   message that is described in RFC5440.


6.  Security  Considerations

   The mechanism described in this document does not raise any new



Chen                    Expires September 8, 2011              [Page 11]


Internet-Draft          Forward Search P2MP Path              March 2011


   security issues for the PCEP protocols.


7.  IANA Considerations

   This section specifies requests for IANA allocation.

7.1.  Request Parameter Bit Flags

   A new RP Object Flag has been defined in this document.  IANA is
   requested to make the following allocation from the "PCEP RP Object
   Flag Field" Sub-Registry:

         Bit       Description                         Reference

          18       Forward Path Computation (F-bit)    This I-D




8.  Acknowledgement

   The author would like to thank people for their valuable comments on
   this draft.


9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC3209]  Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
              and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
              Tunnels", RFC 3209, December 2001.

   [RFC5440]  Vasseur, JP. and JL. Le Roux, "Path Computation Element
              (PCE) Communication Protocol (PCEP)", RFC 5440,
              March 2009.

   [RFC6006]  Zhao, Q., King, D., Verhaeghe, F., Takeda, T., Ali, Z.,
              and J. Meuric, "Extensions to the Path Computation Element
              Communication Protocol (PCEP) for Point-to-Multipoint
              Traffic Engineering Label Switched Paths", RFC 6006,
              September 2010.





Chen                    Expires September 8, 2011              [Page 12]


Internet-Draft          Forward Search P2MP Path              March 2011


9.2.  Informative References

   [RFC4655]  Farrel, A., Vasseur, J., and J. Ash, "A Path Computation
              Element (PCE)-Based Architecture", RFC 4655, August 2006.

   [RFC5862]  Yasukawa, S. and A. Farrel, "Path Computation Clients
              (PCC) - Path Computation Element (PCE) Requirements for
              Point-to-Multipoint MPLS-TE", RFC 5862, June 2010.


Author's Address

   Huaimo Chen
   Huawei Technologies
   Boston, MA
   USA

   Email: Huaimochen@huawei.com

































Chen                    Expires September 8, 2011              [Page 13]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/