idnits 2.17.1 draft-chen-ospf-intelligent-db-exch-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (September 2017) is 2413 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: 'RFC2119' is defined on line 512, but no explicit reference was found in the text == Unused Reference: 'RFC5243' is defined on line 527, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2740 (Obsoleted by RFC 5340) Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force H. Chen 3 Internet-Draft Huawei 4 Intended status: Standards Track September 2017 5 Expires: March 5, 2018 7 Intelligent OSPF Link State Database Exchange 8 draft-chen-ospf-intelligent-db-exch-02.txt 10 Abstract 12 This document presents an intelligent database exchange mechanism for 13 the database exchange procedure in OSPFv2 and OSPFv3. This mechanism 14 is backward compatible. It eliminates the unnecessary database 15 exchanges through using the existing reachability information 16 calculated from the link state database and the un-reachability 17 information about routers recorded. It significantly speeds up the 18 establishment of the full adjacency between two routers in some 19 situations. 21 Status of this Memo 23 This Internet-Draft is submitted to IETF in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on March 5, 2018. 38 Copyright Notice 40 Copyright (c) 2017 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1. Eliminating Whole Link State Database Exchange . . . . . . 3 57 1.2. Eliminating Part of Link State Database Exchange . . . . . 4 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. Conventions Used in This Document . . . . . . . . . . . . . . 5 60 4. Intelligent Link State Database Exchange . . . . . . . . . . . 5 61 5. Changes to OSPF Protocols . . . . . . . . . . . . . . . . . . 5 62 5.1. Changes to Creation of Database Summary List . . . . . . . 6 63 5.2. Changes to Processing of DD Packet Contents . . . . . . . 6 64 5.3. New Data Structures and Procedures . . . . . . . . . . . . 7 65 6. Some Details about Implementations of New Procedures . . . . . 7 66 6.1. Finding and Recording Failure Time and LSA Change Time . . 8 67 6.1.1. Finding and Recording Failure Time and LSA Change 68 Time . . . . . . . . . . . . . . . . . . . . . . . . . 8 69 6.1.2. A Simpler Method for Finding Failure Time . . . . . . 9 70 6.1.3. Finding and Recording LSA Change Time . . . . . . . . 10 71 6.2. Reusing LSA Age, Finding and Recording Adjust Time . . . . 11 72 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 73 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 74 9. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 12 75 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 76 10.1. Normative References . . . . . . . . . . . . . . . . . . . 12 77 10.2. Informative References . . . . . . . . . . . . . . . . . . 12 78 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12 80 1. Introduction 82 If a full adjacency is to be formed between two OSPF routers, their 83 link state databases will be synchronized through the database 84 exchange procedure described in OSPFv2 [RFC2328] and OSPFv3 85 [RFC2740]. Each of the routers sends the other the summary of its 86 database through a set of Database Description packets containing the 87 header of every LSA in its database. For every LSA header received 88 in the Database Description packets, the router compares it with the 89 corresponding LSA instance in its database and sends the other router 90 a request for the LSA if the LSA instance in its database is older. 91 The adjacency becomes full when the router finishes sending the 92 summary of its database and processing all the Database Description 93 packets from the other router and gets all the LSAs it requested. 95 1.1. Eliminating Whole Link State Database Exchange 97 In some situations, the whole link state database exchange is 98 unnecessary. For example, in the case illustrated in the figure 99 below, we suppose that full adjacencies between routers RT3 and RT4, 100 RT4 and RT5, and RT5 and RT6 have been established, and a new full 101 adjacency between RT3 and RT6 is to be formed over the link directly 102 connecting them. In this case, RT3 and RT6 are reachable each other 103 through RT4 and RT5. They do not need to exchange their link state 104 databases at all since they are reachable each other and already have 105 the same database. 107 + 108 | 3+---+ N12 N14 109 N1|--|RT1|\ 1 \ N13 / 110 | +---+ \ 8\ |8/8 111 + \ ____ \|/ 112 / \ 1+---+8 8+---+ 113 * N3 *---|RT4|------|RT5| 114 \____/ +---+ +---+ 115 + / | |6 116 | 3+---+ / | | 117 N2|--|RT2|/1 |1 |6 118 | +---+ +---+6 6+---+ 119 + |RT3|==============|RT6| 120 +---+ +---+ 122 Figure 1: A Full Adjacency between RT3 and RT6 to be Formed 124 For a large database, eliminating the unnecessary database exchange 125 will significantly speed up the establishment of the full adjacency 126 and save lots of link bandwidth for the transmission of the 127 unnecessary Database Description packets and CPU cycles for the 128 processing of the packets. 130 1.2. Eliminating Part of Link State Database Exchange 132 In some other cases, some part of the database exchange is not 133 needed. For example, in the topology shown in the figure below, when 134 the only connection between two routers Rt4 and RT5 is down for a 135 short time and then up again, most parts of their link state 136 databases are the same and only small parts of the databases may be 137 different. In this case, it is not necessary for these two routers 138 to exchange the parts of their databases that are the same. 140 + 141 | 3+---+ N12 N14 142 N1|--|RT1|\ 1 \ N13 / 143 | +---+ \ 8\ |8/8 144 + \ ____ \|/ 145 / \ 1+---+8 8+---+ 146 * N3 *---|RT4|======|RT5| 147 \____/ +---+ +---+ 148 + / | |6 149 | 3+---+ / | | 150 N2|--|RT2|/1 |1 |6 151 | +---+ +---+6 6+---+ 152 + |RT3| |RT6| 153 +---+ +---+ 155 Figure 2: Link between RT4 and RT5 goes Down and then Up 157 Another example is in a Mobile Ad-Hoc Network (MANET) where nodes are 158 mobile. When a mobile node moves out of a transmission range and 159 into another range in the same OSPF area in a short time, the 160 adjacencies to the nodes in the old range will be down and the new 161 adjacencies to some nodes in the new range will be established. In 162 this situation, most of their databases are the same. 164 This document describes a solution, called an intelligent database 165 exchange mechanism, for eliminating the unnecessary database 166 exchanges and processes during the establishment of a full adjacency 167 between two routers. This solution is backward compatible. 169 2. Terminology 171 This document uses terminologies defined in RFC 2328, and RFC 2740. 173 3. Conventions Used in This Document 175 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 176 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 177 document are to be interpreted as described in RFC 2119. 179 4. Intelligent Link State Database Exchange 181 The intelligent OSPF Link State database exchange mechanism 182 eliminates the unnecessary Database Description packets exchanges and 183 processes through using the existing reachability information 184 calculated from the link state database and the un-reachability 185 information about routers recorded. 187 When two OSPF routers are going to bring up a full adjacency between 188 them, each of them checks whether it is reachable to the other 189 through using its route table calculated from its link state 190 database. If it can reach the other router, it does not need to send 191 the other any Database Description packets that contain the summary 192 of its database since two routers have the same database. In this 193 case, all the unnecessary Database Description packets exchanges and 194 processes are eliminated. The full adjacency between two routers is 195 formed almost immediately. 197 If one router can not reach to the other now but it could reach the 198 other at time t and the difference between the current time and t is 199 less than the LSA maximum age MaxAge (3600 seconds), then it does not 200 need to send the other the header of every LSA in its database 201 through Database Description packets. It just needs to send the 202 other the headers of the LSAs that have been changed in its database 203 since time t at which the other router became unreachable. During 204 the intelligent database exchange, when one router detects that the 205 other router was restarted after time t through some way such as 206 comparing the router LSA generated by the other router with its 207 corresponding LSA instance in its link state database, it stops its 208 current intelligent database exchange and starts a new normal 209 database exchange with the other router. 211 During the intelligent database exchange between two routers, if one 212 router detects that the other router becomes unreachable, it stops 213 its current intelligent database exchange and starts a new normal 214 database exchange with the other router. 216 5. Changes to OSPF Protocols 218 The changes to the OSPF protocols include three parts. The first 219 part is to modify the creation of the neighbor database summary list. 220 The second is to change the processing of a Database Description 221 packet contents. The third is to add some data structures and 222 procedures. 224 5.1. Changes to Creation of Database Summary List 226 In the OSPF protocols, when a local router is going to form a full 227 adjacency with a neighboring router, it creates the neighbor database 228 summary list that has the contents of its entire area link state 229 database. The area link state database consists of the router-LSAs, 230 network-LSAs and summary-LSAs contained in the area structure, along 231 with the AS-external-LSAs contained in the global structure. The 232 intelligent database exchange mechanism modifies the creation of the 233 summary list as follows: 235 If the local router can reach the neighboring router now, then the 236 neighbor database summary list is empty; otherwise (i.e., the router 237 can not reach the neighboring router now), if the router could reach 238 the neighboring router at time t and the difference between the 239 current time and t is less than the LSA maximum age MaxAge, then the 240 neighbor database summary list must have the contents of the LSAs 241 that have been changed in its link state database since time t at 242 which the neighboring router became unreachable; otherwise, the 243 neighbor database summary list has the contents of its entire area 244 link state database. 246 5.2. Changes to Processing of DD Packet Contents 248 In the original OSPF protocols [RFC2328, RFC2740], when the local 249 router accepts a received Database Description Packet as the next in 250 sequence, one part of processing of the packet contents is that the 251 router looks up the LSA contained in the packet in its database to 252 see whether it also has an instance of the LSA. If it does not, or 253 if the database copy is less recent, the LSA is put on the Link state 254 request list so that it can be requested in Link State Request 255 Packets. This part of processing of the packet contents is modified 256 as follows: 258 If the local router can reach the neighboring router now, it does not 259 look up any LSA contained in the packet in its database to see 260 whether it also has an instance of the LSA or if the database copy is 261 less recent. Otherewise, the local router follows the processing of 262 the packet contents as described in OSPF protocols. 264 5.3. New Data Structures and Procedures 266 In addition to the above modification, some new data structures and 267 procedures should be added to provide the following functions: 269 1. Record function, which records the information about: 271 * Every tuple , where r is the remote router in the 272 entire area that became unreachable from the local router at 273 time tu and the difference between the current time and tu is 274 less than the LSA maximum age MaxAge (3600 seconds). 276 * The time tc for every LSA at which the LSA is changed if there 277 exist some remote routers that became unreachable less than 278 MaxAge ago. It is not necessary to record time tc for any LSA 279 if there is not any remote router that became unreachable 280 within the past MagAge (3600 seconds). 282 2. Retrieve function, which provides the information about: 284 * For a given unreachable remote router r, the time tu at which 285 the router r became unreachable. 287 * For a given time tu, all the LSAs in the link state database 288 that have been changed since then. Normally tu is the time 289 when a remote router became unreachable. 291 3. Delete function, which removes the information about: 293 * Every tuple when the remote router r becomes reachable 294 or the difference between the current time and tu (where tu is 295 the time when r became unreachable) is equal to or greater 296 than the LSA maximum age MaxAge (3600 seconds). 298 * The time tc for every LSA recorded if there is not any remote 299 router that are unreachable. 301 During the full adjacency establishment between two routers, either 302 of them may restart to form the adjacency in the normal way as 303 described in the OSPF protocols [RFC2328] and [RFC2740] if it detects 304 that the reachability between them is broken. 306 6. Some Details about Implementations of New Procedures 308 This section describes some implementation options for the record 309 function. The implementations of the retrieve and delete functions 310 depend on the implementation of the record function to some extend 311 and should be trivial after the details of the implementation of the 312 record function are determined. 314 One implementation finds the failure time and LSA change time and 315 records them accordingly. It finds time tu for every remote router r 316 at which r became unreachable because some failures happened at time 317 tu and records the information about . It also finds time tc 318 for every LSA at which the LSA is changed and records the information 319 about tc for the LSA. 321 Another implementation reuses some of the existing information in the 322 link state database such as LSA age, and finds some other information 323 such as failure time and records them. 325 6.1. Finding and Recording Failure Time and LSA Change Time 327 This subsection specifies two methods for finding the failure time. 328 One is more accurate. The other is simpler. In addition, it 329 describes a method for calculating the time for every LSA at which it 330 is changed. 332 If a remote router r becomes unreachable from reachable after the 333 shortest path first algorithm is run against the link state database, 334 then tuple is recorded, where tu is the time at which a 335 failure such as a link down happened that leads to the router r 336 unreachable. Failures can be classified into two classes: link/ 337 interface failures and node failures. When an OSPF router detects a 338 failure, it will regenerate and flood LSAs for the failure. Suppose 339 that ti is the maximum time delay for the OSPF router to detect an 340 interface failure and tn is the maximum time delay for the OSPF 341 router to detect a node failure. For an LSA, assume that tp is the 342 time delay for the LSA to reach the local router from its origin. 344 6.1.1. Finding and Recording Failure Time and LSA Change Time 346 For a point to point link failure in the network, two router LSAs 347 with the link down are regenerated and flooded. One is by each of 348 two end routers of the link. For a broadcast link or NBMA link 349 failure, one network LSA and one or more router LSAs with the 350 information about link down are generated and flooded. The network 351 LSA is generated by the designated router and the router LSAs are 352 generated by the routers attached to the link. 354 Among these LSAs, suppose that tr is the earliest time at which one 355 of the LSAs is received. tp is less than the age of the LSA, which 356 can be used as an estimated value of tp. We can also estimate tp as 357 (255 - TTL of the LSA update packet). We may select the smaller one 358 between these two estimated values for tp. In all these cases, the 359 exact tp is less than its estimated value. The time tu at which the 360 interface failed can be estimated as tu = (tr - ti - tp). The 361 estimated value for tu is earlier than the exact time at which the 362 failure happened. This guarantees that all the LSAs that are changed 363 after the exact tu will be included in the neighbor database summary 364 list if a full adjacency is to be established with router r. 366 For n (n > 1) link failures, the time at which each of these n link 367 failures happened can be calculated as above. The time tu is the 368 earliest time among all these n times. If we can identify m (1 <= m 369 <= n) link failures among these n link failures that results in the 370 remote router r unreachable, we only need to calculate the time at 371 which each of those m link failures happened. In this case, the time 372 tu is the earliest time among all those m times. 374 For one node failure in the network, every node that has a full 375 adjacency with the failed node will regenerate and flood the LSA with 376 the link to the failure node down. Among these LSAs, suppose that tr 377 is the earliest time at which one of these LSAs is received and tp is 378 the time delay for this LSA to reach the local router from its 379 origin, then the time tu at which the node failed can be estimated as 380 tu = (tr - tn - tp). The estimated value for tu is earlier than the 381 exact time at which the failure happened. This guarantees that all 382 the LSAs that are changed after the exact tu will be included in the 383 neighbor database summary list if a full adjacency is to be 384 established with router r. 386 For k (k > 1) node failures in the network, there are at most k 387 groups of LSAs will be regenerated and flooded in the network. Every 388 LSA in one of these groups contains the information about the link to 389 the same failed node down. For each group of LSAs, the time at which 390 the node failed can be estimated in the same way as above for one 391 node failure. The time tu at which the remote router r became 392 unreachable because of k node failures is estimated as the earliest 393 time among all the estimated node failure times. 395 In the case that there are link and node failures in the network, two 396 times are estimated in the ways described above. One time is the 397 time at which the earliest link failure happened. The other is the 398 time at which the earliest node failure happened. The time tu at 399 which the remote router r became unreachable because of link and node 400 failures is estimated as the earlier between these two times. 402 6.1.2. A Simpler Method for Finding Failure Time 404 One simpler way for finding failure time uses all the changed LSAs 405 received. It derives the failure time from every LSA in the way 406 similar to the ones described above and then selects the earliest 407 time as tu. For every changed LSA received at time tr, the failure 408 time derived from this LSA is (tr - max(ti, tn) - tp), where ti, tn 409 and tp are defined above and tp is calculated in the same way as 410 described above. 412 This method is simpler than the method described in the above 413 subsection. But the failure time it estimated may not be as accurate 414 as the one the previous method calculated. Thus the LSAs changed 415 between these two times will be included in the neighbor database 416 summary list when a full adjacency is to be created to router r and 417 this failure time is used as the unreachable time for router r. 418 However, it is not necessary to include these LSAs in the summary 419 list. 421 6.1.3. Finding and Recording LSA Change Time 423 If there exist some remote routers that became unreachable less than 424 MaxAge ago, for an LSA, we use the time tr at which the LSA is 425 received as the time tc at which the LSA is changed for recording the 426 time tc for the LSA. This time may be a little bit later than the 427 exact time at which the LSA is changed. But it guarantees that the 428 LSA will be included in the neighbor database summary list if a full 429 adjacency is to be established with a router r that became 430 unreachable before the exact tc. 432 There are a number of ways for recording the LSA change time. One 433 way is to add a new field similar to the field for LSA age into the 434 data structure for storing LSA and store the estimated change time tc 435 into this new field for each changed LSA. 437 Another way for recording the LSA change time is to add a link field 438 into the data structure for storing an LSA, a new array and a 439 variable for the index of the array into the data structure for 440 storing an area. The link field is used to link all the LSAs that 441 have the same change time together. The size of the array is the 442 number of time units in MaxAge (3600 seconds). A time unit can be 443 one second, 1/10 second or other smaller time unit. This depends on 444 the implementation. The array and the variable for the index can be 445 considered as a relative clock. The index variable starts from 0, 446 and goes up by one every time unit. When it reaches the size of the 447 array, it starts from 0 again. If the value of the index variable is 448 k at the current time, the time tj represented by the element of the 449 array at index j is tj = (current time - time unit * d), where d = (k 450 - j) if k >= j and d = (array size - j + k) if k < j. The element of 451 the array at index j is a pointer that points to the header of the 452 linked list of all the LSAs that are changed at the time tc, where tc 453 = tj or (tc + one time unit) > tj if tc < tj (i.e., rounding up tc is 454 tj). 456 6.2. Reusing LSA Age, Finding and Recording Adjust Time 458 For every remote router r that became unreachable at time tu, tu can 459 be estimated in one of the ways described above. For every changed 460 LSA received at time tr after time tu, its age is less than 255, 461 which is the maximum time to live value in the IP packet containing 462 the LSA. Thus we use tu and reuse the age of an LSA to decide 463 whether the LSA is put into the summary list. When a full adjacency 464 to router r is to be created, every LSA that satisfies the condition 465 "the age of the LSA < the current time - tu + 255" (i.e., "tu - 255 < 466 the current time - the age of the LSA") must be put into the neighbor 467 database summary list. This will guarantee that all the LSAs that 468 were changed after the router r became unreachable are included in 469 the summary list. However, some LSAs that were changed before time 470 tu may be included. In order to reduce the number of the LSAs 471 changed before time tu to be included, we need to find the earliest 472 time te in which the changed LSA was regenerated in term of LSA age. 473 Thus we can use te in place of tu - 255 to decide whether an LSA must 474 be put into the summary list. When a full adjacency to router r is 475 to be created, every LSA that satisfies the condition "te < the 476 current time - the age of the LSA" must be put into the neighbor 477 database summary list. 479 For each changed LSA received at time tr-i after time tu and before 480 time (tu + 255), the time at which the LSA was regenerated is 481 estimated as (tr-i - ta-i), where ta-i is the age of the LSA. The 482 time te is the earliest one among all (tr-i - ta-i). 484 For the case that another remote router r' became unreachable later 485 during the calculation of the time te for router r, we stop finding 486 te and s tart to find the earliest time te' for the remote router r' 487 in the same way as described above and mark that the time te relies 488 on the time te'. When a full adjacency to router r is to be created, 489 the time te is calculated as follows. It is the earliest time among 490 the te partially calculated and the te' that the te depends on. 492 7. Security Considerations 494 The mechanism described in this document does not raise any new 495 security issues for the OSPF protocols. 497 8. IANA Considerations 499 This document specifies a backward compatible intelligent link state 500 database exchange mechanism for OSPFv2 and OSPFv3, which does not 501 require any new number assignment. 503 9. Acknowledgement 505 The author would like to thank Richard Li, Yang Yu, Steve Yao, 506 Quintin Zhao and others for their valuable comments on this draft. 508 10. References 510 10.1. Normative References 512 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 513 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 514 RFC2119, March 1997, 515 . 517 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/ 518 RFC2328, April 1998, 519 . 521 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 522 RFC 2740, DOI 10.17487/RFC2740, December 1999, 523 . 525 10.2. Informative References 527 [RFC5243] Ogier, R., "OSPF Database Exchange Summary List 528 Optimization", RFC 5243, DOI 10.17487/RFC5243, May 2008, 529 . 531 Author's Address 533 Huaimo Chen 534 Huawei 535 Boston, MA 536 US 538 Email: Huaimo.chen@huawei.com