idnits 2.17.1 draft-ietf-ospf-overflow-00.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-03-19) 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 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. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 162: '...OspfExtLsdbLimit MUST be set identical...' 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.) -- The document date (November 1994) is 10717 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) == Unused Reference: '3' is defined on line 407, but no explicit reference was found in the text ** Obsolete normative reference: RFC 1583 (ref. '1') (Obsoleted by RFC 2178) ** Obsolete normative reference: RFC 1587 (ref. '2') (Obsoleted by RFC 3101) ** Downref: Normative reference to an Informational RFC: RFC 1245 (ref. '3') -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Downref: Normative reference to an Informational RFC: RFC 1246 (ref. '5') ** Downref: Normative reference to an Historic RFC: RFC 1584 (ref. '6') Summary: 14 errors (**), 0 flaws (~~), 2 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Moy 3 Internet Draft Cascade 4 Expiration Date: May 1995 November 1994 5 File name: draft-ietf-ospf-overflow-00.txt 7 OSPF Database Overflow 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six 17 months and may be updated, replaced, or obsoleted by other documents 18 at any time. It is inappropriate to use Internet- Drafts as 19 reference material or to cite them other than as "work in progress". 21 To learn the current status of any Internet-Draft, please check the 22 "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow 23 Directories on ds.internic.net (US East Coast), nic.nordu.net 24 (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific 25 Rim). 27 Abstract 29 Proper operation of the OSPF protocol requires that all OSPF routers 30 maintain an identical copy of the OSPF link-state database. 31 However, when the size of the link-state database becomes very 32 large, some routers may be unable to keep the entire database due to 33 resource shortages; we term this "database overflow". When database 34 overflow is anticipated, the routers with limited resources can be 35 accommodated by configuring OSPF stub areas and NSSAs. This memo 36 details a way of gracefully handling unanticipated database 37 overflows. 39 This memo is a product of the OSPF Working Group. Please send 40 comments to ospf@gated.cornell.edu. 42 Table of Contents 44 1 Overview ............................................... 3 45 2 Implementation details ................................. 4 46 2.1 Configuration .......................................... 4 47 2.2 Entering OverflowState ................................. 5 48 2.3 Operation while in OverflowState ....................... 6 49 2.3.1 Modifications to Flooding .............................. 6 50 2.3.2 Originating AS-external-LSAs ........................... 7 51 2.3.3 Receiving self-originated LSAs ......................... 7 52 2.4 Leaving OverflowState .................................. 7 53 3 An example ............................................. 7 54 4 Administrative response to database overflow ........... 8 55 5 Operational experience ................................. 9 56 6 Possible enhancements .................................. 9 57 A Related MIB parameters ................................ 10 58 References ............................................ 11 59 Security Considerations ............................... 11 60 Author's Address ...................................... 11 62 1. Overview 64 OSPF requires that all OSPF routers within a single area maintain an 65 identical copy of the OSPF link-state database. However, when the 66 size of the link-state database becomes very large, some routers may 67 be unable to keep the entire database due to resource shortages; we 68 term this "database overflow". For example, a regional network may 69 have a very large OSPF database because it is importing a large 70 number of external routes into OSPF. Unless database overflow is 71 handled correctly, routers will end up with inconsistent views of 72 the network, possibly leading to incorrect routing. 74 One way of handling database overflow is to encase routers having 75 limited resources within OSPF stub areas (see Section 3.6 of [1]) or 76 NSSAs ([2]). AS-external-LSAs are omitted from these areas' link- 77 state databases, thereby controlling database size. 79 However, unexpected database overflows cannot be handled in the 80 above manner. This memo describes a way of dynamically limiting 81 database size under overflow conditions. The basic mechanism is as 82 follows: 84 (1) A parameter, ospfExtLsdbLimit, is configured in each router 85 indicating the maximum number of AS-external-LSAs (excluding 86 those describing the default route) that are allowed in the 87 link-state database. This parameter must be the same in all 88 routers in the routing domain (see Section 2.1); synchronization 89 of the parameter is achieved via network management. 91 (2) In any router's database, the number of AS-external-LSAs 92 (excluding default) is never allowed to exceed ospfExtLsdbLimit. 93 If a router receives a non-default AS-external-LSA that would 94 cause the limit of ospfExtLsdbLimit to be exceeded, it drops the 95 LSA and does NOT acknowledge it. 97 (3) If the number of non-default AS-external-LSAs in a router's 98 database hits ospfExtLsdbLimit, the router a) flushes all non- 99 default AS-external-LSAs that it has itself originated (see 100 Section 2.2) and b) goes into "OverflowState". 102 (4) While in OverflowState, the router refuses to originate any 103 non-default AS-external-LSAs (see Section 2.3.2). 105 (5) Optionally, the router can attempt to leave OverflowState after 106 the configurable parameter ExitOverflowInterval has elapsed 107 since entering Overflow state (see Section 2.4). Only at this 108 point can the router resume originating non-default AS- 109 external-LSAs. 111 The reason for limiting non-default AS-external-LSAs, but not other 112 LSA types, is twofold. First of all, the non-default AS-external 113 LSAs are the most likely to dominate the database size in those 114 networks with huge databases (e.g., regional networks; see [5]). 115 Second, the non-default AS-external-LSAs can be viewed as "optional" 116 in the following sense: the router can probably be 117 monitored/reconfigured without them. (However, using similar 118 strategies, other LSA types can also be limited; see Section 5.) 120 The method of dealing with database overflow described herein has 121 the following desirable properties: 123 o After a short period of convergence, all routers will have 124 identical link-state databases. This database will contain less 125 than ospfExtLsdbLimit non-default AS-external-LSAs. 127 o At all times, routing WITHIN the OSPF Autonomous System will 128 remain intact. Among other things, this means that the routers 129 will continue to be manageable. 131 o Default routing to external destinations will also remain 132 intact. This hopefully will mean that a large amount of external 133 connectivity will be preserved, although possibly taking less 134 efficient routes. 136 o If parameter ExitOverflowInterval is configured, the OSPF system 137 will recover fully and automatically (i.e., without network 138 management intervention) from transient database overflow 139 conditions (see Section 2.4). 141 2. Implementation details 143 This section describes the mechanism for dealing with database 144 overflow in more detail. The section is organized around the concept 145 OverflowState, describing how routers enter the OverflowState, the 146 operation of the router while in OverflowState, and when the router 147 leaves OverflowState. 149 2.1. Configuration 151 The following configuration parameters are added to support the 152 database overflow functionality. These parameters are set by 153 network management. 155 ospfExtLsdbLimit 156 When the number of non-default AS-external-LSAs in a 157 router's link-state database reaches ospfExtLsdbLimit, the 158 router enters OverflowState. The router never holds more 159 than ospfExtLsdbLimit non-default AS-external-LSAs in its 160 database. 162 OspfExtLsdbLimit MUST be set identically in all routers 163 attached to the OSPF backbone and/or any "regular" OSPF 164 area. (This memo does not pertain to routers contained 165 within OSPF stub areas or NSSAs, since such routers do not 166 receive AS-external-LSAs.) If ospfExtLsdbLimit is not set 167 identically in all routers, then when the database 168 overflows: 1) the routers will NOT converge on a common 169 link-state database, 2) incorrect routing, possibly 170 including routing loops, will result and 3) constant 171 retransmission of AS-external-LSAs will occur. Identical 172 setting of ospfExtLsdbLimit is achieved/ensured by network 173 management. 175 When ospfExtLsdbLimit is set in a router, the router must 176 have some way to guarantee that it can hold that many non- 177 default AS-external-LSAs in its link-state database. One way 178 of doing this is to preallocate resources (e.g., memory) for 179 the configured number of LSAs. 181 ExitOverflowInterval 182 The number of minutes that, after entering OverflowState, a 183 router will attempt to leave OverflowState. This allows the 184 router to again originate non-default AS-external-LSAs. When 185 set to 0, the router will not leave OverflowState until 186 restarted. The default setting for ExitOverflowInterval is 187 0. 189 It is not necessary for ExitOverflowInterval to be 190 configured the same in all routers. A smaller value may be 191 configured in those routers that originate the "more 192 important" AS-external-LSAs. In fact, setting 193 ExitOverflowInterval the same may cause problems, as 194 multiple routers attempt to leave OverflowState 195 simultaneously. For this reason, the value of 196 ExitOverflowInterval must be "jittered" by adding a random 197 number in the range of 1 to 10 to ExitOverflowInterval 198 before using. 200 2.2. Entering OverflowState 202 The router enters OverflowState when the number of non-default 203 AS-external-LSAs in the database hits ospfExtLsdbLimit. There 204 are two cases when this can occur. First, when receiving an LSA 205 during flooding. In this case, an LSA which does not already 206 have a database instance is added in Step 5 of Section 13 of 208 [1]. The second case is when the router originates a non- 209 default AS-external-LSA itself. 211 Whenever the router enters OverflowState it flushes all non- 212 default AS-external-LSAs that it itself had originated. Flushing 213 is accomplished through the premature aging scheme described in 214 Section 14.1 of [1]. Only self-originated LSAs are flushed; 215 those originated by other routers are kept in the link-state 216 database. 218 2.3. Operation while in OverflowState 220 While in OverflowState, the flooding and origination of non- 221 default AS-external-LSAs are modified in the following fashion. 223 2.3.1. Modifications to Flooding 225 Flooding while in OverflowState is modified as follows. If 226 in Step 5 of Section 13 of [1], a non-default AS-external- 227 LSA has been received that a) has no current database 228 instance and b) would cause the count of non-default AS- 229 external-LSAs to exceed ospfExtLsdbLimit, then that LSA is 230 discarded. Such an LSA is not installed in the link-state 231 database, nor is it acknowledged. 233 When all routers have identical values for ospfExtLsdbLimit 234 (as required), the above flooding modification should be 235 exercised only during a short period of convergence. During 236 convergence, there will be retransmissions of LSAs. However, 237 after convergence the retransmissions will cease, as the 238 routers settle on a database having less than 239 ospfExtLsdbLimit non-default As-external-LSAs. 241 In OverflowState, non-default AS-external-LSAs ARE still 242 accepted in the following conditions: 244 (1) If the LSA updates an LSA that currently exists in the 245 router's link-state database. 247 (2) LSAs having LS age of MaxAge are always accepted. The 248 processing of these LSAs follows the procedures 249 described in Sections 13 and 14 of [1]. 251 (3) If adding the LSA to the router's database would keep 252 the number of non-default AS-external-LSAs less than or 253 equal to ospfExtLsdbLimit, the LSA is accepted. 255 2.3.2. Originating AS-external-LSAs 257 Originating AS-external-LSAs is described in Section 12.4.5 258 of [1]. When a router is in OverflowState, it does not 259 originate non-default AS-external-LSAs. In other words, the 260 only AS-external-LSAs originated by a router in 261 OverflowState have Link State ID 0.0.0.0. 263 2.3.3. Receiving self-originated LSAs 265 Receiving self-originated LSAs is described in Section 13.4 266 of [1]. When in OverflowState, a router receiving a self- 267 originated non-default AS-external-LSA responds by flushing 268 it from the routing domain using the premature aging scheme 269 described in Section 14.1 of [1]. 271 2.4. Leaving OverflowState 273 If ExitOverflowInterval is non-zero, then as soon as a router 274 enters OverflowState, it sets a timer equal to the value of 275 ExitOverflowInterval plus a random value between 1 and 10. When 276 this timer fires, the router leaves OverflowState and begins 277 originating non-default AS-external-LSAs again. 279 This allows a router to automatically recover from transient 280 overflow conditions. For example, an AS boundary router that 281 imports a great many AS-external-LSAs may crash. Other routers 282 may then start importing the routes, but until the crashed AS 283 boundary router is either a) restarted or b) its AS-external- 284 LSAs age out, there will be a much larger database than usual. 285 Since such an overflow is guaranteed to go away in MaxAge 286 seconds (1 hour), automatic recovery may be appropriate (and 287 fast enough) if the overflow happens off-hours. 289 As soon as the router leaves OverflowState, it is again eligible 290 to reenter Overflow state according to the text of Section 2.2. 292 3. An example 294 As an example, suppose that a router implements the database 295 overflow logic, and that its ospfExtLsdbLimit is 10,000 and its 296 ExitOverflowInterval is set to 10 minutes. Suppose further that the 297 router itself is originating 400 non-default AS-external-LSAs, and 298 that the current number of non-default AS-external-LSAs in the 299 router's database is equal to 9,997. 301 Next it receives a Link State Update packet from a neighbor, 302 containing 6 non-default AS-external-LSAs, none of which have 303 current database copies. The first two LSAs are then installed in 304 the database. The third LSA is also installed in the database, but 305 causes the router to go into OverflowState. Going into 306 OverflowState causes the router to flush (via premature aging) its 307 400 self-originated non-default LSAs. However, these 400 LSAs are 308 still considered to be part of the link-state database until their 309 re-flooding (with age set to MaxAge) is acknowledged (see Section 14 310 of [1]); for this reason, the last three LSAs in the received update 311 are discarded without being acknowledged. 313 After some small period of time all routers will converge on a 314 common database, having less than 10,000 non-default AS-external- 315 LSAs. During this convergence period there may be some link-state 316 retransmissions; for example, the sender of the above Link State 317 Update packet may retransmit the three LSAs that were discarded. If 318 this retransmission happens after the flushing of the 400 self- 319 originated LSAs is acknowledged, the 3 LSAs will then be accepted. 321 Going into OverflowState also causes the router to set a timer that 322 will fire some time between 11 and 20 minutes later. When this timer 323 fires, the router will leave OverflowState and re-originate its 400 324 non-default AS-external-LSAs, provided that the current database has 325 less than 9600 (10,000 - 400) non-default AS-external-LSAs. If there 326 are more than 9600, the timer is simply restarted. 328 4. Administrative response to database overflow 330 Once the link-state database has overflowed, it may take 331 intervention by network management before all routing is restored. 332 (If the overflow condition is transient, routing may be restored 333 automatically; see Section 2.4 for details.) An overflow condition 334 is indicated by SNMP traps (see Appendix B). Possible responses by a 335 network manager may include: 337 o Increasing the value of ospfExtLsdbLimit. Perhaps it had been 338 set too conservatively, and the routers are able to support 339 larger databases than they are currently configured for. 341 o Isolating routers having limited resources within OSPF stub 342 areas or NSSAs. This would allow increasing the value of 343 ospfExtLsdbLimit in the remaining routers. 345 o Reevaluating the need to import certain external routes. If 346 ospfExtLsdbLimit cannot be increased, the network manager will 347 want to make sure that the more important routes continue to be 348 imported; this is accomplished by turning off the importing of 349 less important routes. 351 5. Operational experience 353 The database overflow scheme described in this memo has been 354 implemented in the Proteon router for a number of years, with the 355 following differences. First, the router did not leave OverflowState 356 until it was restarted (i.e., ExitOverflowInterval was always 0). 357 Second, default AS-external-LSAs were not separated from non-default 358 AS-external-LSAs. Operationally the scheme performed as expected: 359 during overflow conditions, the routers converged on a common 360 database having less than a configured number of AS-external-LSAs. 362 6. Possible enhancements 364 Possible enhancements to the overflow scheme include the following: 366 o Other LSA types, with the exception of the transit LSAs 367 (router-LSAs and network-LSAs), could be limited in a similar 368 fashion. For example, one could limit the number of summary- 369 LSAs, or group-membership-LSAs (see [6]). 371 o Rather than flushing all of its non-default AS-external-LSAs 372 when entering OverflowState, a router could flush a fixed number 373 whenever the database size hits ospfExtLsdbLimit. This would 374 allow the router to prioritize its AS-external-LSAs, flushing 375 the least important ones first. 377 A. Related MIB parameters 379 The following OSPF MIB variables have been defined to support the 380 database overflow procedure described in this memo (see [4] for more 381 information): 383 ospfExtLsdbLimit 384 The maximum number of AS-external-LSAs that can be stored within 385 the database. If set to -1, there is no limit. In this memo, we 386 have excluded default route AS-external-LSAs (those having Link 387 State ID of 0.0.0.0) from the limit. This parameter is then the 388 same as "ospfExtLsdbLimit" in Section 2.1. 390 ospfLsdbOverflow 391 A trap indicating that the number of non-default AS-external- 392 LSAs has exceeded ospfExtLsdbLimit. For this memo, we would 393 modify this to "exceeded or equaled". This trap then indicates 394 that the router is entering OverflowState. 396 ospfLsdbApproachingOverflow 397 A trap indicating that the number of non-default AS-external- 398 LSAs has exceeded ninety percent of "ospfExtLsdbLimit". 400 References 402 [1] Moy, J., "OSPF Version 2", RFC 1583, Proteon, Inc., March 1994. 404 [2] Coltun, R. and V. Fuller, "The OSPF NSSA Option", RFC 1587, 405 RainbowBridge Communications, Stanford University, March 1994. 407 [3] Moy, J., editor, "OSPF protocol analysis", RFC 1245, Proteon, 408 Inc., July 1991. 410 [4] Baker F. and R. Coltun, "OSPF Version 2 Management Information 411 Base", work in progress. 413 [5] Moy, J., editor, "Experience with the OSPF protocol", RFC 1246, 414 Proteon, Inc., July 1991. 416 [6] Moy, J., "Multicast Extensions to OSPF", RFC 1584, Proteon, 417 Inc., March 1994. 419 Security Considerations 421 Security issues are not discussed in this memo. 423 Author's Address 425 John Moy 426 Cascade Communications Corp. 427 5 Carlisle Road 428 Westford, MA 01886 430 Phone: 508-692-2600 Ext. 394 431 Fax: 508-692-9214 432 Email: jmoy@casc.com 434 This document expires in May 1995.