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]