Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 3626

Optimized Link State Routing Protocol (OLSR)

Pages: 75
Experimental
Errata
Part 1 of 3 – Pages 1 to 21
None   None   Next

Top   ToC   RFC3626 - Page 1
Network Working Group                                    T. Clausen, Ed.
Request for Comments: 3626                               P. Jacquet, Ed.
Category: Experimental                           Project Hipercom, INRIA
                                                            October 2003


              Optimized Link State Routing Protocol (OLSR)

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

Abstract

This document describes the Optimized Link State Routing (OLSR) 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. The key concept used in the protocol is that of multipoint relays (MPRs). MPRs are selected nodes which forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a classical flooding mechanism, where every node retransmits each message when it receives the first copy of the message. In OLSR, link state information is generated only by nodes elected as MPRs. Thus, a second optimization is achieved by minimizing the number of control messages flooded in the network. As a third optimization, an MPR node may chose to report only links between itself and its MPR selectors. Hence, as contrary to the classic link state algorithm, partial link state information is distributed in the network. This information is then used for route calculation. 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.
Top   ToC   RFC3626 - Page 2

Table of Contents

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. OLSR Terminology. . . . . . . . . . . . . . . . . . . . 5 1.2. Applicability. . . . . . . . . . . . . . . . . . . . . . 7 1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . 8 1.4. Multipoint Relays . . . . . . . . . . . . . . . . . . . 9 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . 10 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . 12 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . 13 3.1. Protocol and Port Number. . . . . . . . . . . . . . . . 13 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . 13 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 14 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . 14 3.3.2. Message Header . . . . . . . . . . . . . . . . . 15 3.4. Packet Processing and Message Flooding . . . . . . . . . 16 3.4.1. Default Forwarding Algorithm. . . . . . . . . . . 18 3.4.2. Considerations on Processing and Forwarding . . . 20 3.5. Message Emission and Jitter. . . . . . . . . . . . . . . 21 4. Information Repositories . . . . . . . . . . . . . . . . . . 22 4.1. Multiple Interface Association Information Base . . . . 22 4.2. Link sensing: Local Link Information Base. . . . . . . . 22 4.2.1. Link Set. . . . . . . . . . . . . . . . . . . . . 22 4.3. Neighbor Detection: Neighborhood Information Base. . . . 23 4.3.1. Neighbor Set. . . . . . . . . . . . . . . . . . . 23 4.3.2. 2-hop Neighbor Set. . . . . . . . . . . . . . . . 23 4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . 23 4.3.4. MPR Selector Set. . . . . . . . . . . . . . . . . 23 4.4. Topology Information Base . . . . . . . . . . . . . . . 24 5. Main Addresses and Multiple Interfaces . . . . . . . . . . . 24 5.1. MID Message Format . . . . . . . . . . . . . . . . . . . 25 5.2. MID Message Generation . . . . . . . . . . . . . . . . . 25 5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . 26 5.4. MID Message Processing . . . . . . . . . . . . . . . . . 26 5.5. Resolving a Main Address from an Interface Address . . . 27 6. HELLO Message Format and Generation . . . . . . . . . . . . . 27 6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 27 6.1.1. Link Code as Link Type and Neighbor Type. . . . . 29 6.2. HELLO Message Generation . . . . . . . . . . . . . . . . 30 6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . 33 6.4. HELLO Message Processing . . . . . . . . . . . . . . . . 33 7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . 33 7.1. Populating the Link Set . . . . . . . . . . . . . . . . 33 7.1.1. HELLO Message Processing . . . . . . . . . . . . 34 8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . 35 8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . 35 8.1.1. HELLO Message Processing . . . . . . . . . . . . 37
Top   ToC   RFC3626 - Page 3
       8.2. Populating the 2-hop Neighbor Set. . . . . . . . . . . .  37
            8.2.1. HELLO Message Processing. . . . . . . . . . . . .  37
       8.3. Populating the MPR set . . . . . . . . . . . . . . . . .  38
            8.3.1. MPR Computation . . . . . . . . . . . . . . . . .  39
       8.4. Populating the MPR Selector Set. . . . . . . . . . . . .  41
            8.4.1. HELLO Message Processing. . . . . . . . . . . . .  41
       8.5. Neighborhood and 2-hop Neighborhood Changes. . . . . . .  42
   9.  Topology Discovery  . . . . . . . . . . . . . . . . . . . . .  43
       9.1. TC Message Format. . . . . . . . . . . . . . . . . . . .  43
       9.2. Advertised Neighbor Set. . . . . . . . . . . . . . . . .  44
       9.3. TC Message Generation. . . . . . . . . . . . . . . . . .  45
       9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . .  45
       9.5. TC Message Processing. . . . . . . . . . . . . . . . . .  45
   10. Routing Table Calculation . . . . . . . . . . . . . . . . . .  47
   11. Node Configuration. . . . . . . . . . . . . . . . . . . . . .  50
       11.1. Address Assignment. . . . . . . . . . . . . . . . . . .  50
       11.2. Routing Configuration . . . . . . . . . . . . . . . . .  51
       11.3. Data Packet Forwarding. . . . . . . . . . . . . . . . .  51
   12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . .  51
       12.1. HNA Message Format. . . . . . . . . . . . . . . . . . .  52
       12.2. Host and Network Association Information Base . . . . .  52
       12.3. HNA Message Generation. . . . . . . . . . . . . . . . .  53
       12.4. HNA Message Forwarding. . . . . . . . . . . . . . . . .  53
       12.5. HNA Message Processing. . . . . . . . . . . . . . . . .  53
       12.6. Routing Table Calculation . . . . . . . . . . . . . . .  54
       12.7. Interoperability Considerations . . . . . . . . . . . .  55
   13. Link Layer Notification . . . . . . . . . . . . . . . . . . .  55
       13.1. Interoperability Considerations . . . . . . . . . . . .  56
   14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . .  56
       14.1. Local Link Set  . . . . . . . . . . . . . . . . . . . .  56
       14.2. Hello Message Generation  . . . . . . . . . . . . . . .  57
       14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . .  57
       14.4. Interoperability Considerations . . . . . . . . . . . .  59
   15. Redundant Topology Information. . . . . . . . . . . . . . . .  59
       15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . .  60
       15.2. Interoperability Considerations . . . . . . . . . . . .  60
   16. MPR Redundancy. . . . . . . . . . . . . . . . . . . . . . . .  60
       16.1. MPR_COVERAGE Parameter. . . . . . . . . . . . . . . . .  61
       16.2. MPR Computation . . . . . . . . . . . . . . . . . . . .  61
       16.3. Interoperability Considerations . . . . . . . . . . . .  62
   17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . .  63
   18. Proposed Values for Constants . . . . . . . . . . . . . . . .  63
       18.1. Setting emission interval and holding times . . . . . .  63
       18.2. Emission Interval . . . . . . . . . . . . . . . . . . .  64
       18.3. Holding time  . . . . . . . . . . . . . . . . . . . . .  64
       18.4. Message Types . . . . . . . . . . . . . . . . . . . . .  65
       18.5. Link Types. . . . . . . . . . . . . . . . . . . . . . .  65
       18.6. Neighbor Types  . . . . . . . . . . . . . . . . . . . .  65
Top   ToC   RFC3626 - Page 4
       18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . .  66
       18.8. Willingness . . . . . . . . . . . . . . . . . . . . . .  66
       18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . .  67
   19. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . . .  67
   20. Security Considerations . . . . . . . . . . . . . . . . . . .  67
       20.1. Confidentiality . . . . . . . . . . . . . . . . . . . .  67
       20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . .  68
       20.3. Interaction with External Routing Domains . . . . . . .  69
       20.4. Node Identity . . . . . . . . . . . . . . . . . . . . .  70
   21. Flow and congestion control . . . . . . . . . . . . . . . . .  70
   22. IANA Considerations . . . . . . . . . . . . . . . . . . . . .  70
   23. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .  71
   24. Contributors. . . . . . . . . . . . . . . . . . . . . . . . .  71
   25. References. . . . . . . . . . . . . . . . . . . . . . . . . .  73
   26. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . .  74
   27. Full Copyright Statement. . . . . . . . . . . . . . . . . . .  75

1. Introduction

The Optimized Link State Routing Protocol (OLSR) is developed for mobile ad hoc networks. It operates as a table driven, proactive protocol, i.e., exchanges topology information with other nodes of the network regularly. Each node selects a set of its neighbor nodes as "multipoint relays" (MPR). In OLSR, only nodes, selected as such MPRs, are 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 OLSR 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. In route calculation, the MPRs are used to form the route from a given node to any destination in the network. Furthermore, the protocol uses the MPRs to facilitate efficient flooding of control messages 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
Top   ToC   RFC3626 - Page 5
   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).

   OLSR is developed to work independently from other protocols.
   Likewise, 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. 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]. Additionally, this document uses the following terminology: node A MANET router which implements the Optimized Link State Routing protocol as specified in this document. OLSR interface A network device participating in a MANET running OLSR. A node may have several OLSR interfaces, each interface assigned an unique IP address. non OLSR interface A network device, not participating in a MANET running OLSR. A node may have several non OLSR interfaces (wireless and/or wired). Routing information from these interfaces MAY be injected into the OLSR routing domain. single OLSR interface node A node which has a single OLSR interface, participating in an OLSR routing domain. multiple OLSR interface node A node which has multiple OLSR interfaces, participating in an OLSR routing domain.
