MPLS Working Group Heinrich Hummel, Internet Draft Jochen Grimminger Expiration Date: September 2002 Siemens AG March 2002 Hierarchical LSP draft-hummel-mpls-hierarchical-lsp-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. For potential updates to the above required-text see: http://www.ietf.org/ietf/1id-guidelines.txt Abstract This draft pursues the standardization of a the "Hierarchical LSP" being a label-switched sequence of other LSPs, i.e. of hierarchically next-lower LSPs, which eventually, after some recursive cycles, consist of label-switched sequences of physical interfaces, i.e. of LSPs as of today. Hierarchically stacked LSPs will eliminate the notorious N-square problem when virtual networks (or even virtual networks on top of virtual networks) are to be built. It is another kind of "Generalized MPLS" which, for the first time, tries to propagate an MPLS-Control Signalling that copes with the full Label STACK paradigma. Hummel March 2002 [Page 1] Hierarchical LSP Exp. Sept. 2002 1 Introduction and motivation The full blown label stack has been an essential MPLS-property since day one of MPLS. It insinuates that you may concatenate (=label- switch) LSPs, which themselves are concatenated (=label-switched) sequences of physical interfaces, and even more, which themselves are concatenated (=label-switched) sequences of LSPs. However, even today and six years later, there is still no MPLS control signalling protocol which enables such LSP constructions on top of other, already existing LSPs. When early-year MPLS-supporters wore T-shirts boasting "ATM - tomorrows technology misapplied today" they nourished expectations that they would soon come up with protocols that can handle label switched paths of whichever label stack depth, i.e. of whichever hierarchical level and not just plain VCs resp. VPs. MPLS was considered a synonym for overcoming the N-square problem - but nothing happened. On the mailing lists many ideas have been exchanged where and how to twist some screws, however only based on configuration and not based on signalling. In the meantime other folks, pwe3-folks, try to quench some more sense out of the label stack, while "abusing" the bottom most label for non-MPLS purposes, calling it VC-label or PW-label ("Pseudo Wire"- label). I think the time is overdue to launch a comprehensive work on standardizing what I like to call the "Hierarchical LSP (H-LSP) of hierarchy level m" which is a label-switched sequence of H-LSPs of hierarchy levels next lower to m. Hereby any such sequence may either be linear (p2p), merging (mp2p) or branching (p2mp). The benefits will be enormous. The n-square problem would vanish: By concatenating (=label- switching) LSPs (of next lower hierarchical level) to different sequences towards different egresses, a full mesh connectivity can be accomplished based on O(n) many lower level LSPs only! Note, it is a stated requirement for the ppvpn WG to develop scalable solutions for up to n=50,000 CEs. Deploying n*(n-1) CE-to-CE tunnels for such a value n is unthinkable. The efforts made so far as to overcome this scalability problem shall not be ignored: E.g. RFC2547-model uses PE-to-PE tunnels, as to interconnect N PEs rather than n CEs, assuming that N < n . It also employs the so called VC-label, which enables tunnel sharing followed by disaggregation at the remote PE with the help of the VC-label. It is also admitted that deploying N merging (p2mp) PE-to-PE tunnels rather than N*(N-1) p2p PE-to-PE tunnels will relax the scalablility problem even further. While this is all acknowledged, CE-based VPNs using CE-to-CE tunnels will also have its market share (according to a study of The Yankee Group an even bigger market share than the PE-based VPNs). And here, the concept of the H-LSP can truly help: Only 2*(n-1) CE-to-CE Hummel March 2002 [Page 2] Hierarchical LSP Exp. Sept. 2002 tunnels are required at minimum. 4*n CE-to-CE tunnels (which will enable multiple alternatively routed tunnel sequences) will be more than enough. The tunnels from this relatively small set of tunnels may be used multiple times as to form different label-switched tunnel sequences towards different egresses, i.e. as to accomplish, effectively, a full mesh. Back to PE-based VPNs: Even for them the H-LSP concept can still improve the scalability situation and also: It may eliminate the needs for tunnel sharing between different VPNs, so that VPN policing becomes a doable objective. You can only identify the right sinner who violoates his SLA by overloading a particular tunnel, if that tunnel is not shared with other VPNs. In the end, virtual networks on top of virtual networks can be established. 2 Definition of the H-LSP The H-LSP of level m is a concatenated (label-switched) sequence of sub H-LSPs of levels w, with 1<= w <= m-1, whereby at least one of them has level m-1. By the same recursive manner, each of these sub H-LSPs is defined as well. Eventually some of these sub H-LSPs may be and definitely some of their sub-sub H-LSPs will be an LSP of level 1 which shall be an LSP as is well-known today. We may also envision NON-MPLS tunnels (L2TP, IPSEC,GRE) to be used as sub H-LSPs of level 1 (ffs). As a result, the H-LSP of level m may be viewed as an LSP-stack of m LSPs, at least at one route section between its ingress and egress. Each H-LSP, of whichever level, can be conceived as a logical (uni- directional !) interface. Therefore, each one shall have an LSP-ID as known from CR-LDP. Its meaning will be similar to the port number of a physical interface. Hummel March 2002 [Page 3] Hierarchical LSP Exp. Sept. 2002 Examples: The following figure shows the HOMOGENEOUS H-LSP L-3,1 ( LSP-stack depth m=3 constantly). H-LSP 3,1 is a label-switched sequence of its U-Plane sub H-LSPs 2,1 / 2,2. PE1 PE2 PE3 PE4 PE5 |a--b--c--0--|d--e--f-0--|g--h--i--0--|j---k--0----| LSPs of level 1: |--LSP 1,1-->|--LSP1,2-->|--LSP 1,3-->|---LSP 1,4->| |a1----------|0----------|b1----------|0-----------| LSPs of level 2: |-------LSP 2,1--------->|------LSP 2,2----------->| |a2----------------------|0------------------------| LSP of level m=3:|-------------LSP 3,1----------------------------->| Labels: a,b,c,d,e,f,g,h,i,j,k, a1, b1, a2, 0 (=IPv4 Explicit Null) Data is forwarded from router PE1 to router PE5. PE1 generates the initial label stack (a,a1,a2). PE2 pops and discards one 0-label, replaces label a1 with (d, 0). PE3 pops and discards two 0-labels, replaces label a2 with (g,b1, 0). PE4 pops and discards one 0-label, replaces label b1 with (j,0) PE5 pops and discards three 0-labels: the entire label stack has exhausted. The following shows an INHOMOGENEOUS H-LSP L3,1 (LSP stack depth varies between 2 and 3). L3,1 is a label-switched sequence of its U-Plane sub H-LSPs 2,1 / 1,3 / 1,4. PE1 PE2 PE3 PE4 PE5 |a--b--c--0--|d--e--f-0--|g--h--i--0--|j---k--0----| LSPs of level 1: |--LSP 1,1-->|--LSP1,2-->|--LSP 1,3-->|---LSP 1,4->| |a1----------|0----------| | | LSP of level 2: |-------LSP 2,1--------->| | | |a2----------------------|b1----------|0-----------| LSP of level m=3:|-------------LSP 3,1----------------------------->| Labels: a,b,c,d,e,f,g,h,i,j,k, a1, a2, b1, 0 (=IPv4 Explicit Null) Data is forwarded from router PE1 to router PE5. PE1 generates the initial label stack (a,a1,a2). PE2 pops and discards one 0-label, replaces label a1 with (d, 0). PE3 pops and discards two 0-labels, replaces label a2 with (g, b1). PE4 pops and discards one 0-labels, replaces label b1 with (j, 0). PE5 pops and discards two 0-labels: the entire label stack has exhausted. Hummel March 2002 [Page 4] Hierarchical LSP Exp. Sept. 2002 A H-LSP may either be used as U-Plane LSP or as C-Plane LSP or as both. By the following this draft describes the establishment of a p2p U-Plane H-LSP of level m in Downstream on-demand mode. The reader may be assured that there is no difference if its purpose were to carry C-Plane information instead. 3 Knowing all needed sub H-LSPs In this section let us consider all needed direct sub H-LSPs for establishing a p2p U-Plane H-LSP of level m. According to the above, the uni-directional "U-Plane" H-LSP of level m is a concatenated (label-switched) sequence of the immediate uni-directional "U-Plane" sub H-LSPs. They have to be known. With respect to each of these "U-Plane" sub H-LSPs there will be a parallel (if not identical) "C-Plane" sub H-LSP, going from the same ingress to the same egress edge router, as well as a respectively inverse C-Plane sub H-LSP. They have to be known as well. (Note, these C-Plane H-LSPs are called C-Plane sub H-LSP only because they have the same edge routers as the respective U-Plane sub H-LSPs). In summary, all these U-Plane and C-Plane sub H-LSPs must have been established before, and their existence must properly have been communicated/advertised to the routers which are now supposed to establish this U-Plane H-LSP of level m. MP-BGP and its communities-concept (based on the Extended Communities Attribute) could play a supportive role in the process of establishing and advertising all of them as well as of all of their sub-sub H-LSPs. This concept may take care that the right sub-entities (VRFs) of the right pair of edge routers will recognize what (sub) H-LSP they are supposed to establish between each other. As soon as it is established, its existence may be communicated to all "community/communities" members. The edge router which is to establish the U-Plane H-LSP of level m must be able to compute the respective sequence of U-Plane sub H-LSPs in compliance with all appropriate constraints. Furthermore, it must be able to determine the right C-Plane sub-H-LSP which is to be used, e.g. for sending the LABEL REQUEST message. Hummel March 2002 [Page 5] Hierarchical LSP Exp. Sept. 2002 Therefore, each sub H-LSP needs to have some property information like: - its LSP ID - its ingress and its egress router addresses - its plane-type (U-Plane only , C-Plane only, U-Plane AND C-Plane) - if U-Plane, (inherited) QoS/SLA/Traffic Parameter, bandwidth,color,preference etc. - if U-Plane, what is the respective parallel (if not identical) C- Plane LSP. - whether it is shared among several VPNs/communities or exclusively owned by some specific VPN/community. - ID of VPN/community which exclusively owns this H-LSP, if applicable - if C-Plane, what is the LSP-ID of the inverse C-Plane LSP. - etc. Note that there may be several parallel U-Plane sub H-LSPs (sharing the same ingress router and the same egress router), e.g. for carrying different types of traffic, or, being differently routed, for supporting traffic balancing. Note that there may be several parallel C-Plane sub H-LSPs, but belonging to different VPNs/communities exclusively. Finally note, that we don't need to know any sub-sub H-LSP. Dealing with them is a subordinate task as will be shown in section 5. 4 Explicit routing versus hop-by-hop routing Each involved transit edge router of the sub H-LSPs needs to determine the two U-Plane H-LSPs to be concatenated, as well as the two adjacent C-Plane H-LSPs in forward resp. backward direction. a) Explicit Routing information: An ER TLV is proposed which contains the list of LSP-IDs of the U- PLANE sub H-LSPs in proper sequence (and NOT, as is known from CR- LDP, C-Plane LSP-IDs !!!). Before any transit edge router of any of these U-Plane sub-H-LSPs forwards the LABEL REQUEST message, it will remove the first entry (ER HOP) inside the ER TLV. Consequently each such transit edge router will get the LSP-IDs of the incoming and of the outgoing U-Plane sub H-LSP (which have to be concatenated) by the first two received ER HOP TLVs. From them and with the help of locally available property information (see list above), it may drive the two appropriate C-Plane sub H-LSPs, the one in upstream direction and the one in downstream direction. Hummel March 2002 [Page 6] Hierarchical LSP Exp. Sept. 2002 b) Hop-by hop Routing information: Each edge router must compute the next-hop U-Plane sub H-LSP based on other received information like FEC, Parameters, etc. From it and again with the help of locally available property information it will derive the respective parallel (if not identical) next-hop C-Plane sub H-LSP (in downstream direction). Furthermore, it needs to know the C-Plane sub H-LSP towards the preceding edge router (in upstream direction). Solution 1: The preceding edge router sends the wanted LSP ID by means of a new TLV. Solution 2: The preceding edge router sends the LSP-ID of the downstream U-Plane sub H-LSP by means of a new TLV and let the successor derive the wanted C-Plane sub H-LSP in upstream direction. Solution 3: The preceding edge router sends the LSP-ID of the downstream C-Plane sub H-LSP and let the successor derive the respective inverse C-Plane sub H-LSP. 5 Downstream on-demand process for establishing the H-LSP of level m See the following figure. +-----+ +-----+ +-----+ +-----+ +------+ | | | PE- |---Uu---->| |----Ud---->| PE- | | | | | | up | | PE | | down| | | |PE- | | |---Cui--->| |----Cdo--->| | |PE- | |in- |...| |<--Cuo----| |<---Cdi----| |...|egress| |gress| | | | | | | | | +-----+ +-----+ +-----+ +-----+ +------+ Uu = U-Plane sub H-LSP coming from router PE-up Ud = U-Plane sub H-LSP going to router PE-down Cuo = outgoing C-Plane sub H-LSP to router PE-up Cui = incoming C-Plane sub H-LSP from router PE-up Cdo = outgoing C-Plane sub H-LSP to router PE-down Cdi = incoming C-Plane sub H-LSP from router PE-down PE-ingress initiates a LABEL REQUEST message which shall carry an LSP-ID (generated as known from CR-LDP ) which shall identify the H- LSP of level m to be established. PE-up will forward the LABEL REQUEST to PE via Cui. The LABEL REQUEST either carries Explicit Routing information or Hop-by-Hop Routing information as described above. In either case, PE will be able to determine the LSP-IDs for Ud, Cdo and Cuo (as described above, too) and store this information as part of the "Control Plane Hummel March 2002 [Page 7] Hierarchical LSP Exp. Sept. 2002 state". PE will forward the LABEL REQUEST message via Cdo to PE-down. For doing so it needs to determine the initial label stack as well as the first physical interface of Cdo as follows: Let's assume Cdo starts out being a stack of m-1 LSPs. Their LSP-IDs shall be: Cdo-(1), Cdo-(2),...,Cdo-(m-2), Cdo-(m-1) = Cdo. When LSP Cdo-(1) had been established, PE allocated a MIB- entry,retrievable based on LSP-ID Cdo-(1), of the following (new) form: {S-Bit=1; first phys.interface of Cdo-(1), first label of Cdo-(1)}, When LSP Cdo-(2) was established, PE allocated a MIB- entry,retrievable based on LSP-ID Cdo-(2), as follows: {S-Bit=0; LSP-ID Cdo-(2), first label of Cdo-(2)}, ... When LSPs Cdo-(m-1) was established, PE allocated a MIB- entry,retrievable based on LSP-ID Cdo-(m-1), as follows: {S-Bit=0; LSP-ID Cdo-(m-1) = Cdo, first label of Cdo-(m-1)}, Starting with LSP-ID Cdo, we can retrieve all these MIB-entries and stop navigating as soon as we encounter S-Bit=1. Hereby we retrieve all labels for the initial label stack as well as the first physical interface of C-Plane sub H-LSP Cdo. The LABEL REQUEST message may finally reach PE-egress. The PE-egress will send back a LABEL MAPPING with a LABEL-TLV (its value shall be the EXPLICIT NULL LABEL) After several hops, this LABEL MAPPING will be forwarded from PE-down to PE via LSP Cdi whereby the LABEL-TLV shall contain label value y which has been assigned by PE-down. PE will process this LABEL MAPPING message: a) by forwarding it, properly modified, to PE-up. b) by allocating an extended NHLFE as to concatenate Uu to Ud. ad a) Forwarding the LABEL MAPPING to PE-up: PE assigns a new available label x, replaces y with x in the LABEL- TLV and forwards the LABEL MAPPING such modified to PE-up via Cuo. For doing so it determine the first physical interface as well as the initial label stack of Cuo analogously as has been described above with respect to Cdo. ad b) Allocating an (extended) NHLFE: U-Plane LSP Uu is to be concatenated to U-Plane LSP Ud. With respect Hummel March 2002 [Page 8] Hierarchical LSP Exp. Sept. 2002 to U-Plane LSP Ud, PE retrieves its first physical interface as well as its initial label stack analogously as has been described above w.r.t. Cdo. PE allocates an NHLFE and stores in it all the retrieved information and also label y. I.e. this NHLFE shall begin with the physical interface, followed by the at last retrieved label, ..., followed by the at first retrieved label, followed by label y. PE also takes care that this extended NHLFE can be retrieved based on label value x. 6 Forwarding user data using the H-LSP of hierarchical level m Via this H-LSP of hierarchical level m user data is transmitted from PE-ingress to PE-egress. When a user packet arrives at router PE, its prepended label stack will contain label x and eventually several EXPLICIT NULL LABELs above label x. I.e. label x will become effective: Label value x will be used to look up the extended NHLFE as composed in section 8. Label x will be replaced by this looked-up stack of labels (with value y at its bottom). Note that, the received label stack may have further labels below label x. They will transparently be forwarded below the looked-up stack of labels. However this has been state of the art since the beginning of MPLS. 7 Outlook The previous sections were focussed on p2p downstream on-demand H- LSPs using either Explicit Routing or Hop-by-Hop Routing. However it takes to consider all combinations a * b * c of the following three sets: - a is element from { Linear (P2p), merging (mp2p), branching (p2mp) H-LSP } - b is element from { Downstream on-demand, Unsolicited downstream } - c is element from { Explicit Routing, Hop-by-Hop Routing } Some of them will be more reasonable, some may be less. We should also have a closer look to the properties/ parameters of Hummel March 2002 [Page 9] Hierarchical LSP Exp. Sept. 2002 the H-LSP. Which new parameters make sense ? Which well-known parameters may or may not be inherited from the sub-H-LSP ? Altogether, it will really be a comprehensive and necessary work item. 8 References [1] H.Hummel,J.Grimminger (Siemens AG): Partially meshed base tunnels plus hierarchical mp2p tunnel sequence LSPs draft-hummel-ppvpn-mp2p-tunnel-sequencing-00.txt [2] H.Hummel (Siemens AG): Tree/Ring/Meshy VPN tunnel systems draft-hummel-ppvpn-tunnel-systems-00.txt 9 Authors' Addresses Heinrich Hummel Siemens AG Hofmannstrasse 51 81379 Munich, Germany Tel: +49 89 722 32057 Email: heinrich.hummel@icn.siemens.de Jochen Grimminger Siemens AG Otto-Hahn-Ring 6 81739 Munich, Germany Tel.+49 89 636 417410 Email: Jochen.Grimminger@mchp.siemens.de Full Copyright Statement "Copyright (C) The Internet Society (March 2000). 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 implmentation 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 Hummel March 2002 [Page 10] Hierarchical LSP Exp. Sept. 2002 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. Hummel March 2002 [Page 11]