PPVPN Working Group Heinrich Hummel
Internet Draft Siemens AG
Expiration Date: February 2002
July 2001
Tree/Ring/Meshy VPN tunnel systems
draft-hummel-ppvpn-tunnel-systems-01.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.
Abstract
Version 01 is a significant redesign. Exclusive full mesh (EFM)
intersite tunneling per VPN is considered as overkill. Options for
optimizations are discussed and compared:
a) Shared full mesh (SFM)
b) Exclusive partial mesh per VPN (EPM)
c) Shared partial mesh (SPM)
This draft favors partial mesh (EPM, SPM) but cautions from pursuing
SPM (complexity, further study needed).
The draft also contains algorithms for computing minimal/optimal
tree/ring/mesh inter-site tunnel topologies.
The establishment of partial mesh MPLS tunnel systems is removed and
will be subject for a separate draft.
Hummel July 2001 [Page 1]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
1 Introduction
This draft deals with full mesh versus partial mesh intersite VPN
tunneling.
Full mesh does not mean that there is a tunnel from site S to site D
even if no traffic is expected from S to D. However, in case some
traffic is expected from S to D, then there is a direct tunnel from S
to D.
Partial mesh means a set of tunnels via which all sites are
interconnected- either directly or indirectly. In general, a sequence
of tunnels is to be passed when data flows from site S to site D.
Exclusive full mesh (EFM) intersite tunneling per VPN is overkill.
Optimization options are:
a) Shared full mesh (SFM): Share PE-to-PE tunnels among different
VPNs where applicable.
b) Exclusive partial mesh per VPN (EPM): Use PE-to-PE-to-PE resp.
CE-to-CE-to-CE tunnel sequences exclusively for the traffic of one
particular VPN.
c) Shared partial mesh (SPM): Share PE-to-PE-to-PE tunnel sequences
among different VPNs where applicable.
Though all known IP VPN models mention b) as a viable option they
rather concentrate on a): Notice the backbone virtual router in the
VR-model, notice the BGP-transmitted label in RFC2547bis being called
the "second label" - it would be the "third label" if option b)
applied.
This draft is focussed on partial mesh and its advantages over full
mesh (see section 2 and 3). Therefore it favors options b) and c).
However a cautioning warning against c) is appropriate: you may loose
something while trying to get everything, and also, it is complex and
needs further study.
Section 3 contains algorithms for computing minimal/optimal
tree/ring/mesh inter-site tunnel topologies.
The establishment of partial mesh MPLS tunnel systems is removed and
will be subject for a separate draft.
Hummel July 2001 [Page 2]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
2 Savings of tunnels: Minimal partial mesh versus full mesh
Full mesh topologies for interconnecting n sites either require
n*(n-1) uni-directional tunnels or n*(n-1)/2 bi-directional tunnels.
For comparison, minimal but contiguous topologies require either n
uni-directional tunnels which form a ring or n-1 bi-directional
tunnels which form a (meshless) tree.
In the first i.e. uni-direction case, the absolute savings are n*(n-
1)-n =n*(n-2) tunnels while the relative savings are [n*(n-1)-
n]/[n*(n-1)] = 100*(n-2)/(n-1) %.
In the second i.e. bi-direction case, the absolute savings are n*(n-
1)/2-(n-1) = (n-1)*(n-2)/2 tunnels while the relative savings are
[n*(n-1)/2-(n-1)]/[n*(n-1)/2] = 100*(n-2)/ n %.
The absolute and relative savings S-abs and S-rel in terms of tunnels
compared with full mesh is exorbitant:
Uni-directional ring:
n=11; S-abs= 99 tunnels; S-rel =90 %
n=101; S-abs= 9,999 tunnels; S-rel =99 %
n=1001; S-abs= 999,999 tunnels; S-rel =99.9 %
Bi-directional tree:
n=10; S-abs= 36 tunnels; S-rel =80 %
n=100; S-abs= 9,702 tunnels; S-rel =98 %
n=1000; S-abs= 997,002 tunnels; S-rel =99.8 %
3 Partial mesh versus full mesh
Diverse traffic engineering aspects are discussed from the "partial
versus full mesh" point of view.
3.1 Admission Control
Exclusive Partial Mesh (EPM):
In the attempt to add a further VPN, EPM enables "VPN Admission
Control" as to maintain the promised quality with respect to all
previously established VPNs as well as w.r.t. the actual VPN which is
about to be established. It may be an iterative process to determine
all the tunnels of the partial, VPN-dedicated mesh and also all their
routes such that the requested and eventually aggregated traffic
bandwidth is reserved on each physical link of each determined
tunnel.
Hummel July 2001 [Page 3]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
Shared Full Mesh (SFM):
The attempt to add a further VPN, may impact some existing (shared)
PE-to-PE tunnel and/or require the establishment of some new PE-to-PE
tunnel: Hereby the requested bandwidth reservation may either be
successful or may fail.
Shared Partial Mesh (SPM):
The attempt to add a further VPN, may impact some existing (shared)
PE-to-PE-to-PE tunnel sequence and/or require the establishment of
some new PE-to-PE-to-PE tunnel sequence: Hereby the requested
bandwidth reservation may either be successful or may fail. (Of
course, such a tunnel sequence may also consists of one single tunnel
as well).
3.2 VPN-specific Traffic Policing
Only EPM allows for VPN-specific traffic policing.
3.3 Multiple routes
The immense tunnel savings in case of MINIMAL partial mesh as shown
in section 2 allow some luxury, i.e a few more tunnels, so that
services like traffic balancing, fast path restoration or traffic-
type/Qos-specific traffic multiplexing can be supported. The
resulting number of tunnels would still be from the order of n and
would still yield a partial mesh.
3.3.1 Fast path protection
In the full mesh case, though there are n*(n-1) uni-dir. tunnels, no
fast path protection mechanism can be provided for some traffic
stream in case one of their links would break. However, if you have
only 2*n uni-dir.tunnels that form two inversive rings, then an
alternative route between any pair of sites would always be available
in case one of their links is broken. To match this capability the
full mesh needs to be doubled i.e. needs 2*n*(n-1) tunnels.
3.3.2 Traffic-type/Qos-specific traffic multiplexing
Assume there should be x completely different tunnels resp. tunnel
sequences for any site-to-site communication, e.g. one tunnel per
traffic-type (voice, data,...) resp. per QoS-class. In the full mesh
case, x*n*(n-1) tunnels were required. In the partial mesh case, x*n
tunnels were required.
Hummel July 2001 [Page 4]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
3.3.3 Traffic balancing
Assume there should be x alternate routes for any site-to-site
communication for reasons of traffic balancing. In a full mesh
x*n*(n-1) tunnels were required. In a partial mesh not more than x*n
tunnels were required. There may be even less, if the alternate
routes may have partially shared route sections.
3.4 Customer-based VPN and Layer-2 provider-provisioned VPN
Customer-based VPNs, whereby the service provider is completely
unaware of what is the purpose of any traversing CE-to-CE tunnels,
can only be optimized by EPM, i.e not by SFM and not by SPM.
The same is true for provider-provisioned CE-to-CE tunnels (i.e. for
Layer-2 provider-provisioned VPN).
3.5 VPN Multicast
In this section VPN multicast is evaluated from the resource taking
prospective.
Shared and Exclusive Full Mesh (SFM and EM): A general goal of
multicast is to employ a (tree-like) delivery channel as to avoid
multiple transmission over the same physical links. This goal is not
supported at all in case of full mesh models like EFM and SFM.
Indeed, at the source-PE the multicast data must be forwarded as
often as there are destination-PEs. None of these flows is ever
branched on its way to its destination-PE.
Solution favored by E.Rosen in [2]: That solution essentially
favors one multicast tree per VPN or one per suitable set of VPNs
(Multicast domain). All multicast applications within the VPN shall
forward the multicast packets along that tree to ALL respective PEs -
even in case there are no receivers on some of the sites (so that the
packet has to be discarded). This solution requires P-routers'
involvement and multicast trees in additon (!!!) to the tunnels for
point-to-point traffic.
Exclusive Partial Mesh (EPM): The exclusive partial mesh which is
already provided for point-to-point traffic can be utilized also for
multicast. The P-router stays completely VPN-unaware.
Hummel July 2001 [Page 5]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
4 Computing partial mesh topologies
The intersite tunnels may be CE-to-CE (L2vpn, customer-based VPNs) or
PE-to-PE (RFC2547bis, Virtual Router).
Tunnels may have associated weight values:
a) Weight= number of hops
b) Weight= 1/traffic load between its endpoint nodes
c) Weight= Price taken from a Least-Cost-Routing table, structured
according to service providers, time-of-day/day-of-week time
zones, distance zones, direction of tunnel establishment,
anticipated tunnel lifetime, etc.
VPN tunnel computation according to 4.1 and 4.2 may either be done in
awareness of the carrier network's topology ( weight according to a)
or b) may apply ) or without that awareness (weight according to c)
may apply ). A customer who computes a VPN tunnel system based on
weight definition c) may order the resulting VPN tunnel system at the
right service provider(s), e.g. by post-mail, or order it based on
user signalling (i.e. the service provider becomes aware of what will
be established), or establish it all by himself based on user
signalling such that the service provider is not informed about the
purpose of the established tunnels. All respective signalling details
should be described and provided by the IETF.
4.1 Computing Minimal Tree VPN tunnel systems
The minimal number of bi-directional tunnels for interconnecting n
sites is n-1. In a full-meshed VPN tunnel system n sites will be
interconnected by n*(n-1)/2 bi-directional tunnels. Among them we
select those n-1 tunnels of smallest weight which contiguously
interconnect all n sites. They will form a tree-like topology.
In case of uni-directional tunnels the full mesh configuration will
require n*(n-1) tunnels. Among them we need to select those n-1 pairs
of inverse tunnels whose weights (for the total pair) are smallest
and which still form a contiguous topology.
The following algorithm selects n-1 bi-directional tunnels which form
a tree-like topology. Minor modification were only necessary as to
build an algorithm which selected n-1 pairs of inverse, uni-
directional tunnels that form a tree-like topology as well.
Hummel July 2001 [Page 6]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
Start of algorithm:
We have sorted all n*(n-1)/2 candidate tunnels in ascending order
according to their weights and have all of them marked REGARD rather
than DISREGARD.
We start with an empty tunnel system and with n separated
subnetworks, each of which initially contains just one site=node
without any tunnel link. In each of the following iteration step we
will combine any two so far separate subnetworks by a particular
interconnecting tunnel (which will be added to the tunnel system) and
repeat the step n-1 times as to get one contiguous subnetwork and
consequently one contiguous tunnel system.
Iteration step:
Take the tunnel of smallest weight which is marked REGARD and add it
to the tunnel system. Mark this tunnel to DISREGARD. Build the
combined subnetwork out of those two subnetworks A and B which are
interconnected by the taken tunnel. Mark DISREGARD all tunnels which
start at a node in A and end at a node in B.
Result: We have determined a Minimal Tree VPN tunnel system, which
interconnects all n sites by the least number of shortest tunnels.
4.2 Computing Optimal Ring VPN tunnel systems
The following algorithms A and B select n bi-directional tunnels
which form a ring while their weight sum is fairly minimal.
Analogous tasks: Select n uni-directional tunnels resp. n pairs of
inverse, uni-directional tunnels which form a ring as well.
Note that both algorithms are of order n, and not of order n!, with
respect to the number of iterations.
Goal of algorithm A: Form a ring such that as often as possible two
nodes become immediate neighbors if the respective interconnecting
tunnel has a smallest weight; furthermore such, that as often as
possible two nodes become 2nd (3rd, 4th,..) degree neighbors, if the
respective interconnecting tunnel string has a smallest weight sum.
Algorithm A:
Start with an empty tunnel system and n tunnel strings Si .Each Si
has weight Wi =0, contains just 1 node which is both Left- and Right
tunnel string border node.
Build n-2 times combined tunnel strings Si&k, by concatenating the
Hummel July 2001 [Page 7]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
strings Si and Sk by their shortest interconnecting tunnel. In each
step, search for those two tunnel strings Si and Sk , which yield the
smallest weightsum: Wi&k =Wi +Wk + Weight of connecting Tunnel.
Hereby determine out of (maximal) 4 candidates that tunnel of
smallest Weight; and also the two new border nodes of tunnel string
Si&k.
Add the shorter final tunnel pair to the tunnel system as to close
the ring.
Algorithm B: Add step by step one further node (site) to the ring
which initially contains any two nodes. Each time insert the
new,arbitrarily chosen node Z between those nodes X and Y for which
is true: ABS (weight for tunnel X-Z + weight for tunnel Z-Y - weight
for tunnel X-Y) is smallest.
There are certainly more such algorithms, see also [5, 6 ].
4.3 Forming VPN tunnel systems of arbitrarily meshed graph
VPN tunnel systems of arbitrarily meshed graph may be formed e.g.
based on pure configuration or based on some algorithms like the
following algorithm:
Spend a direct tunnel between any two nodes, if the traffic,
exchanged between them, exceeds some limit. As a result you may get
m tunnel-and-node fragments, 1 <= m <= n. Some of them may form some
meshes, or may form some trees, or may still be isolated nodes (i.e.
without any tunnel).
Interconnect these fragments by a minimal tree topology (apply
algorithm A) or by a minimal ring topology (apply algorithm B).
Hereby, each fragment is an initial "node" according to the algorithm
description.
5 Summary and proposals
The draft clearly shows the value/advantages of partial mesh VPN
tunneling. The editors of the ppvpn-documents may take this into
consideration.
6 Intellectual Property Considerations
This proposal in is full conformity with [RFC-2026].
Hummel July 2001 [Page 8]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
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.
7 References
[1] Eric Rosen (Cisco) RFC 2547bis,
draft-rosen-rfc2547bis-03.txt
[2] Eric Rosen (Cisco) : Multicast in MPLS/BGP VPNs
draft-rosen-vpn-mcast-00.txt
[3] RFC2917: A Core MPLS IP VPN Architecture
[4] Kampella (Juniper Networks): MPLS-based Layer 2 VPNs
draft-kompella-mpls-l2vpn-02.txt
[5] Walid Ben-Ameur and Bernard Liau, Computing Internet routing
metrics; Annals of telecommunications (April 2001)
[6] Walid Ben-Ameur, Nicolas Michel and Bernard Liau, Routing Strategie
for IP networks; Telektronikk magazine, 2001
[7] Tissa Senevirathne (Force10) : Use of Partial meshed tunnels
to achieve forwarding behavior of full meshed tunnels
draft-tsenevir-l2vpn-pmesh-00.txt
[8] Tissa Senevirathne(Nortel),Waldemar Augustyn (Nortel),
Pascal Menezes (TeraBeam):
A Framework for Virtual Metropolitan Internetworks (VMI)
draft-senevirathne-vmi-frame-01.txt
8 Author's Address
Heinrich Hummel
Siemens AG
Hofmannstrasse 51
81379 Munich, Germany
Tel: +49 89 722 32057
Hummel July 2001 [Page 9]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
Email: heinrich.hummel@icn.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
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 July 2001 [Page 10]