Internet DRAFT - draft-ogier-manet-ospf-mdr-ext
draft-ogier-manet-ospf-mdr-ext
OSPF/MANET Working Groups R. Ogier
Internet-Draft January 16, 2006
Expires: July 16, 2006
Extension of OSPF-MDR to Allow Option of Using MPRs
draft-ogier-manet-ospf-mdr-ext-00.txt
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-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on July 16, 2006.
Copyright Notice
Copyright (C) The Internet Society (2006).
Abstract
This document describes an extension of OSPF-MDR which allows the
option of using multipoint relays (MPRs) to select the MANET
Designated Routers (MDRs), which form a CDS used for flooding LSAs.
This extension allows each router to decide independently whether or
not to select MPRs, so it provides additional flexibility without
having to specify OSPF-MDR so that it either requires or prohibits
MPRs. The use of MPRs in OSPF-MDR may provide some advantages (e.g.,
a CDS with a smaller stretch factor), although this may come with
some costs in terms of overhead and/or response time. Simulations
are planned to compare the performance of OSPF-MDR with and without
MPRs.
Ogier Expires July 16, 2006 [Page 1]
Internet-Draft MANET Extension of OSPF January 2006
1. Introduction
OSPF-MDR [OSPF-MDR] is an extension of OSPF which supports the new
MANET interface type, in addition to the interface types already
supported by OSPF. OSPF-MDR performs flooding along a connected
dominating set (CDS), consisting of MANET Designated Routers (MDRs)
and Backup MDRs, which generalize the notion of the Designated Router
(DR) and Backup DR to multi-hop wireless networks. To reduce the
number of adjacencies, in OSPF-MDR only a subset of neighbor pairs
(links) form adjacencies, which are selected to ensure the set of
adjacencies (called the adjacency subgraph) is connected and spans
all routers. This is accomplished by ensuring that the MDRs together
with the adjacencies between them form a connected backbone, and by
having each non-MDR router form an adjacency with at least one MDR
neighbor (its parent). The configurable parameter AdjConnectivity
can be set to 1 or 2, which ensures the adjacency subgraph is
connected or biconnected, respectively. OSPF-MDR has been shown to
scale to more than 100 nodes [Boeing].
In OSPF-MDR, MDRs select themselves based on 2-hop neighbor
information, using an MDR selection algorithm which generalizes the
DR election algorithm of OSPF. MDRs are selected persistently, i.e.,
preference is given to existing MDRs when selecting new MDRs, which
improves CDS stability and adjacency lifetimes. This reduces the
rate at which new adjacencies are formed, which is important since
database exchange must be performed whenever a new adjacency is
formed.
In the INRIA report [INRIA02], an algorithm is described in which a
CDS is selected by pruning MPRs. Simulations presented in the INRIA
report [INRIA05] indicate that the resulting MPR-based CDS may
provide more robust flooding than a CDS obtained using an algorithm
in which CDS nodes select themselves based on 2-hop neighbor
information, similar to the one used by OSPF-MDR with the parameter
MDRConstraint set to infinity.
This document describes an extension of OSPF-MDR that uses an
adaptation of the MPR-based CDS algorithm to select MDRs. Backup
MDRs are also selected based on Backup MPRs. Since it is important
to minimize the rate at which new adjacencies are formed, the MPRs
and adjacencies must be selected in a way that achieves this goal.
Several different methods and variations were compared via
simulations, and the methods described in this draft achieved
approximately the lowest rate of new adjacencies among the methods
compared. (We note that it is possible to use any MPR selection
algorithm, such as the one described in [OLSR], but the variation
described in this document achieves a lower rate of new adjacencies.)
Ogier Expires July 16, 2006 [Page 2]
Internet-Draft MANET Extension of OSPF January 2006
The extension described in this document requires changes to the MDR
selection algorithm described in Section 5 of [OSPF-MDR], which
includes the selection of MDRs and Backup MDRs, the selection of
dependent neighbors, and the selection of parents. (Dependent
neighbors and parents are used to determine which neighbors should
become adjacent.) The extension also requires MPRs and Backup MPRs
to be selected as described in this document, and to be reported in
Hellos via a new MPR TLV. (We note, however, that any router may
choose not to select and report MPRs.) No change is required to the
other procedures of OSPF-MDR, including the origination and flooding
of LSAs.
2. Changes to MDR Selection Algorithm to Use MPRs
This section describes the changes to the MDR selection algorithm in
Section 5 of [OSPF-MDR] to use MPRs if some or all neighbors are
selecting and reporting MPRs. If no neighbor is reporting MPRs, then
there is no change to the MDR selection algorithm of [OSPF-MDR]. The
selection of MPRs and Backup MPRs is described in Section 3.
The MDR selection algorithm is used to select (Backup) MDRs, (Backup)
Dependent Neighbors, and (Backup) Parents. If AdjConnectivity = 1,
then each MDR will become adjacent with each Dependent Neighbor that
is an MDR, forming a connected backbone, and each non-MDR will become
adjacent with its Parent. If AdjConnectivity = 2, then each (Backup)
MDR will become adjacent with each (Backup) Dependent Neighbor that
is a (Backup) MDR, forming a biconnected backbone, and each MDR Other
will become adjacent with its Parent and Backup Parent.
The following subsections describe the changes to each of the four
phases of the MDR selection algorithm. The changes to Phases 1 and 4
are independent of MPRs; they are improvements to OSPF-MDR that are
applicable whether or not MPRs are used.
For convenience, in the following description, the term "neighbor"
will refer to a neighbor on the MANET interface that is bidirectional
(in state 2-Way or greater).
2.1 Phase 1: Creating the Neighbor Connectivity Matrix
The Neighbor Connectivity Matrix (NCM) is created as described in
[OSPF-MDR]. However, a router MAY use 2-hop adjacency information if
it is available (see Phases 2 and 3). Such information is obtained
from Hellos via a new optional Adjacent Neighbor List (ANL) TLV. The
ANL specifies which neighbors are adjacent (in state Exchange or
above), and is similar to the Reported Neighbor List (RNL) TLV, which
specifies which neighbors are bidirectional. The set of all ANLs
Ogier Expires July 16, 2006 [Page 3]
Internet-Draft MANET Extension of OSPF January 2006
from all bidirectional neighbors represents the 2-hop adjacency
information.
2.2 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 (MDR Level, RtrPri, RID)
than all of its neighbors, then the router selects itself as an
MDR, and selects all of its neighbors as Dependent Neighbors.
Else, proceed to Step 2.3.
(2.3) Let Rmax be the neighbor that has the largest value of (MDR
Level, RtrPri, RID). If Rmax is not reporting MPRs, then
perform Phase 2 of the MDR selection algorithm of [OSPF-MDR].
Else, proceed to Step 2.4.
(2.4) If Rmax has not selected the router as an MPR, then the router
does not select itself as an MDR, and selects no Dependent
Neighbors. Else, the router selects itself as an MDR, selects
Rmax as a Dependent Neighbor, and proceeds to Step 2.5.
(2.5) For each neighbor k that is not a neighbor of Rmax, the router
selects k as a Dependent Neighbor if and only if both of the
following conditions are satisfied:
(a) There does not exist a neighbor j that is also an MPR of
Rmax, is a neighbor of node k, and has a larger value of (MDR
Level, RtrPri, RID) than the router itself.
(b) If 2-hop adjacency information is available, there does not
exist a path of at most MDRConstraint hops from Rmax to node
k, which does not go through the router itself and which uses
only links between adjacent neighbors (based on the 2-hop
adjacency information).
2.3 Phase 3: Backup MDR Selection
(3.1) If Rmax is not reporting MPRs (and Backup MPRs), then perform
Phase 3 of the MDR selection algorithm of [OSPF-MDR]. Else,
proceed to Step 3.2.
(3.2) If Rmax has selected the router as a Backup MPR, then the
router selects itself as a Backup MDR. If the router has not
selected itself as an MDR or a Backup MDR, or if
AdjConnectivity = 1, then Backup Dependent Neighbors are not
required, so proceed to Phase 4. Otherwise, proceed to Step
3.3.
Ogier Expires July 16, 2006 [Page 4]
Internet-Draft MANET Extension of OSPF January 2006
(3.3) If the router has selected itself as a Backup MDR, then it
selects Rmax as a Backup Dependent Neighbor.
(3.4) For each neighbor k that is not a neighbor of Rmax, the router
selects k as a Backup Dependent Neighbor if and only if k has
not already been selected as a Dependent Neighbor and both of
the following conditions are satisfied:
(a) There do not exist two neighbors that are MPRs of Rmax, are
neighbors of node k, and have larger values of (MDR Level,
RtrPri, RID) than the router itself.
(b) If 2-hop adjacency information is available, there do not
exist two node-disjoint paths (of any length) from Rmax to
node k, which do not go through the router itself and which
use only links between adjacent neighbors (based on the 2-hop
adjacency information).
If AdjConnectivity = 1, then the following alternative
version of Phase 3 will also be investigated. In this
version, Backup MPRs are not required, and each router that
is not an MDR selects itself as a Backup MDR.
2.4. Phase 4: Selection of the Parent and Backup Parent
Each router selects (for each MANET interface) a Parent, which will
be the router itself if the router is an MDR, and will otherwise be a
neighboring (Backup) MDR if one exists. Each router that is not an
MDR also selects a Backup Parent, which will be the router itself if
the router is a Backup MDR, and will otherwise be a neighboring
(Backup) MDR if one exists that is not the Parent. If
AdjConnectivity = 1, then each router that is not an MDR forms an
adjacency with its parent. If AdjConnectivity = 2, then each MDR
Other forms adjacencies with both of its parents.
One property of the (Backup) Parent is that it always has a larger
value of (MDR Level, RtrPri, RID) than the router itself (unless it
is equal to the router itself). Thus, the directed graph defined by
the parent relationship will not contain any cycles. All paths in
this directed graph lead to an MDR that has a larger value of (MDR
Level, RtrPri, RID) than all of its neighbors.
For a given MANET interface, let Rmax denote the router with the
largest value of (MDR Level, RtrPri, RID) among all bidirectional
neighbors, if such a neighbor exists that has a larger value of (MDR
Level, RtrPri, RID) than the router itself. Otherwise, Rmax is null.
If the calculating router has selected itself as an MDR, then its
Ogier Expires July 16, 2006 [Page 5]
Internet-Draft MANET Extension of OSPF January 2006
Parent is equal to the router itself, and its Backup Parent is Rmax.
If the calculating router has selected itself as a Backup MDR, then
its Backup Parent is equal to the router itself, and its Parent
depends on AdjConnectivity. If AdjConnectivity = 2, its Parent is
equal to Rmax. (This is necessary to ensure the backbone is
biconnected.) If AdjConnectivity = 1, then the Parent of a Backup
MDR is selected to be be any MDR neighbor, with preference given to
routers that are already adjacent. (This helps to reduce the rate of
new adjacencies.) If no adjacent MDR neighbor exists, then the
Parent is selected to be the neighbor with the largest value of (MDR
Level, RtrPri, RID).
If the calculating router is an MDR Other, then its Parent is
selected to be any (Backup) MDR neighbor, with preference given to
routers that are already adjacent. If no adjacent (Backup) MDR
neighbor exists, then the Parent is selected to be the neighbor with
the largest value of (MDR Level, RtrPri, RID). The Backup Parent is
then selected to be any (Backup) MDR neighbor other than the Parent,
with preference given to routers that are already adjacent.
3. Selection of MPRs
Although any MPR selection algorithm can be used, such as the one
described in [OLSR], the algorithm described in this section is
designed to maximize the stability of adjacencies when the MDR
selection algorithm in Section 2 is used.
The algorithm selects MPRs and Backup MPRs. Backup MPRs guarantee
not only that each 2-hop neighbor is covered by at least two (Backup)
MPRs, but also guarantee that each 1-hop neighbor is covered by at
least one (Backup) MPR (not including the neighbor itself). This is
necessary to provide a redundant path to each neighbor, in order to
ensure biconnectivity.
The algorithm has four main steps: (1) adding MPRs, (2) adding Backup
MPRs, (3) changing redundant MPRs to Backup MPRs, and (4) removing
redundant Backup MPRs.
(1) The list of MPRs and the list of Backup MPRs are initially empty.
For each neighbor j, in order of decreasing (MDR Level, RtrPri,
RID): If j covers any 2-hop neighbor that is not yet covered by a
selected MPR, then select j as an MPR.
(2) For each neighbor j that has not been selected as an MPR, in
order of decreasing (MDR Level, RtrPri, RID): If j covers any
2-hop neighbor that is not yet covered by at least two selected
Ogier Expires July 16, 2006 [Page 6]
Internet-Draft MANET Extension of OSPF January 2006
(Backup) MPRs, or j covers any 1-hop neighbor that is not yet
covered by at least one selected (Backup) MPR, then select j as a
Backup MPR.
(3) For each selected MPR j, in order of increasing (MDR Level,
RtrPri, RID): If every 2-hop neighbor that is covered by j is
also covered by another selected MPR, then change j from an MPR
to a Backup MPR.
(4) For each selected Backup MPR j whose MDR Level is 0 (MDR Other),
in order of increasing (RtrPri, RID): If every 2-hop neighbor
that is covered by j is also covered by at least two other
selected (Backup) MPRs, and every 1-hop neighbor that is covered
by j is also covered by at least one other selected (Backup) MPR,
then remove j from the list of selected Backup MPRs.
Note that a redundant Backup MPR is removed in Step 4 only if it is
not a (Backup) MDR. This is done to maximize the stability of
adjacencies.
References
[OSPF-MDR] R. Ogier and P. Spagnolo. "MANET Extension of OSPF using
CDS Flooding", draft-ogier-manet-ospf-extension-06.txt (work in
progress), December 2005.
[Boeing] T.R. Henderson, P.A. Spagnolo, and G. Pei. "Evaluation of
OSPF MANET Extensions", Boeing Technical Report D950-10897-1,
July 2005.
[INRIA02] C. Adjih, P. Jacquet, and L. Viennot. "Computing connected
dominated sets with multipoint relays", INRIA Research Report
No. 4597, October 2002.
[INRIA05] C. Adjih, E. Baccelli, T. Clausen, and P. Jacquet. "On the
robustness and stability of Connected Dominating Sets", INRIA
Research Report No. 5609, 2005.
[OLSR] T. Clausen and P. Jacquet (ed). "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
Author's Address
Richard G. Ogier
Email: rich.ogier@earthlink.net
Ogier Expires July 16, 2006 [Page 7]
Internet-Draft MANET Extension of OSPF January 2006
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2006). 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.
Ogier Expires July 16, 2006 [Page 8]
