Internet Draft
Network Working Group                                         Alex Zinin
Internet Draft                                                Mike Shand
Expiration Date: January 2001                              Cisco Systems
File name: draft-zinin-flood-opt-00.txt                   July 2000



                         Flooding optimizations
                    in link-state routing protocols

                   draft-zinin-flood-opt-00.txt


Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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. Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time. It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "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.


Abstract

   The flooding algorithm is one of the most important parts of any link
   state routing protocol. It ensures that all routers within a link
   state domain converge on the same topological information within a
   finite period of time. To ensure reliability, typical implementations
   of the flooding algorithm send new information via all interfaces
   other than the one the new piece of information was received on. This
   redundancy is necessary to guarantee that flooding is performed
   reliably, but implies considerable overhead of utilized bandwidth and
   CPU time if neighboring routers are connected with more than one
   link.  This document describes a method that reduces this overhead.




Zinin, Shand                                                    [Page 1]





INTERNET DRAFT           Flooding optimizations                July 2000


1 Introduction

   In order to guarantee convergence of a link state routing protocol,
   it is vital to ensure that link state PDUs (LSAs in the case of OSPF
   [Ref1] or LSPs in the case of ISIS [Ref2]) that are originated after
   the initial LSDB synchronization between neighbors is completed are
   delivered to all routers within the flooding scope limits (an area or
   the whole AS depending on the protocol and the type of the link state
   PDU).

   The method used by link state protocols to achieve this implies that
   a) PDUs are transmitted reliably between any pair of routers, and b)
   whenever a new PDU is received, it is sent across all interfaces
   other than the one it was received on (except for the case when the
   router is the DR in OSPF, where the LSA is sent back over the same
   interfaces, see [Ref1]).

   To fulfil the first requirement, link state routing protocols keep
   retransmitting new PDUs to the neighbors that have not acknowledged
   reception (the only exception is flooding performed on broadcast
   links in ISIS, see [Ref2]). As an example, in OSPF, a link state
   retransmission list is maintained for every neighbor data structure
   on every interface. When an LSA is sent through an interface, it is
   put on the retransmission list of every neighbor associated with this
   interface and is removed from it only after the neighbor has
   acknowledged reception of the LSA. Similarly, ISIS implementations
   use SRMflag and SSNflag that are interface-specific, as well as
   periodical CSNP announcements on broadcast links to ensure
   reliability of flooding.

2 Motivation

   If multiple links connect two routers, flooding of new information
   will cause considerable overhead of link bandwidth and CPU time spent
   by the protocol. Let's consider an example shown in Figure 1.


                            |                |
                            |   _____ 1 ___  |
                      -|   +--+/  .      . \+--+  |-
                       |---|R1|   :      :  |R2|--|
                      -|   +--+\_____ N ___/+--+  |-
                            |                |
                            |                |
                         Figure 1. Sample topology


   When R1 receives a new PDU from its LAN segment, it installs it in



Zinin, Shand                                                    [Page 2]





INTERNET DRAFT           Flooding optimizations                July 2000


   its LSDB and submits for flooding through all of its interfaces.
   Since flooding presumes sending the new PDU over all interfaces
   except for the one it was received on routers end up doing the
   following.

      1) R1 sends not one, but N copies of the new PDU to R2.

      2) Only the first copy of the PDU is actually installed
         in R2's LSDB, but link bandwidth and CPU cycles are
         spend to transmit and process all N copies.

      3) Furthermore, when R2 receives the first copy of the LSA
         and installs it, it floods back to R1 N-1 copies of it,
         again spending extra bandwidth and CPU time.

      4) If R1 receives an acknowledgment from R2 on some links,
         but not from others, it will keep retransmitting unacknowledged
         LSAs though they are already in R2's LSDB.

   The solution described in this document provides a technique to
   minimize the overhead that link state routing protocols cause in the
   described situation and use link bandwidth more efficiently.