Top   ToC   RFC3626 - Page 6
      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 the OLSR interfaces of
         the node.

         A single OLSR interface node MUST use the address of its only
         OLSR interface as the main address.

         A multiple OLSR interface node MUST choose one of its OLSR
         interface addresses as its "main address" (equivalent of
         "router ID" or "node identifier").  It is of no importance
         which address is chosen, however a node SHOULD always use the
         same address as its main address.

      neighbor node

         A node X is a neighbor node of node Y if node Y can hear node X
         (i.e., a link exists between an OLSR interface on node X and an
         OLSR interface on Y).

      2-hop neighbor

         A node heard by a neighbor.

      strict 2-hop neighbor

         a 2-hop neighbor which is not the node itself or a neighbor of
         the node, and in addition is a neighbor of a neighbor, with
         willingness different from WILL_NEVER, of the node.

      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
         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 its
         multipoint relay, will be called a multipoint relay selector of
         node X.
Top   ToC   RFC3626 - Page 7
      link

         A link is a pair of OLSR interfaces (from two different nodes)
         susceptible 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.

      symmetric link

         A verified bi-directional link between two OLSR interfaces.

      asymmetric link

         A link between two OLSR interfaces, verified in only one
         direction.

      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 X.

      symmetric 2-hop neighborhood

         The symmetric 2-hop neighborhood of X is the set of nodes,
         excluding 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 X is the set of
         nodes, excluding X itself and its neighbors, which have a
         symmetric link to some symmetric 1-hop neighbor, with
         willingness different of WILL_NEVER, of X.

1.2. Applicability

OLSR is a proactive routing protocol for mobile ad-hoc networks (MANETs) [1], [2]. 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 a larger set of nodes rather than being almost exclusively between a small specific set of nodes. As a proactive
Top   ToC   RFC3626 - Page 8
   protocol, OLSR is also suitable for scenarios where the communicating
   pairs change over time: no additional control traffic is generated in
   this situation since routes are maintained for all known destinations
   at all times.

1.3. 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 classical link state protocol, tailored for mobile ad hoc networks. OLSR minimizes the overhead from flooding of control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only partial link state to be flooded in order to provide shortest path routes. The minimal set of link state information required is, that all nodes, selected as MPRs, MUST declare the links to their MPR selectors. Additional topological information, if present, MAY be utilized e.g., for redundancy purposes. 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 to all destinations 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 changing 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 optimization can be achieved as compared to the classic link state algorithm. OLSR 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, OLSR 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.
Top   ToC   RFC3626 - Page 9
   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 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.4. 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. Each node selects its MPR set from among its 1-hop symmetric neighbors. This set 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. [2] gives an analysis and example of MPR selection algorithms. 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. A broadcast message, intended to be diffused in the whole network, coming from any of the MPR selectors of node N is assumed to be retransmitted by node N, if N has not received it yet. 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 messages.

2. Protocol Functioning

