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

Versions: 00 01

Network Working Group                                        A. Roy, Ed.
Internet-Draft                                             Cisco Systems
Expires: May 27, 2006                                  November 23, 2005

           Adjacency Reduction in OSPF using SPT Reachability

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of 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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on May 27, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2005).


   There is significant overhead in OSPF when a router has to establish
   adjacencies with every peer with whom it can verify 2-way
   connectivity.  OSPF supports the broadcast network type for these
   scenarios, where you only have to peer with the designated router
   (DR).  However,a full mesh of connectivity is required for proper
   operation and this doesn't help in networks with overlapping partial
   meshes of connectivity.  This draft proposes a technique to reduce
   the number of adjacencies based on shortest path tree (SPT)
   reachability information.

Roy                       Expires May 27, 2006                  [Page 1]

Internet-Draft          OSPF Adjacency Reduction           November 2005

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Previous Related Work  . . . . . . . . . . . . . . . . . . . .  4
   3.  Smart Peering  . . . . . . . . . . . . . . . . . . . . . . . .  5
     3.1.  SPT Reachability Heuristics  . . . . . . . . . . . . . . .  5
     3.2.  State Machine  . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Advertise the 2-way link in Router-LSA . . . . . . . . . . . .  7
     4.1.  Unsynchronized Adjacencies . . . . . . . . . . . . . . . .  7
     4.2.  Unsynchronized SPT . . . . . . . . . . . . . . . . . . . .  9
     4.3.  Flooding Considerations  . . . . . . . . . . . . . . . . . 10
     4.4.  Overlapping Relay [OR] election impact . . . . . . . . . . 10
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . . 11
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 12
   7.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
     7.1.  Normative References . . . . . . . . . . . . . . . . . . . 13
     7.2.  Informative References . . . . . . . . . . . . . . . . . . 13
   Appendix A.  Contributors  . . . . . . . . . . . . . . . . . . . . 14
   Appendix B.  Acknowledgments . . . . . . . . . . . . . . . . . . . 15
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 16
   Intellectual Property and Copyright Statements . . . . . . . . . . 17

Roy                       Expires May 27, 2006                  [Page 2]

Internet-Draft          OSPF Adjacency Reduction           November 2005

1.  Introduction

   In OSPF [OSPFV2] [OSPFV3], nodes establish an adjacency by first
   verifying 2-way connectivity between them and then synchronizing
   their link state databases.  Once the peering relationship is
   complete and the adjacency is established, the nodes will continue to
   advertise each other in their LSAs.  As a result, the peers are
   maintained in the link state database and are included in all SPF
   calculations.  During the reliable flooding process, a node must
   ensure that each peer has indeed received the flooded routing update
   via an acknowledgment and retransmission mechanism.

   Consequently, maintaining an adjacency for a particular peer is a
   tradeoff between the added redundancy in routing paths and network
   reachability versus the associated overhead (memory consumption, SPF
   computations, routing overhead, and network convergence).

   Consider the possibility of reducing the number of adjacencies that a
   node maintains without compromising reachability and redundancy.
   This will have direct implications on network scalability and is
   especially attractive in environments where the network topology is
   dynamic.  For example, in a Mobile Ad-Hoc Network (MANET) where nodes
   are mobile and the topology is constantly changing, it seems highly
   desirable to 'intelligently' become adjacent with only selected peers
   and not establish a peering session with every node that comes within
   transmission range.  Selective peering can be particularly useful in
   avoiding the peering process for unstable nodes, i.e., nodes that
   come in and out of transmission range.

Roy                       Expires May 27, 2006                  [Page 3]

Internet-Draft          OSPF Adjacency Reduction           November 2005

2.  Previous Related Work

   The formation of a FULL adjacency requires the discovery (2-way
   relationship) and the database synchronization.  To prevent from
   achieving the FULL state, others have taken the approach of modifying
   link state protocols to use periodic advertisements (instead of a
   database exchange).  The result is that neighbor discovery is still
   required, but routing information is learned over time.  An example
   of this approach is:

   o  OSPFv2 Wireless Interface Type [WINTF]

      *  where the use of periodic advertisements "eliminates the
         formation of full adjacencies on wireless interfaces; all
         neighbor states beyond 2-Way are not reached,and no database
         synchronization is performed".

   What we propose in this specification goes a step further by not
   requiring the formation and maintenance of neighbor state (2-way, or
   other) *and* without changing the route distribution mechanisms in
   the link state protocols.  In other words, the mechanism described is
   completely backwards compatible.

