Open Shortest Path (OSPF) E. Baccelli Internet-Draft P. Jacquet Expires: April 14, 2008 D. Nguyen INRIA T. Clausen LIX, Ecole Polytechnique, France October 12, 2007 OSPF MPR Extension for Ad Hoc Networks draft-baccelli-ospf-mpr-ext-04 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/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on April 14, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). Baccelli, et al. Expires April 14, 2008 [Page 1] Internet-Draft OSPF MPR Extension for MANET October 2007 Abstract This document specifies an OSPFv3 interface type tailored for mobile ad hoc networks. This interface type is derived from the broadcast interface type, enhanced with MANET techniques based on multi-point relaying (MPR). Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 4. Protocol Overview and Functionning . . . . . . . . . . . . . . 7 4.1. Efficient Flooding with MPR . . . . . . . . . . . . . . . 7 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 7 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 7 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 8 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 9 5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 11 5.2.1. Flooding MPR Selection . . . . . . . . . . . . . . . . 11 5.2.2. Flooding MPR Selection Signalling in HELLO Packets . . 11 5.2.3. Neighbor Ordering in HELLO Packets . . . . . . . . . . 11 5.2.4. Metric Signalling in HELLO Packets . . . . . . . . . . 12 5.2.5. Path MPR Selection . . . . . . . . . . . . . . . . . . 12 5.2.6. Path MPR Selection Signalling in HELLO Packets . . . . 12 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 12 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 5.3.1. Protocol Packets over 2-WAY Links . . . . . . . . . . 13 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 13 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 14 5.4.2. Link State Acknowlements . . . . . . . . . . . . . . . 15 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.1. Normative References . . . . . . . . . . . . . . . . . . . 21 8.2. Informative References . . . . . . . . . . . . . . . . . . 21 Appendix A. Flooding MPR Selection Heuristic . . . . . . . . . . 22 Appendix B. Path MPR Selection Heuristic . . . . . . . . . . . . 24 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 Intellectual Property and Copyright Statements . . . . . . . . . . 28 Baccelli, et al. Expires April 14, 2008 [Page 2] Internet-Draft OSPF MPR Extension for MANET October 2007 1. Introduction This document specifies an extension of OSPFv3 [2] adapted to MANETs [6], based on mechanisms providing: - Flooding reduction: a mechanism reducing the number of (re)transmissions during floods. - Topology reduction: a mechanism reducing the number and the size of LSAs, by advertizing only a subset of the existing links. - Adjacency reduction: a mechanism reducing the database synchronization overhead by bringing up only selected adjacencies. These mechanisms are based on multipoint relaying (MPR), a technique developed in OLSR, the proactive routing solution standardized in MANET [5] [7]. The extension specified in this document integrates the OSPF framework by defining an OSPF interface type: the MANET interface. While this extension enables OSPF to function efficiently on mobile ad hoc networks, operation of OSPF on other types of interfaces or networks remains unaltered, whether there are MANET interfaces in the area or not. Baccelli, et al. Expires April 14, 2008 [Page 3] Internet-Draft OSPF MPR Extension for MANET October 2007 2. Terminology The keywords "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 [3]. Additionally, this document uses traditional OSPF terminology as defined in [1] [2], LLS terminology as defined in [4], as well as the following terms: MANET interface - the OSPF interface type for MANETs, specified in this document. MANET router - a router which has only MANET interface(s). Wired router - a router which only has OSPF interface(s) of types other than MANET. Hybrid router - a router which has OSPF interfaces of several types, including the MANET type. Neighbor - a router, reachable through an OSPF interface (of any type). MANET neighbor - a neighbor, reachable through an OSPF interface of type MANET. Symmetric neighbor - a neighbor, in a state greater than or equal to 2-Way (through an interface of any type). Baccelli, et al. Expires April 14, 2008 [Page 4] Internet-Draft OSPF MPR Extension for MANET October 2007 Symmetric 2-hop neighbor - a symmetric neighbor of a symmetric neighbor, which is not a neighbor of the considered router. Neighborhood - the set formed by the symmetric neighbors of the considered router. 2-hop neighborhood - the set formed by all the symmetric 2-hop neighbors of the considered router. Synch router - a router which brings up adjacencies with all its MANET neighbors. Flooding MPR set - the subset of symmetric neighbors selected as flooding MPR by this router. Flooding MPR selector set - the subset of symmetric neighbors that have selected this router as flooding MPR. Path MPR set - the subset of symmetric neighbors selected as path MPR by this router. Path MPR selector set - the subset of symmetric neighbors that have selected this router as path MPR. MPR (selector) set - the union of the flooding MPR (selector) set and the path (selector) MPR set of this router. Baccelli, et al. Expires April 14, 2008 [Page 5] Internet-Draft OSPF MPR Extension for MANET October 2007 3. Applicability Statement Characteristics of MANETs include mobility and "half-broadcast" capabilities [9], i.e., a router that makes a transmission on a MANET can only assume that a subset of the routers attached to the MANET will hear this transmission. In particular, these characteristics are not compatible with several traditional OSPF mechanisms, including some reducing the amount of control traffic, such as flooding reduction, topology reduction and adjacency reduction (e.g. Designated Router). However, OSPF's efficient operation over MANETs relies on drastic control traffic reduction, as wireless links generally feature bandwidth scarcity and interference issues. The MANET interface type enables OSPF operation on mobile ad hoc networks, by providing specific flooding reduction, topology reduction and adjacency reduction mechanisms adapted to MANET characteristics. These mechanisms are derived from solutions standardized by the MANET working group. However, while MANET standards address optimized ad hoc routing solutions for truely mobile enviromnents, OSPF's extension for ad hoc networks addresses less mobile scenarios, that possibly include parts of the network that are fixed, using solely the traditional OSPF framework. Baccelli, et al. Expires April 14, 2008 [Page 6] Internet-Draft OSPF MPR Extension for MANET October 2007 4. Protocol Overview and Functionning This document specifies an OSPFv3 interface type tailored for mobile ad hoc networks: the MANET interface. The MANET interface makes use of flooding reduction, topology reduction and adjacency reduction mechanisms based on multipoint relaying (MPR), a technique derived from OLSR [5] [7], the proactive routing solution standardized in MANET. 4.1. Efficient Flooding with MPR MANET interfaces use a flooding reduction mechanism called MPR flooding, whereby only some MANET neighbors (those selected as flooding-MPR) are responsible for retransmitting a routing packet flooded over a MANET interface. This mechanism drastically reduces the number of (re)transmissions during flooding procedures, while still providing a natural high resilience to transmission errors (inherent to the use of wireless links), and obsolete two-hop neighbor information (frequently caused by the mobility of the routers). 4.2. MPR Topology Reduction MANET interfaces use a topology reduction mechanisms called MPR topology reduction, whereby only necessary wireless links to MANET neighbors (those concerned by path-MPR selection, as belonging to shortest paths) are listed in LSAs. MANET routers periodically generate and flood Router-LSAs describing their selection of wireless links to (current) MANET neighbors as point-to-point links. This mechanism greatly reduces the size of LSAs originated by MANET routers, while still keeping OSPF's traditional properties: optimal paths using synchronized adjacencies. 4.3. Multicast Transmissions of Protocol Packets In order to reduce the overehead, multicast is used as much as possible for protocol packet transmissions over MANET interfaces, taking advantage of broadcast capabilities of the wireless medium [9]. In particular, LSA acknowledgements are sent via multicast over these interfaces, and retransmissions over the same interfaces are considered as implicit acknowledgements. Intelligent jitter management delaying packets' (re)transmissions may also be used to increase the chance to bundle several packets in a single transmission, or to avoid superfluous retransmissions due to packet collisions (see [10]). Baccelli, et al. Expires April 14, 2008 [Page 7] Internet-Draft OSPF MPR Extension for MANET October 2007 4.4. MPR Adjacency Reduction Furthermore, MANET routers may form adjacencies with a subset of their MANET neighbors (instead of all of them). However, no Designated Router or Backup Designated Router is elected on an OSPF MANET. Instead, most MANET routers bring up adjacencies only with their MPR and MPR selectors, while some select MANET routers (called Synch routers) must bring up adjacencies with all their MANET neighbors. This reduces the amount of control traffic needed for database synchronization, while ensuring that LSAs still describe synchronized adjacencies only. Baccelli, et al. Expires April 14, 2008 [Page 8] Internet-Draft OSPF MPR Extension for MANET October 2007 5. Protocol Details This section specifies the information that must be maintained, processed and transmitted by MANET and hybrid routers, and complements RFC 2740 [2]. 5.1. Data Structures In addition to the values used in RFC 2740 [2], the type field in the interface data structure can take a new value, "MANET". Furthermore, in addition to the protocol structures defined by RFC 2740 [2], MANET and hybrid routers make use of the data structures described below. N : the router IDs of the set of symmetric neighbors of the router. More precisely, N lists tuples of the form (1_HOP_SYM_id, 1_HOP_SYM_time). 1_HOP_SYM_id is the router ID of the symmetric neighbor. 1_HOP_SYM_time specifies the time, at which the tuple expires and MUST be removed from the set. N2 : the router IDs of the set of symmetric neighbors of routers that are in N, excluding: (i) the router performing the computation (ii) all routers in N. More precisely, N2 lists tuples of the form (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time). 2_HOP_SYM_id is the router ID of a symmetric 2-hops neighbor. 1_HOP_SYM_id is the router ID of the symmetric neighbor through which the 2-hop neighbor can be reached. 2_HOP_SYM_time specifies the time, at which the tuple expires and MUST be removed from the set. Flooding-MPR set: the router IDs of a subset of the routers listed in N, selected such that through this subset, each router listed in N2 is reachable. These neighbors are said to have been "selected as Baccelli, et al. Expires April 14, 2008 [Page 9] Internet-Draft OSPF MPR Extension for MANET October 2007 flooding MPR" by the router. More precisely, the Flooding-MPR set lists tuples of the form (Flooding_MPR_id, Flooding_MPR_time). Flooding_MPR_id is the router ID of the symmetric neighbor selected as flooding MPR. Flooding_MPR_time specifies the time, at which the tuple expires and MUST be removed from the set. For details about MPR selection, see Section 5.2. Flooding-MPR-selector set: the router IDs of the set of neighbors that have selected the router as flooding MPR. More precisely, the Flooding-MPR-selector set lists tuples of the form (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time). Flooding_MPR_SELECTOR_id is the router ID of the symmetric neighbor that has selected the router as flooding MPR. Flooding_MPR_SELECTOR_time specifies the time at which the tuple expires and MUST be removed from the set. For details about Flooding MPR selection, see Section 5.2. Path-MPR set: the router IDs of a subset of the routers listed in N that provide shortest paths from the members of N2 to the router. These neighbors are said to have been "selected as path MPR" by the router. More precisely, the Path-MPR set lists tuples of the form (Path_MPR_id, Path_MPR_time). Path_MPR_id is the router ID of the symmetric neighbor selected as path MPR. Path_MPR_time specifies the time at which the tuple expires and MUST be removed from the set. For details about path MPR selection, see Section 5.2. Path-MPR-selector set : the router IDs of the set of neighbors that have selected the router as path MPR. More precisely, the Path-MPR-selector set lists tuples of the form (Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time). Path_MPR_SELECTOR_id is the router ID of the symmetric neighbor that has selected the router as path MPR. Path_MPR_SELECTOR_time specifies the time at which the tuple expires and MUST be removed from the set. For details about path MPR selection, see Section 5.2. Baccelli, et al. Expires April 14, 2008 [Page 10] Internet-Draft OSPF MPR Extension for MANET October 2007 5.2. Hello Protocol On MANET interfaces, packets are sent, received and processed as defined by RFC 2740 [2] and RFC 2328 [1], with the following additions for MPR selection as described in this section. 5.2.1. Flooding MPR Selection The objective of flooding MPR selection is for a router to select a subset of its neighbors such that a packet, retransmitted by these selected neighbors, will be received by all routers 2 hops away. This property is called the flooding MPR "coverage criterion". The flooding MPR set of a router is computed such that, for each interface, it satisfies this criterion. The information required to perform this calculation (i.e. link sensing and neighborhood information) is acquired through periodic exchange of OSPF HELLO packets. Flooding MPRs are computed by each MANET or hybrid router. The smaller the flooding MPR set is, the lower the overhead will be. However, while it is not essential that the flooding MPR set is minimal, it is essential that all 2-hop neighbors can be reached through the selected flooding MPR routers. A router MUST select a flooding MPR set such that any 2-hop neighbor is covered by at least one flooding MPR router. Flooding MPR selection priority may be given to neighbor routers in descending order of their willingness to flood traffic on behalf of other routers. Appendix A gives a heuristic for flooding MPR selection. 5.2.2. Flooding MPR Selection Signalling in HELLO Packets A router that has selected flooding MPRs among its neighbors MUST signal this selection through appending LLS information (TLV type 3) at the end of its HELLO packets as described in Section 7. This information signals the list of neighbors the router has selected as flooding MPR, and the willingness of the router to be flooding traffic on behalf of other routers. 5.2.3. Neighbor Ordering in HELLO Packets Neighbors listed in the HELLO packets sent over MANET interfaces MUST be listed such that symmetric neighbors are listed before other neighbors. Moreover, neighbors selected as flooding MPR MUST be listed before other symmetric neighbors. This specific ordering corresponds with LLS information (TLV type 3) appended to the HELLO packet, as described in Section 7. Baccelli, et al. Expires April 14, 2008 [Page 11] Internet-Draft OSPF MPR Extension for MANET October 2007 5.2.4. Metric Signalling in HELLO Packets HELLO packets sent over MANET interfaces MUST advertize the costs of links towards ALL its symmetric MANET neighbors. If the router has several MANET interfaces, links to ALL the symmetric MANET neigbors over ALL the MANET interfaces of the router MUST have their costs listed. The costs of the links from the router to its neighbors as well as from the neighbors to the router (the reverse costs) are specified using the LLS format (TLV type 4) described in Section 7, appended at the end of Hello packets. 5.2.5. Path MPR Selection Using the LLS metric information included in HELLO packets, a MANET router MUST identify a subset of its links to neighbors that are on shortest paths with respect to the metric in use. This mechanism is called Path MPR selection. Appendix B gives a heuristic for path MPR selection. Hybrid routers MUST select ALL their MANET and hybrid neighbors as path MPRs. MANET routers MAY select a subset of MANET neighbors as path MPR. However a MANET router MUST ensure that for each element of N or N2 that is not in the path MPR set, there exists a shortest path that goes from this element to the router through a neighbor selected as path MPR (unless the shortest path is only one hop, of course). 5.2.6. Path MPR Selection Signalling in HELLO Packets A router that has selected path MPRs among its neighbors MUST signal this selection through appended LLS information (TLV type 4) at the end of its HELLO packets as described in Section 7. This information signals the list of neighbors the router has selected as path MPR. Neighbors listed in the TLV type 4 MUST be listed such that adjacent neighbors are listed before other neighbors. Moreover, neighbors selected as path MPR MUST be listed before other adjacent neighbors. 5.2.7. Hello Packet Processing In addition to the processing specified by RFC 2740 [2], N and N2 MUST be updated when received HELLO packets signal changes in the neighborhood of a MANET interface. The flooding MPR set and the path MPR set MUST then be recomputed if N or N2 have changed. Moreover, the flooding MPR selector set and the path MPR selector set MUST be updated upon receipt of a HELLO packet containing LLS information signalling change in the list of neighbors that has selected the router as MPR. Baccelli, et al. Expires April 14, 2008 [Page 12] Internet-Draft OSPF MPR Extension for MANET October 2007 5.3. Adjacencies When adjacencies are brought up between MANET and hybrid neighbors, procedure goes on as defined in RFC 2740 [2] and RFC 2328 [1]. However, in order to further reduce the control traffic overhead on the wireless medium, MANET routers MAY bring up adjacencies with a subset of their MANET or hybrid neighbors. Over a MANET interface, a router MUST bring up adjacencies with the neighbors it has included in its MPR set and its MPR Selector set. Some routers (called synch routers) MUST bring up adjacencies with other MANET neighbors as well. Other routers MAY bring up adjacencies with MANET neighbors other than MPRs and MPR selectors, at the expense of more synchronisation overhead. The proposed heuristic for routers to decide whether they are a synch router is as follows: o a MANET router decides it is a synch router if and only if the router has a higher ID than any other ID present in Hello packets or Router-LSAs it has received from other reachable routers in the area. Other algorithms are possible. However, algorithms MUST ensure that if there are no hybrid routers in the MANET, at least one router in the MANET selects itself as synch router. Moreover, a MANET router that selects itself as synch router MUST signal this by setting the S bit in the TLV type 4 appended to the Hello packets it generates, as described in Section 7. 5.3.1. Protocol Packets over 2-WAY Links When a router does not form a FULL adjacency with a MANET neighbor, the state does not progress beyond 2-WAY (as defined in RFC 2740 [2] and RFC 2328 [1]). A MANET interface MAY send routing protocol packets while in 2-WAY state. Therefore, any routing protocol packet received from a symmetric MANET neighbor MUST be processed. Similar to the OSPF broadcast interface [1], the next hop in the forwarding table MAY be a neighbor that is not adjacent. However, when a data packet has travelled beyond its first hop, the MPR selection process guarantees that subsequent hops in the SPT will be over adjacencies. 5.3.2. Adjacency Conservation Adjacencies are torn down as defined in RFC 2740 [2] and RFC 2328 [1]. This means that when the MPR set or MPR selector set is updated Baccelli, et al. Expires April 14, 2008 [Page 13] Internet-Draft OSPF MPR Extension for MANET October 2007 (due to changes in the neighborhood), and when a neighbor was formerly, but is no longer, in the MPR set or the MPR selector set, the adjacency with this neighbor is kept, unless it is no longer a symmetric neighbor. When a router receives Hello packets from a symmetric neighbor which cease to list the router as being adjacent (see Section 5.2.3), the state of this neighbor MUST be changed to (i) 2-WAY if the neighbor is not in the MPR set or the MPR selector set, or (ii) ExStart if the neighbor is in the MPR set or the MPR selector set, or if the neighbor or the router itself is a synch router. 5.4. Link State Advertisements The Router-LSAs originated by a hybrid router list adjacencies over interfaces other than MANET as specifed in RFC 2740 [2] and RFC 2328 [1]. Hybrid and MANET routers MUST list in the Router-LSAs they originate the links to the neighbors that are in their Path MPR set and their Path MPR Selector set. MANET routers MAY list other links they have through MANET interfaces, to the expense of more overhead. Hybrid and MANET routers MUST flood updated Router-LSAs when a new adjacency has been brought up reflecting change in the MPR set (or the MPR Selector set), and when a neighbor formerly listed in originated LSAs is no longer adjacent. 5.4.1. LSA Flooding LSUpdates received on an interface of a type other than MANET are processed and flooded as specified in [1] and [2], over every interface. If an LSUpdate was received on a MANET interface, it is processed as follows, with regards to flooded LSAs. 1. Consistency checks are made on the received packet, as specified in [1] and [2], before being handed to the procedure described in the following steps, and the Link State Update packet is thus associated with a particular neighbor and a particular area. 2. If the LSU was received from a router other than a symmetric neighbor, the LSUpdate MUST be discarded without further processing. Otherwise, for each LSA contained in LSUpdates received on MANET interfaces, the following steps replace steps 1 to 5 of section 13.3 of [1]. 1. If there exists an LSA in the Link State Database, with the same Link State ID, LS Type and Advertizing Router values as the received LSA, and the received LSA is not newer (see section 13.1 of [1]) then the received LSA MUST not be Baccelli, et al. Expires April 14, 2008 [Page 14] Internet-Draft OSPF MPR Extension for MANET October 2007 processed EXCEPT for acknowledgement as described in section 5.4. 2. Otherwise, the LSA MUST be attributed a scope according to its type, as specified in section 3.5 of [2]. 3. If the scope of the LSA is link local or reserved, the LSA MUST not be flooded on any interface. 4. Otherwise: - If the scope of the LSA is the area, the LSA MUST be flooded on all the interfaces of the router in that area according to the default flooding algorithm described below. - Otherwise, the LSA MUST be flooded on all the interfaces of the router according to the default flooding algorithm described below. The default flooding algorithm is then the following: 1. The LSA MUST be installed in the Link State Database. 2. The Age of the LSA is increased by InfTransDelay. 3. The LSA is flooded over all interfaces of type other than MANET. 4. If the sender interface address is an interface address of an flooding MPR selector of this router, the LSA MUST also be retransmitted out all MANET interfaces concerned by the scope, with the multicast address all_SPF_Routers. Note that MinLSArrival SHOULD be set to a value that is appropriate to MANET dynamic topologies: LSA updating may need to be more frequent in MANET parts of the OSPF network than in traditional parts of the OSPF network. 5.4.2. Link State Acknowlements When a router receives an LSA on a MANET interface, the router MUST proceed to acknowledge the LSA as follows 1. If the LSA was not received from an adjacent neighbor, the router MUST NOT acknowledge it. 2. Otherwise, if the LSA was received from an adjacent neighbor if the LSA is already in the database (i.e. the LSA has already been received and processed) the router MUST send an acknowledgement Baccelli, et al. Expires April 14, 2008 [Page 15] Internet-Draft OSPF MPR Extension for MANET October 2007 for this LSA on all MANET interfaces, to the multicast address all_SPF_Routers. 3. Otherwise, if the LSA is not already in the database: 1. If the router decides to retransmit the LSA (as part of the flooding procedure), the router MUST NOT acknowledge it, as this retransmission will be considered as an implicit acknowledgement. 2. Otherwise, if the router decides to not retransmit the LSA (as part of the flooding procedure), the router MUST send an acknowledgement for this LSA on all MANET interfaces, to the multicast address all_SPF_Routers. If a router sends an LSA on a MANET interface, it expects acknowledgements (explicit or implicit) from each adjacent neighbors. In the case where the router did not originate the LSA (i.e. relays the LSA), the router MUST only expect acknowledgements (explicit or implicit) from adjacent neighbors that have not previously acknowledged this LSA. If a router detects that some adjacent neighbor has not acknowledged the LSA, the router retransmits the LSA. If, due to efficient flooding procedure decision, a router decides to not relay an LSA, the router MUST still expect acknowledgements of that LSA (explicit or implicit) from adjacent neighbors that have not previously acknowledged this LSA. If a router detects that some adjacent neighbor has not acklnowledged the LSA, the router retransmits the LSA. Note that it may be beneficial to aggregate several acknowledgements in the same transmission, taking advantage of multicasting. A timer wait MAY thus be used before any acknowledgement transmission in order to avoid multiple OSPF acknowledgement transmissions. Additional jitter delay in packet (re)transmission may be used in order to increase the opportunities to bundle several packets together per transmission (which provides a reduction in the number of overall transmissions, and therefore the number of collisions over the wireless media). Baccelli, et al. Expires April 14, 2008 [Page 16] Internet-Draft OSPF MPR Extension for MANET October 2007 6. Security Considerations This document does currently not specify security considerations. Baccelli, et al. Expires April 14, 2008 [Page 17] Internet-Draft OSPF MPR Extension for MANET October 2007 7. IANA Considerations This document defines the new TLV types below, to be allocated by IANA. OSPF packets sent by MANET and hybrid routers are formated as defined by RFC2740 [2] and RFC2328 [1]. The LLS extension [4] is used in HELLO packets sent over MANET interfaces, as follows. The Hello packets sent over an OSPF MANET interface have the L bit set. An LLS datablock containing flooding MPR selection information is appended to these Hello messages. The TLV of Type 3 is defined as the flooding MPR selection TLV type shown in Fig. 1. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=3 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Willingness | # Sym. Neigh. | # MPR | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 1 : Flooding MPR selection (TLV type 0) Willingness This field specifies the willingness of the router to flood link state information on behalf of other routers. It can be set to any integer value from 1 to 6. By default, a router SHOULD advertise a willingness of WILL_DEFAULT = 3. # Sym. Neigh. Number of symmetric neighbors, listed first among the neighbors in a HELLO packet. # MPR Number of neighbors, listed first among the symmetric neighbors on this interface in a HELLO packet, that are selected by the router as flooding MPR. Baccelli, et al. Expires April 14, 2008 [Page 18] Internet-Draft OSPF MPR Extension for MANET October 2007 Reserved This 8 bits long field is set to 0 by the sender and ignored by the receiver. In addition to flooding MPR TLVs, HELLO packets contain an appended path MPR selection TLV defined as the TLV type 4 shown in Fig. 2. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=4 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # Adj. Neigh | # Path MPR |S| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost | Reverse Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost | Reverse Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 2 : metric advertisement (TLV type 1) # Adj. Neigh Number of blocks (Neighbor ID, Cost, Reverse Cost), listed first in the TLV, that describe adjacent MANET neighbors. # Path MPR Number of blocks (Neighbor ID, Cost, Reverse Cost), listed first among the blocks concerning adjacent MANET neighbors, that describe MANET neighbors that are selected as path MPRs by the router. S bit This bit is set to 1 if the router decides it is a synch router. Otherwise it is set to 0. Baccelli, et al. Expires April 14, 2008 [Page 19] Internet-Draft OSPF MPR Extension for MANET October 2007 Reserved This field is 16 bits long and must be set to 0 to be in compliance with this specification. Neighbor ID This field specifies the router ID of a MANET neighbor. Cost This field specifies the cost of the link going from the router towards the neighbor indicated in the neighbor ID field. If a neighbor is reachable through several interfaces at the same time, the advertized cost is set to the minimum of the costs over these different interfaces. Reverse Cost This field specifies the cost of the link going from the neighbor indicated in the neighbor ID field towards the router. By default it is set to 0xFFFF (maximal value, i.e. infinity), unless information received via HELLO packets from the neighbor specifies otherwise. If a neighbor is reachable through several interfaces at the same time, the advertized cost is set to the minimum of the costs over these different interfaces. Baccelli, et al. Expires April 14, 2008 [Page 20] Internet-Draft OSPF MPR Extension for MANET October 2007 8. References 8.1. Normative References [1] Moy, J., "OSPF version 2", RFC 2328, 1998. [2] Moy, J., Coltun, R., and D. Ferguson, "OSPF for IPv6", RFC 2740, 1999. [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, 1997. [4] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D. Yeung, "OSPF Link Local Signaling", draft-nguyen-ospf-lls-04 (work in progress), 2004. 8.2. Informative References [5] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. [6] Macker, J. and S. Corson, "MANET Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [7] OLSRv2, Design Team., "OLSR version 2", draft-ietf-manet-olsrv2-02 (work in progress), June 2006. [8] Ngyuen, D. and P. Minet, "Analysis of MPR Selection in the OLSR Protocol", 2nd Int. Workshop on Performance Analysis and Enhancement of Wireless Networks , 2007. [9] Macker, J., Chakeres, I., and T. Clausen, "Mobile Ad hoc Network Architecture", ID draft-ietf-autoconf-manetarch, February 2007. [10] Adamson, B., Dearlove, C., and T. Clausen, "Jitter Considerations in MANETs", ID draft-ietf-manet-jitter, June 2007. Baccelli, et al. Expires April 14, 2008 [Page 21] Internet-Draft OSPF MPR Extension for MANET October 2007 Appendix A. Flooding MPR Selection Heuristic The following specifies a proposed heuristic for selection of flooding MPRs. It constructs a flooding MPR set that enables a router to reach routers in the 2-hop neighborhood through relaying by one flooding MPR router. The following terminology will be used in describing the heuristics: D(y) is the degree of a 1-hop neighbor router y (where y is a member of N), defined as the number of neighbors of router y, EXCLUDING all the members of N and EXCLUDING the router performing the computation. The proposed heuristic can then be described as follows. Begin with an empty flooding MPR set. Then: 1. Calculate D(y), where y is a member of N, for all routers in N. 2. Add to the flooding MPR set those routers in N, which are the only routers to provide reachability to a router in N2. For example, if router b in N2 can be reached only through a router a in N, then add router a to the flooding MPR set. Remove the routers from N2 which are now covered by a router in the flooding MPR set. 3. While there exist routers in N2 which are not covered by at least one router in the flooding MPR set: 1. For each router in N, calculate the reachability, i.e. the number of routers in N2 which are not yet covered by at least one router in the flooding MPR set, and which are through this 1-hop neighbor; 2. Select as a flooding MPR the neighbor with highest willingness among the routers in N with non-zero reachability. In case of a tie among routers with same willingness the router which provides reachability to the maximum number of routers in N2. In case of another tie between routers also providing the same amount of reachability, select as flooding MPR the router whose D(y) is greater. Remove the routers from N2 which are now covered by a router in the flooding MPR set. 4. As an optimization, process each router, y, in the flooding MPR set in increasing order of willingness. If all routers in N2 are still covered by at least one router in the flooding MPR set excluding router y, then router y MAY be removed from the flooding MPR set. Other algorithms, as well as improvements over this algorithm, are Baccelli, et al. Expires April 14, 2008 [Page 22] Internet-Draft OSPF MPR Extension for MANET October 2007 possible. Different routers may use different algorithms independently. The only requirement is that the algorithm used by a given router MUST provide the router with an MPR set that fulfills the MPR flooding coverage criterion, i.e. it MUST select a flooding MPR set such that any 2-hop neighbor is covered by at least one flooding MPR router. Baccelli, et al. Expires April 14, 2008 [Page 23] Internet-Draft OSPF MPR Extension for MANET October 2007 Appendix B. Path MPR Selection Heuristic The following specifies a proposed heuristic for selection of path MPRs. It constructs a path MPR-set that enables a router to reach routers in the 2-hop neighborhood through shortest paths via routers in its path MPR-set. The following terminology will be used: - The router where the computation is done will be called A. - For a router B neighbor of A, cost(A,B) is the cost of the path through the direct link, from A to B, and this is an entry in the router cost matrix defined below. - For a router C in the neighborhood or 2-hop neighborhood of A, dist(C,A) is the cost of the shortest path from C to A and this is an entry in the router distance vector defined below. The cost matrix is populated with the values of the costs of links originating from router A (available locally) and by values listed in Hello packets received from neighbor routers. More precisely, the cost matrix is populated as follows: 1. The coefficients of the cost matrix are set by default to 0xFFFF (maximal value, i.e. infinity). 2. The coefficient cost(A,B) of the cost matrix for a link from router A to a neighbor B (the direct cost for this link) is set to the minimum cost over all interfaces that feature router B as a symmetric neighbor. The reverse cost for this link, cost(B,A), is set at the value received in Hello packets from router B. If router B is reachable through several interfaces at the same time, cost(B,A) is set as the minimum cost advertized by router B for its links towards router A. 3. The coefficients of the cost matrix concerning the link between two neighbors of A, routers C and B, are populated at the reception of their Hello packets. The cost (B,C) is set to the value advertized by the Hello packets from B, and respectively, the cost (C,B) is set to the value advertised in Hello packets from C. 4. The coefficients of the cost matrix, cost(B,C) for a link that connects a neighbor B to a 2-hop neighbor C is obtained via the Hello packets received from router B. In this case cost(B,C) and cost(C,B) are respectively set to the values advertized by router B for the direct cost and reverse cost for node C. Once the cost matrix is populated, the proposed heuristic can then be Baccelli, et al. Expires April 14, 2008 [Page 24] Internet-Draft OSPF MPR Extension for MANET October 2007 described as follows. Begin with an empty path MPR set. Then: 1. Using the cost matrix and the Dijkstra algorithm, compute the router distance vector, i.e. the shortest distance for each pair (X,A) where X is in N or N2 minimizing the sum of the cost of the path between X and A. 2. Compute N' as the subset of N made of the elements X such that cost(X,A)=dist(X,A). 3. Compute N2' as the subset of N and N2 made of the elements Y that do not belong to N' and such that there exist X in N' such cost(Y,X)+cost(X,A)=dist(Y,A). 4. Compute the MPR selection algorithm presented in Appendix A with N' instead of N and N2' instead of N2. The resulting MPR set is the path MPR set. Other algorithms, as well as improvements over this algorithm, are possible. Different routers may use different algorithms independently. However, a MANET router MUST ensure that for each element of N or N2 that is not in the path MPR set, there exists a shortest path that goes from this element to the router through a neighbor selected as path MPR (unless the shortest path is only one hop). Baccelli, et al. Expires April 14, 2008 [Page 25] Internet-Draft OSPF MPR Extension for MANET October 2007 Contributors The authors thank Cedric Adjih, Acee Lindem, Padma Pillay-Esnault and Laurent Viennot for their contributions to this document. Baccelli, et al. Expires April 14, 2008 [Page 26] Internet-Draft OSPF MPR Extension for MANET October 2007 Authors' Addresses Emmanuel Baccelli INRIA Phone: +33 1 69 33 55 11 Email: Emmanuel.Baccelli@inria.fr Philippe Jacquet INRIA Phone: +33 1 3963 5263 Email: Philippe.Jacquet@inria.fr Dang-Quan Nguyen INRIA Phone: +33 1 3963 5511 Email: Dang-Quan.Nguyen@inria.fr Thomas Heide Clausen LIX, Ecole Polytechnique, France Phone: +33 6 6058 9349 Email: T.Clausen@computer.org URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/ Baccelli, et al. Expires April 14, 2008 [Page 27] Internet-Draft OSPF MPR Extension for MANET October 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). 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. 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, THE IETF TRUST 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. Intellectual Property 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 http://www.ietf.org/ipr. 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 ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Baccelli, et al. Expires April 14, 2008 [Page 28]