idnits 2.17.1 draft-cc-isis-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 (April 29, 2018) is 2188 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) == Outdated reference: A later version (-05) exists of draft-li-dynamic-flooding-04 == Outdated reference: A later version (-07) exists of draft-shen-isis-spine-leaf-ext-05 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group H. Chen 3 Internet-Draft D. Cheng 4 Intended status: Standards Track Huawei Technologies 5 Expires: October 31, 2018 M. Toy 6 Verizon 7 Y. Yang 8 IBM 9 April 29, 2018 11 ISIS Flooding Reduction 12 draft-cc-isis-flooding-reduction-01 14 Abstract 16 This document proposes an approach to flood ISIS link state protocol 17 data units on a topology that is a subgraph of the complete ISIS 18 topology per underline physical network, so that the amount of 19 flooding traffic in the network is greatly reduced, and it would 20 reduce convergence time with a more stable and optimized routing 21 environment. The approach can be applied to any network topology in 22 a single ISIS area. 24 Requirements Language 26 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 27 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 28 document are to be interpreted as described in RFC 2119 [RFC2119]. 30 Status of this Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on October 31, 2018. 47 Copyright Notice 48 Copyright (c) 2018 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 4 66 4. Extensions to ISIS . . . . . . . . . . . . . . . . . . . . . . 6 67 5. Flooding Behavior . . . . . . . . . . . . . . . . . . . . . . 7 68 5.1. Nodes Support Flooding Reduction . . . . . . . . . . . . . 7 69 5.1.1. Receiving an ISIS LSP . . . . . . . . . . . . . . . . 7 70 5.1.2. Originating an ISIS LSP . . . . . . . . . . . . . . . 8 71 5.1.3. An Exception Case . . . . . . . . . . . . . . . . . . 8 72 5.1.4. One More Note . . . . . . . . . . . . . . . . . . . . 9 73 5.2. Nodes Not Support Flooding Reduction . . . . . . . . . . . 9 74 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 75 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 76 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 77 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 78 9.1. Normative References . . . . . . . . . . . . . . . . . . . 10 79 9.2. Informative References . . . . . . . . . . . . . . . . . . 10 80 Appendix A. Algorithms to Build Flooding Topology . . . . . . . . 10 81 A.1. Algorithms to Build Tree without Considering Flag F . . . 10 82 A.2. Algorithms to Build Tree Considering Flag F . . . . . . . 12 83 A.3. Connecting Leaves . . . . . . . . . . . . . . . . . . . . 14 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 86 1. Introduction 88 For some networks such as dense Data Center (DC) networks, the 89 existing ISIS Link State PDU (LSP) flooding mechanism is not 90 efficient and may have some issues. The extra LSP flooding consumes 91 network bandwidth. Processing the extra LSP flooding, including 92 receiving, buffering and decoding the extra LSPs, wastes memory space 93 and processor time. This may cause scalability issues and affect the 94 network convergence negatively. 96 A flooding reduction method between spines and leaves is proposed in 97 [I-D.shen-isis-spine-leaf-ext]. The problem on flooding reduction 98 and an architectural solution are discussed in 99 [I-D.li-dynamic-flooding]. This document proposes an approach to 100 flood ISIS LSPs on a topology that is a subgraph of the entire ISIS 101 topology per underline physical network, so that the amount of 102 flooding traffic in the network is greatly reduced. The workload for 103 processing the extra LSP flooding is decreased significantly. This 104 would improve the scalability and speed up the network convergence, 105 stable and optimize the routing environment. 107 The approach proposed is applicable to any network topology in a 108 single ISIS area. The approach is backward compatible. 110 2. Problem Statement 112 ISIS, like other link-state routing protocols, deploys a so-called 113 reliable flooding mechanism, where a node must transmit a received or 114 self-originated LSP to all its ISIS interfaces (except the interface 115 where a LSP is received) in the defined context. While this 116 mechanism assures each LSP being distributed to every ISIS node in 117 the relevant routing area or domain, the side-effect is that the 118 mechanism often causes redundant LSPs in individual network segments 119 (e.g., on an ISIS point-to-point link or a broadcast subnet), which 120 in turn forces ISIS nodes to process identical LSPs more than once. 121 This results waste of ISIS link bandwidth and ISIS nodes' computing 122 resources, and the delay of ISIS topology convergence. 124 The problem explained above becomes more serious in ISIS networks 125 with large number of nodes and links, and in particular, higher 126 degree of interconnection (e.g., meshed topology, spine-leaf 127 topology, etc,). In some environment such as in data centers, the 128 drawback of the existing flooding mechanism has already caused 129 operational problems, including repeated and waves of flooding 130 storms, chock of computing resources, slow convergence, oscillating 131 topology changes, instability of routing environment. 133 One example is as shown in Figure 1 (a), where Node 1, Node 2 and 134 Node 3 are interconnected in a mesh. When Node 1 receives a new or 135 updated ISIS LSP on its interface I11, it by default would forward to 136 its interface Il2 and I13 towards Node 2 and Node 3, respectively, 137 after processing. Node 2 and Node 3 upon reception of the LSP and 138 after processing, would potentially flood the same LSP over their 139 respective interface I23 and I32 toward each other, which is 140 obviously not necessary and at the cost of link bandwidth as well as 141 both nodes' computing resource. 143 In example Figure 1 (b), Node 2 and Node 3 both connect to a LAN 144 where Node 4, Node 5 and Node 6 also connect to. When Node 1 145 receives a LSP as in (a) and floods it to Node 2 and Node 3 146 respectively, the two nodes would in turn both (instead of one) flood 147 to the LAN, which is unnecessary and at the cost of link bandwidth as 148 well as computing resource of all nodes connected to the LAN. 150 | | 151 |I11 |I11 152 +--o---+ +--o---+ 153 |Node 1| |Node 1| 154 +-o--o-+ +-o--o-+ 155 I12 / \ I13 / \ 156 / \ I12/ \I13 157 I21/ \I31 / \ 158 +----o-+ I32+-o----+ +----o-+ +-o----+ 159 |Node 2|------|Node 3| |Node 2| |Node 3| 160 +------+I23 +------+ +--o---+ +---o--+ 161 I2L| LAN |I3L 162 (a) -----o--------o-----o--o----- 163 I4L| I5L| I6L| 164 +---o--+ +--o---+ +--o---+ 165 |Node 4| |Node 5| |Node 6| 166 +------+ +------+ +------+ 168 (b) 170 Figure 1 172 3. Flooding Topology 174 It is a norm that an ISIS node sending a received LSP and self- 175 originated LSP to all its ISIS interfaces (except that where an LSP 176 is received), as the reliable-flooding mechanism requires, i.e., any 177 ISIS LSP would potentially traverses on each ISIS link in a given 178 ISIS network topology, sometimes both directions. As demonstrated in 179 Section 2, dissemination over the entire ISIS network topology has 180 drawbacks. 182 To change ISIS's aggressive flooding behavior, a flooding topology is 183 introduced. For a given ISIS network topology, a flooding topology 184 is a sub-graph or sub-network of the given network topology that has 185 the same reachability to every node as the given network topology. 186 Thus all the nodes in the given network topology MUST be in the 187 flooding topology. All the nodes MUST be inter-connected directly or 188 indirectly. As a result, ISIS flooding will in most cases occur only 189 on the flooding topology, that includes all ISIS nodes but a subset 190 of ISIS links. Note even the flooding topology is a sub-graph of the 191 original ISIS topology, any single LSP MUST still be disseminated in 192 the entire ISIS network. 194 There are many different flooding topologies for a given ISIS network 195 topology. A chain connecting all the nodes in the given network 196 topology is a flooding topology. A circle connecting all the nodes 197 is another flooding topology. A tree connecting all the nodes is a 198 flooding topology. In addition, the tree plus the connections 199 between some leaves of the tree and branch nodes of the tree is a 200 flooding topology. 202 There are many different ways to construct a flooding topology for a 203 given ISIS network topology. A few of them are listed below: 205 o One node in the network builds a flooding topology and floods the 206 flooding topology to all the other nodes in the network (This 207 seems not very good. Flooding the flooding topology may increase 208 the flooding.); 210 o Each node in the network automatically calculates a flooding 211 topology by using the same algorithm (No flooding for flooding 212 topology); 214 o Links on the flooding topology are configured statically. 216 The minimum requirement for a flooding topology is all ISIS nodes are 217 interconnected (directly or indirectly), but there is only one path 218 from any node to any other node. While this lean-and-mean type of 219 flooding topology degrades ISIS flooding traffic volume to the least, 220 it may introduce some delay of topology convergence in the network 221 with some network topologies. To compensate convergence efficiency, 222 additional ISIS links may be added as part of the flooding topology. 223 There is a trade-off between the density of the flooding topology and 224 the convergence efficiency. 226 Note that the flooding topology constructed by an ISIS node is 227 dynamic in nature, that means when the ISIS's base topology (the 228 entire topology graph) changes, the flooding topology (the sub-graph) 229 MUST be re-computed/re-constructed to ensure that any node that is 230 reachable on the base topology MUST also be reachable on the flooding 231 topology. 233 For reference purpose, some algorithms that allow ISIS nodes to 234 automatically compute flooding topology are elaborated in Appendix A. 235 However, this document does not attempt to standardize how a flooding 236 topology is established. 238 4. Extensions to ISIS 240 A 1-bit flag F is defined in an ISIS router capability TLV. Flag F 241 set to 1 indicates that the router supports ISIS LSP flood reduction 242 described in this document; and Flag F set to 0 indicates that the 243 router does not do so. 245 This flag is used for an ISIS node during the process of computing a 246 flooding topology. An ISIS node that advertises its LSP containing a 247 capability TLV with "F" bit set to 1 MUST always be included in the 248 flooding topology computed by other ISIS nodes; but in contrast, the 249 node with "F" bit set to zero may or may not be included in the 250 flooding topology by other nodes, depending on how other nodes 251 construct their flooding topology. 253 This flag can also be used for an ISIS node to trigger a decision 254 whether it wants to perform LSP flooding to its neighbor. 256 The format of an ISIS router capability TLV with flag F is shown 257 below. 259 0 1 2 3 260 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 261 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 262 | Type = 242 |Length(5 ~ 255)| Router ID | 263 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 264 | Router ID |Reserved |F|D|S| Optional | 265 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 266 | sub-TLVs ~ 267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 269 5. Flooding Behavior 271 5.1. Nodes Support Flooding Reduction 273 This section describes ISIS flooding behavior for ISIS nodes that 274 support flooding reduction described in this document. For these 275 nodes, they MUST set "F" bit to 1 in their LSPs (see Section 4). The 276 flooding behavior for these nodes differs from that as specified in 277 ISIS ([RFC1195]). Section 5.1.1 describes the flooding behavior when 278 an ISIS node receives an ISIS LSP from one of its interface, and 279 Section 5.1.2 describes the flooding behavior for LSP originated by 280 itself. 282 The revised flooding procedure MUST flood LSPs to every node in the 283 network in any case, as the standard ISIS flooding procedure does. 285 It assumes that the ISIS node of which the flooding behavior is 286 described below is on the flooding topology, i.e., the node and at 287 least one of its ISIS interface are on the flooding topology, where: 289 1. When the node has only one interface on the flooding topology, 290 the node is a leaf on the topology. 292 2. When the node has two interfaces on the flooding topology, the 293 node is a transit node on the topology. 295 3. A flooding topology with nodes having one or two interfaces on 296 the topology is a lean graph, i.e., there is only one path from 297 any node to any other node on the graph. For flooding 298 efficiency, there could be extra ISIS interfaces that are on the 299 flooding topology, i.e., a node may have more than two interfaces 300 that belong to the flooding topology. 302 5.1.1. Receiving an ISIS LSP 304 The flooding behavior when an ISIS node receives a newer ISIS LSP 305 that is not originated by itself from one of its ISIS interface is as 306 follows: 308 1. The LSP is received on a link that is on the flooding topology. 309 The LSP is flooded only to all the other interfaces that are on 310 the flooding topology. 312 2. The LSP is received on a link that is not on the flooding 313 topology. This situation can happen when a neighboring node on a 314 point-to-point link newly forms adjacency with the receiving 315 node, or is not currently on the flooding topology; it can happen 316 when the LSP sending neighbor does not support the ISIS flooding 317 reduction (i.e., with "F" bit set to zero); it can also happen as 318 the receiving link is a broadcast-type interface. The LSP is 319 flooded only to all other interfaces that are on the flooding 320 topology. 322 3. In both cases above, if there is any neighboring node that is 323 advertising its Router LSP with "F" bit set to zero (see 324 Section 4) but it is not on the flooding topology, the received 325 LSP MUST also be sent to this neighboring node. 327 In any case, the LSP must not be transmitted back to the receiving 328 interface. 330 Note before forwarding a received LSP, the ISIS node would do the 331 normal processing as usual. 333 5.1.2. Originating an ISIS LSP 335 The flooding behavior when an ISIS node originates an ISIS LSP is as 336 follows: 338 1. If it is a refresh LSP, i.e., there is no significant change 339 contained in the LSP comparing to the previous LSP, the LSP is 340 transmitted over links on the flooding topology. In addition, if 341 there is any neighboring node that is advertising its Router LSP 342 with "F" bit set to zero (see Section 4) but it is not on the 343 flooding topology, the LSP MUST also be sent to this neighboring 344 node. 346 2. Otherwise, the LSP is transmitted to all ISIS interfaces. 347 Choosing this action instead of limiting to links on flooding 348 topology would speed up the synchronization around the 349 advertising node's neighbors, which could then disseminate the 350 new LSP quickly. 352 5.1.3. An Exception Case 354 In Section 5.1.1 and Section 5.1.2, there are times when an ISIS node 355 sending out a LSP to an interface on the flooding topology detects a 356 critical interface or node failure. A critical interface is an 357 interface on the flooding topology and is the only connection among 358 some nodes on the flooding topology. When this interface goes down, 359 the flooding topology will be split. Note the flooding topology was 360 pre-computed/pre-constructed; but if at the time a critical interface 361 or a node goes down before a re-newed flooding topology can be 362 computed/constructed, the ISIS node MUST send out the LSP to all 363 interfaces (except where it is received from) as a traditional ISIS 364 node would do. This handling is also taking place if there are more 365 than one interfaces or nodes on the existing flooding topology fail, 366 i.e., if more than one interfaces or nodes on the flooding topology 367 fail, the ISIS node does traditional flooding before the flooding 368 topology is re-built. 370 5.1.4. One More Note 372 The destination address that is used when an ISIS node sends out a 373 LSP on an interface on its flooding topology follows the 374 specification in ISIS ([RFC1195]). This means on a local LAN, all 375 other ISIS nodes will receive the LSP. 377 5.2. Nodes Not Support Flooding Reduction 379 For ISIS nodes that do not support flooding reduction as described in 380 this document, they MUST set "F" bit to 0 in their Router LSP (see 381 Section 4); note this is also a default setting. These nodes may or 382 may not be on the flooding topology constructed by other nodes that 383 support flooding reduction in the same ISIS area, however that is not 384 a business these nodes need to concern. 386 The LSP flooding behavior of ISIS nodes that do not support reduction 387 as described in this document MUST follow that as specified in ISIS 388 ([RFC1195]). 390 6. Security Considerations 392 This document does not introduce any security issue. 394 7. IANA Considerations 396 This document has no request to IANA. 398 8. Acknowledgements 400 The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, 401 Stephane Litkowski and Alvaro Retana for their valuable suggestions 402 and comments on this draft. 404 9. References 405 9.1. Normative References 407 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 408 dual environments", RFC 1195, DOI 10.17487/RFC1195, 409 December 1990, . 411 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 412 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 413 RFC2119, March 1997, 414 . 416 9.2. Informative References 418 [I-D.li-dynamic-flooding] 419 Li, T., "Dynamic Flooding on Dense Graphs", 420 draft-li-dynamic-flooding-04 (work in progress), 421 March 2018. 423 [I-D.shen-isis-spine-leaf-ext] 424 Shen, N., Ginsberg, L., and S. Thyamagundalu, "IS-IS 425 Routing for Spine-Leaf Topology", 426 draft-shen-isis-spine-leaf-ext-05 (work in progress), 427 January 2018. 429 Appendix A. Algorithms to Build Flooding Topology 431 There are many algorithms to build a flooding topology. A simple and 432 efficient one is briefed below. 434 o Select a node R according to a rule such as the node with the 435 biggest/smallest node ID; 437 o Build a tree using R as root of the tree (details below); and then 439 o Connect k (k>=0) leaves to the tree to have a flooding topology 440 (details follow). 442 A.1. Algorithms to Build Tree without Considering Flag F 444 An algorithm for building a tree from node R as root starts with a 445 candidate queue Cq containing R and an empty flooding topology Ft: 447 1. Remove the first node A from Cq and add A into Ft 449 2. If Cq is empty, then return with Ft 450 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 451 and not in Ft and X1, X2, ..., Xn are in a special order. For 452 example, X1, X2, ..., Xn are ordered by the cost of the link 453 between A and Xi. The cost of the link between A and Xi is less 454 than the cost of the link between A and Xj (j = i + 1). If two 455 costs are the same, Xi's ID is less than Xj's ID. In another 456 example, X1, X2, ..., Xn are ordered by their IDs. If they are 457 not ordered, then make them in the order. 459 4. Add Xi (i = 1, 2, ..., n) into the end of Cq, goto step 1. 461 Another algorithm for building a tree from node R as root starts with 462 a candidate queue Cq containing R and an empty flooding topology Ft: 464 1. Remove the first node A from Cq and add A into Ft 466 2. If Cq is empty, then return with Ft 468 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 469 and not in Ft and X1, X2, ..., Xn are in a special order. For 470 example, X1, X2, ..., Xn are ordered by the cost of the link 471 between A and Xi. The cost of the link between A and Xi is less 472 than the cost of the link between A and Xj (j = i + 1). If two 473 costs are the same, Xi's ID is less than Xj's ID. In another 474 example, X1, X2, ..., Xn are ordered by their IDs. If they are 475 not ordered, then make them in the order. 477 4. Add Xi (i = 1, 2, ..., n) into the front of Cq and goto step 1. 479 A third algorithm for building a tree from node R as root starts with 480 a candidate list Cq containing R associated with cost 0 and an empty 481 flooding topology Ft: 483 1. Remove the first node A from Cq and add A into Ft 485 2. If all the nodes are on Ft, then return with Ft 487 3. Suppose that node A is associated with a cost Ca which is the 488 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 489 connected to node A and not in Ft and the cost of the link 490 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 491 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 492 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 493 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 494 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 496 4. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 497 ..., m) are the nodes in Cq, Cai is the cost associated with Ai, 498 and IDi is the ID of Ai. One order is that for any k = 1, 2, 499 ..., m-1, Cak < Caj (j = k+1) or Cak = Caj and IDk < IDj. Goto 500 step 1. 502 A.2. Algorithms to Build Tree Considering Flag F 504 An algorithm for building a tree from node R as root with 505 consideration of flag F starts with a candidate queue Cq containing R 506 associated with previous hop PH=0 and an empty flooding topology Ft: 508 1. Remove the first node A with its flag F set to one from the 509 candidate queue Cq if there is such a node A; otherwise (i.e., if 510 there is not such node A in Cq), then remove the first node A 511 from Cq. Add A into the flooding topology Ft. 513 2. If Cq is empty or all nodes are on Ft, then return with Ft 515 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 516 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 517 special order considering whether some of them with flag F = 1. 518 For example, X1, X2, ..., Xn are ordered by the cost of the link 519 between A and Xi. The cost of the link between A and Xi is less 520 than that of the link between A and Xj (j = i + 1). If two costs 521 are the same, Xi's ID is less than Xj's ID. The cost of a link 522 is redefined such that 1) the cost of a link between A and Xi 523 both with F = 1 is much less than the cost of any link between A 524 and Xk where Xk with F=0; 2) the real metric of a link between A 525 and Xi and the real metric of a link between A and Xk are used as 526 their costs for determining the order of Xi and Xk if they all 527 (i.e., A, Xi and Xk) with F = 1 or none of Xi and Xk with F = 1. 529 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 530 the end of the candidate queue Cq, and goto step 1. 532 Another algorithm for building a tree from node R as root with 533 consideration of flag F starts with a candidate queue Cq containing R 534 associated with previous hop PH=0 and an empty flooding topology Ft: 536 1. Remove the first node A with its flag F set to one from the 537 candidate queue Cq if there is such a node A; otherwise (i.e., if 538 there is not such node A in Cq), then remove the first node A 539 from Cq. Add A into the flooding topology Ft. 541 2. If Cq is empty or all nodes are on Ft, then return with Ft. 543 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 544 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 545 special order considering whether some of them with F = 1. For 546 example, X1, X2, ..., Xn are ordered by the cost of the link 547 between A and Xi. The cost of the link between A and Xi is less 548 than the cost of the link between A and Xj (j = i + 1). If two 549 costs are the same, Xi's ID is less than Xj's ID. The cost of a 550 link is redefined such that 1) the cost of a link between A and 551 Xi both with F = 1 is much less than the cost of any link between 552 A and Xk where Xk with F = 0; 2) the real metric of a link 553 between A and Xi and the real metric of a link between A and Xk 554 are used as their costs for determining the order of Xi and Xk if 555 they all (i.e., A, Xi and Xk) have F = 1 or none of Xi and Xk has 556 F = 1. 558 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 559 the front of the candidate queue Cq, and goto step 1. 561 A third algorithm for building a tree from node R as root with 562 consideration of flag F starts with a candidate list Cq containing R 563 associated with low order cost Lc=0, high order cost Hc=0 and 564 previous hop ID PH=0, and an empty flooding topology Ft: 566 1. Remove the first node A from Cq and add A into Ft. 568 2. If all the nodes are on Ft, then return with Ft 570 3. Suppose that node A is associated with a cost Ca which is the 571 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 572 connected to node A and not in Ft and the cost of the link 573 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 574 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 575 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 576 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 577 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 579 4. Suppose that node A is associated with a low order cost LCa which 580 is the low order cost from root R to node A and a high order cost 581 HCa which is the high order cost from R to A, node Xi (i = 1, 2, 582 ..., n) is connected to node A and not in the flooding topology 583 Ft and the real cost of the link between A and Xi is Ci (i=1, 2, 584 ..., n). Compute LCxi and HCxi: LCxi = LCa + Ci if both A and Xi 585 have flag F set to one, otherwise LCxi = LCa HCxi = HCa + Ci if A 586 or Xi does not have flag F set to one, otherwise HCxi = HCa If Xi 587 is not in Cq, then add Xi associated with LCxi, HCxi and PH = A 588 into Cq; If Xi associated with LCxi' and HCxi' and PHxi' is in 589 Cq, then If HCxi' > HCxi then replace Xi with HCxi', LCxi' and 590 PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise (i.e., 591 HCxi' == HCxi) if LCxi' > LCxi , then replace Xi with HCxi', 592 LCxi' and PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise 593 (i.e., HCxi' == HCxi and LCxi' == LCxi) if PHxi' > PH, then 594 replace Xi with HCxi', LCxi' and PHxi' by Xi with HCxi, LCxi and 595 PH=A in Cq. 597 5. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 598 ..., m) are the nodes in Cq, HCai and LCai are low order cost and 599 high order cost associated with Ai, and IDi is the ID of Ai. One 600 order is that for any k = 1, 2, ..., m-1, HCak < HCaj (j = k+1) 601 or HCak = HCaj and LCak < LCaj or HCak = HCaj and LCak = LCaj and 602 IDk < IDj. Goto step 1. 604 A.3. Connecting Leaves 606 Suppose that we have a flooding topology Ft built by one of the 607 algorithms described above. Ft is like a tree. We may connect k (k 608 >=0) leaves to the tree to have a enhanced flooding topology with 609 more connectivity. 611 Suppose that there are m (0 < m) leaves directly connected to a node 612 X on the flooding topology Ft. Select k (k <= m) leaves through 613 using a deterministic algorithm or rule. One algorithm or rule is to 614 select k leaves that have smaller or larger IDs (i.e., the IDs of 615 these k leaves are smaller/bigger than the IDs of the other leaves 616 directly connected to node X). Since every node has a unique ID, 617 selecting k leaves with smaller or larger IDs is deterministic. 619 If k = 1, the leaf selected has the smallest/largest node ID among 620 the IDs of all the leaves directly connected to node X. 622 For a selected leaf L directly connected to a node N in the flooding 623 topology Ft, select a connection/adjacency to another node from node 624 L in Ft through using a deterministic algorithm or rule. 626 Suppose that leaf node L is directly connected to nodes Ni (i = 627 1,2,...,s) in the flooding topology Ft via adjacencies and node Ni is 628 not node N, IDi is the ID of node Ni, and Hi (i = 1,2,...,s) is the 629 number of hops from node L to node Ni in the flooding topology Ft. 631 One Algorithm or rule is to select the connection to node Nj (1 <= j 632 <= s) such that Hj is the largest among H1, H2, ..., Hs. If there is 633 another node Na ( 1 <= a <= s) and Hj = Ha, then select the one with 634 smaller (or larger) node ID. That is that if Hj == Ha and IDj < IDa 635 then select the connection to Nj for selecting the one with smaller 636 node ID (or if Hj == Ha and IDj < IDa then select the connection to 637 Na for selecting the one with larger node ID). 639 Suppose that the number of connections in total between leaves 640 selected and the nodes in the flooding topology Ft to be added is 641 NLc. We may have a limit to NLc. 643 Authors' Addresses 645 Huaimo Chen 646 Huawei Technologies 648 Email: huaimo.chen@huawei.com 650 Dean Cheng 651 Huawei Technologies 653 Email: dean.cheng@huawei.com 655 Mehmet Toy 656 Verizon 657 USA 659 Email: mehmet.toy@verizon.com 661 Yi Yang 662 IBM 663 Cary, NC 664 United States of America 666 Email: yyietf@gmail.com