This section outlines the overall protocol functioning. OLSR is modularized into a "core" of functionality, which is always required for the protocol to operate, and a set of auxiliary functions.
Top   ToC   RFC3626 - Page 10
   The core specifies, in its own right, a protocol able to provide
   routing in a stand-alone MANET.

   Each auxiliary function provides additional functionality, which may
   be applicable in specific scenarios, e.g., in case a node is
   providing connectivity between the MANET and another routing domain.

   All auxiliary functions are compatible, to the extent where any
   (sub)set of auxiliary functions may be implemented with the core.
   Furthermore, the protocol allows heterogeneous nodes, i.e., nodes
   which implement different subsets of the auxiliary functions, to
   coexist in the network.

   The purpose of dividing the functioning of OLSR into a core
   functionality and a set of auxiliary functions is to provide a simple
   and easy-to-comprehend protocol, and to provide a way of only adding
   complexity where specific additional functionality is required.

2.1. Core Functioning

The core functionality of OLSR specifies the behavior of a node, equipped with OLSR interfaces participating in the MANET and running OLSR as routing protocol. This includes a universal specification of OLSR protocol messages and their transmission through the network, as well as link sensing, topology diffusion and route calculation. Specifically, the core is made up from the following components: Packet Format and Forwarding A universal specification of the packet format and an optimized flooding mechanism serves as the transport mechanism for all OLSR control traffic. Link Sensing Link Sensing is accomplished through periodic emission of HELLO messages over the interfaces through which connectivity is checked. A separate HELLO message is generated for each interface and emitted in correspondence with the provisions in section 7. Resulting from Link Sensing is a local link set, describing links between "local interfaces" and "remote interfaces" - i.e., interfaces on neighbor nodes.
Top   ToC   RFC3626 - Page 11
         If sufficient information is provided by the link-layer, this
         may be utilized to populate the local link set instead of HELLO
         message exchange.

      Neighbor detection

         Given a network with only single interface nodes, a node may
         deduct the neighbor set directly from the information exchanged
         as part of link sensing: the "main address" of a single
         interface node is, by definition, the address of the only
         interface on that node.

         In a network with multiple interface nodes, additional
         information is required in order to map interface addresses to
         main addresses (and, thereby, to nodes).  This additional
         information is acquired through multiple interface declaration
         (MID) messages, described in section 5.

      MPR Selection and MPR Signaling

         The objective of MPR selection is for a node to select a subset
         of its neighbors such that a broadcast message, retransmitted
         by these selected neighbors, will be received by all nodes 2
         hops away.  The MPR set of a node is computed such that it, for
         each interface, satisfies this condition.  The information
         required to perform this calculation is acquired through the
         periodic exchange of HELLO messages, as described in section 6.
         MPR selection procedures are detailed in section 8.3.

         MPR signaling is provided in correspondence with the provisions
         in the section 6.

      Topology Control Message Diffusion

         Topology Control messages are diffused with the purpose of
         providing each node in the network with sufficient link-state
         information to allow route calculation.  Topology Control
         messages are diffused in correspondence with the provisions in
         section 9.

      Route Calculation

         Given the link state information acquired through periodic
         message exchange, as well as the interface configuration of the
         nodes, the routing table for each node can be computed.  This
         is detailed in section 10.
Top   ToC   RFC3626 - Page 12
   The key notion for these mechanisms is the MPR relationship.

   The following table specifies the component of the core functionality
   of OLSR, as well as their relations to this document.

          Feature                      |  Section
         ------------------------------+--------------
          Packet format and forwarding |     3
          Information repositories     |     4
          Main addr and multiple if.   |     5
          Hello messages               |     6
          Link sensing                 |     7
          Neighbor detection           |     8
          Topology discovery           |     9
          Routing table computation    |    10
          Node configuration           |    11

2.2. Auxiliary Functioning

In addition to the core functioning of OLSR, there are situations where additional functionality is desired. This includes situations where a node has multiple interfaces, some of which participate in another routing domain, where the programming interface to the networking hardware provides additional information in form of link layer notifications and where it is desired to provide redundant topological information to the network on expense of protocol overhead. The following table specifies auxiliary functions and their relation to this document. Feature | Section ------------------------------+-------------- Non-OLSR interfaces | 12 Link-layer notifications | 13 Advanced link sensing | 14 Redundant topology | 15 Redundant MPR flooding | 16 The interpretation of the above table is as follows: if the feature listed is required, it SHOULD be provided as specified in the corresponding section.
Top   ToC   RFC3626 - Page 13

3. Packet Format and Forwarding

