Internet DRAFT - draft-allan-lsr-flooding-algorithm

draft-allan-lsr-flooding-algorithm



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]