INTERNET-DRAFT Thomas Clausen IETF MANET Working Group Philippe Jacquet Expiration: 30 April 2002 Anis Laouiti Pascale Minet Paul Muhlethaler Amir Qayyum Laurent Viennot INRIA Rocquencourt, France 31 October 2001 Optimized Link State Routing Protocol draft-ietf-manet-olsr-05.txt Status of this Memo This document is a submission by the Mobile Ad Hoc Networking Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the manet@itd.nrl.navy.mil mailing list. Distribution of this memo is unlimited. This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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. Abstract This document describes the Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks. The protocol is an optimization of the pure link state algorithm tailored to the requirements of a mobile wireless LAN. The key concept used in the protocol is that of multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 1] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a pure flooding mechanism, where every node retransmits each message when it receives the first copy of the message. In OLSR, information flooded in the network "through" these MPRs is also "about" the MPRs. Thus, a second optimization is achieved by minimizing the "contents" of the control messages flooded in the network. Hence, as contrary to the classic link state algorithm, a node declares only a small subset of links to its neighbor nodes, rather than all links to all neighbors. This information is then used by the OLSR protocol for route calculation. As a consequence hereof, the routes contain only the MPRs as intermediate nodes from a Source to a Destination. OLSR provides optimal routes (in terms of number of hops). The protocol is particularly suitable for large and dense networks as the technique of MPRs works well in this context. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 5 1.3. Applicability Section . . . . . . . . . . . . . . . . . . 7 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 8 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9 2.1. Packet Format and Forwarding . . . . . . . . . . . . . . . 10 2.1.1. Protocol and Port Number . . . . . . . . . . . . . . . . 11 2.1.2. Multiple Interfaces and Main Address . . . . . . . . . . 11 2.1.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 11 2.1.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . 12 2.1.3.2. Message Header . . . . . . . . . . . . . . . . . . . . 12 2.1.4. Packet Processing and Message Flooding . . . . . . . . . 13 2.1.5. Message Emission and Jitter . . . . . . . . . . . . . . 16 2.2. Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 17 2.2.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 18 2.2.2. Neighbor Sensing Information Base . . . . . . . . . . . 20 2.2.2.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . 20 2.2.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 20 2.2.2.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21 2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . . 21 2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . . 22 2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . . 25 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes . . . . . 27 2.2.6. Advanced Neighbor Sensing Functioning . . . . . . . . . 27 2.2.6.1. Link Hysteresis . . . . . . . . . . . . . . . . . . . 28 2.2.6.2. Optional Link layer notification . . . . . . . . . . . 29 Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 2] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . . 30 2.3.1. Multipoint Relay Information Declaration . . . . . . . . 30 2.3.1.1. Topology Information Base . . . . . . . . . . . . . . 30 2.3.1.2. TC Message Generation . . . . . . . . . . . . . . . . 31 2.3.1.3. TC Message Processing . . . . . . . . . . . . . . . . 32 2.3.2. Multiple Interface Association . . . . . . . . . . . . . 34 2.3.2.1. Interface Association Information Base . . . . . . . . 34 2.3.2.2. MID Broadcast . . . . . . . . . . . . . . . . . . . . 35 2.3.2.3. MID Message Processing . . . . . . . . . . . . . . . . 36 2.3.3. Associated Networks and Hosts . . . . . . . . . . . . . 37 2.3.3.1. Host and Network Association Information Base . . . . 38 2.3.3.2. Host and Network Association Message Broadcast . . . . 38 2.3.3.3. HNA Message Processing . . . . . . . . . . . . . . . . 39 2.3.3.4. Optional Link layer notification . . . . . . . . . . . 40 2.3.4. Routing Table Calculation . . . . . . . . . . . . . . . 41 3. Node Configuration . . . . . . . . . . . . . . . . . . . . . 43 3.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 43 3.2. Routing Configuration . . . . . . . . . . . . . . . . . . 43 3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 44 3.4. Control Message Forwarding . . . . . . . . . . . . . . . . 44 4. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 44 5. Proposed Values for the Constants . . . . . . . . . . . . . 44 6. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 45 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 46 Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 3] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 1. Introduction The Optimized Link State Routing Protocol (OLSR) is developed for mobile ad hoc networks. It operates as a table driven and proactive protocol, thus exchanges topology information with other nodes of the network regularly. The nodes which are selected as a multipoint relay by some neighbor nodes announce this information periodically in their control messages. Thereby, a node announces to the network, that it has reachability to the nodes which have selected it as MPR. In route calculation, the MPRs are used to form the route from a given node to any destination in the network. The protocol uses the MPRs to facilitate efficient flooding of control messages in the net- work. MPRs are selected by a node among its one hop neighbors with "symmet- ric", i.e. bi-directional, link. Therefore, selecting the route through MPRs automatically avoids the problems associated with data packet transfer over uni-directional links (such as the problem of not getting link-layer acknowledgments for data packets at each hop) OLSR is developed to work independently from other protocols. Like- wise, OLSR makes no assumptions about the underlying link-layer. OLSR inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol) which is standardized by ETSI [3]. The protocol is developed in the IPANEMA project (part of the Euclid program) and in the PRIMA project (part of the RNRT program). 1.1. Changes Major changes from version 04 to version 05 - Introduction of support for multiple interfaces - Introduction of support for associated hosts and networks. - Introduction of support for advanced neighbor sensing through hysteresis. - Modularity between neighbor sensing and topology discovery emphasized. Major changes from version 03 to version 04 - Finalized the generic packet/message format to include fea- tures for scope-limited (diameter-bound) flooding of messages Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 4] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 and to handle duplicate messages. - Editorial changes towards language consistency. Major changes from version 02 to version 03 - Introduction of assigned port number for use with OLSR. - The packet format now uses "message length" rather than an offset to the next message. - Optional section describing how link-layer notifications can be utilized included. Major changes from version 01 to version 02 - Introduction of a unified packet format for encapsulation of all messages being exchanged between nodes. This also serves to facilitate extensions in future versions of the protocol (i.e. introduction of new protocol messages) without breaking backwards compatibility. - Removal of "Power Conservation" from this draft. Power Conser- vation may be considered as an extension to the basic routing capabilities. 1.2. OLSR 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 [5]. The OLSR protocol uses the following terminology: multipoint relay (MPR) A node which is selected by its one-hop neighbor, node X, to "re-transmit" all the broadcast messages that it receives from X, provided that the same message is not already received, and the time to live field of the message is greater than one. multipoint relay selector (MPR selector, MS) A node which has selected its one-hop neighbor, node X, as its multipoint relay, will be called a multipoint relay selector of node X. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 5] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 node A MANET router which implements this Optimized Link State Routing protocol. interface A network device participating in the MANET (it is usually wireless). A node may have several interfaces, each one pos- sessing its own IP address. link A link is a pair of interfaces (from two different nodes) sus- ceptible to hear one another (i.e. one may be able to receive traffic from the other). A node is said to have a link to another node when one of its interface has a link to one of the interfaces of the other node. neighbor interface An interface I is a neighbor interface of an interface J if J can hear I (i.e. it is possible to send traffic from I to J). sender interface The sender interface of a control message is the neighbor interface over which the message has been transmitted. receiver interface The reciever interface of a control message is the (local) interface, over which a control message has been recieved. neighbor node A node X is a neighbor node of node Y if node Y can hear node X (i.e. one of X interfaces is a neighbor interface of some interface of Y). symmetric link A bi-directional link between two interfaces, i.e. interface I and interface J where both can hear each other. symmetric neighborhood The symmetric neighborhood of any node X is the set of nodes Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 6] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 which have at least one symmetric link to X. symmetric 2-hop neighborhood The symmetric 2-hop neighborhood of X is the set of nodes which don't have a symmetric link to X but have a symmetric link to the symmetric neighborhood of X. main address The main address of a node, which will be used in OLSR control traffic as the "originator address" of all messages emitted by this node. It is the address of one of its interfaces. 1.3. Applicability Section OLSR is a proactive routing protocol for mobile ad-hoc networks (MANETs). It is well suited to large and dense mobile networks, as the optimization achieved using the MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its local information to route packets. OLSR is well suited for networks, where the traffic is random and sporadic between "several" nodes rather than being almost exclusively between a small specific set of nodes. The performance of the proto- col, compared to a reactive protocol, is even better if these [source, destination] pairs change with time [4]. Such changes may initiate substantial traffic (query flooding) in case of a reactive protocol, but nothing in OLSR, as the routes are maintained for each known destination all the time. 1.4. Protocol Overview OLSR is a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSR is an optimization over the pure link state protocol, tailored for mobile ad hoc networks. Firstly, it reduces the size of the control messages: rather than declaring all links, a node declares only a subset of links with its neighbors, namely the links to those nodes which are its MPR selec- tors. Secondly, OLSR minimizes flooding of control traffic by using only selected nodes, called MPRs, to diffuse its control messages. This technique significantly reduces the number of retransmissions in a flooding or broadcast procedure. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 7] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 OLSR MAY optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. Furthermore, as OLSR continuously maintains routes for all destina- tions in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source,destination] pairs are chang- ing over time. The protocol is particularly suited for large and dense networks, as the optimization done using MPRs works well in this context. The larger and more dense a network, the more optimiza- tion can be achieved as compared to the classic link state algorithm. OLSR is designed to work in a completely distributed manner and does thus not depend on any central entity. The protocol does NOT REQUIRE reliable transmission of control messages: each node sends control messages periodically, and can therefore sustain an occasional loss of some such messages. Such losses occur frequently in radio networks due to collisions or other transmission problems. Also, OLSR does not require sequenced delivery of messages. Each con- trol message contains a sequence number which is incremented for each message. Thus the recipient of a control message can easily identify which information is newer - even if messages have been re-ordered while in transmission. Furthermore, OLSR provides support for protocol extensions such as sleep mode operation, multicast-routing etc. Such extensions may be introduced as additions to the protocol without breaking backwards compatibility with earlier versions. OLSR performs hop by hop routing, i.e. each node uses its most recent local information to route a packet. Hence, for OLSR to be able to route packets, the frequency of control messages should be tuned to the speed of the mobile nodes such that their movements can be tracked by their neighborhood. OLSR does not require any changes to the format of IP packets. Thus any existing IP stack can be used as is: the protocol only interacts with routing table management. 1.5. Multipoint Relays The idea of multipoint relays is to minimize the overhead of flooding messages in the network by reducing duplicate retransmissions in the same region. Each node in the network selects a set of nodes in its symmetric neighborhood which may retransmit its messages. This set of selected neighbor nodes is called the "Multipoint Relay" (MPR) set of that node. The neighbors of node N which are *NOT* in its MPR set, Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 8] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 receive and process broadcast messages but do not retransmit broad- cast messages received from node N. Each node selects its MPR set among its one hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all nodes that are two hops away. The MPR set of N, denoted as MPR(N), is then an arbitrary subset of the symmetric neighborhood of N which satisfies the following condition: every node in the symmet- ric 2-hop neighborhood of N must have a symmetric link towards MPR(N). The smaller the MPR set is, the more optimal is the routing protocol. [2] gives an analysis and example of MPR selection algo- rithms. Each node maintains information about the neighbors that have selected it as MPR. This set is called the "Multipoint Relay Selector set" (MPR selector set) of a node. A node obtains this information from periodic HELLO messages received from the neighbors. A broadcast message, intended to be diffused in the whole network, coming from these MPR selectors is assumed to be retransmitted by the node. This set can change over time (i.e. when a node selects another MPR-set) and is indicated by the selector nodes in their HELLO mes- sages. Each node has a specific "Multipoint relay Selector Sequence Number" (MSSN) associated with this set. Whenever the MPR selector set is updated, the node also increments its MSSN. OLSR relies on selection of MPRs, and calculates routes through these nodes. I.e., the path is made of links between MPR and MPR selector. To enable this, each node in the network periodically floods informa- tion describing which neighbors have selected it as a MPR. Upon receipt of this "MPR Selector" information, each node calculates or updates the route to each known destination. So principally, the route is a sequence of hops through the MPRs from source to the des- tination. MPRs are selected among the symmetric neighborhood. Therefore, selecting the route through MPRs automatically avoids the problems associated with data packet transfer over uni-directional links such as the problem of not getting an acknowledgment for the data packets at each hop. 2. Protocol Functioning This section describes the details of the protocol functioning. This includes descriptions of the format and contents of the packets being exchanged by routers, the algorithms (e.g. for packet handling and routing table calculation) and suggested data structures internally kept in each router. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 9] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen as a transfer layer for the routing protocol. This provides nodes with information about their neighbors and offer an optimized mecha- nism for flooding messages through the concept of MPRs. It completely relies on the exchange of HELLO messages. The "Topoly Discovery" mechanism relies on the "Packet Forwarding" and "Neighbor Sensing" mechanisms. Neighbor and MPR information from the "Neighbor Sensing" mechanism is utilized by a node for diffusing local topology information to the whole network. Topology information is diffused through the "Packet Forwarding" mechanism, and relies on TC, MID and HNA messages. Resulting from the "Topology Discovery" mechanism is information which allows routing table calculation. The key notion in these modules is the MPR relationship. 2.1. Packet Format and Forwarding OLSR communicates using an unified packet format for all data related to the protocol. The purpose of this is to facilitate extensibility of the protocol without breaking backwards compatibility, as well as to provide an easy way of piggybacking different "types" of informa- tion into a single transmission. These packets are embedded in UDP datagrams for transmission over the network. The present draft is presented with IPv4 addresses. Considerations regarding IPv6 are given in section 4. Each packet encapsulates one or more messages. The messages share a common header format, which enables nodes to correctly accept and (if applicable) retransmit messages of an unknown type. Messages can be flooded onto the entire network, or flooding can be limited to nodes within a diameter (in terms of number of hops) from the originator of the message. Thus, broadcasting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be elim- inated locally (i.e. each node maintains a duplicate table to prevent transmitting the same message twice) and minimized in the entire net- work through the usage of MPRs as described in later sections. Furthermore, a node can examine the header of a message to obtain information on the distance (in terms of number of hops) to the orig- inator of the message. This feature may be useful in situations where, e.g., the time information from a received control messages stored in a node depends on the distance to the originator. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 10] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.1.1. Protocol and Port Number Packets in OLSR are communicated using UDP. Port 698 has been assigned by IANA for exclusive usage by the OLSR protocol. 2.1.2. Multiple Interfaces and Main Address A node may have several wireless interfaces, each of them having a distinct IP address. OLSR supports such nodes with multiple inter- faces. For this reason, each node MUST choose one of its interface addresses as its "main address". For example, the smallest interface address may be the chosen as the main interface. The main address MUST be used in OLSR control traffic as the "originator address" of all messages emitted by a node. A node must transmit and retransmit all control messages on all interfaces. The source address in the IP header must contain the IP- address of the interface where the message is transmitted. This address will be denoted the "sender interface address". 2.1.3. Packet Format The basic layout of any packet in OLSR is as follows (omitting the IP and UDP headers): 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Reserved | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Reserved | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 11] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : (etc) 2.1.3.1. Packet Header Packet Length The length (in bytes) of the packet Reserved MUST be set to "0000000000000000" to be in compliance with this version of the draft. The sender information for a packet is obtainable from the UDP header. 2.1.3.2. Message Header Message Type This field indicates which type of message are to be found in the "MESSAGE" partition. Message types in the range of 0-127 are reserved for messages in this draft and in extension drafts. Reserved MUST be set to "00000000" to be in compliance with this ver- sion of the draft. Message Size This field gives the size of this message, counted in bytes and measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field (or - if there are no following messages - the end of the packet). Originator Address Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 12] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 This field contains the main address of the node, which has originally generated this message. This field SHOULD NOT be confused with the source address from the UDP header, which is changed each time to the address of the intermediate interface which is "re-transmitting" this message. The Originator Address field MUST *NEVER* be changed in retransmissions. Time To Live This field contains the maximum number of hops a message will be transmitted. Before a message is retransmitted, the Time To Live MUST be decremented by 1. When a node receives a message with a Time To Live equal to 0 or 1, the message MUST NOT be retransmitted under any circumstances. Normally, a node would not receive a message with a TTL of zero. Thus, by setting this field, the originator of a message can limit the flooding radius. Hop Count This field contains the number of hops a message has attained. Before a message is retransmitted, the Hop Count MUST be incremented by 1. Initially, this is set to '0' by the originator of the mes- sage. Message Sequence Number While generating a message, the "originator" node will assign a unique identification number to each message. This number is inserted into the Sequence Number field of the message. The sequence number is increased by 1 (one) for each message orig- inating from the node - "wrap-arounds" are handled as described in a later section. Message sequence numbers are used to ensure that a given message is not retransmitted more than once by any node. 2.1.4. Packet Processing and Message Flooding Upon receiving a basic packet, the protocol parser examines each of the "message headers". Based on the value of the "Message Type" field, the parser can determine the fate of the message. A node may receive the same message several times. This can happen only if the message is retransmitted by two interfaces in the receivers neighbor- hood and the "Time To Live" and the "Hop Count" fields in the message Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 13] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 satisfy the following condition: Time To Live + Hop Count > 1 Thus, to avoid re-processing of a message which was already received and processed, each node maintains a Duplicate table. In this table, the node records information about the most recently received mes- sages where the above condition holds. For each message, satisfying the above condition, a node records a "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the originator address of the message, D_seq_num is the message sequence number of the message and D_time specifies the time at which a tuple expires and *MUST* be removed. In a node, the set of Duplicate Tuples are denoted the "Duplicate set". Thus, upon receiving a basic packet, a node performs the following tasks for each encapsulated message: 1 If the time to live of the message is less than or equal to '0' (zero), the message MUST silently be dropped. 2 If there exists a tuple in the duplicate set, where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number then the message has already been completely processed and MUST silently be ignored. 3 Otherwise, if the Message Type of the message is known to the node, the message MUST be processed according to the specifi- cations of such message type. 4 Otherwise, If the Message Type of the message is not known to the node, the message SHOULD be processed according to the following algorithm: 4.1 If the sender of the message is not detected to be in the symmetric neighborhood of the node, the message MUST silently be dropped. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 14] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 4.2 If the sender of the message is detected to be in the symmetric neighborhood of the node, an entry in the duplicate set is recorded with: D_addr = originator address D_seq_num = Message Sequence Number D_time = current time + D_HOLD_TIME. 4.3 If the sender address is the link interface address of a MPR selector of this node and if the time to live of the message is greater than '1', the message MUST be for- warded according to the following: 4.3.1 The TTL of the message is reduced by one. 4.3.2 The hop-count of the message is increased by one 4.3.3 The message is broadcasted on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) Notice: known message types are *not* forwarded "blindly" by this algorithm. Forwarding (and setting the correct message header in the forwarded, known, message) is the responsibility of the algorithm specifying how the message is to be handled. This enables, e.g., a message type to be specified such that the message can be modified while in transit (e.g. to reflect the route the message has taken). Further, it enables that the optimization through the MPRs can be bypassed: if for some reason pure flooding of a message type is required (e.g. to transmit control information over unidirectional links), the algorithm which specifies how such messages should be handled will simply rebroadcast the message, regardless of MPRs. Finally, notice that a message, which is to be broadcasted in the neighborhood but not flooded into the entire network, (e.g. a HELLO- message) is simply specified by setting the time to live to 1 (one) and the hop count to 0 (zero), and that no duplicate tuples are recorded for such messages. By defining a set of message types, which MUST be recognized by all implementations of OLSR, it will be possible to extend the protocol through introduction of additional message types, while still be able to maintain compatibility with older implementations. The REQUIRED Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 15] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 message types for OLSR are: - HELLO-messages, performing the task of neighbor sensing. - TC-messages, performing the task of MPR information declara- tion (OLSR topology declaration). - MID-messages, performing the task of multiple interface decla- ration. - HNA-messages, performing the task of associated host and/or network declaration Extensions may for example be messages enabling power conservation / sleep mode, multicast routing, support for unidirectional links, auto-configuration/address assignment etc. 2.1.5. Message Emission and Jitter As a basic implementation requirement, synchronization of control messages SHOULD be avoided. As a consequence, periodic OLSR messages should be emitted such that they avoid synchronization. Emission of control traffic from neighboring nodes may, for various reasons (mainly timer interactions with packet processing), become synchronized such that several neighbor nodes attempt to transmit control traffic simultaneously. Depending on the nature of the under- lying link-layer, this may or may not lead to collisions and hence message loss - possibly loss of several subsequent messages of the same type. To counter such synchronizations, the following simple strategy for emitting control messages is proposed. A node may add an amount of jitter to the interval at which messages are generated. The jitter must be a random value for each message generated. Thus, for a node utilizing jitter: Actual message interval = MESSAGE_INTERVAL + jitter Where jitter is a value, randomly selected from the interval [-MAXJITTER,0] and MESSAGE_INTERVAL is the value of the message interval specified for the message being emitted (e.g. HELLO_INTERVAL for HELLO messages, TC_INTERVAL for TC-messages etc.). It should be noticed that the present draft imposes a minimal rate of control message emission. However a node MAY send control messages at a higher rate (e.g. for better reacting to high mobility). It is an Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 16] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 implementation issue to optimize the rate of control packet emission. If all nodes use the same constant base rate, introducing some jitter as described above may be desirable. 2.2. Neighbor Sensing Each node should detect the neighbor interfaces with which it has a direct and symmetric link. Uncertainties over radio propagation may make some links unidirectional. Consequently, all links MUST be checked in both directions in order to be considered valid. To perform neighbor detection, each node broadcasts HELLO messages, containing information about heard neighbor interfaces and their link status. The link status may either be "symmetric", "heard" (asymmet- ric), "MPR" or "lost". "Symmetric" indicates, that the link has been verified to be bi-directional, i.e. it is possible to transmit data in both directions. "Heard" indicates that the node can hear HELLO messages from a neighbor interface, but it is not confirmed that this neighbor interface is also able to receive messages from the node. "MPR" indicates, that a node is selected by the sender as a MPR. A status of MPR further implies that the link is symmetric. "Lost" indicates that the link with this neighbor interface is now lost. HELLO messages are broadcasted to all one-hop neighbors and are emit- ted on each MANET interface of the node. They are *not relayed* to further nodes. More precisely, a HELLO message contains for each interface I: - a list of neighbor interface addresses, having a symmetric link to interface I; - a list of neighbor interface addresses, which are "heard" by interface I (for historical reasons, the term "heard" is used for "asymmetric"); - a list of neighbor interface addresses of neighbors selected as MPRs, AND having a symmetric link to interface I; - a list of neighbor interface addresses, which have been lost. These lists are computed as described in the HELLO message generation section. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 17] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.2.1. HELLO Message Format To accommodate the above requirements, as well as to accommodate for future extensions, an approach similar to the overall packet format is taken. Thus the proposed format of a HELLO message is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | # Interfaces | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Type | Interface # | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Type | Interface # | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : (etc) This is sent as the data-portion of the general packet format described in the Packet Format and Forwarding section, with the "Mes- sage Type" set to HELLO_MESSAGE and the TTL field set to 1 (one). Description of the fields Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 18] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 Reserved This field is reserved for future usage, and MUST be set to "000000000000000000000000" for compliance with this draft. # Interfaces This field indicates the number of additional MANET interfaces (excluding the main interface) possessed by the node. If the node has only one interface, this number is 0. Interface Address This field indicates the addresses of additional MANET inter- faces. The first one will be referenced as interface address number 1, the second as interface address number 2, and so on. The main address of the node (whose address is given in the originator field of the message header) will be referenced as interface address number 0. Link Message Size The size of the link message, counted in bytes and measured from the beginning of the "Link Type" field and until the next "Link Type" field (or - if there are no more link types - the end of the message). Interface # This field indicates the number of the interface to which the following list of neighbor interfaces corresponds. Number 0 indicates the main interface (whose address is the main address). Link Type This field specifies the type of the link between the inter- face of the sender, as identified by the interface number, and the following list of neighbor interfaces. As a minimum, the following four link types are REQUIRED by OLSR: - ASYM_LINK - indicating that the links are asymmetric (i.e. the neighbor interface is "heard"). - SYM_LINK - indicating that the links are symmetric. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 19] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 - MPR_LINK - indicating, that the links are symmetric AND that the neighbors have been selected as MPR by the sender. - LOST_LINK - indicating that the links have been lost. Neighbor Interface Address An interface address of a neighbor. Neighbor sensing is performed using HELLO message exchange, updating the neighbor sensing information base in each node. 2.2.2. Neighbor Sensing Information Base The neighbor sensing information base stores information about neigh- bor interfaces, 2-hop neighbors, MPRs and MPR selectors. 2.2.2.1. Neighbor Set For each of its interface I and for each neighbor interface NI, heard by I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr, N_main_addr, N_SYM_time, N_ASYM_time, N_time) where N_if_id is the identification number of I, N_if_addr is the address of the neighbor interface NI, N_main_addr is the main address of the neighbor pos- sessing NI, N_SYM_time is the time until which the link is considered symmetric, N_ASYM_time is the time until which the neighbor interface is considered heard, and N_time specifies the time at which this record expires and *MUST* be removed. When N_SYM_time and N_ASYM_time are expired, the link is considered lost. This information is used when declaring the neighbor interfaces in the HELLO messages. N_SYM_time and N_ASYM_time are used to decide the Link Type declared for the neighbor interface. If N_SYM_time is not expired, the link is declared symmetric. If N_SYM_time is expired but N_ASYM_time is not, the link is declared heard. If both N_SYM_time and N_ASYM_time are expired, the link is declared lost. In a node, the set of Neighbor Tuples are denoted the "Neighbor Set". 2.2.2.2. 2-hop Neighbor Set A node records a set of "2-hop tuples" (N_main_addr, N_if_addr, N_2hop_addr, N_time), describing symmetric or MPR links between its neighbors and the 2-hop symmetric neighborhood. N_main_addr and N_if_addr are the main address and an interface address of a Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 20] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 neighbor, N_2hop_addr is an interface address of a 2-hop neighbor with a symmetric or MPR link to interface N_if_addr and N_time speci- fies the time at which the tuple expires and *MUST* be removed. This information is gathered from the HELLO messages received by a node from its neighbor nodes. In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor Set". 2.2.2.3. MPR Set A node maintains a set of neighbors which are elected as MPR. Their main addresses are listed in the so-called MPR Set. The Multipoint relay selection section describes how MPRs are elected. 2.2.2.4. MPR Selector Set A node maintains information (obtained from the HELLO messages) about the neighbors which have selected this node as a MPR. Thus, a node records a MPR-selector tuple (MS_if_addr, MS_main_addr, MS_time), for interfaces of a neighbor which has selected the node as MPR. MS_if_addr is the address of an interface of a node which has selected the node as MPR for that interface, MS_main_addr is the main address of the MPR selector and MS_time specifies the time at which a tuple expires and *MUST* be removed. In a node, the set of MPR-selector tuples are denoted the "MPR Selec- tor Set". A sequence number, MSSN, is associated with this set. When- ever a tuple is added to or removed from this set, the MSSN is incre- mented by 1. 2.2.3. HELLO Message Generation The lists of addresses declared in a HELLO message are computed from the Neighbor Set as follows: - for each tuple where N_SYM_time and N_ASYM_time are expired, the N_if_addr is declared with LOST_LINK Link Type for inter- face N_if_id; - for each tuple where N_SYM_time is not expired, the N_if_addr is declared with MPR_LINK Link Type if N_main_addr is in the MPR set and SYM_LINK Link Type otherwise; Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 21] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 - for each tuple where N_SYM_time is expired but N_ASYM_time is not expired, the N_if_addr is declared with ASYM_LINK Link Type. The list of neighbor interfaces in a HELLO message can be partial (e.g. due to message size limitations, imposed by the network), the rule being the following: for each interface a neighbor interface is heard on, its address is cited with corresponding interface id at least once within a predetermined refreshing period (HELLO_INTERVAL). Notice that for limiting the impact from loss of control messages, it is desirable that a message fits in a single MAC packet. Each HELLO message generated is broadcasted on each MANET interface of the node. 2.2.4. HELLO Message Processing Upon receiving a HELLO message, the node SHOULD update the neighbor information corresponding to the sender node address (a node may - e.g. for security reasons - wish to restrict updating the neighbor- table, i.e. ignoring HELLO messages from some nodes). In this section, the term "Originator Address" will be used for the main address of the node which sent the HELLO-message. The term "Sender Interface Address" will be used for the sender address (given in the IP header of the packet containing the message) of the inter- face which sent the HELLO message. The term "Receiver Interface" will be used for the interface which received the HELLO message. The term "link interface addresses" will be used for the own interface addresses of the sender listed in the HELLO message. The Neighbor Set should be updated as follows: 1 Upon receiving a HELLO message, if there exists no neighbor tuple with N_if_addr == Sender Interface Address and N_if_id == identifier of the Receiver Interface, a new tuple is created with Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 22] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 N_if_addr = Sender Interface Address N_if_id = identifier of the Receiver Interface N_SYM_time = current time - 1 (expired time) N_time = current time + NEIGHB_HOLD_TIME 2 The tuple is then modified as follows: 2.1 N_main_addr = Originator Address. 2.3 N_time = max (N_time, current time + NEIGHB_HOLD_TIME); 2.4 N_ASYM_time = current time + NEIGHB_HOLD_TIME; 2.5 if the node finds the receiver interface address among the addresses listed in the HELLO with: Link Interface Address == Sender Interface Address, then, the tuple is modified as follows: if Link Type == LOST_LINK then N_SYM_time = current time - 1 (expired time) else: N_SYM_time = current time + NEIGHB_HOLD_TIME, N_time = current time + 2 * NEIGHB_HOLD_TIME. The rule for setting N_time is the following: a link loosing its sym- metricity should still be advertised at least NEIGHB_HOLD_TIME. This allows neighbors to detect the link breakage. The 2-hop Neighbor Set is updated as follows: 1 for each 2-hop interface address listed in the HELLO message with Link Type SYM_LINK or MPR_LINK, a 2-hop tuple is created with: N_main_addr = Originator Address; Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 23] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 N_if_addr = Link Interface Address corresponding to the 2-hop interface address; N_2hop_addr = the interface address of the 2-hop neigh- bor; N_time = current time + NEIGHB_HOLD_TIME. This tuple may replaces an older similar tuple with same N_if_addr and N_2hop_addr values. 2 For each 2-hop interface address listed in the HELLO message with Link Type LOST_LINK or ASYM_LINK, all the 2-hop tuples where: N_if_addr == Link Interface Address corresponding to the 2-hop interface address, and N_2hop_addr == the 2-hop interface address are deleted. Based on the information obtained from the HELLO messages, each node constructs its MPR selector set. Thus, upon receiving a HELLO message, if a node finds one of its interface addresses in a list with a link type of "MPR", it MUST update the MPR selector set to contain updated information about the sender of the HELLO message: 1 If there exists no MPR selector tuple with: MS_if_addr == Link Interface Address and MS_main_addr == Originator Address then MSSN is incremented to indicate that the MPR selector table is going to change. 2 If there exists no MPR selector tuple with: MS_if_addr == Link Interface Address Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 24] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 then a new tuple is created with: MS_if_addr = Link Interface Address 3 The tuple is then modified as follows: MS_main_addr = Originator Address, MS_time = current time + NEIGHB_HOLD_TIME. Deletion of MPR selector tuples occurs in case of expiration of the timer or in case of link breakage as described in the neighborhood and 2-hop neighborhood changes section. 2.2.5. Multipoint Relay Selection Each node in the network selects, independently, its own set of MPRs among its symmetric neighborhood. The symmetric links with MPRs are advertised with Link Type MPR_LINK instead of SYM_LINK in HELLO mes- sages. MPRs are used to flood control messages from that node into the net- work while reducing the number of retransmissions that will occur in a region. Thus, the concept of MPR is an optimization of a pure flooding mechanism. The MPR set must be calculated by a node in such a way that it, through the neighbors in the MPR-set, can reach all symmetric 2-hop neighbors which are not at the same time symmetric neighbors of the node. This means that the union of the symmetric neighborhoods of the MPR nodes contains the symmetric 2-hop neighborhood. While it is not essential that the MPR set is minimal, it is essential that all 2-hop neighbors can be reached through the selected MPR nodes. The smaller a MPR-set, however, the more optimization is achieved. By default, the MPR set can coincide with the entire symmetric neigh- bor set. This will be the case at network initialization. The following specifies a proposed heuristic for selection of MPRs [2] adapted for multiple interfaces support. It constructs a MPR-set that allows to reach any symmetric 2-hop interface (i.e. any inter- face of a 2-hop neighbor having a symmetric link with a neighbor). The following terminology will be used in describing this algorithm (neighbors are identified by their main address and 2-hop interfaces by their address): Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 25] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 N: The set of neighbors with which there exists a symmetric link. N2: The set made of the symmetric 2-hop interfaces excluding all the interfaces of members of N and the interfaces of the node performing the computation. D(y): Degree of one hop neighbor node y (where y is a member of N), defined as the number of symmetric neighbor interfaces of node y, EXCLUDING all the interfaces of members of N and the inter- faces of the node performing the computation. The proposed heuristic is as follows: 1 Start with an empty MPR set 2 Calculate D(y), where y is a member of N, for all nodes in N. 3 Select as MPRs those nodes in N which provide the "only path" to some interfaces in N2. 4 While there exist interfaces in N2 which are not covered by the MPR set: 4.1 For each node in N, calculate the number of interfaces in N2 which are not yet covered by the MPR set and are reachable through this one hop neighbor; 4.2 Select as a MPR the node from N which provides reachabil- ity to the maximum number of uncovered interfaces in N2. In case of a tie, select that node as MPR whose D(y) is greater. 5 As an optimization, process each node y in the MPR set. If the MPR set excluding y still covers all interfaces in N2, node y is removed from the MPR set. When the MPR set has been computed, all the corresponding main addresses are stored in the MPR Set. Some processing such as MPR set re-calculation should occur when changes are detected in the neighborhood or the 2-hop neighborhood. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 26] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes A change in the neighborhood is detected when: - The N_SYM_time field of a neighbor tuple expires. This is con- sidered as a neighbor loss if it was the last link with a neighbor node (on the contrary, a link with an interface may break while a link with another interface of the neighbor node is still alive). - The N_ASYM_time field of a neighbor tuple expires and N_SYM_time is expired. The link is then considered lost. - A new neighbor tuple is inserted in the Neighbor Set with a valid N_SYM_time or a tuple with expired N_SYM_time is modi- fied so that N_SYM_time becomes valid. This is considered as a neighbor appearance if there was previously no link with the corresponding neighbor node. A change in the 2-hop neighborhood is detected when a 2-hop neighbor tuple expires or is deleted according to the HELLO message processing section. The following processing should occur when changes in the neighbor- hood or the 2-hop neighborhood are detected: - In case of neighbor loss, all the 2-hop tuples with N_main_addr == Main Address of the neighbor are deleted. - In case of neighbor loss, all the MPR selector tuples with MS_main_addr == Main Address of the neighbor are deleted - The MPR set is re-calculated when a neighbor appearance or loss is detected, or when a change in the 2-hop neighborhood is detected. - An additional HELLO message may be sent when the MPR set changes. 2.2.6. Advanced Neighbor Sensing Functioning Established links should be as reliable as possible to avoid data packet loss. To enhance the reliability of the neighbor sensing mech- anism, the following implementation recomendations should be consid- ered. Each neighbor tuple in the neighbor set SHOULD, in addition to what Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 27] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 is described in section 2.2.2.1, include a N_pending field, a N_qual- ity field, and a N_LOST_time. N_pending is a boolean value specify- ing if the link is considered pending (i.e. the link is not consid- ered established). N_quality is a dimensionless number between 0 and 1 describing the quality of the link. N_LOST_time is a timer for declaring a link as lost when an established link becomes pending. HELLO message generation should consider those new fields as follows. 1 If N_LOST_time is not expired, the link is advertised with a link type of LOST_LINK; 2 otherwise, if N_LOST_time is expired and N_pending is set to "true", the link SHOULD NOT be advertised at all; 3 otherwise, if N_LOST_time is expired and N_pending is set to "false", the link is advertised as described in the HELLO mes- sage generation section. A node considers it has a symmetric link for each neighbor tuple such that N_LOST_time is expired, N_pending is "false" and N_SYM_time is not expired. This should be taken as definition for computing the symmetric neighborhood when computing the MPR set. Apart from the above points, what has been previously describe do not interfere with this newly introduced fields. The N_quality, N_pending and N_LOST_time fields are updated according to the present section and nowhere else. The other fields are not modified by the advanced neighbor sensing functioning. This advanced functioning is described as separately as possible to increase readability. 2.2.6.1. Link Hysteresis The link between a node and some of its neighbor interfaces might be "bad", i.e. from time to time let HELLOs pass through only to fade out immediately after. In this case, the neighbor information base would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of link layer notification, such a bad link would spoil routing. To cope with such unstable links, the following hysteresis strategy SHOULD be adopted. For each neighbor interface NI heard by interface I, the N_quality Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 28] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 field of the corresponding Neighbor Tuple determines the establish- ment of the link. Its value is compared to two thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW which are fixed between 0 and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. When N_quality becomes higher than HYST_THRESHOLD_HIGH, the N_pending field is set to false. When N_quality goes below HYST_THRESHOLD_LOW, the N_pending field is set to true and N_LOST_time is set to min (N_time, current time + NEIGHB_HOLD_TIME) (the link is then consid- ered as lost according to the Neighborhood and 2-hop neighborhood changes section and this may produce a neighbor loss). The condition for considering a link established is thus stricter than the condi- tion for loosing it. As a basic implementation requirement, an estimation of the link quality must be maintained and stored in the N_quality field. If some measure of the signal/noise level on a received message is available (e.g. as a link layer notification), then it can be used as estima- tion after normalization. If no signal/noise information is available from the link layer, an algorithm such the following can be utilized. The algorithm is parametrized by a scaling parameter HYST_SCALING which is a number fixed between 0 and 1. For each neighbor interface NI heard by inter- face I, the first time NI is heard by I, N_quality is set to HYST_SCALING (and N_pending is set to true). A tuple is updated according to two rules. Every time an OLSR mes- sage emitted by NI is received by I, the stability rule is applied: N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING. When an OLSR message emitted by NI is lost by I, the instability rule is applied: N_quality = (1-HYST_SCALING)*N_quality. The loss of OLSR messages is detected by tracking the missing Message Sequence Numbers and by long period of silence. If no HELLO message has been received for a HELLO_INTERVAL period, a loss of HELLO mes- sage is detected. 2.2.6.2. Optional Link layer notification OLSR is designed not to impose or expect any specific information from the link layer. However, if information from the link-layer is available, a node MAY use this as described in this section. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 29] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 If link layer information describing connectivity to neighboring nodes is available (i.e. loss of connectivity such as through absence of a link layer acknowledgment), this information is used in addition to the information from the HELLO-messages to maintain the neighbor information base and the MPR selector set. Thus, upon receiving a link-layer notification that the link between a node and a neighbor interface is broken, the following actions are taken: 1 if the link is broken to either a symmetric or asymmetric neighbor interface, the corresponding neighbor tuple is modi- fied: N_LOST_time and N_time are set to current time + NEIGHB_HOLD_TIME. 2 this is considred as a link loss and the appropriate process- ing described in the neighborhood and 2-hop neighborhood changes section should be performed. 2.3. Topology Discovery The Neighbor Sensing part of the protocol basically offers to each node a list of neighbors with which it can communicate directly and an optimized flooding mechanism through MPRs. Based on this mecha- nism, topology information is disseminated through the network. The present section describes what part of the information given by the Neighbor Sensing is disseminated and how it is used to construct routes. Routes are constructed through MPR-links and links with neighbors. A node thus basically disseminates its MPR-selector set. If a node has multiple interfaces, it must also disseminate the list of its inter- face addresses. 2.3.1. Multipoint Relay Information Declaration 2.3.1.1. Topology Information Base Each node in the network maintains topological information about the network. This information is acquired from TC-messages and is used for routing table calculations. Thus, for each destination in the network, a "Topology Tuple" (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main address of a node, which may be reached in one hop from the node with Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 30] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 the main address T_last. Typically, T_last is a MPR of T_dest. T_seq is a sequence number, and T_time specifies the time at which this tuple expires and *MUST* be removed. In a node, the set of Topology Tuples are denoted the "Topology Set". 2.3.1.2. TC Message Generation In order to build the topology information base needed, each node, which has been selected as MPR, broadcasts Topology Control (TC) mes- sages. TC messages are flooded to all nodes in the network and take advantage of MPRs. MPRs enable a better scalability in the distribu- tion of topology information [1]. A TC message is sent by a node in the network to declare its MPR Selector set. I.e., the TC message contains the list of neighbors which have selected the sender node as a MPR. The sequence number (MSSN) associated with this MPR selector set is also sent with the list. The list of addresses can be partial in each TC message (e.g. due to message size limitations, imposed by the network), but parsing of all TC messages describing the MPR selector set of a node MUST be complete within a certain refreshing period (TC_INTERVAL). The infor- mation diffused in the network by these TC messages will help each node calculate its routing table. A node which has an empty MPR selector set, i.e. nobody has selected it as a MPR, SHOULD NOT gener- ate any TC message. A node MAY transmit additional TC-messages to increase its reactive- ness to link failures. I.e. when a change to the MPR selector set is detected and this change can be attributed to a link failure, a TC- message SHOULD be transmitted after a shorter interval than TC_INTER- VAL. The proposed format of a TC message is 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MSSN | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multipoint Relay Selector Main Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multipoint Relay Selector Main Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 31] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 This is sent as the data-portion of the general message format with the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set to 255 (maximum value) to diffuse the message into the entire net- work. Description of the fields MPR Selector Sequence Number (MSSN) A sequence number is associated with the MPR selector set. Every time a node detects a change in its MPR selector set, it increments this sequence number. This number is sent in this MSSN field of the TC message to keep track of the most recent information. When a node receives a TC message, it can decide on the basis of this MPR Sequence Number, whether or not the received information about the MPR selectors of the originator node is more recent than what it already has. Multipoint Relay Selector Main Address This field contains the main address of a node, which has selected the Originator node (of the TC message) as a MPR. All addresses of the MPR selectors of the Originator node are put in the TC message. If the maximum allowed message size (as imposed by the network) is reached while there are still MPR selector addresses which which have not been inserted into the TC-message, more TC messages will be generated until the entire MPR selector set has been sent. Reserved This field is reserved for future usage, and MUST be set to "0000000000000000" for compliance with this draft. 2.3.1.3. TC Message Processing TC messages are broadcasted and retransmitted by the MPRs in order to diffuse the messages in the entire network. In this section, the term "originator" is used to designate the node from which the message originally originated, while the term "sender" is used to designate the node from which the message was received (i.e. the "last hop" of the message). The tuples in the topology set are recorded with the topology infor- mation that is exchanged through TC messages, according to the Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 32] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 following algorithm: 1 If the sender interface (NB: not originator) of this message is not in the symmetric neighborhood of this node, the message is discarded. 2 A tuple is inserted into the duplicate table to prevent it from being processed again with: D_addr = originator address D_seq_num = Message Sequence D_time = current time + D_HOLD_TIME. 3 If there exist some tuple in the topology set where: T_last == originator address AND T_seq > MSSN, then no further processing of this TC message is performed and the message is silently discarded (case: message received out of order). 4 All tuples in the topology set where: T_last == originator address AND T_seq < MSSN are removed from the topology set. 5 For each of the MPR selector address received in the TC mes- sage: 5.1 If there exist some tuple in the topology set where: T_dest == MPR selector address, AND T_last == originator address, then the holding time of that tuple is set to: Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 33] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 T_time = current time + TOP_HOLD_TIME. 5.2 Otherwise, a new tuple is recorded in the topology set where: T_dest = MPR selector address, T_last = originator address, T_seq = MSSN, T_time = current time + TOP_HOLD_TIME. 6 If the sender address is the link interface address of a MPR selector of this node and if the time to live of the message is greater than '1', the message MUST be forwarded according to the following: 6.1 The TTL of the message is reduced by one. 6.2 The hop-count of the message is increased by one 6.3 The message is broadcasted on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) 2.3.2. Multiple Interface Association Each node in the network maintains interface information about the other nodes in the network. This information acquired from MID-messages, emit- ted by nodes with multiple interfaces participating in the MANET, and is used for routing table calculations. 2.3.2.1. Interface Association Information Base For each destination in the network, "Interface association Tuples" (I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter- face address of a node, I_main_addr is the main address of this node. I_time specifies the time at which this tuple expires and *MUST* be removed. In a node, the set of Interface association Tuples is denoted the "Interface association Set". Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 34] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.3.2.2. MID Message Broadcast In order to build the interface association information base, each node with multiple interfaces broadcast Multiple Interface Declara- tion (MID) messages. MID messages are flooded to all nodes in the network and take advantage of MPRs. A MID message is sent by a node in the network to declare its multi- ple interfaces (if any). I.e., the MID message contains the list of interface addresses which are associated to its main address. The list of addresses can be partial in each TC message (e.g. due to mes- sage size limitations, imposed by the network), but parsing of all MID messages describing a nodes interface set MUST be complete within a certain refreshing period (MID_INTERVAL). The information diffused in the network by these MID messages will help each node to calculate its routing table. A node which has only a single interface address participating in the MANET (i.e. running OLSR), MUST NOT generate any MID message. A node with more interfaces, where only one is participating in the MANET and running OLSR (e.g. a node is connected to a wired network as well as to a MANET) MUST NOT generate any MID messages. The proposed format of a MID message is 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This is sent as the data-portion of the general message format with the "Message Type" set to MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value) to diffuse the message into the entire network. Description of the fields Interface Address Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 35] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 This field contains the address of an interface of the node other than its main address (already indicated in the origina- tor address). All interface addresses other than the main address of the Originator node are put in the MID message. If the maximum allowed message size (as imposed by the network) is reached while there are still interface addresses which have not been inserted into the MID-message, more MID messages are generated until the entire interface addresses set has been sent. 2.3.2.3. MID Message Processing MID messages are broadcasted and retransmitted by the MPRs in order to diffuse the messages in the entire network. In this section, the term "originator" is used to designate the node from which the message originally originated, while the term "sender" is used to designate the node from which the message was received (i.e. the "last hop" of the message). The tuples in the multiple interface association set are recorded with the information that is exchanged through MID messages, follow- ing the following algorithm: 1 If the sender (NB: not originator) of this message is not in the symmetric neighborhood of this node, the message is dis- carded. 2 A tuple is inserted into the duplicate table to prevent it from being processed again with: D_addr = originator address D_seq_num = Message Sequence D_time = current time + D_HOLD_TIME. 3 For each of the interface address received in the MID message: 3.1 If there exist some tuple in the interface association set where: I_if_addr == interface address, AND Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 36] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 I_main_addr == originator address, then the holding time of that tuple is set to: I_time = current time + MID_HOLD_TIME. 3.2 Otherwise, a new tuple is recorded in the interface asso- ciation set where: I_if_addr = interface address, I_main_addr = originator address, I_time = current time + MID_HOLD_TIME. 4 If the sender address is the link interface address of a MPR selector of this node and if the time to live of the message is greater than '1', the message MUST be forwarded according to the following: 4.1 The TTL of the message is reduced by one. 4.2 The hop-count of the message is increased by one 4.3 The message is broadcasted on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) 2.3.3. Associated Networks and Hosts A node MAY provide access to a set of associated hosts. I.e., a node may act as a "gateway" between the MANET and a number of associated hosts and/or subnets, not running OLSR and thus not participating in the MANET. Thus, a node SHOULD be able to inject routing information describing these associated hosts or networks into MANET, as SHOULD all nodes be capable of interpreting such information. Notice, that this is a different case from that of "multiple inter- faces", described previously. Where, in the "Multiple Interface Asso- ciations", all the described interfaces were participating in the MANET through running the OLSR protocol, this section addresses the interfaces which do not participate. This is, e.g., the case where a node has both a wireless interface (participating in the MANET) and a wired interface, through which a number of hosts statically connect (to the nodes in the MANET). To accomplish this, a node, to which there are associated hosts Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 37] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 and/or networks, periodically issues an Host and Network Association (HNA) message, containing sufficient information for the recipients to construct an appropriate routing table. 2.3.3.1. Host and Network Association Information Base Each node maintains information concerning which nodes may act as "gateways" to associated hosts and networks by recording "association tuples" (GW_main_addr, NET_addr, NET_mask, GS_time), where GW_main_addr is the main address of the gateway, NET_addr and NET_mask specifies the network address and netmask of a network, reachable through this gateway, and GS_time specifies the time at which this tuple expires and hence *MUST* be removed. The set of all association tuples in a node is called the "associa- tion set". 2.3.3.2. Host and Network Association Message Broadcast A node with associated hosts and/or networks SHOULD periodically gen- erate a Host and Network Association (HNA) message, containing pairs of (network address, netmask) corresponding to the connected hosts and networks. HNA-messages SHOULD be transmitted periodically every HNA_INTERVAL. A node without any associated hosts and/or networks SHOULD NOT gener- ate HNA-messages. The proposed format of an HNA-message is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Netmask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Netmask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This is sent as the data part of the general packet format with the "Message Type" set to HNA and the TTL field set to 255. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 38] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 It should be noticed, that the HNA-message can be considered as a "generalized version" of the TC-message: the originator of both the HNA and TC messages announce "reachability" to some other host(s). In the TC-message, no netmask is required, since all reachability is announced on a per-host basis. In HNA-messages, announcing reachabil- ity to an address sequence through a network- and netmask address is typically preferred over announcing reachability to individual host addresses. Description of the fields Network Address The network address of the associated network Netmask The netmask, corresponding to the network address immediately above. 2.3.3.3. HNA Message Processing In this section, the term "originator address" is used to designate the main address of the node which originally issued the HNA-message. Upon receiving a HNA-message, the node performs the following: 1 An entry in the duplicate set is recorded for this message with: D_addr = originator address D_seq_num = Message Sequence Number D_time = current time + D_HOLD_TIME. 2 For each (network address, netmask) pair in the message: 2.1 if an entry in the association set already exists, where: GW_main_addr == originator address NET_addr == network address Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 39] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 NET_mask == netmask then the holding time for that tuple is set to: GW_time = current time + GW_HOLDING_TIME 2.2 otherwise, a new tuple is recorded with: GW_main_addr == originator address NET_addr == network address NET_mask == netmask GW_time = current time + GW_HOLDING_TIME 3 If the sender address is the link interface address of a MPR selector of this node and if the time to live of the message is greater than '1', the message MUST be forwarded according to the following: 3.1 The TTL of the message is reduced by one. 3.2 The hop-count of the message is increased by one 3.3 The message is broadcasted on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) 2.3.3.4. Optional Link layer notification Detection of a link failure between a node and one of its MPR selec- tors through a link-layer notification may trigger additional TC-mes- sages to increase the protocols reactiveness to link failures. I.e. when a change to the MPR selector set is detected and this change can be attributed to a link failure, an additional TC-message SHOULD be transmitted. Thus, if a link failure appears to be a neighbor loss with a neigh- bor, which has selected this node as MPR, the MPR selector set is updated (MSSN is thus incremented) and a TC message SHOULD be gener- ated. Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 40] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 2.3.4. Routing Table Calculation Each node maintains a routing table which allows it to route data, destined for the other nodes in the network. The routing table is based on the information contained in the neighbor sensing informa- tion base, the interface association set and the topology set. There- fore, if any of these tables are changed, the routing table is re- calculated to update the route information about each destination in the network. The route entries are recorded in the routing table in the following format: 1. R_dest R_next R_dist R_if_id 2. R_dest R_next R_dist R_if_id 3. ,, ,, ,, Each entry in the table consists of R_dest, R_next, R_dist, and R_if_id which specifies that the node identified by R_dest is esti- mated to be R_dist hops away from the local node, and that the sym- metric neighbor node with interface address R_next is the next hop node in the route to R_dest, and this one hop is reachable through the local interface R_if_id. Entries are recorded in the table for each destination in the network for which the route is known. All the destinations for which the route is broken or partially known are not entered in the table. This routing table is updated when a change is detected in the neigh- bor information base, or the topology set. More precisely, it is re- calculated in case of neighbor appearance or loss, or when a topology tuple is created or removed. The update of this routing information does not generate or trigger any messages to be transmitted, neither in the network, nor in the one-hop neighborhood. To construct the routing table of node X, a shortest path algorithm is run on the directed graph containing the arcs X -> Y where Y is any symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and the arcs U -> V where there exists an entry in the topology set with V as T_dest and U as T_last. The following procedure is given as an example to calculate (or re- calculate) the routing table : 1 All the entries from the routing table are removed. 2 The new routing entries are added starting with the symmetric neighbors (h=1) as the destination nodes. For each neighbor Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 41] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 tuple in the neighbor set, corresponding to a symmetric link (i.e. N_LOST_time is expired, N_pending == false and N_SYM_time is not expired), a new routing entry is recorded in the routing table where R_dest is set to the main address N_main_addr of the neighbor, R_next is set to the interface address N_if_addr of the neigh- bor interface, R_dist is set to 1, and R_if_id is set to the value field N_if_id of the entry. If N_if_addr is distinct of N_main_addr, another new routing entry with R_dest = N_main_addr, R_next = N_if_addr, R_if_id = N_if_id and R_dist = 1 is added. 3 The new route entries for the destination nodes h+1 hops away are recorded in the routing table. The following procedure is executed for each value of h, starting with h=1 and increment- ing it by 1 each time. The execution will stop if no new entry is recorded in an iteration. 3.1 For each topology entry in the topology table, if its T_dest does not correspond to R_dest of any route entry in the routing table AND its T_last corresponds to R_dest of a route entry whose R_dist is equal to h, then a new route entry is recorded in the routing table (if it does not already exist) where: R_dest is set to T_dest; R_next is set to R_next of the recorded route entry whose R_dest is equal to T_last R_dist is set to h+1; and R_if_id is set to the value of the R_if_id of the recorded route entry whose R_dest is equal to T_last. The routing table is further completed by using the multiple inter- face association set: 1 For each entry in the multiple interface association where there exists a routing entry such that: R_dest == I_main_addr (of the multiple interface inter- face association entry) Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 42] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 a route entry is created in the routing table with: R_dest = I_if_addr (of the multiple interface associa- tion entry) R_next = R_next (of the recorded route entry) R_dist = R_dist (of the recorded route entry) R_if_id = R_if_id (of the recorded route entry). The routing table is finally completed by using the host and network association set: 1 For each tuple in the routing set, record an entry in the routing table, with: R_dest = NET_addr/NET_mask R_next = the next hop on the path from the node to GW_main_addr R_dist = dist to GW_main_addr R_next and R_if_id are set to the same values as the tuple from the routing set with R_dest == GW_main_addr. 3. Node Configuration 3.1. Address Assignment The nodes in the MANET network SHOULD be assigned addresses within a defined address sequence. I.e., the nodes in the MANET SHOULD be addressable through a network address and a netmask. Likewise, the nodes in each associated network SHOULD be assigned addresses from a defined address sequence, distinct from that being used in the MANET. 3.2. Routing Configuration MANET nodes MUST be configured such that they have a network route set up on one of the interfaces participating in the MANET. I.e., in Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 43] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 lack of other routing information, any incoming datagrams, destined for a node in the MANET address sequence, is transmitted onto this interface (efficiently: incoming data to a MANET node, which the node cannot find an exact match for, is broadcast to all neighbors) Any node with associated networks or hosts SHOULD, in addition to the configuration described above, be configured such that it has routes set up to the interfaces with associated hosts or network. 3.3. Data Packet Forwarding OLSR itself does not perform packet forwarding. Rather, it maintains the routing table in the underlying operating system, which is assumed to be forwarding packets as specified in RFC1812. 3.4. Control Message Forwarding Control messages, destined for flooding into the entire network, SHOULD be relayed by the MPR via the following rule: A node retransmits a message only when it is received from one of its MPR selector AND it is not before registered in the duplicate table AND the time to live is greater than 1 (one). Before retransmitting, the hop count is incremented by one and the time to live is decremented by one. 4. IPv6 Considerations All the operations and parameters described in this document used by OLSR for IP version 4 are the same as those used by OLSR for IP ver- sion 6. However, with IP version 6, we only need to replace all the 4 bytes Ipv4 address field in different messages with 16 bytes Ipv6 address format. 5. Proposed Values for the Constants This section list the values for the constants used in the descrip- tion of the protocol. HELLO_INTERVAL = 2 seconds TC_INTERVAL = 5 seconds Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 44] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 MID_INTERVAL = TC_INTERVAL HNA_INTERVAL = TC_INTERVAL NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL TOP_HOLD_TIME = 3 x TC_INTERVAL D_TIME = 30 seconds I_TIME = 3 x MID_INTERVAL GW_TIME = 3 x HNA_INTERVAL HELLO_MESSAGE = 1 TC_MESSAGE = 2 MID_MESSAGE = 3 HNA_MESSAGE = 4 ASYM_LINK = 1 SYM_LINK = 2 MPR_LINK = 3 LOST_LINK = 4 HYST_THRESHOLD_HIGH = 0.8 HYST_THRESHOLD_LOW = 0.3 HYST_SCALING = 0.5 MAXJITTER = 0.5 6. Sequence Numbers Sequence numbers are used in OLSR with the purpose of discarding "old" information, i.e. messages received out of order. However with Clausen Jacquet Laouiti Minet Muhlethaler Qayyum Viennot [Page 45] INTERNET-DRAFT Optimized Link State Routing 31 October 2001 a limited number of bits for representing sequence numbers, wrap- arounds (that the sequence number is incremented from the maximum possible value to zero) will occur. To prevent this from interfering with the operation of the protocol, the following MUST be observed. The term MAXVALUE designates in the following the largest possible value for a sequence number. The sequence number S1 is said to be "greater than" the sequence num- ber S2 iff: S1-S2 < MAXVALUE/2 OR S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2 Thus when comparing two messages, it is possible - even in the pres- ence of wrap-around - to determine which message contains the most recent information. 7. Acknowledgments The authors would like to thank Joseph Macker and his team for their valuable suggestions on the advanced neighbor sensing mechanism. 8. References 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- bility in cable free radio LANs: Low level forwarding in HIPERLAN. Wireless Personal Communications, 1996 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. INRIA research report RR-3898, 2000 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June 1996 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- work Protocols, INRIA research report RR-3965, 2000 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- els. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997.