tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 3626

Experimental
Pages: 75
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: MANET

Optimized Link State Routing Protocol (OLSR)

Part 1 of 3, p. 1 to 21
None       Next RFC Part

 


Top       ToC       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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.


Next RFC Part