MPLS Working Group Heinrich Hummel, Internet Draft Jochen Grimminger Expiration Date: April 2003 Siemens AG October 2002 Hierarchical LSP draft-hummel-mpls-hierarchical-lsp-03.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 the "Hierarchical LSP" being a label-switched sequence of other LSPs (and interfaces), 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. Version 03 is based on RSVP-TE (not on CR-LDP anymore). Hummel October 2002 [Page 1] Hierarchical LSP Exp. April 2003 1 Introduction and motivation This draft is written in favor of extending RSVP-TE as to enable the "Hierarchical LSP" (=H-LSP). A "conventional LSP" is a label-switched concatenation of physical interfaces, whereas the hierarchical LSP is, in general, a label-switched concatenation of physical interfaces AND of already existing H-LSPs. An H-LSP is established by label-switched concatenation of sub H- LSPs, precisely "User Plane sub H-LSPs". Hereby Control messages (PATH, RESV) have to be forwarded via corresponding "Control Plane sub H-LSPs" With respect to each U-Plane sub H-LSP, there must be a parallel C- Plane sub H-LSP as well as an inverse directed C-Plane sub H-LSP, which both have the same endpoints like the U-Plane sub H-LSP. H-LSP Control Plane messages (PATH, RESV) have to be forwarded hop by hop, i.e. "C-Plane sub H-LSP" by "C-Plane sub H-LSP". Note that a particular sub H-LSP may be configured as to transport Control Plane messages only, or user data only, or Control Plane messages AND user data. Also note that a Control Plane message may take one hop by being sent thru a C-Plane sub H-LSP which shall also become a U-Plane sub H-LSP of the resulting H-LSP.Respectively, we refer to this sub H-LSP once as C-Plane sub H-LSP, once as U-Plane sub H-LSP. In [3] the H-LSP is called FA-LSP (FA = forwarding adjacency). That draft specifies the FA-LSP as to "inject" the resulting "virtual link" back to OSPF, so that some other entity may eventually find several such virtual links and may build an even hierachically higher FA-LSP out of them, and may inject this even hierarchically higher FA-LSP back to OSPF again,etc. However this draft is focussed on the establishment issues and also pursues an additional goal which is to overcome the notorious N- Square problem. With the help of H-LSPs an effective full mesh of tunnels can be accomplished by using just O(n) many (elementary) tunnels - which may form a contiguous partial mesh - rather than a full mesh using O(n**2) many tunnels. Sufficient many H-LSPs are to be established so that there is a concatenated sequence of elementary tunnels from any to any of the n sites. These H-LSPs will only consume network resources at the endpoints of the used elementary tunnels (control state, NHLFE), not at any P-router. The costs (incl. performance costs) for the H-LSPs from the network core's point of view will however even be equal to ZERO, if the H-LSPs become absolutely invisible for any P-router. This will be accomplished, if the messages (PATH, RESV,...) for establishing the H-LSPs are sent thru Hummel October 2002 [Page 2] Hierarchical LSP Exp. April 2003 the elementary tunnels as well. Find more about savings due to H-LSPs in [5] Additional arguments in favor of using H-LSPs: Multicast: Note that none of the LSPs according to a) or b) can be used for VPN-multicast traffic: Using these LSPs, the same multicast data would have to be send out as often as there are receiver nodes (PEs, CEs), or, what is no good solution either, has to be tranmitted via one (per VPN) additional (!!!) multicast delivery channel tree (which must carry even blind traffic - a trade-off in order to avoid multiple (application-dedicated) multicast delivery channel trees. VPN-multicast based on solution c) means: do multicast while using the elementary LSPs as "parent link" or "child links" of the multicast delivery tree. No additonal elementary LSPs are needed, no P-router is bothered with VPN-multicast. VPN-Multipath: VPN-Multipath means to provide multiple alternate pathes (e.g. differently routed, or for differently aggregated data) between any pair of sites. VPN-Multipath is usefull for traffic balancing, fast path restoration,QoS-sensitive data aggregation. Multiple full mesh according to solutions a) or b) is certainly not scalable, whereas according to c) only additional H-LSPs were required, but no additional elementary LSPs. Carrier's carrier networking: VPNs may be built based on a "network of LSPs" which is rented by some "virtual service provider" The elementary LSPs between the PEs of some VPN may already be H-LSPs themselves! MPLS over IP and over IPSEC due to H-LSPs: H-LSP may be built such that IP-tunnels (L2TP,GRE,IPSEC) are concatenated as well - together with MPLS-LSPs (ffs). Accordingly, a service provider may deploy VPN tunneling which spans both its MPLS- domains as well as its IP-domains. If IPSEC tunnels are used, they will be concatenated only "on safe ground". Security associations are reduced: not n, but only as many as there are neighboring PEs/CEs according to the partial mesh. The VC-label can still be exploited, too. Hummel October 2002 [Page 3] Hierarchical LSP Exp. April 2003 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 LSPs of level 1, i.e. conventional LSPs as are well-known today. Or, by repeating paragraphs from above section 1: An H-LSP is established by label-switched concatenation of sub H-LSPs, precisely "User Plane sub H-LSPs". Hereby Control messages (PATH, RESV) have to be forwarded via corresponding "Control Plane sub H-LSPs" With respect to each U-Plane sub H-LSP, there must be a parallel C- Plane sub H-LSP as well as an inverse directed C-Plane sub H-LSP, which both have the same endpoints as the U-Plane sub H-LSP. H-LSP Control Plane messages (PATH, RESV) have to be forwarded hop by hop, i.e. "C-Plane sub H-LSP" by "C-Plane sub H-LSP". Note that a particular sub H-LSP may be configured as to transport Control Plane messages only, or user data only, or Control Plane messages AND user data. Also note that a Control Plane message may take one hop by being sent thru a C-Plane sub H-LSP which shall also become a U-Plane sub H-LSP of the resulting H-LSP.Respectively, we refer to this sub H-LSP once as C-Plane sub H-LSP, once as U-Plane sub H-LSP. We may also envision NON-MPLS tunnels (L2TP, IPSEC,GRE) to be used as sub H-LSPs of level 1 (ffs). The sequence of sub H-LSPs may be linear (p2p H-LSP), or tree-like (mp2p /p2mp /mp2mp H-LSP) The establishment of the H-LSP may be initiated by the ingress or by the egress i.e. by which ever root of the tree-like H-LSP. The rest of this draft is focussed on p2p H-LSP initiated by the ingress. The other cases may be subject for further drafts in the future. Example: The following figure shows H-LSP U16 which shall carry labelled user packets from PE1 to PE6 passing PE2,...,PE5 as well as P-routers P1,...,P8 as displayed. It will concatenate/label-switch the three U-Plane sub H-LSPs U13, U34 and U46. Sub H-LSP U13 is itself a Hummel October 2002 [Page 4] Hierarchical LSP Exp. April 2003 concatenation of LSPs U12 and U23. Sub H-LSP U46 is itself a concatenation of LSPs U45 and U56. Sub H-LSP U34 is a conventional LSP. Figure 1: PE1-P1---P2--PE2----P3---PE3----P4---P5---PE4---P6-----PE5--P7-P8---PE6 | | | | | | | | | | | | | | | | | | | | | | | | | | | | |a--|b---|0--|c-----|0---|d-----|e---|0---|f----|0-----|g---|h-|0---| |--LSP U12-->|--LSP U23->|-sub H-LSP U34->|---LSP U45->|--LSP U56-->| | | | | | | | | | | | | |a1----------|0----------| |b1----------|0-----------| |---sub H-LSP U13------->| |---sub H-LSP U46-------->| | | | | | | | | |a2----------------------|b2--------------|0------------------------| |------------H-LSP U16--------------------------------------------->| Labels: a,b,c,d,e,f,g,h, a1, b1, a2, 0 (=IPv4 Explicit Null) P1 to P8 indicate P-routers PE1 to PE6 indicate Provider Edge routers LSP U12 shall carry user packets from PE1 via P1 and P2 to PE2, which are initially labelled with label a, which is swapped with label b at P1, which is swapped with label 0 (=explicit IPv4 Null label) at P2. LSP U23 shall carry user packets from PE2 via P3 to PE3, which are initially labelled with label c, which is swapped with label 0 at P3. (sub H-)LSP U34 shall carry user packets from PE3 via P4 and P5 to PE4, which are initially labelled with label d, which is swapped with label e at P4, which is swapped with label 0 at P5. LSP U45 shall carry user packets from PE4 via P6 to PE5, which are initially labelled with label f, which is swapped with label 0 at P6. LSP U56 shall carry user packets from PE5 via P7 and P8 to PE6, which are initially labelled with label g, which is swapped with label h at P7, which is swapped with label 0 at P8. Sub H-LSP U13 shall carry user packets from PE1 to PE3 with an initial label stack = (a, a1). PE2 will pop the received top-most 0- label and swap a1 with ( c, 0 ). Hummel October 2002 [Page 5] Hierarchical LSP Exp. April 2003 Sub H-LSP U46 shall carry user packets from PE4 to PE6 with an initial label stack = (f, b1). PE5 will pop the received top-most 0- label and swap b1 with ( g,0 ). H-LSP U16 shall be established such that user packets will be carried from PE1 to PE6 based on an initial label stack (a,a1,a2). PE3 shall pop two 0-labels and swap a2 with label stack (d, b2). PE4 will pop one 0-label and swap label b2 with label stack (f, b1,0). C-Plane sub H-LSPs: For establishing H-LSP U16 the following C-Plane sub H-LSPs are needed: C13 and inverse directed C31 sharing the tunnel endpoints with U13 C34 and inverse directed C43 sharing the tunnel endpoints with U34 C46 and inverse directed C64 sharing the tunnel endpoints with U46 They are used to forward the Control messages PATH and RESV. Figure 3: PE1-P1---P2--PE2----P3---PE3----P4---P5---PE4---P6-----PE5--P7-P8---PE6 | | | | |---sub H-LSP U13------->|-sub H-LSP U34->|---sub H-LSP U46-------->| | | | | | | | | | PATH | PATH | PATH | |---sub H-LSP C13------->|-sub H-LSP C34->|---sub H-LSP C46-------->| | | | | | RESV | RESV | RESV | |<--sub H-LSP C31--------|<-sub H-LSP C43-|<--sub H-LSP C64---------| | | |------------H-LSP U16--------------------------------------------->| 3 Knowing all relevant sub H-LSPs PE1 in above example must be enabled to determine that concatenating U13,U34, and U46 is the right choice as to build U-Plane H-LSP U16. The involved C-Plane sub H-LSPs, i.e. C13, C31, C34, C43,C46 and C64 must be derivable from the U-Plane sub H-LSPs (i.e. from U13, U34 and U46). In detail: PE1 must be able to derive C13 from U13 (evtl. both are identical). Hummel October 2002 [Page 6] Hierarchical LSP Exp. April 2003 PE3 must be able to derive C34 from U34 (evtl. both are identical). PE3 must also derive C31 from U13. PE4 must be able to derive C46 from U46 (evtl. both are identical). PE4 must also deri e C43 from U34. PE6 must be able to derive C64 from U46. How is any of these U- or C-Plane sub H-LSP composed ? This to know must be a local matter of each sub H-LSP's ingress node ! E.g. PE1 must be able to derive, based on LSP-ID U13, all deeper nested sub sub H-LSP information, i.e. all first hop's labels and the first hop's interface. Section 3.1. shows how to do it. Parallel and inverse directed C-Plane sub H-LSP must be derivable from the respective U-Plane sub H-LSP. Section 3.2 shows how this could be done. 3.1 Deriving all nested sub-sub H-LSPs The ingress node of any conventional LSP Z of level 1, which may eventually be used by some H-LSPs, shall allocate a MIB-entry as follows: {LSP-ID Z; S-bit=1; first physical interface of LSP Z; first label of LSP Z }. This entry will be retrievable based on its first component which is LSP-ID Z. The ingress node of any sub H-LSP of level > 1, which may eventually be used by some H-LSPs of even higher hierarchical levels, shall allocate a similar MIB-entry. Let's assume H-LSP X concatenates a sequence of (H-) LSPs which begins with H-LSP Y. Let's also assume that H-LSP Y concatenates a sequence of conventional LSPs which begins with LSP Z. That router which is the ingress of X, Y and Z shall altogether allocate the following MIB-entries for X,Y and Z: {LSP-ID X; S-Bit=0; LSP-ID Y, 1st label of LSP X} {LSP-ID Y; S-Bit=0; LSP-ID Z, 1st label of LSP Y} {LSP-ID Z; S-Bit=1; 1st phys.interface of Z, 1st label of LSP Z} Note that the S-bit has the same purpose like the S-bit in a label stack ! As soon as any LSP resp. H-LSP has been established successfully, the respective MIB-entry shall be allocated in some table. Starting with Hummel October 2002 [Page 7] Hierarchical LSP Exp. April 2003 the right LSP-ID, e.g. with LSP-ID X, we can navigate thru the right MIB-entries as to retrieve the complete initial label stack as well as the initial physical link. As we will see in section 5, we need this information for two reasons: 1) for sending some RSVP-TE-message THRU the respective Control Plane sub-H-LSP 2) for building an NHLFE as to concatenate two consecutive sub H- LSPs. Examples: PE1 shall maintain, after H-LSP U16 has been successfully established, the following MIB-Entries: {LSP-ID U16; S-Bit=0; LSP-ID U13, label a2} {LSP-ID U13; S-Bit=0; LSP-ID U12, label a1} {LSP-ID U12; S-Bit=1; interface to P1, label a } PE2 shall maintain: {LSP-ID U23; S-Bit=1; interface to P3, label c } PE3 shall maintain: {LSP-ID U34; S-Bit=1; interface to P4, label d } PE4 shall maintain: {LSP-ID U46; S-Bit=0; LSP-ID U45, label b1} {LSP-ID U45;S-Bit=1; interface to P6, label f } PE5 shall maintain: {LSP-ID U56; S-Bit=1; interface to P7, label g } Hummel October 2002 [Page 8] Hierarchical LSP Exp. April 2003 3.2 Deriving the relevant C-Plane sub H-LSPs The ingress endpoint router of a User Plane sub H-LSP must be able to derive the LSP-ID of the respective parallel Control Plane sub H- LSP (which has the same ingress and the same egress). The egress endpoint router of a User Plane sub H-LSP must be able to derive the LSP-ID of the respective inverse Control Plane sub H-LSP. Note that there may be several parallel User Plane sub H-LSPs (sharing the same ingress and the same egress), e.g. routed differently or carrying different types of date (voice, video, data,..). They may have in common a parallel C-Plane sub H-LSP (with the same ingress and the same egress), which is either an additional sub H-LSP or one of these U-Plane sub H-LSPs. Also note that there may be several parallel C-Plane sub H-LSPs (sharing the same ingress and the same egress), e.g. being dedicated to different VPNs. Here is an (incomplete) list of property information pertaining to any sub H-LSP which will also help to correlate User Plane sub H-LSP and Control Plane sub H-LSPs as needed: - 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, FEC etc. - if U-Plane, the respective parallel (if not identical) C-Plane LSP. - if C-Plane, the LSP-ID of the inverse C-Plane LSP. - whether it is shared among several VPNs/communities or is exclusively owned by some specific VPN/community. - ID of VPN/community which exclusively owns this H-LSP, if applicable - etc. All this information may be made available to whichever router that will need it, either by BGP-, OSPF, IS-IS-extensions or by static configuration. 4 Routing 4.1 Explicit Routing The ingress edge router sends the entire list of hops in an ERO. New: A particular hop's subobject must be able to carry a U-Plane LSP-ID. Attention: not the C-Plane LSP-ID !!! Hummel October 2002 [Page 9] Hierarchical LSP Exp. April 2003 Each transit edge router will be focussed on the first two entries (e1 and e2) of the received ERO. If e1 denotes a U-Plane sub H-LSP (identifier) , then the router will derive from e1 an inversely directed C-Plane sub H-LSP which it will use as to forward the returning RESV message later on. If e2 denotes a U-Plane sub H-LSP (identifier), then the router will derive from e2 a parallel directed (if not identical) C-Plane sub H-LSP which it will use to forward the PATH message. Before the PATH message is forwarded, the first subobject inside the ERO is stripped off. 4.2 Hop-by hop Routing The ingress edge router sends just one hop's information by means of an RSVP_HOP object which at the next receiving node will be viewed as the previous hop (PHOP). New: It may carry a U-Plane LSP-ID. Attention: not a C-Plane LSP-ID !!! If so, the receiving node will derive from this U-Plane LSP-ID an inversely directed C-Plane sub H-LSP which it will use as to forward the returning RESV message later on. It will determine the next hop by its own. If the next hop is again a U-Plane sub H-LSP, it will put its identifier into the RSVP_HOP object, while overwriting the old content. It will derive from it a parallel directed (if not identical) C-Plane sub H-LSP which it will use to forward the PATH message. 5 Ingress initiated establishment of the H-LSP In comparison with conventional LSP setup, special attention is to be given to: 1) Sending PATH/RESV-message THRU the C-Plane sub H-LSP tunnel 2) Label-switching of U-Plane sub H-LSPs 5.1 Sending PATH/RESV-message thru the C-Plane sub H-LSP tunnel Where ever a PATH or a RESV is to be sent to the next PE we must determine the respective C-Plane sub H-LSP ID. Based on this identifier we have to determine the C-Plane sub H-LSP 's initial label stack and also its first physical interface. The C-Plane sub H-LSP-ID can be determined as described in 4. Its initial label stack and its first physical interface can be determined as described in 3.1. Hummel October 2002 [Page 10] Hierarchical LSP Exp. April 2003 5.2 Label-switching of U-Plane sub H-LSPs Label-switching in a conventional LSP means: a) concatenating two consecutive interfaces (simply said). Label-switching in a H-LSP will also mean: b) concatenating two an upstream U-Plane sub H-LSP Uu with a downstream U-Plane sub H-LSP Ud, c) concatenating an upstream interface with a downstream U-Plane sub H-LSP Ud, d) concatenating an upstream U-Plane sub H-LSP Uu with a downstream interface. All cases a) - d) are covered if "MPLS"-extensions are made such that a single incoming label (from upstream) is mapped to an, eventual, g e n u i n e label stack (plus the downstream interface). A transit-PE which has received a label (value x) inside of a Label Object in the RESV message must assign a new label (value y), replace x by y in the Label object and forward it in the RESV message. It also must allocate a NHLFE which is retrievable based on label value y. We consider the NHLFE composition where a Ud comes into play. The NHLFE (retrievable by label y) must contain the initial label stack of Ud, enhanced by label x at the label stack bottom, as well as the first physical interface of Ud. This NHLFE can be allocated by retrieving all this Ud related information as is described in 3.1. Example as of figure 1: PE4 shall receive label x = 0 and assign label y = b2. Based on LSP-ID U46 it will retrieve the physical interface to P6 as well as the top most label stack portion (f,b1). PE4 will form a NHLFE which is retrievable based on label y=b2 and which encompasses {interface to P6, label f, label b1, label x=0}. 6 Final remarks Enhancements of RSVP_HOP and ERO are required as to carry the U-Plane sub H-LSP-ID, see above. It is up to the IETF to consider the H-LSP as something different then the conventional LSP - or not. Indeed, it may as well be such generic , as to cover all. Hummel October 2002 [Page 11] Hierarchical LSP Exp. April 2003 This draft has been focussed on p2p H-LSP establishment, initiated by the ingress. There will be more types of H-LSPs: - p2p initiated by the egress - mp2p initiated by the egress - p2mp initiated by the ingress - mp2mp initiated by any ingress+egress By some small enhancements RSVP-TE could be extended as to establish all of these H-LSPs (as well as conventional LSPs), yes, even in compliance with all kind of QoS/bandwidth/Policy constraints, so that normal LDP would not provide anything that can't be done better by RSVP-TE. 7 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 [3] K.Kompella (Juniper Networks): LSP Hierarchy with Generalized MPLS TE, draft-ietf-mpls-lsp-hierarchy-07.txt [4] RFC 3209 RSVP-TE: Extensions to RSVP for LSP Tunnels [5] H.Hummel (Siemens AG): O(n**2) Investigations draft-hummel-mpls-n-square-investigation-00.txt 8 Authors' Addresses Heinrich Hummel Siemens AG Hofmannstrasse 51 81379 Munich, Germany Tel: +49 89 722 32057 Email: heinrich-hummel@siemens.com Jochen Grimminger Siemens AG Otto-Hahn-Ring 6 81739 Munich, Germany Tel.+49 89 636 417410 Email: Jochen-Grimminger@siemens.com Hummel October 2002 [Page 12] Hierarchical LSP Exp. April 2003 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 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 October 2002 [Page 13]