idnits 2.17.1 draft-cc-lsr-flooding-reduction-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 214 has weird spacing: '... then mark ...' == Line 262 has weird spacing: '... then mark ...' -- The document date (July 7, 2019) is 1755 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 303, but no explicit reference was found in the text == Unused Reference: 'RFC2328' is defined on line 312, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-spf-uloop-pb-statement' is defined on line 318, 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 (-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: 1 error (**), 0 flaws (~~), 8 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: January 8, 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 July 7, 2019 20 Flooding Topology Computation Algorithm 21 draft-cc-lsr-flooding-reduction-04 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 January 8, 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 . . . . . . . . . . . . . . . . . . . . . . 7 84 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 85 8.1. Normative References . . . . . . . . . . . . . . . . . . 7 86 8.2. Informative References . . . . . . . . . . . . . . . . . 7 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 89 1. Introduction 91 For some networks such as dense Data Center (DC) networks, the 92 existing Link State (LS) flooding mechanism is not efficient and may 93 have some issues. The extra LS flooding consumes network bandwidth. 94 Processing the extra LS flooding, including receiving, buffering and 95 decoding the extra LSs, wastes memory space and processor time. This 96 may cause scalability issues and affect the network convergence 97 negatively. 99 This document proposes an algorithm for a node to compute a flooding 100 topology, which is a subgraph of the complete topology per underline 101 physical network. When every node in an area automatically 102 calculates a flooding topology by using a same algorithm and floods 103 the link states using the flooding topology, the amount of flooding 104 traffic in the network is greatly reduced. This would reduce 105 convergence time with a more stable and optimized routing 106 environment. 108 There may be multiple algorithms for computing a flooding topology. 109 Users can select one they prefer, and smoothly switch from one to 110 another. 112 2. Terminology 114 LSA: A Link State Advertisement in OSPF. 116 LSP: A Link State Protocol Data Unit (PDU) in IS-IS. 118 LS: A Link Sate, which is an LSA or LSP. 120 FT: Flooding Topology. 122 FTC: Flooding Topology Computation. 124 3. Flooding Topology 126 For a given network topology, a flooding topology is a sub-graph or 127 sub-network of the given network topology that has the same 128 reachability to every node as the given network topology. Thus all 129 the nodes in the given network topology MUST be in the flooding 130 topology. All the nodes MUST be inter-connected directly or 131 indirectly. As a result, LS flooding will in most cases occur only 132 on the flooding topology, that includes all nodes but a subset of 133 links. Note even though the flooding topology is a sub-graph of the 134 original topology, any single LS MUST still be disseminated in the 135 entire network. 137 3.1. Flooding Topology Construction 139 Many different flooding topologies can be constructed for a given 140 network topology. For example, a chain connecting all the nodes in 141 the given network topology is a flooding topology. A circle 142 connecting all the nodes is another flooding topology. A tree 143 connecting all the nodes is a flooding topology. In addition, the 144 tree plus the connections between some leaves of the tree and branch 145 nodes of the tree is a flooding topology. 147 The following parameters need to be considered for constructing a 148 flooding topology: 150 o Degree: The degree of the flooding topology is the maximum degree 151 among the degrees of the nodes on the flooding topology. The 152 degree of a node on the flooding topology is the number of 153 connections on the flooding topology it has to other nodes. 155 o Number of links: The number of links on the flooding topology is a 156 key factor for reducing the amount of LS flooding. In general, 157 the smaller the number of links, the less the amount of LS 158 flooding. 160 o Diameter: The diameter of the flooding topology is the shortest 161 distance between the two most distant nodes on the flooding 162 topology. It is a key factor for reducing the network convergence 163 time. The smaller the diameter, the less the convergence time. 165 o Redundancy: The redundancy of the flooding topology means a 166 tolerance to the failures of some links and nodes on the flooding 167 topology. If the flooding topology is split by some failures, it 168 is not tolerant to these failures. In general, the larger the 169 number of links on the flooding topology is, the more tolerant the 170 flooding topology to failures. 172 Note that the flooding topology constructed by a node is dynamic in 173 nature, that means when the base topology (the entire topology graph) 174 changes, the flooding topology (the sub-graph) MUST be re-computed/ 175 re-constructed to ensure that any node that is reachable on the base 176 topology MUST also be reachable on the flooding topology. 178 4. Algorithms to Compute Flooding Topology 180 There are many algorithms to compute a flooding topology. A simple 181 and efficient one is briefed below. 183 o Select a node R0 according to a rule such as the node with the 184 smallest node ID; 186 o Build a tree using R0 as root of the tree; and then 188 o Connect each node whose degree is one to the tree to have a 189 flooding topology. 191 4.1. Algorithm with Considering Degree 193 The algorithm starts from node R0 as root with a given maximum degree 194 MaxD, a candidate queue Cq = {(R0, D = 0, PHs = { })}, and an empty 195 flooding topology FT = { }. Cq contains one element (R0, D = 0, PHs 196 = { }), where node R0 is the root, D = 0 indicates that the Degree (D 197 for short) of R0 is 0 (i.e., the number of links on the flooding 198 topology connected to R0 is 0), PHs = { } indicates that the Previous 199 Hops (PHs for short) of R0 is empty. 201 1. Finding and removing the first element with node A in Cq that is 202 not on FT and one PH's D in PHs < MaxD. 204 If there is no element with a node in Cq whose PHs != { } and one 205 PH in PHs whose D < MaxD, 207 then MaxD++ and restarts algorithm from R0, MaxD, Cq = 208 {(R0,D=0,PHs = { })}, FT = { }; 210 otherwise (i.e., A with one PH's D in PHs < MaxD or PHs = { }), 212 if PHs = { } (i.e., A is the root), 214 then mark A on FT and add A with D=0 and PHs={ } into FT; 216 otherwise (i.e., A is not the root. Assume that PH is the 217 first one in PHs whose D < MaxD), PH's D++, mark A on FT and 218 add A with D=1 and PHs={PH} to FT. 220 2. If all the nodes are on the FT, then goto step 4; 222 3. Suppose that node Xi (i = 1, 2,..., n) is connected to node A and 223 not on FT, and X1, X2,..., Xn are in an increasing order by their 224 IDs (i.e., X1's ID < X2's ID < ... < Xn's ID). If Xi is not in 225 Cq, then add it into the end of Cq with D = 0 and PHs = {A}; 226 otherwise (i.e., Xi is in Cq), add A into Xi's PHs and elements 227 in PHs are in an increasing order by their degrees first and then 228 IDs; Goto step 1. 230 4. For each node B in FT whose D is one, find a link L attached to B 231 such that L's remote node R whose D and ID are minimum; increase 232 B's D and R's D by one. Return FT. 234 4.2. Algorithm with Considering Others 236 There may be some contraints on some nodes in a network. For 237 example, in a spine-and-leaf network, there may be a constraint on 238 the degree of every leaf node on the flooding topology, which is that 239 the degree of every leaf node is not greater than a given number 240 ConMaxD such as ConMaxD = 2. For each of the other nodes such as the 241 spine nodes, there is no such constraint, that is that ConMaxD is a 242 huge number for each of these nodes. 244 Step 1 of the algorithm described above is updated below to consider 245 this constraint. In addition to checking constraint PH's D < MaxD, 246 step 1 checks another constraint PH's D < PH's ConMaxD. 248 1. Finding and removing the first element with node A in Cq that is 249 not on FT and one PH's D in PHs < MaxD and PH's D < PH's ConMaxD. 251 If there is no element with a node in Cq whose PHs != { } and one 252 PH in PHs whose D < MaxD and PH's D < PH's ConMaxD, 254 then MaxD++ and restarts algorithm from R0, MaxD, Cq = 255 {(R0,D=0,PHs = { })}, FT = { }; 257 otherwise (i.e., node A with one PH's D in PHs < MaxD and PH's D 258 < PH's ConMaxD or PHS = { }), 260 if PHs = { } (i.e., A is the root), 262 then mark A on FT and add A with D=0 and PHs={ } into FT; 264 otherwise (i.e., A is not the root. Assume that PH is the 265 first one in PHs whose D < MaxD and PH's D < PH's ConMaxD), 266 PH's D++, mark A on FT and add A with D=1 and PHs={PH} to FT. 268 5. Security Considerations 270 This document does not introduce any new security issue. 272 6. IANA Considerations 274 Under Registry Name: "IGP Algorithm Type For Computing Flooding 275 Topology" under an existing "Interior Gateway Protocol (IGP) 276 Parameters" IANA registries (refer to Section 7.3. IGP 277 [I-D.ietf-lsr-dynamic-flooding]), IANA is requested to assign one 278 value of IGP Algorithm Type For Computing Flooding Topology as 279 follows: 281 +==========+========================================+=============+ 282 |Type Value| Type Name | reference | 283 +==========+========================================+=============+ 284 | 1 | Breadth First Minimum Degree Algorithm |This document| 285 +----------+----------------------------------------+-------------+ 287 7. Acknowledgements 289 The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, 290 Stephane Litkowski and Alvaro Retana for their valuable suggestions 291 and comments on this draft. 293 8. References 295 8.1. Normative References 297 [I-D.ietf-lsr-dynamic-flooding] 298 Li, T., Psenak, P., Ginsberg, L., Chen, H., Przygienda, 299 T., Cooper, D., Jalil, L., and S. Dontula, "Dynamic 300 Flooding on Dense Graphs", draft-ietf-lsr-dynamic- 301 flooding-03 (work in progress), June 2019. 303 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 304 dual environments", RFC 1195, DOI 10.17487/RFC1195, 305 December 1990, . 307 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 308 Requirement Levels", BCP 14, RFC 2119, 309 DOI 10.17487/RFC2119, March 1997, 310 . 312 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 313 DOI 10.17487/RFC2328, April 1998, 314 . 316 8.2. Informative References 318 [I-D.ietf-rtgwg-spf-uloop-pb-statement] 319 Litkowski, S., Decraene, B., and M. Horneffer, "Link State 320 protocols SPF trigger and delay algorithm impact on IGP 321 micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-10 322 (work in progress), January 2019. 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 Authors' Addresses 330 Huaimo Chen 331 Futurewei 332 Boston 333 USA 335 Email: huaimo.chen@futurewei.com 337 Dean Cheng 338 Individual 339 Santa Clara 340 USA 342 Email: deanccheng@gmail.com 344 Mehmet Toy 345 Verizon 346 USA 348 Email: mehmet.toy@verizon.com 350 Yi Yang 351 IBM 352 Cary, NC 353 United States of America 355 Email: yyietf@gmail.com 357 Aijun Wang 358 China Telecom 359 Beiqijia Town, Changping District 360 Beijing 102209 361 China 363 Email: wangaj.bri@chinatelecom.cn 365 Xufeng Liu 366 Volta Networks 367 McLean, VA 368 USA 370 Email: xufeng.liu.ietf@gmail.com 371 Yanhe Fan 372 Casa Systems 373 USA 375 Email: yfan@casa-systems.com 377 Lei Liu 378 Fujitsu 379 USA 381 Email: liulei.kddi@gmail.com