idnits 2.17.1 draft-cc-lsr-flooding-reduction-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 7, 2019) is 1935 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: 'RFC5340' is defined on line 1376, but no explicit reference was found in the text == Unused Reference: 'I-D.li-dynamic-flooding' is defined on line 1392, but no explicit reference was found in the text == Unused Reference: 'I-D.shen-isis-spine-leaf-ext' is defined on line 1397, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Chen 3 Internet-Draft D. Cheng 4 Intended status: Standards Track Huawei Technologies 5 Expires: July 11, 2019 M. Toy 6 Verizon 7 Y. Yang 8 IBM 9 A. Wang 10 China Telecom 11 X. Liu 12 Volta Networks 13 Y. Fan 14 Casa Systems 15 L. Liu 16 January 7, 2019 18 LS Flooding Reduction 19 draft-cc-lsr-flooding-reduction-01 21 Abstract 23 This document proposes an approach to flood link states on a topology 24 that is a subgraph of the complete topology per underline physical 25 network, so that the amount of flooding traffic in the network is 26 greatly reduced, and it would reduce convergence time with a more 27 stable and optimized routing environment. The approach can be 28 applied to any network topology in a single area. 30 Requirements Language 32 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 33 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 34 document are to be interpreted as described in RFC 2119 [RFC2119]. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at https://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on July 11, 2019. 53 Copyright Notice 55 Copyright (c) 2019 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (https://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 72 3. Conventions Used in This Document . . . . . . . . . . . . . . 4 73 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 74 5. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 5 75 5.1. Construct Flooding Topology . . . . . . . . . . . . . . . 6 76 5.2. Protect Flooding Topology Split . . . . . . . . . . . . . 7 77 6. Extensions to OSPF . . . . . . . . . . . . . . . . . . . . . 8 78 6.1. Extensions for Operations . . . . . . . . . . . . . . . . 8 79 6.2. Extensions for Centralized Mode . . . . . . . . . . . . . 9 80 6.2.1. Message for Flooding Topology . . . . . . . . . . . . 9 81 6.2.2. Leaders Selection . . . . . . . . . . . . . . . . . . 17 82 7. Extensions to IS-IS . . . . . . . . . . . . . . . . . . . . . 18 83 7.1. Extensions for Operations . . . . . . . . . . . . . . . . 18 84 7.2. Extensions for Centralized Mode . . . . . . . . . . . . . 19 85 7.2.1. TLV for Flooding Topology . . . . . . . . . . . . . . 19 86 7.2.2. Leaders Selection . . . . . . . . . . . . . . . . . . 20 87 8. Flooding Behavior . . . . . . . . . . . . . . . . . . . . . . 20 88 8.1. Nodes Perform Flooding Reduction without Failure . . . . 21 89 8.1.1. Receiving an LS . . . . . . . . . . . . . . . . . . . 21 90 8.1.2. Originating an LS . . . . . . . . . . . . . . . . . . 21 91 8.1.3. Establishing Adjacencies . . . . . . . . . . . . . . 21 92 8.2. An Exception Case . . . . . . . . . . . . . . . . . . . . 22 93 8.2.1. Multiple Failures . . . . . . . . . . . . . . . . . . 22 94 8.2.2. Changes on Flooding Topology . . . . . . . . . . . . 23 95 9. Operations on Flooding Reduction . . . . . . . . . . . . . . 23 96 9.1. Configuring Flooding Reduction . . . . . . . . . . . . . 24 97 9.1.1. Configurations for Centralized Flooding Reduction . . 24 98 9.1.2. Configurations for Distributed Flooding Reduction . . 24 99 9.2. Migration to Flooding Reduction . . . . . . . . . . . . . 24 100 9.2.1. Migration to Centralized Flooding Reduction . . . . . 24 101 9.2.2. Migration to Distributed Flooding Reduction . . . . . 25 102 9.3. Roll Back to Normal Flooding . . . . . . . . . . . . . . 25 103 9.4. Transfer from Distributed to Centralized Mode . . . . . . 26 104 9.5. Transfer from Centralized to Distributed Mode . . . . . . 27 105 9.6. Adding a New Node to Network . . . . . . . . . . . . . . 27 106 10. Manageability Considerations . . . . . . . . . . . . . . . . 28 107 11. Security Considerations . . . . . . . . . . . . . . . . . . . 28 108 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 109 12.1. OSPFv2 . . . . . . . . . . . . . . . . . . . . . . . . . 28 110 12.2. OSPFv3 . . . . . . . . . . . . . . . . . . . . . . . . . 29 111 12.3. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . 30 112 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30 113 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 114 14.1. Normative References . . . . . . . . . . . . . . . . . . 30 115 14.2. Informative References . . . . . . . . . . . . . . . . . 31 116 Appendix A. Algorithms to Build Flooding Topology . . . . . . . 32 117 A.1. Algorithms to Build Tree without Considering Others . . . 32 118 A.2. Algorithms to Build Tree Considering Others . . . . . . . 33 119 A.3. Connecting Leaves . . . . . . . . . . . . . . . . . . . . 35 120 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 36 122 1. Introduction 124 For some networks such as dense Data Center (DC) networks, the 125 existing Link State (LS) flooding mechanism is not efficient and may 126 have some issues. The extra LS flooding consumes network bandwidth. 127 Processing the extra LS flooding, including receiving, buffering and 128 decoding the extra LSs, wastes memory space and processor time. This 129 may cause scalability issues and affect the network convergence 130 negatively. 132 This document proposes an approach to minimize the amount of flooding 133 traffic in the network. Thus the workload for processing the extra 134 LS flooding is decreased significantly. This would improve the 135 scalability, speed up the network convergence, stable and optimize 136 the routing environment. 138 This approach is also flexible. It has multiple modes for 139 computation of flooding topology. Users can select a mode they 140 prefer, and smoothly switch from one mode to another. The approach 141 is applicable to any network topology in a single area. It is 142 backward compatible. 144 2. Terminology 146 Flooding Topology: 147 A sub-graph or sub-network of a given (physical) network topology 148 that has the same reachability to every node as the given network 149 topology, through which link states are flooded. 151 Critical link or interface on a flooding topology: 152 A only link or interface among some nodes on the flooding 153 topology. When this link or interface goes down, the flooding 154 topology will be split. 156 Critical node on a flooding topology: 157 A only node connecting some nodes on the flooding topology. When 158 this node goes down, the flooding topology will be split. 160 Backup path: 161 A path or a sequence of links, providing an alternative 162 connection between the two end nodes of a link on the flooding 163 topology or between the two end nodes of a path crossing a node 164 on the flooding topology. when a critical link goes down, the 165 backup path for the link provides a connection to connect two 166 parts of a split flooding topology. When a critical node goes 167 down, the backup paths for the paths crossing the node connect 168 all the split parts of the floooding topology into one. 170 Remaining Flooding Topology: 171 A topology from a flooding topology by removing the failed links 172 and nodes from the flooding topology. 174 LSA: 175 A Link State Advertisement in OSPF. 177 LSP: 178 A Link State Protocol Data Unit (PDU) in IS-IS. 180 LS: 181 A Link Sate, which is an LSA or LSP. 183 3. Conventions Used in This Document 185 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 186 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 187 document are to be interpreted as described in [RFC2119]. 189 4. Problem Statement 191 OSPF and IS-IS deploy a so-called reliable flooding mechanism, where 192 a node must transmit a received or self-originated LS to all its 193 interfaces (except for the interface where an LS is received). While 194 this mechanism assures each LS being distributed to every node in an 195 area or domain, the side-effect is that the mechanism often causes 196 redundant LS, which in turn forces nodes to process identical LS more 197 than once. This results in the waste of link bandwidth and nodes' 198 computing resources, and the delay of topology convergence. 200 This becomes more serious in networks with large number of nodes and 201 links, and in particular, higher degree of interconnection (e.g., 202 meshed topology, spine-leaf topology, etc.). In some environments 203 such as in data centers, the drawback of the existing flooding 204 mechanism has already caused operational issues, including waves of 205 flooding storms, choke of computing resources, slow convergence, 206 oscillating topology changes, and instability of routing environment. 208 One example is as shown in Figure 1, where Node 1, Node 2 and Node 3 209 are interconnected in a mesh. When Node 1 receives a new or updated 210 LS on its interface I11, it by default would forward the LS to its 211 interface Il2 and I13 towards Node 2 and Node 3, respectively, after 212 processing. Node 2 and Node 3 upon reception of the LS and after 213 processing, would potentially flood the same LS over their respective 214 interface I23 and I32 toward each other, which is obviously not 215 necessary and at the cost of link bandwidth as well as both nodes' 216 computing resource. 218 | 219 |I11 220 +--o---+ 221 |Node 1| 222 +-o--o-+ 223 I12 / \ I13 224 / \ 225 I21/ \I31 226 +----o-+ I32+-o----+ 227 |Node 2|------|Node 3| 228 +------+I23 +------+ 230 Figure 1 232 5. Flooding Topology 234 For a given network topology, a flooding topology is a sub-graph or 235 sub-network of the given network topology that has the same 236 reachability to every node as the given network topology. Thus all 237 the nodes in the given network topology MUST be in the flooding 238 topology. All the nodes MUST be inter-connected directly or 239 indirectly. As a result, LS flooding will in most cases occur only 240 on the flooding topology, that includes all nodes but a subset of 241 links. Note even though the flooding topology is a sub-graph of the 242 original topology, any single LS MUST still be disseminated in the 243 entire network. 245 5.1. Construct Flooding Topology 247 Many different flooding topologies can be constructed for a given 248 network topology. A chain connecting all the nodes in the given 249 network topology is a flooding topology. A circle connecting all the 250 nodes is another flooding topology. A tree connecting all the nodes 251 is a flooding topology. In addition, the tree plus the connections 252 between some leaves of the tree and branch nodes of the tree is a 253 flooding topology. 255 The following parameters need to be considered for constructing a 256 flooding topology: 258 o Number of links: The number of links on the flooding topology is a 259 key factor for reducing the amount of LS flooding. In general, 260 the smaller the number of links, the less the amount of LS 261 flooding. 263 o Diameter: The shortest distance between the two most distant nodes 264 on the flooding topology (i.e., the diameter of the flooding 265 topology) is a key factor for reducing the network convergence 266 time. The smaller the diameter, the less the convergence time. 268 o Redundancy: The redundancy of the flooding topology means a 269 tolerance to the failures of some links and nodes on the flooding 270 topology. If the flooding topology is split by some failures, it 271 is not tolerant to these failures. In general, the larger the 272 number of links on the flooding topology is, the more tolerant the 273 flooding topology to failures. 275 There are many different ways to construct a flooding topology for a 276 given network topology. A few of them are listed below: 278 o Centralized Mode: One node in the network builds a flooding 279 topology and floods the flooding topology to all the other nodes 280 in the network (Note: Flooding the flooding topology may increase 281 the flooding. The amount of traffic for flooding the flooding 282 topology should be minimized.); 284 o Distributed Mode: Each node in the network automatically 285 calculates a flooding topology by using the same algorithm (No 286 flooding for flooding topology); 288 o Static Mode: Links on the flooding topology are configured 289 statically. 291 Note that the flooding topology constructed by a node is dynamic in 292 nature, that means when the base topology (the entire topology graph) 293 changes, the flooding topology (the sub-graph) MUST be re-computed/ 294 re-constructed to ensure that any node that is reachable on the base 295 topology MUST also be reachable on the flooding topology. 297 For reference purpose, some algorithms that allow nodes to 298 automatically compute flooding topology are elaborated in Appendix A. 299 However, this document does not attempt to standardize how a flooding 300 topology is established. 302 5.2. Protect Flooding Topology Split 304 It is hard to construct a flooding topology that reduces the amount 305 of LS flooding greatly and is tolerant to multiple failures. Without 306 any protection against a flooding topology split when multiple 307 failures on the flooding topology happen, we may have a slow 308 convergence. For example, in centralized mode, it takes some time 309 for the leader to detect the failures through receiving the link 310 states, compute a new flooding topology and flood the new flooding 311 topology. In addition, it takes some time for each of the other 312 nodes to receive the new flooding topology (piece by piece), decode 313 it and build it locally. It is better to have some simple and fast 314 methods for protecting the flooding topology split. Thus the 315 convergence is not slowed down. 317 In one way, when two or more failures on the current flooding 318 topology occur almost in the same time, each of the nodes within a 319 given distance (such as 3 hops) to a failure point, floods the link 320 state (LS) that it receives to all the links (except for the one from 321 which the LS is received) until a new flooding topology is built. 323 In another way, each node computes and maintains a small number of 324 backup paths. For a backup path for a link L on the flooding 325 topology, a node N computes and maintains it only if the backup path 326 goes through node N. Node N stores the links (e.g., local link L1 327 and L2) attached to it and on the backup path. When link L fails and 328 there are one or more other failures on the flooding topology, node N 329 adds the links (e.g., L1 and L2) to the flooding topology temporarily 330 until a new flooding topology is built. Suppose that the two end 331 nodes of link L is A and B, and A's ID is smaller than B's. Node N 332 computes a path from A to B with minimum hops and whose links are not 333 on the flooding topology. This path is a backup path for link L. 335 6. Extensions to OSPF 337 The extensions to OSPF comprises two parts: one part is for 338 operations on flooding reduction, the other is specially for 339 centralized flooding reduction (or say flooding reduction in 340 centralized mode). 342 6.1. Extensions for Operations 344 A new TLV is defined in OSPF RI LSA [RFC7770]. It contains 345 instructions about flooding reduction, and is called Flooding 346 Reduction Instruction TLV or Instruction TLV for short. This TLV is 347 originated from only one node and has the format below. 349 0 1 2 3 350 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 352 | INST-TLV-Type (TBD1) | TLV-Length | 353 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 354 | OP | MOD | Algorithm | Reserved (MUST be zero) | NL | 355 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 356 ~ sub TLVs (optional) ~ 357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 359 Flooding Reduction Instruction TLV 361 A OP field of three bits is defined in the TLV. It may have a value 362 of the followings. 364 o 0x001 (R): Perform flooding Reduction, which instructs the nodes 365 in an area to perform flooding reduction. 367 o 0x010 (N): Roll back to Normal flooding, which instructs the nodes 368 in an area to roll back to perform normal flooding. 370 When any of the other values is received, it is ignored. 372 A MOD field of three bits is defined in the TLV and may have a value 373 of the followings. 375 o 0x001 (C): Centralized Mode, which instructs: 1) the nodes in an 376 area to select leaders (primary/designated leader, secondary/ 377 backup leader, and so on); 2) the primary leader to compute a 378 flooding topology and flood it to all the other nodes in the area; 379 3) every node in the area to receive and use the flooding topology 380 originated by the primary leader. 382 o 0x010 (D): Distributed Mode, which instructs every node in an area 383 to compute and use its own flooding topology. 385 o 0x011 (S): Static Mode, which instructs every node in an area to 386 use the flooding topology statically configured on the node. 388 When any of the other values is received, it is ignored. 390 An Algorithm field of eight bits is defined in the TLV to instruct 391 the leader node in centralized mode or every node in distributed mode 392 to use the algorithm indicated in this field for computing a flooding 393 topology. 395 A NL field of three bits is defined in the TLV, which indicates the 396 number of leaders to be selected when Centralized Mode is used. NL 397 set to 2 means two leaders (a designated/primary leader and a backup/ 398 secondary leader) to be selected for an area, and NL set to 3 means 399 three leaders to be selected. When Centralized Mode is not used, The 400 NL field is not valid. 402 Some optional sub TLVs may be defined in the future, but none is 403 defined now. 405 6.2. Extensions for Centralized Mode 407 6.2.1. Message for Flooding Topology 409 A flooding topology can be represented by the links in the flooding 410 topology. For the links between a local node and its adjacent (or 411 remote) nodes, we can encode the local node and its adjacent nodes. 412 After all the links in the flooding topology are encoded, the encoded 413 links can be flooded to every node in the network. After receiving 414 the encoded links, every node decodes the links and creates and/or 415 updates the flooding topology. 417 Every node orders the nodes by their node IDs (router IDs in OSPF, 418 system IDs in IS-IS) in ascending order, and generates the same 419 sequence of the nodes in the area. The sequence of nodes have the 420 index 0, 1, 2, and so on respectively. Every node in the encoded 421 links is represented by its index. 423 6.2.1.1. Links Encoding 425 A local node can be encoded in two parts: encoded node index size 426 indication (ENSI) of 4 bits and compact node index (CNI). ENSI value 427 plus 8 gives the size of compact node index. For example, ENSI = 0 428 indicates that the size of CNIs is 8 bits. In the figure below, 429 Local node LN1 is encoded as ENSI=0 using 4 bits and CNI=LN1's Index 430 using 8 bits. LN1 is encoded in 12 bits in total. 432 0 1 2 3 4 5 6 7 433 +-+-+-+-+-+-+-+-+ 434 |0 0 0 0| ENSI (4 bits) [0 + 8 = 8 bits CNI] 435 +-+-+-+-+-+-+-+-+ 436 | LN1's Index | CNI (8 bits) 437 +-+-+-+-+-+-+-+-+ 439 Encoding for local node LN1 441 The adjacent nodes can be encoded in two parts: Number of Nodes (NN) 442 of 4 bits and compact node indexes (CNIs). The size of CNIs is the 443 same as the local node. For example, local node LN1 has three 444 adjacent nodes RN1, RN2 and RN3 in the following figure. 446 o LN1 447 / | \ 448 / | \ 449 / | \ 450 o RN1 o RN2 o RN3 452 Links from LN1 to its adjacent nodes RN1, RN2 and RN3 454 These three adjacent nodes RN1, RN2 and RN3 are encoded below in 28 455 bits (i.e., 3.5 bytes). 457 0 1 2 3 4 5 6 7 458 +-+-+-+-+-+-+-+-+ 459 |0 0 1 1| NN (4 bits) [3 adjacent nodes] 460 +-+-+-+-+-+-+-+-+ 461 | RN1's Index | CNI (8 bits) for RN1 462 +-+-+-+-+-+-+-+-+ 463 | RN2's Index | CNI (8 bits) for RN2 464 +-+-+-+-+-+-+-+-+ 465 | RN3's Index | CNI (8 bits) for RN3 466 +-+-+-+-+-+-+-+-+ 468 Encoding for three adjacent nodes RN1, RN2 and RN3 470 The links between a local node and its adjacent (or remote) nodes can 471 be encoded as the local node followed by the adjacent nodes. For 472 example, three links between local node LN1 and its three adjacent 473 nodes RN1, RN2 and RN3 are encoded below in 40 bits (i.e., 5 bytes). 475 0 1 2 3 4 5 6 7 476 +-+-+-+-+-+-+-+-+ _ 477 |0 0 0 0| ENSI (4 bits) [8 bits CNI] | 478 +-+-+-+-+-+-+-+-+ } Encoding for 479 | LN1's Index | CNI (8 bits) for LN1 _| Local Node LN1 480 +-+-+-+-+-+-+-+-+ _ 481 |0 0 1 1| NN (4 bits) [3 nodes] | 482 +-+-+-+-+-+-+-+-+ | Encoding for 483 | RN1's Index | CNI (8 bits) for RN1 | 3 adjacent nodes 484 +-+-+-+-+-+-+-+-+ } RN1, RN2, RN3 485 | RN2's Index | CNI (8 bits) for RN2 | of LN1 486 +-+-+-+-+-+-+-+-+ | 487 | RN3's Index | CNI (8 bits) for RN3 _| 488 +-+-+-+-+-+-+-+-+ 490 Links Encoding for links from LN1 to RN1, RN2 and RN3 492 For a flooding topology computed by a leader of an area, it is 493 represented by all the links on the flooding topology. A Type- 494 Length-Value (TLV) of the following format for the links encodings is 495 included in an LSA to represent the flooding topology (FT). 497 0 1 2 3 498 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 500 | FTLK-TLV-Type (TBD2) | TLV-Length | 501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 502 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 506 : : 507 : : 508 Flooding Topology Links TLV 510 Note that a link between a local node LN and its adjacent node RN is 511 encoded once and as a bi-directional link. That is that if it is 512 encoded in a Links Encoding from LN to RN, then the link from RN to 513 LN is implied or assumed. 515 For OSPFv2, an Opaque LSA of a new opaque type (TBD3) containing a 516 Flooding Topology Links TLV is used to flood the flooding topology 517 from the leader of an area to all the other nodes in the area. 519 0 1 2 3 520 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 522 | LS age | Options | LS Type = 10 | 523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 524 | FT-Type(TBD3) | Instance ID | 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 | Advertising Router | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 | LS Sequence Number | 529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 530 | LS checksum | Length | 531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 532 ~ Flooding Topology Links TLV ~ 533 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 535 OSPFv2: Flooding Topology Opaque LSA 537 For OSPFv3, an area scope LSA of a new LSA function code (TBD4) 538 containing a Flooding Topology Links TLV is used to flood the 539 flooding topology from the leader of an area to all the other nodes 540 in the area. 542 0 1 2 3 543 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 545 | LS age |1|0|1| FT-LSA (TBD4) | 546 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 547 | Link State ID | 548 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 549 | Advertising Router | 550 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 | LS Sequence Number | 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | LS checksum | Length | 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 ~ Flooding Topology Links TLV ~ 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 558 OSPFv3: Flooding Topology LSA 560 The U-bit is set to 1, and the scope is set to 01 for area-scoping. 562 6.2.1.2. Block Encoding 564 Block encoding uses a single structure to encode a block (or part) of 565 topology, which can be a block of links in a flooding topology. It 566 can also be all the links in the flooding topology. It starts with a 567 local node LN and its adjacent (or remote) nodes RNi (i = 1, 2, ..., 568 n), and can be considered as an extension to the links encoding. 570 The encoding of links between a local node and its adjacent nodes 571 described in Section 6.2.1.1 is extended to include the links 572 attached to the adjacent nodes. 574 The encoding for the adjacent nodes is extended to include Extending 575 Flags (E Flags for short) between the NN (Number of Nodes) field and 576 the CNIs (Compact Node Indexes) for the adjacent nodes. The length 577 of the E Flags field is NN bits. The following is an encoding of 578 LN1's adjacent nodes RN1, RN2 and RN3 with E Flags of 3 bits, which 579 is the value of the NN (the number of adjacent nodes). 581 0 1 2 3 4 5 6 7 582 +-+-+-+-+-+-+-+-+ _ 583 |0 0 1 1| NN(4 bits)[3 adjacent nodes]| 584 +-+-+-+-+ | 585 |1 0 1| E Flags [NN=3 bits] | Encoding for 586 +-+-+-+-+-+-+-+-+ | 3 adjacent nodes 587 | RN1's Index | CNI (8 bits) for RN1 } (RN1, RN2, RN3) 588 +-+-+-+-+-+-+-+-+ | of LN1 589 | RN2's Index | CNI (8 bits) for RN2 | with E Flags 590 +-+-+-+-+-+-+-+-+ | 591 | RN3's Index | CNI (8 bits) for RN3 _| 592 +-+-+-+-+-+-+-+-+ 594 Encoding of LN1's Adjacent Nodes RN1, RN2 and RN3 with E Flags 596 There is a bit flag (called E flag) in the E Flags field for each 597 adjacent node. The first bit (i.e., the most significant bit) in the 598 E Flags field is for the first adjacent node (e.g., RN1), the second 599 bit is for the second adjacent node (e.g., RN2), and so on. The E 600 flag for an adjacent node RNi set to one indicates that the links 601 attached to the adjacent node RNi are included below. The E flag for 602 an adjacent node RNi set to zero means that no links attached to the 603 adjacent node RNi are included below. 605 The links attached to the adjacent node RNi are represented by the 606 RNi as a local node and the adjacent nodes of RNi. The encoding for 607 the adjacent nodes of RNi is the same as that for the adjacent nodes 608 of a local node. It consists of an NN field of 4 bits, E Flags field 609 of NN bits, and CNIs for the adjacent nodes of RNi. 611 The following is an example of a block encoding for a flooding 612 topology (FT) block below. 614 o LN1 615 / | \ 616 / | \ 617 / | \ 618 o RN1 o RN2 o RN3 619 / / \ 620 / / \ 621 / / \ 622 o RN11 o RN31 o RN32 624 FT Block from LN1 to RN1, RN2 and RN3, and to RN11, RN31 and RN32 626 It represents 6 links: 3 links between local node LN1 and its 3 627 adjacent nodes RN1, RN2 and RN3; 1 link between RN1 as a local node 628 and its 1 adjacent node RN11; and 2 links between RN3 as a local node 629 and its 2 adjacent nodes RN31 and RN32. 631 It starts with the encoding of the links between local node LN1 and 3 632 adjacent nodes RN1, RN2 and RN3 of the local node LN1. The encoding 633 for the local node LN1 is the same as that for a local node described 634 in Section 6.2.1.1. The encoding for 3 adjacent nodes RN1, RN2 and 635 RN3 of local node LN1 comprises an NN field of 4 bits with value of 636 3, E Flags field of NN = 3 bits, and the indexes of adjacent nodes 637 RN1, RN2 and RN3. 639 0 1 2 3 4 5 6 7 640 +-+-+-+-+-+-+-+-+ _ 641 |0 0 0 0| ENSI (4 bits) [8 bits CNI] | 642 +-+-+-+-+-+-+-+-+ } Encoding for 643 | LN1's Index | CNI (8 bits) _| Local Node LN1 644 +-+-+-+-+-+-+-+-+ _ 645 |0 0 1 1| NN(4 bits)[3 adjacent nodes]| 646 +-+-+-+-+ | 647 |1 0 1| E Flags [NN=3 bits] | Encoding for 648 +-+-+-+-+-+-+-+-+ | 3 adjacent nodes 649 | RN1's Index | CNI (8 bits) for RN1 } (RN1, RN2, RN3) 650 +-+-+-+-+-+-+-+-+ | of LN1 651 | RN2's Index | CNI (8 bits) for RN2 | with E Flags 652 +-+-+-+-+-+-+-+-+ | 653 | RN3's Index | CNI (8 bits) for RN3 _| 654 +-+-+-+-+-+-+-+-+ _ 655 |0 0 0 1| NN (4 bits)[1 adjacent node]| 656 +-+-+-+-+ | Encoding for 657 |0| E Flags [NN=1 bit] } 1 adjacent node 658 +-+-+-+-+-+-+-+-+ | (RN11) of RN1 659 | RN11's Index | CNI (8 bits) for RN11 _| with E Flags 660 +-+-+-+-+-+-+-+-+ _ 661 |0 0 1 0| NN(4 bits)[2 adjacent nodes]| 662 +-+-+-+-+ | 663 |0 0| E Flags [NN=2 bits] | Encoding for 664 +-+-+-+-+-+-+-+-+ } 2 adjacent nodes 665 | RN31's Index | CNI (8 bits) for RN31 | (RN31, RN32) 666 +-+-+-+-+-+-+-+-+ | of RN3 as a 667 | RN32's Index | CNI (8 bits) for RN32 | local node 668 +-+-+-+-+-+-+-+-+ _| with E Flags 670 Block Encoding for FT block 671 from LN1 to RN1, RN2 and RN3, and to RN11, RN31 and RN32 673 The first E flag in the encoding for adjacent nodes RN1, RN2 and RN3 674 is set to one, which indicates that the links between the first 675 adjacent node RN1 as a local node and its adjacent nodes are included 676 below. In this example, 1 link between RN1 and its adjacent node 677 RN11 is represented by the encoding for the adjacent node RN11 of RN1 678 as a local node. The encoding for 1 adjacent node RN11 consists of 679 an NN field of 4 bits with value of 1, E Flags field of NN = 1 bits, 680 and the index of adjacent node RN11. The size of the index of RN11 681 is the same as that of local node LN1 indicated by the ENSI in the 682 encoding for local node LN1. 684 The second E flag in the encoding for adjacent nodes RN1, RN2 and RN3 685 is set to zero, which indicates that no links between the second 686 adjacent node RN2 as a local node and its adjacent nodes are included 687 below. 689 The third E flag in the encoding for adjacent nodes RN1, RN2 and RN3 690 is set to one, which indicates that the links between the third 691 adjacent node RN3 as a local node and its adjacent nodes are included 692 below. In this example, 2 links between RN3 and its 2 adjacent nodes 693 RN31 and RN32 are represented by the encoding for the adjacent nodes 694 RN31 and RN32 of RN3 as a local node. The encoding for 2 adjacent 695 nodes RN31 and RN32 consists of an NN field of 4 bits with value of 696 2, E Flags field of NN = 2 bits, and the indexes of adjacent nodes 697 RN31 and RN32. The size of the index of RN31 and RN32 is the same as 698 that of local node LN1 indicated by the ENSI in the encoding for 699 local node LN1. 701 A new TLV is defined to contain a number of block encodings, and is 702 called Flooding Topology Blocks TLV or Blocks TLV for short. Its 703 format is illustrated below. This TLV may be used in the place of 704 Links TLV in Section 6.2.1.1 for more efficiency. 706 0 1 2 3 707 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 708 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 709 | FTBK-TLV-Type (TBD5) | TLV-Length | 710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 711 ~ Block Encoding (for FT block from Node i to ~ 712 ~ its adjacent Nodes, and so on) ~ 713 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 714 ~ Block Encoding (for FT block from Node j to ~ 715 ~ its adjacent Nodes, and so on) ~ 716 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 717 : : 718 : : 719 Flooding Topology Blocks TLV 721 6.2.2. Leaders Selection 723 The leader or Designated Router (DR) selection for a broadcast link 724 is about selecting two leaders: a DR and Backup DR. This is 725 generalized to select two or more leaders for an area: the primary/ 726 first leader (or leader for short), the secondary leader, the third 727 leader and so on. 729 A new TLV is defined to include the information on flooding reduction 730 of a node, which is called Flooding Reduction Information TLV or 731 Information TLV for short. This TLV is generated by every node that 732 supports flooding reduction in general. Every node originates a RI 733 LSA with a Flooding Reduction Information TLV containing its priority 734 to become a leader. The format of the TLV is as follows. 736 0 1 2 3 737 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 739 | INFO-TLV-Type (TBD6) | TLV-Length | 740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 741 | Priority | Reserved (MUST be zero) | 742 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 743 ~ sub TLVs (optional) ~ 744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 746 Flooding Reduction Information TLV 748 A Priority field of eight bits is defined in the TLV to indicate the 749 priority of the node originating the TLV to become the leader node in 750 centralized mode. 752 A sub-TLV called leaders sub-TLV is defined. It has the following 753 format. 755 0 1 2 3 756 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 758 | LEADS-TLV-Type (TBD7) | TLV-Length | 759 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 760 | 1st Leader Node/Router ID | 761 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 762 | 2nd Leader Node/Router ID | 763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 764 ~ ~ 765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 766 | nth Leader Node/Router ID | 767 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 769 Leaders sub-TLV 771 When a node selects itself as a leader, it originates a RI LSA 772 containing the leader in a leaders sub-TLV. 774 After the first leader node is down, the other leaders will be 775 promoted. The secondary leader becomes the first leader, the third 776 leader becomes the secondary leader, and so on. When a node selects 777 itself as the n-th leader, it originates a RI LSA with a Leaders sub- 778 TLV containing n leaders. 780 7. Extensions to IS-IS 782 The extensions to IS-IS is similar to OSPF. 784 7.1. Extensions for Operations 786 A new TLV for operations is defined in IS-IS LSP. It has the 787 following format and contains the same contents as the Flooding 788 Reduction Instruction TLV defined in OSPF RI LSA. 790 0 1 2 3 791 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 793 |INS-Type(TBDi1)| Length | 794 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 795 | OP | MOD | Algorithm | Reserved (MUST be zero) | NL | 796 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 797 ~ sub TLVs (optional) ~ 798 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 800 IS-IS Flooding Reduction Instruction TLV 802 7.2. Extensions for Centralized Mode 804 7.2.1. TLV for Flooding Topology 806 A new TLV for the encodings of the links in the flooding topology is 807 defined. It has the following format and contains the same contents 808 as the Flooding Topology Links TLV defined in OSPF Flooding Topology 809 Opaque LSA. 811 0 1 2 3 812 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 813 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 814 |FTL-Type(TBDi2)| Length | 815 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 816 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 817 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 818 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 820 : : 821 : : 822 IS-IS Flooding Topology Links TLV 824 Another new TLV for the encodings of the blocks in the flooding 825 topology is defined. It has the format below and contains the same 826 contents as the Flooding Topology Blocks TLV defined in previous 827 section. 829 0 1 2 3 830 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 |FTB-Type(TBDi3)| Length | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 ~ Block Encoding (for FT block from Node i to ~ 835 ~ its adjacent Nodes, and so on) ~ 836 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 837 ~ Block Encoding (for FT block from Node j to ~ 838 ~ its adjacent Nodes, and so on) ~ 839 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 840 : : 841 : : 842 ISIS Flooding Topology Blocks TLV 844 7.2.2. Leaders Selection 846 Similar to Flooding Reduction Information TLV in OSPF, a new TLV 847 called IS-IS Flooding Reduction Information TLV is defined. It has 848 the following format and contains the same contents as Flooding 849 Reduction Information TLV in OSPF. 851 0 1 2 3 852 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 853 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 854 |INF-Type(TBDi4)| Length | 855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 856 | Priority | Reserved (MUST be zero) | 857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 858 ~ sub TLVs (optional) ~ 859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 861 IS-IS Flooding Reduction Information TLV 863 A sub-TLV called IS-IS leaders sub-TLV is defined. It has the 864 following format and contains the contents similar to those in 865 leaders sub-TLV in OSPF. 867 0 1 2 3 868 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 870 |LeadType(TBDi5)| Length | 871 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 872 ~ 1st Leader Node/System ID ~ 873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 874 ~ 2nd Leader Node/System ID ~ 875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 876 ~ ~ 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 878 ~ nth Leader Node/System ID ~ 879 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 881 IS-IS Leaders sub-TLV 883 8. Flooding Behavior 885 This section describes the revised flooding behavior for a node. The 886 revised flooding procedure MUST flood an LS to every node in the 887 network in any case, as the standard flooding procedure does. 889 8.1. Nodes Perform Flooding Reduction without Failure 891 8.1.1. Receiving an LS 893 When a node receives a newer LS that is not originated by itself from 894 one of its interfaces, it floods the LS only to all the other 895 interfaces that are on the flooding topology. 897 When the LS is received from an interface on the flooding topology, 898 it is flooded only to all the other interfaces that are on the 899 flooding topology. When the LS is received on an interface that is 900 not on the flooding topology, it is also flooded only to all the 901 other interfaces that are on the flooding topology. 903 In any case, the LS must not be transmitted back to the receiving 904 interface. 906 Note before forwarding a received LS, the node would do the normal 907 processing as usual. 909 8.1.2. Originating an LS 911 When a node originates an LS, it floods the LS to its interfaces on 912 the flooding topology if the LS is a refresh LS (i.e., there is no 913 significant change in the LS comparing to the previous LS); otherwise 914 (i.e., there are significant changes such as link down in the LS), it 915 floods the LS to all its interfaces. Choosing flooding the LS with 916 significant changes to all the interfaces instead of limiting to the 917 interfaces on the flooding topology would speed up the distribution 918 of the significant link state changes. 920 8.1.3. Establishing Adjacencies 922 Adjacencies being established can be classified into two categories: 923 adjacencies to new nodes and adjacencies to existing nodes. 925 8.1.3.1. Adjacency to New Node 927 An adjacency to a new node is an adjacency between an existing node 928 (say node E) on the flooding topology and the new node (say node N) 929 which is not on the flooding topology. There is not any adjacency 930 between node N and a node in the network area. The procedure for 931 establishing the adjacency between E and N is the existing normal 932 procedure unchanged. 934 When the adjacency between N and E is established, node E adds node N 935 and the link between N and E to the flooding topology temporarily 936 until a new flooding topology is built. New node N adds node N and 937 the link between N and E to the flooding topology temporarily until a 938 new flooding topology is built. 940 8.1.3.2. Adjacency to Existing Node 942 An adjacency to an existing node is an adjacency between two nodes 943 (say nodes E and X) on the flooding topology. The procedure for 944 establishing the adjacency between E and X is the existing normal 945 procedure unchanged. 947 Both node E and node X assume that the link between E and X is not on 948 the flooding topology until a new flooding topology is built. After 949 the adjacency between E and X is established, node E does not send 950 node X any new or updated LS that it receives or originates, and node 951 X does not send node E any new or updated LS that it receives or 952 originates until a new flooding topology is built. 954 8.2. An Exception Case 956 During an LS flooding, one or more link and node failures may happen. 957 Some failures do not split the flooding topology, thus do not affect 958 the flooding behavior. For example, multiple failures of the links 959 not on the flooding topology do not split the flooding topology and 960 do not affect the flooding behavior. The sections below focus on the 961 failures that may split the flooding topology. 963 8.2.1. Multiple Failures 965 When two or more failures on the current flooding topology occur 966 almost in the same time, each of the nodes within a given distance 967 (such as 3 hops) to a failure point, floods the link state (LS) that 968 it receives or originates to all its links (except for the one from 969 which the LS is received) until a new flooding topology is built. 971 In other words, when the failures happen, each of the nodes within a 972 given distance to a failure point, adds all its local links to the 973 flooding topology temporarily until a new flooding topology is built. 975 In alternative way, each node computes and maintains a small number 976 of backup paths. For a backup path for a link L on the flooding 977 topology, a node N computes and maintains it only if the backup path 978 goes through node N. Node N stores the links (e.g., local link L1 979 and L2) attached to it and on the backup path for link L. When link 980 L fails and there are one or more other failures on the flooding 981 topology or the flooding topology splits, node N adds the links 982 (e.g., L1 and L2) to the flooding topology temporarily until a new 983 flooding topology is built. 985 Similarly, for a backup path for a connection crossing a node M on 986 the flooding topology, a node N computes and maintains it only if the 987 backup path goes through node N. Node N stores the links (e.g., 988 local link La and Lb) attached to it and on the backup path for node 989 M. 991 When node M fails and there are one or more other failures on the 992 flooding topology or the flooding topology splits, node N adds the 993 links (e.g., La and Lb) to the flooding topology temporarily until a 994 new flooding topology is built. 996 For one link/node failure that splits the current flooding topology, 997 the above behavior is applied. 999 Note that if it can be quickly determined that the flooding topology 1000 is not split by the failures, the flooding behavior in Section 8.1 1001 may follow. 1003 8.2.2. Changes on Flooding Topology 1005 After multiple failures split the current (old) flooding topology, 1006 some link states may be out of synchronization among some nodes. 1007 This can be resolved as follows. 1009 After a node N computes or receives a new flooding topology, for a 1010 local link L attached to node N, if 1) link L is not on the current 1011 (old) flooding topology and is on the new flooding topology, and 2) 1012 there is a failure after the current (old) flooding topology is 1013 built, then node N sends a delta of the link states that it received 1014 or originated to its adjacent node over link L. 1016 For node N, the delta of the link states is the link states with 1017 changes that node N received or originated during the period of time 1018 in which the current (old) flooding topology is split. 1020 Suppose that Max_Split_Period is a number (in seconds), which is the 1021 maximum period of time in which a flooding topology is split. Tc is 1022 the time at which the current (old) flooding topology is built, Tn is 1023 the time at which the new flooding topology is built, and Ts is the 1024 bigger one between Tc and (Tn - Max_Split_Period). Node N sends its 1025 adjacent node over link L the link states with changes that it 1026 received or originated from Ts to Tn. 1028 9. Operations on Flooding Reduction 1029 9.1. Configuring Flooding Reduction 1031 This section describes configurations for link state flooding 1032 reduction, including configurations for centralized flooding 1033 reduction (i.e., flooding reduction in centralized mode) and 1034 configurations for distributed flooding reduction (i.e., flooding 1035 reduction in distributed mode). 1037 9.1.1. Configurations for Centralized Flooding Reduction 1039 At first, for each node, if it is eligible to become a leader for 1040 flooding reduction in centralized mode, a user configures a priority 1041 on the node for the leader election. The value range for the 1042 priority is from 0 to 255. A node with a priority set to zero cannot 1043 become a leader. The node with the higher priority has the higher 1044 precedence to be elected as the leader. 1046 And then, a user selects the centralized mode on one node, which 1047 tells the other nodes in the area to use centralized flooding 1048 reduction. 1050 9.1.2. Configurations for Distributed Flooding Reduction 1052 For distributed flooding reduction, an algorithm for computing a 1053 flooding topology needs to be configured. The algorithm and 1054 distributed mode are configured on one node, which tells the other 1055 nodes in the area the algorithm and the mode via advertising the 1056 number of the algorithm and the mode. Every node participating in 1057 the distributed flooding reduction uses this same algorithm. 1059 9.2. Migration to Flooding Reduction 1061 Migrating a OSPF or IS-IS area from normal flooding to flooding 1062 reduction smoothly takes a few steps or stages. This section 1063 describes the steps for migrating an area to centralized flooding 1064 reduction or distributed flooding reduction from normal flooding. 1066 9.2.1. Migration to Centralized Flooding Reduction 1068 At first, a user configures a priority on every node that is eligible 1069 for the leader for centralized flooding reduction. In this stage, a 1070 node does not originate or advertise its priority. 1072 Second, after configuring the priority, a user selects the 1073 centralized mode on one node, which tells the other nodes in the area 1074 to use centralized flooding reduction. 1076 After a node knows that the centralized mode is used, it originates 1077 and advertises its priority. The leader election is started in the 1078 area. A user may check whether a leader is elected through showing 1079 the link state containing leaders. After the leader is elected, the 1080 centralized flooding reduction may be activated. 1082 And then, a user activates the flooding reduction through using a 1083 configuration such as perform flooding Reduction on one node, which 1084 tells all the nodes in the area to use centralized flooding 1085 reduction. The node generates and advertises a link state with OP = 1086 R (indicating perform flooding Reduction) after it receives the 1087 configuration. After another node in the area receives the link 1088 state with OP = R, it also perform flooding reduction (i.e., floods 1089 link states using flooding topology). Thus, activating the flooding 1090 reduction on one node propagates to every node in the area, which 1091 migrates to flooding reduction. 1093 9.2.2. Migration to Distributed Flooding Reduction 1095 At first, a user selects the distributed mode on one node, which 1096 tells the other nodes in the area to use distributed flooding 1097 reduction. 1099 After a node knows that the distributed mode is used, it advertises 1100 the algorithms it supports. A user may check whether every node 1101 advertises its supporting algorithms through showing the link state 1102 containing the algorithms. 1104 And then, a user selects an algorithm and activates the flooding 1105 reduction through using configurations such as perform flooding 1106 Reduction on one node, which tells all the nodes in the area to use 1107 the given algorithm and start the distributed flooding reduction. 1109 9.3. Roll Back to Normal Flooding 1111 For rolling back from flooding reduction to normal flooding, a user 1112 de-activates the flooding reduction through configuring roll back to 1113 normal flooding on one node, which tells all the nodes in the area to 1114 roll back to normal flooding. 1116 After receiving a configuration to roll back to normal flooding, the 1117 node floods link states using all its local links instead of the 1118 local links on the flooding topology. It also advertises the roll 1119 back to Normal flooding (i.e., OP = N) to all the other nodes in the 1120 area. When each of the other nodes receives the advertisement, it 1121 rolls back to normal flooding (i.e., floods link states using all its 1122 local links instead of the local links on the flooding topology). 1124 In centralized mode, after rolling back to normal flooding, the 1125 leader of the area stops computing and advertising a flooding 1126 topology, the other nodes stops receiving and building the flooding 1127 topology. In distributed mode, every node in the area will not 1128 compute or build flooding topology. 1130 9.4. Transfer from Distributed to Centralized Mode 1132 When the distributed flooding reduction in an area is running, in 1133 order to transfer it to centralized flooding reduction, a user may 1134 take the following steps. 1136 At first, the user rolls back from flooding reduction to normal 1137 flooding as described in section "Roll Back to Normal Flooding". 1139 And then, the user migrates to centralized flooding reduction from 1140 normal flooding as described in section "Migration to Centralized 1141 Flooding Reduction". 1143 Alternatively, the user may just change the flooding reduction mode 1144 from distributed mode to centralized mode on one node through a 1145 configuration. After receiving the configuration for changing the 1146 mode, the node transfers from distributed mode to centralized mode 1147 and tells the other nodes the change through advertising MOD = C 1148 (i.e., Centralized mode). After receiving the advertisement, each of 1149 the other nodes transfers from distributed mode to centralized mode. 1151 Note that before changing the flooding reduction mode to centralized 1152 mode, the user needs to configure a priority on every node that is 1153 eligible for the leader for centralized flooding reduction. 1155 While transferring from distributed mode to centralized mode, a node 1156 uses the distributed flooding reduction (i.e., floods the link states 1157 over its local links on the flooding topology computed and built by 1158 itself) until the centralized flooding reduction is fully functional 1159 for a given time such as 5 seconds. After this time, the node stops 1160 its distributed flooding reduction, i.e., stops computing and 1161 building its flooding topology, and using this flooding topology to 1162 flood the link states. 1164 Each node in the area advertises its priority. A leader will be 1165 elected for the area. The leader starts to compute a flooding 1166 topology and floods it to all the other nodes. Every node builds the 1167 flooding topology computed by the leader and starts to flood the link 1168 states over its local links on this flooding topology. 1170 9.5. Transfer from Centralized to Distributed Mode 1172 When the centralized flooding reduction in an area is running, in 1173 order to transfer it to distributed flooding reduction, a user may 1174 take the following steps. 1176 At first, the user rolls back from flooding reduction to normal 1177 flooding as described in section "Roll Back to Normal Flooding". 1179 And then, the user migrates to distributed flooding reduction from 1180 normal flooding as described in section "Migration to Distributed 1181 Flooding Reduction". 1183 Alternatively, the user may just change the flooding reduction mode 1184 from centralized mode to distributed mode on one node through a 1185 configuration. After receiving the configuration for changing the 1186 mode, the node transfers from centralized mode to distributed mode 1187 and tells the other nodes the change through advertising MOD = D 1188 (i.e., Distributed mode). After receiving the advertisement, each of 1189 the other nodes transfers from centralized mode to distributed mode. 1191 While transferring from centralized mode to distributed mode, a node 1192 uses the centralized flooding reduction (i.e., floods the link states 1193 over its local links on the flooding topology computed by the leader 1194 of the area) until the distributed flooding reduction is fully 1195 functional for a given time. After this time, the node stops its 1196 centralized flooding reduction. The leader stops computing the 1197 flooding topology, advertising it to all the other routers, and using 1198 this flooding topology to flood the link states. Each of the other 1199 nodes stops receiving and building the flooding topology computed by 1200 the leader. 1202 Every node starts to compute and build its flooding topology and to 1203 flood the link states over its local links on this flooding topology. 1205 9.6. Adding a New Node to Network 1207 If the centralized flooding reduction is used in an area, for adding 1208 a new node (say node N) to the area, a user configures a priority for 1209 this new node to become the leader of the area. 1211 The other configurations on the new node are the existing normal ones 1212 unchanged. 1214 When the new node N is connected via a link to a node (say E) on the 1215 flooding topology, there is not any adjacency between them (i.e., N 1216 and E) over the link. The procedure for establishing the adjacency 1217 between N and E is the existing normal procedure unchanged. 1219 Node E adds node N and the link between N and E to the flooding 1220 topology temporarily until a new flooding topology is built. 1222 New node N adds node N and the link between N and E to the flooding 1223 topology temporarily until a new flooding topology is built. 1225 10. Manageability Considerations 1227 Section 9 "Operations on Flooding Reduction" outlines the 1228 configuration process and deployment scenarios for link state 1229 flooding reduction. The configurable items include to set the 1230 priority of a node to become a leader of the area for link state 1231 flooding reduction in centralized mode. The flooding reduction 1232 function may be controlled by a policy module and assigned a suitable 1233 user privilege level to enable. A suitable model may be required to 1234 verify the flooding reduction status on routers participating in the 1235 flooding reduction, including their role as a leader in centralized 1236 mode or a normal node advertising link states using flooding 1237 topology. The mechanisms defined in this document do not imply any 1238 new liveness detection and monitoring requirements in addition to 1239 those indicated in [RFC2328] and [RFC1195]. 1241 11. Security Considerations 1243 A notable beneficial security aspect of link state flooding reduction 1244 is that the flooding topology in the centralized mode is advertised 1245 in a single area, and a link state is not advertised over every link, 1246 but over the links on the flooding topology. It should be noted that 1247 a malicious node could inject a fake flooding topology in the 1248 centralized mode, which could lead inconsistent link state databases 1249 among the nodes in an area. The malicious node could inject a link 1250 state with the OP field set to R or N, which could trigger the 1251 migration or roll back into/from a flooding reduction. Good security 1252 practice might reuse the IS-IS authentication in [RFC5304] as well as 1253 [RFC5310], and the OSPF authentication and other security mechanisms 1254 described in [RFC2328], [RFC4552] and [RFC7474] to mitigate this type 1255 of risk. 1257 12. IANA Considerations 1259 12.1. OSPFv2 1261 Under Registry Name: OSPF Router Information (RI) TLVs [RFC7770], 1262 IANA is requested to assign two new TLV values for OSPF flooding 1263 reduction as follows: 1265 +===============+==================+=====================+ 1266 | TLV Value | TLV Name | reference | 1267 +===============+==================+=====================+ 1268 | 11 | Instruction TLV | This document | 1269 +---------------+------------------+---------------------+ 1270 | 12 | Information TLV | This document | 1271 +---------------+------------------+---------------------+ 1273 Under the registry name "Opaque Link-State Advertisements (LSA) 1274 Option Types" [RFC5250], IANA is requested to assign new Opaque Type 1275 registry values for FT LSA as follows: 1277 +====================+===============+=======================+ 1278 | Registry Value | Opaque Type | reference | 1279 +====================+===============+=======================+ 1280 | 10 | FT LSA | This document | 1281 +--------------------+---------------+-----------------------+ 1283 IANA is requested to create and maintain new registries: 1285 o OSPFv2 FT LSA TLVs 1287 Initial values for the registry are given below. The future 1288 assignments are to be made through IETF Review [RFC5226]. 1290 Value OSPFv2 FT LSA TLV Name Definition 1291 ----- ----------------------- ---------- 1292 0 Reserved 1293 1 FT Links TLV see Section 6.2.1.1 1294 2 FT Blocks TLV see Section 6.2.1.2 1295 3-32767 Unassigned 1296 32768-65535 Reserved 1298 12.2. OSPFv3 1300 Under the registry name "OSPFv3 LSA Function Codes", IANA is 1301 requested to assign new registry values for FT LSA as follows: 1303 +===========+==========================+=======================+ 1304 | Value | LSA Function Code Name | reference | 1305 +======================================+=======================+ 1306 | 16 | FT LSA | This document | 1307 +-----------+--------------------------+-----------------------+ 1309 IANA is requested to create and maintain new registries: 1311 o OSPFv3 FT LSA TLVs 1313 Initial values for the registry are given below. The future 1314 assignments are to be made through IETF Review [RFC5226]. 1316 Value OSPFv3 FT LSA TLV Name Definition 1317 ----- ----------------------- ---------- 1318 0 Reserved 1319 1 FT Links TLV see Section 6.2.1.1 1320 2 FT Blocks TLV see Section 6.2.1.2 1321 3-32767 Unassigned 1322 32768-65535 Reserved 1324 12.3. IS-IS 1326 Under Registry Name: IS-IS TLV Codepoints, IANA is requested to 1327 assign new TLV values for IS-IS flooding reduction as follows: 1329 Value TLV Name Definition 1330 ----- ------------------------ ---------- 1331 151 FT Links TLV see Section 7.2.1 1332 152 FT Blocks TLV see Section 7.2.1 1333 153 Instruction TLV see Section 7.1 1334 154 Information TLV see Section 7.2.2 1336 13. Acknowledgements 1338 The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, 1339 Stephane Litkowski and Alvaro Retana for their valuable suggestions 1340 and comments on this draft. 1342 14. References 1344 14.1. Normative References 1346 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 1347 dual environments", RFC 1195, DOI 10.17487/RFC1195, 1348 December 1990, . 1350 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1351 Requirement Levels", BCP 14, RFC 2119, 1352 DOI 10.17487/RFC2119, March 1997, 1353 . 1355 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1356 DOI 10.17487/RFC2328, April 1998, 1357 . 1359 [RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality 1360 for OSPFv3", RFC 4552, DOI 10.17487/RFC4552, June 2006, 1361 . 1363 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 1364 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 1365 July 2008, . 1367 [RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic 1368 Authentication", RFC 5304, DOI 10.17487/RFC5304, October 1369 2008, . 1371 [RFC5310] Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R., 1372 and M. Fanto, "IS-IS Generic Cryptographic 1373 Authentication", RFC 5310, DOI 10.17487/RFC5310, February 1374 2009, . 1376 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 1377 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 1378 . 1380 [RFC7474] Bhatia, M., Hartman, S., Zhang, D., and A. Lindem, Ed., 1381 "Security Extension for OSPFv2 When Using Manual Key 1382 Management", RFC 7474, DOI 10.17487/RFC7474, April 2015, 1383 . 1385 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 1386 S. Shaffer, "Extensions to OSPF for Advertising Optional 1387 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 1388 February 2016, . 1390 14.2. Informative References 1392 [I-D.li-dynamic-flooding] 1393 Li, T. and P. Psenak, "Dynamic Flooding on Dense Graphs", 1394 draft-li-dynamic-flooding-05 (work in progress), June 1395 2018. 1397 [I-D.shen-isis-spine-leaf-ext] 1398 Shen, N., Ginsberg, L., and S. Thyamagundalu, "IS-IS 1399 Routing for Spine-Leaf Topology", draft-shen-isis-spine- 1400 leaf-ext-07 (work in progress), October 2018. 1402 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1403 IANA Considerations Section in RFCs", RFC 5226, 1404 DOI 10.17487/RFC5226, May 2008, 1405 . 1407 Appendix A. Algorithms to Build Flooding Topology 1409 There are many algorithms to build a flooding topology. A simple and 1410 efficient one is briefed below. 1412 o Select a node R according to a rule such as the node with the 1413 biggest/smallest node ID; 1415 o Build a tree using R as root of the tree (details below); and then 1417 o Connect k (k>=0) leaves to the tree to have a flooding topology 1418 (details follow). 1420 A.1. Algorithms to Build Tree without Considering Others 1422 An algorithm for building a tree from node R as root starts with a 1423 candidate queue Cq containing R and an empty flooding topology Ft: 1425 1. Remove the first node A from Cq and add A into Ft 1427 2. If Cq is empty, then return with Ft 1429 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1430 and not in Ft and X1, X2, ..., Xn are in a special order. For 1431 example, X1, X2, ..., Xn are ordered by the cost of the link 1432 between A and Xi. The cost of the link between A and Xi is less 1433 than the cost of the link between A and Xj (j = i + 1). If two 1434 costs are the same, Xi's ID is less than Xj's ID. In another 1435 example, X1, X2, ..., Xn are ordered by their IDs. If they are 1436 not ordered, then make them in the order. 1438 4. Add Xi (i = 1, 2, ..., n) into the end of Cq, goto step 1. 1440 Another algorithm for building a tree from node R as root starts with 1441 a candidate queue Cq containing R and an empty flooding topology Ft: 1443 1. Remove the first node A from Cq and add A into Ft 1445 2. If Cq is empty, then return with Ft 1447 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1448 and not in Ft and X1, X2, ..., Xn are in a special order. For 1449 example, X1, X2, ..., Xn are ordered by the cost of the link 1450 between A and Xi. The cost of the link between A and Xi is less 1451 than the cost of the link between A and Xj (j = i + 1). If two 1452 costs are the same, Xi's ID is less than Xj's ID. In another 1453 example, X1, X2, ..., Xn are ordered by their IDs. If they are 1454 not ordered, then make them in the order. 1456 4. Add Xi (i = 1, 2, ..., n) into the front of Cq and goto step 1. 1458 A third algorithm for building a tree from node R as root starts with 1459 a candidate list Cq containing R associated with cost 0 and an empty 1460 flooding topology Ft: 1462 1. Remove the first node A from Cq and add A into Ft 1464 2. If all the nodes are on Ft, then return with Ft 1466 3. Suppose that node A is associated with a cost Ca which is the 1467 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 1468 connected to node A and not in Ft and the cost of the link 1469 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 1470 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 1471 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 1472 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 1473 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 1475 4. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 1476 ..., m) are the nodes in Cq, Cai is the cost associated with Ai, 1477 and IDi is the ID of Ai. One order is that for any k = 1, 2, 1478 ..., m-1, Cak < Caj (j = k+1) or Cak = Caj and IDk < IDj. Goto 1479 step 1. 1481 A.2. Algorithms to Build Tree Considering Others 1483 An algorithm for building a tree from node R as root with 1484 consideration of others's support for flooding reduction starts with 1485 a candidate queue Cq containing R associated with previous hop PH=0 1486 and an empty flooding topology Ft: 1488 1. Remove the first node A that supports flooding reduction from the 1489 candidate queue Cq if there is such a node A; otherwise (i.e., if 1490 there is not such node A in Cq), then remove the first node A 1491 from Cq. Add A into the flooding topology Ft. 1493 2. If Cq is empty or all nodes are on Ft, then return with Ft 1495 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1496 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 1497 special order considering whether some of them that support 1498 flooding reduction (. For example, X1, X2, ..., Xn are ordered 1499 by the cost of the link between A and Xi. The cost of the link 1500 between A and Xi is less than that of the link between A and Xj 1501 (j = i + 1). If two costs are the same, Xi's ID is less than 1502 Xj's ID. The cost of a link is redefined such that 1) the cost 1503 of a link between A and Xi both support flooding reduction is 1504 much less than the cost of any link between A and Xk where Xk 1505 with F=0; 2) the real metric of a link between A and Xi and the 1506 real metric of a link between A and Xk are used as their costs 1507 for determining the order of Xi and Xk if they all (i.e., A, Xi 1508 and Xk) support flooding reduction or none of Xi and Xk support 1509 flooding reduction. 1511 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 1512 the end of the candidate queue Cq, and goto step 1. 1514 Another algorithm for building a tree from node R as root with 1515 consideration of others' support for flooding reduction starts with a 1516 candidate queue Cq containing R associated with previous hop PH=0 and 1517 an empty flooding topology Ft: 1519 1. Remove the first node A that supports flooding reduction from the 1520 candidate queue Cq if there is such a node A; otherwise (i.e., if 1521 there is not such node A in Cq), then remove the first node A 1522 from Cq. Add A into the flooding topology Ft. 1524 2. If Cq is empty or all nodes are on Ft, then return with Ft. 1526 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1527 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 1528 special order considering whether some of them support flooding 1529 reduction. For example, X1, X2, ..., Xn are ordered by the cost 1530 of the link between A and Xi. The cost of the link between A and 1531 Xi is less than the cost of the link between A and Xj (j = i + 1532 1). If two costs are the same, Xi's ID is less than Xj's ID. 1533 The cost of a link is redefined such that 1) the cost of a link 1534 between A and Xi both support flooding reduction is much less 1535 than the cost of any link between A and Xk where Xk does not 1536 support flooding reduction; 2) the real metric of a link between 1537 A and Xi and the real metric of a link between A and Xk are used 1538 as their costs for determining the order of Xi and Xk if they all 1539 (i.e., A, Xi and Xk) support flooding reduction or none of Xi and 1540 Xk supports flooding reduction. 1542 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 1543 the front of the candidate queue Cq, and goto step 1. 1545 A third algorithm for building a tree from node R as root with 1546 consideration of others' support for flooding reduction (using flag F 1547 = 1 for support, and F = 0 for not support in the following) starts 1548 with a candidate list Cq containing R associated with low order cost 1549 Lc=0, high order cost Hc=0 and previous hop ID PH=0, and an empty 1550 flooding topology Ft: 1552 1. Remove the first node A from Cq and add A into Ft. 1554 2. If all the nodes are on Ft, then return with Ft 1556 3. Suppose that node A is associated with a cost Ca which is the 1557 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 1558 connected to node A and not in Ft and the cost of the link 1559 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 1560 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 1561 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 1562 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 1563 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 1565 4. Suppose that node A is associated with a low order cost LCa which 1566 is the low order cost from root R to node A and a high order cost 1567 HCa which is the high order cost from R to A, node Xi (i = 1, 2, 1568 ..., n) is connected to node A and not in the flooding topology 1569 Ft and the real cost of the link between A and Xi is Ci (i=1, 2, 1570 ..., n). Compute LCxi and HCxi: LCxi = LCa + Ci if both A and Xi 1571 have flag F set to one, otherwise LCxi = LCa HCxi = HCa + Ci if A 1572 or Xi does not have flag F set to one, otherwise HCxi = HCa If Xi 1573 is not in Cq, then add Xi associated with LCxi, HCxi and PH = A 1574 into Cq; If Xi associated with LCxi' and HCxi' and PHxi' is in 1575 Cq, then If HCxi' > HCxi then replace Xi with HCxi', LCxi' and 1576 PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise (i.e., 1577 HCxi' == HCxi) if LCxi' > LCxi , then replace Xi with HCxi', 1578 LCxi' and PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise 1579 (i.e., HCxi' == HCxi and LCxi' == LCxi) if PHxi' > PH, then 1580 replace Xi with HCxi', LCxi' and PHxi' by Xi with HCxi, LCxi and 1581 PH=A in Cq. 1583 5. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 1584 ..., m) are the nodes in Cq, HCai and LCai are low order cost and 1585 high order cost associated with Ai, and IDi is the ID of Ai. One 1586 order is that for any k = 1, 2, ..., m-1, HCak < HCaj (j = k+1) 1587 or HCak = HCaj and LCak < LCaj or HCak = HCaj and LCak = LCaj and 1588 IDk < IDj. Goto step 1. 1590 A.3. Connecting Leaves 1592 Suppose that we have a flooding topology Ft built by one of the 1593 algorithms described above. Ft is like a tree. We may connect k (k 1594 >=0) leaves to the tree to have a enhanced flooding topology with 1595 more connectivity. 1597 Suppose that there are m (0 < m) leaves directly connected to a node 1598 X on the flooding topology Ft. Select k (k <= m) leaves through 1599 using a deterministic algorithm or rule. One algorithm or rule is to 1600 select k leaves that have smaller or larger IDs (i.e., the IDs of 1601 these k leaves are smaller/bigger than the IDs of the other leaves 1602 directly connected to node X). Since every node has a unique ID, 1603 selecting k leaves with smaller or larger IDs is deterministic. 1605 If k = 1, the leaf selected has the smallest/largest node ID among 1606 the IDs of all the leaves directly connected to node X. 1608 For a selected leaf L directly connected to a node N in the flooding 1609 topology Ft, select a connection/adjacency to another node from node 1610 L in Ft through using a deterministic algorithm or rule. 1612 Suppose that leaf node L is directly connected to nodes Ni (i = 1613 1,2,...,s) in the flooding topology Ft via adjacencies and node Ni is 1614 not node N, IDi is the ID of node Ni, and Hi (i = 1,2,...,s) is the 1615 number of hops from node L to node Ni in the flooding topology Ft. 1617 One Algorithm or rule is to select the connection to node Nj (1 <= j 1618 <= s) such that Hj is the largest among H1, H2, ..., Hs. If there is 1619 another node Na ( 1 <= a <= s) and Hj = Ha, then select the one with 1620 smaller (or larger) node ID. That is that if Hj == Ha and IDj < IDa 1621 then select the connection to Nj for selecting the one with smaller 1622 node ID (or if Hj == Ha and IDj < IDa then select the connection to 1623 Na for selecting the one with larger node ID). 1625 Suppose that the number of connections in total between leaves 1626 selected and the nodes in the flooding topology Ft to be added is 1627 NLc. We may have a limit to NLc. 1629 Authors' Addresses 1631 Huaimo Chen 1632 Huawei Technologies 1633 Boston 1634 USA 1636 Email: huaimo.chen@huawei.com 1638 Dean Cheng 1639 Huawei Technologies 1640 Santa Clara 1641 USA 1643 Email: dean.cheng@huawei.com 1644 Mehmet Toy 1645 Verizon 1646 USA 1648 Email: mehmet.toy@verizon.com 1650 Yi Yang 1651 IBM 1652 Cary, NC 1653 United States of America 1655 Email: yyietf@gmail.com 1657 Aijun Wang 1658 China Telecom 1659 Beiqijia Town, Changping District 1660 Beijing 102209 1661 China 1663 Email: wangaj.bri@chinatelecom.cn 1665 Xufeng Liu 1666 Volta Networks 1667 McLean, VA 1668 USA 1670 Email: xufeng.liu.ietf@gmail.com 1672 Yanhe Fan 1673 Casa Systems 1674 USA 1676 Email: yfan@casa-systems.com 1678 Lei Liu 1679 USA 1681 Email: liulei.kddi@gmail.com