Skip to main content

Use of OSPF-MDR in Single-Hop Broadcast Networks
draft-ietf-ospf-manet-single-hop-mdr-04

The information below is for an old version of the document that is already published as an RFC.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 7038.
Author Richard G. Ogier
Last updated 2015-10-14 (Latest revision 2013-08-07)
RFC stream Internet Engineering Task Force (IETF)
Intended RFC status Experimental
Formats
Reviews
Additional resources Mailing list discussion
Stream WG state WG Document
Document shepherd Acee Lindem
Shepherd write-up Show Last changed 2013-06-04
IESG IESG state Became RFC 7038 (Experimental)
Action Holders
(None)
Consensus boilerplate Unknown
Telechat date (None)
Responsible AD Stewart Bryant
Send notices to (None)
IANA IANA review state Version Changed - Review Needed
IANA action state No IANA Actions
draft-ietf-ospf-manet-single-hop-mdr-04
Network Working Group                                           R. Ogier
Internet-Draft                                         SRI International
Updates: 5614                                             August 7, 2013
Intended status: Experimental
Expires: February 8, 2014

            Use of OSPF-MDR in Single-Hop Broadcast Networks
              draft-ietf-ospf-manet-single-hop-mdr-04.txt

Abstract

RFC 5614 (OSPF-MDR) extends OSPF to support mobile ad hoc networks
(MANETs) by specifying its operation on the new OSPF interface of type
MANET.  This document describes the use of OSPF-MDR in a single-hop
broadcast network, which is a special case of a MANET in which each
router is a (one-hop) neighbor of each other router.  Unlike an OSPF
broadcast interface, such an interface can have a different cost
associated with each neighbor.  The document includes configuration
recommendations and simplified mechanisms that can be used in single-hop
broadcast networks.

Status of this Memo

   This Internet-Draft is submitted 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."

Copyright Notice

   Copyright (c) 2013 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.

Ogier                   Expires February 8, 2014                [Page 1]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

1.  Introduction

   OSPF-MDR [RFC5614] specifies an extension of OSPF [RFC2328, RFC5340]
   to support mobile ad-hoc networks (MANETs) by specifying its
   operation on the new OSPF interface of type MANET.  OSPF-MDR
   generalizes the Designated Router (DR) to a connected dominating set
   (CDS) consisting of a typically small subset of routers called MANET
   Designated Routers (MDRs).  Similarly, the Backup Designated Router
   (BDR) is generalized to a subset of routers called Backup MDRs
   (BMDRs).  MDRs achieve scalability in MANETs similar to the way DRs
   achieve scalability in broadcast networks:

   o  MDRs have primary responsibility for flooding LSAs. Backup MDRs
      provide backup flooding when MDRs temporarily fail.

   o  MDRs allow the number of adjacencies to be dramatically reduced,
      by requiring adjacencies to be formed only between MDR/BMDR
      routers and their neighbors.

   In addition, OSPF-MDR has the following features:

   o  MDRs and BMDRs are elected based on information obtained from
      modified Hello packets received from neighbors.

   o  If adjacency reduction is used (the default), adjacencies are
      formed between MDRs so as to form a connected subgraph.
      An option (AdjConnectivity = 2) allows for additional adjacencies
      to be formed between MDRs/BMDRs to form a biconnected subgraph.

   o  Each non-MDR router becomes adjacent with an MDR called its
      Parent, and optionally (if AdjConnectivity = 2) becomes adjacent
      with another MDR or BMDR called its Backup Parent.

   o  Each router advertises connections to its neighbor routers as
      point-to-point links in its router-LSA. Network-LSAs are not used.

   o  In addition to full-topology LSAs, partial-topology LSAs may be
      used to reduce the size of router-LSAs.  Such LSAs are formatted
      as standard LSAs, but advertise links to only a subset of
      neighbors.

   o  Optionally, differential Hellos can be used, which reduce
      overhead by reporting only changes in neighbor states.

   This document describes the use of OSPF-MDR in a single-hop broadcast
   network, which is a special case of a MANET in which each router is a
   (one-hop) neighbor of each other router.  An understanding of
   [RFC5614] is assumed.  Unlike an OSPF broadcast interface, such an
   interface can have a different cost associated with each neighbor.
   An example use case is when the underlying radio system performs
   layer-2 routing, but has a different number of (layer-2) hops to

