Open Shortest Path (OSPF) E. Baccelli Internet-Draft HITACHI Labs Europe Expires: August 31, 2006 T. Clausen LIX, Ecole Polytechnique, France P. Jacquet Project Hipercom, INRIA February 27, 2006 OSPF MPR Extension for Ad Hoc Networks draft-baccelli-ospf-mpr-ext-00 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 31, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This draft describes an OSPF extension taylored for MANETs. This extension leverages the techniques that were developed by the IETF MANET working group. No currently existing OSPF interface type corresponds to MANET characteristics, therefore this extension consists in the design of an OSPF interface type, called the OSPF Baccelli, et al. Expires August 31, 2006 [Page 1] Internet-Draft OSPF MPR Extension for MANET February 2006 wireless interface. OSPF's functionning over the wireless interface is inspired from its functionning on broadcast interfaces, which, combined with MPR mechanisms from the MANET working group, provides for OSPF efficient operation over MANETs. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 8 5.1 MPR Selection over OSPF Wireless Interfaces . . . . . . . 8 5.1.1 MPR Selection Heuristics . . . . . . . . . . . . . . . 9 5.1.2 MPR Selection Signalling . . . . . . . . . . . . . . . 10 5.1.3 MPR Selection Information Repositories . . . . . . . . 11 5.2 Adjacencies over OSPF Wireless Interfaces . . . . . . . . 12 5.3 Flooding Operation over OSPF Wireless Interfaces . . . . . 12 5.4 Acknowledging over OSPF Wireless Interface . . . . . . . . 14 6. Interaction with Other OSPF Interface Types . . . . . . . . . 17 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 19 A. Usage of Link Local Signaling . . . . . . . . . . . . . . . . 20 A.1 MPR Selection Signalling with LLS . . . . . . . . . . . . 21 B. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 C. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 24 Intellectual Property and Copyright Statements . . . . . . . . 25 Baccelli, et al. Expires August 31, 2006 [Page 2] Internet-Draft OSPF MPR Extension for MANET February 2006 1. Introduction Mobile Ad hoc Networks (MANETs [3]) have attracted considerable attention over the last decade, both in academic and industrial envi- ronments. 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 characterics (such as the dynamic topol- ogy) implied by ad hoc connectivity made traditional solutions inap- propriate. MANET routing solutions have been the subject of intensive attention from the IETF in the recent years, and have been exten- sively experimented in various scenarii including actual deployments. In order to integrate MANET routing with other Internet routing, this document specifies a wireless extension for OSPFv3 enabling router ad hoc mobility. 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] [2]. This document speci- fies a new OSPF interface, taylored for wireless ad hoc networks: the OSPF wireless interface type. Baccelli, et al. Expires August 31, 2006 [Page 3] Internet-Draft OSPF MPR Extension for MANET February 2006 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. Additionally, this document uses the following terminology: o Node: a device, capable of routing. o Wireless Interface: the OSPF interface type for MANETs, speci- fied in this document. o Wireless Node: a node which has only wireless interface(s). o Wired Node: a node which has only traditional OSPF inter- face(s). o Hybrid Node: a node which has both traditional and wireless interfaces. o Wireless Neighbor: a neighbor, reachable through a wireless interface. o Symmetric Neighbor: a neighbor, in a state greater than or equal to ExStart or 2-Way. o Neighborhood of a Node: the set formed by the nodes to which this node has a link. o 2-Hop Neighborhood of a Node: the set formed by the union of the neighborhoods of the neighbors of this node (excluding this node itself, and its neighborhood). o Synch Node: a node which brings up adjacencies with all its wireless neighbors. Baccelli, et al. Expires August 31, 2006 [Page 4] Internet-Draft OSPF MPR Extension for MANET February 2006 3. Applicability Statement This draft describes an extension of the OSPFv3 routing protocol for ad hoc networks. An interface type is designed, adapted to this spe- cific network type. While this extension enables OSPF to function efficiently on MANETs, it does not change in any way the functionning of OSPF on other types of interfaces or networks. The OSPF wireless interface type enables OSPF operation over mobile wireless networks, that may partition of merge depending on the dynamic topology of routers. Baccelli, et al. Expires August 31, 2006 [Page 5] Internet-Draft OSPF MPR Extension for MANET February 2006 4. Protocol Overview and Functioning This section describes an extension to OSPFv3 for MANETs, inspired by techniques from OLSR [1] [2]. The wireless interface type, described in this document captures the specific characteristics of MANETs, sporting "half-broadcast" capabilities (i.e. a node that makes a transmission on a MANET can only assume that a subset of the nodes attached to the MANET will hear this transmission). The OSPF wireless interface's functionning is inspired from how OSPF functions on broadcast interfaces, which, combined with MPR mecha- nisms, provides for OSPF operation over MANETs. OSPF operation on wireless interace pursues the same goals as on broadcast interfaces: reduce the number of superflueous adjacencies, and reduce the number of superfluous retransmission of routing packets. However, these goals are reached using modified mechanisms with regards to flooding, adjacency formation and acknowledging opera- tions. These modifications are effective only in wireless ad hoc parts of the OSPF network and does not impact in any way other parts of the OSPF network. OSPF operation remains thus unaltered over other types of OSPF interfaces, whether there are OSPF wireless interfaces in the network, or not. Similarly to OSPF functionning on broadcast networks, nodes 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 nodes (called Synch nodes) 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 opti- mal paths using synchronized adjacencies. Wireless and hybrid nodes periodically generate and flood Router-LSAs describing their adjacencies with their wireless neighbors. Wireless adjacencies are advertized as point-to-point links to (current) wire- less neighbors. 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) 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 Baccelli, et al. Expires August 31, 2006 [Page 6] Internet-Draft OSPF MPR Extension for MANET February 2006 high resilience to transmission errors (inherent to the use of wire- less links), and obsolete two-hop neighbor information (frequently caused by the mobility of the nodes). 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 manage- ment 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 August 31, 2006 [Page 7] Internet-Draft OSPF MPR Extension for MANET February 2006 5. Protocol Details Each hybrid or wireless node MUST select a subset of its wireless neighbors as MPR, and MUST signal MPR selection to its wireless neighbors. Section 5.1 describes MPR selection and signalling in details. MPR selection is used to determine wether or not to become adjacent with a 2-Way neighbor. MPR selection is also used to determine wether or not to retransmit a neighbor node's broadcasts. This technique, inherited from the proactive MANET routing protocol OLSR [1], drasti- cally reduces control traffic overhead. Adjacency formation is detailed in Section 5.2, before Section 5.3 details LSA flooding over wireless interfaces, and Section 5.4 describes how LSA acknowledgement is managed over wireless inter- faces. 5.1 MPR Selection over OSPF Wireless Interfaces The objective of MPR selection is for a node to select a subset of its neighbors such that a packet, retransmitted by these selected neighbors, will be received by all nodes 2 hops away. This property is called the MPR coverage criterion. The MPR set of a node is com- puted 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. MPRs are computed per wireless interface, by each wireless or hybrid node. The union of the MPR sets of each wireless interface of a node make up the MPR set for this node. While it is not essential that the MPR set is minimal, it is essen- tial that all 2-hop neighbors can be reached through the selected MPR nodes. A node SHOULD select an MPR set such that any 2-hop neighbor is covered by at least one MPR node. Keeping the MPR set small ensures that the overhead of the protocol is kept at a minimum. However, the MPR set can coincide with the entire neighbor set. MPR selection priority may be given to neighbor nodes in descending order of their willingness to be forwarding traffic on behalf of other nodes. Baccelli, et al. Expires August 31, 2006 [Page 8] Internet-Draft OSPF MPR Extension for MANET February 2006 5.1.1 MPR Selection Heuristics The following specifies a proposed heuristic for selection of MPRs. It constructs an MPR-set that enables a node to reach nodes in the 2-hop neighborhood through relaying by one MPR node. The heuristic should be applied per interface, I. The MPR set for a node is the union of the MPR sets found for each interface. The following termi- nology will be used in describing the heuristics: Neighbor of an interface: A node is a "neighbor of an interface" if the interface (on the local node) has a link to any one interface of the neighbor node. N: N is the set of symmetric neighbors of the node (i.e. neighbors in a state greater than or equal to ExStart or 2-Way), which are neighbor of the interface I. N2: The set symmetric neighbors of nodes in N (i.e. 2-hop neighbors), excluding: (i) the node performing the computation (ii) all the nodes in N. MPR set of an interface I: A (sub)set of the neighbors selected such that through these selected nodes, all the 2-hop neighbors (that are in N2 for interface I) are reachable. D(y): The degree of a 1-hop neighbor node y (where y is a member of N), is defined as the number of neighbors of node y, EXCLUDING all the members of N and EXCLUDING the node performing the computation. The proposed heuristic can then be described as follows, for each wireless interface: Baccelli, et al. Expires August 31, 2006 [Page 9] Internet-Draft OSPF MPR Extension for MANET February 2006 1 Calculate D(y), where y is a member of N, for all nodes in N. 2 Add to the MPR set those nodes in N, which are the *only* nodes to provide reachability to a node in N2. For example, if node b in N2 can be reached only through a node a in N, then add node a to the MPR set. Remove the nodes from N2 which are now covered by a node in the MPR set. 3 While there exist nodes in N2 which are not covered by at least one node in the MPR set: 3.1 For each node in N, calculate the reachability, i.e. the number of nodes in N2 which are not yet covered by at least one node in the MPR set, and which are through this 1-hop neighbor; 3.2 Select as a MPR the neighbor with highest willingness among the nodes in N with non-zero reachability. In case of a tie among nodes with same willingness the node which provides reachability to the maximum number of nodes in N2. In case of another tie between nodes also providing the same amount of reachability, select as MPR the node whose D(y) is greater. Remove the nodes from N2 which are now covered by a node in the MPR set. 4 A node's MPR set is generated from the union of the MPR sets for each interface. As an optimization, process each node, y, in the MPR set in increasing order of willingness. If all nodes in N2 are still covered by at least one node in the MPR set excluding node y, then node y MAY be removed from the MPR set. Other algorithms, as well as improvements over this algorithm, are possible. Different nodes may use different algorithms independently. The only requirement is that the algorithm used by a given node MUST provide the node with an MPR set that fulfills the MPR coverage cri- terion. 5.1.2 MPR Selection Signalling A node that has selected MPRs among its neighbors MUST signal this selection through appending LLS information at the end of its HELLO packets as described in Appendix A. This information signals the list of neighbors the node has selected as MPR, and the willingness Baccelli, et al. Expires August 31, 2006 [Page 10] Internet-Draft OSPF MPR Extension for MANET February 2006 of the node to be forwarding traffic on behalf of other nodes. Moreover, 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. 5.1.3 MPR Selection Information Repositories Each wireless or hybrid node also maintains a set called the "Wire- less 2-Hop Neighbors Set". This set keeps information about a node's symmetric neighbors two hops away. The set lists tuples (2_HOP_SYM_addr, 1_HOP_SYM_addr, LOCAL_if, 2_HOP_SYM_time). 2_HOP_SYM_addr is the address of a symmetric neighbor 2-hops away. 1_HOP_SYM_addr is the address of the symmetric neighbor through which the 2-hop neighbor can be reached. LOCAL_if is the address of the local interface of the node, through which the 1-hop neighbor can be reached. 2_HOP_SYM_time specifies the time at which the tuple expires and *MUST* be removed from the set. Each wireless or hybrid node maintains a set called the "Wireless Neighbors Set". This set keeps information about a node's symmetric neighbors two hops away. The set lists tuples (1_HOP_SYM_addr, LOCAL_if, 1_HOP_SYM_time). 1_HOP_SYM_addr is the address of a symmet- ric neighbor of the node. LOCAL_if is the address of the local inter- face of the node, through which the neighbor can be reached. 1_HOP_SYM_time specifies the time at which the tuple expires and *MUST* be removed from the set. The wireless neighbors and 2-hop neighbors sets are updated when received HELLO packets signal changes in the neighborhood. In addition, each wireless or hybrid node maintains a set called the "MPR Set". This set lists the addresses of the neighbors selected as MPR by the node. The MPR set is updated by the algorithm described in Section 5.1.1, which is used as soon as the node detects a change in its wireless neighbors, or 2-hop neighbors sets. At the end of this procedure new MPRs may be added to the set, and formerly selected nodes are removed from the set. Similarly, each wireless or hybrid node also maintains a set called the "MPR Selector Set". This set lists tuples (MPRS_addr, MPRS_time), describing the neighbors which have selected this node as a MPR. MPRS_addr is the address of a neighbor, which has selected Baccelli, et al. Expires August 31, 2006 [Page 11] Internet-Draft OSPF MPR Extension for MANET February 2006 this node as MPR. MPRS_time specifies the time at which the tuple expires and *MUST* be removed from the set. The MPR set is updated upon receipt of LLS information in which the recipient is listed as MPR by the originator of the LLS information. 5.2 Adjacencies over OSPF Wireless Interfaces In order to reduce the control traffic overhead on the wireless medium, nodes do not bring up adjacencies with all their wireless neighbors. This is similar to broadcast interfaces, over which a node forms adjacencies only with the Designated Router and the Backup Designated Router. Over a wireless interface, a node brings up adjacencies only with the neighbors it has included in its MPR set and its MPR Selector set. However, some nodes (called synch nodes) 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 [8] [10]). A node decides it is a synch node if and only if: o the node is a hybrid node, OR o the node is a wireless node that has the highest willingness in its neighborhood (in case of ties, the node that also has the greatest Router ID is elected). When a node does not form an adjacency with a wireless neighbor, the state of this neighbor will be 2-Way (instead of FULL, for an adja- cent neighbor). Contrary to other types of interfaces, over a wire- less interface routing packets may also be sent over 2-Way links. Therefore, any routing packet received from a wireless 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 packet is further than its first hop, the MPR selection process guarantees that the next hop in the SPT will be over an adjacency. 5.3 Flooding Operation over OSPF Wireless Interfaces Flooding operation is modified over wireless interfaces. However, note that flooding runs unaltered over all other types of OSPF inter- faces. If an LSU was received on an interface of a type other than wireless, its processing and the flooding procedure go on as speci- fied in [4] and [6], over every interface (wireless or not). If an LSU was received on a wireless interface, it is processed as follows, with regards to flooded LSAs. Baccelli, et al. Expires August 31, 2006 [Page 12] Internet-Draft OSPF MPR Extension for MANET February 2006 Note that, as specified in [4] 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 node A will consider flooding retransmission of an LSA it has received on a wireless interface from a neighbor B only if node B has signalled an MPR set including node A. If this is not the case, node A will suppress its wireless retransmission of LSAs flooded by node B (since its retransmissions are superfluous). The following details the exact changes to the usual OSPFv3 specifi- cations (i.e. section 13.3 of [4] and section 3.5 of [6]) for flood- ing 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 LSU MUST be discarded without fur- ther processing. Else, for each LSA contained in LSUs received on wireless interfaces, the following steps replace steps 1 to 5 of sec- tion 13.3 of [4]. 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 [4]) 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: 3.1 If the scope of the LSA is link local or reserved, the LSA MUST not be forwarded on any interface. 3.2 Otherwise: 3.2.1 If the scope of the LSA is the area, the LSA MUST be forwarded on all the interfaces of the node in that area according to the default forwarding algorithm described below. 3.2.2 Otherwise, the LSA MUST be forwarded on all the interfaces of the node according to the default forwarding algorithm described below. Baccelli, et al. Expires August 31, 2006 [Page 13] Internet-Draft OSPF MPR Extension for MANET February 2006 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 MPR selector of this node, 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 fre- quent in MANET parts of the OSPF network than in traditional parts of the OSPF network. 5.4 Acknowledging over OSPF Wireless Interface When a node receives an LSA on a wireless interface, the node MUST proceed to acknowledge the LSA as follows Baccelli, et al. Expires August 31, 2006 [Page 14] Internet-Draft OSPF MPR Extension for MANET February 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 node 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 node 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 node 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 node MUST send an acknowledgement for this LSA on all wireless interfaces, to the multicast address all_SPF_Routers. If a node sends an LSA on a wireless interface, it expects acknowledgements (explicit or implicit) from each adjacent neighbors. In the case where the node did not originate the LSA (i.e. relays the LSA), the node MUST only expect acknowledgements (explicit or implicit) from adjacent neighbors that have not previously acknowledged this LSA. If a node detects that some adjacent neighbor has not acknowledged the LSA, the node retransmits the LSA. If, due to efficient flooding procedure decision, a node decides to not relay an LSA, the node MUST still expect acknowledgements of that LSA (explicit or implicit) from adjacent neighbors that have not previously acknowledged this LSA. If a node detects that some adjacent neighbor has not aclnowledged the LSA, the node 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. Baccelli, et al. Expires August 31, 2006 [Page 15] Internet-Draft OSPF MPR Extension for MANET February 2006 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 August 31, 2006 [Page 16] Internet-Draft OSPF MPR Extension for MANET February 2006 6. Interaction with Other OSPF Interface Types OSPF operation remains unaltered over other types of OSPF interfaces, wether there are OSPF wireless interfaces in the network, or not. The difference in flooding, adjacency formation and acknowledging opera- tions described above is effective only in wireless ad hoc parts of the OSPF network and does not impact in any way on other parts of the OSPF network. In wireless ad hoc parts of the OSPF network, routing is performed over synchronized adjacencies, as in usual OSPF. This way, the same properties of robusteness (shortest and loop-free paths) are still garanteed throughout the whole OSPF network wether there are OSPF wireless interfaces in the network, or not. Baccelli, et al. Expires August 31, 2006 [Page 17] Internet-Draft OSPF MPR Extension for MANET February 2006 7. Security Considerations This document does currently not specify security considerations. Baccelli, et al. Expires August 31, 2006 [Page 18] Internet-Draft OSPF MPR Extension for MANET February 2006 8. IANA Considerations This document does currently not specify IANA considerations. Authors' Addresses Emmanuel Baccelli HITACHI Labs Europe Phone: +33 1 69 33 55 11 Email: baccelli@eurecom.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/ Philippe Jacquet Project Hipercom, INRIA Phone: +33 1 3963 5263 Email: Philippe.Jacquet@inria.fr Baccelli, et al. Expires August 31, 2006 [Page 19] Internet-Draft OSPF MPR Extension for MANET February 2006 Appendix A. Usage of Link Local Signaling Nodes 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 [14]). With LLS, nodes may append a data block containing arbitrary informa- tion 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 dat- ablock) is followed by a number of TLV blocks. 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Baccelli, et al. Expires August 31, 2006 [Page 20] Internet-Draft OSPF MPR Extension for MANET February 2006 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 Appendix A.1 MPR Selection Signalling with LLS The Hello packets sent over an OSPF wireless interface have the L bit set. An LLS datablock containing MPR selection information is appended to these Hello messages. The TLV of Type 0 is defined as the 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : : | Addresses of Neighbors Selected as MPR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 4 : MPR selection TLV Baccelli, et al. Expires August 31, 2006 [Page 21] Internet-Draft OSPF MPR Extension for MANET February 2006 Willingness: This field specifies the willingness of a node to carry and forward traffic for other nodes. It can be set to any integer value from 1 to 6. By default, a node 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 must be set to "000000000000000000000" to be in compliance with this specification. Addresses of Neighbors Selected as MPR: Concatenation of successive IPv6 addresses of neighbors selected as MPR by the node. Baccelli, et al. Expires August 31, 2006 [Page 22] Internet-Draft OSPF MPR Extension for MANET February 2006 Appendix B. References [1] T. Clausen, P. Jacquet, RFC 3626: Optimized Link State Routing Pro- tocol. 2003. [2] OLSRv2 Design Team, Optimized Link State Routing Protocol version 2, Internet Draft draft-ietf-manet-olsrv2-00, July 2005. [3] S. Corson, J. Macker, RFC 2501: Mobile Ad hoc Networking (MANET), Routing Protocol Performance Issues and Evaluation Considerations, 1999. [4] J. Moy, RFC 2328: OSPF version 2, 1998. [5] J. Moy, OSPF, Anatomy of an Internet Routing Protocol, Addison-Wes- ley, 1998. [6] R. Coltun, D. Ferguson, J. Moy, RFC 2740: OSPF for IPv6, 1999. [7] E. Baccelli, T. Clausen, P. Jacquet, Ad-hoc and Internet Conver- gence: Adapting OSPF-style Database Exchanges for Ad-hoc Networks, Proceedings of the Conference on Performance Modelling and Evalua- tion of Heterogeneous Networks (HET-NETs), Oct. 2004. [8] A. Qayyum, L. Viennot, A. Laouiti, Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks, INRIA Research Report RR-3898, March 2000. [9] C. Adjih, P. Jacquet, L. Viennot, Computing Connected Dominating Sets with Multipoint Relays, INRIA Research Report RR-4597, 2002. [10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot, Performance Evalua- tion of Multipoint Relaying in Mobile Ad Hoc Networks, Proceedings of the Networking International Conference, 2002. [11] J. Ahrenholz, E. Baccelli, T. Clausen, T. Henderson, P. Jacquet, P. Spagnolo, OSPFv2 Wireless Interface Type, Internet Draft draft- spagnolo-manet-ospf-wireless-interface-01.txt, May 2004. [12] R. Ogier, MANET Extension of OSPF using CDS Flooding, Internet Draft draft-ogier-manet-ospf-extension-05, 2005. [13] M. Chandra et al. Extensions to OSPF to Support Mobile Ad Hoc Net- working, Internet Draft draft-chandra-ospf-manet-ext-03, 2005. [14] A. Zinin, B. Friedman, A. Roy, L. Nguyen, D. Yeung, OSPF Link Local Signaling, Internet Draft draft-nguyen-ospf-lls-04, 2004. Baccelli, et al. Expires August 31, 2006 [Page 23] Internet-Draft OSPF MPR Extension for MANET February 2006 Appendix C. Contributors Cedric Adjih, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: Cedric.Adjih@inria.fr Laurent Viennot, Project Gyroweb, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: Laurent.Viennot@inria.fr Baccelli, et al. Expires August 31, 2006 [Page 24] Internet-Draft OSPF MPR Extension for MANET February 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 August 31, 2006 [Page 25]