idnits 2.17.1 draft-hummel-ppvpn-tunnel-systems-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 9 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 10 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 4 instances of too long lines in the document, the longest one being 3 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 29 has weird spacing: '...ificant redes...' == Line 60 has weird spacing: '...l sites are...' == Line 74 has weird spacing: '... models menti...' == Line 96 has weird spacing: '...n sites eithe...' == Line 98 has weird spacing: '...ologies requi...' == (16 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 2001) is 8311 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'RFC-2026' on line 375 == Unused Reference: '1' is defined on line 389, but no explicit reference was found in the text == Unused Reference: '3' is defined on line 395, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 397, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 400, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 403, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 406, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 410, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-rosen-rfc2547bis-03 -- Possible downref: Normative reference to a draft: ref. '1' == Outdated reference: A later version (-15) exists of draft-rosen-vpn-mcast-00 ** Downref: Normative reference to an Historic draft: draft-rosen-vpn-mcast (ref. '2') ** Downref: Normative reference to an Informational RFC: RFC 2917 (ref. '3') -- Possible downref: Normative reference to a draft: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Normative reference to a draft: ref. '7' == Outdated reference: A later version (-02) exists of draft-senevirathne-vmi-frame-01 -- Possible downref: Normative reference to a draft: ref. '8' Summary: 11 errors (**), 0 flaws (~~), 19 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 PPVPN Working Group Heinrich Hummel 2 Internet Draft Siemens AG 3 Expiration Date: February 2002 5 July 2001 7 Tree/Ring/Meshy VPN tunnel systems 8 draft-hummel-ppvpn-tunnel-systems-01.txt 10 Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet- 17 Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet- Drafts as reference 21 material or to cite them other than as "work in progress." 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 24 The list of Internet-Draft Shadow Directories can be accessed at 25 http://www.ietf.org/shadow.html. 27 Abstract 29 Version 01 is a significant redesign. Exclusive full mesh (EFM) 30 intersite tunneling per VPN is considered as overkill. Options for 31 optimizations are discussed and compared: 33 a) Shared full mesh (SFM) 35 b) Exclusive partial mesh per VPN (EPM) 37 c) Shared partial mesh (SPM) 39 This draft favors partial mesh (EPM, SPM) but cautions from pursuing 40 SPM (complexity, further study needed). 42 The draft also contains algorithms for computing minimal/optimal 43 tree/ring/mesh inter-site tunnel topologies. 45 The establishment of partial mesh MPLS tunnel systems is removed and 46 will be subject for a separate draft. 48 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 50 1 Introduction 52 This draft deals with full mesh versus partial mesh intersite VPN 53 tunneling. 55 Full mesh does not mean that there is a tunnel from site S to site D 56 even if no traffic is expected from S to D. However, in case some 57 traffic is expected from S to D, then there is a direct tunnel from S 58 to D. 60 Partial mesh means a set of tunnels via which all sites are 61 interconnected- either directly or indirectly. In general, a sequence 62 of tunnels is to be passed when data flows from site S to site D. 64 Exclusive full mesh (EFM) intersite tunneling per VPN is overkill. 65 Optimization options are: 66 a) Shared full mesh (SFM): Share PE-to-PE tunnels among different 67 VPNs where applicable. 68 b) Exclusive partial mesh per VPN (EPM): Use PE-to-PE-to-PE resp. 69 CE-to-CE-to-CE tunnel sequences exclusively for the traffic of one 70 particular VPN. 71 c) Shared partial mesh (SPM): Share PE-to-PE-to-PE tunnel sequences 72 among different VPNs where applicable. 74 Though all known IP VPN models mention b) as a viable option they 75 rather concentrate on a): Notice the backbone virtual router in the 76 VR-model, notice the BGP-transmitted label in RFC2547bis being called 77 the "second label" - it would be the "third label" if option b) 78 applied. 80 This draft is focussed on partial mesh and its advantages over full 81 mesh (see section 2 and 3). Therefore it favors options b) and c). 82 However a cautioning warning against c) is appropriate: you may loose 83 something while trying to get everything, and also, it is complex and 84 needs further study. 86 Section 3 contains algorithms for computing minimal/optimal 87 tree/ring/mesh inter-site tunnel topologies. 89 The establishment of partial mesh MPLS tunnel systems is removed and 90 will be subject for a separate draft. 92 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 94 2 Savings of tunnels: Minimal partial mesh versus full mesh 96 Full mesh topologies for interconnecting n sites either require 97 n*(n-1) uni-directional tunnels or n*(n-1)/2 bi-directional tunnels. 98 For comparison, minimal but contiguous topologies require either n 99 uni-directional tunnels which form a ring or n-1 bi-directional 100 tunnels which form a (meshless) tree. 102 In the first i.e. uni-direction case, the absolute savings are n*(n- 103 1)-n =n*(n-2) tunnels while the relative savings are [n*(n-1)- 104 n]/[n*(n-1)] = 100*(n-2)/(n-1) %. 106 In the second i.e. bi-direction case, the absolute savings are n*(n- 107 1)/2-(n-1) = (n-1)*(n-2)/2 tunnels while the relative savings are 108 [n*(n-1)/2-(n-1)]/[n*(n-1)/2] = 100*(n-2)/ n %. 110 The absolute and relative savings S-abs and S-rel in terms of tunnels 111 compared with full mesh is exorbitant: 112 Uni-directional ring: 113 n=11; S-abs= 99 tunnels; S-rel =90 % 114 n=101; S-abs= 9,999 tunnels; S-rel =99 % 115 n=1001; S-abs= 999,999 tunnels; S-rel =99.9 % 117 Bi-directional tree: 118 n=10; S-abs= 36 tunnels; S-rel =80 % 119 n=100; S-abs= 9,702 tunnels; S-rel =98 % 120 n=1000; S-abs= 997,002 tunnels; S-rel =99.8 % 122 3 Partial mesh versus full mesh 124 Diverse traffic engineering aspects are discussed from the "partial 125 versus full mesh" point of view. 127 3.1 Admission Control 129 Exclusive Partial Mesh (EPM): 131 In the attempt to add a further VPN, EPM enables "VPN Admission 132 Control" as to maintain the promised quality with respect to all 133 previously established VPNs as well as w.r.t. the actual VPN which is 134 about to be established. It may be an iterative process to determine 135 all the tunnels of the partial, VPN-dedicated mesh and also all their 136 routes such that the requested and eventually aggregated traffic 137 bandwidth is reserved on each physical link of each determined 138 tunnel. 140 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 142 Shared Full Mesh (SFM): 144 The attempt to add a further VPN, may impact some existing (shared) 145 PE-to-PE tunnel and/or require the establishment of some new PE-to-PE 146 tunnel: Hereby the requested bandwidth reservation may either be 147 successful or may fail. 149 Shared Partial Mesh (SPM): 151 The attempt to add a further VPN, may impact some existing (shared) 152 PE-to-PE-to-PE tunnel sequence and/or require the establishment of 153 some new PE-to-PE-to-PE tunnel sequence: Hereby the requested 154 bandwidth reservation may either be successful or may fail. (Of 155 course, such a tunnel sequence may also consists of one single tunnel 156 as well). 158 3.2 VPN-specific Traffic Policing 160 Only EPM allows for VPN-specific traffic policing. 162 3.3 Multiple routes 164 The immense tunnel savings in case of MINIMAL partial mesh as shown 165 in section 2 allow some luxury, i.e a few more tunnels, so that 166 services like traffic balancing, fast path restoration or traffic- 167 type/Qos-specific traffic multiplexing can be supported. The 168 resulting number of tunnels would still be from the order of n and 169 would still yield a partial mesh. 171 3.3.1 Fast path protection 173 In the full mesh case, though there are n*(n-1) uni-dir. tunnels, no 174 fast path protection mechanism can be provided for some traffic 175 stream in case one of their links would break. However, if you have 176 only 2*n uni-dir.tunnels that form two inversive rings, then an 177 alternative route between any pair of sites would always be available 178 in case one of their links is broken. To match this capability the 179 full mesh needs to be doubled i.e. needs 2*n*(n-1) tunnels. 181 3.3.2 Traffic-type/Qos-specific traffic multiplexing 183 Assume there should be x completely different tunnels resp. tunnel 184 sequences for any site-to-site communication, e.g. one tunnel per 185 traffic-type (voice, data,...) resp. per QoS-class. In the full mesh 186 case, x*n*(n-1) tunnels were required. In the partial mesh case, x*n 187 tunnels were required. 189 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 191 3.3.3 Traffic balancing 193 Assume there should be x alternate routes for any site-to-site 194 communication for reasons of traffic balancing. In a full mesh 195 x*n*(n-1) tunnels were required. In a partial mesh not more than x*n 196 tunnels were required. There may be even less, if the alternate 197 routes may have partially shared route sections. 199 3.4 Customer-based VPN and Layer-2 provider-provisioned VPN 201 Customer-based VPNs, whereby the service provider is completely 202 unaware of what is the purpose of any traversing CE-to-CE tunnels, 203 can only be optimized by EPM, i.e not by SFM and not by SPM. 205 The same is true for provider-provisioned CE-to-CE tunnels (i.e. for 206 Layer-2 provider-provisioned VPN). 208 3.5 VPN Multicast 210 In this section VPN multicast is evaluated from the resource taking 211 prospective. 213 Shared and Exclusive Full Mesh (SFM and EM): A general goal of 214 multicast is to employ a (tree-like) delivery channel as to avoid 215 multiple transmission over the same physical links. This goal is not 216 supported at all in case of full mesh models like EFM and SFM. 217 Indeed, at the source-PE the multicast data must be forwarded as 218 often as there are destination-PEs. None of these flows is ever 219 branched on its way to its destination-PE. 221 Solution favored by E.Rosen in [2]: That solution essentially 222 favors one multicast tree per VPN or one per suitable set of VPNs 223 (Multicast domain). All multicast applications within the VPN shall 224 forward the multicast packets along that tree to ALL respective PEs - 225 even in case there are no receivers on some of the sites (so that the 226 packet has to be discarded). This solution requires P-routers' 227 involvement and multicast trees in additon (!!!) to the tunnels for 228 point-to-point traffic. 230 Exclusive Partial Mesh (EPM): The exclusive partial mesh which is 231 already provided for point-to-point traffic can be utilized also for 232 multicast. The P-router stays completely VPN-unaware. 234 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 236 4 Computing partial mesh topologies 238 The intersite tunnels may be CE-to-CE (L2vpn, customer-based VPNs) or 239 PE-to-PE (RFC2547bis, Virtual Router). 241 Tunnels may have associated weight values: 242 a) Weight= number of hops 244 b) Weight= 1/traffic load between its endpoint nodes 246 c) Weight= Price taken from a Least-Cost-Routing table, structured 247 according to service providers, time-of-day/day-of-week time 248 zones, distance zones, direction of tunnel establishment, 249 anticipated tunnel lifetime, etc. 251 VPN tunnel computation according to 4.1 and 4.2 may either be done in 252 awareness of the carrier network's topology ( weight according to a) 253 or b) may apply ) or without that awareness (weight according to c) 254 may apply ). A customer who computes a VPN tunnel system based on 255 weight definition c) may order the resulting VPN tunnel system at the 256 right service provider(s), e.g. by post-mail, or order it based on 257 user signalling (i.e. the service provider becomes aware of what will 258 be established), or establish it all by himself based on user 259 signalling such that the service provider is not informed about the 260 purpose of the established tunnels. All respective signalling details 261 should be described and provided by the IETF. 263 4.1 Computing Minimal Tree VPN tunnel systems 265 The minimal number of bi-directional tunnels for interconnecting n 266 sites is n-1. In a full-meshed VPN tunnel system n sites will be 267 interconnected by n*(n-1)/2 bi-directional tunnels. Among them we 268 select those n-1 tunnels of smallest weight which contiguously 269 interconnect all n sites. They will form a tree-like topology. 271 In case of uni-directional tunnels the full mesh configuration will 272 require n*(n-1) tunnels. Among them we need to select those n-1 pairs 273 of inverse tunnels whose weights (for the total pair) are smallest 274 and which still form a contiguous topology. 276 The following algorithm selects n-1 bi-directional tunnels which form 277 a tree-like topology. Minor modification were only necessary as to 278 build an algorithm which selected n-1 pairs of inverse, uni- 279 directional tunnels that form a tree-like topology as well. 281 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 283 Start of algorithm: 284 We have sorted all n*(n-1)/2 candidate tunnels in ascending order 285 according to their weights and have all of them marked REGARD rather 286 than DISREGARD. 288 We start with an empty tunnel system and with n separated 289 subnetworks, each of which initially contains just one site=node 290 without any tunnel link. In each of the following iteration step we 291 will combine any two so far separate subnetworks by a particular 292 interconnecting tunnel (which will be added to the tunnel system) and 293 repeat the step n-1 times as to get one contiguous subnetwork and 294 consequently one contiguous tunnel system. 296 Iteration step: 297 Take the tunnel of smallest weight which is marked REGARD and add it 298 to the tunnel system. Mark this tunnel to DISREGARD. Build the 299 combined subnetwork out of those two subnetworks A and B which are 300 interconnected by the taken tunnel. Mark DISREGARD all tunnels which 301 start at a node in A and end at a node in B. 303 Result: We have determined a Minimal Tree VPN tunnel system, which 304 interconnects all n sites by the least number of shortest tunnels. 306 4.2 Computing Optimal Ring VPN tunnel systems 308 The following algorithms A and B select n bi-directional tunnels 309 which form a ring while their weight sum is fairly minimal. 310 Analogous tasks: Select n uni-directional tunnels resp. n pairs of 311 inverse, uni-directional tunnels which form a ring as well. 313 Note that both algorithms are of order n, and not of order n!, with 314 respect to the number of iterations. 316 Goal of algorithm A: Form a ring such that as often as possible two 317 nodes become immediate neighbors if the respective interconnecting 318 tunnel has a smallest weight; furthermore such, that as often as 319 possible two nodes become 2nd (3rd, 4th,..) degree neighbors, if the 320 respective interconnecting tunnel string has a smallest weight sum. 322 Algorithm A: 324 Start with an empty tunnel system and n tunnel strings Si .Each Si 325 has weight Wi =0, contains just 1 node which is both Left- and Right 326 tunnel string border node. 328 Build n-2 times combined tunnel strings Si&k, by concatenating the 330 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 332 strings Si and Sk by their shortest interconnecting tunnel. In each 333 step, search for those two tunnel strings Si and Sk , which yield the 334 smallest weightsum: Wi&k =Wi +Wk + Weight of connecting Tunnel. 335 Hereby determine out of (maximal) 4 candidates that tunnel of 336 smallest Weight; and also the two new border nodes of tunnel string 337 Si&k. 339 Add the shorter final tunnel pair to the tunnel system as to close 340 the ring. 342 Algorithm B: Add step by step one further node (site) to the ring 343 which initially contains any two nodes. Each time insert the 344 new,arbitrarily chosen node Z between those nodes X and Y for which 345 is true: ABS (weight for tunnel X-Z + weight for tunnel Z-Y - weight 346 for tunnel X-Y) is smallest. 348 There are certainly more such algorithms, see also [5, 6 ]. 350 4.3 Forming VPN tunnel systems of arbitrarily meshed graph 352 VPN tunnel systems of arbitrarily meshed graph may be formed e.g. 353 based on pure configuration or based on some algorithms like the 354 following algorithm: 356 Spend a direct tunnel between any two nodes, if the traffic, 357 exchanged between them, exceeds some limit. As a result you may get 358 m tunnel-and-node fragments, 1 <= m <= n. Some of them may form some 359 meshes, or may form some trees, or may still be isolated nodes (i.e. 360 without any tunnel). 362 Interconnect these fragments by a minimal tree topology (apply 363 algorithm A) or by a minimal ring topology (apply algorithm B). 364 Hereby, each fragment is an initial "node" according to the algorithm 365 description. 367 5 Summary and proposals 369 The draft clearly shows the value/advantages of partial mesh VPN 370 tunneling. The editors of the ppvpn-documents may take this into 371 consideration. 373 6 Intellectual Property Considerations 375 This proposal in is full conformity with [RFC-2026]. 377 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 379 Siemens may have patent rights on technology described in this 380 document which employees of Siemens contribute for use in IETF 381 standards discussions. In relation to any IETF standard incorporating 382 any such technology, Siemens hereby agrees to license on fair, 383 reasonable and non-discriminatory terms, based on reciprocity, any 384 patent claims it owns covering such technology, to the extent such 385 technology is essential to comply with such standard. 387 7 References 389 [1] Eric Rosen (Cisco) RFC 2547bis, 390 draft-rosen-rfc2547bis-03.txt 392 [2] Eric Rosen (Cisco) : Multicast in MPLS/BGP VPNs 393 draft-rosen-vpn-mcast-00.txt 395 [3] RFC2917: A Core MPLS IP VPN Architecture 397 [4] Kampella (Juniper Networks): MPLS-based Layer 2 VPNs 398 draft-kompella-mpls-l2vpn-02.txt 400 [5] Walid Ben-Ameur and Bernard Liau, Computing Internet routing 401 metrics; Annals of telecommunications (April 2001) 403 [6] Walid Ben-Ameur, Nicolas Michel and Bernard Liau, Routing Strategie 404 for IP networks; Telektronikk magazine, 2001 406 [7] Tissa Senevirathne (Force10) : Use of Partial meshed tunnels 407 to achieve forwarding behavior of full meshed tunnels 408 draft-tsenevir-l2vpn-pmesh-00.txt 410 [8] Tissa Senevirathne(Nortel),Waldemar Augustyn (Nortel), 411 Pascal Menezes (TeraBeam): 412 A Framework for Virtual Metropolitan Internetworks (VMI) 413 draft-senevirathne-vmi-frame-01.txt 415 8 Author's Address 417 Heinrich Hummel 418 Siemens AG 419 Hofmannstrasse 51 420 81379 Munich, Germany 421 Tel: +49 89 722 32057 423 Tree/Ring/Meshy VPN tunnel systems Exp. Oct. 2001 425 Email: heinrich.hummel@icn.siemens.de 427 Full Copyright Statement 429 "Copyright (C) The Internet Society (March 2000). All Rights 430 Reserved. This document and translations of it may be copied and 431 furnished to others, and derivative works that comment on or 432 otherwise explain it or assist in its implmentation may be prepared, 433 copied, published and distributed, in whole or in part, without 434 restriction of any kind, provided that the above copyright notice and 435 this paragraph are included on all such copies and derivative works. 436 However, this document itself may not be modified in any way, such as 437 by removing the copyright notice or references to the Internet 438 Society or other Internet organizations, except as needed for the 439 purpose of developing Internet standards in which case the procedures 440 for copyrights defined in the Internet Standards process must be 441 followed, or as required to translate it into languages other than 442 English. 444 The limited permissions granted above are perpetual and will not be 445 revoked by the Internet Society or its successors or assigns.