Ogier                   Expires February 8, 2014                [Page 2]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

   (layer-3) neighbors.

   The rationale for using this interface type for single-hop broadcast
   networks, instead of a broadcast interface type, is to represent the
   underlying network in a point-to-multipoint manner, allowing each
   router to advertise different costs to different neighbors in its
   router-LSA.  In this sense, this document shows how the OSPF-MDR
   interface type can be configured (and simplified if desired) to
   achieve the same goals as the OSPF Hybrid Broadcast and Point-to-
   Multipoint interface type [RFC6845].

   Section 2 describes the operation of OSPF-MDR in a single-hop
   broadcast network with recommended parameter settings.  Section 3
   describes an alternative procedure which may be used to decide which
   neighbors on a single-hop broadcast network to advertise in the
   router-LSA.  Section 4 describes a simplified version of the MDR
   selection algorithm for single-hop networks.

   The alternative procedure of Section 3 and the simplified algorithm
   of Section 4 are optional and MUST NOT be used if it is possible for
   two routers in the network to be more than one hop from each other.

1.1.  Terminology

   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].

2.  Operation in a Single-Hop Broadcast Network

   When OSPF-MDR is used in a single-hop broadcast network, the
   following parameter settings and options (defined in [RFC5614])
   should be used:

   o  AdjConnectivity SHOULD be equal to 2 (biconnected); this provides
      the smoothest transition when one router replaces another as MDR,
      since the set of adjacencies forms a biconnected network which
      remains connected during the transition.

   o  AdjConnectivity MAY be equal to 1 (uniconnected), resulting in a
      slightly less smooth transition since adjacencies must be formed
      between the new MDR and all of its neighbors.

   o  AdjConnectivity SHOULD NOT be equal to 0 (full topology) since
      this requires adjacencies to be formed between all pairs of
      routers, adding unnecessary message overhead.

   o  An adjacency SHOULD be eliminated if neither the router nor
      the neighbor is an MDR or BMDR (see Section 7.3 of [RFC5614]).

Ogier                   Expires February 8, 2014                [Page 3]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

   o  LSAFullness MUST be equal to 4 or 5 if full-topology LSAs are
      required. (The value 5 is defined in Section 3 of this document.)

   o  LSAFullness MAY be equal to 1 (min-cost LSAs) if full-topology
      LSAs are not required.  This option reduces the number of
      advertised links while still providing shortest paths.

   If AdjConnectivity equals 1 or 2 and full-topology LSAs are used,
   OSPF-MDR running on a single-hop broadcast network has the following
   properties:

   o  A single MDR is selected, which becomes adjacent with every other
      router, as in an OSPF broadcast network.

   o  Two BMDRs are selected.  This occurs because the MDR selection
      algorithm ensures that the MDR/BMDR backbone is biconnected.
      If AdjConnectivity = 2, every non-MDR/BMDR router becomes adjacent
      with one of the BMDRs in addition to the MDR.

   o  When all adjacencies are fully adjacent, the router-LSA for each
      router includes point-to-point (type 1) links to all bidirectional
      neighbors (in state 2-Way or greater).

3. Originating Router-LSAs

   A router running OSPF-MDR with LSAFullness = 4 includes in its
   router-LSA point-to-point (type 1) links for all fully adjacent
   neighbors, and for all bidirectional neighbors that are routable.  A
   neighbor is routable if the SPF calculation has produced a route to
   the neighbor and a flexible quality condition is satisfied.

   This section describes an alternative procedure which MAY be used
   instead of the procedure described in Section 6 of [RFC5614], to
   decide which neighbors on a single-hop broadcast network to advertise
   in the router-LSA.  The alternative procedure will correspond to
   LSAFullness = 5, and is interoperable with the other choices for
   LSAFullness.  This procedure avoids the need to check whether a
   neighbor is routable, and thus avoids having to update the set of
   routable neighbors.

   If LSAFullness = 5, then the Selected Advertised Neighbor Set (SANS)
   is the same as specified for LSAFullness = 4, and the following steps
   are performed instead of the first paragraph of Section 9.4 in
   [RFC5614].

   (1) The MDR includes in its router-LSA a point-to-point (type 1) link
       for each fully adjacent neighbor.  (Note that the MDR becomes
       adjacent with all of its neighbors.)

   (2) Each non-MDR router includes in its router-LSA a point-to-point