3 Proposed solution

   3.1 Introduction

   The main idea of the technique described in this document is to move
   the flooding algorithm from the per-interface to per-neighbor basis
   in a backward-compatible manner.

   The technique is generic for all protocols utilizing reliable
   flooding and is based on the observation that the ultimate goal of
   the flooding algorithm is not to send link state PDUs over all
   interfaces, but to deliver them to all routers in the network.

   To implement this optimization, it is necessary to maintain a list of
   neighbors within an area. Whenever a new neighbor is discovered on an
   interface belonging to the area, the corresponding interface neighbor
   data structure is linked to the corresponding element in the list of
   neighbors. Based on the information in the list of neighbors, as well
   as on the type of interfaces they use, interfaces within the area are
   marked either flooding-active or flooding-passive. The process of
   election of flooding-active interfaces takes into consideration the
   costs of interfaces, giving preference to faster interfaces.
   Multiaccess interfaces need special treatment, since they may be
   (usually are) associated with more than one neighbor.  However, if
   such an interface connects only two routers, it still may be marked



Zinin, Shand                                                    [Page 3]





INTERNET DRAFT           Flooding optimizations                July 2000


   as flooding-passive. Whenever the number of entries in the list or
   state of the adjacency in the list changes, the interface election
   algorithm is rerun.

   Note that since flooding paradigm is changed from the per-interface
   to per-neighbor basis, PDU retransmission is not performed for a
   specific neighbor on a specific interface, but is instead done for a
   specific neighbor in general, and it is enough to receive a single
   acknowledgment on any interface for sending router to stop
   retransmitting.

   The asynchronous flooding algorithm is changed to first consider area
   neighbor list and then use available physical interfaces to reliably
   deliver LSAs to the neighbors. Note that if more than one interface
   to a particular neighbor is marked as flooding-active, the flooding
   algorithm may perform equal- or unequal-cost load balancing, flooding
   different PDUs through different links.

   Flooding is also changed not to send PDUs to the sending neighbor via
   other links.

   The initial process of LSDB synchronization is also changed to take
   advantage of multiple links. If a new adjacency is coming up and the
   router can be sure that its LSDB is already synchronized with the
   remote router over other links, the router can speed up the adjacency
   establishment process by sending a empty database description to the
   remote neighbor.  Note that this speeds up the announcement of links
   that come up, since OSPF announces an adjacency only when it reaches
   Full state, i.e., when routers have synchronized their LSDBs. Skiping
   the LSDB synchronization part in ISIS does not speed link
   announcement (since ISIS announces adjacency as soon as two-way
   connectivity has been ensured), but it reduces the amount of time CPU
   spends on processing of CSNPs and LSPs.

   To illustrate the benefits of the described method, consider the
   situation where R1 in Figure 1 has 100 PDUs to flood to R2, and N
   equals 3. Without the described optimization, we would have:


       o    300 copies of PDUs going from R1 to R2

       o    300 LSDB lookups performed by R2

       o    300 acknowledgements coming back from R2

       o    300 lookups on the retransmit list or LSDB by R1 to remove
            acknowledged PDUs




Zinin, Shand                                                    [Page 4]





INTERNET DRAFT           Flooding optimizations                July 2000


       o    200 copies of PDUs coming back from R2 to R1

       o    200 LSDB lookups performed by R1

       o    200 ackowledgments going from R1 to R2

       o    200 lookups on the retransmit list or LSDB by R2 to remove
            acknowledged PDUs

   If described technique is implemented, we would have:

       o    100 copies of PDUs going from R1 to R2 possibly over dif-
            ferent interfaces for faster transmission

       o    100 LSDB lookups performed by R2

       o    100 acknowledgements coming back from R2

       o    100 lookups on the retransmit list or LSDB by R1 to remove
            acknowledged PDUs

       o    no copies of PDUs coming back from R2 to R1

       o    no LSDB lookups performed by R1

       o    no acknowledgments going from R1 to R2

       o    no lookups on the retransmit list or LSDB by R2 to remove
            acknowledged PDUs

