Open Shortest Path (OSPF) E. Baccelli Internet-Draft INRIA Expires: May 7, 2007 T. Clausen LIX, Ecole Polytechnique, France P. Jacquet INRIA November 3, 2006 OSPF MPR Extension for Ad Hoc Networks draft-baccelli-ospf-mpr-ext-02 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 May 7, 2007. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This draft describes an OSPF extension tailored for MANET environments. This extension leverages the techniques that were developed by the IETF MANET working group. Currently no existing OSPF interface type corresponds to MANET characteristics. This proposal therefore defines an extension for an OSPF wireless Baccelli, et al. Expires May 7, 2007 [Page 1] Internet-Draft OSPF MPR Extension for MANET November 2006 interface. OSPF specificities over the wireless interface are derived from its broadcast interfaces handling. The new OSPF wireless interface combined with MPR mechanisms from the MANET working group, provides efficient operation of OSPF over MANETs. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Applicability Statement . . . . . . . . . . . . . . . . . 4 1.3. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Overview of the OSPF MPR extension . . . . . . . . . . . . . . 6 2.1. Adjacency Picking with MPR . . . . . . . . . . . . . . . . 6 2.2. Efficient Flooding with MPR . . . . . . . . . . . . . . . 6 2.3. Multicast LSA Acknowledgements . . . . . . . . . . . . . . 7 3. Implementation Details . . . . . . . . . . . . . . . . . . . . 8 3.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 8 3.2. Packet Processing . . . . . . . . . . . . . . . . . . . . 10 3.2.1. Hello Protocol . . . . . . . . . . . . . . . . . . . . 10 3.2.2. Adjacencies . . . . . . . . . . . . . . . . . . . . . 12 3.2.3. Link State Advertisements . . . . . . . . . . . . . . 13 4. Security Considerations . . . . . . . . . . . . . . . . . . . 16 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Appendix A. Data Formats . . . . . . . . . . . . . . . . . . . . 18 Appendix B. Flooding MPR Selection Heuristic . . . . . . . . . . 23 Appendix C. Path MPR Selection Heuristic . . . . . . . . . . . . 25 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 Intellectual Property and Copyright Statements . . . . . . . . . . 28 Baccelli, et al. Expires May 7, 2007 [Page 2] Internet-Draft OSPF MPR Extension for MANET November 2006 1. Introduction Mobile Ad hoc Networks (MANETs [2]) have attracted considerable attention over the last decade, both in academic and industrial environments. MANETs were initially designed as networks isolated from the Internet (at most, MANETs would be connected via a gateway), and the main challenge was that of providing efficient routing within these networks, as the new characteristics (such as the dynamic topology) implied by ad hoc connectivity made traditional solutions inappropriate. MANET routing solutions have been the subject of intensive attention from the IETF in the recent years, and have been extensively experimented in various scenarii including actual deployments. This document proposes a wireless extension for ospfv3 to address MANET routing challenges. In order to guarantee full compatibility with legacy OSPF, a natural solution is to base this extension the proactive MANET routing approach, since OSPF is itself proactive. This draft therefore introduces a wireless extension for OSPF inspired from the proactive MANET routing protocol OLSR [1]. This document specifies a new OSPF interface, tailored for wireless ad hoc networks: the OSPF wireless interface type. 1.1. 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. Additionally, this document uses the following terminology: - Wireless Interface: the OSPF interface type for MANETs, specified in this document. - Wireless Router: a router which has only wireless interface(s). Baccelli, et al. Expires May 7, 2007 [Page 3] Internet-Draft OSPF MPR Extension for MANET November 2006 - Wired Router: a router which has only traditional OSPF interface(s). - Hybrid Router: a router which has both traditional and wireless interfaces. - Wireless Neighbor: a neighbor, reachable through a wireless interface. - Symmetric Neighbor: a neighbor, in a state greater than or equal to ExStart or 2-Way. - Neighborhood of a Router: the set formed by the routers to which this router has a link. - 2-Hop Neighborhood of a Router: 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 wireless neighbors. 1.2. Applicability Statement An interface type for OSPFv3 operation on MANETs is designed, adapted to this specific network type. While this extension enables OSPF to function efficiently on MANETs, it does not change the normal Baccelli, et al. Expires May 7, 2007 [Page 4] Internet-Draft OSPF MPR Extension for MANET November 2006 operation of OSPF on other types of interfaces or networks. The difference in flooding, adjacency formation and acknowledging operations described in the following is effective only in wireless ad hoc parts of the OSPF network. This difference does not impact in any way on OSPF routing properties in other parts of the OSPF network (routing over adjacencies, shortest paths) whether there are wireless interfaces in the area, or not. This extension allows OSPF operation over mobile wireless networks, that may partition of merge depending on the dynamic topology of routers. 1.3. Changes - Structural changes for easier matching with RFC 2740 and RFC 2328. - Introduction of the Path MPR selection. Baccelli, et al. Expires May 7, 2007 [Page 5] Internet-Draft OSPF MPR Extension for MANET November 2006 2. Overview of the OSPF MPR extension This section describes an extension to OSPFv3 for MANETs, inspired by techniques from OLSR [1]. The wireless interface type, described in this document captures the specific characteristics of MANETs, sporting "half-broadcast" capabilities (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). Adjacency reduction and minimizing superfluous retransmission of protocol packets are part of OSPF operation on broadcast interfaces. The OSPF wireless interface cannot use these techniques as is and be efficient. Hence the MPR mechanisms will be incorporated in the OSPF wireless interfaces operation. 2.1. Adjacency Picking with MPR Similarly to OSPF operation on broadcast networks, routers will only form adjacencies with a subset of its wireless neighbors. However, no Designated Router or Backup Designated Router are elected on an OSPF MANET. Instead, adjacencies are simply formed between MPR and MPR Selectors, and only some select routers (called Synch routers) bring up adjacencies with all their wireless neighbors. Doing this greatly reduces the amount of control traffic needed for OSPF to function, while keeping OSPF's traditional properties: robust routing and optimal paths using synchronized adjacencies. Wireless and hybrid routers periodically generate and flood Router- LSAs describing adjacencies with wireless neighbors. Wireless adjacencies are advertized as point-to-point links to (current) wireless neighbors. However, these Router-LSAs may not advertize every single adjacency that is formed. Only those wireless adjacencies that are necessary (because on shortest paths) are picked to be listed in LSAs originated by wireless and hybrid routers, through a process called path MPR selection. 2.2. Efficient Flooding with MPR Wireless interfaces also enforce efficient flooding. The goal is the same as on broadcast interfaces: to reduce the number of superfluous retransmissions. However the implementation of this semantic on OSPF wireless interfaces differs from that on OSPF broadcast interfaces: over wireless interfaces, MPR flooding is enforced, i.e. only some wireless neighbors (those selected as MPR for flooding) are responsible for retransmitting a routing packet flooded over a wireless interface. MPR flooding is an essential feature for OSPF to function correctly in a wireless ad hoc environment. This technique provides a natural high resilience to transmission errors (inherent Baccelli, et al. Expires May 7, 2007 [Page 6] Internet-Draft OSPF MPR Extension for MANET November 2006 to the use of wireless links), and obsolete two-hop neighbor information (frequently caused by the mobility of the routers). 2.3. Multicast LSA Acknowledgements Finally, in order to further reduce the number of transmissions over wireless interfaces, 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 be used to increase the chance to bundle several packets in a single transmission, or to avoid superfluous retransmissions. The following sections detail these specific mechanisms. Baccelli, et al. Expires May 7, 2007 [Page 7] Internet-Draft OSPF MPR Extension for MANET November 2006 3. Implementation Details This section describes in details the additions and modifications to RFC 2740 and RFC 2328 defining the OSPF MPR extension. 3.1. Data Structures The interface data structure is enhanced: the type field can take a new value called "wireless". Furthermore, in addition to the protocol structure defined by RFC 2740 and RFC 2328, wireless and hybrid routers make use of the repositories described below. For each interface I is defined: N(I): the IDs of the set of the symmetric neighbors of the router through interface I (i.e. neighbors in a state greater than or equal to ExStart or 2-Way). More precisely, the repository lists tuples (1_HOP_SYM_id, 1_HOP_SYM_time). 1_HOP_SYM_id is the 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 IDs of the set of the symmetric neighbors of routers that are in N (i.e. 2-hop neighbors), excluding: (i) the router performing the computation (ii) all the routers in N. More precisely, the repository lists tuples (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time). 2_HOP_SYM_id is the ID of a symmetric neighbor 2-hops away. 1_HOP_SYM_id is the 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): Baccelli, et al. Expires May 7, 2007 [Page 8] Internet-Draft OSPF MPR Extension for MANET November 2006 the IDs of a set of neighbors selected such that through these selected routers, all the 2-hop neighbors (that are in N2 for interface I) are reachable. These neighbors are then said to have been "selected as flooding MPR" by the router. More precisely, the repository lists tuples (Flooding_MPR_id, Flooding_MPR_time). Flooding_MPR_id is the ID of the symmetric neighbor selected as 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 3.2.1. Flooding-MPR-selector(I): the IDs of the set of neighbors that have selected the router as flooding MPR through interface I. More precisely, the repository lists tuples (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time). Flooding_MPR_SELECTOR_id is the ID of the symmetric neighbor selected as 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 3.2.1. Path-MPR(I): the IDs of a set of neighbors that provide the shortest paths to the elements of N2. These neighbors are then said to have been "selected as path MPR" by the router. More precisely, the repository lists tuples (Path_MPR_id, Path_MPR_time). Path_MPR_id is the ID of the symmetric neighbor selected as 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 3.2.1. Path-MPR-selector(I): the IDs of the set of neighbors that have selected the router as flooding MPR through interface I. More precisely, the repository lists tuples (Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time). Path_MPR_SELECTOR_id is the ID of the symmetric neighbor selected as 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 3.2.1. Baccelli, et al. Expires May 7, 2007 [Page 9] Internet-Draft OSPF MPR Extension for MANET November 2006 In the following, the flooding MPR (selector) set of a router is defined as the union of the flooding MPR (selector) sets of each interface of the router. Similarly, the path (selector) MPR set of a router is defined as the union of the path (selector) MPR sets of each interface of the router. Finally, the MPR set of a router is defined as the union of the flooding MPR set and the path MPR set of a router. The wireless neighbors set (i.e. N) and 2-hop neighbors set (i.e. N2) are updated when received HELLO packets signal changes in the neighborhood. The flooding MPR set and the path MPR sets are then updated by the algorithm described in Section 3.2.1. At the end of this procedure new MPRs may be added to these sets, and formerly selected routers may be removed from these sets. The flooding MPR selector set and the path MPR selector set are updated upon receipt of LLS information (see Section 3.2.1) in which the recipient is listed as flooding MPR or path MPR by the originator of the LLS information. 3.2. Packet Processing On wireless interfaces, packets are sent, received and processed as defined by RFC 2740 and RFC 2328. There are however some modifications regarding the handling of Hello packets. These modifications are described in this section. 3.2.1. Hello Protocol The Hello protocol over wireless interface is enhanced with MPR selection as described in the following. This technique, inherited from the proactive MANET routing protocol [1], drastically reduces control traffic overhead. 3.2.1.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 the periodic exchange of OSPF HELLO packets. Flooding MPRs are computed per wireless interface, by each wireless or hybrid router. The union of the flooding MPR sets of each wireless interface of a router make up the flooding MPR set for this Baccelli, et al. Expires May 7, 2007 [Page 10] Internet-Draft OSPF MPR Extension for MANET November 2006 router. 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. Keeping the flooding MPR set small ensures that the overhead of the protocol is kept at a minimum. However, the flooding MPR set can coincide with the entire neighbor set. Flooding MPR selection priority may be given to neighbor routers in descending order of their willingness to be forwarding traffic on behalf of other routers. A heuristic for flooding MPR selection is given in Appendix B. 3.2.1.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 0) 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. 3.2.1.3. Metric Signalling in HELLO Packets The HELLO packets sent over wireless interfaces also advertize link costs with appended LLS information. 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 2) described in Appendix A. By default the reverse cost is set to 0xffff (maximal value, i.e. infinity), unless information received (i.e. a HELLO packet from the neighbor) specifies otherwise. 3.2.1.4. Neighbor Ordering in HELLO Packets Neighbors listed in the HELLO packets sent over wireless interfaces MUST be listed in a specific order: symmetric neighbors (i.e. in a state greater than or equal to ExStart or 2-Way) MUST be listed first. The number of symmetric neighbors is also signalled in the LLS information appended to the HELLO packet, as described in Appendix A. Any neighbor that is not symmetric (i.e. in a state lower than ExStart or 2-Way) MUST be listed after ALL symmetric neighbors. Baccelli, et al. Expires May 7, 2007 [Page 11] Internet-Draft OSPF MPR Extension for MANET November 2006 3.2.1.5. Path MPR Selection Using the LLS metric information included in HELLO packets, a wireless router identifies the subset of its wireless links that is sufficient to advertize in its Router-LSAs in order to ensure that the shortest paths (with respect to the costs in use) are known throughout the network. This mechanism is called Path MPR selection, and can be achieved using the heuristic proposed in Appendix C. Wireless routers MAY not select every wireless neighbor as path MPR, however hybrid routers MUST select ALL their wireless and hybrid neighbors as path MPRs, in order to ensure that shortest paths are used throughout the network. 3.2.1.6. Path MPR Selection Signalling in HELLO Packets A router that has selected path MPRs among its neighbors MUST signal this selection through appending LLS information (TLV type 1) 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. 3.2.2. Adjacencies Between wireless and hybrid neighbors, adjacencies are brought up and down as defined in RFC 2740 and RFC 2328. However, in order to reduce the control traffic overhead on the wireless medium, wireless routers MAY not bring up adjacencies with all their wireless or hybrid neighbors. Over a wireless interface, a router brings up adjacencies only with the neighbors it has included in its MPR set and its MPR Selector set. However, some routers (called synch routers) bring up adjacencies with all their wireless neighbors. This ensures that the adjacencies over the whole OSPF network contain the shortest paths, even with not all adjacencies being formed (see [4] [3]). A router decides it is a synch router if and only if: o the router is a wireless router that has the highest willingness in its neighborhood (in case of ties, the router that also has the greatest ID is elected). When a router does not form a FULL adjacency with a wireless neighbor, the state does not progress beyond 2-WAY. Contrary to other OSPF interfaces, a wireless interface may send routing protocol packets while in 2-WAY state. Therefore, any routing protocol packet received from a wireless Baccelli, et al. Expires May 7, 2007 [Page 12] Internet-Draft OSPF MPR Extension for MANET November 2006 neighbor in a state greater than or equal to ExStart or 2-Way MUST be processed. Similarly to the broadcast interface, the next hop in the forwarding table may be a neighbor that is not adjacent. However, when a data packet is further than its first hop, the MPR selection process guarantees that the next hops in the SPT will be over adjacencies. 3.2.3. Link State Advertisements The Router-LSAs originated by a hybrid router list wired adjacencies as specifed in RFC 2740 and RFC 2328. However, hybrid and wireless routers MAY only list the links to the neighbors that are in their Path MPR set and their Path MPR Selector set. This doing reduces the overhead (the size of the LSAs) while still ensuring that the shortest paths are known and used throughout the network. 3.2.3.1. LSA Flooding Flooding operation is modified over wireless interfaces, as described below. If an LSUpdate was received on an interface of a type other than wireless, its processing and the flooding procedure go on as specified in [5] and [6], over every interface (wireless or not). If an LSUpdates was received on a wireless interface, it is processed as follows, with regards to flooded LSAs. Note that, as specified in [5] and [6], consistency checks have been made on the received packet before being handed to the modified flooding procedure described in the following, and the Link State Update packet has thus been associated with a particular neighbor and a particular area. The principle is that a router A will consider flooding retransmission of an LSA it has received on a wireless interface from a neighbor B only if router B has signalled an flooding MPR set including router A. If this is not the case, router A will suppress its wireless retransmission of LSAs flooded by router B (since its retransmissions are superfluous). The following details the exact changes to the usual OSPFv3 specifications (i.e. section 13.3 of [5] and section 3.5 of [6]) for flooding decisions on wireless interfaces. If the LSU was not received from a neighbor in a state greater than or equal to ExStart or 2-Way, the LSUpdate MUST be discarded without further processing. Else, for each LSA contained in LSUpdates received on wireless interfaces, the following steps replace steps 1 to 5 of section 13.3 of [5]. Baccelli, et al. Expires May 7, 2007 [Page 13] Internet-Draft OSPF MPR Extension for MANET November 2006 1. If there exists an LSA in the Link State Database, with the same Link State ID, LS Type and Advertizing Router values, and the LSA is not newer (see section 13.1 of [5]) then the LSA MUST not be processed EXCEPT for acknowledgement as described in section 5.4. 2. Otherwise, the LSA MUST be forwarded according to the scope of the LSA type (see section 3.5 of [6]). 3. Flooding scope condition: 1. If the scope of the LSA is link local or reserved, the LSA MUST not be forwarded on any interface. 2. 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 non-wireless interfaces. 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 wireless 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. 3.2.3.2. Link State Acknowlements When a router receives an LSA on a wireless interface, the router MUST proceed to acknowledge the LSA as follows Baccelli, et al. Expires May 7, 2007 [Page 14] Internet-Draft OSPF MPR Extension for MANET November 2006 1. If the LSA is already in the database (i.e. the LSA has already been received) and it is received from a non-adjacent neighbor, the router MUST NOT acknowledge it. 2. If the LSA is already in the database (i.e. the LSA has already been received) and it is received from an adjacent neighbor, the router MUST send an acknowledgement for this LSA on all wireless interfaces, to the multicast address all_SPF_Routers. 3. If the LSA is not already in the database (i.e. the LSA has not already been received) and it decides to retransmit it (as part of the flooding procedure), the router MUST NOT acknowledge it, as this retransmission will be considered as an implicit acknowledgement. 4. If the LSA is not already in the database (i.e. the LSA has not already been received) and it decides to not retransmit it (as part of the flooding procedure), the router MUST send an acknowledgement for this LSA on all wireless interfaces, to the multicast address all_SPF_Routers. If a router sends an LSA on a wireless 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 aclnowledged the LSA, the router retransmits the LSA. Note that it may be beneficial to aggregate several acknowledgements in the same transmission (taking advantage of the 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 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 May 7, 2007 [Page 15] Internet-Draft OSPF MPR Extension for MANET November 2006 4. Security Considerations This document does currently not specify security considerations. Baccelli, et al. Expires May 7, 2007 [Page 16] Internet-Draft OSPF MPR Extension for MANET November 2006 5. IANA Considerations This document does currently not specify IANA considerations. 6. References [1] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. [2] Macker, J. and S. Corson, "MANET Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [3] Qayyum, A., Viennot, L., and A. Laouiti, "Multipoint Relaying: An efficient technique for flooding in mobile wireless networks", 35th Annual Hawaii International Conference on System Sciences , 2001. [4] Jacquet, P., Laouiti, A., Minet, P., and L. Viennot, "Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models", INRIA Research Report RR-4260, 2001. [5] Moy, J., "OSPF version 2", RFC 2328, 1998. [6] Moy, J., Coltun, R., and D. Ferguson, "OSPF for IPv6", RFC 2740, 1999. [7] Jacquet, P., Adjih, C., and L. Viennot, "Computing Connected Dominating Sets with Multipoint Relays", INRIA Research Report RR-4597, 2002. [8] OLSRv2, Design Team., "OLSR version 2", draft-ietf-manet-olsrv2-00 (work in progress), July 2005. [9] Ahrenholz, J., Baccelli, E., Clausen, T., Henderson, T., Jacquet, P., and P. Spagnolo, "OSPFv2 Wireless Interface Type", Internet-Draft spagnolo-manet-ospf-wireless-interface-01, May 2004. [10] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D. Yeung, "OSPF Link Local Signaling", draft-nguyen-ospf-lls-04 (work in progress), 2004. Baccelli, et al. Expires May 7, 2007 [Page 17] Internet-Draft OSPF MPR Extension for MANET November 2006 Appendix A. Data Formats OSPF packets sent by wireless and hybrid routers are formated as defined by RFC2740 and RFC2328. However, the LLS extension is used in Hello packets sent over wireless interfaces, as described in the following. Wireless and hybrid routers may set a flag, called L (L for LLS), in the OSPFv3 packets Options field (see [6]) which indicates that the packet contains LLS data block (see [10]). With LLS, wireless and hybrid routers may append a data block containing arbitrary information at the end of OSPFv3 packets. The length of the data block is not included in the OSPFv3 packet length field, but is included in the IP packet length, as shown below. +---------------------+ -- ^ | IPv6 Header | ^ | | Length = X+Y+Z | | Z = IPv6 Header Length | | | v | +---------------------+ -- | | OSPFv3 Header | ^ | | Length = X | | IP | |.....................| | X = OSPF Packet Length Packet | | | | | | OSPFv3 Data | | | | | v | +---------------------+ -- | | | ^ | | LLS Data Block | | Y = LLS Data Block Length V | | v +---------------------+ Fig. 1 : OSPFv3 and LLS data block in an IPv6 Packet In order to provision for different uses of the LLS, the type length value (TLV) format is used for the LLS datablock, as shown below in Fig. 2 and Fig. 3. An LLS header (checksum and length of the LLS datablock) is followed by a number of TLV blocks. Baccelli, et al. Expires May 7, 2007 [Page 18] Internet-Draft OSPF MPR Extension for MANET November 2006 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | LLS Data Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | TLV Blocks | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 2 : LLS datablock header 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 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Value | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 3 : TLV Block format The Hello packets sent over an OSPF wireless interface have the L bit set. An LLS datablock containing flooding MPR selection information is appended to these Hello messages. The TLV of Type 0 is defined as the flooding MPR selection TLV type shown in Fig. 4. 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=0 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Willingness | # Sym. Neigh. | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : : | IDs of Neighbors Selected as Flooding MPR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 4 : Flooding MPR selection (TLV type 0) Baccelli, et al. Expires May 7, 2007 [Page 19] Internet-Draft OSPF MPR Extension for MANET November 2006 Willingness This field specifies the willingness of a 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, i.e. the number of neighbors, listed first in the HELLO packet, that are in a state greater than or equal to ExStart or 2-Way. These neighbors are then considered in MPR selection mechanisms. Reserved This field is 16 bits long and must be set to 0 to be in compliance with this specification. IDs of Neighbors Selected as Flooding MPR Concatenation of successive IDs of neighbors selected as flooding MPR by the router. In addition to flooding MPR TLVs, HELLO packets also feature an appended path MPR selection TLV defined as the TLV type 1 shown in Fig. 5. 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=1 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : : | IDs of Neighbors Selected as path MPR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 5 : Path MPR selection (TLV type 1) Baccelli, et al. Expires May 7, 2007 [Page 20] Internet-Draft OSPF MPR Extension for MANET November 2006 IDs of Neighbors Selected as path MPR Concatenation of successive IDs of neighbors selected as path MPRs by the router. The TLV of Type 2 is defined as the metric advertisement TLV type shown in Fig. 6. 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=2 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost | Reverse Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost | Reverse Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 6 : metric advertisement (TLV type 2) Neighbor ID This field specifies the ID of a neighbor. Cost This field specifies the cost of the link going from the router towards the neighbor indicated in the neighbor ID field. 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. Baccelli, et al. Expires May 7, 2007 [Page 21] Internet-Draft OSPF MPR Extension for MANET November 2006 Baccelli, et al. Expires May 7, 2007 [Page 22] Internet-Draft OSPF MPR Extension for MANET November 2006 Appendix B. Flooding MPR Selection Heuristic The following specifies a proposed heuristic for selection of flooding MPRs. It constructs an 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 wireless 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 May 7, 2007 [Page 23] Internet-Draft OSPF MPR Extension for MANET November 2006 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 May 7, 2007 [Page 24] Internet-Draft OSPF MPR Extension for MANET November 2006 Appendix C. Path MPR Selection Heuristic The following specifies a proposed heuristic for selection of path MPRs. It constructs an 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. We will use the following terminology: - Let us call A the router where the computation is done - For a router B neighbor of A, we call cost(A,B) the cost of the path through the direct link, from B to A - For router C in the network, we call dist(A,C) the cost of the shortest path from C to A. The proposed heuristic can then be described as follows, for each wireless interface I: 1. Using the Dijkstra algorithm, compute the shortest paths for each pair (A,X) and (X,Y), where X is in N(I) and Y in N2(I) or N(I). 2. Compute N'(I) and N2'(I) as the subsets of elements of N(I) and N2(I) respectively, that DO NOT feature cost(A,X)>dist(A,X) or cost(A,X)+cost(X,Y)>dist(A,Y). 3. 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 May 7, 2007 [Page 25] Internet-Draft OSPF MPR Extension for MANET November 2006 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 Dang-Quan Nguyen, INRIA, France. Dang-Quan.Nguyen@inria.fr Baccelli, et al. Expires May 7, 2007 [Page 26] Internet-Draft OSPF MPR Extension for MANET November 2006 Authors' Addresses Emmanuel Baccelli INRIA Phone: +33 1 69 33 55 11 Email: Emmanuel.Baccelli@inria.fr Thomas Heide Clausen LIX, Ecole Polytechnique, France Phone: +33 6 6058 9349 Email: T.Clausen@computer.org Philippe Jacquet INRIA Phone: +33 1 3963 5263 Email: Philippe.Jacquet@inria.fr Baccelli, et al. Expires May 7, 2007 [Page 27] Internet-Draft OSPF MPR Extension for MANET November 2006 Intellectual Property Statement 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. 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Baccelli, et al. Expires May 7, 2007 [Page 28]