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]