3.2 Changes to OSPF

   3.2.1 Data structures

   Some basic modifications to OSPF data structures are necessary to
   implement described solution.

   First of all, a new field is introduced to the area data structure,
   called NeighborList. NeighborList is a list of entries, each contain-
   ing the following fields. Note that the NeighborList entry is created
   when the first neighbor data structure for the neighbor with a par-
   ticular router ID is created within an area.

       o    NeighborID---the router ID of the neighbor connected with
            the calculating router with one or more interfaces.

       o    P2pIntList---list of interfaces that have only one fully
            established adjacency and it is established with the



Zinin, Shand                                                    [Page 5]





INTERNET DRAFT           Flooding optimizations                July 2000


            neighbor identified by the NeighborID (point-to-point and
            virtual links, as well as broadcast and NBMA interfaces con-
            necting only two routers).

       o    P2mpIntList---list of interfaces that have more than one
            fully established adjacency and one of them is established
            with the neighbor identified by the NeighborID (apparently
            NBMA and broadcast networks).

       o    Retransmission list---list of LSAs that must be delivered to
            the remote router using available physical interfaces.

   Note that when a neighbor is reachable over multiple interfaces,
   there will be more than one entry in the above lists of interfaces.

   A new field is introduced to the interface-specific neighbor data
   structure---NeighborEntry. When an instance of interface-specific
   neighbor data structure is created, its NeighborEntry is set to
   reference corresponding entry in the area neighbor list.  Note that
   whenever an adjacency goes to or from Full state, the P2pIntList and
   P2mpIntList of area neighbor data structures corresponding to the
   neighbors reachable through the same interface are modified accord-
   ingly.

   Also, a new field is introduced to the interface data structure,
   called FloodingActive. If the value of this field is TRUE, the inter-
   face is used for flooding. Otherwise the interface is flooding- pas-
   sive and no LSAs are sent over it when asynchronous flooding is per-
   formed. Note that whenever an interface is put on a P2mpIntList of
   any area neighbor data structure, its FloodingActive field is always
   set to TRUE.

   Another field introduced to the interface data structure is LSASent,
   that is used by the flooding procedure (see Section 3.2.3 for more
   details).

   Whenever there is a change in the contents of the P2pIntList or
   P2mpIntList of an area neighbor data structure, the router performs
   election of flooding-active interfaces among the interfaces listed in
   the P2pIntList field.

   Below follows the algorithm describing the election process.  Note
   that this algorithm produces the minimal set of active interfaces.
   Implementations may use different algorithms, but these algorithms
   must not produce a smaller set of interfaces.

   For every entry in the area neighbor list, do the following.




Zinin, Shand                                                    [Page 6]





INTERNET DRAFT           Flooding optimizations                July 2000


       1.   If the P2mpIntList is not empty, go through all interfaces
            in the P2pIntList and mark them flooding-passive by setting
            the FloodingActive interface field to FALSE. (We always
            prefer sending LSAs to multiple neighbors simultaneously).

       2.   Otherwise, among the interfaces in the P2pIntList, set
            FloodingActive field to TRUE for those interfaces that have
            the best interface cost. Set it to FALSE for all other
            interfaces in the list.

3.2.2 Initial LSDB synchronization

   Whenever a neighbor's FSM reaches state ExStart, routers exchange
   database description packets to inform each other about the contents
   of their LSDBs. If at this moment there is at least one full adja-
   cency with the same neighbor going through another interface, the
   router can speed up establishment of the new adjacency by including
   in the DBD packets only those LSAs that are currently in the
   neighbor's retransmission list (if any).

   The implementation may also consider ignoring the contents of
   received database description packets. Howeber, there is some proba-
   bility that already established adjacencies are not quite reliable
   and the other router is trying to deliver some LSAs and the router in
   question misses its chance to get them since its ignoring the DBD
   contents.

   Implementations may also decide to maintain a single link state
   request list per neighbor in an area. This may be used to split the
   Loading process among several links when more than one adjacency is
   coming up simultaneously. Note that in this case, whenever the link
   state request list becomes empty, a LoadingDone event should be gen-
   erated for all adjacencies that are currently in the Loading state.

