LSR Working Group Dave Allan Internet Draft Ericsson Intended status: Standards Track October 2018 Expires: April 2019 A Distributed Algorithm for Constrained Flooding of IGP Advertisements draft-allan-lsr-flooding-algorithm-00 Abstract This document describes a distributed algorithm that can be applied to the problem of constraining IGP flooding in dense mesh topologies. The flooding topology utilizes two node-diverse spanning trees in order to provide complete coverage in the presence of any single failure while constraining the number of LSAs received by any IGP speaker connected to the flooding topology. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. 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". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire in March 2019. Copyright and License Notice Allan, Expires April 2019 [Page 1] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 Copyright (c) 2018 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 (http://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...................................................3 1.1. Authors......................................................3 1.2. Requirements Language........................................3 2. Conventions used in this document..............................3 2.1. Terminology..................................................3 3. Solution Overview..............................................4 3.1. The Flooding Topology........................................4 3.2. Solution Applicability.......................................4 3.3. Algorithm....................................................4 3.3.1. Algorithm Basics...........................................5 3.3.2. Generating Diverse Trees...................................5 3.3.3. Desirable Properties Computation Wise......................6 4. Applying the Algorithm.........................................6 4.1. Tree Generation..............................................6 4.2. Illustrating the result......................................6 4.3. Interactions between Participating and Non-Participating Nodes.............................................................7 4.4. Flooding of LSAs.............................................8 4.5. Root Selection...............................................9 4.6. Node Additions...............................................9 5. Further work..................................................10 5.1. Thoughts on Coexistence in the Context of a Larger Network..10 5.1.1. Multiple flooding Domains and the Severing of Flooding Domains..........................................................10 5.2. Thoughts on Flooding Topology Re-Optimization...............10 5.3. Thoughts on Node and Network Initialization.................11 5.4. Thoughts on Loop Prevention.................................11 5.5. Thoughts on Pathological Failure Scenarios..................11 6. Acknowledgements..............................................12 7. Security Considerations.......................................12 8. IANA Considerations...........................................12 9. References....................................................12 Allan et al., Expires April 2019 [Page 2] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 9.1. Normative References........................................12 9.2. Informative References......................................12 10. Author's Address.............................................13 1. Introduction This memo describes an algorithm suitable for reducing the quantity of IGP flooding in dense mesh networks. The only property that the algorithm is dependent upon is that there are at least two equal and diverse shortest paths between any pair of IGP speakers in order to meet the requirements elucidated in [Li]. The algorithm uses a re- purposing of the tie breaking algorithm used in 802.1aq Shortest Path Bridging as an element of construction of the flooding topology. It is not the intention of this memo to specify a complete solution, but to offer a foundation of an eventual solution. 1.1. Authors David Allan 1.2. 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 RFC2119 [RFC2119]. 2. Conventions used in this document 2.1. Terminology Member Adjacency - An adjacency that has been determined to part of the flooding topology. Member Node - A Participant node that is connected to the flooding topology. Participant Adjacency - An adjacency between two participating nodes. It may be a member adjacency or a non-member adjacency Non-Participant Adjacency - An adjacency where at least one of the two nodes is a not a Participating Node Participating Node - An IGP speaker that has advertised the capability, and hence the intention, to participate in a flooding topology Allan et al., Expires April 2019 [Page 3] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 3. Solution Overview 3.1. The Flooding Topology A flooding topology is composed of a contiguously connected set of participating nodes. The flooding topology constructed from two diversely rooted spanning trees. A participating node that is connected to the physical topology with a degree of two or greater and has at least two participating adjacencies will be bi-connected to the flooding topology. The resulting flooding topology diameter will typically be two times the depth of the tree hierarchy. The compromise in this approach is that a subset of nodes in the network will not see a reduction of the replication burden from current practice when flooding LSAs as the degree of a subset of nodes in the flooding topology will correspond to the degree of the physical topology. The protocol structure of flooded information is unmodified. A participant node may relay a received LSA onto member links of both spanning trees. Specific forwarding rules prevent undue flooding, the result being that every participant node that is bi-connected to the flooding topology will receive two copies of any flooded LSA in a fault free network. Participating nodes that due to network degradation are only singly connected will receive one copy. The forwarding rules are described in section 4.4. 3.2. Solution Applicability This algorithm has been considered in the context of pure bipartite graphs, bipartite graphs modified with the addition of intra-tier adjacencies, and hierarchical variations of the above. Applicability to other network designs is for further study. For all graphs the link costs are assumed to be common for all inter- tier links and common for any intra-tier links. Inter-tier and intra- tier links do not have to have the same cost. 3.3. Algorithm The algorithm borrows from 802.1aq for the construction of the spanning trees used in this application. This is described in clause 28.5 of [802.1Q]. Allan et al., Expires April 2019 [Page 4] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 3.3.1. Algorithm Basics The key component of the 802.1aq employed is the tie breaking algorithm. The original application of the algorithm was to produce a symmetrically congruent mesh of multicast trees and unicast forwarding whereby the path between any two nodes in the network was symmetric in both directions and congruent for both unicast and multicast traffic. For this application the algorithm is used in the generation of two diversely rooted spanning trees that define the flooding topology. As part of tree construction, the algorithm tie breaks between equal cost paths. When a tie is identified as part of a Dijkstra computation, a path-id is constructed for each equal cost path. A path-id is expressed as a lexicographically sorted list of the node- ids in the path. The set of equal cost paths is ranked, and the lowest selected. As an example: Path-id 23-39-44-68-85 is ranked lower than Path-id 23-44-59-63-90 When the path-ids are of unequal length, the path-ids with the fewest hops are ranked superior to the longer paths, and tie breaking is applied to select between the shorter path-ids. This is not expected to apply in the general case of the dense graphs this application is targeted at. The node-ids used would be the loopback address of each node, therefore each path-id will be unique. 3.3.2. Generating Diverse Trees The algorithm includes the concept of an "algorithm-mask", which is a value XOR'd with the node-ids prior to sorting into path IDs and ranking the paths. This permits the construction of diverse trees in a dense topology. Two algorithm masks are used (zero and -1). When computing two trees from the same root, when there are at least two nodes to choose from at each distance from the root, fully diverse trees will be generated. When computing two trees from diverse roots in a tree architecture, diverse nodes will be selected in each tier in the hierarchy as the relay nodes to the next tier. Allan et al., Expires April 2019 [Page 5] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 3.3.3. Desirable Properties Computation Wise The algorithm has the property of permitting the pruning of intermediate state as a Dijkstra progresses as ties can be immediately evaluated, and the all but the selected path removed from further consideration. This is desirable when computing a Dijkstra in a dense graph as all path permutations do not need to be carried forward during computation. This permits the computation to be quite fast. The resulting computational complexity would still be expressed as 2N(lnN). 4. Applying the Algorithm 4.1. Tree Generation Each IGP speaker in the network has knowledge of each of the two spanning tree roots and the algorithm mask associated with each. This memo does not specify how root selection is performed and disseminated through the network, but does discuss selection requirements in section 4.5. Each root has one of the two algorithm masks associated with it. Each participating IGP speaker in the network computes a spanning tree from each the two roots (using the algorithm mask associated with each root) and from that can determine its own role in the flooding topology. The two spanning trees are designated the "low spanning tree" and the "high spanning tree". The spanning trees are a starting point for a redundant topology. Unlike the commonly accepted operation of a spanning tree, in this application the distinction between upstream and downstream adjacencies is important and is an input to how a member node further relays any LSAs received. Upstream member adjacencies are in the direction of a root, and downstream member adjacencies are in the direction away from the root. 4.2. Illustrating the result The following diagram illustrates the general layout of the flooding graph constructed using the algorithm as applied to a bi-partite style of tree (no intra tier links): Allan et al., Expires April 2019 [Page 6] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 Spine +---+ +---+ +---+ +---+ +---+ | a | | b | | c | | d | o o o | z | +---+ +---+ +---+ +---+ +---+ /|\ /|\ \|/ \|/ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | i | |ii | |iii| o o o | x | | 1 | | 2 | | 3 | o o o | n | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ /|\ /|\ /|\ /|\ In the example, there are two tiers of switches. The spine (nodes a..z), and the next tier with two groups of nodes (i..x) and (1..n). The algorithm will select the node with the lowest node ID in each tier as the replicating node for the low spanning tree; 'a' and 'i' for the set of nodes connecting the spine and the next tier. The algorithm will select the nodes with highest node ID in the same set of nodes for the high spanning tree; 'z' and 'n' for the same set of nodes. In the flooding topology: - Node 'a' is connected to nodes i..x and 1..n for the low spanning tree. - Node 'z' is connected to the same set of nodes for the high spanning tree. - Node 'i' is connected to nodes 'a'..'z' for the low spanning tree, and - Node 'n' is connected to the same nodes for the high spanning tree. - All other nodes are bi-connected to the flooding topology If there was a further tier added below nodes i..x, then 'i' and 'x' would be selected as the replicating nodes for the low and high spanning tree respectively. This is similarly true for nodes 1..n. 4.3. Interactions between Participating and Non-Participating Nodes This solution proposes primarily only nodal behaviors with respect to constraining flooding to member adjacencies. To address the scenario Allan et al., Expires April 2019 [Page 7] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 where the participating nodes were a subset of a larger network, it would be necessary to advertise the capability to participate in flood reduction. This would then require that each participating node use this information to be able to identify the set of participating adjacencies and confine the spanning tree computation to the set of participating adjacencies in order to identify local set of member adjacencies. Interactions with non-participant adjacencies would conform to current practice. 4.4. Flooding of LSAs The design of the protocol elements that are flooded is unmodified by this solution. Therefore, there is no additional information available to associate a received LSA with a given tree, nor is such information needed; the two spanning trees are not treated as unique entities in the flooding topology. As per current practice, a node does not relay LSAs that it has already seen. A new LSA received from an upstream member adjacency is flooded on: - All downstream member adjacencies exclusive of the adjacency of arrival, irrespective of which tree the adjacencies are part of. - All non-participant adjacencies A new LSA received from a downstream member adjacency is flooded on: - All other member adjacencies exclusive of the adjacency of arrival irrespective of which tree the adjacencies are part of. - All non-participant adjacencies A new LSA received from a member adjacency where upstream and downstream is ambiguous (it is an upstream member on one of the spanning trees and a downstream member on the other), is flooded on: - All other member adjacencies exclusive of the adjacency of arrival irrespective of which adjacency the links are part of. - All Non-Participant adjacencies Allan et al., Expires April 2019 [Page 8] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 A new LSA received from a non-member adjacency is flooded on all member adjacency irrespective of which tree the adjacencies are part of (see sections 5.1 and 5.5). 4.5. Root Selection The algorithm depends on tie breaking between sets of node IDs to produce diverse paths, therefore it does place some restrictions on root selection. A root SHOULD be selected so that the root"s node-id when XORd with the associated algorithm mask is the lowest ranked node in the local tier in the tree hierarchy. This would be analogous to path-id ranking where the paths were all of length 1. The root MUST NOT be selected such that the node-ID when XORd with the other root"s algorithm mask is the lowest ranked node. This would result in the root also being a transit node for the other spanning tree and produce a scenario whereby a single failure could render both spanning trees incomplete. Roots MUST NOT be directly connected for either of the low or high spanning trees. If the topology does not permit this to be satisfied purely by root selection, then the inter-root adjacency must be pruned from the graph prior to spanning tree computation to ensure that diverse paths between the roots are used. For a true bipartite graph, there are no other restrictions on node selection. For a bipartite graph modified with inter-tier links, the roots MUST be placed in different tiers to ensure a pathological combination of link weights and node-ids does not result in a scenario where a single failure would render the flooding topology incomplete. Other sources of failure may exist that may require an administrative component to root selection. This, for example, would ensure that both roots were not selected from a common shared risk group. See also section 5.5. 4.6. Node Additions A participating node that is added to the topology will initially not be served by the flooding topology. A participating node adjacent to that node is required to treat it as a non-participating node until such time as tree re-optimization has completed. At the end of tree Allan et al., Expires April 2019 [Page 9] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 optimization, typically two adjacent participating nodes will have member adjacencies with the new node, so the ability to flood LSAs between the new node and the flooding topology will have been uninterrupted during the process. 5. Further work 5.1. Thoughts on Coexistence in the Context of a Larger Network A node that had a combination of participating and non-participating adjacencies would be required to do the following: - For any new LSA received on a participating adjacency, in addition to the rules for member adjacencies, it would also flood the LSA on all non-participating adjacencies. - For any new LSA received on a non-participating adjacency, it would flood the LSA on all member adjacencies. This is reflected in the forwarding rules described in section 4.4. 5.1.1. Multiple flooding Domains and the Severing of Flooding Domains It is possible to envision several scenarios whereby there are sets of participating nodes that are not contiguously connected via participating adjacencies in a given IGP domain. 1. A node has been incorrectly configured as a participating node but has no participating adjacencies. 2. A participating node or set of nodes has become severed from the flooding topology but is still connected to other nodes in the network. Nodes in this set would still be able to compute a local extension of the flooding topology, but it would only be useful if the set was sufficiently large that a majority of the nodes were not connected to non-participants. 3. Procedures are designed to permit more than one flooding topology in an IGP domain. In which case participating nodes would have to be administratively configured to associate with a flooding topology instance. 5.2. Thoughts on Flooding Topology Re-Optimization After a topology change, it is desirable that the flooding topology remain stable until the network has stabilized. However a single failure may render one of the spanning trees incomplete, such that a Allan et al., Expires April 2019 [Page 10] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 further single failure could make the flooding topology incomplete. Therefore procedures should include re-optimization of the flooding topology after a topology change. In order to maintain complete coverage it would make sense not to recompute the spanning trees simultaneously. One approach that would appear to make sense to separate in time network convergence, re-optimization of the low spanning tree and re- optimization of the high spanning tree. The ideal would be to reoptimize an incomplete tree first, however this would require the participating nodes to maintain a complete map of all member adjacencies so that a common determination of the most degraded spanning tree and hence the order of re-optimization could be made. 5.3. Thoughts on Node and Network Initialization A participating node at power up will be not be able to establish member links until it has synchronized with the network and the network is stable in the new topology. This suggests it simply treats power up similarly to how a topology change and network re- optimization is treated. The only difference being that it will flood all LSAs received or originated as per current practice until both spanning trees have stabilized. 5.4. Thoughts on Loop Prevention 802.1aq included additional mechanisms to prevent looping, a reverse path forwarding check, and digest exchange across adjacencies to ensure IGP synchronization. Routing LSAs are not relayed if they are a duplicate, therefore destructive looping cannot occur and additional mitigation mechanisms are not required. 5.5. Thoughts on Pathological Failure Scenarios While in a stable fault free network with sufficient mesh density of the types considered, the flooding topology used by this solution would ensure that no single failure rendered both spanning trees incomplete, it is also useful to consider multiple failure scenarios and if they can be mitigated. Preliminary analysis suggests that in a tree network of sufficient mesh density, the only dual link failure that can render the flooding topology incomplete is if a participant node has failures in both Allan et al., Expires April 2019 [Page 11] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 upstream member adjacencies. This can be partially mitigated if the node recognizes this scenario and reverts to flooding on all adjacencies. If the suggested procedures of 5.1.1 above are adopted, surrounding participating nodes that receive the LSA on a non-member adjacency will introduce the LSA into the flooding topology. The pathological scenario is the simultaneous failure of both roots. This does suggest that root selection should place the roots two hops apart so there will be a constituency of participants that would observe a simultaneous failure of both upstream member adjacencies and revert to normal flooding. 6. Acknowledgements The author would like to acknowledge Jerome Chiabaut for his original algorithm work that underpins this memo. 7. Security Considerations For a future version of this document. 8. IANA Considerations This memo requires no IANA allocations 9. References 9.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 9.2. Informative References [802.1Q] 802.1Q (2014) IEEE Standard for Local and Metropolitan Area Networks--Media Access Control (MAC) Bridges and Virtual Bridged Local Area Networks [Li] Li, T., Psenak, P., "Dynamic Flooding on Dense Graphs", IETF work in progress, draft-li-dynamic-flooding-05, June 2018 Allan et al., Expires April 2019 [Page 12] Internet-Draft draft-allan-lsr-flooding-algorithm October 2018 10. Author's Address Dave Allan Ericsson 2455 Augustine Drive Santa Clara, CA 95054 USA Email: david.i.allan@ericsson.com Allan et al., Expires April 2019 [Page 13]