idnits 2.17.1 draft-chen-lsr-dynamic-flooding-algorithm-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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([I-D.ietf-lsr-dynamic-flooding]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (3 March 2020) is 1508 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-18) exists of draft-ietf-lsr-dynamic-flooding-04 Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force S. Chen 3 Internet-Draft T. Li 4 Intended status: Informational Arista Networks 5 Expires: 4 September 2020 3 March 2020 7 An Algorithm for Computing Dynamic Flooding Topologies 8 draft-chen-lsr-dynamic-flooding-algorithm-00 10 Abstract 12 Link-state routing protocols suffer from excessive flooding in dense 13 network topologies. Dynamic flooding [I-D.ietf-lsr-dynamic-flooding] 14 alleviates the problem by decoupling the flooding topology from the 15 physical topology. Link-state protocol updates are flooded only on 16 the sparse flooding topology while data traffic is still forwarded on 17 the physical topology. 19 This document describes an algorithm to obtain a sparse subgraph from 20 a dense graph. The resulting subgraph has certain desirable 21 properties and can be used as a flooding topology in dynamic 22 flooding. 24 This document discloses the algorithm that we have developed in order 25 to make it easier for other developers to implement similar 26 algorithms. We do not claim that our algorithm is optimal, rather it 27 is a pragmatic effort and we expect that further research and 28 refinement can improve the results. 30 We are not proposing that this algorithm be standardized, nor that 31 the working group use this as a basis for further standardization 32 work, however we have no objections if the working group chooses to 33 do so. 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 4 September 2020. 51 Copyright Notice 53 Copyright (c) 2020 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 (https://trustee.ietf.org/ 58 license-info) in effect on the date of publication of this document. 59 Please review these documents carefully, as they describe your rights 60 and restrictions with respect to this document. Code Components 61 extracted from this document must include Simplified BSD License text 62 as described in Section 4.e of the Trust Legal Provisions and are 63 provided without warranty as described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 68 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 3 69 3. Algorithm Outline . . . . . . . . . . . . . . . . . . . . . . 3 70 4. Algorithm Details . . . . . . . . . . . . . . . . . . . . . . 4 71 4.1. Initial Cycle Setup . . . . . . . . . . . . . . . . . . . 4 72 4.2. Arc Path Selection . . . . . . . . . . . . . . . . . . . 5 73 4.3. Exceptions . . . . . . . . . . . . . . . . . . . . . . . 6 74 4.4. LANs . . . . . . . . . . . . . . . . . . . . . . . . . . 7 75 5. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 76 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 77 7. Informative References . . . . . . . . . . . . . . . . . . . 9 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 80 1. Introduction 82 In [I-D.ietf-lsr-dynamic-flooding], dynamic flooding is proposed to 83 reduce the flooding of link-state protocol packets in the network. 84 The basic idea is to find a sparse flooding topology from the 85 physical topology and flood link-state protocol data units (LSPDUs or 86 LSPs) only on the flooding topology. The flooding topology should 87 have the following properties: 89 1. It should include all nodes in the area. This ensures that LSPs 90 can reach all nodes. 92 2. It should be biconnected if possible. This ensures that the LSP 93 delivery is resilient to a single node or link failure. 95 3. It has a limited diameter. Being a subgraph, the flooding 96 topology often has a larger diameter than the physical topology. 98 A larger diameter indicates a longer convergence time. The 99 tradeoff between flooding reduction and convergence should be 100 considered during the flooding topology computation. 102 4. It has a balanced degree of distribution. The degree of a node 103 on the flooding topology indicates its burden in flooding LSPs. 104 It is desirable to balance this burden across multiple nodes. 105 Hence, the degree of each node should also be considered during 106 flooding topology computation. 108 With the above properties in mind, we propose an iterative algorithm 109 to compute the flooding topology. 111 2. Problem Statement 113 We model the physical topology as an undirected graph. Each system 114 or pseudonode in the area is represented by a node in the graph. An 115 edge connects two nodes who advertise each other as neighbors. Given 116 the set of the nodes and the set of edges, we propose an algorithm to 117 compute a biconnected (if possible) subgraph that covers all nodes. 118 The subgraph is computed with consideration of diameter and node 119 degree. 121 3. Algorithm Outline 123 A simple cycle that covers all nodes is a biconnected subgraph with 124 balanced node degrees. While it has some desirable properties, a 125 simple cycle is not suitable as a flooding topology at large scale. 126 With N nodes in the area, a link-state update has to take N/2 hops to 127 reach all nodes. The undue propagation delay causes a long 128 convergence time. 130 The proposed algorithm constructs a subgraph composed of small 131 overlapping cycles. The base graph is denoted by G(V, E), where V is 132 the set of all reachable nodes in this area, and E is the set of 133 edges. The subgraph to be computed is denoted by G'({}, {}), which 134 starts with an empty set of nodes and an empty set of edges. 136 1. Select a subset of nodes V(0) from V and a subset of edges E(0) 137 from E to form an initial cycle. This cycle is added to the 138 subgraph: G'(V(0), E(0)). 140 2. Select a subset of nodes V(i) and a subset of edges E(i), that 141 are not included in the current subgraph. That is, V(i) is 142 selected from V - V(0) - ... - V(i-1) and E(i) is selected from E 143 - E(0) - ... - E(i-1). These nodes and the edges are selected to 144 form an arc path whose two endpoints are included in the current 145 subgraph. This arc path is added to the subgraph: G'( V(0) + 146 V(1) + ... + V(i), E(0) + E(1) + ... + E(i) ). 148 3. Repeat step 2 until all nodes are included in the subgraph G'. 150 The subgraph constructed by this algorithm has the following 151 properties: 153 1. It covers all nodes in the area. 155 2. It is biconnected. This can be easily proven by induction. 156 Specifically, the initial cycle is biconnected. Adding an arc 157 path, whose two endpoints differ, to a biconnected subgraph 158 maintains the biconnectivity of the subgraph. 160 3. It has a limited diameter. By selecting small cycles, the 161 subgraph will have a smaller diameter. More specifically, the 162 implementation can pick endpoints of each arc path to reduce the 163 diameter of the subgraph. The degree of a node in the subgraph 164 is determined by the number of arc paths it is on. By carefully 165 selecting the arc endpoints, we may balance the node degrees. 167 Together with the encoding scheme in [I-D.ietf-lsr-dynamic-flooding], 168 this algorithm can be used to implement centralized dynamic flooding. 169 The area leader can build the base graph from its link-state database 170 (LSDB), apply this algorithm to compute the flooding topology, and 171 then encode it into the Dynamic Flooding Path TLVs specified in 172 [I-D.ietf-lsr-dynamic-flooding]. In a topology change event, the 173 area leader can repeat the above process and send out the new 174 flooding topology. 176 4. Algorithm Details 178 The outlined algorithm allows for different approaches to find the 179 initial cycle and subsequent arc paths. We do not intend to find the 180 theoretically optimal solution. Our aim is to find a practical 181 approach that works for any connected base graph, and is also easy to 182 implement. 184 4.1. Initial Cycle Setup 186 The initial cycle forms a base of the subgraph computation. 187 Intuitively, we would like to place the initial cycle around the 188 centroid of the base graph, and gradually expand it outwards. 189 Complicated graph analysis can help, but is not desired. 191 We propose to select a starting node and then search a path that ends 192 at this node. We suggest selecting the node with the highest degree 193 as the starting node. The degree of each node can be easily 194 determined when the base graph is constructed from the LSDB. 195 Starting from this node, we perform a depth-first search (DFS) for a 196 limited number of steps, and then a breadth-first search (BFS) to 197 find the shortest path back to the starting node. The restriction of 198 the DFS depths and the use of BFS effectively help limit the diameter 199 of the initial cycle. Below is a summary of the procedure. We omit 200 the details of the well-known DFS and BFS algorithms. 202 1. Let V(0) = [] be the list of nodes on the initial cycle. 204 2. Find the starting node, denoted by n0. V(0) = [n0]. 206 3. Perform DFS starting from n0 until either the first leaf is 207 reached or the depth exceeds a preset limit. The visited nodes 208 are denoted by n1, n2, ..., ni, where i < DFS depth limit, and 209 added to the list V(0) in order. 211 4. Mark nodes in V(0) as visited to avoid BFS visiting these nodes. 212 Then perform BFS to find the shortest path from ni to n0. Append 213 nodes on the shortest path to V(0). Since this is a cycle, node 214 n0 appears twice in V(0): the first and the last places. 216 Note that since DFS and BFS do not process a node more than once, we 217 are ensured to obtain a cycle (if one exists) from the above 218 procedure. 220 4.2. Arc Path Selection 222 After obtaining an initial cycle, we recursively add arc paths to the 223 subgraph until all nodes are included. Each arc path's two endpoints 224 are chosen from the current subgraph. This ensures that the 225 resulting subgraph remains biconnected. To limit the diameter of the 226 resulting subgraph, we select an arc path with limited length and 227 attach it closer to the initial cycle. 229 In each iteration, we have a starting subgraph, which includes the 230 initial cycle and the arc paths obtained in earlier iterations. We 231 first select a node from the starting subgraph, that has at least one 232 neighbor that is not in the starting subgraph. To balance the degree 233 distribution, we prefer to select a node that has the least degree in 234 the starting subgraph. Meanwhile, we intend to place the new arc 235 path closer to the initial cycle, which will help reduce the diameter 236 of the resulting subgraph. As the number of iterations increases, it 237 becomes hard to find such nodes that meet both conditions. A 238 tradeoff between the node degree and the node distance to the initial 239 cycle has to be made. 241 Starting from the selected node, we perform a DFS for a limited 242 number of steps in the base graph to include nodes and edges that do 243 not belong to the starting subgraph. Then BFS is performed to find 244 the shortest path back to any node in the starting subgraph except 245 the starting node of this iteration. The resulting path is combined 246 with the starting subgraph to generate a new subgraph, which serves 247 as the starting subgraph in the next iteration. The iteration is 248 repeated until all nodes in the base graph are included in the 249 subgraph. 251 The procedure in each iteration is very similar to the one used to 252 find the initial cycle, except that the two endpoints of the new path 253 do not match: 255 1. Let V(i) = [] be the list of nodes found in the i-th iteration. 256 The starting subgraph includes nodes in V(0) + ... + V(i-1), and 257 edges between each pair of adjacent nodes in each node list V(j). 259 2. Select a starting node n0 for this iteration from the starting 260 subgraph. V(i) = [n0]. 262 3. Mark all nodes in V(0) + ... + V(i-1) as visited. Then perform 263 DFS from n0 until either the first leaf is reached or the depth 264 exceeds a preset limit. Nodes visited in this iteration are 265 denoted by n1, n2, ..., ni in order, and appended to the list 266 V(i). 268 4. Mark all nodes in V(0) + ... + V(i-1) + V(i) as visited. Then 269 perform BFS to find the shortest path from ni to any node in V(0) 270 + ... V(i-1) - [n0], where n0 is the starting node in this 271 iteration. If a path is found, append its nodes to V(i) and 272 repeat the iteration from step 1. 274 By correctly marking the visited nodes before DFS and BFS, we ensure 275 that the obtained arc path (if it exists) has two endpoints and only 276 these two points on the starting subgraph. 278 4.3. Exceptions 280 If the base graph is biconnected, there exists a simple cycle between 281 any two nodes. We are thus ensured to find one arc path in each 282 iteration and the algorithm described above will yield a biconnected 283 subgraph that covers all nodes in the base graph. Otherwise, 284 however, we may not be able to find an arc path with both endpoints 285 belonging to the starting subgraph in that iteration. When this 286 happens, we know that the edge between the last node found by DFS and 287 its parent is a cut edge in the base graph. For connectivity, this 288 edge must be included in the resulting subgraph. Hence, when step 4 289 (the BFS stage in earlier procedures) fails, we should amend it with 290 the following: 292 5. If BFS does not find a shortest path from ni, and V(i) contains 293 only two nodes, i.e., the cut edge case, then go back to step 1 294 to continue the iteration. 296 6. If BFS does not find a shortest path from ni, and V(i) contains 297 more than two nodes, then remove the last node from V(i), and go 298 back to step 4. 300 Similarly, we might face the same problem when selecting the initial 301 cycle. We can apply step 6 until we find a cycle. However, if we 302 happen to find a cut edge, we can change the first neighbor of the 303 starting node that is visited by the DFS and repeat the procedure. 304 If all edges connecting to the starting node are cut edges, we can 305 change the starting node. If an initial cycle is not found after all 306 the above efforts, indicating that the base graph does not have a 307 cycle, then we will return the base graph as the result. 309 4.4. LANs 311 We model a pseudonode as a node in the base graph. The proposed 312 algorithm can be applied as-is. There are, however, possible 313 optimizations for the multi-access LAN case. First, a pseudonode is 314 not required to be on the flooding topology. The algorithm can thus 315 be terminated as soon as all real nodes are included in the subgraph. 316 Second, if a pseudonode is included on the flooding topology, all 317 nodes connecting to this LAN will have to flood their LSPs to this 318 LAN (see [I-D.ietf-lsr-dynamic-flooding] Section 6.6). Hence, if a 319 pseudonode is included in the subgraph, then it will automatically 320 provide uni-connectivity to all its neighbors that are not yet 321 included. The algorithm can take advantage of this LAN property to 322 reduce the edges in the subgraph. 324 5. Example 326 The proposed algorithm can be applied to any connected base graph. 327 For ease of explanation, we consider a complete graph of 10 nodes and 328 45 edges. To limit the diameter of the resulting subgraph, we pre- 329 set the maximum steps in the DFS to 3. 331 1. Let ni, i = 0, 1, ... 9, denote nodes in the base graph. 333 2. Find an initial cycle. 335 a. Without loss of generality, we select node n0 as the starting 336 point. 338 b. Perform DFS from n0 for 3 steps. We obtain a path n0 - n1 - 339 n2 - n3. 341 c. Perform BFS from n3 to n0. Since this is a complete graph, 342 where every node is directly connected to any other node, the 343 shortest path is only one hop away. 345 d. The initial cycle is found n0 - n1 - n2 - n3 - n0. 347 3. Find the first arc path. 349 a. Select a node on the initial cycle, say n0. 351 b. Perform DFS from n0 for 3 steps. We obtain a path n0 - n4 - 352 n5 - n6. 354 c. Perform BFS from n6 to any node on the initial cycle except 355 n0, i.e., {n1, n2, n3}. These three nodes have the same 356 degree. We may select any one of them as the endpoint. 357 Suppose that n1 is selected. 359 d. The first arc path is found n0 - n4 - n5 - n6 - n1. 361 4. Find the second arc path. 363 a. When selecting the starting node for this path, we may 364 consider the current node degree as well as the node distance 365 to n0 (the starting point of the initial cycle). We notice 366 that both n0 and n1 have a degree of 3 while other nodes have 367 a degree of 2. Nodes n1, n3, n4 are the closest to n0. We 368 select a node with a lower degree and closer to n0. Suppose 369 n3 is selected. 371 b. Perform DFS from n3 for 3 steps. We obtain a path n3 - n7 372 -n8 - n9. 374 c. Perform BFS from n9 to any node except n3. Using the same 375 criteria in a. to select the endpoint, we select n4. 377 d. The second arc path is found n3 - n7 -n8 - n9 - n4. 379 5. The subgraph has included all nodes. The iteration ends. 381 The subgraph found by the proposed algorithm can be represented by 382 three paths: 384 n0 - n1 - n2 - n3 - n0 385 n0 - n4 - n5 - n6 - n1 387 n3 - n7 -n8 - n9 - n4 389 The subgraph has 12 edges, significantly reduced from 45 in the base 390 graph. The highest node degree is 3 and the lowest node degree is 2. 391 The diameter of the subgraph is 4, increased, as expected, from that 392 of the base graph. 394 6. Security Considerations 396 This document introduces no new security issues. Security issues 397 within dynamic flooding are already discussed in 398 [I-D.ietf-lsr-dynamic-flooding]. 400 7. Informative References 402 [I-D.ietf-lsr-dynamic-flooding] 403 Li, T., Psenak, P., Ginsberg, L., Chen, H., Przygienda, 404 T., Cooper, D., Jalil, L., and S. Dontula, "Dynamic 405 Flooding on Dense Graphs", Work in Progress, Internet- 406 Draft, draft-ietf-lsr-dynamic-flooding-04, 26 November 407 2019, . 410 Authors' Addresses 412 Sarah Chen 413 Arista Networks 414 5453 Great America Parkway 415 Santa Clara, California 95054 416 United States of America 418 Email: sarahchen@arista.com 420 Tony Li 421 Arista Networks 422 5453 Great America Parkway 423 Santa Clara, California 95054 424 United States of America 426 Email: tony.li@tony.li