idnits 2.17.1 draft-cc-lsr-flooding-reduction-07.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 : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 17, 2019) is 1652 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: 'RFC1195' is defined on line 294, but no explicit reference was found in the text == Unused Reference: 'RFC2328' is defined on line 303, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-spf-uloop-pb-statement' is defined on line 309, but no explicit reference was found in the text == Unused Reference: 'RFC8126' is defined on line 315, but no explicit reference was found in the text == Outdated reference: A later version (-18) exists of draft-ietf-lsr-dynamic-flooding-03 ** Downref: Normative reference to an Experimental draft: draft-ietf-lsr-dynamic-flooding (ref. 'I-D.ietf-lsr-dynamic-flooding') Summary: 2 errors (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Chen 3 Internet-Draft Futurewei 4 Intended status: Standards Track D. Cheng 5 Expires: April 19, 2020 Individual 6 M. Toy 7 Verizon 8 Y. Yang 9 IBM 10 A. Wang 11 China Telecom 12 X. Liu 13 Volta Networks 14 Y. Fan 15 Casa Systems 16 L. Liu 17 Fujitsu 18 October 17, 2019 20 Flooding Topology Computation Algorithm 21 draft-cc-lsr-flooding-reduction-07 23 Abstract 25 This document proposes an algorithm for a node to compute a flooding 26 topology, which is a subgraph of the complete topology per underline 27 physical network. When every node in an area automatically 28 calculates a flooding topology by using a same algorithm and floods 29 the link states using the flooding topology, the amount of flooding 30 traffic in the network is greatly reduced. This would reduce 31 convergence time with a more stable and optimized routing 32 environment. 34 Requirements Language 36 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 37 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 38 document are to be interpreted as described in RFC 2119 [RFC2119]. 40 Status of This Memo 42 This Internet-Draft is submitted in full conformance with the 43 provisions of BCP 78 and BCP 79. 45 Internet-Drafts are working documents of the Internet Engineering 46 Task Force (IETF). Note that other groups may also distribute 47 working documents as Internet-Drafts. The list of current Internet- 48 Drafts is at https://datatracker.ietf.org/drafts/current/. 50 Internet-Drafts are draft documents valid for a maximum of six months 51 and may be updated, replaced, or obsoleted by other documents at any 52 time. It is inappropriate to use Internet-Drafts as reference 53 material or to cite them other than as "work in progress." 55 This Internet-Draft will expire on April 19, 2020. 57 Copyright Notice 59 Copyright (c) 2019 IETF Trust and the persons identified as the 60 document authors. All rights reserved. 62 This document is subject to BCP 78 and the IETF Trust's Legal 63 Provisions Relating to IETF Documents 64 (https://trustee.ietf.org/license-info) in effect on the date of 65 publication of this document. Please review these documents 66 carefully, as they describe your rights and restrictions with respect 67 to this document. Code Components extracted from this document must 68 include Simplified BSD License text as described in Section 4.e of 69 the Trust Legal Provisions and are provided without warranty as 70 described in the Simplified BSD License. 72 Table of Contents 74 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 75 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 76 3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 3 77 3.1. Flooding Topology Construction . . . . . . . . . . . . . 3 78 4. Algorithms to Compute Flooding Topology . . . . . . . . . . . 4 79 4.1. Algorithm with Considering Degree . . . . . . . . . . . . 5 80 4.2. Algorithm with Considering Others . . . . . . . . . . . . 5 81 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6 82 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 83 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6 84 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 85 8.1. Normative References . . . . . . . . . . . . . . . . . . 7 86 8.2. Informative References . . . . . . . . . . . . . . . . . 7 87 Appendix A. FT Computation Details through Example . . . . . . . 7 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 90 1. Introduction 92 For some networks such as dense Data Center (DC) networks, the 93 existing Link State (LS) flooding mechanism is not efficient and may 94 have some issues. The extra LS flooding consumes network bandwidth. 95 Processing the extra LS flooding, including receiving, buffering and 96 decoding the extra LSs, wastes memory space and processor time. This 97 may cause scalability issues and affect the network convergence 98 negatively. 100 This document proposes an algorithm for a node to compute a flooding 101 topology, which is a subgraph of the complete topology per underline 102 physical network. When every node in an area automatically 103 calculates a flooding topology by using a same algorithm and floods 104 the link states using the flooding topology, the amount of flooding 105 traffic in the network is greatly reduced. This would reduce 106 convergence time with a more stable and optimized routing 107 environment. 109 There may be multiple algorithms for computing a flooding topology. 110 Users can select one they prefer, and smoothly switch from one to 111 another. 113 2. Terminology 115 LSA: A Link State Advertisement in OSPF. 117 LSP: A Link State Protocol Data Unit (PDU) in IS-IS. 119 LS: A Link Sate, which is an LSA or LSP. 121 FT: Flooding Topology. 123 FTC: Flooding Topology Computation. 125 3. Flooding Topology 127 For a given network topology, a flooding topology is a sub-graph or 128 sub-network of the given network topology that has the same 129 reachability to every node as the given network topology. Thus all 130 the nodes in the given network topology MUST be in the flooding 131 topology. All the nodes MUST be inter-connected directly or 132 indirectly. As a result, LS flooding will in most cases occur only 133 on the flooding topology, that includes all nodes but a subset of 134 links. Note even though the flooding topology is a sub-graph of the 135 original topology, any single LS MUST still be disseminated in the 136 entire network. 138 3.1. Flooding Topology Construction 140 Many different flooding topologies can be constructed for a given 141 network topology. For example, a chain connecting all the nodes in 142 the given network topology is a flooding topology. A circle 143 connecting all the nodes is another flooding topology. A tree 144 connecting all the nodes is a flooding topology. In addition, the 145 tree plus the connections between some leaves of the tree and branch 146 nodes of the tree is a flooding topology. 148 The following parameters need to be considered for constructing a 149 flooding topology: 151 o Degree: The degree of the flooding topology is the maximum degree 152 among the degrees of the nodes on the flooding topology. The 153 degree of a node on the flooding topology is the number of 154 connections on the flooding topology it has to other nodes. 156 o Number of links: The number of links on the flooding topology is a 157 key factor for reducing the amount of LS flooding. In general, 158 the smaller the number of links, the less the amount of LS 159 flooding. 161 o Diameter: The diameter of the flooding topology is the shortest 162 distance between the two most distant nodes on the flooding 163 topology. It is a key factor for reducing the network convergence 164 time. The smaller the diameter, the less the convergence time. 166 o Redundancy: The redundancy of the flooding topology means a 167 tolerance to the failures of some links and nodes on the flooding 168 topology. If the flooding topology is split by some failures, it 169 is not tolerant to these failures. In general, the larger the 170 number of links on the flooding topology is, the more tolerant the 171 flooding topology to failures. 173 Note that the flooding topology constructed by a node is dynamic in 174 nature, that means when the base topology (the entire topology graph) 175 changes, the flooding topology (the sub-graph) MUST be re-computed/ 176 re-constructed to ensure that any node that is reachable on the base 177 topology MUST also be reachable on the flooding topology. 179 4. Algorithms to Compute Flooding Topology 181 There are many algorithms to compute a flooding topology. A simple 182 and efficient one is briefed, which comprises: 184 o Selecting a node R0 with the smallest node ID; 186 o Building a tree using R0 as root in breadth first; and then 188 o Connecting each node whose degree is one to another node to have a 189 flooding topology. 191 4.1. Algorithm with Considering Degree 193 The algorithm is described below. The detailed FT computation by the 194 algorithm is illustrated in Appendix A through an example. 196 The algorithm starts from node R0 as root with a given maximum degree 197 MaxD such as MaxD = 3, a candidate queue Cq = {(R0, D = 0, PHs = { 198 })}, and an empty flooding topology FT = { }. Cq contains one 199 element (R0, D = 0, PHs = { }), where node R0 is the root, D = 0 200 indicates that the Degree (D for short) of R0 is 0 (i.e., the number 201 of links on the flooding topology connected to R0 is 0), PHs = { } 202 indicates that the Previous Hops (PHs for short) of R0 is empty. 204 1. Finding and removing the first element with node A in Cq that is 205 not on FT and one PH's D in PHs < MaxD. 207 If A is root R0, then add the element into FT 209 otherwise (i.e., A != R0 with one PH's D in PHs < MaxD. Assume 210 that PH is the first one in PHs whose D < MaxD), PH's D++, and 211 add A with D = 1 and PHs = {PH} into FT. 213 Note: if there is no element in Cq satisfying the conditions, 214 then algorithm may be restarted from R0, ++MaxD, Cq = 215 {(R0,D=0,PHs = { })}, FT = { }; 217 2. If all the nodes are on the FT, then goto step 4; 219 3. Suppose that node Xi (i = 1, 2,..., n) is connected to node A and 220 not on FT, and X1, X2,..., Xn are in an increasing order by their 221 IDs (i.e., X1's ID < X2's ID < ... < Xn's ID). If Xi is not in 222 Cq, then add it into the end of Cq with D = 0 and PHs = {A}; 223 otherwise (i.e., Xi is in Cq), add A into the end of Xi's PHs; 224 Goto step 1. 226 4. For each node B on FT whose D is one (from minimum to maximum 227 node ID), find a link L attached to B such that L's remote node R 228 has minimum D and ID, add link L between B and R into FT and 229 increase B's D and R's D by one. Return FT. 231 4.2. Algorithm with Considering Others 233 There may be some constraints on some nodes in a network. For 234 example, in a spine-and-leaf network, there may be a constraint on 235 the degree of every leaf node on the flooding topology, which is that 236 the degree of every leaf node is not greater than a given number 237 ConMaxD such as ConMaxD = 2. For each of the other nodes such as the 238 spine nodes, there is no such constraint, that is that ConMaxD is a 239 huge number for each of these nodes. 241 Step 1 of the algorithm described above is updated below to consider 242 this constraint. In addition to checking constraint PH's D < MaxD, 243 step 1 checks another constraint PH's D < PH's ConMaxD. 245 1. Finding and removing the first element with node A in Cq that is 246 not on FT and one PH's D in PHs < MaxD and PH's D < PH's ConMaxD. 248 If A is root R0, then add the element into FT 250 otherwise (i.e., A != R0 with one PH's D in PHs < MaxD and PH's 251 D < PH's ConMaxD. Assume that PH is the first one in PHs 252 whose D < MaxD and PH's D < PH's ConMaxD), PH's D++, and add A 253 with D = 1 and PHs = {PH} into FT. 255 Note: if there is no element with a node in Cq satisfying the 256 conditions, then algorithm may be restarted from R0, ++MaxD, 257 Cq = {(R0,D=0,PHs = { })}, FT = { }; 259 5. Security Considerations 261 This document does not introduce any new security issue. 263 6. IANA Considerations 265 Under Registry Name: "IGP Algorithm Type For Computing Flooding 266 Topology" under an existing "Interior Gateway Protocol (IGP) 267 Parameters" IANA registries (refer to Section 7.3. IGP 268 [I-D.ietf-lsr-dynamic-flooding]), IANA is requested to assign one 269 value of IGP Algorithm Type For Computing Flooding Topology as 270 follows: 272 +==========+========================================+=============+ 273 |Type Value| Type Name | reference | 274 +==========+========================================+=============+ 275 | 1 | Breadth First Minimum Degree Algorithm |This document| 276 +----------+----------------------------------------+-------------+ 278 7. Acknowledgements 280 The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, 281 Stephane Litkowski and Alvaro Retana for their valuable suggestions 282 and comments on this draft. 284 8. References 286 8.1. Normative References 288 [I-D.ietf-lsr-dynamic-flooding] 289 Li, T., Psenak, P., Ginsberg, L., Chen, H., Przygienda, 290 T., Cooper, D., Jalil, L., and S. Dontula, "Dynamic 291 Flooding on Dense Graphs", draft-ietf-lsr-dynamic- 292 flooding-03 (work in progress), June 2019. 294 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 295 dual environments", RFC 1195, DOI 10.17487/RFC1195, 296 December 1990, . 298 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 299 Requirement Levels", BCP 14, RFC 2119, 300 DOI 10.17487/RFC2119, March 1997, 301 . 303 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 304 DOI 10.17487/RFC2328, April 1998, 305 . 307 8.2. Informative References 309 [I-D.ietf-rtgwg-spf-uloop-pb-statement] 310 Litkowski, S., Decraene, B., and M. Horneffer, "Link State 311 protocols SPF trigger and delay algorithm impact on IGP 312 micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-10 313 (work in progress), January 2019. 315 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 316 Writing an IANA Considerations Section in RFCs", BCP 26, 317 RFC 8126, DOI 10.17487/RFC8126, June 2017, 318 . 320 Appendix A. FT Computation Details through Example 322 This section presents the details on FT computation by the algorithm 323 through an example. The detailed procedure of computing a FT for a 324 network of five nodes with full mess connections is illustrated. 325 Suppose that the network has five nodes R0, R1, R2, R3 and R4; R0's 326 ID < R1's ID < R2's ID < R3's ID < R4's ID. The algorithm starts 327 with Cq = {(R0, D=0, PH={})}, FT = {}, MaxD = 3. 329 0. // remove the first element containing root R0 from Cq 330 Cq = { }; 331 // add the element into FT 332 FT = { (R0,D=0,PHs={ }) }; // root R0 on FT 333 // for each Ri connected to R0 (not in Cq), add it to the end of Cq 334 Cq = { (R1,D=0,PHs={R0}), (R2,D=0,PHs={R0}), (R3,D=0,PHs={R0}), 335 ^^^^^^^^^^^^^^^^^ (R4,D=0,PHs={R0}) } 337 R0 338 __/--- O ---\__ 339 __/ / \ \__ 340 __/ / \ \__ 341 __/ / \ \__ 342 / / \ \ 343 R1 O--\_--------/---------\--------_/--O R4 344 \ \____ / \ ____/ / 345 \ \/ \/ / 346 \ /\_____ ____/\ / 347 \ / ___\__/___ \ / 348 \ / / \ \ / 349 \/____/ \___\/ 350 R2 O -------------------- O R3 352 1. //remove first element (R1,D=0,PHs={R0}) from Cq, R0's D=0 < MaxD 353 Cq = { (R2,0,{R0}), (R3,0,{R0}), (R4,0,{R0}) }; 354 // add (R1,1,{R0}) into FT, increase PH R0's D by one 355 FT = { (R0,1, { }), (R1,1, {R0}) }; // Link R1--R0 on FT 356 ^^^ ^^^^^^^^^^^^ 357 // for Ri connected to R1 (in Cq) not on FT, append R1 to Ri's PHs 358 Cq = { (R2,0, {R0,R1}), (R3,0, {R0,R1}), (R4,0,{R0,R1}) }. 359 ^^ ^^ ^^ 360 R0 ==== Link on FT 361 __//== O ---\__ 362 __// / \ \__ link R1--R0 added to FT 363 __// / \ \__ 364 __// / \ \__ 365 // / \ \ 366 R1 O--\_--------/---------\--------_/--O R4 367 \ \____ / \ ____/ / 368 \ \/ \/ / 369 \ /\_____ ____/\ / 370 \ / ___\__/___ \ / 371 \ / / \ \ / 372 \/____/ \___\/ 373 R2 O --------------------- O R3 375 2. // remove the first element (R2,0, {R0,R1}) from Cq, R0's D=1 < MaxD 376 Cq = { (R3,0, {R0,R1}), (R4,0,{R0,R1}) } 377 // add (R2,1,{R0}) into FT, increase R0's D by one 378 FT = { (R0,2,{ }), (R1,1,{R0}), (R2,1,{R0}) } //Link R2--R0 on FT 379 ^^^ ^^^^^^^^^^^ 380 // for Ri connected to R2 (in Cq) not on FT, append R2 to Ri's PHs 381 Cq = { (R3,0, {R0,R1,R2}), (R4,0,{R0,R1,R2}) } 382 ^^ ^^ 383 R0 ==== Link on FT 384 __//== O ---\__ 385 __// // \ \__ link R2--R0 added to FT 386 __// // \ \__ 387 __// // \ \__ 388 // // \ \ 389 R1 O--\_-------//---------\--------_/--O R4 390 \ \____ // \ ____/ / 391 \ \/ \/ / 392 \ //\_____ ____/\ / 393 \ // ___\__/___ \ / 394 \ // / \ \ / 395 \/____/ \___\/ 396 R2 O --------------------- O R3 398 3. //remove the 1st element (R3,0,{R0,R1,R2}) from Cq, R0's D=2 < MaxD 399 Cq = { (R4,0,{R0,R1,R2}) } 400 // add (R3,1,{R0}) into FT, increase R0's D by one 401 FT = { (R0,3,{}), (R1,1,{R0}), (R2,1,{R0}), (R3,1,{R0}) } 402 ^^^ ^^^^^^^^^^^ 403 // for Ri connected to R3 (in Cq) not on FT, append R3 to Ri's PHs 404 Cq = { (R4,0,{R0,R1,R2,R3}) }. 405 ^^ 406 R0 ==== Link on FT 407 __//== O ---\__ 408 __// // \\ \__ link R3--R0 added to FT 409 __// // \\ \__ 410 __// // \\ \__ 411 // // \\ \ 412 R1 O--\_-------//---------\\-------_/--O R4 413 \ \____ // \\ ____/ / 414 \ \/ \/ / 415 \ //\_____ ____/\\ / 416 \ // ___\__/___ \\ / 417 \ // / \ \\ / 418 \/____/ \___\/ 419 R2 O --------------------- O R3 421 4. //remove the 1st element (R4,0,{R0,R1,R2,R3}) from Cq,R1's D=1 < MaxD 422 Cq = { } 423 // add (R4,1,{R1}) into FT, increase R1's D by one 424 FT = {(R0,3,{}), (R1,2,{R0}), (R2,1,{R0}), (R3,1,{R0}), (R4,1,{R1})} 425 ^^^ ^^^^^^^^^^^ 426 R0 ==== Link on FT 427 __//== O ---\__ 428 __// // \\ \__ link R4--R1 added to FT 429 __// // \\ \__ 430 __// // \\ \__ 431 // // \\ \ 432 R1 O==\_=======//=========\\=======_/==O R4 433 \ \____ // \\ ____/ / 434 \ \/ \/ / 435 \ //\_____ ____/\\ / 436 \ // ___\__/___ \\ / 437 \ // / \ \\ / 438 \/____/ \___\/ 439 R2 O --------------------- O R3 441 All nodes are on FT now. In the following, for each node on FT whose 442 D = 1 (from minimum to maximum ID), link L attached to it and not on 443 FT is found such that L's remote node has minimum D and ID. L is 444 added into FT. 446 5. // On FT, get node R2 with smallest ID whose D=1 447 FT = {(R0,3,{}),(R1,2,{R0}),(R2,1,{R0}),(R3,1,{R0}), (R4,1,{R1})} 448 // Add link R2--R3 to FT, ^^^^^^^^^^^ 449 // where R2--R3 is not on FT, R3's D=1 is minimum first and then 450 // R3's ID is minimum (R3 and R4 tie for D), R2's D++ and R3's D++ 451 FT = {(R0,3,{}),(R1,2,{R0}),(R2,2,{R0,R3}),(R3,2,{R0}),(R4,1,{R1})} 452 ^^^ ^^ ^^^ 453 R0 ==== Link on FT 454 __//== O ---\__ 455 __// // \\ \__ link R2--R3 added to FT 456 __// // \\ \__ 457 __// // \\ \__ 458 // // \\ \ 459 R1 O==\_=======//=========\\=======_/==O R4 460 \ \____ // \\ ____/ / 461 \ \/ \/ / 462 \ //\_____ ____/\\ / 463 \ // ___\__/___ \\ / 464 \ // / \ \\ / 465 \/____/ \___\/ 466 R2 O ===================== O R3 468 6. // On FT, get node R4 with smallest ID whose D=1 469 FT = {(R0,3,{}),(R1,2,{R0}),(R2,2,{R0,R3}),(R3,2,{R0}),(R4,1,{R1})} 470 // Add link R4--R2 to FT, where ^^^^^^^^^^^ 471 // R4--R2 is not on FT, R2's D=2 is minimum first and then R2's ID is 472 // minimum (R2 and R3 tie for D), increase R2's D and R4's D by one 473 FT = {(R0,3,{}),(R1,2,{R0}),(R2,3,{R0,R3}),(R3,2,{R0}),(R4,2,{R1,R2})} 474 ^^^ ^^^ ^^ 475 R0 ==== Link on FT 476 __//== O ---\__ 477 __// // \\ \__ link R4--R2 added to FT 478 __// // \\ \__ 479 __// // \\ \__ 480 // // \\ \ 481 R1 O==\_=======//=========\\=======//==O R4 482 \ \____ // \\ ____// / 483 \ \/ \// / 484 \ //\_____ ___//\\ / 485 \ // ___\__//__ \\ / 486 \ // // \ \\ / 487 \/ _// \___\/ 488 R2 O ==//================= O R3 490 FT is computed, which has Degree of 3 and Diameter of 2. 492 Authors' Addresses 494 Huaimo Chen 495 Futurewei 496 Boston 497 USA 499 Email: huaimo.chen@futurewei.com 501 Dean Cheng 502 Individual 503 Santa Clara 504 USA 506 Email: deanccheng@gmail.com 508 Mehmet Toy 509 Verizon 510 USA 512 Email: mehmet.toy@verizon.com 513 Yi Yang 514 IBM 515 Cary, NC 516 United States of America 518 Email: yyietf@gmail.com 520 Aijun Wang 521 China Telecom 522 Beiqijia Town, Changping District 523 Beijing 102209 524 China 526 Email: wangaj.bri@chinatelecom.cn 528 Xufeng Liu 529 Volta Networks 530 McLean, VA 531 USA 533 Email: xufeng.liu.ietf@gmail.com 535 Yanhe Fan 536 Casa Systems 537 USA 539 Email: yfan@casa-systems.com 541 Lei Liu 542 Fujitsu 543 USA 545 Email: liulei.kddi@gmail.com