OLSR communicates using a 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. This also provides an easy way of piggybacking different "types" of information into a single transmission, and thus for a given implementation to optimize towards utilizing the maximal frame-size, provided by the network. These packets are embedded in UDP datagrams for transmission over the network. The present document is presented with IPv4 addresses. Considerations regarding IPv6 are given in section 17. 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 transmitting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be eliminated locally (i.e., each node maintains a duplicate set to prevent transmitting the same OLSR control message twice) and minimized in the entire network 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 originator 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.

3.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.

3.2. Main Address

For a node with one interface, the main address of a node, as defined in "OLSR Terminology", MUST be set to the address of that interface.
Top   ToC   RFC3626 - Page 14

3.3. Packet Format

The basic layout of any packet in OLSR is as follows (omitting 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 | Packet Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Vtime | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Vtime | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : (etc.)

3.3.1. Packet Header

Packet Length The length (in bytes) of the packet Packet Sequence Number The Packet Sequence Number (PSN) MUST be incremented by one each time a new OLSR packet is transmitted. "Wrap-around" is handled as described in section 19. A separate Packet Sequence Number is maintained for each interface such that packets transmitted over an interface are sequentially enumerated.
Top   ToC   RFC3626 - Page 15
   The IP address of the interface over which a packet was transmitted
   is obtainable from the IP header of the packet.

   If the packet contains no messages (i.e., the Packet Length is less
   than or equal to the size of the packet header), the packet MUST
   silently be discarded.

   For IPv4 addresses, this implies that packets, where the Packet
   Length < 16 MUST silently be discarded.

3.3.2. Message Header

Message Type This field indicates which type of message is to be found in the "MESSAGE" part. Message types in the range of 0-127 are reserved for messages in this document and in possible extensions. Vtime This field indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received. The validity time is represented by its mantissa (four highest bits of Vtime field) and by its exponent (four lowest bits of Vtime field). In other words: validity time = C*(1+a/16)* 2^b [in seconds] where a is the integer represented by the four highest bits of Vtime field and b the integer represented by the four lowest bits of Vtime field. The proposed value of the scaling factor C is specified in section 18. Message Size This 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 - until the end of the packet). Originator Address 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 IP header, which is changed each time to the address of the intermediate interface
Top   ToC   RFC3626 - Page 16
         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 message.

      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
         originating from the node.  "Wrap-around" is handled as
         described in section 19.  Message sequence numbers are used to
         ensure that a given message is not retransmitted more than once
         by any node.

3.4. Packet Processing and Message Flooding

Upon receiving a basic packet, a node examines each of the "message headers". Based on the value of the "Message Type" field, the node can determine the fate of the message. A node may receive the same message several times. Thus, to avoid re-processing of some messages which were already received and processed, each node maintains a Duplicate Set. In this set, the node records information about the most recently received messages where duplicate processing of a message is to be avoided. For such a message, a node records a "Duplicate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list, D_time), where D_addr is the originator address of the message, D_seq_num is the message sequence number of the message, D_retransmitted is a boolean indicating whether the message has been
Top   ToC   RFC3626 - Page 17
   already retransmitted, D_iface_list is a list of the addresses of the
   interfaces on which the message has been received 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".

   In this section, the term "Originator Address" will be used for the
   main address of the node which sent the 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 interface
   which sent the message.  The term "Receiving Interface Address" will
   be used for the address of the interface of the node which received
   the message.

   Thus, upon receiving a basic packet, a node MUST perform the
   following tasks for each encapsulated message:

     1    If the packet contains no messages (i.e., the Packet Length is
          less than or equal to the size of the packet header), the
          packet MUST silently be discarded.

          For IPv4 addresses, this implies that packets, where the
          Packet Length < 16 MUST silently be discarded.

     2    If the time to live of the message is less than or equal to
          '0' (zero), or if the message was sent by the receiving node
          (i.e., the Originator Address of the message is the main
          address of the receiving node): the message MUST silently be
          dropped.

     3    Processing condition:

          3.1  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 not be processed again.

          3.2  Otherwise, if the node implements the Message Type of the
               message, the message MUST be processed according to the
               specifications for the message type.