Roy                       Expires May 27, 2006                  [Page 4]

Internet-Draft          OSPF Adjacency Reduction           November 2005

3.  Smart Peering

   Two routers are defined synchronized when they have identical link
   state database.  To limit the number of neighbors that are formed, an
   algorithm is needed to select which neighbors with whom to peer.

   The algorithm MUST provide reachability to every possible destination
   in the network, just like when normal adjacency formation processes
   are used.  We should always peer with a neighbor if it provides our
   only path to currently unreachable destinations.

3.1.  SPT Reachability Heuristics

   The peering decision is really a local matter to a router.  If a
   router can ensure that reachability to other nodes is available
   without bringing up a new adjacency, it can choose not to bring up
   the new adjacency.

   We propose an algorithm which uses the existing information about a
   new neighbor's reachability in the SPT.  If the two routers can
   already reach each other in the SPT, it is not necessary to form an
   adjacency between them.

   The decision to peer or not, is made when a hello is received.  When
   a hello is received from a new neighbor or a neighbor in a state
   lower than Exchange:

   o  A check is made in the link state database to see if the peer is
      already reachable in the SPT.

      *  If the peer is either not known in the SPT or is not reachable,
         we start the Exchange process.

      *  If the peer is reachable than bringing up adjacency with this
         neighbor does not provide reachability to any new destinations.

   Let's take an example of a single OSPF area.  This check would look
   for the neighbor's Router LSA.  If the LSA is present in the database
   and is reachable in the SPT, we have a chance to suppress adjacency

   It's worth noting that as the number of links and redundancy in the
   network is reduced, the likelihood of suboptimal routing increases.

3.2.  State Machine

   The state machine of a basic implementation of this algorithm is
   provided below: An implementation MAY use some heuristics below (step

Roy                       Expires May 27, 2006                  [Page 5]

Internet-Draft          OSPF Adjacency Reduction           November 2005

   (3)), beyond the SPT reachability to decide whether or not it
   considers a new adjacency to be of value.

                        |Receive a hello     |
                    (1) |from a new potential|
                        |neighbor            |
                        |Check to see if there |
                    (2) |is a router LSA from  |----no--(4)form a
                        |the new potential     |          new
                        |neighbor in the link  |          neighbor
                        |state database, which |
                        |is reachable in SPT   |
         (3)                      |
      |                            (3b)........................ |
      |(3a),______________________     |Determine if the      | |
      |    |Determine if the new |     |number of redundant   | |
      |    |link cost is better  |     |paths to the potential| |
      |    |than the current path|     |neighbor is < the     | |
      |    |cost by a configured |     |maximum configured    | |
      |    |amount               |     |value                 | |
      |    '`'''''''''''''''''''''     '`'''''''''''''''''''''' |
      |                       \             /                   |
      |                   .....\.........../....                |
      |                   |User configurable   |                |
      |                   |selection algorithm |                |
      |                   '`'''/'''''''\''''''''                |
      |                       /         \                       |
                            /             \
                     requirements     requirements
                        met              not met
                        /                    \
                       /                      \
           (4) form a new neighbor      (5) do not become

Roy                       Expires May 27, 2006                  [Page 6]

Internet-Draft          OSPF Adjacency Reduction           November 2005

4.  Advertise the 2-way link in Router-LSA

   The technique described in Section 3 minimizes the number of
   adjacencies in highly meshed environments.  This is especially useful
   when the network is in motion and the average adjacency lifetime is

   However, it suffers from an undesirable side effect of limiting the
   number of transit links available to forward traffic.

   An implementation may choose to allow some (or even all) of these
   2-way state neighbors to be announced in the Router-LSA.  Since the
   state remains 2-way, we don't incur control plane (database sync and
   flooding) overhead.  However, advertising the link in the Router-LSA
   makes the link available to the data plane.

   This can be safely done if the neighbor is reachable in a special SPT
   constructed by ignoring any other 2-way links in the network.  This
   optional optimization is described below.

4.1.  Unsynchronized Adjacencies

   If the new neighbor is already reachable in the SPT, there is no
   urgency in doing a full database sync with it.  These are the steps
   we need to perform when a neighbor has reached 2-way state.

   Note that when we say SPT in this section, we mean the special SPT
   constructed based on rules in Section 4.2.

   o  After 2-WayReceived event, check if the neighbor is reachable in
      the SPT.  If yes, mark the neighbor as FULL with respect to link

   o  This means that the router-LSA or network-LSA link corresponding
      to the neighbor is advertised as if the neighbor is FULL.

   o  The adjacency information is constructed with U-bit (see below).

   o  Database synchronization is postponed:

      *  By a configured amount of time -OR-

      *  Until the time it's absolutely "necessary"

   In either case, if a database sync is currently pending, it is
   started as soon as we detect the neighbor is no longer reachable in
   the SPT.  The database sync can be done by Out-of-band Sync [OOB],
   which maintains the current adjacency and does the sync in the

Roy                       Expires May 27, 2006                  [Page 7]

Internet-Draft          OSPF Adjacency Reduction           November 2005

   background.  A normal Resync can alternately be done with the
   drawback of adjacency flap.

   In standard OSPF we first bring up adjacency and then announce a
   transit link.  The approach described above will allow the link to be
   used as a forwarding path very quickly and still allows the database
   to be synchronized in a timely fashion when the alternate flooding
   path has recently been broken.

   There is a circular dependency issue which also needs to be resolved.
   Once you start announcing the link, the shortest path will likely be
   via this very link.  So it's non-trivial to detect when the alternate
   dependent path is gone.  What we would like to be able to detect is
   that the neighbor is reachable via a path which doesn't traverse an
   unsynchronized path.

   We have generally solved this class of problems by running an SPF and
   pretending that the link in question doesn't exist.  It doesn't
   require a full SPF, just enough to see if ANY other path is available
   to reach the neighbor.  The worst case is when the alternate path is
   really gone and we find that out by building a full SPT.  This needs
   to be done every time the link state database changes, and for EACH
   link which has SPT dependence for it's viability.  This approach has
   scalability concerns and is not considered further here.

   We can achieve the same results with just ONE additional SPF which is
   capable of ignoring these Unsynchronized links.  The result from this
   SPT can be used to satisfy the reachability condition for ANY number
   of Unsynchronized Adjacencies.  This basically requires that we can
   actually tell the difference between a normal FULL adjacency and this
   new Unsynchronized Adjacency.  We can do this in one of two ways:

   [A] Define LD Options and use a bit in it, as shown below:

Roy                       Expires May 27, 2006                  [Page 8]

Internet-Draft          OSPF Adjacency Reduction           November 2005

      |     Type      |   LD Options  |          Metric               |
      |                      Interface ID                             |
      |                   Neighbor Interface ID                       |
      |                    Neighbor Router ID                         |

                  Link Description in a Router-LSA

      LD Options
         Link Description options. Used to specify some special
         capability or state of a link.

                              |       0     |U|

                                 LD Options

         The "Unsynchronized" bit. This is set if the adjacency is being
         announced before databases are fully synchronized.

      This approach is backward compatible because the only routers
      looking at this bit are those that support the mechanisms
      specified in this document.

   [B] Introducing a new link type in Router-LSA.

      This is a much more complex solution with backward compatibility
      concerns due to the fact that unknown link type handling is not
      defined in OSPF standard [OSPFV2].  Hence this solution isn't
      considered further.

4.2.  Unsynchronized SPT

   Whenever link state changes happen, we need to run ONE additional SPF
   by ignoring all links with U-bit set.  This SPT is then consulted to
   see if any of our Unsynchronized Adjacencies need to start database
   sync.  This SPT is also consulted when a new neighbor goes into 2-way
   to decide if we should form the adjacency immediately or defer it for

Roy                       Expires May 27, 2006                  [Page 9]

Internet-Draft          OSPF Adjacency Reduction           November 2005

4.3.  Flooding Considerations

   One of the main goals in trying to delay the database synchronization
   is to be able to reduce unnecessary OSPF packets traversing these
   links.  Since the unsynchronized Adjacencies remain in 2-way state,
   OSPF updates will not be flooded over the corresponding interfaces
   resulting in additional savings.

   An option is provided to enable or disable flooding over these
   Unsynchronized Adjacencies.  The advantage of allowing flooding is
   being able to use more links for control plane purposes.  We will
   still have the savings of not having to form the adjacency.