3.2.3 Asynchronous Flooding

   Asynchronous flooding algorithm is changed as follows. Note that
   changes described below do not affect flooding back to a multiaccess
   interface if the router is the DR. The changes are only in the part
   where LSA is sent over other interfaces.

       If the flooding scope is domain-wide, perform the following for
       all areas. If the flooding scope is area-wide, do the following
       steps only for the area the interface on which the LSA was
       received belongs to.

       Consider every neighbor element in the area neighbor list as fol-
       lows.



Zinin, Shand                                                    [Page 7]





INTERNET DRAFT           Flooding optimizations                July 2000


       1)   If the value of the NeighborID field is equal to the router
            ID of neighbor that sent the LSA to the router, consider the
            next neighbor element (there is no need to send the LSA back
            to the sending router, except for the case when the receiv-
            ing router is the DR and the LSA is flooded back to a
            mutliaccess interface).

       2)   If P2mpIntList is empty, go to step 2. Otherwise do the fol-
            lowing steps

            a)   Put the LSA on the neighbor's retransmission list

            b)   Go through every interface on the P2mpIntList and do
                 the following:

                 o    Compare the LSA being flooded and the one identi-
                      fied by the LSASent field of the interface data
                      structure. If the LSAs are the same, the LSA has
                      already been sent on this interfaces and next
                      interface in P2mpIntList must be considered.

                 o    Send the LSA in a link state update packets set-
                      ting the destination address according to the
                      rules in Section 13 of [Ref1]

                 o    Set LSASent field of the interface data structure
                      to the LSA that has just been sent.

                 c)   Consider the next neighbor element in the area
                      neighbor list.

       3)   If P2pIntList is empty, consider the next neighbor element.
            Otherwise

            a)   Put the LSA on the neighbor's retransmission list

            b)   Go through every interface on the P2pIntList and do the
                 following:

                 o    If the interface FloodingActive flag is clear,
                      skip this interface and consider the next inter-
                      face in the list.

                 o    Send the LSA in a link state update packets set-
                      ting the destination address according to the
                      rules in Section 13 of [Ref1]

            c)   Consider the next neighbor element in the area neighbor



Zinin, Shand                                                    [Page 8]





INTERNET DRAFT           Flooding optimizations                July 2000


                 list.

   Reception of OSPF acknowledgements is modified as follows.

     Whenever a link state acknowledgement is received from a neighbor,
     the corresponding entry in the area neighbor list is located and
     corresponding LSA is removed from the retransmission list.

3.2.4 Retransmitting

   The OSPF implementation should also be modified to perform
   retransmission of LSAs on a per-neighbor basis.

   Normally, the interfaces for LSA retransmission should be selected
   according to the rules used for asynchronous LSA flooding.  However,
   implementations may consider retransmitting LSAs over a bigger set of
   interfaces leading to the neighbor if the minimal interface set is
   suspected to be not sufficient (because of link load, or packet
   drops) to complete LSDB synchronization within a reasonable period of
   time.

3.2.5 Compatibility

   The optimization described above is designed to be backward-
   compatible.  No software modification is necessary for the neighbor-
   ing routers. However, if both routers support the described modifica-
   tions, the advantages will be greater.

3.3 Changes to ISIS

   The changes for IS-IS are similar to those for OSPF.

   Each non-broadcast circuit has associated with it the system ID of
   the neighbor that is adjacent over that circuit. The set of one or
   more circuits with a common neighbor is identified as a group.
   SRMflags are associated with groups rather than circuit. SSNflags
   remain associated with circuits.


   ISO/IEC 10589 describes the setting or clearing of SRMflag or SSNflag
   on a non-broadcast circuit for the following reasons.



     1.   SSNflag is cleared after the transmission of a PSNP over cir-
          cuit C.