Top   ToC   RFC3626 - Page 18
     4    Forwarding condition:

          4.1  if there exists a tuple in the duplicate set, where:

                                D_addr    == Originator Address, AND

                                D_seq_num == Message Sequence Number,
                    AND

                                the receiving interface (address) is
                                in D_iface_list

               then the message has already been considered for
               forwarding and SHOULD NOT be retransmitted again.

          4.2  Otherwise:

               4.2.1
                    If the node implements the Message Type of the
                    message, the message MUST be considered for
                    forwarding according to the specifications for
                    the message type.

               4.2.2
                    Otherwise, if the node does not implement the
                    Message Type of the message, the message SHOULD
                    be processed according to the default
                    forwarding algorithm described below.

3.4.1. Default Forwarding Algorithm

The default forwarding algorithm is the following: 1 If the sender interface address of the message is not detected to be in the symmetric 1-hop neighborhood of the node, the forwarding algorithm MUST silently stop here (and the message MUST NOT be forwarded). 2 If there exists a tuple in the duplicate set where: D_addr == Originator Address D_seq_num == Message Sequence Number Then the message will be further considered for forwarding if and only if: D_retransmitted is false, AND
Top   ToC   RFC3626 - Page 19
               the (address of the) interface which received the message
               is not included among the addresses in D_iface_list

     3    Otherwise, if such an entry doesn't exist, the message is
          further considered for forwarding.

   If after those steps, the message is not considered for forwarding,
   then the processing of this section stops (i.e., steps 4 to 8 are
   ignored), otherwise, if it is still considered for forwarding then
   the following algorithm is used:

     4    If the sender interface address is an 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 retransmitted
          (as described later in steps 6 to 8).

     5    If an entry in the duplicate set exists, with same Originator
          Address, and same Message Sequence Number, the entry is
          updated as follows:

               D_time    = current time + DUP_HOLD_TIME.

               The receiving interface (address) is added to
               D_iface_list.

               D_retransmitted is set to true if and only if the message
               will be retransmitted according to step 4.

          Otherwise an entry in the duplicate set is recorded with:

               D_addr    = Originator Address

               D_seq_num = Message Sequence Number

               D_time    = current time + DUP_HOLD_TIME.

               D_iface_list contains the receiving interface address.

               D_retransmitted is set to true if and only if the message
               will be retransmitted according to step 4.

   If, and only if, according to step 4, the message must be
   retransmitted then:

     6    The TTL of the message is reduced by one.

     7    The hop-count of the message is increased by one
Top   ToC   RFC3626 - Page 20
     8    The message is broadcast on all interfaces (Notice: The
          remaining fields of the message header SHOULD be left
          unmodified.)

3.4.2. Considerations on Processing and Forwarding

It should be noted that processing and forwarding messages are two different actions, conditioned by different rules. Processing relates to using the content of the messages, while forwarding is related to retransmitting the same message for other nodes of the network. Notice that this specification includes a description for both the forwarding and the processing of each known message type. Messages with known message types MUST *NOT* be 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 and, if necessary, retransmitted. This enables 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). It also enables bypassing of the MPR flooding mechanism if for some reason classical flooding of a message type is required, the algorithm which specifies how such messages should be handled will simply rebroadcast the message, regardless of MPRs. 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 being able to maintain compatibility with older implementations. The REQUIRED message types for the core functionality of OLSR are: - HELLO-messages, performing the task of link sensing, neighbor detection and MPR signaling, - TC-messages, performing the task of topology declaration (advertisement of link states). - MID-messages, performing the task of declaring the presence of multiple interfaces on a node. Other message types include those specified in later sections, as well as possible future extensions such as messages enabling power conservation / sleep mode, multicast routing, support for unidirectional links, auto-configuration/address assignment etc.
Top   ToC   RFC3626 - Page 21

3.5. Message Emission and Jitter

As a basic implementation requirement, synchronization of control messages SHOULD be avoided. As a consequence, OLSR control 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 underlying 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 avoid such synchronizations, the following simple strategy for emitting control messages is proposed. A node SHOULD 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 [0,MAXJITTER] 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.). Jitter SHOULD also be introduced when forwarding messages. The following simple strategy may be adopted: when a message is to be forwarded by a node, it should be kept in the node during a short period of time : Keep message period = jitter Where jitter is a random value in [0,MAXJITTER]. Notice that when the node sends a control message, the opportunity to piggyback other messages (before their keeping period is expired) may be taken to reduce the number of packet transmissions. Notice, that a minimal rate of control messages is imposed. A node MAY send control messages at a higher rate, if beneficial for a specific deployment.