Open Shortest Path (OSPF) E. Baccelli Internet-Draft P. Jacquet Expires: August 5, 2007 D. Nguyen INRIA T. Clausen LIX, Ecole Polytechnique, France February 2007 OSPF MPR Extension for Ad Hoc Networks draft-baccelli-ospf-mpr-ext-03 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 August 5, 2007. Copyright Notice Copyright (C) The IETF Trust (2007). Baccelli, et al. Expires August 5, 2007 [Page 1] Internet-Draft OSPF MPR Extension for MANET February 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 . . . . . . . . . . 12 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 . . . . . . . . . . . . . . . 13 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 5.3.1. Protocol Packets over 2-WAY Links . . . . . . . . . . 13 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 14 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 14 5.4.2. Link State Acknowlements . . . . . . . . . . . . . . . 16 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8.1. Normative References . . . . . . . . . . . . . . . . . . . 20 8.2. Informative References . . . . . . . . . . . . . . . . . . 20 Appendix A. Data Formats . . . . . . . . . . . . . . . . . . . . 21 Appendix B. Flooding MPR Selection Heuristic . . . . . . . . . . 24 Appendix C. Path MPR Selection Heuristic . . . . . . . . . . . . 26 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29 Intellectual Property and Copyright Statements . . . . . . . . . . 30 Baccelli, et al. Expires August 5, 2007 [Page 2] Internet-Draft OSPF MPR Extension for MANET February 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 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 is remains unaltered, whether there are MANET interfaces in the area or not. Baccelli, et al. Expires August 5, 2007 [Page 3] Internet-Draft OSPF MPR Extension for MANET February 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 ExStart or 2-Way (through an interface of any type). Baccelli, et al. Expires August 5, 2007 [Page 4] Internet-Draft OSPF MPR Extension for MANET February 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 the union of the neighborhoods of the neighbors of this router (excluding this router itself, and its neighborhood). Synch router - a router which brings up adjacencies with all its MANET neighbors. Flooding MPR (selector) set - the union of the flooding MPR (selector) sets of each MANET interface of this router. Path MPR (selector) set - the union of the path MPR (selector) sets of each MANET interface of this router. MPR set - the union of the flooding MPR set and the path MPR set of this router. Baccelli, et al. Expires August 5, 2007 [Page 5] Internet-Draft OSPF MPR Extension for MANET February 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 those 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, 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 scenarii, that possibly include parts of the network that are fixed, using the OSPF framework. Baccelli, et al. Expires August 5, 2007 [Page 6] Internet-Draft OSPF MPR Extension for MANET February 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 a shortest path) are listed in LSAs. MANET routers periodically generate and flood Router-LSAs describing their selection of wireless links as point-to-point links to (current) MANET neighbors. This mechanism greatly reduces the size of LSAs originated by MANET routers, while still keeping OSPF's traditional properties: robust routing and optimal paths using synchronized adjacencies. 4.3. Multicast Transmissions of Protocol Packets In order to reduce the overehad, 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. Baccelli, et al. Expires August 5, 2007 [Page 7] Internet-Draft OSPF MPR Extension for MANET February 2007 4.4. MPR Adjacency Reduction Furthermore, MANET routers may form adjacencies with a subset of its MANET neighbors (instead of all of them). However, no Designated Router or Backup Designated Router are elected on an OSPF MANET. Instead, routers must at least bring up adjacencies with their MPR and MPR selectors. Some select routers (called Synch routers) must also bring up adjacencies with their other MANET neighbors. However other routers (most of them) do not have to bring up adjacencies with MANET neighbors other than their MPR and MPR selectors. This reduces the amount of control traffic needed for database synchronization, while ensuring that LSAs still describe synchronized adjacencies only. Baccelli, et al. Expires August 5, 2007 [Page 8] Internet-Draft OSPF MPR Extension for MANET February 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] and RFC 2328 [1]. 5.1. Data Structures In addition to the values defined in RFC 2328 [1] the type field in the interface data structure can take a new value, "MANET". Furthermore, in addition to the protocol structure defined by RFC 2740 [2] and RFC 2328 [1], MANET and hybrid routers make use of the data structures described below. N(I) : the router IDs of the set of symmetric neighbors of the router through interface I. More precisely, N(I) 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(I) : the router IDs of the set of symmetric neighbors of routers that are in N(I), excluding: (i) the router performing the computation (ii) all routers in N(I). More precisely, N2(I) 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(I) : the router IDs of a subset of N(I) selected such that through this subset, each router listed in N2(I) is reachable. These neighbors Baccelli, et al. Expires August 5, 2007 [Page 9] Internet-Draft OSPF MPR Extension for MANET February 2007 are said to have been "selected as flooding MPR" by the router. More precisely, Flooding-MPR(I) 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(I) : the router IDs of the set of neighbors that have selected the router as flooding MPR through interface I. More precisely, Flooding-MPR-selector(I) 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(I) : the router IDs of a subset of N(I) that provide shortest paths to the routers in N2(I). These neighbors are said to have been "selected as path MPR" by the router. More precisely, Path-MPR(I) 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(I) : the router IDs of the set of neighbors that have selected the router as path MPR through interface I. More precisely, Path-MPR- selector(I) 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 August 5, 2007 [Page 10] Internet-Draft OSPF MPR Extension for MANET February 2007 The structures listed above are defined per interface. 5.2. Hello Protocol On MANET interfaces, packets are sent, received and processed as defined by RFC 2740 [2] and RFC 2328 [1], with 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 per MANET interface, by each MANET or hybrid router. The union of the flooding MPR sets of each MANET interface of a router make up the flooding MPR set for this router. The smaller the 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 SHOULD 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 forward traffic on behalf of other routers. Appendix B 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 Appendix A. This information signals the list of neighbors the router has selected as flooding MPR, and the willingness of the router to be forwarding traffic on behalf of other routers. Baccelli, et al. Expires August 5, 2007 [Page 11] Internet-Draft OSPF MPR Extension for MANET February 2007 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 Appendix A. 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 Appendix A, 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 C 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 at least select those of its neighbors that are the last hop on shortest paths of at least 2 hops, originating in the neighborhood or the 2-hop neighborhood and ending at the router. 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 Appendix A. 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. Baccelli, et al. Expires August 5, 2007 [Page 12] Internet-Draft OSPF MPR Extension for MANET February 2007 5.2.7. Hello Packet Processing In addtition to the processing specified by RFC 2740 [2] and RFC 2328 [1], N(I) and N2(I) MUST be updated when received HELLO packets signal changes in the neighborhood of a MANET interface I. The flooding MPR set and the path MPR set of this interface MUST then be recomputed if N(I) or N2(I) 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. 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 received in Hello packets or Router-LSAs. 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 Appendix A. 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. Baccelli, et al. Expires August 5, 2007 [Page 13] Internet-Draft OSPF MPR Extension for MANET February 2007 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 (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. Baccelli, et al. Expires August 5, 2007 [Page 14] Internet-Draft OSPF MPR Extension for MANET February 2007 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 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 forwarded on any interface. 4. Otherwise: - If the scope of the LSA is the area, the LSA MUST be forwarded on all the interfaces of the router in that area according to the default forwarding algorithm described below. - Otherwise, the LSA MUST be forwarded on all the interfaces of the router according to the default forwarding algorithm described below. The default forwarding 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. Baccelli, et al. Expires August 5, 2007 [Page 15] Internet-Draft OSPF MPR Extension for MANET February 2007 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 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 to avoid superfluous retransmissions. Additional jitter delay in packet (re)transmission may be used in Baccelli, et al. Expires August 5, 2007 [Page 16] Internet-Draft OSPF MPR Extension for MANET February 2007 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 August 5, 2007 [Page 17] Internet-Draft OSPF MPR Extension for MANET February 2007 6. Security Considerations This document does currently not specify security considerations. Baccelli, et al. Expires August 5, 2007 [Page 18] Internet-Draft OSPF MPR Extension for MANET February 2007 7. IANA Considerations This document defines new TLV types (see Appendix A) to be allocated by IANA. Baccelli, et al. Expires August 5, 2007 [Page 19] Internet-Draft OSPF MPR Extension for MANET February 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. Baccelli, et al. Expires August 5, 2007 [Page 20] Internet-Draft OSPF MPR Extension for MANET February 2007 Appendix A. Data Formats 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 I 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 carry and forward traffic for 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 in a HELLO packet, that are selected as flooding MPR for interface I by the router. Reserved This field is 8 bits long and must be set to 0 to be in compliance Baccelli, et al. Expires August 5, 2007 [Page 21] Internet-Draft OSPF MPR Extension for MANET February 2007 with this specification. 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. Reserved This field is 16 bits long and must be set to 0 to be in compliance with this specification. Baccelli, et al. Expires August 5, 2007 [Page 22] Internet-Draft OSPF MPR Extension for MANET February 2007 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 August 5, 2007 [Page 23] Internet-Draft OSPF MPR Extension for MANET February 2007 Appendix B. 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 heuristic should be applied per interface, I. The flooding MPR set for a router is the union of the flooding MPR sets found for each interface. 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), is 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, for each MANET interface I: 1. Calculate D(y), where y is a member of N(I), for all routers in N(I). 2. Add to the flooding MPR(I) set those routers in N(I), which are the only routers to provide reachability to a router in N2(I). For example, if router b in N2(I) can be reached only through a router a in N(I), then add router a to the flooding MPR(I) set. Remove the routers from N2(I) which are now covered by a router in the flooding MPR(I) set. 3. While there exist routers in N2(I) which are not covered by at least one router in the flooding MPR(I) set: 1. For each router in N(I), calculate the reachability, i.e. the number of routers in N2(I) which are not yet covered by at least one router in the flooding MPR(I) 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(I) 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(I). 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(I) which are now covered by a router in the flooding MPR(I) 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 Baccelli, et al. Expires August 5, 2007 [Page 24] Internet-Draft OSPF MPR Extension for MANET February 2007 flooding MPR set. Other algorithms, as well as improvements over this algorithm, are 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. Baccelli, et al. Expires August 5, 2007 [Page 25] Internet-Draft OSPF MPR Extension for MANET February 2007 Appendix C. 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 heuristic should be applied per interface, I. The path MPR set for a router is the union of the path MPR sets found for each interface. 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. Baccelli, et al. Expires August 5, 2007 [Page 26] Internet-Draft OSPF MPR Extension for MANET February 2007 Once the cost matrix is populated, the proposed heuristic can then be described as follows, for each MANET interface I: 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(I) or N2(I) minimizing the sum of the cost of the path between X and A. 2. Compute N'(I) as the subset of N(I) made of the elements X such that cost(X,A)=dist(X,A). 3. Compute N2'(I) as the subset of N(I) and N2(I) made of the elements Y that do not belong to N'(I) and such that there exist X in N'(I) such cost(Y,X)+cost(X,A)=dist(Y,A). 4. Compute the MPR selection algorithm presented in Appendix B with N'(I) instead of N(I) and N2'(I) instead of N2(I). 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. The only requirement is that the algorithm used by a given router MUST provide the network with the knowledge of the shortest paths. Baccelli, et al. Expires August 5, 2007 [Page 27] Internet-Draft OSPF MPR Extension for MANET February 2007 Contributors Padma Pillay-Esnault, Cisco Systems, USA. Email: ppe@cisco.com Cedric Adjih, INRIA, France. Email: Cedric.Adjih@inria.fr Laurent Viennot, INRIA, France. Laurent.Viennot@inria.fr Baccelli, et al. Expires August 5, 2007 [Page 28] Internet-Draft OSPF MPR Extension for MANET February 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 August 5, 2007 [Page 29] Internet-Draft OSPF MPR Extension for MANET February 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 August 5, 2007 [Page 30]