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