[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03

Internet Engineering Task Force                                  H. Chen
Internet-Draft                                                 Futurewei
Intended status: Standards Track                         October 2, 2019
Expires: April 4, 2020


             Intelligent OSPF Link State Database Exchange
               draft-chen-ospf-intelligent-db-exch-03.txt

Abstract

   This document presents an intelligent database exchange mechanism for
   the database exchange procedure in OSPFv2 and OSPFv3.  This mechanism
   is backward compatible.  It eliminates the unnecessary database
   exchanges through using the existing reachability information
   calculated from the link state database and the un-reachability
   information about routers recorded.  It significantly speeds up the
   establishment of the full adjacency between two routers in some
   situations.

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).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on April 4, 2020.

Copyright Notice

   Copyright (c) 2019 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (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



Chen                      Expires April 4, 2020                 [Page 1]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   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.  Eliminating Whole Link State Database Exchange . . . . . .  3
     1.2.  Eliminating Part of Link State Database Exchange . . . . .  4
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Conventions Used in This Document  . . . . . . . . . . . . . .  5
   4.  Intelligent Link State Database Exchange . . . . . . . . . . .  5
   5.  Changes to OSPF Protocols  . . . . . . . . . . . . . . . . . .  5
     5.1.  Changes to Creation of Database Summary List . . . . . . .  6
     5.2.  Changes to Processing of DD Packet Contents  . . . . . . .  6
     5.3.  New Data Structures and Procedures . . . . . . . . . . . .  7
   6.  Some Details about Implementations of New Procedures . . . . .  7
     6.1.  Finding and Recording Failure Time and LSA Change Time . .  8
       6.1.1.  Finding and Recording Failure Time and LSA Change
               Time . . . . . . . . . . . . . . . . . . . . . . . . .  8
       6.1.2.  A Simpler Method for Finding Failure Time  . . . . . .  9
       6.1.3.  Finding and Recording LSA Change Time  . . . . . . . . 10
     6.2.  Reusing LSA Age, Finding and Recording Adjust Time . . . . 11
   7.  Security  Considerations . . . . . . . . . . . . . . . . . . . 11
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 11
   9.  Acknowledgement  . . . . . . . . . . . . . . . . . . . . . . . 12
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 12
     10.2. Informative References . . . . . . . . . . . . . . . . . . 12
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12




















Chen                      Expires April 4, 2020                 [Page 2]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


1.  Introduction

   If a full adjacency is to be formed between two OSPF routers, their
   link state databases will be synchronized through the database
   exchange procedure described in OSPFv2 [RFC2328] and OSPFv3
   [RFC2740].  Each of the routers sends the other the summary of its
   database through a set of Database Description packets containing the
   header of every LSA in its database.  For every LSA header received
   in the Database Description packets, the router compares it with the
   corresponding LSA instance in its database and sends the other router
   a request for the LSA if the LSA instance in its database is older.
   The adjacency becomes full when the router finishes sending the
   summary of its database and processing all the Database Description
   packets from the other router and gets all the LSAs it requested.

1.1.  Eliminating Whole Link State Database Exchange

   In some situations, the whole link state database exchange is
   unnecessary.  For example, in the case illustrated in the figure
   below, we suppose that full adjacencies between routers RT3 and RT4,
   RT4 and RT5, and RT5 and RT6 have been established, and a new full
   adjacency between RT3 and RT6 is to be formed over the link directly
   connecting them.  In this case, RT3 and RT6 are reachable each other
   through RT4 and RT5.  They do not need to exchange their link state
   databases at all since they are reachable each other and already have
   the same database.

                    +
                    | 3+---+                     N12      N14
                  N1|--|RT1|\ 1                    \ N13 /
                    |  +---+ \                     8\ |8/8
                    +         \ ____                 \|/
                               /    \   1+---+8    8+---+
                              *  N3  *---|RT4|------|RT5|
                               \____/    +---+      +---+
                     +         /   |                  |6
                     | 3+---+ /    |                  |
                   N2|--|RT2|/1    |1                 |6
                     |  +---+    +---+6            6+---+
                     +           |RT3|==============|RT6|
                                 +---+              +---+


        Figure 1: A Full Adjacency between RT3 and RT6 to be Formed

   For a large database, eliminating the unnecessary database exchange
   will significantly speed up the establishment of the full adjacency
   and save lots of link bandwidth for the transmission of the



Chen                      Expires April 4, 2020                 [Page 3]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   unnecessary Database Description packets and CPU cycles for the
   processing of the packets.

1.2.  Eliminating Part of Link State Database Exchange

   In some other cases, some part of the database exchange is not
   needed.  For example, in the topology shown in the figure below, when
   the only connection between two routers Rt4 and RT5 is down for a
   short time and then up again, most parts of their link state
   databases are the same and only small parts of the databases may be
   different.  In this case, it is not necessary for these two routers
   to exchange the parts of their databases that are the same.

                    +
                    | 3+---+                     N12      N14
                  N1|--|RT1|\ 1                    \ N13 /
                    |  +---+ \                     8\ |8/8
                    +         \ ____                 \|/
                               /    \   1+---+8    8+---+
                              *  N3  *---|RT4|======|RT5|
                               \____/    +---+      +---+
                     +         /   |                  |6
                     | 3+---+ /    |                  |
                   N2|--|RT2|/1    |1                 |6
                     |  +---+    +---+6            6+---+
                     +           |RT3|              |RT6|
                                 +---+              +---+


         Figure 2: Link between RT4 and RT5 goes Down and then Up

   Another example is in a Mobile Ad-Hoc Network (MANET) where nodes are
   mobile.  When a mobile node moves out of a transmission range and
   into another range in the same OSPF area in a short time, the
   adjacencies to the nodes in the old range will be down and the new
   adjacencies to some nodes in the new range will be established.  In
   this situation, most of their databases are the same.

   This document describes a solution, called an intelligent database
   exchange mechanism, for eliminating the unnecessary database
   exchanges and processes during the establishment of a full adjacency
   between two routers.  This solution is backward compatible.


2.  Terminology

   This document uses terminologies defined in RFC 2328, and RFC 2740.




Chen                      Expires April 4, 2020                 [Page 4]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


3.  Conventions Used in This Document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119.


4.  Intelligent Link State Database Exchange

   The intelligent OSPF Link State database exchange mechanism
   eliminates the unnecessary Database Description packets exchanges and
   processes through using the existing reachability information
   calculated from the link state database and the un-reachability
   information about routers recorded.

   When two OSPF routers are going to bring up a full adjacency between
   them, each of them checks whether it is reachable to the other
   through using its route table calculated from its link state
   database.  If it can reach the other router, it does not need to send
   the other any Database Description packets that contain the summary
   of its database since two routers have the same database.  In this
   case, all the unnecessary Database Description packets exchanges and
   processes are eliminated.  The full adjacency between two routers is
   formed almost immediately.

   If one router can not reach to the other now but it could reach the
   other at time t and the difference between the current time and t is
   less than the LSA maximum age MaxAge (3600 seconds), then it does not
   need to send the other the header of every LSA in its database
   through Database Description packets.  It just needs to send the
   other the headers of the LSAs that have been changed in its database
   since time t at which the other router became unreachable.  During
   the intelligent database exchange, when one router detects that the
   other router was restarted after time t through some way such as
   comparing the router LSA generated by the other router with its
   corresponding LSA instance in its link state database, it stops its
   current intelligent database exchange and starts a new normal
   database exchange with the other router.

   During the intelligent database exchange between two routers, if one
   router detects that the other router becomes unreachable, it stops
   its current intelligent database exchange and starts a new normal
   database exchange with the other router.


5.  Changes to OSPF Protocols

   The changes to the OSPF protocols include three parts.  The first



Chen                      Expires April 4, 2020                 [Page 5]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   part is to modify the creation of the neighbor database summary list.
   The second is to change the processing of a Database Description
   packet contents.  The third is to add some data structures and
   procedures.

5.1.  Changes to Creation of Database Summary List

   In the OSPF protocols, when a local router is going to form a full
   adjacency with a neighboring router, it creates the neighbor database
   summary list that has the contents of its entire area link state
   database.  The area link state database consists of the router-LSAs,
   network-LSAs and summary-LSAs contained in the area structure, along
   with the AS-external-LSAs contained in the global structure.  The
   intelligent database exchange mechanism modifies the creation of the
   summary list as follows:

   If the local router can reach the neighboring router now, then the
   neighbor database summary list is empty; otherwise (i.e., the router
   can not reach the neighboring router now), if the router could reach
   the neighboring router at time t and the difference between the
   current time and t is less than the LSA maximum age MaxAge, then the
   neighbor database summary list must have the contents of the LSAs
   that have been changed in its link state database since time t at
   which the neighboring router became unreachable; otherwise, the
   neighbor database summary list has the contents of its entire area
   link state database.

5.2.  Changes to Processing of DD Packet Contents

   In the original OSPF protocols [RFC2328, RFC2740], when the local
   router accepts a received Database Description Packet as the next in
   sequence, one part of processing of the packet contents is that the
   router looks up the LSA contained in the packet in its database to
   see whether it also has an instance of the LSA.  If it does not, or
   if the database copy is less recent, the LSA is put on the Link state
   request list so that it can be requested in Link State Request
   Packets.  This part of processing of the packet contents is modified
   as follows:

   If the local router can reach the neighboring router now, it does not
   look up any LSA contained in the packet in its database to see
   whether it also has an instance of the LSA or if the database copy is
   less recent.  Otherewise, the local router follows the processing of
   the packet contents as described in OSPF protocols.







Chen                      Expires April 4, 2020                 [Page 6]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


5.3.  New Data Structures and Procedures

   In addition to the above modification, some new data structures and
   procedures should be added to provide the following functions:

   1.  Record function, which records the information about:

       *  Every tuple <r, tu>, where r is the remote router in the
          entire area that became unreachable from the local router at
          time tu and the difference between the current time and tu is
          less than the LSA maximum age MaxAge (3600 seconds).

       *  The time tc for every LSA at which the LSA is changed if there
          exist some remote routers that became unreachable less than
          MaxAge ago.  It is not necessary to record time tc for any LSA
          if there is not any remote router that became unreachable
          within the past MagAge (3600 seconds).

   2.  Retrieve function, which provides the information about:

       *  For a given unreachable remote router r, the time tu at which
          the router r became unreachable.

       *  For a given time tu, all the LSAs in the link state database
          that have been changed since then.  Normally tu is the time
          when a remote router became unreachable.

   3.  Delete function, which removes the information about:

       *  Every tuple <r, tu> when the remote router r becomes reachable
          or the difference between the current time and tu (where tu is
          the time when r became unreachable) is equal to or greater
          than the LSA maximum age MaxAge (3600 seconds).

       *  The time tc for every LSA recorded if there is not any remote
          router that are unreachable.

   During the full adjacency establishment between two routers, either
   of them may restart to form the adjacency in the normal way as
   described in the OSPF protocols [RFC2328] and [RFC2740] if it detects
   that the reachability between them is broken.


6.  Some Details about Implementations of New Procedures

   This section describes some implementation options for the record
   function.  The implementations of the retrieve and delete functions
   depend on the implementation of the record function to some extend



Chen                      Expires April 4, 2020                 [Page 7]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   and should be trivial after the details of the implementation of the
   record function are determined.

   One implementation finds the failure time and LSA change time and
   records them accordingly.  It finds time tu for every remote router r
   at which r became unreachable because some failures happened at time
   tu and records the information about <r, tu>.  It also finds time tc
   for every LSA at which the LSA is changed and records the information
   about tc for the LSA.

   Another implementation reuses some of the existing information in the
   link state database such as LSA age, and finds some other information
   such as failure time and records them.

6.1.  Finding and Recording Failure Time and LSA Change Time

   This subsection specifies two methods for finding the failure time.
   One is more accurate.  The other is simpler.  In addition, it
   describes a method for calculating the time for every LSA at which it
   is changed.

   If a remote router r becomes unreachable from reachable after the
   shortest path first algorithm is run against the link state database,
   then tuple <r, tu> is recorded, where tu is the time at which a
   failure such as a link down happened that leads to the router r
   unreachable.  Failures can be classified into two classes: link/
   interface failures and node failures.  When an OSPF router detects a
   failure, it will regenerate and flood LSAs for the failure.  Suppose
   that ti is the maximum time delay for the OSPF router to detect an
   interface failure and tn is the maximum time delay for the OSPF
   router to detect a node failure.  For an LSA, assume that tp is the
   time delay for the LSA to reach the local router from its origin.

6.1.1.  Finding and Recording Failure Time and LSA Change Time

   For a point to point link failure in the network, two router LSAs
   with the link down are regenerated and flooded.  One is by each of
   two end routers of the link.  For a broadcast link or NBMA link
   failure, one network LSA and one or more router LSAs with the
   information about link down are generated and flooded.  The network
   LSA is generated by the designated router and the router LSAs are
   generated by the routers attached to the link.

   Among these LSAs, suppose that tr is the earliest time at which one
   of the LSAs is received. tp is less than the age of the LSA, which
   can be used as an estimated value of tp.  We can also estimate tp as
   (255 - TTL of the LSA update packet).  We may select the smaller one
   between these two estimated values for tp.  In all these cases, the



Chen                      Expires April 4, 2020                 [Page 8]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   exact tp is less than its estimated value.  The time tu at which the
   interface failed can be estimated as tu = (tr - ti - tp).  The
   estimated value for tu is earlier than the exact time at which the
   failure happened.  This guarantees that all the LSAs that are changed
   after the exact tu will be included in the neighbor database summary
   list if a full adjacency is to be established with router r.

   For n (n > 1) link failures, the time at which each of these n link
   failures happened can be calculated as above.  The time tu is the
   earliest time among all these n times.  If we can identify m (1 <= m
   <= n) link failures among these n link failures that results in the
   remote router r unreachable, we only need to calculate the time at
   which each of those m link failures happened.  In this case, the time
   tu is the earliest time among all those m times.

   For one node failure in the network, every node that has a full
   adjacency with the failed node will regenerate and flood the LSA with
   the link to the failure node down.  Among these LSAs, suppose that tr
   is the earliest time at which one of these LSAs is received and tp is
   the time delay for this LSA to reach the local router from its
   origin, then the time tu at which the node failed can be estimated as
   tu = (tr - tn - tp).  The estimated value for tu is earlier than the
   exact time at which the failure happened.  This guarantees that all
   the LSAs that are changed after the exact tu will be included in the
   neighbor database summary list if a full adjacency is to be
   established with router r.

   For k (k > 1) node failures in the network, there are at most k
   groups of LSAs will be regenerated and flooded in the network.  Every
   LSA in one of these groups contains the information about the link to
   the same failed node down.  For each group of LSAs, the time at which
   the node failed can be estimated in the same way as above for one
   node failure.  The time tu at which the remote router r became
   unreachable because of k node failures is estimated as the earliest
   time among all the estimated node failure times.

   In the case that there are link and node failures in the network, two
   times are estimated in the ways described above.  One time is the
   time at which the earliest link failure happened.  The other is the
   time at which the earliest node failure happened.  The time tu at
   which the remote router r became unreachable because of link and node
   failures is estimated as the earlier between these two times.

6.1.2.  A Simpler Method for Finding Failure Time

   One simpler way for finding failure time uses all the changed LSAs
   received.  It derives the failure time from every LSA in the way
   similar to the ones described above and then selects the earliest



Chen                      Expires April 4, 2020                 [Page 9]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


   time as tu.  For every changed LSA received at time tr, the failure
   time derived from this LSA is (tr - max(ti, tn) - tp), where ti, tn
   and tp are defined above and tp is calculated in the same way as
   described above.

   This method is simpler than the method described in the above
   subsection.  But the failure time it estimated may not be as accurate
   as the one the previous method calculated.  Thus the LSAs changed
   between these two times will be included in the neighbor database
   summary list when a full adjacency is to be created to router r and
   this failure time is used as the unreachable time for router r.
   However, it is not necessary to include these LSAs in the summary
   list.

6.1.3.  Finding and Recording LSA Change Time

   If there exist some remote routers that became unreachable less than
   MaxAge ago, for an LSA, we use the time tr at which the LSA is
   received as the time tc at which the LSA is changed for recording the
   time tc for the LSA.  This time may be a little bit later than the
   exact time at which the LSA is changed.  But it guarantees that the
   LSA will be included in the neighbor database summary list if a full
   adjacency is to be established with a router r that became
   unreachable before the exact tc.

   There are a number of ways for recording the LSA change time.  One
   way is to add a new field similar to the field for LSA age into the
   data structure for storing LSA and store the estimated change time tc
   into this new field for each changed LSA.

   Another way for recording the LSA change time is to add a link field
   into the data structure for storing an LSA, a new array and a
   variable for the index of the array into the data structure for
   storing an area.  The link field is used to link all the LSAs that
   have the same change time together.  The size of the array is the
   number of time units in MaxAge (3600 seconds).  A time unit can be
   one second, 1/10 second or other smaller time unit.  This depends on
   the implementation.  The array and the variable for the index can be
   considered as a relative clock.  The index variable starts from 0,
   and goes up by one every time unit.  When it reaches the size of the
   array, it starts from 0 again.  If the value of the index variable is
   k at the current time, the time tj represented by the element of the
   array at index j is tj = (current time - time unit * d), where d = (k
   - j) if k >= j and d = (array size - j + k) if k < j.  The element of
   the array at index j is a pointer that points to the header of the
   linked list of all the LSAs that are changed at the time tc, where tc
   = tj or (tc + one time unit) > tj if tc < tj (i.e., rounding up tc is
   tj).



Chen                      Expires April 4, 2020                [Page 10]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


6.2.  Reusing LSA Age, Finding and Recording Adjust Time

   For every remote router r that became unreachable at time tu, tu can
   be estimated in one of the ways described above.  For every changed
   LSA received at time tr after time tu, its age is less than 255,
   which is the maximum time to live value in the IP packet containing
   the LSA.  Thus we use tu and reuse the age of an LSA to decide
   whether the LSA is put into the summary list.  When a full adjacency
   to router r is to be created, every LSA that satisfies the condition
   "the age of the LSA < the current time - tu + 255" (i.e., "tu - 255 <
   the current time - the age of the LSA") must be put into the neighbor
   database summary list.  This will guarantee that all the LSAs that
   were changed after the router r became unreachable are included in
   the summary list.  However, some LSAs that were changed before time
   tu may be included.  In order to reduce the number of the LSAs
   changed before time tu to be included, we need to find the earliest
   time te in which the changed LSA was regenerated in term of LSA age.
   Thus we can use te in place of tu - 255 to decide whether an LSA must
   be put into the summary list.  When a full adjacency to router r is
   to be created, every LSA that satisfies the condition "te < the
   current time - the age of the LSA" must be put into the neighbor
   database summary list.

   For each changed LSA received at time tr-i after time tu and before
   time (tu + 255), the time at which the LSA was regenerated is
   estimated as (tr-i - ta-i), where ta-i is the age of the LSA.  The
   time te is the earliest one among all (tr-i - ta-i).

   For the case that another remote router r' became unreachable later
   during the calculation of the time te for router r, we stop finding
   te and s tart to find the earliest time te' for the remote router r'
   in the same way as described above and mark that the time te relies
   on the time te'.  When a full adjacency to router r is to be created,
   the time te is calculated as follows.  It is the earliest time among
   the te partially calculated and the te' that the te depends on.


7.  Security  Considerations

   The mechanism described in this document does not raise any new
   security issues for the OSPF protocols.


8.  IANA Considerations

   This document specifies a backward compatible intelligent link state
   database exchange mechanism for OSPFv2 and OSPFv3, which does not
   require any new number assignment.



Chen                      Expires April 4, 2020                [Page 11]


Internet-Draft       Intelligent OSPF LSDB Exchange         October 2019


9.  Acknowledgement

   The author would like to thank Richard Li, Yang Yu, Steve Yao,
   Quintin Zhao and others for their valuable comments on this draft.


10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/
              RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/
              RFC2328, April 1998,
              <https://www.rfc-editor.org/info/rfc2328>.

   [RFC2740]  Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
              RFC 2740, DOI 10.17487/RFC2740, December 1999,
              <https://www.rfc-editor.org/info/rfc2740>.

10.2.  Informative References

   [RFC5243]  Ogier, R., "OSPF Database Exchange Summary List
              Optimization", RFC 5243, DOI 10.17487/RFC5243, May 2008,
              <https://www.rfc-editor.org/info/rfc5243>.


Author's Address

   Huaimo Chen
   Futurewei
   Boston, MA
   US

   Email: Huaimo.chen@futurewei.com













Chen                      Expires April 4, 2020                [Page 12]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/