Internet DRAFT - draft-hummel-mpls-hierarchical-lsp
draft-hummel-mpls-hierarchical-lsp
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]