4.4.  Overlapping Relay [OR] election impact

   The overlapping relay election algorithm uses the two hop
   neighborhood it gleans from our neighbor's Router-LSAs.  The
   introduction of Unsynchronized Adjacencies needs to be considered in
   the relay election algorithm.

   If flooding is enabled on unsynchronized Adjacencies, no change is
   needed in the relay election algorithm.  If flooding is disabled,
   then the relay election algorithm needs to prune neighbors that are
   connected via an Unsynchronized Adjacency from our 1-hop and 2-hop
   neighbor lists.

Roy                       Expires May 27, 2006                 [Page 10]

Internet-Draft          OSPF Adjacency Reduction           November 2005

5.  Security Considerations

   The function described in this document does not create any new
   security issues for the OSPF protocol.

   Security considerations for the base OSPF protocol are covered in
   [OSPFV2], [OSPFV3] and [OSPFV3SEC].

Roy                       Expires May 27, 2006                 [Page 11]

Internet-Draft          OSPF Adjacency Reduction           November 2005

6.  IANA Considerations

   A new registry is defined for LD Options.

   The values are defined in Section 4.1.  All additions to LD Options
   are subject to OSPF WG review and require IETF standards action.

Roy                       Expires May 27, 2006                 [Page 12]

Internet-Draft          OSPF Adjacency Reduction           November 2005

7.  References

7.1.  Normative References

   [OSPFV2]  Moy, J., "OSPF Version 2", RFC 2328, April 1998.

   [OSPFV3]  Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
             RFC 2740, December 1999.

7.2.  Informative References

   [OOB]      Zinin, A., Roy, A., and L. Nguyen, "OSPF Out-of-band LSDB
              resynchronization", draft-nguyen-ospf-oob-resync-05.txt
              (work in progress), September 2004.

   [OR]       Chandra, M., Baker, F., Cook, D., Retana, A., Roy, A.,
              White, R., and Y. Yang, "Extensions to OSPF to Support
              Mobile Ad Hoc Networking",
              draft-chandra-ospf-manet-ext-xx.txt (work in progress),
              April 2005.

              Gupta, M. and N. Melam, "Authentication/Confidentiality
              for OSPFv3", draft-ietf-ospf-ospfv3-auth-07.txt (work in
              progress), February 2005.

   [WINTF]    Ahrenholz, J., "OSPFv2 Wireless Interface Type",
              draft-spagnolo-manet-ospf-wireless-interface-01.txt (work
              in progress), May 2004.

Roy                       Expires May 27, 2006                 [Page 13]

Internet-Draft          OSPF Adjacency Reduction           November 2005

Appendix A.  Contributors

      These people made significant contributions to the document:

      Dave Cook                         Russ White
      Cisco Systems                     Cisco Systems
      7025-4 Kit Creek Road             7025-4 Kit Creek Road
      RTP, NC 27709                     RTP, NC 27709
      USA                               USA
      Email: dacook@cisco.com           Email: riw@cisco.com

      Alvaro Retana                      Yi Yang
      Cisco Systems                      Cisco Systems
      7025-4 Kit Creek Road              7025-4 Kit Creek Road
      RTP, NC 27709                      RTP, NC 27709
      USA                                USA
      Email: aretana@cisco.com           Email: yiya@cisco.com

      Madhavi W. Chandra                 Acee Lindem
      Cisco Systems                      Cisco Systems
      7025-4 Kit Creek Road              7025-4 Kit Creek Road
      RTP, NC 27709                      RTP, NC 27709
      USA                                USA
      Email: mchandra@cisco.com          Email: acee@cisco.com

Roy                       Expires May 27, 2006                 [Page 14]

Internet-Draft          OSPF Adjacency Reduction           November 2005

Appendix B.  Acknowledgments

   The RFC text was produced using Marshall Rose's xml2rfc tool.

Roy                       Expires May 27, 2006                 [Page 15]

Internet-Draft          OSPF Adjacency Reduction           November 2005

Author's Address

   Abhay Roy (editor)
   Cisco Systems
   170 W. Tasman Dr
   San Jose, CA  95134

   Email: akr@cisco.com

Roy                       Expires May 27, 2006                 [Page 16]

Internet-Draft          OSPF Adjacency Reduction           November 2005

Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at

Disclaimer of Validity

   This document and the information contained herein are provided on an

Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


   Funding for the RFC Editor function is currently provided by the
   Internet Society.

Roy                       Expires May 27, 2006                 [Page 17]

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