Ogier                   Expires February 8, 2014                [Page 4]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

       link for each fully adjacent neighbor, and, if the router is
       fully adjacent with the MDR, for each bidirectional neighbor j
       such that the MDR's router-LSA includes a link to j.

   To provide rationale for the above procedure, let i and j be two non-
   MDR routers.  Since the SPF calculation (Section 16.1 of [RFC2328])
   allows router i to use router j as a next hop only if router j
   advertises a link back to router i, routers i and j must both
   advertise a link to each other in their router-LSAs before either can
   use the other as a next hop.  Therefore, the above procedure for non-
   MDR routers (Step 2) implies there must exist a path of fully
   adjacent links between i and j (via the MDR) in both directions
   before this can happen.  The above procedure for non-MDR routers is
   similar to one described in Section 4.6 of [RFC6845] for non-DR
   routers.

4. MDR Selection Algorithm

   The MDR selection algorithm of [RFC5614] simplifies as follows in
   single-hop networks.  The resulting algorithm is similar to the DR
   election algorithm of OSPF, but is slightly different (e.g., two
   Backup MDRs are selected).  The following simplified algorithm is
   interoperable with the full MDR selection algorithm.

   Note that lexicographic order is used when comparing tuples of the
   form (RtrPri, MDR Level, RID).  Also note that each router will form
   adjacencies with its parents and dependent neighbors.  In the
   following, the term "neighbor" refers to a bidirectional neighbor (in
   state 2-Way or greater).

   Phase 1 (creating the neighbor connectivity matrix) is not required.

   Phase 2: MDR Selection

   (2.1) The set of Dependent Neighbors is initialized to be empty.

   (2.2) If the router has a larger value of (RtrPri, MDR Level, RID)
         than all of its (bidirectional) neighbors: the router selects
         itself as an MDR, selects its BMDR neighbors as Dependent
         Neighbors if AdjConnectivity = 2, then proceeds to Phase 4.

   (2.3) Otherwise, if the router's MDR Level is currently MDR, then it
         is changed to BMDR before executing Phase 3.

   Phase 3: Backup MDR Selection

   (3.1) Let Rmax be the neighbor with the largest value of (RtrPri, MDR
         Level, RID).

   (3.2) Determine whether or not there exist two neighbors, other than

Ogier                   Expires February 8, 2014                [Page 5]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

         Rmax, with a larger value of (RtrPri, MDR Level, RID) than the
         router itself.

   (3.3) If there exist two such neighbors, then the router sets its MDR
         Level to MDR Other.

   (3.4) Else, the router sets its MDR Level to BMDR, and if
         AdjConnectivity = 2, adds Rmax and its MDR/BMDR neighbors as
         Dependent Neighbors.

   (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing
         from MDR Other to BMDR, then execute Step 2.2 again before
         proceeding to Phase 4.  (This is necessary because running Step
         2.2 again can cause the MDR Level to change to MDR.)

   Phase 4: Parent Selection

   Each router selects a Parent and (if AdjConnectivity = 2) a Backup
   Parent for the single-hop broadcast network.  The Parent for a non-
   MDR router will be the MDR.  The Backup Parent for an MDR Other, if
   it exists, will be a BMDR.  Each non-MDR router becomes adjacent with
   its Parent and its Backup Parent, if it exists.  The parent selection
   algorithm is already simple, so a simplified version is not given
   here.

   The Parent and Backup Parent are analogous to the Designated Router
   and Backup Designated Router interface data items in OSPF.  As in
   OSPF, these are advertised in the DR and Backup DR fields of each
   Hello sent on the interface.

5. Security Considerations

   This document describes the use of OSPF-MDR in a single-hop broadcast
   network, and raises no security issues in addition to those already
   covered in [RFC5614].

6. IANA Considerations

   This document has no IANA considerations.

7. Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC5340]  Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF

Ogier                   Expires February 8, 2014                [Page 6]
Internet-Draft  OSPF-MDR in Single-Hop Broadcast Networks    August 2013

              for IPv6", RFC 5340, July 2008.

   [RFC5614]  Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET)
              Extension of OSPF Using Connected Dominating Set (CDS)
              Flooding", RFC 5614, August 2009.

8. Informative References

   [RFC6845]  Sheth, N., L. Wang, and J. Zhang, "OSPF Hybrid Broadcast
              and Point-to-Multipoint Interface Type", RFC 6845, January
              2013.

Author's Address

   Richard G. Ogier
   Email: ogier@earthlink.net

Ogier                   Expires February 8, 2014                [Page 7]