idnits 2.17.1 draft-zhang-ospf-dvl-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** 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 -- however, there's a paragraph with a matching beginning. Boilerplate error? ** 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 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.) ** There are 8 instances of too long lines in the document, the longest one being 3 characters in excess of 72. ** There are 38 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '2' on line 325 looks like a reference -- Missing reference section? '1' on line 323 looks like a reference -- Missing reference section? '3' on line 328 looks like a reference Summary: 10 errors (**), 0 flaws (~~), 1 warning (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Z. Zhang 2 Expiration Date: May, 1998 Bay Networks 3 File name: draft-zhang-ospf-dvl-01.txt November, 1997 5 Fixing Backbone Partition with Dynamic Virtual Links 7 Zhaohui Zhang 9 Bay Networks, Inc. 11 Status of this Memo 13 This document is an Internet-Draft. Internet-Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its 15 areas, and its working groups. Note that other groups may also 16 distribute working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six 19 months and may be updated, replaced, or obsoleted by other 20 documents at any time. It is inappropriate to use Internet- 21 Drafts as reference material or to cite them other than as 22 ``work in progress.'' 24 To learn the current status of any Internet-Draft, please check 25 the ``1id-abstracts.txt'' listing contained in the Internet- 26 Drafts Shadow Directories on ftp.is.co.za (Africa), 27 nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), 28 ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). 30 Abstract 32 This document proposes a Dynamic Virtual Link (DVL) algorithm to 33 dynamically detect and fix OSPF backbone area partition. 35 In the DVL algorithm, each ABR periodically checks if it can reach 36 via backbone area all other ABRs that it can reach via its transit 37 areas. If not, it knows that a backbone partition has occurred and 38 a spanning tree of Dynamic Virtual Links are created. When the 39 DVLs are not needed, they are automatically deleted. 41 1. Introduction 43 Open Shortest Path First (OSPF) protocol requires that all Area 44 Border Routers (ABRs) be connected to a backbone area and that 45 the backbone area be contiguous. However, the protocol does not 46 try to detect and fix partitioned areas. 48 Virtual links can be used to provide or enhance backbone 49 connectivity. However, a lot of redundant virtual links have to 50 be used to ENSURE backbone connectivity and they introduce a 51 lot of overhead both in traffic and to the routers. 53 The author proposes that virtual links be made dynamic: they are 54 created when they are needed and destroyed when they are not 55 needed. 57 Supporting Dynamic Virtual Links (DVL) is optional. 59 1.1 Differences from previous version 61 1. The "spanning tree center" is no longer "elected" and 62 "maintained". The "center" is now always the router with 63 the highest ID. 65 2. To detect redundant DVLs, routers now run a special Dijkstra 66 in the backbone area, using tie-breakers similar to those in 67 MOSPF, instead of depending upon random timers to avoid 68 thrashing. 70 3. A configurable area parameter is added to control whether 71 DVLs are allowed through a transit area. 73 2. Dynamic Virtual Links 75 2.1 Detect Backbone Partition 77 Since each router maintains a routing table in each area for all 78 ABRs in that area, the backbone partition can be easily detected: 79 if an ABR discovers that it can reach another ABR via a transit 80 area, but it can not reach the ABR via the backbone area, then it 81 knows that there is a backbone partition and DVLs need to be 82 created to fix the partition. 84 2.2 Spanning Tree of DVLs 86 It is not necessary that a DVL be created between each pair of 87 ABRs that can not reach each other via the backbone area. 89 In Figure 1, the ABRs in a transit area are divided into disjoint 90 groups (shown as blocks): ABRs (shown as "o" in the blocks) in a 91 group can reach each other via the backbone area, but they can not 92 reach ABRs outside the group via backbone. A star-shaped spanning 93 tree (see 5.2 of [2]) that connects the groups is enough: a chosen 94 ABR in a leaf group creates a DVL to a chosen ABR in the center 95 group B if it cannot reach the chosen ABR in the center via the 96 backbone, and deletes the DVL when it is not needed to reach the 97 ABR in the center. The chosen ABR in the center is passive and 98 dynamically creates a DVL when it receives the first Hello packet 99 from a new virtual neighbor with lower ID. 101 The chosen ABR in a center group is hereafter called a center. 103 Previously disjoint groups merge into one group after adjacencies 104 on their DVLs to the center have been established. However, this 105 does not change anything. A group can also split, and a chosen ABR 106 in each subgroup will have a DVL to the center. 108 +------+ +------+ 109 ++==+ o o +==============+ o +==+ 110 // | o o | DVL | o o | \\ 111 // | o o +--------------+ o o | \\ 112 // +------+ /+----+-+ \\ 113 ++ A / B | ++ 114 || / | || 115 || transit area / DVL | || 116 ++ / DVL | ++ 117 \\ C / D | // 118 \\ +------+ / +----+-+ // 119 \\ | o | | o o | // 120 ++==+ +==============+ +==++ 121 | o o | ^ | o o | 122 +------+ | +------+ 123 | 124 transit area border 126 Figure 1. Disjoint groups of ABRs 128 The spanning tree needs not to be a Minimum Weight Spanning Tree 129 (MST) (see 5.2.2 of [2]): 130 1. A distributed MST algorithm requires exchange of cost 131 information among the ABRs, which can cause extra routing 132 traffic and longer convergence time. 133 2. A MST needs to be reformed whenever there is a topology 134 change in the transit area, which again leads to more 135 traffic and longer convergence time. 136 3. Even if a nonoptimal spanning tree of virtual links is used, 137 the route calculation will still result in shortest path 138 trees for the ABRs (see 16.3 of [1]). 140 The spanning tree is formed per transit area, but some tie- 141 breakers make sure that there will be no redundant DVLs formed 142 or kept in all areas (see 3.2.2 & 3.3). 144 The center could change when more ABRs join the transit area. 145 It is always the router with the highest ID in a transit area. 146 However, existing DVLs to old centers are not affected by a 147 new center. 149 Note that if a DVL is already established for a group, when 150 another ABR with higher Router ID joins the group, it does not 151 create another DVL because it can reach the center via the 152 existing DVL. 154 2.3 Detect/delete Redundant DVLs 156 Some DVLs become redundant when the original backbone connection 157 failures are fixed. Sometimes redundant DVLs could be created due 158 to the distributed nature of the algorithm. Redundant DVLs should 159 be deleted. 161 Note that the deleting of a redundant DVL is only initiated by the 162 router that initiated the DVL when the router was a leaf. 164 To find out if a DVL initiated by the router is redundant, the router 165 runs a Dijkstra in the backbone area, rooting the tree at the router 166 with the highest ID of those reachable in the backbone area. 167 Tie-breaks similar to those in MOSPF are used to ensure that all ABRs 168 get the same shortest path trees rooting at the highest ID router, 169 so that they agree which DVLs are redundant. 171 3. Implementation Details 173 3.1 A Functionality Bit -- D-bit 175 A new functionality bit, D-bit, is used in Router LSAs to indicate 176 that a router supports DVL in the area, as shown in Figure 2. 178 0 1 2 3 179 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 181 | | 182 + | 183 | Router LSA Header | 184 + | 185 | | 186 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 187 | 0 |D|W|V|E|B| 0 | # links | 188 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 189 | Link ID | 190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 191 | Link Data | 192 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 193 | ... | 195 Figure 2. Functionality bits 196 3.2 Detect and Fix Possible Backbone Partition 198 The following procedure is taken by an ABR for a transit area 199 whenever: 201 a. there is a topology change (indicated by new Router/Net LSAs) 202 in the backbone area. 203 b. there is a topology change in the transit area. 205 1. Find out current center C, which is the ABR with the highest ID 206 of those with the D-bit set in their Router LSAs and reachable in 207 the transit area. 209 Find out the ABR with the highest ID of those with the D-bit 210 set in their Router LSAs and reachable via the backbone area, 211 calling it L. 213 2. create a DVL to the center if all the following three conditions 214 are met: 216 a. this router is L but not the current center C 217 b. it can not reach the center C via the backbone 218 c. there is not another transit area with a higher area ID, 219 via which the center can be reached 221 3.3 Detect/Delete Redundant DVLs 223 If a router has active DVLs (with neighbors fully adjacent over the 224 DVLs) initiated by itself, the following procedure is taken in the 225 backbone area when there is a topology change in the backbone area 226 and there is no partition in the backbone area after the change. 228 1. Find out the router H with the highest ID of those reachable in the 229 backbone area, whether the D-bit is set in their Router LSAs or not. 231 2. With H's Router LSA as the root, do a Dijkstra in the backbone area 232 with the following special process: 234 a) Use tie-breakers similar to those in MOSPF (see step (2)(d) in 235 Section 16.1, RFC 2178). 237 b) When a vertex is moved from the candidate list to the SPF 238 tree, if the link between its parent and itself is a DVL 239 initiated by this router, mark it as "needed". 241 3. Delete those DVLs that are initiated by the router and not marked 242 as "needed". 244 Because of the tie-breakers all DVL routers will build the same 245 tree so they will agree on which DVLs are redundant. Note that 246 DVLs that are not absolutely needed but do lead to optimal paths 247 are not deleted. 249 Before a DVL is deleted, if the associateed neighbor is in state 250 N2WAY or higher, the router should send a Hello packet with no 251 listed neighbor over the DVL, so that the neighbor can immediately 252 drop its adjacency with this router and delete the DVL from its end. 254 4. Discussions 256 4.1 Performance 258 The backbone partition detecting/fixing procedure is taken for a 259 transit area only when there is a topology change in the backbone 260 area or in the transit area; the procedure for detecting/deleting 261 redundant DVLs is taken only for the backbone area when there are 262 DVLs initiated by this router and there is a topology change in 263 the backbone area and there is no backbone partition after the 264 change. 266 Therefore, the algorithm does not introduce much extra load. 268 4.2 Spanning tree center/leaf determination 270 The algorithm relies on the routers that have the highest IDs of 271 all ABRs in a transit area or of all ABRs reachable via backbone. 272 If each ABR, instead of only the one with the highest ID of all ABRs 273 reachable via backbone, creates a DVL to the center, there will be 274 some redundant DVLs being created and then deleted, causing extra 275 traffic and routing oscillation. 277 5. Configurable Area Parameters 279 DVLEnabled 280 Control whether DVLs are allowed through this transit area. 282 DVLRxmtInterval 283 DVLInfTransDelay 284 DVLHelloInterval 285 DVLRouterDeadInterval 286 DVLAuType 287 DVLAuthKey 289 6. Acknowledgement 291 Special thanks goes to John Moy. This document and related work 292 could not have been finished without help from him. 293 In fact, John had his DVL idea in 294 his mind too when the author's was brought up to him. He also 295 pointed out some holes and gave some suggestions, such as on 296 spanning tree, eliminating center election in version 0, and the 297 logic for deleting DVLs, which are very important in the DVL 298 algorithm. 300 A special thanks also goes to Rob Coltun, whose OSPF simulator 301 made it possible to implement and test the DVL algorithm in draft 302 version 0. 304 The initial work and versions of this document were finished 305 while the author was working in the IP/Routing Consortium, 306 InterOperability Laboratory (http://www.iol.unh.edu), University 307 of New Hampshire. 309 7. Author's Address 311 Zhaohui Zhang 312 Bay Networks, Inc. 313 600 Technology Park 314 Billerica, MA 01821 316 Email: zzhang@baynetworks.com 318 Phone: (978) 916-8225 319 Fax: (978) 670-8760 321 Reference 323 [1] John Moy, "OSPF Version 2", RFC2178, July 1997 325 [2] Dimitri Bertsekas and Robert Gallager, "Data Networks", 326 Prentice-Hall, Inc., 1992. 328 [3] John Moy, "Multicast Extension to OSPF", RFC 1584, March 1994. 330 This document expires in May, 1998.