PPVPN Working Group Heinrich Hummel,
Internet Draft Jochen Grimminger
Expiration Date: May 2002 Siemens AG
November 2001
Partially meshed base tunnels plus
hierarchical mp2p tunnel sequence LSPs
draft-hummel-ppvpn-mp2p-tunnel-sequencing-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
Placement of this Memo in Sub-IP Area
RELATED DOCUMENTS:
See reference.
WHERE DOES IT FIT IN THE PICTURE OF THE SUB-IP WORK
The presented ID fits into ppvpn, ccamp and into idr of the Routing
Area.
WHY IS IT TARGETED AT THIS WG(s)
The application in mind for which to setup hierarchical multipoint-
to-point tunnel sequence LSPs, as described, is CE-based VPN as well
as Network(PE)-based VPN.
The detailed C-Plane aspects (procedures, messages, TLVs) for setting
up hierarchical mp2p tunnel sequence LSPs, i.e. for concatenating
Hummel,Grimminger Nov. 2001 [Page 1]
mp2p Tunnel sequence trees Exp. May 2002
some base tunnels to different tree-shaped tunnel sequences, would be
a work item for ccamp.
The details w.r.t. distribution/discovery of all base tunnels to/by
all targetted communities (VRFs) would be an extension of MP-BGP and
subject for idr.
JUSTIFICATION
So far, any-CE-to-any-CE connectivity may either mean full mesh CE-
CE-tunneling (in CE-based VPNs) or full mesh PE-PE tunneling (in
Network(PE)-based VPNs). Accordingly, a CE-based VPN with 50 000 CEs
(which is a stated requirement) would need 2,499,950 unidirectional
CE-CE-tunnels; a network(PE)-based VPN with 1000 PEs would need
999,000 PE-PE uni-dir.tunnels. However, by using only a partial mesh,
e.g. a chessboard mesh, n nodes may be fully interconnected using
less than 4 * n unidir. base tunnels plus n tree-shaped tunnel
sequence LSPs where the base tunnels are reused again and again for
conveying traffic to each egress node. Even more, by installing
several, differently routed tree shaped tunnel sequence LSPs rooted
at the same egress node, such nice services like path protection,
traffic balancing and QoS-/SLA-/traffic type-specific tunneling can
easily be supported without needing any extra tunnel.
Abstract
In order to provide any-CE-to-any-CE connectivity it is proposed to
deploy an O(n)-sized set of base tunnels which form a reasonable
partial mesh (e.g. chessboard topology), and to use them and re-use
them many times as elements of concatenated hierarchical multipoint-
to-point tunnel sequence LSPs. The number of saved tunnels is of
order n-square. Multiple,differently routed tunnel sequence LSPs but
rooted at the same node may cater for features like traffic
balancing, path protection, QoS-routing, etc., without needing any
extra tunnel. It is outlined how to establish such an optimal VPN
inter-site tunneling.
Hummel,Grimminger Nov. 2001 [Page 2]
mp2p Tunnel sequence trees Exp. May 2002
1 Introduction
In order to provide any-CE-to-any-CE connectivity it is proposed to
deploy an O(n)-sized set of base tunnels which form a reasonable
partial mesh (e.g. chessboard topology), and to use them and re-use
them many times as elements of concatenated hierarchical multipoint-
to-point tunnel sequence LSPs.
For a CE-based VPN with N CEs, N such mp2p hierarchical tunnel
sequence LSPs would be required, whereby each such hierarchical LSP
is composed of some CE-CE base tunnels and is egressing at a
different CE. There may be even x (e.g. x=3 or 4) such hierarchical
LSPs per egress-CE, which are differently routed, i.e. which are
composed by different CE-CE base tunnels, as to support traffic
balancing, path protection, QoS-specific routing, etc.
For a network(PE)-based VPN with n PEs, n such hierarchical mp2p
tunnel sequence LSPs would be required, whereby each such
hierarchical LSP is composed of some PE-PE base tunnels and is
egressing at a different PE. There may be even x (e.g. x=3 or 4)
such hierarchical LSPs per egress-PE, which are differently routed,
i.e. which are composed by different PE-PE base tunnels, as to
support traffic balancing, path protection, QoS-specific routing,etc.
The so-called VC-Label,which selects the remote interface to the
remote CE, would become the "third" label instead of the "second"
label in the label stack.
The draft outlines how such optimal VPN inter-site tunneling may be
established. Hereby, for reasons of simplicity, the draft is focussed
on network(PE)-based VPNs using uni-directional LSPs (covering CE-
based VPNs and bi-directional LSPs as well wouldn't take extra
inspiration, but extra transpiration).
Extensions/modifications to LDP and RSVP-TE as well as to MP-BGP will
be required.
2 Savings and advantages
Full mesh tunneling among n nodes requires n*(n-1) uni-directional
tunnels.
The absolute minimal number of tunnels to interconnect all nodes
contiguously would be 2 * (n-1), whereby any two nodes, which are
connected by some tunnel in one direction, are also connected by the
inverse-directional tunnel. Hereby the tunnel topology has no meshes
and looks like a tree. An algorithm for selecting those tunnels which
form the tree with the smallest weight sum can be found in [1].
Hummel,Grimminger Nov. 2001 [Page 3]
mp2p Tunnel sequence trees Exp. May 2002
However, without any meshes it is impossible to use alternate routes
for traffic balancing, path protection, etc. Therefore, let's assume
a set of such pairs of mutual inverse base tunnels which form a
reasonable partial mesh, e.g. a chessboard topology. Hereby n nodes
are contiguously webbed together by less than 4 * n (uni-directional)
tunnels.
Compared with full mesh we save at least n*(n-1) -4*n = n*(n-5)
tunnels. Note that the establishment of each of these tunnels would
involve P-routers and would consume one label at each P-router.
Accordingly are the effects, if we can save so many "base" tunnels.
Also note, that from the statistical multiplex performance's point of
view it is better to have only 4*n tunnels with more bandwidth than
n*(n-1) tunnels with less bandwidth.
In order to provide any-to-any connectivity based on only the
chessboard meshed set of base tunnels, we need to establish some
tree-shaped tunnel sequence LSPs, which would convey all user traffic
from any of n-1 ingress nodes to one specific egress node.
We may even want to have x such LSPs which eventually are differently
routed (i.e. composed by different sets of base tunnels) but convey
traffic to the same egress node. We may want this for reasons of
traffic balancing, fast rerouting, QoS/SLA/traffic-type-specific
tunneling.
Note that in a full mesh scenario you would need x * n * (n-1)
tunnels to get the same benefits !
The immense saving with respect to base tunnels allows us to be less
keen on PE-PE tunnel sharing: We can afford NOT to share some PE-PE
base tunnel in case the respective customers are not allied. This
opens the capability to do VPN-specific bandwidth policing. Otherwise
you won't know which customer is to blame for his SLA-violation.
Multicast:
The fundamental goal of multicast is to avoid retransmitting the same
user data multiple times over the same physical link. In the full
mesh scenario the chance is big that the same data is transmitted
multiple times (up to n-1 times) over the same physical link. This is
much less likely, in case there are multiple transit base tunnels
involved. Nevertheless, Multicast is for further study.
A particular base tunnel may be used many times, i.e. for
transmitting user traffic to different egress nodes. A hierarchical
label, let's call it the "Tunnel-Sequence-Label" will take care that
the user traffic which exits some base tunnel will enter the next
base tunnel on its way to some egress node. As mentioned above, we
Hummel,Grimminger Nov. 2001 [Page 4]
mp2p Tunnel sequence trees Exp. May 2002
need trees of tunnel sequences. As we will see, no P-router will ever
become aware of the existence of any tunnel sequence LSP! This
includes: A P-router will never have to use its label space for
assigning some Tunnel-Sequence-Label.
3 Establishing the elementary base tunnels
Each PE which is involved in a particular VPN/Community needs to know
the entire respective set of PE-PE-base-tunnels. This information
may either be provided by network configuration or by MP-BGP
advertisement.
Hereby, a particular VRF at a particular PE must EXACTLY know this
set. Which tunnels are part of this set may depend on some policy:
a) Base tunnels dedicated to some customer:
PE-PE-base tunnel exclusively belongs to some specific VPN/Community.
It may be appropriate to have several base tunnels from PE-x to PE-y,
whereby some of them belong to VPN/Community A while others belong to
VPN/Community B.
b) All base tunnels are shared by all customers:
Base tunnel from PE-x to PE-y participates (transitively) in a
tree-shaped tunnel sequence LSP rooted in PE-z, though the customers
with sites at PE-z have neither sites at PE-x nor at PE-y.
c) Some base tunnels are shared by all customers, some other base
tunnels are dedicated to individual customers.
MP-BGP may advertise, by means of a new TLV inside the MP_REACH_NLRI,
all characteristic data of each base tunnel to be built and may
convey them to the right VRFs at the right PEs by means of some Route
Target Community in the Extended Communities attribute - in
accordance with the mentioned policy.
Characteristic data of a base tunnel comprises: tunnel endpoints,
direction, usage (i.e for User and/or Control plane), bandwidth,FEC
at its egress endpoint, "color".
The respective adjacent VRFs may initiate the establishment of these
base tunnels, which includes assigning their LSP-IDs. As a result of
a base tunnel establishment its ingress-PE must store its first hop
interface and its first hop Tunnel-Label in such a way that these
information can be retrieved based on the LSP-ID again.
When the base tunnels have been established MP-BGP shall advertise
them once again, enhanced with their LSP-IDs.
Hummel,Grimminger Nov. 2001 [Page 5]
mp2p Tunnel sequence trees Exp. May 2002
As a result each VRF of some VPN/Community will learn the entire
topology composed of all those established base tunnels it is
supposed to know.
Prior to MP-BGP, network configuration has properly been done, if all
PE nodes of a VPN/Community are contiguously interwebbed by base
tunnels, and if any pair of nodes, which is connected by some U-plane
base tunnel, is also connected by two (mutually inverse) C-Plane base
tunnels.
4 Establishing the hierarch. Multipoint-to-point Tunnel Sequence LSP
A particular egress-PE computes a Dijkstra-spanning tree of base
tunnels which are all directed towards this egress-PE. Hereby
QoS/SLA/traffic-type- specific constraints may have influenced the
selection of the participating base tunnels. This tree of base
tunnels will be the "U-plane tree".
For each of the participating tunnels there exists an inverse base
tunnel. All these inverse tunnels form the "C-plane tree".
Using the unsolicit mode, the egress-PE sends out an explicitly
routed LABEL MAPPING message along the p2mp C-plane tree. The LABEL
MAPPING message will only be seen by the end nodes of the C-Plane
base tunnels (which are PEs) and not by any P-router. In order to
direct the message down the C-Plane tree, an extension to the
existing Explicit Route TLV (ER-TLV) is needed:
New "("-TLVs and ")"-TLVs should be inserted between the ER-HOP-TLVs
in accordance with the structure of the tree route. A simple
algorithm at any transit PE will take care that the proper part of
the received ER-TLV is forwarded, especially at the merging nodes of
the U-Plane tree.
Furthermore, the ER HOP-TLV needs to be enhanced as well: It shall
be able to carry two LSP-IDs (one for the next U-Plane base tunnel,
and one for the respectively inverse C-Plane base tunnel).
+----
| +--> ...
v |
+----+ ----C1----> +----+ ------C2----> +----+ --->
|PE-A| <------U1--- |PE-B| <-U2---------- |PE-C| <--- ....
+----+ +----+ +----+
Egress
Above figure shows some part of the p2mp C-plane tree (i.e. C1,C2)
and some part of the mp2p U-plane tree (i.e. U1,U2), both rooted in
Hummel,Grimminger Nov. 2001 [Page 6]
mp2p Tunnel sequence trees Exp. May 2002
PE-A.
(Note: C-Plane base tunnels may eventually also be used as U-Plane
base tunnels which participate in U-Plane trees rooted somewhere
else. Also, any C-Plane base tunnel may participate in differently
rooted C-plane trees. Any U-Plane base tunnel may participate in
differently rooted U-Plane trees)
The U-plane tree is built by installing base tunnel bindings at the
transit PEs, will say by "Multiprotocol Tunnel-Sequence-Label
Switching". As a matter of fact, the U-plane tree is a hierarchical
multipoint-to-point LSP, whose labels shall be called "Tunnel-
Sequence-Label".
PE-A in above figure assigns an available Tunnel-Sequence-Label x (it
is a label like any other Tunnel-Label) and writes it into the
Label-TLV of the LABEL MAPPING message. Furthermore, PE-A provides
an ER-TLV whose top-most ER HOP-TLV shall contain a) LSP-ID U1 and b)
LSP-ID C1, followed by an ER HOP -TLV which contains a) LSP-ID U2 and
b) LSP-ID C2.
When PE-B receives the LABEL MAPPING message, it assigns an own
Tunnel-Sequence-Label y and creates an NHLFE which is retrievable
based on y. The NHLFE entry shall contain the following information:
- PE-B's physical interface of base tunnel U1
- PE-B's Tunnel Label of base tunnel U1
(PE-B must know the two information at this
point in time, i.e. it must be able to retrieve them
by means of LSP-ID U1 from the top-most ER HOP-TLV)
- Tunnel Sequence Label x.
PE-B forwards the LABEL MAPPING message to PE-C thru C-Plane base
tunnel C2. For doing this, it locally looks up the physical interface
as well as the first Tunnel-Label of C2 based on LSP-ID C2. Hereby it
forwards the Tunnel-Sequence-Label y (inside the Label-TLV) and also
the ER-TLV, however without the top-most ER-HOP-TLV. ,sp 1 Any
transit PE, where the U-Plane tree is supposed to merge, may assign
further Tunnel-Sequence-Labels (e.g. y2, y3,..) for each branch and
map them to (the same) Label-Sequence-Label x analogously. Hereby a
well deterministic algorithm must crack the received ER-TLV in
compliance with the contained "("-TLVs and ")"-TLVs and determine all
ER HOP-TLVs that contain LSP-IDs of adjacent U-Plane and C-Plane base
tunnels.
Additionally, penultimate label popping may apply to Tunnel Sequence
Hummel,Grimminger Nov. 2001 [Page 7]
mp2p Tunnel sequence trees Exp. May 2002
Labels just like to plain Tunnel Labels.
So far the establishment of the hierarchical multipoint-to-point
Tunnel Sequence LSP in LDP syntax. An analogous description in
RSVP-TE syntax may be provided in a follow-up draft version.
5 Carrier's carrier network
The preceding sections have shown how Multiprotocol Tunnel-Sequence-
Label Switching could be done as to save order-n-square many tunnels
and provide even better services than in a simple full mesh scenario.
Additionally, we may consider network(PE)-based VPNs, which are
provided by some "virtual service provider" whose network consists of
a set of "Service Provider"-LSPs, provided by some "carrier's
carrier".
Indeed, the technology outlined above, may somehow recursively be
repeated in such a scenario. The VPN-related base tunnels may be
tunnel sequence LSPs themselves, more precisely: The "VPN"-base
tunnel is a (linear, not merging) hierarchical "Service Provider
Tunnel Sequence" LSP.
Consequently, a user packet may have a label stack which contains:
- Service Provider Tunnel -Label
- Service Provider Tunnel-Sequence-Label
- VPN Tunnel-Sequence-Label
- VC-Label
The NHLFEs that perform the label binding for a "VPN"- U-Plane tree
rooted at some VPN/Community-specific egress PE may contain:
- physical interface of the (first) SP-base tunnel
of a particular VPN-base tunnel
- Tunnel-label of the (first) SP-base tunnel
of a particular VPN-base tunnel
- Tunnel-Sequence Label which concatenates
some SP-base tunnels to one VPN-base tunnel
- Tunnel-Sequence Label of the U-Plane tree rooted at
some egress-PE of some specific VPN
The extensions of LDP, RSVP-TE and MP-BGP may be done such
generalized that this scenario is covered as well.
Hummel,Grimminger Nov. 2001 [Page 8]
mp2p Tunnel sequence trees Exp. May 2002
6 Conclusion, outlook
By relatively small protocol extensions (LDP, RSVP-TE, MP-BGP) the
notorious N-Square Problem would be eliminated once and forever:
Signalling would catch up with what the Label Stack paradigma has
promised since the beginning of MPLS.
Network(PE)-based VPNs as well as CE-based VPN may benefit immensely.
But other applications/scenarios (typically overlay scenarios) may
benefit as well. For instance, MPOA, the ATM Forum's Overlay models
could reduce its n-square number of SVCs by introducing hierarchical
multipoint-to-point SVCs as well.
7 Intellectual Property Considerations
This proposal in is full conformity with [RFC-2026].
Siemens may have patent rights on technology described in this
document which employees of Siemens contribute for use in IETF
standards discussions. In relation to any IETF standard incorporating
any such technology, Siemens hereby agrees to license on fair,
reasonable and non-discriminatory terms, based on reciprocity, any
patent claims it owns covering such technology, to the extent such
technology is essential to comply with such standard.
8 References
[1] H.Hummel (Siemens AG): Tree/Ring/Meshy VPN tunnel systems
draft-hummel-ppvpn-tunnel-systems-00.txt
8 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
Hummel,Grimminger Nov. 2001 [Page 9]
mp2p Tunnel sequence trees Exp. May 2002
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,Grimminger Nov. 2001 [Page 10]