Zinin, Shand                                                    [Page 9]





INTERNET DRAFT           Flooding optimizations                July 2000


     2.   A packet has been received on circuit C and a flag on circuit
          C set or cleared as a result.


     3.   A packet has been received on circuit C and the flags on all
          other circuits set or cleared as a result.

     4.   The flags on all circuits are set or cleared.
   These actions are modified as described below. In these descriptions,
   the term Sxxflag refers to either SSNflag or SRMflag.


     1.   SSNflag is cleared after the transmission of a PSNP over cir-
          cuit C.

             Clear the flag on circuit C.

     2.   A packet has been received on circuit C and an Sxxflag on cir-
          cuit C is to be set or cleared as a result. Circuit C is a
          member of group G.

          a.   If an SSNflag is to be cleared, clear ALL SSNflags for
               circuits in group G.

          b.   If an SRMflag is to be cleared, clear the SRMflag for
               group G.

          c.   If an SSNflag is to be set, set the SSNflag for circuit C
               only.

          d.   If an SRMflag is to be set, set the SRMflag for group G.


     3.   A packet has been received on circuit C and the Sxxflags on
          all other circuits are to be set or cleared as a result. Cir-
          cuit C is a member of group G.

          a.   If an SSNflag is to be cleared, clear ALL SSNflags for
               all circuits belonging to groups other than G.

          b.   If an SRMflag is to be cleared, clear ALL SRMflags for
               groups other than G.

          c.   If an SRMflag is to be set, set ALL SRMflags for groups
               other than G.






Zinin, Shand                                                   [Page 10]





INTERNET DRAFT           Flooding optimizations                July 2000


     4.   The flags on all circuits are set or cleared

          a.   If an SSNflag is to be cleared, clear ALL SSNflags for
               all circuits.

          b.   If an SRMflag is to be cleared, clear SRMflags for all
               groups.

          c.   If an SRMflag is to be set, set SRMflags for all groups.


     5    Transmitting a (set of) CSNP(s) over a circuit Q, which is a
          member of group G

               Transmit each CSNP over ONE circuit chosen from group G.
               Different CSNPs in the set of CSNPs MAY be transmitted
               over different circuits in group G.


     6    Transmitting an LSP as a result of SRMflags being set on group
          G.

               Choose ONE circuit from group G, and transmit the LSP
               over that circuit.

   Where a circuit is required to be chosen from within a group, the
   choice made is implementation dependant and may be based on any cri-
   teria, such as bandwidth or management control. The result of the
   choice MAY be different on each occasion.  Implementations may also
   decide to choose no point-to-point links if a neighboring system is
   available via a broadcast circuit, since LSPs need to be flooded
   throught it anyway. It is also possible to treat broadcast circuits
   with only two routers attached as point-to-point circuits.

4 Security issues

   This document does not introduce any new security issues to ISIS or
   OSPF.

5. References

   [Ref1] J. Moy. OSPF version 2. Technical Report RFC 2328, Internet
          Engineering Task Force, 1998. ftp://ftp.isi.edu/in-
          notes/rfc2328.txt.

   [Ref2] ISO, "Intermediate system to Intermediate system routeing
          information exchange protocol for use in conjunction with the
          Protocol for providing the Connectionless-mode Network Service



Zinin, Shand                                                   [Page 11]





INTERNET DRAFT           Flooding optimizations                July 2000


          (ISO 8473)," ISO/IEC 10589:1992.


6 Authors' addresses

   Alex Zinin                    Mike Shand
   Cisco Systems                 Cisco Systems
   150 West Tasman Dr.           4, The Square
   San Jose,CA                   Stockley Park
   95134                         UXBRIDGE
   E-mail: azinin@cisco.com      Middlesex
                                 UB11 1BN, UK
                                 E-mail: mshand@cisco.com






































Zinin, Shand                                                   [Page 12]