PPVPN Working Group Heinrich Hummel
Internet Draft Siemens AG
Expiration Date: October 2001
March 2001
Tree/Ring/Meshy VPN tunnel systems
draft-hummel-ppvpn-tunnel-systems-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.
Abstract
This draft shows how n sites of a private network may be
interconnected by n-1 shortest (L2/L3)-tunnels that form a minimal
tree tunnel system, or by n fairly shortest tunnels that form a ring
tunnel system. Algorithms are provided for computing such tree/ring
tunnel systems within a fraction of a second. Analogous variants
thereof may be used to determine tree/ring tunnel systems for
interconnecting all member VPNs of a VPN alliance. Tunnel weights
may either pursue the optimal use of carrier resources or the minimal
monetary costs for the customer. Explicit routing mechanisms are
proposed for establishing/ testing/ tearing down entire VPN-tunnel
systems of arbitrary topology (trees, rings, meshes).
Hummel March 2001 [Page 1]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
1 Introduction, Requirements
This contribution deals with computing, establishing and testing of
L2/L3-VPN tunnel systems that interconnect the sites of a VPN, resp.
the VPNs of a VPN alliance.
It shows how a tunnel system may be determined which interconnects n
nodes (sites, alliance member VPNs) by n-1 shortest tunnels =
Minimal Tree Tunnel System.
It also shows how a ring tunnel system may be determined which
interconnects n nodes (sites, alliance member VPNs) by n fairly
shortest tunnels without checking (n-1)! candidate ring arrangements
as known from the traveling salesman problem.
Furthermore the idea is shown how to send out tunnel
establishment/termination messages, navigated by Enhanced Explicit
Routing Information which corresponds to the given set of tunnels
(which may form a tree, a ring or any mesh graph). In this way the
entire VPN tunnel system may be deployed full automatically.
Analogously, the idea is shown how to send STATUS ENQUIRY messages,
navigated again by Enhanced Explicit Routing Information,
through/along all established tunnels (which may form a tree, a ring
or any mesh graph) as to test whether the tunnel systems is still
functioning.
2 Computing VPN tunnel systems
The Virtual Router VPN Model employs PE-to-PE tunnels whereas the
Layer-2 VPN model employs tunnels from CE to shining CE. PE-to-PE
tunnels are only subject for provider provisioned VPNs. CE-to-CE
tunnels may be employed not only in provider provisioned VPNs, but
also in customer-based VPNs.
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 2.1 and 2.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)
Hummel March 2001 [Page 2]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
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.
2.1 Computing Minimal Tree VPN tunnel systems
The minimal number of 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 tunnels. Among them we select those n-1 tunnels of smallest
weight which form a contiguous tunnel system that indeed does
interconnect all n sites.
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.
2.2 Computing Optimal Ring VPN tunnel systems
n sites = nodes shall be interconnected by n VPN tunnels which form a
ring while the weight sum of these tunnels is fairly minimal. The
main advantages of a ring structure are, that all nodes will still
be interconnected if any single tunnel breaks, and that the forward +
Hummel March 2001 [Page 3]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
backward bandwidth capacity of the tunnels can be utilized best.
According to the Travelling Salesman Problem (n-1)! candidate ring
arrangements need to be checked in order to select the one of minimal
weight sum. If n is equal to let's say 100 the exact computation may
take thousands of years. However the following algorithm will provide
an acceptable best result within a fraction of a second.
It's goal: 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:
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
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.
2.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 configurational additions to
a computed tree or ring graph.
2.4 Computing Ring/Tree inter-VPN tunnel systems for VPN alliances
n VPNs may want to form a VPN alliance. A respective inter alliance
member VPN tunnel system may have to be computed, which may either be
a minimal tree or an optimal ring. Above algorithms may be used in
analogy whereby each VPN is an "abstract node/abstract site".
2.5 Further considerations and requirements
If a tunnel system is to be computed based on weight definition a) or
b) we certainly need to know the routes of all candidate tunnels.
This information plus the weight values themselves may eventually be
Hummel March 2001 [Page 4]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
provided by OSPF, IS-IS, or static info. However, in case all these
routes are BGP-routes, it will be necessary to query from any
candidate site all its best routes to all other sites of the same
VPN. This constitutes the requirement to standardize respective query
and response messages.
3 Establishing/testing/tearing down VPN tunnel systems
Requirements as well as procedural specifications shall be developped
with respect to a process for establishing/testing/tearing down
total/partial VPN tunnel systems.
One way of handling is to establish/test/tear down any VPN tunnel
individually. Another, more automated method is, to
establish/test/tear down a set of VPN tunnels (e.g. all tunnels of a
particular VPN) in one stroke.
Indeed it is possible to compute an explicit source routing
information with respect to a given arbitrarily structured VPN tunnel
system (tree, ring , meshy graph) which may be used to navigate along
all the routes of these tunnels. Appropriate syntax may be defined
for all kind of tunnels (IPSEC, GRE, MPLS) i.e. where we know or
where we don't know the routes of the tunnels.
In the following it is assumed that CR-LDP tunnels shall be built,
i.e. where we know the routes of the tunnels. Important however is
the basic mechanism how to enlist all tunnels of a meshy tunnel
graph. It resembles a person who eats spaghetti and tries to get all
of them onto his fork. Will say: In principle it applies to RSVP-TE,
IPSEC, GRE, and IP in IP tunnels as well.
The source routing information may be composed of multiples of
Explicit-Route TLVs, each of which represents exactly one tunnel, as
well as of intermingled "("- and ")"-Meta-language TLVs which
indicate the structure of the meshy tunnel system. Furthermore opaque
container- TLVs may adequately be intermingled such that all routers
that are involved in a particular tunnel can be made aware of the
therein contained information (like bandwidth info for that tunnel)
. When received by any transit router the explicit source routing
information can be processed such that this transit router recognizes
all actions to be done by himself and which portion of the received
information must be forwarded to which of eventually multiples of
succeeding routers.
Hummel March 2001 [Page 5]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
See the following diagram:
1------T1-----2-----T4-------------3
| | ---------|
| | |
| T3 T5
| | |
----T2--------4-----T6---5
A tunnel system is shown which consists of tunnels T1,...,T6.
T1 connects site 1 and site 2.
T2 connects site 1 and site 4.
T3 connects site 2 and site 4.
T4 connects site 2 and site 3.
T5 connects site 3 and site 5.
T6 connects site 4 and site 5.
Tunnel T5 shares some transit routers with tunnel T4. The message
is: This is as normal as if there were no common transit routers: no
special treatment! No confusion is appropriate when the same router's
ER-HOP TLV shows up in more than one ER-TLVs.
At the root node (= site 1) we compute an explicit source routing
information by the following recursive procedure
(buildMeshyRouteTree). Initially all tunnels are marked "regard"
rather than "disregard". Also initially: the source routing
information is empty. We call the recursive procedure with "root"
(here = site 1) as parameter:
buildMeshyRouteTree (root);
The procedure is defined as follows:
buildMeshyRouteTree (current_node)
{ loop 1: over all tunnels adjacent to current_node: among them
identify all tunnels (at current nesting level) which are marked
"regard" and mark them "disregard"; end of loop 1;
loop 2 "over all such identified links: add to the source routing
information: - "(" -TLV, only if there are more than one identified
tunnels - ER-TLV for this current tunnel
buildMeshyRouteTree (remote node of current tunnel) - ")" -TLV,
only if there are more than one identified tunnels end of loop 2; }
The VPN tunnel system consists of tunnels T1, ...,T6.
Hummel March 2001 [Page 6]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
The procedure buildMeshyRouteTree produces the following source
routing information:
"(", ER[T1], "(", ER[T4], ER[T5], ER[T6], ")",
"(", ER[T3] , ")",
"(", ER[T2] ")"
i.e. multiples of "("-TLVs, ")"-TLVs, and Explicit -Route-TLVs,
which may be integrated in a respective source routing TLV
Relatively simple rules for processing the source routing information
at each tunnel endpoint may take care that the source routing
information as received by any tunnel endpoint node is properly
processed, i.e. in particular is adequately split when forwarded.
This mechanism complies with a concept once presented in draft-
hummel-mpls-explicit-tree-01.txt.
Testing: A STATUS ENQUIRY message may be forwarded along all VPN
tunnel routes based on such explicit source routing information. In
case it cannot be forwarded as dictated by the source routing
information a failure is detected. Hereby and in addition: Each
tunnel end node may be supposed to return a STATUS message back to
the respective tunnel start node as to acknowledge the STATUS
ENQUIRY message. If such a STATUS message is not received within a
time limit at the tunnel start node a failure will be detected as
well.
Tearing down: Similarily the VPN tunnel system may either be torn
down tunnel by tunnel by separate actions and/or as a whole in one
stroke.
4 Conclusion
An operation & maintainance process for establishing /testing/
tearing down VPN tunnel systems should be outlined in the framework
document which allows/enables/supports what is presented by this
draft. Appropriate sections of [2] are:
Section 5. VPN Establishment and Maintenance
Section 6.2 Tunnel Establishment
5 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
Hummel March 2001 [Page 7]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
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.
6 References
[1] M. Suzuki and J. Sumimoto (NTT):
A Framework for Network-based VPNs,
draft-suzuki-nbvpn-framework-02.txt
[2] R. Callon (Juniper Networks) et. all:
Outline for A Framework for Network Based Virtual Private Networks,
draft-callon-nbvpn-outline-00.txt
[3] Hummel (Siemens)and Loke (Nortel Networks): "Explicit Tree Routing",
draft-hummel-mpls-explicit-tree-01.txt, June 1999
[4] Bilel Jamoussi (Nortel Networks) et all: "Constraint-Based LSP Setup
using LDP", draft-ietf-mpls-cr-ldp-04.txt
7 Author's Address
Heinrich Hummel
Siemens AG
Hofmannstrasse 51
81379 Munich, Germany
Tel: +49 89 722 32057
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.
Hummel March 2001 [Page 8]
Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
Hummel March 2001 [Page 9]