Network Working Group H. Chen Internet-Draft Futurewei Intended status: Standards Track D. Cheng Expires: January 8, 2020 Individual M. Toy Verizon Y. Yang IBM A. Wang China Telecom X. Liu Volta Networks Y. Fan Casa Systems L. Liu Fujitsu July 7, 2019 Flooding Topology Computation Algorithm draft-cc-lsr-flooding-reduction-04 Abstract This document proposes an algorithm for a node to compute a flooding topology, which is a subgraph of the complete topology per underline physical network. When every node in an area automatically calculates a flooding topology by using a same algorithm and floods the link states using the flooding topology, the amount of flooding traffic in the network is greatly reduced. This would reduce convergence time with a more stable and optimized routing environment. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Chen, et al. Expires January 8, 2020 [Page 1] Internet-Draft FTC Algorithm July 2019 Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on January 8, 2020. Copyright Notice Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Flooding Topology Construction . . . . . . . . . . . . . 3 4. Algorithms to Compute Flooding Topology . . . . . . . . . . . 4 4.1. Algorithm with Considering Degree . . . . . . . . . . . . 5 4.2. Algorithm with Considering Others . . . . . . . . . . . . 5 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.1. Normative References . . . . . . . . . . . . . . . . . . 7 8.2. Informative References . . . . . . . . . . . . . . . . . 7 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 1. Introduction For some networks such as dense Data Center (DC) networks, the existing Link State (LS) flooding mechanism is not efficient and may have some issues. The extra LS flooding consumes network bandwidth. Processing the extra LS flooding, including receiving, buffering and decoding the extra LSs, wastes memory space and processor time. This may cause scalability issues and affect the network convergence negatively. Chen, et al. Expires January 8, 2020 [Page 2] Internet-Draft FTC Algorithm July 2019 This document proposes an algorithm for a node to compute a flooding topology, which is a subgraph of the complete topology per underline physical network. When every node in an area automatically calculates a flooding topology by using a same algorithm and floods the link states using the flooding topology, the amount of flooding traffic in the network is greatly reduced. This would reduce convergence time with a more stable and optimized routing environment. There may be multiple algorithms for computing a flooding topology. Users can select one they prefer, and smoothly switch from one to another. 2. Terminology LSA: A Link State Advertisement in OSPF. LSP: A Link State Protocol Data Unit (PDU) in IS-IS. LS: A Link Sate, which is an LSA or LSP. FT: Flooding Topology. FTC: Flooding Topology Computation. 3. Flooding Topology For a given network topology, a flooding topology is a sub-graph or sub-network of the given network topology that has the same reachability to every node as the given network topology. Thus all the nodes in the given network topology MUST be in the flooding topology. All the nodes MUST be inter-connected directly or indirectly. As a result, LS flooding will in most cases occur only on the flooding topology, that includes all nodes but a subset of links. Note even though the flooding topology is a sub-graph of the original topology, any single LS MUST still be disseminated in the entire network. 3.1. Flooding Topology Construction Many different flooding topologies can be constructed for a given network topology. For example, a chain connecting all the nodes in the given network topology is a flooding topology. A circle connecting all the nodes is another flooding topology. A tree connecting all the nodes is a flooding topology. In addition, the tree plus the connections between some leaves of the tree and branch nodes of the tree is a flooding topology. Chen, et al. Expires January 8, 2020 [Page 3] Internet-Draft FTC Algorithm July 2019 The following parameters need to be considered for constructing a flooding topology: o Degree: The degree of the flooding topology is the maximum degree among the degrees of the nodes on the flooding topology. The degree of a node on the flooding topology is the number of connections on the flooding topology it has to other nodes. o Number of links: The number of links on the flooding topology is a key factor for reducing the amount of LS flooding. In general, the smaller the number of links, the less the amount of LS flooding. o Diameter: The diameter of the flooding topology is the shortest distance between the two most distant nodes on the flooding topology. It is a key factor for reducing the network convergence time. The smaller the diameter, the less the convergence time. o Redundancy: The redundancy of the flooding topology means a tolerance to the failures of some links and nodes on the flooding topology. If the flooding topology is split by some failures, it is not tolerant to these failures. In general, the larger the number of links on the flooding topology is, the more tolerant the flooding topology to failures. Note that the flooding topology constructed by a node is dynamic in nature, that means when the base topology (the entire topology graph) changes, the flooding topology (the sub-graph) MUST be re-computed/ re-constructed to ensure that any node that is reachable on the base topology MUST also be reachable on the flooding topology. 4. Algorithms to Compute Flooding Topology There are many algorithms to compute a flooding topology. A simple and efficient one is briefed below. o Select a node R0 according to a rule such as the node with the smallest node ID; o Build a tree using R0 as root of the tree; and then o Connect each node whose degree is one to the tree to have a flooding topology. Chen, et al. Expires January 8, 2020 [Page 4] Internet-Draft FTC Algorithm July 2019 4.1. Algorithm with Considering Degree The algorithm starts from node R0 as root with a given maximum degree MaxD, a candidate queue Cq = {(R0, D = 0, PHs = { })}, and an empty flooding topology FT = { }. Cq contains one element (R0, D = 0, PHs = { }), where node R0 is the root, D = 0 indicates that the Degree (D for short) of R0 is 0 (i.e., the number of links on the flooding topology connected to R0 is 0), PHs = { } indicates that the Previous Hops (PHs for short) of R0 is empty. 1. Finding and removing the first element with node A in Cq that is not on FT and one PH's D in PHs < MaxD. If there is no element with a node in Cq whose PHs != { } and one PH in PHs whose D < MaxD, then MaxD++ and restarts algorithm from R0, MaxD, Cq = {(R0,D=0,PHs = { })}, FT = { }; otherwise (i.e., A with one PH's D in PHs < MaxD or PHs = { }), if PHs = { } (i.e., A is the root), then mark A on FT and add A with D=0 and PHs={ } into FT; otherwise (i.e., A is not the root. Assume that PH is the first one in PHs whose D < MaxD), PH's D++, mark A on FT and add A with D=1 and PHs={PH} to FT. 2. If all the nodes are on the FT, then goto step 4; 3. Suppose that node Xi (i = 1, 2,..., n) is connected to node A and not on FT, and X1, X2,..., Xn are in an increasing order by their IDs (i.e., X1's ID < X2's ID < ... < Xn's ID). If Xi is not in Cq, then add it into the end of Cq with D = 0 and PHs = {A}; otherwise (i.e., Xi is in Cq), add A into Xi's PHs and elements in PHs are in an increasing order by their degrees first and then IDs; Goto step 1. 4. For each node B in FT whose D is one, find a link L attached to B such that L's remote node R whose D and ID are minimum; increase B's D and R's D by one. Return FT. 4.2. Algorithm with Considering Others There may be some contraints on some nodes in a network. For example, in a spine-and-leaf network, there may be a constraint on the degree of every leaf node on the flooding topology, which is that Chen, et al. Expires January 8, 2020 [Page 5] Internet-Draft FTC Algorithm July 2019 the degree of every leaf node is not greater than a given number ConMaxD such as ConMaxD = 2. For each of the other nodes such as the spine nodes, there is no such constraint, that is that ConMaxD is a huge number for each of these nodes. Step 1 of the algorithm described above is updated below to consider this constraint. In addition to checking constraint PH's D < MaxD, step 1 checks another constraint PH's D < PH's ConMaxD. 1. Finding and removing the first element with node A in Cq that is not on FT and one PH's D in PHs < MaxD and PH's D < PH's ConMaxD. If there is no element with a node in Cq whose PHs != { } and one PH in PHs whose D < MaxD and PH's D < PH's ConMaxD, then MaxD++ and restarts algorithm from R0, MaxD, Cq = {(R0,D=0,PHs = { })}, FT = { }; otherwise (i.e., node A with one PH's D in PHs < MaxD and PH's D < PH's ConMaxD or PHS = { }), if PHs = { } (i.e., A is the root), then mark A on FT and add A with D=0 and PHs={ } into FT; otherwise (i.e., A is not the root. Assume that PH is the first one in PHs whose D < MaxD and PH's D < PH's ConMaxD), PH's D++, mark A on FT and add A with D=1 and PHs={PH} to FT. 5. Security Considerations This document does not introduce any new security issue. 6. IANA Considerations Under Registry Name: "IGP Algorithm Type For Computing Flooding Topology" under an existing "Interior Gateway Protocol (IGP) Parameters" IANA registries (refer to Section 7.3. IGP [I-D.ietf-lsr-dynamic-flooding]), IANA is requested to assign one value of IGP Algorithm Type For Computing Flooding Topology as follows: +==========+========================================+=============+ |Type Value| Type Name | reference | +==========+========================================+=============+ | 1 | Breadth First Minimum Degree Algorithm |This document| +----------+----------------------------------------+-------------+ Chen, et al. Expires January 8, 2020 [Page 6] Internet-Draft FTC Algorithm July 2019 7. Acknowledgements The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, Stephane Litkowski and Alvaro Retana for their valuable suggestions and comments on this draft. 8. References 8.1. Normative References [I-D.ietf-lsr-dynamic-flooding] Li, T., Psenak, P., Ginsberg, L., Chen, H., Przygienda, T., Cooper, D., Jalil, L., and S. Dontula, "Dynamic Flooding on Dense Graphs", draft-ietf-lsr-dynamic- flooding-03 (work in progress), June 2019. [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and dual environments", RFC 1195, DOI 10.17487/RFC1195, December 1990, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/RFC2328, April 1998, . 8.2. Informative References [I-D.ietf-rtgwg-spf-uloop-pb-statement] Litkowski, S., Decraene, B., and M. Horneffer, "Link State protocols SPF trigger and delay algorithm impact on IGP micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-10 (work in progress), January 2019. [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, . Authors' Addresses Chen, et al. Expires January 8, 2020 [Page 7] Internet-Draft FTC Algorithm July 2019 Huaimo Chen Futurewei Boston USA Email: huaimo.chen@futurewei.com Dean Cheng Individual Santa Clara USA Email: deanccheng@gmail.com Mehmet Toy Verizon USA Email: mehmet.toy@verizon.com Yi Yang IBM Cary, NC United States of America Email: yyietf@gmail.com Aijun Wang China Telecom Beiqijia Town, Changping District Beijing 102209 China Email: wangaj.bri@chinatelecom.cn Xufeng Liu Volta Networks McLean, VA USA Email: xufeng.liu.ietf@gmail.com Chen, et al. Expires January 8, 2020 [Page 8] Internet-Draft FTC Algorithm July 2019 Yanhe Fan Casa Systems USA Email: yfan@casa-systems.com Lei Liu Fujitsu USA Email: liulei.kddi@gmail.com Chen, et al. Expires January 8, 2020 [Page 9]