idnits 2.17.1 draft-ietf-lsr-flooding-topo-min-degree-04.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 (31 December 2021) is 818 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 301, but no explicit reference was found in the text == Unused Reference: 'RFC2328' is defined on line 310, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-spf-uloop-pb-statement' is defined on line 316, but no explicit reference was found in the text == Unused Reference: 'RFC8126' is defined on line 324, but no explicit reference was found in the text == Outdated reference: A later version (-17) exists of draft-ietf-lsr-dynamic-flooding-10 ** 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: 4 July 2022 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 31 December 2021 18 Flooding Topology Minimum Degree Algorithm 19 draft-ietf-lsr-flooding-topo-min-degree-04 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 4 July 2022. 55 Copyright Notice 57 Copyright (c) 2021 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 (https://trustee.ietf.org/ 62 license-info) in effect on the date of publication of this document. 63 Please review these documents carefully, as they describe your rights 64 and restrictions with respect to this document. Code Components 65 extracted from this document must include Revised BSD License text as 66 described in Section 4.e of the Trust Legal Provisions and are 67 provided without warranty as described in the Revised BSD License. 69 Table of Contents 71 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 72 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 73 3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 3 74 3.1. Flooding Topology Construction . . . . . . . . . . . . . 4 75 4. Algorithms to Compute Flooding Topology . . . . . . . . . . . 4 76 4.1. Algorithm with Considering Degree . . . . . . . . . . . . 5 77 4.2. Algorithm with Considering Others . . . . . . . . . . . . 6 78 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6 79 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 80 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 81 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 82 8.1. Normative References . . . . . . . . . . . . . . . . . . 7 83 8.2. Informative References . . . . . . . . . . . . . . . . . 7 84 Appendix A. FT Computation Details through Example . . . . . . . 8 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 87 1. Introduction 89 For some networks such as dense Data Center (DC) networks, the 90 existing Link State (LS) flooding mechanism is not efficient and may 91 have some issues. The extra LS flooding consumes network bandwidth. 92 Processing the extra LS flooding, including receiving, buffering and 93 decoding the extra LSs, wastes memory space and processor time. This 94 may cause scalability issues and affect the network convergence 95 negatively. 97 This document proposes an algorithm for a node to compute a flooding 98 topology, which is a subgraph of the complete topology per underline 99 physical network. The physical network can be any network, including 100 clos leaf spine network. It can be used in the distributed mode of 101 flooding topology computation for flooding reduction and the 102 centralized mode, which are described in 103 [I-D.ietf-lsr-dynamic-flooding]. When the distributed mode is 104 selected, every node in an area automatically calculates a flooding 105 topology by using a same algorithm and floods the link states using 106 the flooding topology, the amount of flooding traffic in the network 107 is greatly reduced. This would reduce convergence time with a more 108 stable and optimized routing environment. 110 There may be multiple algorithms for computing a flooding topology. 111 Users can select one they prefer, and smoothly switch from one to 112 another. 114 2. Terminology 116 LSA: A Link State Advertisement in OSPF. 118 LSP: A Link State Protocol Data Unit (PDU) in IS-IS. 120 LS: A Link Sate, which is an LSA or LSP. 122 FT: Flooding Topology. 124 FTC: Flooding Topology Computation. 126 3. Flooding Topology 128 For a given network topology, a flooding topology is a sub-graph or 129 sub-network of the given network topology that has the same 130 reachability to every node as the given network topology. Thus all 131 the nodes in the given network topology MUST be in the flooding 132 topology. All the nodes MUST be inter-connected directly or 133 indirectly. As a result, LS flooding will in most cases occur only 134 on the flooding topology, that includes all nodes but a subset of 135 links. Note even though the flooding topology is a sub-graph of the 136 original topology, any single LS MUST still be disseminated in the 137 entire network. 139 3.1. Flooding Topology Construction 141 Many different flooding topologies can be constructed for a given 142 network topology. For example, a chain connecting all the nodes in 143 the given network topology is a flooding topology. A circle 144 connecting all the nodes is another flooding topology. A tree 145 connecting all the nodes is a flooding topology. In addition, the 146 tree plus the connections between some leaves of the tree and branch 147 nodes of the tree is a flooding topology. 149 The following parameters need to be considered for constructing a 150 flooding topology: 152 * Degree: The degree of the flooding topology is the maximum degree 153 among the degrees of the nodes on the flooding topology. The 154 degree of a node on the flooding topology is the number of 155 connections on the flooding topology it has to other nodes. 157 * Number of links: The number of links on the flooding topology is a 158 key factor for reducing the amount of LS flooding. In general, 159 the smaller the number of links, the less the amount of LS 160 flooding. 162 * Diameter: The diameter of the flooding topology is the shortest 163 distance between the two most distant nodes on the flooding 164 topology. It is a key factor for reducing the network convergence 165 time. The smaller the diameter, the less the convergence time. 167 * Redundancy: The redundancy of the flooding topology means a 168 tolerance to the failures of some links and nodes on the flooding 169 topology. If the flooding topology is split by some failures, it 170 is not tolerant to these failures. In general, the larger the 171 number of links on the flooding topology is, the more tolerant the 172 flooding topology to failures. 174 Note that the flooding topology constructed by a node is dynamic in 175 nature, that means when the base topology (the entire topology graph) 176 changes, the flooding topology (the sub-graph) MUST be re-computed/ 177 re-constructed to ensure that any node that is reachable on the base 178 topology MUST also be reachable on the flooding topology. 180 4. Algorithms to Compute Flooding Topology 182 There are many algorithms to compute a flooding topology. A simple 183 and efficient one is briefed, which comprises: 185 * Selecting a node R0 with the smallest node ID; 186 * Building a tree using R0 as root in breadth first; and then 188 * 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, where a variable MaxD with an 194 initial value 3, data structures candidate queue Cq and flooding 195 topology FT are used. Cq and FT comprise elements of form (N, D, 196 PHs), where N represents a Node, D is the Degree of node N, and PHs 197 contains the Previous Hops of node N. The detailed FT computation by 198 the algorithm is illustrated in Appendix A through an example. 200 The algorithm starts from node R0 as root with 202 * a maximum degree MaxD of value 3; 204 * an initial flooding topology FT = {(R0, D=0, PHs={ })}, where node 205 R0 is the root, D = 0 indicates that the Degree (D for short) of 206 R0 is 0 (i.e., the number of links on the flooding topology 207 connected to R0 is 0), PHs = { } indicates that the Previous Hops 208 (PHs for short) of R0 is empty; 210 * an initial candidate queue Cq = {(R1,D=0, PHs={R0}), (R2,D=0, 211 PHs={R0}), ..., (Rm,D=0, PHs={R0})}, where each of nodes R1 to Rm 212 is connected to R0, its Degree D = 0 and Previous Hops PHs ={R0}, 213 R1 to Rm are in increasing order by their IDs. 215 1. Finding and removing the first element with node A from Cq that 216 is not on FT and one PH's D in PHs < MaxD, and add the element 217 with A into FT; Set A's D to one, increase A's PH's D by one. If 218 no element in Cq satisfies the conditions, algorithm is restarted 219 with ++MaxD, the initial FT and Cq. 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 and R'D < MaxD, add link L between B and R 233 into FT and increase B's D and R's D by one. Return FT if every 234 node on FT has its D > 1; otherwise, algorithm is restarted with 235 ++MaxD, the initial FT and Cq. 237 4.2. Algorithm with Considering Others 239 There may be some constraints on some nodes in a network. For 240 example, in a spine-and-leaf network, there may be a constraint on 241 the degree of every leaf node on the flooding topology, which is that 242 the degree of every leaf node is not greater than a given number 243 ConMaxD of value 2. For each of the other nodes such as the spine 244 nodes, there is no such constraint, that is that ConMaxD is a huge 245 number for each of these nodes. 247 Step 1 of the algorithm described above is updated below to consider 248 this constraint. In addition to checking constraint PH's D < MaxD, 249 step 1 checks another constraint PH's D < PH's ConMaxD. 251 1. Finding and removing the first element with node A from Cq that 252 is not on FT and one PH's D in PHs < MaxD and PH's D < PH's 253 ConMaxD, and add the element with A into FT; Set A's D to one, 254 increase A's PH's D by one. If no element in Cq satisfies the 255 conditions, algorithm is restarted with ++MaxD, the initial FT 256 and Cq. 258 Similarly, step 4 of the algorithm described above is updated to 259 consider this constraint. In addition to checking constraint R's D < 260 MaxD, step 4 checks another constraint R's D < R's ConMaxD. 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., Przygienda, T., Psenak, P., Ginsberg, L., Chen, 295 H., Cooper, D., Jalil, L., Dontula, S., and G. S. Mishra, 296 "Dynamic Flooding on Dense Graphs", Work in Progress, 297 Internet-Draft, draft-ietf-lsr-dynamic-flooding-10, 7 298 December 2021, . 301 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 302 dual environments", RFC 1195, DOI 10.17487/RFC1195, 303 December 1990, . 305 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 306 Requirement Levels", BCP 14, RFC 2119, 307 DOI 10.17487/RFC2119, March 1997, 308 . 310 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 311 DOI 10.17487/RFC2328, April 1998, 312 . 314 8.2. Informative References 316 [I-D.ietf-rtgwg-spf-uloop-pb-statement] 317 Litkowski, S., Decraene, B., and M. Horneffer, "Impact of 318 Shortest Path First (SPF) Trigger and Delay Strategies on 319 IGP Micro-loops", Work in Progress, Internet-Draft, draft- 320 ietf-rtgwg-spf-uloop-pb-statement-10, 16 January 2019, 321 . 324 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 325 Writing an IANA Considerations Section in RFCs", BCP 26, 326 RFC 8126, DOI 10.17487/RFC8126, June 2017, 327 . 329 Appendix A. FT Computation Details through Example 331 This section presents the details on FT computation by the algorithm 332 through an example. The detailed procedure of computing a FT for a 333 network of five nodes with full mess connections is illustrated. 334 Suppose that the network has five nodes R0, R1, R2, R3 and R4; R0's 335 ID < R1's ID < R2's ID < R3's ID < R4's ID. The algorithm starts 336 with MaxD = 3, FT = {(R0, D=0, PH={})}, Cq = { (R1,0,{R0}), 337 (R2,0,{R0}), (R3,0,{R0}), (R4,0,{R0}) }. 339 1. //remove first element (R1,D=0,PHs={R0}) from Cq, R0's D=0 < MaxD 340 Cq = { (R2,0,{R0}), (R3,0,{R0}), (R4,0,{R0}) }; 341 // add (R1,1,{R0}) into FT, increase PH R0's D by one 342 FT = { (R0,1, { }), (R1,1, {R0}) }; // Link R1--R0 on FT 343 ^^^ ^^^^^^^^^^^^ 344 // for Ri connected to R1 (in Cq) not on FT, append R1 to Ri's PHs 345 Cq = { (R2,0, {R0,R1}), (R3,0, {R0,R1}), (R4,0,{R0,R1}) }. 346 ^^ ^^ ^^ 347 R0 ==== Link on FT 348 __//== O ---\__ 349 __// / \ \__ link R1--R0 added to FT 350 __// / \ \__ 351 __// / \ \__ 352 // / \ \ 353 R1 O--\_--------/---------\--------_/--O R4 354 \ \____ / \ ____/ / 355 \ \/ \/ / 356 \ /\_____ ____/\ / 357 \ / ___\__/___ \ / 358 \ / / \ \ / 359 \/____/ \___\/ 360 R2 O --------------------- O R3 362 2. // remove the first element (R2,0, {R0,R1}) from Cq, R0's D=1 < MaxD 363 Cq = { (R3,0, {R0,R1}), (R4,0,{R0,R1}) } 364 // add (R2,1,{R0}) into FT, increase R0's D by one 365 FT = { (R0,2,{ }), (R1,1,{R0}), (R2,1,{R0}) } //Link R2--R0 on FT 366 ^^^ ^^^^^^^^^^^ 367 // for Ri connected to R2 (in Cq) not on FT, append R2 to Ri's PHs 368 Cq = { (R3,0, {R0,R1,R2}), (R4,0,{R0,R1,R2}) } 369 ^^ ^^ 370 R0 ==== Link on FT 371 __//== O ---\__ 372 __// // \ \__ link R2--R0 added to FT 373 __// // \ \__ 374 __// // \ \__ 375 // // \ \ 376 R1 O--\_-------//---------\--------_/--O R4 377 \ \____ // \ ____/ / 378 \ \/ \/ / 379 \ //\_____ ____/\ / 380 \ // ___\__/___ \ / 381 \ // / \ \ / 382 \/____/ \___\/ 383 R2 O --------------------- O R3 385 3. //remove the 1st element (R3,0,{R0,R1,R2}) from Cq, R0's D=2 < MaxD 386 Cq = { (R4,0,{R0,R1,R2}) } 387 // add (R3,1,{R0}) into FT, increase R0's D by one 388 FT = { (R0,3,{}), (R1,1,{R0}), (R2,1,{R0}), (R3,1,{R0}) } 389 ^^^ ^^^^^^^^^^^ 390 // for Ri connected to R3 (in Cq) not on FT, append R3 to Ri's PHs 391 Cq = { (R4,0,{R0,R1,R2,R3}) }. 392 ^^ 393 R0 ==== Link on FT 394 __//== O ---\__ 395 __// // \\ \__ link R3--R0 added to FT 396 __// // \\ \__ 397 __// // \\ \__ 398 // // \\ \ 399 R1 O--\_-------//---------\\-------_/--O R4 400 \ \____ // \\ ____/ / 401 \ \/ \/ / 402 \ //\_____ ____/\\ / 403 \ // ___\__/___ \\ / 404 \ // / \ \\ / 405 \/____/ \___\/ 406 R2 O --------------------- O R3 408 4. //remove the 1st element (R4,0,{R0,R1,R2,R3}) from Cq,R1's D=1 < MaxD 409 Cq = { } 410 // add (R4,1,{R1}) into FT, increase R1's D by one 411 FT = {(R0,3,{}), (R1,2,{R0}), (R2,1,{R0}), (R3,1,{R0}), (R4,1,{R1})} 412 ^^^ ^^^^^^^^^^^ 413 R0 ==== Link on FT 414 __//== O ---\__ 415 __// // \\ \__ link R4--R1 added to FT 416 __// // \\ \__ 417 __// // \\ \__ 418 // // \\ \ 419 R1 O==\_=======//=========\\=======_/==O R4 420 \ \____ // \\ ____/ / 421 \ \/ \/ / 422 \ //\_____ ____/\\ / 423 \ // ___\__/___ \\ / 424 \ // / \ \\ / 425 \/____/ \___\/ 426 R2 O --------------------- O R3 428 All nodes are on FT now. In the following, for each node on FT whose 429 D = 1 (from minimum to maximum ID), link L attached to it and not on 430 FT is found such that L's remote node has minimum D and ID. L is 431 added into FT. 433 5. // On FT, get node R2 with smallest ID whose D=1 434 FT = {(R0,3,{}),(R1,2,{R0}),(R2,1,{R0}),(R3,1,{R0}), (R4,1,{R1})} 435 // Add link R2--R3 to FT, ^^^^^^^^^^^ 436 // where R2--R3 is not on FT, R3's D=1 is minimum first and then 437 // R3's ID is minimum (R3 and R4 tie for D), R2's D++ and R3's D++ 438 FT = {(R0,3,{}),(R1,2,{R0}),(R2,2,{R0,R3}),(R3,2,{R0}),(R4,1,{R1})} 439 ^^^ ^^ ^^^ 440 R0 ==== Link on FT 441 __//== O ---\__ 442 __// // \\ \__ link R2--R3 added to FT 443 __// // \\ \__ 444 __// // \\ \__ 445 // // \\ \ 446 R1 O==\_=======//=========\\=======_/==O R4 447 \ \____ // \\ ____/ / 448 \ \/ \/ / 449 \ //\_____ ____/\\ / 450 \ // ___\__/___ \\ / 451 \ // / \ \\ / 452 \/____/ \___\/ 453 R2 O ===================== O R3 455 6. // On FT, get node R4 with smallest ID whose D=1 456 FT = {(R0,3,{}),(R1,2,{R0}),(R2,2,{R0,R3}),(R3,2,{R0}),(R4,1,{R1})} 457 // Add link R4--R2 to FT, where ^^^^^^^^^^^ 458 // R4--R2 is not on FT, R2's D=2 is minimum first and then R2's ID is 459 // minimum (R2 and R3 tie for D), increase R2's D and R4's D by one 460 FT = {(R0,3,{}),(R1,2,{R0}),(R2,3,{R0,R3}),(R3,2,{R0}),(R4,2,{R1,R2})} 461 ^^^ ^^^ ^^ 462 R0 ==== Link on FT 463 __//== O ---\__ 464 __// // \\ \__ link R4--R2 added to FT 465 __// // \\ \__ 466 __// // \\ \__ 467 // // \\ \ 468 R1 O==\_=======//=========\\=======//==O R4 469 \ \____ // \\ ____// / 470 \ \/ \// / 471 \ //\_____ ___//\\ / 472 \ // ___\__//__ \\ / 473 \ // // \ \\ / 474 \/ _// \___\/ 475 R2 O ==//================= O R3 477 FT is computed, which has Degree of 3 and Diameter of 2. 479 Authors' Addresses 481 Huaimo Chen 482 Futurewei 483 Boston, 484 United States of America 486 Email: huaimo.chen@futurewei.com 488 Mehmet Toy 489 Verizon 490 United States of America 492 Email: mehmet.toy@verizon.com 494 Yi Yang 495 IBM 496 Cary, NC 497 United States of America 499 Email: yyietf@gmail.com 500 Aijun Wang 501 China Telecom 502 Beiqijia Town, Changping District 503 Beijing 504 102209 505 China 507 Email: wangaj3@chinatelecom.cn 509 Xufeng Liu 510 Volta Networks 511 McLean, VA 512 United States of America 514 Email: xufeng.liu.ietf@gmail.com 516 Yanhe Fan 517 Casa Systems 518 United States of America 520 Email: yfan@casa-systems.com 522 Lei Liu 523 Fujitsu 524 United States of America 526 Email: liulei.kddi@gmail.com