idnits 2.17.1 draft-hsmit-lsr-isis-dnfm-00.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 : ---------------------------------------------------------------------------- No issues found here. 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 (October 22, 2018) is 2006 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) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 LSR Working Group H. Smit, Ed. 3 Internet-Draft 4 Intended status: Standards Track G. Van de Velde 5 Expires: April 25, 2019 Nokia 6 October 22, 2018 8 IS-IS Sparse Link-State Flooding 9 draft-hsmit-lsr-isis-dnfm-00 11 Abstract 13 This document describes a technology extension to reduce link-state 14 flooding in highly resilient dense networks. It does this by using 15 simple and backwards-compatible extensions to reduce the number of 16 adjacencies over which link-state flooding takes place. 18 "IS-IS Sparse Link-State Flooding" is an extension to the IS-IS 19 routing protocol. 21 It is relatively easy to understand and implement. It is backwards 22 compatible. It requires no per-node configuration. It uses a 23 distributed algorithm, therefor no centralized computations are 24 required. No complex computations are required on each node in the 25 network. The algorithm has no requirements for the network topology. 26 It can be deployed in a redundant way to improve robustness and 27 convergence-times. 29 Requirements Language 31 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 32 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 33 document are to be interpreted as described in RFC 2119 [1]. 35 Status of This Memo 37 This Internet-Draft is submitted in full conformance with the 38 provisions of BCP 78 and BCP 79. 40 Internet-Drafts are working documents of the Internet Engineering 41 Task Force (IETF). Note that other groups may also distribute 42 working documents as Internet-Drafts. The list of current Internet- 43 Drafts is at https://datatracker.ietf.org/drafts/current/. 45 Internet-Drafts are draft documents valid for a maximum of six months 46 and may be updated, replaced, or obsoleted by other documents at any 47 time. It is inappropriate to use Internet-Drafts as reference 48 material or to cite them other than as "work in progress." 49 This Internet-Draft will expire on April 25, 2019. 51 Copyright Notice 53 Copyright (c) 2018 IETF Trust and the persons identified as the 54 document authors. All rights reserved. 56 This document is subject to BCP 78 and the IETF Trust's Legal 57 Provisions Relating to IETF Documents 58 (https://trustee.ietf.org/license-info) in effect on the date of 59 publication of this document. Please review these documents 60 carefully, as they describe your rights and restrictions with respect 61 to this document. Code Components extracted from this document must 62 include Simplified BSD License text as described in Section 4.e of 63 the Trust Legal Provisions and are provided without warranty as 64 described in the Simplified BSD License. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 69 2. High level overview of Sparse Link-State Flooding . . . . . . 3 70 3. The Sparse Link-State Flooding algorithm in detail . . . . . 4 71 3.1. Role of the Anchor . . . . . . . . . . . . . . . . . . . 4 72 3.2. Bootstrapping the flooding . . . . . . . . . . . . . . . 4 73 3.3. Determining which adjacency a router wants to flood over 5 74 3.4. Determining where flooding can be suppressed . . . . . . 5 75 4. Using multiple concurrent flooding topologies . . . . . . . . 7 76 5. Benefits of the Sparse Link-State Flooding algorithm . . . . 7 77 6. Extensions to IS-IS PDUs . . . . . . . . . . . . . . . . . . 8 78 6.1. Anchor TLV in LSPs . . . . . . . . . . . . . . . . . . . 8 79 6.2. Flooding-Suppression TLV in IIHs . . . . . . . . . . . . 8 80 7. Operations of the new Sparse Link-State Flooding algorithm . 9 81 7.1. Flooding at the anchor itself . . . . . . . . . . . . . . 9 82 7.2. New action after each SPF . . . . . . . . . . . . . . . . 9 83 7.3. When sending a IIH . . . . . . . . . . . . . . . . . . . 10 84 7.4. When receiving a IIH . . . . . . . . . . . . . . . . . . 10 85 7.5. When installing a new LSP in the LSDB . . . . . . . . . . 10 86 7.6. Preventing loops in the flooding topology . . . . . . . . 10 87 7.7. Fall-back to classic full flooding . . . . . . . . . . . 11 88 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 89 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 90 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 91 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 92 10.2. Informative References . . . . . . . . . . . . . . . . . 11 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 95 1. Introduction 97 In dense network topologies, using massive ECMP or massive numbers of 98 resilient links, the flooding algorithm of link-state protocols is 99 highly redundant. This results in unnecessary overhead, potentially 100 overloading control planes, decreasing robustness and slowing down 101 convergence. Because of this percepted inefficiency, some operators 102 have resorted to using BGP as the IGP in their data center networks. 103 Draft-li-dynamic-flooding [3] describes this in more detail. However 104 it is very clear that using an Exterior Gateway Protocol as an IGP is 105 sub-optimal, if only due to the configuration overhead. 107 This document proposes a technology extension to reduce the number of 108 interfaces over which a link-state protocol floods its updates in 109 highly resilient networks. The result is a sparse flooding topology 110 over a dense physical network topology. We describe details how to 111 implement this algorithm for the IS-IS protocol [2]. This algorithm 112 can be extended to other link-state routing protocols, like OSPF. 113 However, no details for protocols other IS-IS are included in this 114 document. 116 This proposal uses simple and backwards-compatible extensions. It is 117 easy to understand and and relatively easy to implement for IS-IS 118 coders. These proposed IS-IS extensions do not require additional 119 configuration on every router. However, it might be beneficial for 120 the operation of the algorithm to manually configure one or more 121 routers as "anchors" in the network. The purpose of an "anchor" is 122 explained in the next section of this document. This extension uses 123 a distributed algorithm. No centralized calculations need to be 124 performed. Each pair of routers decide for themselves where flooding 125 can be suppressed. After ever regular SPF computation a router can 126 adjust the interfaces over which it does flooding. This decision 127 requires no computational-complex calculations. 129 2. High level overview of Sparse Link-State Flooding 131 The goal of the new Sparse Link-State Flooding algorithm is to create 132 a tree of nodes and links, over which updates will be flooded. This 133 tree is called "the flooding topology". The flooding topology 134 includes all the nodes in the network. But it includes only a 135 (small) subset of all available links in the physical network. 137 The idea is that the flooding topology starts at a single router in 138 the network. This single router is called "the anchor". Routers 139 that are adjacent to the anchor will "attach" or "clamp" themselves 140 to the flooding topology. Making the flooding topology bigger. 141 Their neighbors will "attach" themselves as well, making the flooding 142 topology spread out. In the end all routers will be part of the 143 flooding topology. The flooding topology resembles a tree, with the 144 anchor as the root of the tree. 146 The decision to flood or not flood over an adjacency is a local 147 matter. This makes the algorithm a distributed algorithm. The 148 flooding topology itself is not flooded through the network. Only 149 the location of the anchor(s) is announced in LSPs. An anchor 150 announces itself by including this information in its LSP. Two 151 adjacent routers determine whether they need to exchange LSPs or not 152 via a mechanism using a new TLV in hello PDUs (IIHs). 154 This algorithm can be run once, or multiple times in parallel. This 155 creates one or more concurrent flooding topologies. This provides 156 robustness and faster convergence to the flooding process. We 157 envision that anchors are configured manually, like BGP's Route 158 Reflectors. Or they can be elected automatically. For this the 159 anchor-TLV contains a priority field, to allow operators to have 160 influence on the location of the anchor(s). 162 3. The Sparse Link-State Flooding algorithm in detail 164 3.1. Role of the Anchor 166 Each flooding topology needs a root of its tree. The router acting 167 as root is called "the anchor" of a flooding topology. An anchor 168 router includes information in its LSP to announce that it wants to 169 function as an anchor. This information can be encoded as a new TLV, 170 or as a new capability in the existing IS-IS capability TLV. This 171 choice is open for discussion. 173 The content of this new TLV includes a priority. If multiple routers 174 advertise their willingness to act as an anchor, the anchor with the 175 highest priority is chosen as the anchor. If multiple potential 176 anchors have the same priority, then the router with the highest 177 system-id is chosen as the anchor. 179 Besides announcing itself as an anchor in its LSP, the role of the 180 anchor-route is purely passive. No extra actions are required of the 181 anchor. 183 3.2. Bootstrapping the flooding 185 When a router boots, or when a new adjacency comes up, routers need 186 to synchronize their LSDBs. The reason is that a network could have 187 been partitioned in two separate parts. And flooding over the new 188 adjacency might be the only way to make the two parts of the network 189 aware of each other. 191 After the LSDBs are synchronized, and at least one SPF computation 192 has been executed, the new algorithm can be used. An implementation 193 could use a longer grace period to wait before using the new 194 algorithm, to ensure all or most of the LSPs in a network have been 195 received. 197 3.3. Determining which adjacency a router wants to flood over 199 The decision to do regular flooding, or suppress flooding, is done as 200 follows. After each SPF computation, a router looks at the newly 201 computed route towards the anchor. Each router wants to do flooding 202 over the adjacency to a router that is closer to the anchor than it 203 is itself. This guarantees that each router will do flooding with a 204 router that is already part of the flooding topology. 206 If there are multiple (equal-cost) paths towards the anchor, one of 207 the next-hop adjacencies of the route towards the anchor is chosen to 208 flood over. It doesn't matter which adjacency that is, as long as 209 the adjacent router is closer to the anchor. 211 When the flooding topology breaks, the two routers next to the point 212 of breakage will notice. They will each generate a new LSP. And 213 they will send out that new LSP over the old flooding topology. The 214 LSP generated by the router that is still reachable through the old 215 flooding topology will be received by all routers on their side of 216 the breakage. This will trigger new SPF computations on all those 217 routers. This SPF computation will compute a new path towards the 218 anchor. The routers will now adjust their flooding topology 219 according to the new path they have just computed. All routers in 220 the network do this. New LSPs will be flooded over the new flooding 221 topology. Which might trigger a follow-up SPF computation. Which 222 might cause routers to adjust their flooding topology again. After a 223 while all routers will have received all new LSPs. Which will 224 guarantee that they will all compute a new correct flooding topology. 226 A requirement is that when routers start using an adjacency for their 227 flooding topology, they need to synchronize LSDBs first. This is 228 done by exchanging CSNPs. This can potentially be done more reliable 229 and faster when doing IS-IS Flooding over TCP [4]. 231 3.4. Determining where flooding can be suppressed 233 The decision whether to flood over an adjacency or not is a local 234 matter. Only the two routers of the adjacency are involved in this 235 decision. Both routers have a say in whether flooding will be 236 suppressed or not. 238 This document defines a new TLV, called the Flooding-Suppression TLV, 239 to be included in Hello PDUs (IIHs). This new TLV includes a field 240 that indicates whether a router wants to do flooding over this 241 interface, or wants to suppress flooding. The content of this TLV is 242 set according to the decision made after each SPF, as explained in 243 the previous section of this document. 245 As a result, a router keeps two new pieces of state for each 246 adjacency. 248 o Does the router itself want to flood over this adjacency ? We'll 249 call this the adjacency's "suppression-local-request-state". 251 o Does the neighbor want to flood over this adjacency ? We'll call 252 this the adjacency's "suppression-neighor-request-state". 254 The suppression-local-request-state is determined after each SPF 255 computation. 257 The suppression-neighbor-request-state is learned from examining the 258 Flooding-Suppression TLV in each received IIH. If a router did not 259 include the new Flooding-Suppression TLV in its IIH, it is assumed 260 that the neighbor does want to flood over this adjacency. 262 When both "suppression-local-request-state" and "suppression- 263 neighbor-request-state" are true, then the overall "suppression- 264 state" of the interface is set to true. In that case flooding over 265 the interface is to be suppressed. In all 3 other cases, where at 266 least one of the two routers does not want to suppress flooding, 267 flooding is done in the normal way. 269 So flooding over an adjacency is only suppressed when both neighbors 270 have indicated that they want to suppress flooding over the 271 adjacency. This means that when one of the two routers does not 272 support this new algorithm, and thus does not include the new TLV in 273 its IIH, flooding is always done. This makes the algorithm backwards 274 compatible with routers that do not support this new extension of the 275 protocol. 277 A router will always have one or more flooding adjacencies. One 278 adjacency that the router itself needs, to "clamp" on to the part of 279 the flooding topology that is closer to the anchor than it is itself. 280 This adjacency points towards the anchor. And zero or more 281 adjacencies that its neighbors, downstream of the anchor, use to 282 clamp themselves onto the flooding topology. These adjacencies point 283 away from the anchor. 285 4. Using multiple concurrent flooding topologies 287 It is possible to use more than one flooding topology in parallel. 288 This requires more than one anchor. For each anchor a new flooding 289 topology is built. These flooding topologies can co-exist without 290 problems. 292 All that is required is that after each SPF computation, the router 293 examines the shortest path to each anchor. And sets the local state 294 of each adjacency according to this. This guarantees that the router 295 will "clamp onto" each flooding topology. 297 To ensure an optimal use of parallel flooding topologies, all routers 298 in an IS-IS flooding domain (area or level-2 backbone) should use the 299 same number of parallel flooding topologies. This can be done 300 through configuration. Or an easier way would be to include the 301 number of parallel flooding topologies to use, inside the new Anchor 302 TLV. When looking for Anchors, a router must first find all LSPs 303 with the new Anchor TLV. It then selects the router with the highest 304 Anchor-priority as the main anchor. If multiple router use the same 305 priority, the router with the highest system-id is selected as the 306 anchor. Once the main anchor has been determined, a router looks 307 inside the new anchor-TLV to determine how many parallel flooding 308 topologies it should use. It then selects that amount of anchors 309 with the highest priorities, to set the flooding-state of adjacencies 310 pointing towards those anchors. 312 Flooding suppression is a local matter. Therefore an implementation 313 can decide to flood over more adjacencies than the minimum to build 314 the minimal flooding topology. It can signal this through the 315 Flooding-Supression TLV in its IIHs. This can improve robustness and 316 convergence times, at the cost of some extra flooding overhead. 318 5. Benefits of the Sparse Link-State Flooding algorithm 320 The algorithm described in this document has a number of advantages. 322 o The algorithm is a distributed algorithm. Distributed algorithms 323 are usually more robust than centralized algorithms. The flooding 324 topology itself does not need to be flooded, which makes the 325 algorithm easier when the flooding topology breaks. 327 o The algorithm is backwards compatible. No flag-day is required to 328 introduce this new sparse-flooding extension. Older routers that 329 do not support the new extension will obviously not include the 330 flooding-state TLV in their IIHs. The result of this is that 331 regular flooding is done over all adjacencies of those older 332 routers. This guarantees that older routers will never break the 333 flooding topology. 335 o No extra computations have to be done to compute the flooding 336 topology. Using the result of the regular SPF computation 337 suffices to determine over which adjacencies a router wants to 338 flood. 340 o The proposed algorithm is robust and guarantees that a flooding 341 topology eventually heals so that all routers are included in the 342 flooding again. 344 o Several instances of the algorithm can be run in parallel. This 345 results in multiple parallel flooding topologies. Although 346 parallel flooding topologies are not required for correct 347 operation of the algorithm, it will help in speeding up the 348 healing of the flooding topology. And thus convergence times in 349 general. 351 6. Extensions to IS-IS PDUs 353 To implement this algorithm, we need two extensions of IS-IS PDUs. 355 6.1. Anchor TLV in LSPs 357 A new Anchor TLV in the LinkState PDUs. This TLV indicates that a 358 router can be used as an anchor. This new TLV must include a 359 priority field. And it should include a field that suggests how many 360 parallel flooding topologies all routers should use. 362 6.2. Flooding-Suppression TLV in IIHs 364 A new Flooding-Suppression TLV in the IIH PDUs. This TLV is used to 365 indicate to the neighbor if a router wants to suppress flooding over 366 the adjacency. This new TLV holds three fields: 368 o Flooding suppression suggestion field: this field indicates 369 whether the sending router would like to suppress flooding over 370 this interface or not. The value of this field is set to the 371 current "suppression-local-request-state". Note, only when two 372 routers both indicate they want to suppress flooding, then 373 flooding will indeed be suppressed. 375 o Resulting actual suppression field: this field indicates whether 376 the sending router will or will not do flooding. The value of 377 this field is set to the current "suppression-state" of the 378 interface. This field is included only for debugging purposes. 379 The first field (the received suppression-local-request-state 380 field) is used to make the flooding decision. The result of that 381 decision is announced in the second field. 383 o The number of currently active flooding adjacencies. This field 384 can be used by the receiving router to pick a flooding adjacency 385 when there are multiple ECMP paths towards the anchor. A router 386 can pick the upstream router with the least amount of flooding 387 adjacencies. In dense networks with many parallel paths, this can 388 help spreading out the load of flooding equally over multiple 389 routers. 391 Backward compatibility: when a router does not include the Flooding- 392 State TLV in the IIHs it sends out, it can be treated as if that 393 router included the Flooding-State TLV while setting the first field 394 to: "I do not want to suppress flooding". 396 7. Operations of the new Sparse Link-State Flooding algorithm 398 7.1. Flooding at the anchor itself 400 When a router is acting as the anchor, it floods over all its 401 interfaces. It does include the Flooding-Suppression TLV in its 402 IIHs, but it always sets the value inside the new TLV to "I do not 403 want to suppress flooding". 405 7.2. New action after each SPF 407 At the end of each SPF computation, a router looks at the best-path 408 to reach the anchor-router. The router sets the "suppression-local- 409 request-state" for that adjacency to false. The router sets the 410 "suppression-local-request-state" for all other adjacencies to true. 412 If the best-path to the anchor-router's is load-balanced over 413 multiple adjacencies, the router picks one of those adjacencies as 414 its own "upstream flooding adjacencies". 416 A router must take effort to ensure it changes its "upstream flooding 417 adjacency" as little as possible. Switching its upstream flooding 418 adjacency is not without cost. Every time an adjacency changes from 419 suppressed flooding to normal flooding, the LSDBs of the two routers 420 must be synchronized. 422 If the "suppression-local-request-state" changed for one or more 423 adjacencies, compared to the state after the previous SPF 424 computation, the router will re-compute the "suppression-state". If 425 the "suppression-state" of an adjacency changes, the router will 426 start or stop flooding over that adjacency. 428 7.3. When sending a IIH 430 When a router sends an IIH, it includes the new Flooding-Suppression 431 TLV. 433 For adjacencies that were selected as "upstream flooding adjacency", 434 the value of the Flooding-Suppression TLV must be set to: "I do not 435 want to suppress flooding". For all other adjacencies the value must 436 be set to: "I do want to suppress flooding". 438 7.4. When receiving a IIH 440 When a router receives an IIH, it checks for the existence of the new 441 Flooding-Suppression TLV. 443 If it there is none, the state of the neighbor is assumed to be: "I 444 do not want to suppress flooding". 446 If the "suppression-remote-request-state" changed for this adjacency, 447 compared to the state after receiving the previous IIH, the router 448 will re-compute the "suppression-state". If the "suppression-state" 449 of an adjacency changes, the router will start or stop flooding over 450 that adjacency. 452 7.5. When installing a new LSP in the LSDB 454 When a router receives a new LSP, it installs it in the LSDB. It 455 will normally then set the IS-IS SRM (Send Routing Message) bits for 456 all adjacencies (in UP state). Now, with the new algorithm, it will 457 set SRM-bits for only the adjacencies that are part of the reduced 458 flooding topology. 460 7.6. Preventing loops in the flooding topology 462 When the flooding topology changes, during a short period of time 463 different routers can have a different view of the flooding topology. 464 This can make the actual flooding topology in use be a random cyclic 465 graph, instead of a non-cyclic tree. This is not a problem. The 466 flooding algorithm in link-state protocols deals with this by 467 default. An LSP is only (scheduled to be) flooded the first time it 468 is received and installed in the LSDB. 470 The Sparse Link-State Flooding algorithm has some resemblance to the 471 Spanning Tree Protocol used by transparent bridges. Transient 472 forwarding loops can be a huge problem in the operation of a SPT 473 network. However, while the flooding topology can be looping for 474 short periods of time, this is not a problem at all. Because as 475 described in the previous paragraph, link-state flooding will take 476 care of this by default. This works because routers keep copies of 477 the LSPs they forward in their LSDB. This allows them to determine 478 if they have received an LSP before or not. In STP routers have no 479 recollection of data-frames that they have forwarded in the past. So 480 in STP looping frames can not be recognized as looping. 482 To improve convergence times during changes of the flooding topology 483 it is recommended that when a router changes the state of an 484 adjacency from flooding to non-flooding, both routers keep flooding 485 over this adjacency for a short period of time. A suggested value 486 for this is 30 or 60 seconds. By doing this, during changes of the 487 flooding topology, both the old and the new topology will be in use. 488 This guarantees that LSPs are flooded as quickly as possible. This 489 will also help in repairing the flooding topology itself. 491 7.7. Fall-back to classic full flooding 493 When a router thinks it might have got behind on flooding, it can 494 always fall back to normal flooding behaviour. It omits including 495 the Flooding-Suppression TLV from its IIHs. Consequently, classic 496 flooding will allow guaranteed synchronization of its IS-IS LSDB with 497 all neighbors. This can be done on all adjacencies at once, or on 498 subset. 500 8. Security Considerations 502 This draft introduces no new security considerations. 504 9. IANA Considerations 506 This document requests a new TLV and sub-TLV for IS-IS. 508 10. References 510 10.1. Normative References 512 [1] Bradner, S., "Key words for use in RFCs to Indicate 513 Requirement Levels", BCP 14, RFC 2119, March 1997, 514 . 516 10.2. Informative References 518 [2] International Standard 10589, "Intermediate System to 519 Intermediate System intra- domain routeing information 520 exchange protocol for use in conjunction with the protocol 521 for providing the connectionless-mode network service (ISO 522 8473), Second Edition.", 2002. 524 [3] Li, T. and P. Psenak, "Dynamic Flooding on Dense Graphs", 525 June 2018. 527 [4] Smit, H. and G. Van De Velde, "IS-IS Flooding over TCP", 528 October 2018. 530 Authors' Addresses 532 Henk Smit (editor) 533 NL 535 Email: hhw.smit@xs4all.nl 537 Gunter Van de Velde 538 Nokia 539 Copernicuslaan 50 540 Antwerp 541 BE 543 Email: gunter.van_de_velde@nokia.com