Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Expires: September 7, 2006 C. Dearlove BAE Systems Advanced Technology Centre The OLSRv2 Design Team MANET Working Group March 6, 2006 The Optimized Link-State Routing Protocol version 2 draft-ietf-manet-olsrv2-01 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 September 7, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document describes version 2 of the Optimized Link State Routing (OLSRv2) protocol for mobile ad hoc networks. The protocol is an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. Clausen, et al. Expires September 7, 2006 [Page 1] Internet-Draft OLSRv2 March 2006 The key optimization of OLSRv2 is that of multipoint relays, providing an efficient mechanism for network-wide broadcast of link- state information. A secondary optimization is, that OLSRv2 employs partial link-state information: each node maintains information of all destinations, but only a subset of links. This allows that only select nodes diffuse link-state advertisements (i.e. reduces the number of network-wide broadcasts) and that these advertisements contain only a subset of links (i.e. reduces the size of each network-wide broadcast). The partial link-state information thus obtained allows each OLSRv2 node to at all times maintain optimal (in terms of number of hops) routes to all destinations in the network. OLSRv2 imposes minimum requirements to the network by not requiring sequenced or reliable transmission of control traffic. Furthermore, the only interaction between OLSRv2 and the IP stack is routing table management. OLSRv2 is particularly suitable for large and dense networks as the technique of MPRs works well in this context. Clausen, et al. Expires September 7, 2006 [Page 2] Internet-Draft OLSRv2 March 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Applicability Statement . . . . . . . . . . . . . . . . . 7 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 2.1 Protocol Extensibility . . . . . . . . . . . . . . . . . . 11 3. Processing and Forwarding Repositories . . . . . . . . . . . . 13 3.1 Received Message Set . . . . . . . . . . . . . . . . . . . 13 3.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Processed Set . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 14 4. Packet Processing and Message Forwarding . . . . . . . . . . . 16 4.1 Actions when Receiving an OLSRv2 Packet . . . . . . . . . 16 4.2 Actions when Receiving an OLSRv2 Message . . . . . . . . . 16 4.3 Message Considered for Processing . . . . . . . . . . . . 16 4.4 Message Considered for Forwarding . . . . . . . . . . . . 18 5. Information Repositories . . . . . . . . . . . . . . . . . . . 21 5.1 Neighborhood Information Base . . . . . . . . . . . . . . 21 5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 21 5.1.2 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . 22 5.1.3 Neighborhood Address Association Set . . . . . . . . . 23 5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 23 5.1.5 MPR Selector Set . . . . . . . . . . . . . . . . . . . 23 5.1.6 Advertised Neighbor Set . . . . . . . . . . . . . . . 23 5.2 Topology Information Base . . . . . . . . . . . . . . . . 24 5.2.1 Topology Set . . . . . . . . . . . . . . . . . . . . . 24 5.2.2 Attached Network Set . . . . . . . . . . . . . . . . . 24 5.2.3 Routing Set . . . . . . . . . . . . . . . . . . . . . 25 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 26 6.1 General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 26 6.1.1 VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 26 6.1.2 INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 27 6.2 Local Interface Blocks . . . . . . . . . . . . . . . . . . 28 6.3 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 28 6.3.1 HELLO Message: Message TLVs . . . . . . . . . . . . . 29 6.3.2 HELLO Message: Address Blocks TLVs . . . . . . . . . . 29 6.4 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 30 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 31 7.1 HELLO Message: Transmission . . . . . . . . . . . . . . . 33 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 34 8.1 Populating the Link Set . . . . . . . . . . . . . . . . . 34 8.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 36 8.3 Populating the MPR Selector Set . . . . . . . . . . . . . 37 8.4 Neighborhood and 2-Hop Neighborhood Changes . . . . . . . 38 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 40 9.1 TC Message: Transmission . . . . . . . . . . . . . . . . . 41 Clausen, et al. Expires September 7, 2006 [Page 3] Internet-Draft OLSRv2 March 2006 10. TC Message Processing . . . . . . . . . . . . . . . . . . . 42 10.1 Checking Freshness & Validity of a TC message . . . . . . 42 10.2 Updating the Topology Set . . . . . . . . . . . . . . . . 43 10.3 Purging Old Entries from the Topology Set . . . . . . . . 44 10.4 Updating the Attached Networks Set . . . . . . . . . . . . 44 10.5 Purging Old Entries from the Attached Network Set . . . . 45 10.6 Processing Unfragmented TC Messages . . . . . . . . . . . 45 10.7 Processing Partially or Wholly Self-Contained Fragmented TC Messagess . . . . . . . . . . . . . . . . . 45 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . 47 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . 48 12.1 Populating the Relay Set . . . . . . . . . . . . . . . . . 48 12.2 Populating the Advertised Neighbor Set . . . . . . . . . . 48 13. Populating the Neighborhood Address Association Set . . . . 49 14. Routing Table Calculation . . . . . . . . . . . . . . . . . 50 15. Proposed Values for Constants . . . . . . . . . . . . . . . 53 15.1 Message Intervals . . . . . . . . . . . . . . . . . . . . 53 15.2 Holding Times . . . . . . . . . . . . . . . . . . . . . . 53 15.3 Willingness . . . . . . . . . . . . . . . . . . . . . . . 53 15.4 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 16. Representing Time . . . . . . . . . . . . . . . . . . . . . 55 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . 56 17.1 Multicast Addresses . . . . . . . . . . . . . . . . . . . 56 17.2 Message Types . . . . . . . . . . . . . . . . . . . . . . 56 17.3 TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 56 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 57 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 58 A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 59 B. Example Algorithms for Generating Control Traffic . . . . . . 62 B.1 Example Algorithm for Generating HELLO messages . . . . . 62 B.2 Example Algorithm for Generating TC messages . . . . . . . 63 C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 65 D. Packet and Message Layout . . . . . . . . . . . . . . . . . . 66 D.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 66 E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 73 F. Security Considerations . . . . . . . . . . . . . . . . . . . 74 F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 74 F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 74 F.3 Interaction with External Routing Domains . . . . . . . . 75 F.4 Node Identity . . . . . . . . . . . . . . . . . . . . . . 76 G. Flow and Congestion Control . . . . . . . . . . . . . . . . . 77 H. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 78 I. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 79 J. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 80 Intellectual Property and Copyright Statements . . . . . . . . 81 Clausen, et al. Expires September 7, 2006 [Page 4] Internet-Draft OLSRv2 March 2006 1. Introduction The Optimized Link State Routing Protocol version 2 (OLSRv2) is an update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626, OLSRv2 retains the same basic mechanisms and algorithms, while providing an even more flexible signaling framework and some simplification of the messages being exchanged. Also, OLSRv2 takes care to accomodate both IPv4 and IPv6 addresses in a compact fashion. OLSRv2 is developed for mobile ad hoc networks. It operates as a table driven, proactive protocol, i.e. it exchanges topology information with other nodes of the network regularly. Each node selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs). In OLSRv2, only nodes that are selected as such MPRs are then responsible for forwarding control traffic intended for diffusion into the entire network. MPRs provide an efficient mechanism for flooding control traffic by reducing the number of transmissions required. Nodes selected as MPRs also have a special responsibility when declaring link state information in the network. Indeed, the only requirement for OLSRv2 to provide shortest path routes to all destinations is that MPR nodes declare link-state information for their MPR selectors. Additional available link-state information may be utilized, e.g., for redundancy. Nodes which have been selected as multipoint relays by some neighbor node(s) 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 an MPR. Thus, as well as being used to facilitate efficient flooding, MPRs are also used for route calculation from any given node to any destination in the network. A node selects MPRs from among its one hop neighbors with "symmetric", i.e., bi-directional, linkages. 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, for link-layers employing this technique for unicast traffic). OLSRv2 is developed to work independently from other protocols. Likewise, OLSRv2 makes no assumptions about the underlying link- layer. However, OLSRv2 may use link-layer information and notifications when available and applicable. OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying Clausen, et al. Expires September 7, 2006 [Page 5] Internet-Draft OLSRv2 March 2006 from HIPERLAN (a MAC layer protocol) which is standardized by ETSI [5]. 1.1 Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [2]. Additionally, this document uses the following terminology: node - a MANET router which implements the Optimized Link State Routing protocol as specified in this document. OLSRv2 interface - A network device participating in a MANET running OLSRv2. A node may have several OLSRv2 interfaces, each interface assigned one or more IP addresses. neighbor - A node X is a neighbor of node Y if node Y can hear node X (i.e., a link exists from an OLSRv2 interface on node X to an OLSRv2 interface on node Y). A neighbor may also be called a 1-hop neighbor. 2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is a neighbor of a neighbor of node Y, but is not node Y itself. strict 2-hop neighbor - a 2-hop neighbor which is not a neighbor of the node, and is not a 2-hop neighbor only through a neighbor with willingness WILL_NEVER. multipoint relay (MPR) - A node which is selected by its 1-hop neighbor, node X, to "re-transmit" all the broadcast messages that it receives from node X, provided that the message is not a duplicate, and that the time to live field of the message is greater than one. multipoint relay selector (MPR selector, MS) - A node which has selected its 1-hop neighbor, node X, as one of its multipoint relays, will be called an MPR selector of node X. link - A link is a pair of OLSRv2 interfaces from two different nodes, where at least one interface is able to hear (i.e. receive traffic from) the other. symmetric link - A link where both interfaces are able to hear (i.e. receive messages from) the other. Clausen, et al. Expires September 7, 2006 [Page 6] Internet-Draft OLSRv2 March 2006 asymmetric link - A link which is not symmetric. symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of any node X is the set of nodes which have at least one symmetric link to node X. symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of node X is the set of nodes, excluding node X itself, which have a symmetric link to the symmetric 1-hop neighborhood of X. symmetric strict 2-hop neighborhood - The symmetric strict 2-hop neighborhood of node X is the set of nodes in its symmetric 2-hop neighborhood that are neither in its symmetric 1-hop neighborhood nor reachable only through a symmetric 1-hop neighbor of node X with willingness WILL_NEVER. 1.2 Applicability Statement OLSRv2 is a proactive routing protocol for mobile ad hoc networks (MANETs) [6], [7]. It is well suited to large and dense networks of mobile nodes, 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. OLSRv2 uses hop-by-hop routing, i.e., each node uses its local information to route packets. As OLSRv2 continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where the traffic is random and sporadic between a large subset of nodes, and where the [source, destination] pairs are changing over time: no additional control traffic need be generated in this situation since routes are maintained for all known destinations at all times. Also, since routes are maintained continously, traffic is subject to no delays due to buffering/route-discovery. This continued route maintenance may be done using periodic message exchange, as detailed in this specification, or triggered by external events if available. OLSRv2 supports nodes which have multiple interfaces which participate in the MANET. OLSRv2, additionally, supports nodes which have non-MANET interfaces which can serve as (if configured to do so) gateways towards other networks. The message exchange format, contained in previous versions of this specification, has been factored out to an independant specification [4], which is used for carrying OLSRv2 control signals. OLSRv2 is thereby able to accommodate for extensions via "external" and "internal" extensibility. External extensibility implies that a Clausen, et al. Expires September 7, 2006 [Page 7] Internet-Draft OLSRv2 March 2006 protocol extension may specify and exchange new message types which can be forwarded and delivered correctly according to [4]. Internal extensibility implies, that a protocol extension may define additional attributes to be carried embedded in the OLSRv2 control messages, detailed in this specification, while these OLSRv2 control messages with additional attributes can still be correctly understood by all OLSRv2 nodes. Clausen, et al. Expires September 7, 2006 [Page 8] Internet-Draft OLSRv2 March 2006 2. Protocol Overview and Functioning OLSRv2 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. OLSRv2 is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. The main tailoring and optimizations of OLSRv2 are: o periodic, unacknowledged transmission of all control messages; o optimized flooding for global link-state information diffusion; o partial topology maintenance -- each node will know of all destinations and a subset of links in the network. More specifically, OLSRv2 consists of the following main components: o A general and flexible signaling framework, allowing for information exchange between OLSRv2 nodes. This framework allows for both local information exchange (between neighboring nodes) and global information exchange using an optimized flooding mechanism denoted "MPR flooding". o A specification of local signaling, denoted HELLO messages. HELLO messages in OLSRv2 serve to: * discover links to adjacent OLSR nodes; * perform bidirectionality check on the discovered links; * advertise neighbors and hence discover 2-hop neighbors; * signal MPR selection. HELLO messages are emitted periodically, thereby allowing nodes to continuously track changes in their local neighborhoods. o A specification of global signaling, denoted TC messages. TC messages in OLSRv2 serve to: * inject link-state information into the entire network. * inject addresses of hosts and networks for which they may serve as a gateway into the entire network. * allow nodes with multiple interface addresses to ensure that nodes within two hops can associate these addresses with a Clausen, et al. Expires September 7, 2006 [Page 9] Internet-Draft OLSRv2 March 2006 single node for efficient MPR Set determination. TC messages are emitted periodically, thereby allowing nodes to continuously track global changes in the network. Thus, through periodic exchange of HELLO messages, a node is able to acquire and maintain information about its immediate neighborhood. This includes information about immediate neighbors, as well as nodes which are two hops away. By HELLO messages being exchanged periodically, a node learns about changes in the neighborhood (new nodes emerging, old nodes disappearing) without requiring explicit mechanisms for doing so. Based on the local topology information, acquired through the periodic exchange of HELLO messages, an OLSRv2 node is able to make provisions for ensuring optimized flooding, denoted "MPR flooding", as well as injection of link-state information into the network. This is done through the notion of Multipoint Relays. The idea of multipoint relays is to minimize the overhead of flooding messages in the network by reducing redundant retransmissions in the same region. Each node in the network selects a set of nodes in its symmetric 1-hop 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, receive and process broadcast messages but do not retransmit broadcast messages received from node N. The MPR Set of a node is selected such that it covers (in terms of radio range) all symmetric strict 2-hop nodes. The MPR Set of N, denoted as MPR(N), is then an arbitrary subset of the symmetric 1-hop neighborhood of N which satisfies the following condition: every node in the symmetric strict 2-hop neighborhood of N MUST have a symmetric link towards MPR(N). The smaller a MPR Set, the less control traffic overhead results from the routing protocol. [7] gives an analysis and example of MPR selection algorithms. Notice, that as long as the condition above is satisfied, any algorithm selecting MPR Sets is acceptable in terms of implementation interoperability. Each node maintains information about the set of 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. Each node also maintains a Relay Set, which is the set of nodes for which a node is to relay broadcast traffic. The Relay Set is derived from the MPR Selector Set in that the Relay Set MUST contain all the nodes in the MPR Selector set and MAY contain additional nodes. A broadcast message, intended to be diffused in the whole network, Clausen, et al. Expires September 7, 2006 [Page 10] Internet-Draft OLSRv2 March 2006 coming from any of the nodes in the Relay Set of node N is assumed to be retransmitted by node N, if N has not received it yet. This set can change over time (e.g., when a node selects another MPR Set) and is indicated by the selector nodes in their HELLO messages. Using the MPR flooding mechanism, link-state information can be injected into the network. For this purpose, a node maintains an Advertised Neighbor Set which MUST contain all the nodes in the MPR selector set and MAY contain additional nodes. If the Advertised Neighbor Set of a node is non-empty, TC messages, containing the links between the node and the nodes in the Advertised Neighbor Set, are not generated, unless needed for gateway reporting or multiple interface address association (if the latter case only, with minimal scope). OLSRv2 is designed to work in a completely distributed manner and does 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 a reasonable loss of some such messages. Such losses occur frequently in radio networks due to collisions or other transmission problems. Also, OLSRv2 does not require sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message. Thus the recipient of a control message can, if required, easily identify which information is more recent - even if messages have been re-ordered while in transmission. Furthermore, OLSRv2 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. OLSRv2 does not require any changes to the format of IP packets. Thus any existing IP stack can be used as is: OLSRv2 only interacts with routing table management. OLSR sends its own control messages using UDP. 2.1 Protocol Extensibility This specification defines and uses two OLSRv2 message types, HELLO and TC. As for OLSRv1 [1] extensions to OLSRv2 may define new message types to carry additional information. This may be considered as "external" extensibility. New message types are divided into two ranges, those which may be added by standards actions (with types up to 127) and those made available for private/ local use (with types 128 to 255). All new messages must be syntactically OLSRv2 messages, as defined in Clausen, et al. Expires September 7, 2006 [Page 11] Internet-Draft OLSRv2 March 2006 [4]. (Some additional constraints to that specification are added for OLSRv2 packets and messages, requiring full packet and message headers.) Note that if it is required to include one or more blocks of unstructured data in such a message (possibly as its only content) this may be achieved by including each block as a single message TLV block, with an appropriately defined message TLV. (Like message types, TLV types are divided into those up to 127 which may be added by standards action, and those from 128 to 255 available for private/ local use.) A network may contain nodes both aware of, and unaware of, any new message types. The originator of a message can control whether a message flooded through the network is forwarded by nodes which are unaware of the message type, thus reaching all nodes in the network, or is only flooded by nodes which recognise the message type. OLSRv2 also supports an alternative, and more powerful, extension mechanism which was not supported by OLSRv1, that of adding new information to an already defined message type, whilst still leaving the predefined information unchanged and usable, including by a node which does not recognise the new information. This may be considered to be "internal" extensibility of a message. The mechanism for this extensibility is the use of TLV (type-length- value) structures in the message format defined in [4] to carry information associated with either the message as a whole, or with one or more addresses carried in the message. The messages defined in this specification carry two types of addresses, those of the originating node's own interfaces participating in OLSRv2, and those of neighbouring nodes or networks to which it has a route. (New message types may define other relationships to addresses which they carry.) All information associated with these addresses, or the message as a whole, in messages defined in this specification is in TLV format; additional TLVs may be defined and added to these messages. Those nodes which do not recognise newly defined TLV types ignore the added TLVs. (This is facilitated by that the TLVs defined in this specification, or in [4], have the lowest type numbers and that TLVs must be included in type order, as specified in [4].) It is important that newly defined TLV types permit this behaviour. Clausen, et al. Expires September 7, 2006 [Page 12] Internet-Draft OLSRv2 March 2006 3. Processing and Forwarding Repositories The following data-structures are employed in order to ensure that a message is processed at most once and is forwarded at most once per interface of a node, and that fragmented content is treated correctly. 3.1 Received Message Set Each node maintains, for each OLSRv2 interface it possesses, a set of signatures of messages, which have been received over that interface, in the form of "Received Tuples": (RX_type, RX_addr, RX_seq_number, RX_time) where: RX_type is the received message type, or zero if the received message sequence number is not type-specific. RX_addr is the originator address of the received message; RX_seq_number is the message sequence number of the received message; RX_time specifies the time at which this record expires and *MUST* be removed. In a node, this is denoted the "Received Message Set" for that interface. 3.2 Fragment Set Each node stores messages containing fragmented content until all fragments are received and the message processing can be completed, in the form of "Fragment Tuples": (FG_message, FG_time) where: FG_message is the message containing fragmented content; FG_time specifies the time at which this record expires and MUST be removed. In a node, this is denoted the "Fragment Set". Clausen, et al. Expires September 7, 2006 [Page 13] Internet-Draft OLSRv2 March 2006 3.3 Processed Set Each node maintains a set of signatures of messages which have been processed by the node, in the form of "Processed Tuples": (P_type, P_addr, P_seq_number, P_time) where: P_type is the processed message type, or zero if the processed message sequence number is not type-specific. P_addr is the originator address of the processed message; P_seq_number is the message sequence number of the processed message; P_time specifies the time at which this record expires and *MUST* be removed. In a node, this is denoted the "Processed Set". 3.4 Forwarded Set Each node maintains a set of signatures of messages which have been retransmitted/forwarded by the node, in the form of "Forwarded Tuples": (FW_type, FW_addr, FW_seq_number, FW_time) where: FW_type is the forwarded message type, or zero if the forwarded message sequence number is not type-specific. FW_addr is the originator address of the forwarded message; FW_seq_number is the message sequence number of the forwarded message; FW_time specifies the time at which this record expires and *MUST* be removed. In a node, this is denoted the "Forwarded Set". 3.5 Relay Set Each node maintains a set of neighbor interface addresses for which it is to relay flooded messages, in the form of "Relay Tuples": Clausen, et al. Expires September 7, 2006 [Page 14] Internet-Draft OLSRv2 March 2006 (RY_if_addr) where: RY_if_addr is the address of a neighbor interface for which the node SHOULD relay flooded messages. In a node, this is denoted the "Relay Set". Clausen, et al. Expires September 7, 2006 [Page 15] Internet-Draft OLSRv2 March 2006 4. Packet Processing and Message Forwarding Upon receiving a basic packet, a node examines each of the message headers. If the message type is known to the node, the message is processed locally according to the specifications for that message type. The message is also independently evaluated for forwarding. 4.1 Actions when Receiving an OLSRv2 Packet Upon receiving a packet, a node MUST perform the following task: 1. If the packet contains no messages (i.e. the packet length is less than or equal to the size of the packet header) or if the packet cannot be parsed into messages, the packet MUST be silently discarded. 2. Otherwise, each message in the packet is treated according to Section 4.2. 4.2 Actions when Receiving an OLSRv2 Message A node MUST perform the following tasks for each received OLSRv2 message: 1. If the received OLSRv2 message header cannot be correctly parsed according to the specification in [4], or if the originator address of the message is an interface address of the receiving node then the message MUST be silently discarded; 2. Otherwise: 1. If the message is of a known type then the message is considered for processing according to Section 4.3; 2. If for the received message TTL > 0, and if either the message is of a known type, or bit 3 of the message semantics octet in the message header is clear, as indicated in [4], then the message is considered for forwarding according to Section 4.4. 4.3 Message Considered for Processing If a message is considered for processing, the following tasks MUST be performed: Clausen, et al. Expires September 7, 2006 [Page 16] Internet-Draft OLSRv2 March 2006 1. If an entry exists in the Processed Set where: * P_type == the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear, AND; * P_addr == the originator address of the message, AND; * P_seq_number == the sequence number of the message. then the message MUST NOT be processed. 2. Otherwise: 1. Create an entry in the Processed Set with: + P_type = the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear; + P_addr = originator address of the message; + P_seq_number = sequence number of the message; + P_time = current time + P_HOLD_TIME. 2. If the message does not contain a message TLV of type Fragment (or if it does and the indicated number of fragments is one) then process the message fully according to its type. 3. Otherwise: 1. If the message is "wholly or partially self-contained" as indicated by its Fragment TLV then process the current message as far as possible according to its type; 2. If the Fragment Set includes any messages with the same originator address and content sequence number as the current message, and either the same fragment number or a different number of fragments, then remove these messages are from the Fragment Set; 3. If the Fragment Set includes messages containing all the remaining fragments of the same overall message as the current message (i.e. if the number of messages in the Fragment Set with the same originator address and content sequence number as the current message is equal to the current message's number of fragments, less one) then all of these messages are removed from the Fragment Set and processed according to their type (taking account of any Clausen, et al. Expires September 7, 2006 [Page 17] Internet-Draft OLSRv2 March 2006 previous processing if any or all were wholly or partially self-contained); 4. Otherwise, the current message is added to the Fragment Set with a FG_time of FG_HOLD_TIME (possibly replacing an identical and previous received instance of the same fragment of the same content). 4.4 Message Considered for Forwarding If a message is considered for forwarding then if it is either of a message type defined in this document, or of an unknown message type it MUST use the following algorithm. A message type not defined in this document may specify the use of this, or another algorithm. (Such an other algorithm MAY use the Received Set for the receiving interface, it SHOULD use the Forwarded Set similarly to the following algorithm.) If a message is considered for forwarding according to this algorithm, the following tasks MUST be performed: 1. If there is no symmetric link in the Link Set between the receiving interface and the sending interface (as indicated by the source interface of the IP datagram containing the message) then the message MUST be silently discarded. 2. Otherwise: 1. If an entry exists in the Received Set for the receiving interface, where: + RX_type == the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear, AND; + RX_addr == the originator address of the received message, AND; + RX_seq_number == the sequence number of the received message. then the message MUST be silently discarded. 2. Otherwise: 1. Create an entry in the Received Set for the receiving interface with: Clausen, et al. Expires September 7, 2006 [Page 18] Internet-Draft OLSRv2 March 2006 - RX_type = the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear; - RX_addr = originator address of the message; - RX_seq_number = sequence number of the message; - RX_time = current time + RX_HOLD_TIME. 2. If an entry exists in the Forwarded Set where: - FW_type == the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear; - FW_addr == the originator address of the received message, AND; - FW_seq_number == the sequence number of the received message. then the message MUST be silently discarded. 3. Otherwise if an entry exists in the Relay Set, where RY_if_addr == source address of the message (as indicated by the source interface of the IP datagram containing the message): 1. Create an entry in the Forwarded Set with: o FW_type = the message type, or 0 if bit 2 of the message semantics octet (in the message header) is clear; o FW_addr = originator address of the message; o FW_seq_number = sequence number of the message; o FW_time = current time + FW_HOLD_TIME. 2. The message header is modified as follows: o Decrement the message TTL by 1; o Increment the message hop count by 1; Clausen, et al. Expires September 7, 2006 [Page 19] Internet-Draft OLSRv2 March 2006 3. Transmit the message on all OLSRv2 interfaces of the node. Messages are retransmitted in the format specified by [4] with the All-OLSRv2-Multicast address (see Section 17.1) as destination IP address. Clausen, et al. Expires September 7, 2006 [Page 20] Internet-Draft OLSRv2 March 2006 5. Information Repositories The purpose of OLSRv2 is to determine the Routing Set, which may be used to update IP's Routing Table, providing "next hop" routing information for IP datagrams. In order to accomplish this, OLSRv2 maintains a number of protocol sets, the information repository of the protocol. These sets are updated, directly or indirectly, by the exchange of messages between nodes in the network. In turn the contents of these messages are largely determined by the contents of a part of the information repositories, the Neighbourhood Information Base, which contains information about the 1- and 2- hop neighbourhoods of the node. The remaining part of the information repository, the Topology Information Base (including the Routing Set) contains information about the network which is not constrained to the node's neighbourhood. The Topology Information Base is updated by the OLSRv2 messages defined in this document, it is not used to define their contents. The process of information exchange which leads to the population of the Neighbourhood Information Base and the Topology Information Base is started using only the node's own OLSRv2 interface addresses and host and network associated addresses. These are not affected by the exchange of the OLSRv2 messages defined in this document. 5.1 Neighborhood Information Base The neighborhood information base stores information about links between local interfaces and interfaces on adjacent nodes. 5.1.1 Link Set A node records a set of "Link Tuples": (L_local_iface_addr, L_neighbor_iface_addr, L_SYM_time, L_ASYM_time, L_willingness, L_time). where: L_local_iface_addr is the interface address of the local node; L_neighbor_iface_addr is the interface address of the neighbor node; L_SYM_time is the time until which the link is considered symmetric; L_ASYM_time is the time until which the neighbor interface is considered heard; Clausen, et al. Expires September 7, 2006 [Page 21] Internet-Draft OLSRv2 March 2006 L_willingness is the nodes willingness to be selected as MPR; L_time specifies when this record expires and *MUST* be removed. +-------------+-------------+--------------+ | L_SYM_time | L_ASYM_time | L_STATUS | +-------------+-------------+--------------+ | Expired | Expired | LOST | | | | | | Not Expired | Expired | SYMMETRIC | | | | | | Not Expired | Not Expired | SYMMETRIC | | | | | | Expired | Not Expired | ASYMMETRIC | +-------------+-------------+--------------+ Table 1 The status of the link, denoted L_STATUS, can be derived based on the fields L_SYM_time and L_ASYM_time as defined in Table 1. In a node, the set of Link Tuples is denoted the "Link Set". 5.1.2 2-Hop Neighbor Set A node records a set of "2-Hop Neighbor Tuples" (N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, N2_time) describing symmetric links between its neighbors and the symmetric 2-hop neighborhood. N2_local_iface_addr is the address of the local interface over which the information was received; N2_neighbor_iface_addr is the interface address of a neighbor; N2_2hop_iface_addr is the interface address of a 2-hop neighbor with a symmetric link to the node with interface address N_neighbor_iface_addr; N2_time specifies the time at which the tuple expires and *MUST* be removed. In a node, the set of 2-Hop Neighbor Tuples is denoted the "2-Hop Neighbor Set". Clausen, et al. Expires September 7, 2006 [Page 22] Internet-Draft OLSRv2 March 2006 5.1.3 Neighborhood Address Association Set A node maintains, for each 1-hop and 2-hop neighbor with multiple addresses participating in the OLSRv2 network, a "Neighborhood Address Association Tuple", representing that "these addresses belong to the same node". (NA_neighbor_addr_list, NA_time) NA_neighbor_iface_addr_list is the list of interface addresses of the 1-hop or 2-hop neighbor node; NA_time specifies the time at which the tuple expires and *MUST* be removed. In a node, the set of Neighborhood Address Association Tuples is denoted the "Neighborhood Address Association Set". 5.1.4 MPR Set A node maintains a set of neighbors which are selected as MPRs. Their interface addresses are listed in the MPR Set. 5.1.5 MPR Selector Set A node maintains, for each interface of an 1-hop neighbor which has selected it as MPR, an "MPR Selector Tuple", representing the an interface of the neighbor node which have selected it as an MPR. (MS_neighbor_if_addr, MS_time) MS_neighbor_if_addr specifies the interface address of a 1-hop neighbor, which has selected the node as MPR; MS_time specifies the time at which the tuple expires and *MUST* be removed. Notice that if a MPR selector node has multiple interface addresses, the MPR Selector Set will contain one tuple for each interface address of the MPR selector. 5.1.6 Advertised Neighbor Set A node maintains a set of neighbor interface addresses, which are to be advertised through TC messages: (A_neighbor_iface_addr) Clausen, et al. Expires September 7, 2006 [Page 23] Internet-Draft OLSRv2 March 2006 For this set, an Advertised Neighbor Set Sequence Number (ASSN) is maintained. Each time the Advertised Neighbor Set is updated, the ASSN MUST be incremented. 5.2 Topology Information Base The Topology Information Base stores topological information describing the network beyond the nodes neighborhood (i.e. beyond the Neighborhood Information Base of the node). 5.2.1 Topology Set Each node in the network maintains topology information about the network. For each destination in the network, at least one "Topology Tuple" (T_dest_iface_addr, T_last_iface_addr, T_seq, T_time) is recorded. T_dest_iface_addr is the interface address of a node, which may be reached in one hop from the node with the interface address T_last_iface_addr; T_last_iface_addr is, conversely, the last hop towards T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of T_dest_iface_addr; 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". 5.2.2 Attached Network Set Each node in the network maintains information about attached networks. For each attached network, at least one "Attached Network Tuple" (AN_net_addr, AN_prefix_lenght, AN_gw_addr, AN_seq_no, AN_time) is recorded. Clausen, et al. Expires September 7, 2006 [Page 24] Internet-Draft OLSRv2 March 2006 AN_net_addr is the network address (prefix) of a network, which may be reached via the node with the OLSRv2 interface address AN_gw_addr; AN_prefix_length is the length of the prefix of the network address AN_net_addr; AN_gw_addr is the address of an OLSRv2 interface of a node which can act as gateway to the network identified by the AD_net_addr/ AD_prefix_length; AN_seq_no is a sequence number, and; AN_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". 5.2.3 Routing Set A node records a set of "Routing Tuples": (R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr) describing the next hop and distance of the path to each destination in the network for which a route is known. R_dest_iface_addr is the interface address of the destination node; R_next_iface_addr is the interface address of the "next hop" on the path towards R_dest_iface_addr; R_dist is the number of hops on the path to R_dest_iface_addr; R_iface_addr is the address of the local interface over which a packet MUST be sent to reach R_next_iface_addr. In a node, the set of Routing Tuples is denoted the "Routing Set". Clausen, et al. Expires September 7, 2006 [Page 25] Internet-Draft OLSRv2 March 2006 6. OLSRv2 Control Message Structures Nodes using OLSRv2 exchange information through messages. One or more messages sent by a node at the same time are combined into a packet. These messages may have originated at the sending node, or have originated at another node and forwarded by the sending node. Messages with different originators may be combined in the same packet. The packet and message format used by OLSRv2 is defined in [4]. However this specification contains some options which are not used by OLSRv2. In particular (using the syntactical elements defined in the packet format specification): o All OLSRv2 packets include a . o All OLSRv2 messages, not limited to those defined in this document, include a full and hence have bits 0 and 1 of cleared. o All OLSRv2 message defined in this document have all remaining bits of cleared. Other options defined in [4] may be freely used, in particular any values of consistent with its specification. An implementation of OLSRv2 MAY take full advantage of the features of the message specification in [4] allowing decisions relating to whether a message should be forwarded and/or processed to be taken parsing only the message header (plus, if a message is to be processed but may be fragmented, only the first octets of the message body). OLSRv2 messages are sent using UDP, see Appendix C. The remainder of this section defines, within the framework of [4], message types and TLVs specific to OLSRv2. 6.1 General OLSRv2 Message TLVs This document specifies two message TLVs, which can be applied to any OLSRv2 control message, VALIDITY_TIME and INTERVAL_TIME, detailed in this section. 6.1.1 VALIDITY_TIME TLV All OLSRv2 messages specified in this specification MUST include a VALIDITY_TIME TLV, specifying for how long a node may, upon receiving a message, consider the message content to be valid. The validity Clausen, et al. Expires September 7, 2006 [Page 26] Internet-Draft OLSRv2 March 2006 time of a message MAY be specified to depend on the distance from the originator (i.e. the field in the message header as defined in [4]). Thus, the VALIDITY_TIME TLV contains a sequence of pairs (time, hop-limit) in increasing hop-limit order, followed by a default value. Thus, an instance of a VALIDITY_TIME TLV could have the following value: ... .... Which would mean that the message, carrying this VALIDITY_TIME TLV, would have the following validity times: o in the interval from 0 (exclusive) to (inclusive) hops away from the originator; o in the interval from (exclusive) to (inclusive) hops away from the originator; and o in the interval from (exclusive) to 255> (inclusive) hops away from the originator. The VALIDITY_TIME message TLV specification is given in Table 2. VALIDITY_TIME message TLV specification overview +----------------+--------+-------------------+---------------------+ | Name | Type | Length | Value | +----------------+--------+-------------------+---------------------+ | VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {