idnits 2.17.1 draft-cc-lsr-flooding-reduction-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- 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 (December 10, 2018) 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: 'RFC2328' is defined on line 1630, but no explicit reference was found in the text == Unused Reference: 'RFC5340' is defined on line 1638, but no explicit reference was found in the text == Unused Reference: 'I-D.li-dynamic-flooding' is defined on line 1649, but no explicit reference was found in the text == Unused Reference: 'I-D.shen-isis-spine-leaf-ext' is defined on line 1654, 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 (~~), 5 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: June 13, 2019 M. Toy 6 Verizon 7 Y. Yang 8 IBM 9 December 10, 2018 11 LS Flooding Reduction 12 draft-cc-lsr-flooding-reduction-00 14 Abstract 16 This document proposes an approach to flood link states on a topology 17 that is a subgraph of the complete topology per underline physical 18 network, so that the amount of flooding traffic in the network is 19 greatly reduced, and it would reduce convergence time with a more 20 stable and optimized routing environment. The approach can be 21 applied to any network topology in a single area. 23 Requirements Language 25 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 26 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 27 document are to be interpreted as described in RFC 2119 [RFC2119]. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at https://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on June 13, 2019. 46 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 (https://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. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Conventions Used in This Document . . . . . . . . . . . . . . 4 66 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 4 67 5. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 5 68 5.1. Construct Flooding Topology . . . . . . . . . . . . . . . 5 69 5.2. Backup for Flooding Topology Split . . . . . . . . . . . 7 70 6. Extensions to OSPF . . . . . . . . . . . . . . . . . . . . . 7 71 6.1. Extensions for Operations . . . . . . . . . . . . . . . . 8 72 6.2. Extensions for Centralized Mode . . . . . . . . . . . . . 9 73 6.2.1. Message for Flooding Topology . . . . . . . . . . . . 9 74 6.2.2. Encodings for Backup Paths . . . . . . . . . . . . . 16 75 6.2.3. Message for Incremental Changes . . . . . . . . . . . 24 76 6.2.4. Leaders Selection . . . . . . . . . . . . . . . . . . 25 77 7. Extensions to IS-IS . . . . . . . . . . . . . . . . . . . . . 27 78 7.1. Extensions for Operations . . . . . . . . . . . . . . . . 27 79 7.2. Extensions for Centralized Mode . . . . . . . . . . . . . 27 80 7.2.1. TLV for Flooding Topology . . . . . . . . . . . . . . 27 81 7.2.2. Encodings for Backup Paths . . . . . . . . . . . . . 28 82 7.2.3. TLVs for Incremental Changes . . . . . . . . . . . . 29 83 7.2.4. Leaders Selection . . . . . . . . . . . . . . . . . . 30 84 8. Flooding Behavior . . . . . . . . . . . . . . . . . . . . . . 30 85 8.1. Nodes Perform Flooding Reduction without Failure . . . . 30 86 8.1.1. Receiving an LS . . . . . . . . . . . . . . . . . . . 30 87 8.1.2. Originating an LS . . . . . . . . . . . . . . . . . . 31 88 8.1.3. Establishing Adjacencies . . . . . . . . . . . . . . 31 89 8.2. An Exception Case . . . . . . . . . . . . . . . . . . . . 32 90 8.2.1. Multiple Failures . . . . . . . . . . . . . . . . . . 32 91 8.2.2. Changes on Flooding Topology . . . . . . . . . . . . 33 92 9. Security Considerations . . . . . . . . . . . . . . . . . . . 34 93 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 34 94 10.1. OSPFv2 . . . . . . . . . . . . . . . . . . . . . . . . . 34 95 10.2. OSPFv3 . . . . . . . . . . . . . . . . . . . . . . . . . 35 96 10.3. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . 36 97 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 37 98 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 37 99 12.1. Normative References . . . . . . . . . . . . . . . . . . 37 100 12.2. Informative References . . . . . . . . . . . . . . . . . 37 101 Appendix A. Algorithms to Build Flooding Topology . . . . . . . 38 102 A.1. Algorithms to Build Tree without Considering Others . . . 38 103 A.2. Algorithms to Build Tree Considering Others . . . . . . . 39 104 A.3. Connecting Leaves . . . . . . . . . . . . . . . . . . . . 41 105 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 42 107 1. Introduction 109 For some networks such as dense Data Center (DC) networks, the 110 existing Link State (LS) flooding mechanism is not efficient and may 111 have some issues. The extra LS flooding consumes network bandwidth. 112 Processing the extra LS flooding, including receiving, buffering and 113 decoding the extra LSs, wastes memory space and processor time. This 114 may cause scalability issues and affect the network convergence 115 negatively. 117 This document proposes an approach to minimize the amount of flooding 118 traffic in the network. Thus the workload for processing the extra 119 LS flooding is decreased significantly. This would improve the 120 scalability, speed up the network convergence, stable and optimize 121 the routing environment. 123 This approach is also flexible. It has multiple modes for 124 computation of flooding topology. Users can select a mode they 125 prefer, and smoothly switch from one mode to another. The approach 126 is applicable to any network topology in a single area. It is 127 backward compatible. 129 2. Terminology 131 Flooding Topology: 132 A sub-graph or sub-network of a given (physical) network topology 133 that has the same reachability to every node as the given network 134 topology, through which link states are flooded. 136 critical link or interface on a flooding topology: 137 A only link or interface among some nodes on the flooding 138 topology. When this link or interface goes down, the flooding 139 topology will be split. 141 critical node on a flooding topology: 143 A only node connecting some nodes on the flooding topology. When 144 this node goes down, the flooding topology will be split. 146 backup path: 147 A path or a sequence of links, when a critical link or node goes 148 down, providing a connection to connect two parts of a split 149 flooding topology. When a critical node goes down, the flooding 150 topology may be split into more than two parts. In this case, 151 two or more backup paths are needed to connect all the split 152 parts into one. 154 Remaining Flooding Topology: 155 A topology from a flooding topology by removing the failed links 156 and nodes from the flooding topology. 158 LSA: 159 A Link State Advertisement in OSPF. 161 LSP: 162 A Link State Protocol Data Unit (PDU) in IS-IS. 164 LS: 165 A Link Sate, which is an LSA or LSP. 167 3. Conventions Used in This Document 169 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 170 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 171 document are to be interpreted as described in [RFC2119]. 173 4. Problem Statement 175 OSPF and IS-IS deploy a so-called reliable flooding mechanism, where 176 a node must transmit a received or self-originated LS to all its 177 interfaces (except the interface where an LS is received). While 178 this mechanism assures each LS being distributed to every node in an 179 area or domain, the side-effect is that the mechanism often causes 180 redundant LS, which in turn forces nodes to process identical LS more 181 than once. This results in the waste of link bandwidth and nodes' 182 computing resources, and the delay of topology convergence. 184 This becomes more serious in networks with large number of nodes and 185 links, and in particular, higher degree of interconnection (e.g., 186 meshed topology, spine-leaf topology, etc.). In some environments 187 such as in data centers, the drawback of the existing flooding 188 mechanism has already caused operational issues, including repeated 189 and waves of flooding storms, chock of computing resources, slow 190 convergence, oscillating topology changes, instability of routing 191 environment. 193 One example is as shown in Figure 1, where Node 1, Node 2 and Node 3 194 are interconnected in a mesh. When Node 1 receives a new or updated 195 LS on its interface I11, it by default would forward the LS to its 196 interface Il2 and I13 towards Node 2 and Node 3, respectively, after 197 processing. Node 2 and Node 3 upon reception of the LS and after 198 processing, would potentially flood the same LS over their respective 199 interface I23 and I32 toward each other, which is obviously not 200 necessary and at the cost of link bandwidth as well as both nodes' 201 computing resource. 203 | 204 |I11 205 +--o---+ 206 |Node 1| 207 +-o--o-+ 208 I12 / \ I13 209 / \ 210 I21/ \I31 211 +----o-+ I32+-o----+ 212 |Node 2|------|Node 3| 213 +------+I23 +------+ 215 Figure 1 217 5. Flooding Topology 219 For a given network topology, a flooding topology is a sub-graph or 220 sub-network of the given network topology that has the same 221 reachability to every node as the given network topology. Thus all 222 the nodes in the given network topology MUST be in the flooding 223 topology. All the nodes MUST be inter-connected directly or 224 indirectly. As a result, LS flooding will in most cases occur only 225 on the flooding topology, that includes all nodes but a subset of 226 links. Note even though the flooding topology is a sub-graph of the 227 original topology, any single LS MUST still be disseminated in the 228 entire network. 230 5.1. Construct Flooding Topology 232 Many different flooding topologies can be constructed for a given 233 network topology. A chain connecting all the nodes in the given 234 network topology is a flooding topology. A circle connecting all the 235 nodes is another flooding topology. A tree connecting all the nodes 236 is a flooding topology. In addition, the tree plus the connections 237 between some leaves of the tree and branch nodes of the tree is a 238 flooding topology. 240 The following parameters need to be considered for constructing a 241 flooding topology: 243 o Number of links: The number of links on the flooding topology is a 244 key factor for reducing the amount of LS flooding. In general, 245 the smaller the number of links, the less the amount of LS 246 flooding. 248 o Diameter: The shortest distance between the two most distant nodes 249 on the flooding topology is a key factor for reducing the network 250 convergence time. The smaller the diameter, the less the 251 convergence time. 253 o Redundancy: The redundancy of the flooding topology means a 254 tolerance to the failures of some links and nodes on the flooding 255 topology. If the flooding topology is split by some failures, it 256 is not tolerant to these failures. In general, the larger the 257 number of links on the flooding topology is, the more tolerant the 258 flooding topology to failures. 260 There are many different ways to construct a flooding topology for a 261 given network topology. A few of them are listed below: 263 o Central Mode: One node in the network builds a flooding topology 264 and floods the flooding topology to all the other nodes in the 265 network (This seems not good. Flooding the flooding topology may 266 increase the flooding. The amount of traffic for flooding the 267 flooding topology should be minimized.); 269 o Distributed Mode: Each node in the network automatically 270 calculates a flooding topology by using the same algorithm (No 271 flooding for flooding topology); 273 o Static Mode: Links on the flooding topology are configured 274 statically. 276 Note that the flooding topology constructed by a node is dynamic in 277 nature, that means when the base topology (the entire topology graph) 278 changes, the flooding topology (the sub-graph) MUST be re-computed/ 279 re-constructed to ensure that any node that is reachable on the base 280 topology MUST also be reachable on the flooding topology. 282 For reference purpose, some algorithms that allow nodes to 283 automatically compute flooding topology are elaborated in Appendix A. 285 However, this document does not attempt to standardize how a flooding 286 topology is established. 288 5.2. Backup for Flooding Topology Split 290 It is hard to construct a flooding topology that reduces the amount 291 of LS flooding greatly and is tolerant to multiple failures. To get 292 around this, we can compute and use backup paths for a critical link 293 and node on the flooding topology. Using backup paths may also speed 294 up convergence when the link and node fail. 296 When a critical link on the flooding topology fails, the flooding 297 topology without the critical link (i.e., the remaining flooding 298 topology) is split into two parts. A backup path for the critical 299 link connects the two parts into one. Through the backup path and 300 the remaining flooding topology, an LS can be flooded to every node 301 in the network. The combination of the backup path and the flooding 302 topology is tolerant to the failure of the critical link. 304 When a critical node on the flooding topology goes down, the flooding 305 topology without the critical node and the links attached to the node 306 (i.e., the remaining flooding topology) is split into two or more 307 parts. One or more backup paths for the critical node connects the 308 split parts into one. Through the backup paths and the remaining 309 flooding topology, an LS can be flooded to every live node in the 310 network. The combination of the backup paths and the flooding 311 topology is tolerant to the failure of the critical node. 313 In addition to the backup paths for a critical link and node, backup 314 paths for every non critical link and node on the flooding topology 315 can be computed. When the failures of multiple links and nodes on 316 the flooding topology happen, through the remaining flooding topology 317 and the backup paths for these links and nodes, an LS can be flooded 318 to every live node in the network. The combination of the backup 319 paths and the flooding topology is tolerant to the failures of these 320 links and nodes. If there are other failures that break the backup 321 paths, an LS can be flooded to every live node by the traditional 322 flooding procedure. 324 In a centralized mode, the leader computes the backup paths and 325 floods them to all the other nodes. In a distributed mode, every 326 node computes the backup paths. 328 6. Extensions to OSPF 330 The extensions to OSPF comprises two parts: one part is for 331 operations on flooding reduction, the other is specially for 332 centralized mode flooding reduction. 334 6.1. Extensions for Operations 336 A new TLV is defined in OSPF RI LSA [RFC7770]. It contains 337 instructions about flooding reduction, which is called Flooding 338 Reduction Instruction TLV or Instruction TLV for short. This TLV is 339 originated from only one node at any time. 341 The format of a Flooding Reduction Instruction TLV is as follows. 343 0 1 2 3 344 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 345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 346 | INST-TLV-Type (TBD1) | TLV-Length | 347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 348 | OP | MOD | Algorithm | Reserved (MUST be zero) | NL | 349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 350 ~ sub TLVs (optional) ~ 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 353 Flooding Reduction Instruction TLV 355 A OP field of three bits is defined in the TLV. It may have a value 356 of the followings. 358 o 0x001 (R): Perform flooding Reduction, which instructs the nodes 359 in a network to perform flooding reduction. 361 o 0x010 (N): Roll back to Normal flooding, which instructs the nodes 362 in a network to roll back to perform normal flooding. 364 When any of the other values is received, it is ignored. 366 A MOD field of three bits is defined in the TLV and may have a value 367 of the followings. 369 o 0x001 (C): Central Mode, which instructs 1) the nodes in a network 370 to select leaders (primary/designated leader, secondary/backup 371 leader, and so on); 2) the leaders in a network to compute a 372 flooding topology and the primary leader to flood the flooding 373 topology to all the other nodes in the network; 3) every node in 374 the network to receive and use the flooding topology originated by 375 the primary leader. 377 o 0x010 (D): Distributed Mode, which instructs every node in a 378 network to compute and use its own flooding topology. 380 o 0x011 (S): Static Mode, which instructs every node in a network to 381 use the flooding topology statically configured on the node. 383 When any of the other values is received, it is ignored. 385 An Algorithm field of eight bits is defined in the TLV to instruct 386 the leader node in central mode or every node in distributed mode to 387 use the algorithm indicated in this field for computing a flooding 388 topology. 390 A NL field of three bits is defined in the TLV, which indicates the 391 number of leaders to be selected when Central Mode is used. NL set 392 to 2 means two leaders (a designated/primary leader and a backup/ 393 secondary leader) to be selected for an area, and NL set to 3 means 394 three leaders to be selected. When Central Mode is not used, The NL 395 field is not valid. 397 Some optional sub TLVs may be defined in the future, but none is 398 defined now. 400 6.2. Extensions for Centralized Mode 402 6.2.1. Message for Flooding Topology 404 A flooding topology can be represented by the links in the flooding 405 topology. For the links between a local node and a number of its 406 adjacent (or remote) nodes, we can encode the local node in a way, 407 and encode its adjacent nodes in the same way or another way. After 408 all the links in the flooding topology are encoded, the encoded links 409 can be flooded to every node in the network. After receiving the 410 encoded links, every node decodes the links and creates and/or 411 updates the flooding topology. 413 For every node in an area, we may use an index to represent it. 414 Every node in an area may order the nodes in a rule, which generates 415 the same sequence of the nodes on every node in the area. The 416 sequence of nodes have the index 0, 1, 2, and so on respectively. 417 For example, every node orders the nodes by their router IDs in 418 ascending order. 420 6.2.1.1. Links Encoding 422 A local node can be encoded in two parts: encoded node index size 423 indication (ENSI) and compact node index (CNI). ENSI value plus a 424 number (e.g., 9) gives the size of compact node index. For example, 425 ENSI = 0 indicates that the size of CNIs is 9 bits. In the figure 426 below, Local node LN1 is encoded as ENSI=0 using 3 bits and CNI=LN1's 427 Index using 9 bits. LN1 is encoded in 12 bits in total. 429 0 1 2 3 4 5 6 7 8 430 +-+-+-+-+-+-+-+-+-+ 431 |0 0 0| ENSI (3 bits) [9 bits CNI] 432 +-+-+-+-+-+-+-+-+-+ 433 | LN1 Index Value | CNI (9 bits) 434 +-+-+-+-+-+-+-+-+-+ 436 An Example of Local Node Encoding 438 The adjacent nodes can be encoded in two parts: Number of Nodes (NN) 439 and compact node indexes (CNIs). The size of CNIs is the same as the 440 local node. For example, three adjacent nodes RN1, RN2 and RN3 are 441 encoded below in 30 bits (i.e., 3.75 bytes). 443 0 1 2 3 4 5 6 7 8 444 +-+-+-+-+-+-+-+-+-+ 445 |0 1 1| NN (3 bits) [3 adjacent nodes] 446 +-+-+-+-+-+-+-+-+-+ 447 | RN1's Index | CNI (9 bits) for RN1 448 +-+-+-+-+-+-+-+-+-+ 449 | RN2's Index | CNI (9 bits) for RN2 450 +-+-+-+-+-+-+-+-+-+ 451 | RN3's Index | CNI (9 bits) for RN3 452 +-+-+-+-+-+-+-+-+-+ 454 An Example of Adjacent Nodes Encoding 456 The links between a local node and a number of its adjacent (or 457 remote) nodes can be encoded as the local node followed by the 458 adjacent nodes. For example, three links between local node LN1 and 459 its three adjacent nodes RN1, RN2 and RN3 are encoded below in 42 460 bits (i.e., 5.25 bytes). 462 0 1 2 3 4 5 6 7 8 463 +-+-+-+-+-+-+-+-+-+ _ 464 |0 0 0| ENSI (3 bits) [9 bits CNI] | 465 +-+-+-+-+-+-+-+-+-+ } Encoding for 466 | LN1 Index Value | CNI (9 bits) for LN1 _| Local Node LN1 467 +-+-+-+-+-+-+-+-+-+ _ 468 |0 1 1| NN (3 bits) [3 nodes] | 469 +-+-+-+-+-+-+-+-+-+ | Encoding for 470 | RN1's Index | CNI (9 bits) for RN1 | 3 adjacent nodes 471 +-+-+-+-+-+-+-+-+-+ } RN1, RN2, RN3 472 | RN2's Index | CNI (9 bits) for RN2 | of LN1 473 +-+-+-+-+-+-+-+-+-+ | 474 | RN3's Index | CNI (9 bits) for RN3 _| 475 +-+-+-+-+-+-+-+-+-+ 477 An Example of Links Encoding 479 For a flooding topology computed by a leader of an area, it may be 480 represented by all the links on the flooding topology. A Type- 481 Length-Value (TLV) of the following format for the links encodings 482 can be included in an LSA to represent the flooding topology (FT) and 483 flood the FT to every node in the area. 485 0 1 2 3 486 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 487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 488 | FTLK-TLV-Type (TBD2) | TLV-Length | 489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 490 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 491 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 492 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 494 : : 495 : : 496 Flooding Topology Links TLV 498 Note that a link between a local node LN and its adjacent node RN can 499 be encoded once and as a bi-directional link. That is that if it is 500 encoded in a Links Encoding from LN to RN, then the link from RN to 501 LN is implied or assumed. 503 For OSPFv2, an Opaque LSA of a new opaque type (TBD3) containing a 504 Flooding Topology Links TLV is used to flood the flooding topology 505 from the leader of an area to all the other nodes in the area. 507 0 1 2 3 508 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 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 510 | LS age | Options | LS Type = 10 | 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 | FT-Type(TBD3) | Instance ID | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 | Advertising Router | 515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 516 | LS Sequence Number | 517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 518 | LS checksum | Length | 519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 520 ~ Flooding Topology Links TLV ~ 521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 523 OSPFv2: Flooding Topology Opaque LSA 525 For OSPFv3, an area scope LSA of a new LSA function code (TBD4) 526 containing a Flooding Topology Links TLV is used to flood the 527 flooding topology from the leader of an area to all the other nodes 528 in the area. 530 0 1 2 3 531 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 532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 533 | LS age |1|0|1| FT-LSA (TBD4) | 534 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 535 | Link State ID | 536 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 537 | Advertising Router | 538 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 539 | LS Sequence Number | 540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 | LS checksum | Length | 542 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 543 ~ Flooding Topology Links TLV ~ 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 OSPFv3: Flooding Topology LSA 548 The U-bit is set to 1, and the scope is set to 01 for area-scoping. 550 6.2.1.2. Block Encoding 552 Block encoding uses a single structure to encode a block (or part) of 553 topology, which can be a block of links in a flooding topology. It 554 can also be all the links in the flooding topology. It starts with a 555 local node LN and its adjacent (or remote) nodes RNi (i = 1, 2, ..., 556 n), and can be considered as an extension to the links encoding. 558 The encoding of links between a local node and its adjacent nodes 559 described in Section 6.2.1.1 is extended to include the links 560 attached to the adjacent nodes. 562 The encoding for the adjacent nodes is extended to include Extending 563 Flags (E Flags for short) between the NN (Number of Nodes) field and 564 the CNIs (Compact Node Indexes) for the adjacent nodes. The length 565 of the E Flags field is NN bits. The following is an example 566 encoding of the adjacent nodes with E Flags of 3 bits, which is the 567 value of the NN (the number of adjacent nodes). 569 0 1 2 3 4 5 6 7 8 570 +-+-+-+-+-+-+-+-+-+ 571 |0 1 1| NN (3 bits) [3 adjacent nodes] 572 +-+-+-+ 573 |1 0 1| E Flags [NN=3 bits] 574 +-+-+-+-+-+-+-+-+-+ 575 | RN1's Index | CNI (9 bits) for RN1 576 +-+-+-+-+-+-+-+-+-+ 577 | RN2's Index | CNI (9 bits) for RN2 578 +-+-+-+-+-+-+-+-+-+ 579 | RN3's Index | CNI (9 bits) for RN3 580 +-+-+-+-+-+-+-+-+-+ 582 An Example of Adjacent Nodes with E Flags Encoding 584 There is a bit flag (called E flag) in the E Flags field for each 585 adjacent node. The first bit (i.e., the most significant bit) in the 586 E Flags field is for the first adjacent node (e.g., RN1), the second 587 bit is for the second adjacent node (e.g., RN2), and so on. The E 588 flag for an adjacent node RNi set to one indicates that the links 589 attached to the adjacent node RNi are included below. The E flag for 590 an adjacent node RNi set to zero means that no links attached to the 591 adjacent node RNi are included below. 593 The links attached to the adjacent node RNi are represented by the 594 RNi as a local node and the adjacent nodes of RNi. The encoding for 595 the adjacent nodes of RNi is the same as that for the adjacent nodes 596 of a local node. It consists of an NN field of 3 bits, E Flags field 597 of NN bits, and CNIs for the adjacent nodes of RNi. 599 The following is an example of a block encoding for a block (or part) 600 of flooding topology below. 602 o LN1 603 / | \ 604 / \ 605 / | \ 606 o RN1 o RN2 o RN3 607 / / \ 608 / / \ 609 / / \ 610 o RN11 o RN31 o RN32 612 An Example Block of Flooding Topology 614 It represents 6 links: 3 links between local node LN1 and its 3 615 adjacent nodes RN1, RN2 and RN3; 1 link between RN1 as a local node 616 and its 1 adjacent node RN11; and 2 links between RN3 as a local node 617 and its 2 adjacent nodes RN31 and RN32. 619 It starts with the encoding of the links between local node LN1 and 3 620 adjacent nodes RN1, RN2 and RN3 of the local node LN1. The encoding 621 for the local node LN1 is the same as that for a local node described 622 in Section 6.2.1.1. The encoding for 3 adjacent nodes RN1, RN2 and 623 RN3 of local node LN1 comprises an NN field of 3 bits with value of 624 3, E Flags field of NN = 3 bits, and the indexes of adjacent nodes 625 RN1, RN2 and RN3. 627 0 1 2 3 4 5 6 7 8 628 +-+-+-+-+-+-+-+-+-+ _ 629 |0 0 0| ENSI (3 bits) [9 bits CNI] | 630 +-+-+-+-+-+-+-+-+-+ } Encoding for 631 | LN1 Index Value | CNI (9 bits) _| Local Node LN1 632 +-+-+-+-+-+-+-+-+-+ _ 633 |0 1 1| NN(3 bits)[3 adjacent nodes]| 634 +-+-+-+ | 635 |1 0 1| E Flags [NN=3 bits] | Encoding for 636 +-+-+-+-+-+-+-+-+-+ | 3 adjacent nodes 637 | RN1's Index | CNI (9 bits) for RN1 } (RN1, RN2, RN3) 638 +-+-+-+-+-+-+-+-+-+ | of LN1 639 | RN2's Index | CNI (9 bits) for RN2 | 640 +-+-+-+-+-+-+-+-+-+ | 641 | RN3's Index | CNI (9 bits) for RN3 _| 642 +-+-+-+-+-+-+-+-+-+ _ 643 |0 0 1| NN (3 bits)[1 adjacent node]| 644 +-+-+-+ | Encoding for 645 |0| E Flags [NN=1 bit] } 1 adjacent node 646 +-+-+-+-+-+-+-+-+-+ | (RN11) 647 | RN11's Index | CNI (9 bits) for RN11 _| of RN1 648 +-+-+-+-+-+-+-+-+-+ _ 649 |0 1 0| NN(3 bits)[2 adjacent nodes]| 650 +-+-+-+ | 651 |0 0| E Flags [NN=2 bits] | Encoding for 652 +-+-+-+-+-+-+-+-+-+ } 2 adjacent nodes 653 | RN31's Index | CNI (9 bits) for RN31 | (RN31, RN32) 654 +-+-+-+-+-+-+-+-+-+ | of RN3 as a 655 | RN32's Index | CNI (9 bits) for RN32 | local node 656 +-+-+-+-+-+-+-+-+-+ _| 658 An Example of Block Encoding 660 The first E flag in the encoding for adjacent nodes RN1, RN2 and RN3 661 is set to one, which indicates that the links between the first 662 adjacent node RN1 as a local node and its adjacent nodes are included 663 below. In this example, 1 link between RN1 and its adjacent node 664 RN11 is represented by the encoding for the adjacent node RN11 of RN1 665 as a local node. The encoding for 1 adjacent node RN11 consists of 666 an NN field of 3 bits with value of 1, E Flags field of NN = 1 bits, 667 and the index of adjacent node RN11. The size of the index of RN11 668 is the same as that of local node LN1 indicated by the ENSI in the 669 encoding for local node LN1. 671 The second E flag in the encoding for adjacent nodes RN1, RN2 and RN3 672 is set to zero, which indicates that no links between the second 673 adjacent node RN2 as a local node and its adjacent nodes are included 674 below. 676 The third E flag in the encoding for adjacent nodes RN1, RN2 and RN3 677 is set to one, which indicates that the links between the third 678 adjacent node RN3 as a local node and its adjacent nodes are included 679 below. In this example, 2 links between RN3 and its 2 adjacent nodes 680 RN31 and RN32 are represented by the encoding for the adjacent nodes 681 RN31 and RN32 of RN3 as a local node. The encoding for 2 adjacent 682 nodes RN31 and RN32 consists of an NN field of 3 bits with value of 683 2, E Flags field of NN = 2 bits, and the indexes of adjacent nodes 684 RN31 and RN32. The size of the index of RN31 and RN32 is the same as 685 that of local node LN1 indicated by the ENSI in the encoding for 686 local node LN1. 688 The block encoding may be used in the place of the links encoding in 689 Section 6.2.1.1 for more efficiency. That is that it may be used in 690 a Flooding Topology Links TLV. Alternatively, a new TLV, which is 691 similar to the Flooding Topology Links TLV, may be defined to contain 692 a number of block encodings. 694 6.2.2. Encodings for Backup Paths 696 When the leader of an area computes a flooding topology, it may 697 compute a backup path or multiple backup paths for a critical link on 698 the flooding topology. When the critical link fails, a link state 699 can be distributed to every node in the area through one backup path 700 and other links on the flooding topology. In addition, it may 701 compute a backup path or multiple backup paths for a node. When the 702 node fails, a link state can be distributed to the other nodes in the 703 area through the backup paths and the links on the flooding topology. 705 This section describes two encodings for backup paths: separated 706 encoding and integrated one. In the former, backup paths are encoded 707 in a new message, where the message for the flooding topology 708 described in the previous section is required; In the latter, backup 709 paths are integrated into the flooding topology links encoding, where 710 one message contains the flooding topology and the backup paths. 712 6.2.2.1. Message for Backup Paths 714 Backup paths for a node (such as Node1) may be represented by the 715 node index encoding and node backup paths encoding. The former is 716 similar to local node index encoding. The latter has the following 717 format. It comprises a K flag (Key/Critical node flag) of 1 bit, a 3 718 bits NNBP field (number of node backup paths), and each of the backup 719 paths encoding, which consists of the path length PLEN of 4 bits 720 indicating the length of the path (i.e., the number of nodes), and 721 the encoding of the sequence of nodes along the path such as 722 encodings for nodes PN1, ..., PNn. The encoding of every node may 723 use the encoding of a local node, which comprises encoded node index 724 size indication (ENSI) and compact node index (CNI). 726 0 1 2 3 4 5 6 7 8 727 +-+-+-+-+-+-+-+-+ 728 |K| 1 bit (K=1: Key/Critical Node, K=0: Normal Node) 729 +-+-+-+ _ 730 |NNBP | 3 bits (number of node backup paths) | 731 +-+-+-+-+ _ | 732 |PLEN | 4 bits (backup path len) | | 733 +-+-+-+-+-+-+-+-+ | | Backup 734 | PN1 Encoding | Variable bits | One } paths 735 +-+-+-+-+-+-+-+-+ } backup path | for Node 736 ~ ~ | for Node | 737 +-+-+-+-+-+-+-+-+ | | 738 | PNn Encoding | Variable bits _| | 739 +-+-+-+-+-+-+-+-+ | 740 // // _| 742 An Example of Node Backup Paths Encoding 744 Another encoding of the sequence of nodes along the path uses one 745 encoded node index size indication (ENSI) for all the nodes in the 746 path. Thus we have the following Node Backup Paths Encoding. 748 0 1 2 3 4 5 6 7 8 749 +-+-+-+-+-+-+-+-+ 750 |K| 1 bit (K=1: Key/Critical Node, K=0: Normal Node) 751 +-+-+-+ _ 752 |NNBP | 3 bits (number of node backup paths) | 753 +-+-+-+-+ _ | 754 |PLEN | 4 bits (backup path len) | | 755 +-+-+-+-+ | | 756 |ENSI | 3 bits(Ix Bits Indication)| | Backup 757 +-+-+-+-+-+-+-+-+ | One } paths 758 | PN1 Index | #Bits indicated by ENSI } backup path | for Node 759 +-+-+-+-+-+-+-+-+ | for Node | 760 ~ ~ | | 761 +-+-+-+-+-+-+-+-+ | | 762 | PNn Index | #Bits indicated by ENSI _| | 763 +-+-+-+-+-+-+-+-+ | 764 // // _| 766 Another Example of Node Backup Paths Encoding 768 A new TLV called Node Backup Paths TLV is defined below. It may 769 include multiple nodes and their backup paths. Each node is 770 represented by its index encoding, which is followed by its node 771 backup paths encoding. 773 0 1 2 3 774 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 775 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 776 | NBP-TLV-Type (TBD5) | TLV-Length | 777 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 778 |Node1 Index Enc| Variable bits 779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 780 : Node1 backup paths encoding : 781 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 782 |Node2 Index Enc| Variable bits 783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 784 : Node2 backup paths encoding : 785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 786 // // 787 Node Backup Paths TLV 789 The encoding for backup paths for a link (such as Link1) on the 790 flooding topology consists of the link encoding such as Link1 Index 791 Encoding and the link backup paths encoding. The former is similar 792 to local node encoding. It contains encoded link index size 793 indication (ELSI) and compact link index (CLI). The latter has the 794 following format. It comprises a C flag (Critical link flag) of 1 795 bit, a 2 bits NLB field (number of link backup paths), and each of 796 the backup paths encoding, which consists of the path length PLEN of 797 3 bits indicating the length of the path (i.e., the number of nodes), 798 and the encoding of the sequence of nodes along the path such as 799 encodings for nodes PN1, ..., PNm. Note that two ends of a link 800 (i.e., the local node and the adjacent/remote node of the link) are 801 not needed in the path. The encoding of every node may use the 802 encoding of a local node, which comprises encoded node index size 803 indication (ENSI) and compact node index (CNI). 805 0 1 2 3 4 5 6 7 8 806 +-+-+-+-+-+-+-+-+ 807 |C| 1 bit (C=1: Critical Link, C=0: Normal Link) 808 +-+-+ _ 809 |NLB| 2 bits (number of link backup paths) | 810 +-+-+-+ _ | 811 |PLEN | 3 bits (backup path len) | | 812 +-+-+-+-+-+-+-+-+ | | Backup 813 | PN1 Encoding | Variable bits | One } paths 814 +-+-+-+-+-+-+-+-+ } backup path | for Link 815 ~ ~ | for Link | 816 +-+-+-+-+-+-+-+-+ | | 817 | PNm Encoding | Variable bits _| | 818 +-+-+-+-+-+-+-+-+ | 819 // // _| 821 An Example of Link Backup Paths Encoding 823 Another encoding of the sequence of nodes along the path uses one 824 encoded node index size indication (ENSI) for all the nodes in the 825 path. Thus we have the following Link Backup Paths Encoding. 827 0 1 2 3 4 5 6 7 8 828 +-+-+-+-+-+-+-+-+ 829 |C| 1 bit (C=1: Critical Link, C=0: Normal Link) 830 +-+-+ _ 831 |NLB| 2 bits (number of link backup paths) | 832 +-+-+-+ _ | 833 |PLEN | 3 bits (backup path len) | | 834 +-+-+-+ | | 835 |ENSI | 3 bits(Ix Bits Indication)| | Backup 836 +-+-+-+-+-+-+-+-+ | One } paths 837 | PN1 Index | #Bits indicated by ENSI } backup path | for Link 838 +-+-+-+-+-+-+-+-+ | for Link | 839 ~ ~ | | 840 +-+-+-+-+-+-+-+-+ | | 841 | PNm Index | #Bits indicated by ENSI _| | 842 +-+-+-+-+-+-+-+-+ | 843 // // _| 845 Another Example of Link Backup Paths Encoding 847 A new TLV called Link Backup Paths TLV is defined below. It may 848 include multiple links and their backup paths. Each link is 849 represented by its index encoding, which is followed by its link 850 backup paths encoding. 852 0 1 2 3 853 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 854 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 855 | LBP-TLV-Type (TBD6) | TLV-Length | 856 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 857 |Link1 Index Enc| Variable bits 858 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 859 : Link1 backup paths encoding : 860 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 861 |Link2 Index Enc| Variable bits 862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 863 : Link2 backup paths encoding : 864 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 865 // // 866 Link Backup Paths TLV 868 For OSPFv2, an Opaque LSA of a new opaque type (TBD7), containing 869 node backup paths TLVs and link backup paths TLVs, is used to flood 870 the backup paths from the leader of an area to all the other nodes in 871 the area. 873 0 1 2 3 874 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 875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 876 | LS age | Options | LS Type = 10 | 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 878 | BP-Type(TBD7) | Instance ID | 879 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 880 | Advertising Router | 881 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 882 | LS Sequence Number | 883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 884 | LS checksum | Length | 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 ~ Link Backup Paths TLVs ~ 887 ~ Node Backup Paths TLVs ~ 888 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 890 OSPFv2: Backup Paths Opaque LSA 892 For OSPFv3, an area scope LSA of a new LSA function code (TBD8), 893 containing node backup paths TLVs and link backup paths TLVs, is used 894 to flood the backup paths from the leader of an area to all the other 895 nodes in the area. 897 0 1 2 3 898 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 899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 900 | LS age |1|0|1| BP-LSA (TBD8) | 901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 902 | Link State ID | 903 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 904 | Advertising Router | 905 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 906 | LS Sequence Number | 907 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 908 | LS checksum | Length | 909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 910 ~ Link Backup Paths TLVs ~ 911 ~ Node Backup Paths TLVs ~ 912 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 914 OSPFv3: Backup Paths LSA 916 The U-bit is set to 1, and the scope is set to 01 for area-scoping. 918 6.2.2.2. Backup Paths in Links TLV 920 A local node and its backup paths can be encoded in the following 921 format. It is the local node (such as local node LN1) encoding 922 followed by the local node backup paths encoding, which is the same 923 as the node backup paths encoding described in Section 6.2.2.1. 925 0 1 2 3 4 5 6 7 8 926 +-+-+-+-+-+-+-+-+-+ _ 927 |ENSI | 3 bits(#bits indication) | 928 +-+-+-+-+-+-+-+-+-+ } Local Node LN1 929 | LN1 Index Value | #bits indicated by ENSI _| Encoding 930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 931 : Local node LN1 backup paths encoding : 932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 934 Local Node with Backup Paths Encoding 936 A adjacent node and its backup paths can be encoded in the following 937 format. It is the adjacent node (such as adjacent node RN10) index 938 value followed by the adjacent node backup paths encoding, which is 939 the same as the node backup paths encoding described in 940 Section 6.2.2.1. 942 +-+-+-+-+-+-+-+-+-+ 943 |RN10 Index Value | (#bits indicated by ENSI) 944 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 945 : adjacent node RN10 backup paths encoding : 946 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 948 Adjacent Node with Backup Paths Encoding 950 The links between a local node and a number of its adjacent nodes, 951 the backup paths for each of the nodes, and the backup paths for each 952 of the links can be encoded in the following format. It is called 953 Links from Node with Backup Paths Encoding. 955 0 1 2 3 956 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 957 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 958 : Local Node with backup paths encoding : 959 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 960 | NN | Number of adjacent Nodes (i.e., Number of links) 961 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 962 : Adjacent Node 1 with backup paths encoding : 963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 964 : Link1 backup paths Encoding : 965 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 966 : Adjacent Node 2 with backup paths encoding : 967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 968 : Link2 backup paths Encoding : 969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 970 | | 972 Links from Node with Backup Paths Encoding 974 A new TLV called Links with Backup Paths TLV is defined below. It 975 includes a number of Links from Node with Backup Paths Encodings 976 described above. This TLV contains both the flooding topology and 977 the backup paths for the links and nodes on the flooding topology. 979 0 1 2 3 980 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 981 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 982 | LNSBP-TLV-Type (TBD9) | TLV-Length | 983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 984 : Links from Node 1 with backup paths encoding : 985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 986 : Links from Node 2 with backup paths encoding : 987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 988 : : 989 : : 990 Links with Backup Paths TLV 992 For OSPFv2, an Opaque LSA of a new opaque type (TBDa), called 993 Flooding Topology with Backup Paths (FTBP) Opaque LSA, containing a 994 Links with Backup Paths TLV, is used to flood the flooding topology 995 with backup paths from the leader of an area to all the other nodes 996 in the area. 998 0 1 2 3 999 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 1000 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1001 | LS age | Options | LS Type = 10 | 1002 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1003 |FTBP-Type(TBDa)| Instance ID | 1004 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1005 | Advertising Router | 1006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1007 | LS Sequence Number | 1008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1009 | LS checksum | Length | 1010 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1011 ~ Links with Backup Paths TLV ~ 1012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1014 OSPFv2: Flooding Topology with Backup Paths (FTBP) Opaque LSA 1016 For OSPFv3, an area scope LSA of a new LSA function code (TBDb), 1017 containing a Links with Backup Paths TLV, is used to flood the 1018 flooding topology with backup paths from the leader of an area to all 1019 the other nodes in the area. 1021 0 1 2 3 1022 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 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1024 | LS age |1|0|1| FTBP-LSA (TBDb) | 1025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1026 | Link State ID | 1027 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1028 | Advertising Router | 1029 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1030 | LS Sequence Number | 1031 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1032 | LS checksum | Length | 1033 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1034 ~ Links with Backup Paths TLV ~ 1035 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1037 OSPFv3: Flooding Topology with Backup Paths (FTBP) LSA 1039 6.2.3. Message for Incremental Changes 1041 For adding some links to the flooding topology, we define a new TLV 1042 called Add Links TLVs of the following format. When some new links 1043 are added to the flooding topology, the leader may not flood the 1044 whole flooding topology with the new links to all the other nodes. 1045 It may just flood these new links. After receiving these new links, 1046 each of the other nodes adds these new links into the existing 1047 flooding topology. When the leader floods the whole flooding 1048 topology with the new links to all the other nodes, it removes the 1049 LSA for the new links. When removing the LSA for these new links, 1050 each of the other nodes does not update the flooding topology (i.e., 1051 does not remove these links from the flooding topology). 1053 0 1 2 3 1054 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 1055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1056 | ADDLK-TLV-Type (TBDc) | TLV-Length | 1057 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1058 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 1059 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1060 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 1061 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1062 : : 1063 : : 1064 Add Links TLV 1066 For deleting some links from the flooding topology, we define a new 1067 TLV called Delete Links TLVs of the following format. When some old 1068 links are removed from the flooding topology, the leader may not 1069 flood the whole flooding topology without the old links to all the 1070 other nodes. It may just flood these old links. After receiving 1071 these old links, each of the other nodes deletes these old links from 1072 the existing flooding topology. When the leader floods the whole 1073 flooding topology without the old links to all the other nodes, it 1074 removes the LSA for the old links. When removing the LSA for these 1075 old links, each of the other nodes does not update the flooding 1076 topology (i.e., does not add these links into the flooding topology). 1078 0 1 2 3 1079 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 1080 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1081 | DELLK-TLV-Type (TBDd) | TLV-Length | 1082 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1083 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 1084 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1085 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 1086 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1087 : : 1088 : : 1089 Delete Links TLV 1091 The Add Links TLVs and Delete Links TLVs should be in a separate LSA 1092 instance. The LSA can be a Flooding Topology LSA defined above. 1093 Alternatively, we may define a new LSA for these TLVs. 1095 6.2.4. Leaders Selection 1097 The leader or Designated Router (DR) selection for a broadcast link 1098 is about selecting two leaders: a DR and Backup DR. This is 1099 generalized to select two or more leaders for an area: the primary/ 1100 first leader (or leader for short), the secondary leader, the third 1101 leader and so on. 1103 A new TLV is defined to include the information on flooding reduction 1104 of a node, which is called Flooding Reduction Information TLV or 1105 Information TLV for short. This TLV is generated by every node that 1106 supports flooding reduction in general. Every node originates a RI 1107 LSA with a Flooding Reduction Information TLV containing its priority 1108 to become a leader. The format of the TLV is as follows. 1110 0 1 2 3 1111 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 1112 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1113 | INFO-TLV-Type (TBDe) | TLV-Length | 1114 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1115 | Priority | Reserved (MUST be zero) | 1116 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1117 ~ sub TLVs (optional) ~ 1118 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1120 Flooding Reduction Information TLV 1122 A Priority field of eight bits is defined in the TLV to indicate the 1123 priority of the node originating the TLV to become the leader node in 1124 central mode. 1126 A sub-TLV called leaders sub-TLV is defined. It has the following 1127 format. 1129 0 1 2 3 1130 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 1131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1132 | LEADS-TLV-Type (TBDf) | TLV-Length | 1133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1134 | 1st Leader Node/Router ID | 1135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1136 | 2nd Leader Node/Router ID | 1137 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1138 ~ ~ 1139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1140 | nth Leader Node/Router ID | 1141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1143 Leaders sub-TLV 1145 When a node selects itself as a leader, it originates a RI LSA 1146 containing the leader in a leaders sub-TLV. 1148 After the first leader node is down, the other leaders will be 1149 promoted. The secondary leader becomes the first leader, the third 1150 leader becomes the secondary leader, and so on. When a node selects 1151 itself as the n-th leader, it originates a RI LSA with a Leaders sub- 1152 TLV containing n leaders. 1154 7. Extensions to IS-IS 1156 The extensions to IS-IS is similar to OSPF. 1158 7.1. Extensions for Operations 1160 A new TLV for operations is defined in IS-IS LSP. It has the 1161 following format and contains the same contents as the Flooding 1162 Reduction Instruction TLV defined in OSPF RI LSA. 1164 0 1 2 3 1165 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 1166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1167 |INST-Type(TBDi1| Length | 1168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1169 | OP | MOD | Algorithm | Reserved (MUST be zero) | NL | 1170 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1171 ~ sub TLVs (optional) ~ 1172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1174 IS-IS Flooding Reduction Instruction TLV 1176 7.2. Extensions for Centralized Mode 1178 7.2.1. TLV for Flooding Topology 1180 A new TLV for the encodings of the links in the flooding topology is 1181 defined. It has the following format and contains the same contents 1182 as the Flooding Topology Links TLV defined in OSPF Flooding Topology 1183 Opaque LSA. 1185 0 1 2 3 1186 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 1187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1188 |FTL-Type(TBDi2)| Length | 1189 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1190 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 1191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1192 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 1193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1194 : : 1195 : : 1196 IS-IS Flooding Topology Links TLV 1198 7.2.2. Encodings for Backup Paths 1200 7.2.2.1. TLVs for Backup Paths 1202 For flooding backup paths separately, we define two TLVs: IS-IS Node 1203 Backup Paths TLV and IS-IS Link Backup Path TLV. The former has the 1204 following format and contains the same contents as Node Backup Paths 1205 TLV in OSPF. 1207 0 1 2 3 1208 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 1209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1210 |NBP-Type(TBDi3)| Length | 1211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1212 |Node1 Index Enc| Variable bits 1213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1214 : Node1 backup paths encoding : 1215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1216 |Node2 Index Enc| Variable bits 1217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1218 : Node2 backup paths encoding : 1219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1220 // // 1221 IS-IS Node Backup Paths TLV 1223 The latter has the following format and contains the same contents as 1224 Link Backup Paths TLV in OSPF. 1226 0 1 2 3 1227 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 1228 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1229 |LBP-Type(TBDi4)| Length | 1230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1231 |Link1 Index Enc| Variable bits 1232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1233 : Link1 backup paths encoding : 1234 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1235 |Link2 Index Enc| Variable bits 1236 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1237 : Link2 backup paths encoding : 1238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1239 // // 1240 IS-IS Link Backup Paths TLV 1242 7.2.2.2. Backup Paths in Links TLV 1244 A new TLV is defined to integrate the backup paths with the links on 1245 the flooding topology. It has the following format and contains the 1246 same contents as the Links with Backup Paths TLV in OSPF. 1248 0 1 2 3 1249 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 1250 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1251 |LSB-Type(TBDi5)| Length | 1252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1253 : Links from Node 1 with backup paths encoding : 1254 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1255 : Links from Node 2 with backup paths encoding : 1256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1257 : : 1258 : : 1259 IS-IS Links with Backup Paths TLV 1261 7.2.3. TLVs for Incremental Changes 1263 Similar to Add Links TLV in OSPF, a new TLV called IS-IS Add Links 1264 TLV is defined. It has the following format and contains the same 1265 contents as Add Links TLV in OSPF. 1267 0 1 2 3 1268 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 1269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1270 |ADDL-Type(TBDi6| Length | 1271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1272 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 1273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1274 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 1275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1276 : : 1277 : : 1278 IS-IS Add Links TLV 1280 Similar to Delete Links TLV in OSPF, a new TLV called IS-IS Delete 1281 Links TLV is defined. It has the following format and contains the 1282 same contents as Delete Links TLV in OSPF. 1284 0 1 2 3 1285 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 1286 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1287 |DELL-Type(TBDi7| Length | 1288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1289 ~ Links Encoding (Node 1 to its adjacent Nodes) ~ 1290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1291 ~ Links Encoding (Node 2 to its adjacent Nodes) ~ 1292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1293 : : 1294 : : 1295 IS-IS Delete Links TLV 1297 7.2.4. Leaders Selection 1299 Similar to Flooding Reduction Information TLV in OSPF, a new TLV 1300 called IS-IS Flooding Reduction Information TLV is defined. It has 1301 the following format and contains the same contents as Flooding 1302 Reduction Information TLV in OSPF. 1304 0 1 2 3 1305 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 1306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1307 |INF-Type(TBDi8)| Length | 1308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1309 | Priority | Reserved (MUST be zero) | 1310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1311 ~ sub TLVs (optional) ~ 1312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1314 IS-IS Flooding Reduction Information TLV 1316 8. Flooding Behavior 1318 This section describes the revised flooding behavior for a node 1319 having at least one link on the flooding topology. The revised 1320 flooding procedure MUST flood an LS to every node in the network in 1321 any case, as the standard flooding procedure does. 1323 8.1. Nodes Perform Flooding Reduction without Failure 1325 8.1.1. Receiving an LS 1327 When a node receives a newer LS that is not originated by itself from 1328 one of its interfaces, it floods the LS only to all the other 1329 interfaces that are on the flooding topology. 1331 When the LS is received from an interface on the flooding topology, 1332 it is flooded only to all the other interfaces that are on the 1333 flooding topology. When the LS is received on an interface that is 1334 not on the flooding topology, it is also flooded only to all the 1335 other interfaces that are on the flooding topology. 1337 In any case, the LS must not be transmitted back to the receiving 1338 interface. 1340 Note before forwarding a received LS, the node would do the normal 1341 processing as usual. 1343 8.1.2. Originating an LS 1345 When a node originates an LS, it floods the LS to its interfaces on 1346 the flooding topology if the LS is a refresh LS (i.e., there is no 1347 significant change in the LS comparing to the previous LS); otherwise 1348 (i.e., there are significant changes in the LS), it floods the LS to 1349 all its interfaces. Choosing flooding the LS with significant 1350 changes to all the interfaces instead of limiting to the interfaces 1351 on the flooding topology would speed up the distribution of the 1352 significant link state changes. 1354 8.1.3. Establishing Adjacencies 1356 Adjacencies being established can be classified into two categories: 1357 adjacencies to new nodes and adjacencies to existing nodes. 1359 8.1.3.1. Adjacency to New Node 1361 An adjacency to a new node is an adjacency between a node (say node 1362 A) on the flooding topology and the new node (say node Y) which is 1363 not on the flooding topology. There is not any adjacency between 1364 node Y and a node in the network area. 1366 When new node Y is up and connected to node A, node A assumes that 1367 node Y and the link between node Y and node A are on the flooding 1368 topology until a new flooding topology is computed and built. Node A 1369 may determine whether node Y is a new node through checking if node Y 1370 is reachable or on the flooding topology. 1372 The procedure for establishing the adjacency between node A and node 1373 Y is the existing normal procedure unchanged. After the status of 1374 the adjacency reaches to Exchange or Full, node A sends node Y every 1375 new or updated LS that node A receives or originates. 1377 8.1.3.2. Adjacency to Existing Node 1379 An adjacency to an existing node is an adjacency between a node (say 1380 node A) on the flooding topology and the existing node (say node X) 1381 which exists on the flooding topology. There are some adjacencies 1382 between node X and some nodes in the network area. 1384 When existing node X is connected to node A after a link between node 1385 X and node A is up, node A assumes that the link connecting node A 1386 and node X is not on the flooding topology until a new flooding 1387 topology is computed and built. Node A may determine whether node X 1388 is an existing node through checking if node X is reachable or on the 1389 flooding topology. 1391 The procedure for establishing the adjacency between node A and node 1392 X is the existing normal procedure unchanged. Node A does not send 1393 node X any new or updated LS that node A receives or originates even 1394 after the status of the adjacency reaches to Exchange or Full. 1396 8.2. An Exception Case 1398 During an LS flooding, one or multiple link and node failures may 1399 happen. Some failures do not split the flooding topology, thus do 1400 not affect the flooding behavior. For example, multiple failures of 1401 the links not on the flooding topology do not split the flooding 1402 topology and do not affect the flooding behavior. The sections below 1403 focus on the failures that may split the flooding topology. 1405 8.2.1. Multiple Failures 1407 When two or more failures on the current flooding topology occur 1408 almost in the same time, each of the nodes within a given distance 1409 (such as 3 hops) to a failure point, floods the link state (LS) that 1410 it receives or originates to all the interfaces (except for the one 1411 from which the LS is received) until a new flooding topology is 1412 built. 1414 In other words, when the failures happen, each of the nodes within a 1415 given distance to a failure point, adds all its local links to the 1416 flooding topology temporarily until a new flooding topology is built. 1418 In alternative way, each node computes and maintains a small number 1419 of backup paths. For a backup path for a link L on the flooding 1420 topology, a node N computes and maintains it only if the backup path 1421 goes through node N. Node N stores the links (e.g., local link L1 1422 and L2) attached to it and on the backup path for link L. When link 1423 L fails and there are one or more other failures on the flooding 1424 topology or the flooding topology splits, node N adds the links 1425 (e.g., L1 and L2) to the flooding topology temporarily until a new 1426 flooding topology is built. 1428 Similarly, for a backup path for a connection crossing a node M on 1429 the flooding topology, a node N computes and maintains it only if the 1430 backup path goes through node N. Node N stores the links (e.g., 1431 local link La and Lb) attached to it and on the backup path for node 1432 M. 1434 When node M fails and there are one or more other failures on the 1435 flooding topology or the flooding topology splits, node N adds the 1436 links (e.g., La and Lb) to the flooding topology temporarily until a 1437 new flooding topology is built. 1439 For one link/node failure that splits the current flooding topology, 1440 the above behavior is applied. 1442 Note that if it can be quickly determined that the flooding topology 1443 is not split by the failures, the flooding behavior in Section 8.1 1444 may follow. 1446 8.2.2. Changes on Flooding Topology 1448 After multiple failures split the current (old) flooding topology, 1449 some link states may be out of synchronization among some nodes. 1450 This can be resolved as follows. 1452 After a node N computes or receives a new flooding topology, for a 1453 local link L attached to node N, if 1) link L is not on the current 1454 (old) flooding topology and is on the new flooding topology, and 2) 1455 there is a failure after the current (old) flooding topology is 1456 built, then node N sends a delta of the link states that it received 1457 or originated to its adjacent node over link L. 1459 For node N, the delta of the link states is the link states with 1460 changes that node N received or originated during the period of time 1461 in which the current (old) flooding topology is split. 1463 Suppose that Max_Split_Period is a number (in seconds), which is the 1464 maximum period of time in which a flooding topology is split. Tc is 1465 the time at which the current (old) flooding topology is built, Tn is 1466 the time at which the new flooding topology is built, and Ts is the 1467 bigger one between Tc and (Tn - Max_Split_Period). Node N sends its 1468 adjacent node over link L the link states with changes that it 1469 received or originated from Ts to Tn. 1471 9. Security Considerations 1473 This document does not introduce any security issue. 1475 10. IANA Considerations 1477 10.1. OSPFv2 1479 Under Registry Name: OSPF Router Information (RI) TLVs [RFC7770], 1480 IANA is requested to assign two new TLV values for OSPF flooding 1481 reduction as follows: 1483 +===============+==================+=====================+ 1484 | TLV Value | TLV Name | reference | 1485 +===============+==================+=====================+ 1486 | 11 | Instruction TLV | This document | 1487 +---------------+------------------+---------------------+ 1488 | 12 | Information TLV | This document | 1489 +---------------+------------------+---------------------+ 1491 Under the registry name "Opaque Link-State Advertisements (LSA) 1492 Option Types" [RFC5250], IANA is requested to assign new Opaque Type 1493 registry values for FT LSA, BP LSA, FTBP LSA as follows: 1495 +====================+===============+=======================+ 1496 | Registry Value | Opaque Type | reference | 1497 +====================+===============+=======================+ 1498 | 10 | FT LSA | This document | 1499 +--------------------+---------------+-----------------------+ 1500 | 11 | BP LSA | This document | 1501 +--------------------+---------------+-----------------------+ 1502 | 12 | FTBP LSA | This document | 1503 +--------------------+---------------+-----------------------+ 1505 IANA is requested to create and maintain new registries: 1507 o OSPFv2 FT LSA TLVs 1509 Initial values for the registry are given below. The future 1510 assignments are to be made through IETF Review [RFC5226]. 1512 Value OSPFv2 FT LSA TLV Name Definition 1513 ----- ----------------------- ---------- 1514 0 Reserved 1515 1 FT Links TLV see Section 6.2.1 1516 2-32767 Unassigned 1517 32768-65535 Reserved 1519 o OSPFv2 BP LSA TLVs 1521 Initial values for the registry are given below. The future 1522 assignments are to be made through IETF Review [RFC5226]. 1524 Value OSPFv2 TBPLSA TLV Name Definition 1525 ----- ----------------------- ---------- 1526 0 Reserved 1527 1 Node Backup Paths TLV see Section 6.2.2 1528 2 Link Backup Paths TLV see Section 6.2.2 1529 3-32767 Unassigned 1530 32768-65535 Reserved 1532 o OSPFv2 FTBP LSA TLVs 1534 Initial values for the registry are given below. The future 1535 assignments are to be made through IETF Review [RFC5226]. 1537 Value OSPFv2 FTBP LSA TLV Name Definition 1538 ----- ------------------------ ---------- 1539 0 Reserved 1540 1 Links with Backup Paths TLV see Section 6.2.2 1541 2-32767 Unassigned 1542 32768-65535 Reserved 1544 10.2. OSPFv3 1546 Under the registry name "OSPFv3 LSA Function Codes", IANA is 1547 requested to assign new registry values for FT LSA, BP LSA, FTBP LSA 1548 as follows: 1550 +===========+==========================+=======================+ 1551 | Value | LSA Function Code Name | reference | 1552 +======================================+=======================+ 1553 | 16 | FT LSA | This document | 1554 +-----------+--------------------------+-----------------------+ 1555 | 17 | BP LSA | This document | 1556 +-----------+--------------------------+-----------------------+ 1557 | 18 | FTBP LSA | This document | 1558 +-----------+--------------------------+-----------------------+ 1560 IANA is requested to create and maintain new registries: 1562 o OSPFv3 FT LSA TLVs 1564 Initial values for the registry are given below. The future 1565 assignments are to be made through IETF Review [RFC5226]. 1567 Value OSPFv3 FT LSA TLV Name Definition 1568 ----- ----------------------- ---------- 1569 0 Reserved 1570 1 FT Links TLV see Section 6.2.1 1571 2-32767 Unassigned 1572 32768-65535 Reserved 1574 o OSPFv3 BP LSA TLVs 1576 Initial values for the registry are given below. The future 1577 assignments are to be made through IETF Review [RFC5226]. 1579 Value OSPFv3 TBPLSA TLV Name Definition 1580 ----- ----------------------- ---------- 1581 0 Reserved 1582 1 Node Backup Paths TLV see Section 6.2.2 1583 2 Link Backup Paths TLV see Section 6.2.2 1584 3-32767 Unassigned 1585 32768-65535 Reserved 1587 o OSPFv3 FTBP LSA TLVs 1589 Initial values for the registry are given below. The future 1590 assignments are to be made through IETF Review [RFC5226]. 1592 Value OSPFv3 FTBP LSA TLV Name Definition 1593 ----- ------------------------ ---------- 1594 0 Reserved 1595 1 Links with Backup Paths TLV see Section 6.2.2 1596 2-32767 Unassigned 1597 32768-65535 Reserved 1599 10.3. IS-IS 1601 Under Registry Name: IS-IS TLV Codepoints, IANA is requested to 1602 assign new TLV values for IS-IS flooding reduction as follows: 1604 Value TLV Name Definition 1605 ----- ------------------------ ---------- 1606 151 FT Links TLV see Section 7.2.1 1607 152 Node Backup Paths TLV see Section 7.2.2 1608 153 Link Backup Paths TLV see Section 7.2.2 1609 154 Links with Backup Paths TLV see Section 7.2.2 1610 155 Add Links TLV see Section 7.2.3 1611 156 Delete Links TLV see Section 7.2.3 1612 157 Instruction TLV see Section 7.1 1613 158 Information TLV see Section 7.2.4 1615 11. Acknowledgements 1617 The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, 1618 Stephane Litkowski and Alvaro Retana for their valuable suggestions 1619 and comments on this draft. 1621 12. References 1623 12.1. Normative References 1625 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1626 Requirement Levels", BCP 14, RFC 2119, 1627 DOI 10.17487/RFC2119, March 1997, 1628 . 1630 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1631 DOI 10.17487/RFC2328, April 1998, 1632 . 1634 [RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The 1635 OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250, 1636 July 2008, . 1638 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 1639 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 1640 . 1642 [RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and 1643 S. Shaffer, "Extensions to OSPF for Advertising Optional 1644 Router Capabilities", RFC 7770, DOI 10.17487/RFC7770, 1645 February 2016, . 1647 12.2. Informative References 1649 [I-D.li-dynamic-flooding] 1650 Li, T. and P. Psenak, "Dynamic Flooding on Dense Graphs", 1651 draft-li-dynamic-flooding-05 (work in progress), June 1652 2018. 1654 [I-D.shen-isis-spine-leaf-ext] 1655 Shen, N., Ginsberg, L., and S. Thyamagundalu, "IS-IS 1656 Routing for Spine-Leaf Topology", draft-shen-isis-spine- 1657 leaf-ext-07 (work in progress), October 2018. 1659 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1660 IANA Considerations Section in RFCs", RFC 5226, 1661 DOI 10.17487/RFC5226, May 2008, 1662 . 1664 Appendix A. Algorithms to Build Flooding Topology 1666 There are many algorithms to build a flooding topology. A simple and 1667 efficient one is briefed below. 1669 o Select a node R according to a rule such as the node with the 1670 biggest/smallest node ID; 1672 o Build a tree using R as root of the tree (details below); and then 1674 o Connect k (k>=0) leaves to the tree to have a flooding topology 1675 (details follow). 1677 A.1. Algorithms to Build Tree without Considering Others 1679 An algorithm for building a tree from node R as root starts with a 1680 candidate queue Cq containing R and an empty flooding topology Ft: 1682 1. Remove the first node A from Cq and add A into Ft 1684 2. If Cq is empty, then return with Ft 1686 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1687 and not in Ft and X1, X2, ..., Xn are in a special order. For 1688 example, X1, X2, ..., Xn are ordered by the cost of the link 1689 between A and Xi. The cost of the link between A and Xi is less 1690 than the cost of the link between A and Xj (j = i + 1). If two 1691 costs are the same, Xi's ID is less than Xj's ID. In another 1692 example, X1, X2, ..., Xn are ordered by their IDs. If they are 1693 not ordered, then make them in the order. 1695 4. Add Xi (i = 1, 2, ..., n) into the end of Cq, goto step 1. 1697 Another algorithm for building a tree from node R as root starts with 1698 a candidate queue Cq containing R and an empty flooding topology Ft: 1700 1. Remove the first node A from Cq and add A into Ft 1702 2. If Cq is empty, then return with Ft 1704 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1705 and not in Ft and X1, X2, ..., Xn are in a special order. For 1706 example, X1, X2, ..., Xn are ordered by the cost of the link 1707 between A and Xi. The cost of the link between A and Xi is less 1708 than the cost of the link between A and Xj (j = i + 1). If two 1709 costs are the same, Xi's ID is less than Xj's ID. In another 1710 example, X1, X2, ..., Xn are ordered by their IDs. If they are 1711 not ordered, then make them in the order. 1713 4. Add Xi (i = 1, 2, ..., n) into the front of Cq and goto step 1. 1715 A third algorithm for building a tree from node R as root starts with 1716 a candidate list Cq containing R associated with cost 0 and an empty 1717 flooding topology Ft: 1719 1. Remove the first node A from Cq and add A into Ft 1721 2. If all the nodes are on Ft, then return with Ft 1723 3. Suppose that node A is associated with a cost Ca which is the 1724 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 1725 connected to node A and not in Ft and the cost of the link 1726 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 1727 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 1728 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 1729 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 1730 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 1732 4. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 1733 ..., m) are the nodes in Cq, Cai is the cost associated with Ai, 1734 and IDi is the ID of Ai. One order is that for any k = 1, 2, 1735 ..., m-1, Cak < Caj (j = k+1) or Cak = Caj and IDk < IDj. Goto 1736 step 1. 1738 A.2. Algorithms to Build Tree Considering Others 1740 An algorithm for building a tree from node R as root with 1741 consideration of others's support for flooding reduction starts with 1742 a candidate queue Cq containing R associated with previous hop PH=0 1743 and an empty flooding topology Ft: 1745 1. Remove the first node A that supports flooding reduction from the 1746 candidate queue Cq if there is such a node A; otherwise (i.e., if 1747 there is not such node A in Cq), then remove the first node A 1748 from Cq. Add A into the flooding topology Ft. 1750 2. If Cq is empty or all nodes are on Ft, then return with Ft 1752 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1753 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 1754 special order considering whether some of them that support 1755 flooding reduction (. For example, X1, X2, ..., Xn are ordered 1756 by the cost of the link between A and Xi. The cost of the link 1757 between A and Xi is less than that of the link between A and Xj 1758 (j = i + 1). If two costs are the same, Xi's ID is less than 1759 Xj's ID. The cost of a link is redefined such that 1) the cost 1760 of a link between A and Xi both support flooding reduction is 1761 much less than the cost of any link between A and Xk where Xk 1762 with F=0; 2) the real metric of a link between A and Xi and the 1763 real metric of a link between A and Xk are used as their costs 1764 for determining the order of Xi and Xk if they all (i.e., A, Xi 1765 and Xk) support flooding reduction or none of Xi and Xk support 1766 flooding reduction. 1768 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 1769 the end of the candidate queue Cq, and goto step 1. 1771 Another algorithm for building a tree from node R as root with 1772 consideration of others' support for flooding reduction starts with a 1773 candidate queue Cq containing R associated with previous hop PH=0 and 1774 an empty flooding topology Ft: 1776 1. Remove the first node A that supports flooding reduction from the 1777 candidate queue Cq if there is such a node A; otherwise (i.e., if 1778 there is not such node A in Cq), then remove the first node A 1779 from Cq. Add A into the flooding topology Ft. 1781 2. If Cq is empty or all nodes are on Ft, then return with Ft. 1783 3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A 1784 and not in the flooding topology Ft and X1, X2, ..., Xn are in a 1785 special order considering whether some of them support flooding 1786 reduction. For example, X1, X2, ..., Xn are ordered by the cost 1787 of the link between A and Xi. The cost of the link between A and 1788 Xi is less than the cost of the link between A and Xj (j = i + 1789 1). If two costs are the same, Xi's ID is less than Xj's ID. 1790 The cost of a link is redefined such that 1) the cost of a link 1791 between A and Xi both support flooding reduction is much less 1792 than the cost of any link between A and Xk where Xk does not 1793 support flooding reduction; 2) the real metric of a link between 1794 A and Xi and the real metric of a link between A and Xk are used 1795 as their costs for determining the order of Xi and Xk if they all 1796 (i.e., A, Xi and Xk) support flooding reduction or none of Xi and 1797 Xk supports flooding reduction. 1799 4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into 1800 the front of the candidate queue Cq, and goto step 1. 1802 A third algorithm for building a tree from node R as root with 1803 consideration of others' support for flooding reduction (using flag F 1804 = 1 for support, and F = 0 for not support in the following) starts 1805 with a candidate list Cq containing R associated with low order cost 1806 Lc=0, high order cost Hc=0 and previous hop ID PH=0, and an empty 1807 flooding topology Ft: 1809 1. Remove the first node A from Cq and add A into Ft. 1811 2. If all the nodes are on Ft, then return with Ft 1813 3. Suppose that node A is associated with a cost Ca which is the 1814 cost from root R to node A, node Xi (i = 1, 2, ..., n) is 1815 connected to node A and not in Ft and the cost of the link 1816 between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi, 1817 check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi 1818 is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq, 1819 then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in 1820 Cq; If Cxi == Ci then add Xi with cost Ci into Cq. 1822 4. Suppose that node A is associated with a low order cost LCa which 1823 is the low order cost from root R to node A and a high order cost 1824 HCa which is the high order cost from R to A, node Xi (i = 1, 2, 1825 ..., n) is connected to node A and not in the flooding topology 1826 Ft and the real cost of the link between A and Xi is Ci (i=1, 2, 1827 ..., n). Compute LCxi and HCxi: LCxi = LCa + Ci if both A and Xi 1828 have flag F set to one, otherwise LCxi = LCa HCxi = HCa + Ci if A 1829 or Xi does not have flag F set to one, otherwise HCxi = HCa If Xi 1830 is not in Cq, then add Xi associated with LCxi, HCxi and PH = A 1831 into Cq; If Xi associated with LCxi' and HCxi' and PHxi' is in 1832 Cq, then If HCxi' > HCxi then replace Xi with HCxi', LCxi' and 1833 PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise (i.e., 1834 HCxi' == HCxi) if LCxi' > LCxi , then replace Xi with HCxi', 1835 LCxi' and PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise 1836 (i.e., HCxi' == HCxi and LCxi' == LCxi) if PHxi' > PH, then 1837 replace Xi with HCxi', LCxi' and PHxi' by Xi with HCxi, LCxi and 1838 PH=A in Cq. 1840 5. Make sure Cq is in a special order. Suppose that Ai (i=1, 2, 1841 ..., m) are the nodes in Cq, HCai and LCai are low order cost and 1842 high order cost associated with Ai, and IDi is the ID of Ai. One 1843 order is that for any k = 1, 2, ..., m-1, HCak < HCaj (j = k+1) 1844 or HCak = HCaj and LCak < LCaj or HCak = HCaj and LCak = LCaj and 1845 IDk < IDj. Goto step 1. 1847 A.3. Connecting Leaves 1849 Suppose that we have a flooding topology Ft built by one of the 1850 algorithms described above. Ft is like a tree. We may connect k (k 1851 >=0) leaves to the tree to have a enhanced flooding topology with 1852 more connectivity. 1854 Suppose that there are m (0 < m) leaves directly connected to a node 1855 X on the flooding topology Ft. Select k (k <= m) leaves through 1856 using a deterministic algorithm or rule. One algorithm or rule is to 1857 select k leaves that have smaller or larger IDs (i.e., the IDs of 1858 these k leaves are smaller/bigger than the IDs of the other leaves 1859 directly connected to node X). Since every node has a unique ID, 1860 selecting k leaves with smaller or larger IDs is deterministic. 1862 If k = 1, the leaf selected has the smallest/largest node ID among 1863 the IDs of all the leaves directly connected to node X. 1865 For a selected leaf L directly connected to a node N in the flooding 1866 topology Ft, select a connection/adjacency to another node from node 1867 L in Ft through using a deterministic algorithm or rule. 1869 Suppose that leaf node L is directly connected to nodes Ni (i = 1870 1,2,...,s) in the flooding topology Ft via adjacencies and node Ni is 1871 not node N, IDi is the ID of node Ni, and Hi (i = 1,2,...,s) is the 1872 number of hops from node L to node Ni in the flooding topology Ft. 1874 One Algorithm or rule is to select the connection to node Nj (1 <= j 1875 <= s) such that Hj is the largest among H1, H2, ..., Hs. If there is 1876 another node Na ( 1 <= a <= s) and Hj = Ha, then select the one with 1877 smaller (or larger) node ID. That is that if Hj == Ha and IDj < IDa 1878 then select the connection to Nj for selecting the one with smaller 1879 node ID (or if Hj == Ha and IDj < IDa then select the connection to 1880 Na for selecting the one with larger node ID). 1882 Suppose that the number of connections in total between leaves 1883 selected and the nodes in the flooding topology Ft to be added is 1884 NLc. We may have a limit to NLc. 1886 Authors' Addresses 1888 Huaimo Chen 1889 Huawei Technologies 1891 Email: huaimo.chen@huawei.com 1893 Dean Cheng 1894 Huawei Technologies 1896 Email: dean.cheng@huawei.com 1898 Mehmet Toy 1899 Verizon 1900 USA 1902 Email: mehmet.toy@verizon.com 1903 Yi Yang 1904 IBM 1905 Cary, NC 1906 United States of America 1908 Email: yyietf@gmail.com