INTERNET-DRAFT                                          Philippe Jacquet                                            Thomas Clausen
IETF MANET Working Group                                Philippe Jacquet
Expiration: 30 April 2002                                   Anis Laouiti
                                                           Pascale Minet
                                                        Paul Muhlethaler
Expiration: 02 September 2001
                                                             Amir Qayyum
							    Anis Laouiti
                                                         Laurent Viennot
							  Thomas Clausen
                                              INRIA Rocquencourt, France
                                                            2 March
                                                         31 October 2001

                 Optimized Link State Routing Protocol
                    draft-ietf-manet-olsr-04.txt

                      draft-ietf-manet-olsr-05.txt

Status of this Memo

   This document is a submission by the Mobile Ad Hoc Networking Working
   Group of the Internet Engineering Task Force (IETF).  Comments should
   be submitted to the manet@itd.nrl.navy.mil mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC 2026 except that the right to
   produce derivative works is not granted. 2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups. Note that other
   groups may also distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   This document describes the Optimized Link State Routing (OLSR)
   protocol for mobile ad hoc networks. The protocol is an optimization
   of the pure link state algorithm tailored to the requirements of a
   mobile wireless LAN. The key concept used in the protocol is that of
   multipoint relays (MPRs) [1] & [1], [2]. MPRs are selected nodes which
   forward broadcast messages during the flooding process. This
   technique substantially reduces the message overhead as compared to a
   pure flooding mechanism mechanism, where every node retransmits each message
   when it receives the first copy of the
   packet. message. In OLSR, information
   flooded in the network "through" these MPRs is also "about" the MPRs. Thus
   Thus, a second optimization is achieved by minimizing the "contents"
   of the control messages flooded in the network. Hence, as contrary to
   the classic link state algorithm, a node declares only a small subset
   of links
   with the to its neighbor nodes are declared instead of nodes, rather than all the
   links. links to all
   neighbors. This information is then used by the OLSR protocol for
   route calculation. As a consequence hereof, the routes contain only
   the MPRs as intermediate nodes from a Source to a Destination. OLSR
   provides optimal routes (in terms of number of hops). The protocol is
   particularly suitable for large and dense networks as the technique
   of MPRs works well in this context.

			   Contents

Status

Table of This Memo                                             1
Abstract                                                        1 Contents

     1. Introduction                                                3
 2. . . . . . . . . . . . . . . . . . . . . . . . .   4
     1.1. Changes							3
 3. OLSR terminology  . . . . . . . . . . . . . . . . . . . . . . . . .   4
 4.
     1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . .   5
     1.3. Applicability Section					5
     4.1 Networking Context					5
     4.2 Protocol Characteristics and Mechanisms		6
 5.  . . . . . . . . . . . . . . . . . .   7
     1.4. Protocol Overview						8
 6.  . . . . . . . . . . . . . . . . . . . .   7
     1.5. Multipoint relays						9
 7. Protocol functioning				       10
     7.1 Relays  . . . . . . . . . . . . . . . . . . . .   8

     2. Protocol and port number			       10
     7.2 Packet format					       10
          7.2.1 Functioning . . . . . . . . . . . . . . . . . . . .   9
     2.1. Packet Format and Forwarding . . . . . . . . . . . . . . .  10
     2.1.1. Protocol and Port Number . . . . . . . . . . . . . . . .  11
     2.1.2. Multiple Interfaces and Main Address . . . . . . . . . .  11
     2.1.3. Packet Format  . . . . . . . . . . . . . . . . . . . . .  11
     2.1.3.1. Packet Header  . . . . . . . . . . . . . . . . . . . .  12
	  7.2.2
     2.1.3.2. Message Header . . . . . . . . . . . . . . . . . . . .  12
	  7.2.3
     2.1.4. Packet Processing and Message Flooding . . . . . . . . .  13
     7.3 Neighbor sensing				       15
          7.3.1 Neighbor sensing information base	       15
          7.3.2 HELLO message broadcast
     2.1.5. Message Emission and Jitter  . . . . . . . . . . . . . .  16
	  7.3.3

     2.2. Neighbor Sensing . . . . . . . . . . . . . . . . . . . . .  17
     2.2.1. HELLO message processing		       19
     7.4 Multipoint relay selection			       21
     7.5 Multipoint relay information declaration	       22
          7.5.1 Topology information base		       22
          7.5.2 TC message broadcast			       23
	  7.5.3 TC message processing			       24
     7.6 Routing table calculation			       26
     7.7.Link layer notification			       27
 8. Packet Forwarding					       28
     8.1 Data packet forwarding				       28
     8.2 Control message forwarding			       28
 9. Proposed values for constants			       29
10. Sequence numbers					       29
11. References						       30
12. Authors' addresses					       31

1. Introduction

   This Optimized Link State Routing protocol inherits Message Format . . . . . . . . . . . . . . . . . .  18
     2.2.2. Neighbor Sensing Information Base  . . . . . . . . . . .  20
     2.2.2.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . .  20
     2.2.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . .  20
     2.2.2.3. MPR Set  . . . . . . . . . . . . . . . . . . . . . . .  21
     2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . .  21
     2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . .  21
     2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . .  22
     2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . .  25
     2.2.5.1. Neighborhood and 2-hop Neighborhood Changes  . . . . .  27
     2.2.6. Advanced Neighbor Sensing Functioning  . . . . . . . . .  27
     2.2.6.1. Link Hysteresis  . . . . . . . . . . . . . . . . . . .  28
     2.2.6.2. Optional Link layer notification . . . . . . . . . . .  29
     2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . .  30
     2.3.1. Multipoint Relay Information Declaration . . . . . . . .  30
     2.3.1.1. Topology Information Base  . . . . . . . . . . . . . .  30
     2.3.1.2. TC Message Generation  . . . . . . . . . . . . . . . .  31
     2.3.1.3. TC Message Processing  . . . . . . . . . . . . . . . .  32
     2.3.2. Multiple Interface Association . . . . . . . . . . . . .  34
     2.3.2.1. Interface Association Information Base . . . . . . . .  34
     2.3.2.2. MID Broadcast  . . . . . . . . . . . . . . . . . . . .  35
     2.3.2.3. MID Message Processing . . . . . . . . . . . . . . . .  36
     2.3.3. Associated Networks and Hosts  . . . . . . . . . . . . .  37
     2.3.3.1. Host and Network Association Information Base  . . . .  38
     2.3.3.2. Host and Network Association Message Broadcast . . . .  38
     2.3.3.3. HNA Message Processing . . . . . . . . . . . . . . . .  39
     2.3.3.4. Optional Link layer notification . . . . . . . . . . .  40
     2.3.4. Routing Table Calculation  . . . . . . . . . . . . . . .  41

     3. Node Configuration . . . . . . . . . . . . . . . . . . . . .  43
     3.1. Address Assignment . . . . . . . . . . . . . . . . . . . .  43
     3.2. Routing Configuration  . . . . . . . . . . . . . . . . . .  43
     3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . .  44
     3.4. Control Message Forwarding . . . . . . . . . . . . . . . .  44

     4. IPv6 Considerations  . . . . . . . . . . . . . . . . . . . .  44
     5. Proposed Values for the Constants  . . . . . . . . . . . . .  44
     6. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . .  45
     7. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . .  46

1.  Introduction

   The Optimized Link State Routing Protocol (OLSR) is developed for
   mobile ad hoc networks. It operates as a table driven and proactive
   protocol, thus exchanges topology information with other nodes of the
   network regularly. The nodes which are selected as a multipoint relay
   by some neighbor nodes announce this information periodically in
   their control messages. Thereby, a node announces to the network,
   that it has reachability to the nodes which have selected it as MPR.
   In route calculation, the MPRs are used to form the route from a
   given node to any destination in the network. The protocol uses the
   MPRs to facilitate efficient flooding of control messages in the net-
   work.

   MPRs are selected by a node among its one hop neighbors with "symmet-
   ric", i.e. bi-directional, link. Therefore, selecting the route
   through MPRs automatically avoids the problems associated with data
   packet transfer over uni-directional links (such as the problem of
   not getting link-layer acknowledgments for data packets at each hop)

   OLSR is developed to work independently from other protocols. Like-
   wise, OLSR makes no assumptions about the underlying link-layer.

   OLSR inherits the concept of forwarding and relaying from HIPERLAN (a
   MAC layer protocol) which is standardized by ETSI [3]. The protocol
   is developed in the IPANEMA project (part of the Euclid program) and
   in the PRIMA project (part of the RNRT program).

1.1.  Changes

   Major changes from version 04 to version 05

     -    Introduction of support for multiple interfaces

     -    Introduction of support for associated hosts and networks.

     -    Introduction of support for advanced neighbor sensing through
          hysteresis.

     -    Modularity between neighbor sensing and topology discovery
          emphasized.

   Major changes from version 03 to version 04

     -    Finalized the generic packet/message format to include fea-
          tures for scope-limited (diameter-bound) flooding of messages
          and to handle duplicate messages.

     -    Editorial changes towards language consistency.

   Major changes from version 02 to version 03

     -    Introduction of assigned port number for use with OLSR.

     -    The packet format now uses "message length" rather than an
          offset to the next message.

     -    Optional section describing how link-layer notifications can
          be utilized included.

   Major changes from version 01 to version 02

     -    Introduction of a unified packet format for encapsulation of
          all messages being exchanged between nodes. This also serves
          to facilitate extensions in future versions of the protocol
          (i.e. introduction of new protocol messages) without breaking
          backwards compatibility.

     -    Removal of "Power Conservation" from this draft. Power Conser-
          vation may be considered as an extension to the basic routing
          capabilities.

1.2.  OLSR Terminology

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC2119 [5].  The OLSR
   protocol uses the following terminology:

     multipoint relay (MPR)

          A node which is selected by its one-hop neighbor, node X, to
          "re-transmit" all the broadcast messages that it receives from
          X, provided that the same message is not already received, and
          the time to live field of the message is greater than one.

     multipoint relay selector (MPR selector, MS)

          A node which has selected its one-hop neighbor, node X, as its
          multipoint relay, will be called a multipoint relay selector
          of node X.

     node

          A MANET router which implements this Optimized Link State
          Routing protocol.

     interface

          A network device participating in the MANET (it is usually
          wireless). A node may have several interfaces, each one pos-
          sessing its own IP address.

     link

          A link is a pair of interfaces (from two different nodes) sus-
          ceptible to hear one another (i.e. one may be able to receive
          traffic from the other).  A node is said to have a link to
          another node when one of its interface has a link to one of
          the interfaces of the other node.

     neighbor interface

          An interface I is a neighbor interface of an interface J if J
          can hear I (i.e. it is possible to send traffic from I to J).

     sender interface

          The sender interface of a control message is the neighbor
          interface over which the message has been transmitted.

     receiver interface

          The reciever interface of a control message is the (local)
          interface, over which a control message has been recieved.

     neighbor node

          A node X is a neighbor node of node Y if node Y can hear node
          X (i.e. one of X interfaces is a neighbor interface of some
          interface of Y).

     symmetric link

          A bi-directional link between two interfaces, i.e. interface I
          and interface J where both can hear each other.

     symmetric neighborhood
          The symmetric neighborhood of any node X is the set of nodes
          which have at least one symmetric link to X.

     symmetric 2-hop neighborhood
          The symmetric 2-hop neighborhood of X is the set of nodes
          which don't have a symmetric link to X but have a symmetric
          link to the symmetric neighborhood of X.

     main address

          The main address of a node, which will be used in OLSR control
          traffic as the "originator address" of all messages emitted by
          this node.  It is the address of one of its interfaces.

1.3.  Applicability Section

   OLSR is a proactive routing protocol for mobile ad-hoc networks
   (MANETs). It is well suited to large and dense mobile networks, as
   the optimization achieved using the MPRs works well in this context.
   The larger and more dense a network, the more optimization can be
   achieved as compared to the classic link state algorithm. OLSR uses
   hop-by-hop routing, i.e. each node uses its local information to
   route packets.

   OLSR is well suited for networks, where the traffic is random and
   sporadic between "several" nodes rather than being almost exclusively
   between a small specific set of nodes. The performance of the proto-
   col, compared to a reactive protocol, is even better if these
   [source, destination] pairs change with time [4]. Such changes may
   initiate substantial traffic (query flooding) in case of a reactive
   protocol, but nothing in OLSR, as the routes are maintained for each
   known destination all the time.

1.4.  Protocol Overview

   OLSR is a proactive routing protocol for mobile ad hoc networks.  The
   protocol inherits the stability of a link state algorithm and has the
   advantage of having routes immediately available when needed due to
   its proactive nature. OLSR is an optimization over the pure link
   state protocol, tailored for mobile ad hoc networks.

   Firstly, it reduces the size of the control messages: rather than
   declaring all links, a node declares only a subset of links with its
   neighbors, namely the links to those nodes which are its MPR selec-
   tors. Secondly, OLSR minimizes flooding of control traffic by using
   only selected nodes, called MPRs, to diffuse its control messages.
   This technique significantly reduces the number of retransmissions in
   a flooding or broadcast procedure.

   OLSR MAY optimize the reactivity to topological changes by reducing
   the maximum time interval for periodic control message transmission.
   Furthermore, as OLSR continuously maintains routes for all destina-
   tions in the network, the protocol is beneficial for traffic patterns
   where a large subset of nodes are communicating with another large
   subset of nodes, and where the [source,destination] pairs are chang-
   ing over time. The protocol is particularly suited for large and
   dense networks, as the optimization done using MPRs works well in
   this context. The larger and more dense a network, the more optimiza-
   tion can be achieved as compared to the classic link state algorithm.

   OLSR is designed to work in a completely distributed manner and does
   thus not depend on any central entity. The protocol does NOT REQUIRE
   reliable transmission of control messages: each node sends control
   messages periodically, and can therefore sustain an occasional loss
   of some such messages. Such losses occur frequently in radio networks
   due to collisions or other transmission problems.

   Also, OLSR does not require sequenced delivery of messages. Each con-
   trol message contains a sequence number which is incremented for each
   message. Thus the recipient of a control message can easily identify
   which information is newer - even if messages have been re-ordered
   while in transmission.

   Furthermore, OLSR provides support for protocol extensions such as
   sleep mode operation, multicast-routing etc. Such extensions may be
   introduced as additions to the protocol without breaking backwards
   compatibility with earlier versions.

   OLSR performs hop by hop routing, i.e. each node uses its most recent
   local information to route a packet. Hence, for OLSR to be able to
   route packets, the frequency of control messages should be tuned to
   the speed of the mobile nodes such that their movements can be
   tracked by their neighborhood.

   OLSR does not require any changes to the format of IP packets. Thus
   any existing IP stack can be used as is: the protocol only interacts
   with routing table management.

1.5.  Multipoint Relays

   The idea of multipoint relays is to minimize the overhead of flooding
   messages in the network by reducing duplicate retransmissions in the
   same region. Each node in the network selects a set of nodes in its
   symmetric neighborhood which may retransmit its messages. This set of
   selected neighbor nodes is called the "Multipoint Relay" (MPR) set of
   that node. The neighbors of node N which are *NOT* in its MPR set,
   receive and process broadcast messages but do not retransmit broad-
   cast messages received from node N.

   Each node selects its MPR set among its one hop symmetric neighbors.
   This set is selected such that it covers (in terms of radio range)
   all nodes that are two hops away. The MPR set of N, denoted as
   MPR(N), is then an arbitrary subset of the symmetric neighborhood of
   N which satisfies the following condition: every node in the symmet-
   ric 2-hop neighborhood of N must have a symmetric link towards
   MPR(N). The smaller the MPR set is, the more optimal is the routing
   protocol. [2] gives an analysis and example of MPR selection algo-
   rithms.

   Each node maintains information about the neighbors that have
   selected it as MPR. This set is called the "Multipoint Relay Selector
   set" (MPR selector set) of a node. A node obtains this information
   from periodic HELLO messages received from the neighbors.

   A broadcast message, intended to be diffused in the whole network,
   coming from these MPR selectors is assumed to be retransmitted by the
   node. This set can change over time (i.e. when a node selects another
   MPR-set) and is indicated by the selector nodes in their HELLO mes-
   sages. Each node has a specific "Multipoint relay Selector Sequence
   Number" (MSSN) associated with this set. Whenever the MPR selector
   set is updated, the node also increments its MSSN.

   OLSR relies on selection of MPRs, and calculates routes through these
   nodes. I.e., the path is made of links between MPR and MPR selector.
   To enable this, each node in the network periodically floods informa-
   tion describing which neighbors have selected it as a MPR.  Upon
   receipt of this "MPR Selector" information, each node calculates or
   updates the route to each known destination. So principally, the
   route is a sequence of hops through the MPRs from source to the des-
   tination.

   MPRs are selected among the symmetric neighborhood. Therefore,
   selecting the route through MPRs automatically avoids the problems
   associated with data packet transfer over uni-directional links such
   as the problem of not getting an acknowledgment for the data packets
   at each hop.

2.  Protocol Functioning

   This section describes the details of the protocol functioning.  This
   includes descriptions of the format and contents of the packets being
   exchanged by routers, the algorithms (e.g. for packet handling and
   routing table calculation) and suggested data structures internally
   kept in each router.

   The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen
   as a transfer layer for the routing protocol. This provides nodes
   with information about their neighbors and offer an optimized mecha-
   nism for flooding messages through the concept of MPRs. It completely
   relies on the exchange of HELLO messages.

   The "Topoly Discovery" mechanism relies on the "Packet Forwarding"
   and "Neighbor Sensing" mechanisms. Neighbor and MPR information from
   the "Neighbor Sensing" mechanism is utilized by a node for diffusing
   local topology information to the whole network. Topology information
   is diffused through the "Packet Forwarding" mechanism, and relies on
   TC, MID and HNA messages. Resulting from the "Topology Discovery"
   mechanism is information which allows routing table calculation.

   The key notion in these modules is the MPR relationship.

2.1.  Packet Format and Forwarding

   OLSR communicates using an unified packet format for all data related
   to the protocol. The purpose of this is to facilitate extensibility
   of the protocol without breaking backwards compatibility, as well as
   to provide an easy way of piggybacking different "types" of informa-
   tion into a single transmission. These packets are embedded in UDP
   datagrams for transmission over the network. The present draft is
   presented with IPv4 addresses.  Considerations regarding IPv6 are
   given in section 4.

   Each packet encapsulates one or more messages. The messages share a
   common header format, which enables nodes to correctly accept and (if
   applicable) retransmit messages of an unknown type.

   Messages can be flooded onto the entire network, or flooding can be
   limited to nodes within a diameter (in terms of number of hops) from
   the originator of the message. Thus, broadcasting a message to the
   neighborhood of a node is just a special case of flooding. When
   flooding any control message, duplicate retransmissions will be elim-
   inated locally (i.e. each node maintains a duplicate table to prevent
   transmitting the same message twice) and minimized in the entire net-
   work through the usage of MPRs as described in later sections.

   Furthermore, a node can examine the header of a message to obtain
   information on the distance (in terms of number of hops) to the orig-
   inator of the message. This feature may be useful in situations
   where, e.g., the time information from a received control messages
   stored in a node depends on the distance to the originator.

2.1.1.  Protocol and Port Number

   Packets in OLSR are communicated using UDP. Port 698 has been
   assigned by IANA for exclusive usage by the OLSR protocol.

2.1.2.  Multiple Interfaces and Main Address

   A node may have several wireless interfaces, each of them having a
   distinct IP address. OLSR supports such nodes with multiple inter-
   faces. For this reason, each node MUST choose one of its interface
   addresses as its "main address". For example, the smallest interface
   address may be the chosen as the main interface. The main address
   MUST be used in OLSR control traffic as the "originator address" of
   all messages emitted by a node.

   A node must transmit and retransmit all control messages on all
   interfaces.  The source address in the IP header must contain the IP-
   address of the interface where the message is transmitted. This
   address will be denoted the "sender interface address".

2.1.3.  Packet Format

   The basic layout of any packet in OLSR is as follows (omitting the IP
   and UDP headers):

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |         Packet Length         |            Reserved           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  Message Type |    Reserved   |         Message Size          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Originator Address                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  Time To Live |   Hop Count   |    Message Sequence Number    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      :                            MESSAGE                            :
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  Message Type |    Reserved   |         Message Size          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Originator Address                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  Time To Live |   Hop Count   |    Message Sequence Number    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      :                            MESSAGE                            :
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                                                               :
               (etc)

2.1.3.1.  Packet Header

     Packet Length

          The length (in bytes) of the packet

     Reserved

          MUST be set to "0000000000000000" to be in compliance with
          this version of the draft.

   The sender information for a packet is obtainable from the UDP
   header.

2.1.3.2.  Message Header

     Message Type

          This field indicates which type of message are to be found in
          the "MESSAGE" partition. Message types in the range of 0-127
          are reserved for messages in this draft and in extension
          drafts.

     Reserved

          MUST be set to "00000000" to be in compliance with this ver-
          sion of the draft.

     Message Size

          This field gives the size of this message, counted in bytes
          and measured from the beginning of the "Message Type" field
          and until the beginning of the next "Message Type" field (or -
          if there are no following messages - the end of the packet).

     Originator Address
          This field contains the main address of the node, which has
          originally generated this message. This field SHOULD NOT be
          confused with the source address from the UDP header, which is
          changed each time to the address of the intermediate interface
          which is "re-transmitting" this message. The Originator
          Address field MUST *NEVER* be changed in retransmissions.

     Time To Live

          This field contains the maximum number of hops a message will
          be transmitted. Before a message is retransmitted, the Time To
          Live MUST be decremented by 1. When a node receives a message
          with a Time To Live equal to 0 or 1, the message MUST NOT be
          retransmitted under any circumstances. Normally, a node would
          not receive a message with a TTL of zero.

          Thus, by setting this field, the originator of a message can
          limit the flooding radius.

     Hop Count

          This field contains the number of hops a message has attained.
          Before a message is retransmitted, the Hop Count MUST be
          incremented by 1.

          Initially, this is set to '0' by the originator of the mes-
          sage.

     Message Sequence Number

          While generating a message, the "originator" node will assign
          a unique identification number to each message. This number is
          inserted into the Sequence Number field of the message. The
          sequence number is increased by 1 (one) for each message orig-
          inating from the node - "wrap-arounds" are handled as
          described in a later section. Message sequence numbers are
          used to ensure that a given message is not retransmitted more
          than once by any node.

2.1.4.  Packet Processing and Message Flooding

   Upon receiving a basic packet, the protocol parser examines each of
   the "message headers". Based on the value of the "Message Type"
   field, the parser can determine the fate of the message. A node may
   receive the same message several times. This can happen only if the
   message is retransmitted by two interfaces in the receivers neighbor-
   hood and the "Time To Live" and the "Hop Count" fields in the message
   satisfy the following condition:

                      Time To Live + Hop Count > 1

   Thus, to avoid re-processing of a message which was already received
   and processed, each node maintains a Duplicate table. In this table,
   the node records information about the most recently received mes-
   sages where the above condition holds. For each message, satisfying
   the above condition, a node records a "Duplicate Tuple" (D_addr,
   D_seq_num, D_time), where D_addr is the originator address of the
   message, D_seq_num is the message sequence number of the message and
   D_time specifies the time at which a tuple expires and *MUST* be
   removed.

   In a node, the set of Duplicate Tuples are denoted the "Duplicate
   set".

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

     1    If the time to live of the message is less than or equal to
          '0' (zero), the message MUST silently be dropped.

     2    If there exists a tuple in the duplicate set, where:

                        D_addr == Originator Address, AND

                        D_seq_num == Message Sequence Number

          then the message has already been completely processed and
          MUST silently be ignored.

     3    Otherwise, if the Message Type of the message is known to the
          node, the message MUST be processed according to the specifi-
          cations of such message type.

     4    Otherwise, If the Message Type of the message is not known to
          the node, the message SHOULD be processed according to the
          following algorithm:

          4.1  If the sender of the message is not detected to be in the
               symmetric neighborhood of the node, the message MUST
               silently be dropped.

          4.2  If the sender of the message is detected to be in the
               symmetric neighborhood of the node, an entry in the
               duplicate set is recorded with:

                    D_addr = originator address

                    D_seq_num = Message Sequence Number

                    D_time = current time + D_HOLD_TIME.

          4.3  If the sender address is the link interface address of a
               MPR selector of this node and if the time to live of the
               message is greater than '1', the message MUST be for-
               warded according to the following:

               4.3.1
                    The TTL of the message is reduced by one.

               4.3.2
                    The hop-count of the message is increased by one

               4.3.3
                    The message is broadcasted on all interfaces
                    (Notice: The remaining fields of the message header
                    SHOULD be left unmodified.)

   Notice: known message types are *not* forwarded "blindly" by this
   algorithm. Forwarding (and setting the correct message header in the
   forwarded, known, message) is the responsibility of the algorithm
   specifying how the message is to be handled. This enables, e.g., a
   message type to be specified such that the message can be modified
   while in transit (e.g. to reflect the route the message has taken).
   Further, it enables that the optimization through the MPRs can be
   bypassed: if for some reason pure flooding of a message type is
   required (e.g. to transmit control information over unidirectional
   links), the algorithm which specifies how such messages should be
   handled will simply rebroadcast the message, regardless of MPRs.

   Finally, notice that a message, which is to be broadcasted in the
   neighborhood but not flooded into the entire network, (e.g. a HELLO-
   message) is simply specified by setting the time to live to 1 (one)
   and the concept of
   forwarding hop count to 0 (zero), and relaying from HIPERLAN (a MAC layer protocol) that no duplicate tuples are
   recorded for such messages.

   By defining a set of message types, which
   is standardized MUST be recognized by ETSI [3]. all
   implementations of OLSR, it will be possible to extend the protocol
   through introduction of additional message types, while still be able
   to maintain compatibility with older implementations. The REQUIRED
   message types for OLSR protocol is developed in are:

     -    HELLO-messages, performing the
   IPANEMA project (part task of Euclid program) and in neighbor sensing.

     -    TC-messages, performing the PRIMA project
   (part task of RNRT program).

   This protocol is developed for mobile ad hoc networks. It operates
   as a table driven and proactive protocol and exchanges topology MPR information with other nodes declara-
          tion (OLSR topology declaration).

     -    MID-messages, performing the task of multiple interface decla-
          ration.

     -    HNA-messages, performing the task of associated host and/or
          network at regular intervals.
   The nodes which are selected as declaration

   Extensions may for example be messages enabling power conservation /
   sleep mode, multicast routing, support for unidirectional links,
   auto-configuration/address assignment etc.

2.1.5.  Message Emission and Jitter

   As a multipoint relay by some basic implementation requirement, synchronization of control
   messages SHOULD be avoided. As a consequence, periodic OLSR messages
   should be emitted such that they avoid synchronization.

   Emission of control traffic from neighboring nodes may, for various
   reasons (mainly timer interactions with packet processing), become
   synchronized such that several neighbor nodes announce this information periodically in their
   control messages. The protocol uses the MPRs attempt to facilitate
   efficient flooding of transmit
   control messages in traffic simultaneously. Depending on the network. In route
   calculation, nature of the MPRs are used under-
   lying link-layer, this may or may not lead to form collisions and hence
   message loss - possibly loss of several subsequent messages of the route from a given
   same type.

   To counter such synchronizations, the following simple strategy for
   emitting control messages is proposed. A node may add an amount of
   jitter to any destination in the network.

   MPRs interval at which messages are selected by generated. The jitter
   must be a random value for each message generated. Thus, for a node among its one hop neighbors with
   "symmetric", i.e. bi-directional, link. Therefore, selecting the
   route through MPRs automatically avoids
   utilizing jitter:

        Actual message interval = MESSAGE_INTERVAL + jitter

   Where jitter is a value, randomly selected from the problems associated
   with data packet transfer on uni-directional links (such as interval
   [-MAXJITTER,0] and MESSAGE_INTERVAL is the
   problem value of not getting link-layer acknowledgments the message
   interval specified for the data
   packets message being emitted (e.g. HELLO_INTERVAL
   for HELLO messages, TC_INTERVAL for TC-messages etc.).

   It should be noticed that the present draft imposes a minimal rate of
   control message emission. However a node MAY send control messages at each hop)

   The OLSR protocol
   a higher rate (e.g. for better reacting to high mobility). It is developed an
   implementation issue to work independently from other
   protocols. But it can optimize the rate of control packet emission.
   If all nodes use the same constant base rate, introducing some jitter
   as described above may be adapted to operate desirable.

2.2.  Neighbor Sensing

   Each node should detect the neighbor interfaces with a protocol (like
   IMEP [4]) which could provide common functionalities such as it has a
   direct and symmetric link. Uncertainties over radio propagation may
   make some links unidirectional. Consequently, all links MUST be
   checked in both directions in order to be considered valid.

   To perform neighbor sensing, multipoint relaying, security authentication,
   etc.

2. Changes

   Major changes from version 03 detection, each node broadcasts HELLO messages,
   containing information about heard neighbor interfaces and their link
   status. The link status may either be "symmetric", "heard" (asymmet-
   ric), "MPR" or "lost". "Symmetric" indicates, that the link has been
   verified to version 04

   - Finalized be bi-directional, i.e. it is possible to transmit data
   in both directions. "Heard" indicates that the generic packet/message format to
     include features for scope-limited (diameter-bound)
     flooding of node can hear HELLO
   messages and to handle duplicate messages.

   - Editorial changes towards language consistency.

   Major changes from version 02 a neighbor interface, but it is not confirmed that this
   neighbor interface is also able to version 03

   -  Introduction receive messages from the node.
   "MPR" indicates, that a node is selected by the sender as a MPR. A
   status of assigned port number for use MPR further implies that the link is symmetric.  "Lost"
   indicates that the link with OLSR.

   -  The packet format this neighbor interface is now uses "message length" rather than an
      offset lost.

   HELLO messages are broadcasted to all one-hop neighbors and are emit-
   ted on each MANET interface of the next message.

   -  Optional section describing how link-layer notifications
      can be utilized included.

   Major changes from version 01 node. They are *not relayed* to version 02

   -  Introduction of
   further nodes.

   More precisely, a unified packet format HELLO message contains for encapsulation each interface I:

     -    a list of
      all messages being exchanged between nodes. This also serves neighbor interface addresses, having a symmetric
          link to facilitate extensions in future versions interface I;

     -    a list of neighbor interface addresses, which are "heard" by
          interface I (for historical reasons, the protocol
      (i.e. introduction of new protocol messages) without breaking
      backwards compatibility. term "heard" is used
          for "asymmetric");

     -  Removal    a list of "Power Conservation" from this draft. Power
      Conservation may be considered neighbor interface addresses of neighbors selected
          as an extension to the basic
      routing capabilities, and the information is therefore moved MPRs, AND having a symmetric link to draft-ietf-manet-olsr-extensions-00.txt.

3. OLSR Terminology

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
   this document interface I;

     -    a list of neighbor interface addresses, which have been lost.

   These lists are to be interpreted computed as described in RFC2119 [9].
   The OLSR protocol uses the following terminology, in addition to
   the terms defined in [5].

   connection

      A communication channel or medium *on the same physical
      interface*, over which the nodes can communicate with each
      other.

   holding time

      The lifetime associated with an entry in any table. An entry is
      kept in HELLO message generation
   section.

2.2.1.  HELLO Message Format

   To accommodate the table above requirements, as well as to accommodate for a period of time, equal
   future extensions, an approach similar to its holding
      time. If the entry is not refreshed during this period, it overall packet format
   is
      removed from the table when taken. Thus the holding time expires.

   multipoint relay (MPR)

      A node which proposed format of a HELLO message is:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   Reserved                    |  # Interfaces |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Interface Address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Interface Address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                             . . .                             :
      :                                                               :
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Link Type   |  Interface #  |       Link Message Size       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                             . . .                             :
      :                                                               :
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Link Type   |  Interface #  |       Link Message Size       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                                                               :
      :                                       :
   (etc)

   This is selected by its one-hop neighbor, node X, to
      "re-transmit" all sent as the broadcast messages that it receives from
      X, provided that data-portion of the general packet format
   described in the same message is not already received, Packet Format and Forwarding section, with the time "Mes-
   sage Type" set to live HELLO_MESSAGE and the TTL field set to 1 (one).

Description of the message fields
     Reserved

          This field is greater than zero.

   multipoint relay selector (MPR selector, MS)

      A node which has selected its one-hop neighbor, node X, as its
      multipoint relay, will reserved for future usage, and MUST be called a multipoint relay selector
      of node X.

   node

      A MANET router which implements set to
          "000000000000000000000000" for compliance with this Optimized Link State
      Routing protocol.

   symmetric link

      A bi-directional *link* between two neighbor nodes, i.e. node X
      and node Y where both can hear each other.

4. Applicability Section draft.

     # Interfaces

          This section dictates field indicates the characteristics number of additional MANET interfaces
          (excluding the OLSR protocol as
   specified in the Applicability Statement draft [6].

4.1. Networking Context

   OLSR is well suited to large and dense mobile networks, as main interface) possessed by the
   optimi- zation achieved using node. If the MPRs works well in
          node has only one interface, this
   context. The larger and more dense a network, number is 0.

     Interface Address

          This field indicates the more
   optimization can addresses of additional MANET inter-
          faces.  The first one will be achieved referenced as compared to the normal 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 interface address
          number 1, the traffic is random second as interface address number 2, and
   sporadic between "several" nodes rather than being almost
   exclusively between a small specific set of nodes. so on.
          The performance
   of the protocol, compared to a reactive protocol, is even better
   if these [source, destination] pairs change with time [8]. Such
   changes may initiate substantial traffic (Query flooding) in case main address of reactive protocol, but nothing the node (whose address is given in OLSR, as the routes are
   maintained for each known destination all
          originator field of the time.

4.2. Protocol Characteristics message header) will be referenced as
          interface address number 0.

     Link Message Size

          The size of the link message, counted in bytes and Mechanisms

   * Does measured
          from the protocol provide shortest path routes ?

      Yes.

   * Does beginning of the protocol provide support for unidirectional links? (if
     so, how?)

      No. However, "Link Type" field and until the use of uni-directional links may easily be
      enabled through optional extensions to next
          "Link Type" field (or - if there are no more link types - the protocol.

   * Does
          end of the protocol require message).

     Interface #

          This field indicates the use number of tunneling? (if so, how?)

      No.

   * Does the protocol require using some form interface to which the
          following list of source routing? (if
     so, how?)

      No.

   * Does neighbor interfaces corresponds.  Number 0
          indicates the protocol require main interface (whose address is the use main
          address).

     Link Type

          This field specifies the type of periodic messaging? (if so,
     how?)

      Yes. Periodically, each node in the network sends a message
      containing link between the addresses inter-
          face of the neighbors which have selected
      that node sender, as a MPR. This information enables other nodes to
      build routes to that node through the MPRs.

   * Does identified by the protocol require interface number, and
          the use following list of reliable or sequenced packet
     delivery? (if so, how?)

      No.

   * Does the protocol provide support for routing through neighbor interfaces. As a multi-
     technology routing fabric? (if so, how?)

     No. However, provisions for multiple interfaces may easily be
     enabled through extensions to minimum, the protocol.

   * Does
          following four link types are REQUIRED by OLSR:

          -    ASYM_LINK - indicating that the protocol provide support for multiple hosts per router?
     (if so, how?)

      Yes. The hosts links are added to asymmetric
               (i.e. the MPR selector set of neighbor interface is "heard").

          -    SYM_LINK - indicating that the links are symmetric.

          -    MPR_LINK - indicating, that the node
      (router), which will then announce links are symmetric AND
               that the hosts can be
      reached through neighbors have been selected as MPR by the
               sender.

          -    LOST_LINK - indicating that node.

   * Does the protocol support links have been lost.

     Neighbor Interface Address

          An interface address of a neighbor.

   Neighbor sensing is performed using HELLO message exchange, updating
   the IP addressing architecture? (if so,
     how?)

      Yes. Nodes are assigned neighbor sensing information base in each node.

2.2.2.  Neighbor Sensing Information Base

   The neighbor sensing information base stores information about neigh-
   bor interfaces, 2-hop neighbors, MPRs and MPR selectors.

2.2.2.1.  Neighbor Set

   For each of its interface I and addressed for each neighbor interface NI, heard
   by regular IP-addresses.

   * Does I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr,
   N_main_addr, N_SYM_time, N_ASYM_time, N_time) where N_if_id is the
   identification number of I, N_if_addr is the address of the protocol require link or neighbor status sensing (if so,
     how?)

      Yes. The protocol requires link status sensing. This service
   interface NI, N_main_addr is
      provided by sending/receiving periodic HELLO messages to/from
      one hop neighbors.

   * Does the protocol depend on a central entity? (if so, how?)

      No.

   * Does main address of the protocol function reactively? (if so, how?)

      No.

   * Does neighbor pos-
   sessing NI, N_SYM_time is the protocol function proactively? (if so, how?)

      Yes. Each node periodically sends information about its MPR
      selectors, time until which enables the nodes to construct routes to these
      MPR selectors through link is considered
   symmetric, N_ASYM_time is the node.

   * Does time until which the protocol provide loop-free routing? (if so, how?)

       Yes. As neighbor interface
   is considered heard, and N_time specifies the time at which this
   record expires and *MUST* be removed.  When N_SYM_time and
   N_ASYM_time are expired, the protocol uses a link state algorithm, routing is
       loop-free considered lost.

   This information is used when declaring the neighbor interfaces in a stable state.

   * Does
   the protocol provide for sleep period operation? (if so, how?)

     No. However, provisions for sleep-operation may easily be
     enabled through extensions HELLO messages. N_SYM_time and N_ASYM_time are used to decide the protocol.

   * Does
   Link Type declared for the protocol provide some form of security? (if so, how?)

      No.

   * Does neighbor interface. If N_SYM_time is not
   expired, the link is declared symmetric. If N_SYM_time is expired but
   N_ASYM_time is not, the protocol provide support for utilizing multi-channel,
     link-layer technologies? (if so, how?)

      Yes. OLSR makes no assumptions on link is declared heard. If both N_SYM_time
   and N_ASYM_time are expired, the underlying link-layer
      other, than that local broadcast must be available.

5. Protocol Overview

   OLSR link is declared lost.

   In a proactive routing protocol for mobile ad hoc networks.
   The protocol inherits node, the stability set of Neighbor Tuples are denoted the "Neighbor Set".

2.2.2.2.  2-hop Neighbor Set

   A node records a link state algorithm set of "2-hop tuples" (N_main_addr, N_if_addr,
   N_2hop_addr, N_time), describing symmetric or MPR links between its
   neighbors and
   has the advantage 2-hop symmetric neighborhood. N_main_addr and
   N_if_addr are the main address and an interface address of having routes immediately available when
   needed due to its proactive nature. OLSR a
   neighbor, N_2hop_addr is an optimization over
   the pure interface address of a 2-hop neighbor
   with a symmetric or MPR link state protocol, tailored for mobile ad hoc networks.

   Firstly, it reduces to interface N_if_addr and N_time speci-
   fies the size of time at which the control messages: rather than
   declaring all links, tuple expires and *MUST* be removed.

   This information is gathered from the HELLO messages received by a
   node declares only from its neighbor nodes.

   In a subset node, the set of links with
   its neighbors, namely 2-hop tuples are denoted the links to those nodes "2-hop Neighbor
   Set".

2.2.2.3.  MPR Set

   A node maintains a set of neighbors which are its elected as MPR. Their
   main addresses are listed in the so-called MPR
   selectors (see Set. The Multipoint
   relay selection section 6 on MPRs).  Secondly, OLSR minimizes
   flooding describes how MPRs are elected.

2.2.2.4.  MPR Selector Set

   A node maintains information (obtained from the HELLO messages) about
   the neighbors which have selected this node as a MPR.

   Thus, a node records a MPR-selector tuple (MS_if_addr, MS_main_addr,
   MS_time), for interfaces of control traffic by using only a neighbor which has selected nodes, called
   MPRs, to diffuse its messages.  This technique significantly
   reduces the number node as
   MPR. MS_if_addr is the address of an interface of retransmissions in a flooding or broadcast
   procedure.

   OLSR MAY optimize the reactivity to topological changes by
   reducing node which has
   selected the time interval for periodic control message
   transmission. Furthermore, node as OLSR keeps the routes MPR for all
   destinations in the network, the protocol that interface, MS_main_addr is beneficial for
   traffic patterns where a large subset of nodes are communicating
   with another large subset the main
   address of nodes, the MPR selector and where MS_time specifies the
   [source,destination] pairs are changing over time. The protocol is
   particularly suited for large time at which a
   tuple expires and dense networks, as *MUST* be removed.

   In a node, the
   optimization done using set of MPR-selector tuples are denoted the MPRs works well in "MPR Selec-
   tor Set". A sequence number, MSSN, is associated with this context. The
   larger and more dense set. When-
   ever a network, the more optimization can be
   achieved as compared tuple is added to or removed from this set, the normal link state algorithm.

   OLSR MSSN is designed to work incre-
   mented by 1.

2.2.3.  HELLO Message Generation

   The lists of addresses declared in a completely distributed manner HELLO message are computed from
   the Neighbor Set as follows:

     -    for each tuple where N_SYM_time and
   does thus not depend on any central entity. The protocol does NOT
   REQUIRE reliable transmission N_ASYM_time are expired,
          the N_if_addr is declared with LOST_LINK Link Type for inter-
          face N_if_id;

     -    for control messages: each node
   sends control messages periodically, tuple where N_SYM_time is not expired, the N_if_addr
          is declared with MPR_LINK Link Type if N_main_addr is in the
          MPR set and can therefore sustain an
   occasional loss SYM_LINK Link Type otherwise;
     -    for each tuple where N_SYM_time is expired but N_ASYM_time is
          not expired, the N_if_addr is declared with ASYM_LINK Link
          Type.

   The list of some such messages. Such losses occur frequent neighbor interfaces in radio networks a HELLO message can be partial
   (e.g. due to collisions or other transmission problems.

   Also, OLSR does NOT REQUIRE sequenced delivery of messages. Each
   control message contains size limitations, imposed by the network), the
   rule being the following: for each interface a sequence number which neighbor interface is incremented
   heard on, its address is cited with corresponding interface id at
   least once within a predetermined refreshing period (HELLO_INTERVAL).

   Notice that for each message. Thus limiting the recipient impact from loss of a control message can
   easily identify which information messages, it
   is newer - even if messages have
   been re-ordered while desirable that a message fits in transmission.

   Furthermore, OLSR provides support for protocol extensions such as
   sleep mode operation, multicast-routing etc. Such extensions may be
   introduced as additions to the protocol without breaking backwards
   compatibility with earlier versions.

   OLSR performs hop by hop routing, i.e. a single MAC packet.

   Each HELLO message generated is broadcasted on each MANET interface
   of the node.

2.2.4.  HELLO Message Processing

   Upon receiving a HELLO message, the node uses its most
   recent local SHOULD update the neighbor
   information corresponding to route a packet. Hence the sender node address (a node may -
   e.g. for OLSR to be
   able security reasons - wish to route packets, restrict updating the frequency of control neighbor-
   table, i.e. ignoring HELLO messages should from some nodes).

   In this section, the term "Originator Address" will be
   tuned to used for the speed
   main address of the mobile nodes such that their movements
   can node which sent the HELLO-message. The term
   "Sender Interface Address" will be tracked by their neighborhood.

   OLSR does NOT REQUIRE any changes to used for the sender address (given
   in the format of IP packets. Thus
   any existing IP stack can header of the packet containing the message) of the inter-
   face which sent the HELLO message. The term "Receiver Interface" will
   be used as it is: for the protocol only
   interacts with routing table management.

6. Multipoint Relays interface which received the HELLO message.  The idea of multipoint relays is to minimize term
   "link interface addresses" will be used for the overhead own interface
   addresses of
   flooding messages in the network by reducing duplicate
   retransmissions in the same region. Each node sender listed in the network
   selects HELLO message.

   The Neighbor Set should be updated as follows:

     1    Upon receiving a set of nodes in its neighborhood which may retransmit
   its messages. This set of selected HELLO message, if there exists no neighbor nodes is called
          tuple with

               N_if_addr == Sender Interface Address

          and

               N_if_id == identifier of the
   "Multipoint Relay" (MPR) set Receiver Interface,

          a new tuple is created with
               N_if_addr   = Sender Interface Address

               N_if_id     = identifier of that node. the Receiver Interface

               N_SYM_time  = current time - 1 (expired time)

               N_time      = current time + NEIGHB_HOLD_TIME

     2    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 tuple is then modified as follows:

          2.1  N_main_addr = Originator Address.

          2.3  N_time      = max (N_time, current time +
               NEIGHB_HOLD_TIME);

          2.4  N_ASYM_time = current time + NEIGHB_HOLD_TIME;

          2.5  if the node selects its MPR set finds the receiver interface address among its one hop neighbors. This
   set
               the addresses listed in the HELLO with:

                    Link Interface Address == Sender Interface Address,

               then, the tuple is selected such that it covers (in terms of radio range) all
   nodes that are two hops away. modified as follows:

                    if Link Type == LOST_LINK then

                         N_SYM_time = current time - 1 (expired time)

                    else:

                         N_SYM_time = current time + NEIGHB_HOLD_TIME,

                         N_time     = current time + 2 *
                         NEIGHB_HOLD_TIME.

   The neighborhood of any node N can
   be defined as rule for setting N_time is the set of nodes which have following: a symmetric link loosing its sym-
   metricity should still be advertised at least NEIGHB_HOLD_TIME. This
   allows neighbors to
   N. detect the link breakage.

   The 2-hop neighborhood of N can be defined Neighbor Set is updated as follows:

     1    for each 2-hop interface address listed in the set of nodes
   which don't have a symmetric link to N but have HELLO message
          with Link Type SYM_LINK or MPR_LINK, a symmetric link 2-hop tuple is created
          with:

               N_main_addr = Originator Address;
               N_if_addr   = Link Interface Address corresponding to the neighborhood of N. The MPR set of N, denoted as MPR(N), is
   then an arbitrary subset of
               2-hop interface address;

               N_2hop_addr = the neighborhood interface address of N which satisfies
   the following condition: every node in the 2-hop neighborhood of N
   must have a symmetric link toward MPR(N). The smaller the MPR set
   is, the more optimal is the routing protocol. [2] gives neigh-
               bor;

               N_time      = current time + NEIGHB_HOLD_TIME.

          This tuple may replaces an
   analysis older similar tuple with same
          N_if_addr and example about MPR selection algorithms.

   Each node maintains information about a set of its neighbors. This
   is the set of neighbors, called the "Multipoint Relay Selector
   set" (MPR selector set), which have selected the node as a MPR. A
   node obtains this information from N_2hop_addr values.

     2    For each 2-hop interface address listed in the periodic HELLO messages
   received from the neighbors. A broadcast message, intended to be
   diffused in message
          with Link Type LOST_LINK or ASYM_LINK, all the whole network, coming from these MPR selector
   neighbor nodes is assumed 2-hop tuples
          where:

               N_if_addr == Link Interface Address corresponding to be retransmitted by the node. This
   set can change over time (i.e. when a node selects another
   MPR-set)
               2-hop interface address,

          and is indicated by

               N_2hop_addr == the 2-hop interface address

          are deleted.

   Based on the information obtained from the selector nodes in their HELLO
   messages. Each messages, each node has a specific "Multipoint relay Selector
   Sequence Number" (MSSN) associated with this set. Whenever
   constructs its MPR selector set is updated, the node also increments its MSSN.

   OLSR relies on selection of MPRs, and calculates routes through
   these nodes. I.e. MPR nodes are selected as intermediate nodes in
   the path between set.

   Thus, upon receiving a source and HELLO message, if a destination. To enable this, each node finds one of its
   interface addresses in the network periodically broadcast the information
   describing which neighbors have selected it as a MPR.  Upon
   receipt list with a link type of this "MPR Selector" information, each node calculates
   or updates "MPR", it MUST
   update the route MPR selector set to each known destination. So principally, contain updated information about the route is a sequence
   sender of hops through the MPRs from source HELLO message:

     1    If there exists no MPR selector tuple with:

                    MS_if_addr   == Link Interface Address

               and

                    MS_main_addr == Originator Address

          then MSSN is incremented to indicate that the destination.

   MPRs are selected among the one hop neighbors with "symmetric"
   i.e. bi-directional link. Therefore, selecting the route through
   MPRs automatically avoids the problems associated with data packet
   transfer on uni-directional links such MPR selector
          table is going to change.

     2    If there exists no MPR selector tuple with:

               MS_if_addr   == Link Interface Address
          then a new tuple is created with:

               MS_if_addr   = Link Interface Address

     3    The tuple is then modified as the problem follows:

               MS_main_addr = Originator Address,

               MS_time      = current time + NEIGHB_HOLD_TIME.

   Deletion of not
   getting an acknowledgment for the data packets at each hop.

7. Protocol Functioning

   This section describes the details MPR selector tuples occurs in case of the protocol functioning.
   This includes descriptions expiration of the format and contents
   timer or in case of the
   packets being exchanged by routers, the algorithms (e.g. for
   packet handling and routing table calculation) and suggested data
   structures internally link breakage as described in each router.

7.1. Protocol the neighborhood
   and Port Number

   Packages 2-hop neighborhood changes section.

2.2.5.  Multipoint Relay Selection

   Each node in OLSR are communicated using UDP. Port 698 has been
   assigned by IANA  for exclusive usage by the OLSR protocol.

7.2. Packet Format

   OLSR communicates using an unified packet format for all data
   related to the protocol. The purpose network selects, independently, its own set of this is to facilitate
   extensibility MPRs
   among its symmetric neighborhood.  The symmetric links with MPRs are
   advertised with Link Type MPR_LINK instead of the protocol without breaking backwards
   compatibility as well as SYM_LINK in HELLO mes-
   sages.

   MPRs are used to provide an easy way of piggybacking
   different "types" of information flood control messages from that node into a single transmission. These
   packets are embedded in UDP datagrams for transmission over the
   network. The present draft uses IPv4 addresses. Support for IPv6 net-
   work while reducing the number of retransmissions that will be included occur in
   a future draft.

   Each package 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 region. Thus, the entire network, or concept of MPR is an optimization of a pure
   flooding can mechanism.

   The MPR set must be limited to nodes within calculated by a diameter (in terms node in such a way that it,
   through the neighbors in the MPR-set, can reach all symmetric 2-hop
   neighbors which are not at the same time symmetric neighbors of number the
   node.  This means that the union of hops)
   from the originator symmetric neighborhoods of
   the message. Thus, broadcasting a message
   to a MPR nodes neighborhood contains the symmetric 2-hop neighborhood. While it is just a special case of flooding. When
   flooding any control message, duplicate retransmissions will
   not essential that the MPR set is minimal, it is essential that all
   2-hop neighbors can be
   eliminated locally (i.e. each node maintains reached through the selected MPR nodes. The
   smaller a duplicate table to
   prevent transmitting MPR-set, however, the same message twice) and minimized in more optimization is achieved.

   By default, the MPR set can coincide with the entire network through symmetric neigh-
   bor set. This will be the usage case at network initialization.

   The following specifies a proposed heuristic for selection of MPRs as described
   [2] adapted for multiple interfaces support. It constructs a MPR-set
   that allows to reach any symmetric 2-hop interface (i.e. any inter-
   face of a 2-hop neighbor having a symmetric link with a neighbor).
   The following terminology will be used in section 5 describing this algorithm
   (neighbors are identified by their main address and 6.

   Furthermore, 2-hop interfaces
   by their address):

     N:   The set of neighbors with which there exists a symmetric link.

     N2:  The set made of the symmetric 2-hop interfaces excluding all
          the interfaces of members of N and the interfaces of the node can examine
          performing the header computation.

     D(y):
          Degree of one hop neighbor node y (where y is a message to obtain
   information on the distance (in terms member of N),
          defined as the number of hops) to symmetric neighbor interfaces of node
          y, EXCLUDING all the
   originator interfaces of members of N and the message. This feature may be useful in
   situations where, e.g., inter-
          faces of the time information from a recieved
   control messages is stored in a node depends on the distance to performing the originator. computation.

   The basic layout of any packet in OLSR will be proposed heuristic is as follows:

    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    Start with an empty MPR set

     2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |    Reserved for future use    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Originator Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Message Size          |  Time To Live |   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Message Type |            Message Sequence Number            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                            MESSAGE                            :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Originator Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Message Size          |  Time To Live |   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Message Type |            Message Sequence Number            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                            MESSAGE                            :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                                                               :
            (etc)

7.2.1. Packet Header

   Packet Length

      The length (in bytes)    Calculate D(y), where y is a member of the packet

   Reserved N, for future use

      MUST be set to '0000000000000000' to be all nodes in compliance with this
      version of the draft.

   The sender information for a packet is obtainable from the UDP
   header.

7.2.2. Message Header

   Originator Address

      This field contains the address of the node, N.

     3    Select as MPRs those nodes in N which has
      originally generated this message. This field SHOULD NOT be
      confused with the source address from provide the UDP header, which is
      changed each time "only path"
          to some interfaces in N2.

     4    While there exist interfaces in N2 which are not covered by
          the address of the intermediate MPR set:

          4.1  For each node which
      is "re-transmitting" this message. The Originator Address field
      MUST *NEVER* be changed in N, calculate the retransmissions.

   Message Sequence Number

      While generating number of interfaces in
               N2 which are not yet covered by the TC message, MPR set and are
               reachable through this one hop neighbor;

          4.2  Select as a MPR the "originator" node will
      assign a unique identification number from N which provides reachabil-
               ity to each message. This
      number is inserted into the Sequence Number field of the
      message. The sequence maximum number of uncovered interfaces in N2.
               In case of a tie, select that node as MPR whose D(y) is increased by 1 (one) for
               greater.

     5    As an optimization, process each
      message originating from the node - "wrap-arounds" are handled
      as described y in section 10.

   Message Size

      This field gives the size of this message, measured from MPR set. If the
      beginning of
          MPR set excluding y still covers all interfaces in N2, node y
          is removed from the "Message Type" field and until MPR set.

   When the beginning
      of MPR set has been computed, all the next "Message Type" field (or - if there corresponding main
   addresses are no
      following messages - the end of stored in the packet).

   Message Type

      This field indicates which type of message MPR Set.

   Some processing such as MPR set re-calculation should occur when
   changes are to be found detected in the "MESSAGE" partition. Message types in neighborhood or the range of 0-127 are
      reserved for messages in this draft 2-hop neighborhood.

2.2.5.1.  Neighborhood and 2-hop Neighborhood Changes

   A change in
      draft-ietf-manet-olsr-extensions-00.txt.

   Time To Live

      This field contains the maximum number neighborhood is detected when:

     -    The N_SYM_time field of hops a message will
      be retransmitted. Before a message neighbor tuple expires. This is transmitted, con-
          sidered as a neighbor loss if it was the Time To
      Live MUST be decremented by 1. When last link with a
          neighbor node receives (on the contrary, a message link with an interface may
          break while a Time To Live equal to 0, the message MUST NOT be
      retransmitted under any circumstances.

      Thus, by setting this field, the originator link with another interface of a message can
      limit the flooding radius.

   Hop Count

      This neighbor node
          is still alive).

     -    The N_ASYM_time field will contain the number of hops a message has
      attained. Before a message neighbor tuple expires and
          N_SYM_time is (re-) transmitted, the Hop Count
      MUST be incremented by 1.

      Initially, this expired. The link is set to '0' by the originator of the message.

   Reserved

      This field then considered lost.

     -    A new neighbor tuple is reserved for future usage, and MUST be set to
      '00000000' for compliance inserted in the Neighbor Set with this draft.

7.2.3. Packet Processing

   Upon receiving a basic packet, the protocol parser examines each
   of the "message headers". Based on the value of the "Message Type"
   field, the parser can determine the faith of the message. A node
   may receive the same message in several packets.
          valid N_SYM_time or a tuple with expired N_SYM_time is modi-
          fied so that N_SYM_time becomes valid. This can happen
   only if the message is retransmitted by two nodes in considered as a
          neighbor appearance if there was previously no link with the receivers
   neighborhood, i.e.
          corresponding neighbor node.

   A change in the "Time To Live" and 2-hop neighborhood is detected when a 2-hop neighbor
   tuple expires or is deleted according to the "Hop Count" fields HELLO message processing
   section.

   The following processing should occur when changes in the message satisfies neighbor-
   hood or the following condition:

       Time To Live + Hop Count > 1

   Thus, to avoid re-processing of a message which was already
   received and processed, each node maintains a Duplicate table. 2-hop neighborhood are detected:

     -    In
   this table, case of neighbor loss, all the node records information about 2-hop tuples with
          N_main_addr == Main Address of the most recently
   received messages where neighbor are deleted.

     -    In case of neighbor loss, all the above condition holds. For each
   message, satisfying MPR selector tuples with
          MS_main_addr == Main Address of the above condition, a node records neighbor are deleted

     -    The MPR set is re-calculated when a
   "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr neighbor appearance or
          loss is detected, or when a change in the
   originator address of the message, D_seq_num 2-hop neighborhood
          is the message
   sequence number of the detected.

     -    An additional HELLO message and D_time specifies the time at
   which a tuple expires and *MUST* may be removed.

   In a node, sent when the MPR set
          changes.

2.2.6.  Advanced Neighbor Sensing Functioning

   Established links should be as reliable as possible to avoid data
   packet loss. To enhance the reliability of Duplicate Tuples are denoted the "Duplicate
   set".

   Thus, upon receiving a basic packet, a node performs neighbor sensing mech-
   anism, the following
   tasks for each encapsulated message:

      1. If there exists a implementation recomendations should be consid-
   ered.

   Each neighbor 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 neighbor set SHOULD, in addition to what
   is described in section 2.2.2.1, include a N_pending field, a N_qual-
   ity field, and MUST silently be ignored.

      2. Otherwise, a N_LOST_time.  N_pending is a boolean value specify-
   ing if the Message Type of the message link is known to
         the node, considered pending (i.e. the message MUST be processed according to link is not consid-
   ered established). N_quality is a dimensionless number between 0 and
   1 describing the
	 specifications quality of such the link. N_LOST_time is a timer for
   declaring a link as lost when an established link becomes pending.

   HELLO message type.

      3. Otherwise, generation should consider those new fields as follows.

     1    If N_LOST_time is not expired, the Message Type link is advertised with a
          link type of the message LOST_LINK;

     2    otherwise, if N_LOST_time is not known expired and N_pending is set to
          "true", the node, the message MUST link SHOULD NOT be processed according advertised at all;

     3    otherwise, if N_LOST_time is expired and N_pending is set to
          "false", the
	 following algorithm:

	 3.1 If the sender of link is advertised as described in the message HELLO mes-
          sage generation section.

   A node considers it has a symmetric link for each neighbor tuple such
   that N_LOST_time is expired, N_pending is "false" and N_SYM_time is
   not in expired. This should be taken as definition for computing the
   symmetric neighborhood when computing the MPR selector
	     set of set.

   Apart from the node, above points, what has been previously describe do not
   interfere with this newly introduced fields. The N_quality, N_pending
   and N_LOST_time fields are updated according to the message MUST silently be dropped.

	 3.2 If present section
   and nowhere else. The other fields are not modified by the time advanced
   neighbor sensing functioning.

   This advanced functioning is described as separately as possible to live
   increase readability.

2.2.6.1.  Link Hysteresis

   The link between a node and some of the message is less than or equal its neighbor interfaces might be
   "bad", i.e. from time to '0' (zero), time let HELLOs pass through only to fade
   out immediately after. In this case, the neighbor information base
   would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of
   link layer notification, such a bad link would spoil routing. To cope
   with such unstable links, the message MUST silently following hysteresis strategy SHOULD be dropped.

	 3.3 Otherwise, if
   adopted.

   For each neighbor interface NI heard by interface I, the sender N_quality
   field of the message is an MPR
	     selector of this node and if corresponding Neighbor Tuple determines the time to live establish-
   ment of the
	     message link.  Its value is greater than '0' (zero), the message MUST be
	     forwarded according to the following algorithm:

	     3.3.1 The time compared to live of two thresholds
   HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW which are fixed between 0 and
   1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. When
   N_quality becomes higher than HYST_THRESHOLD_HIGH, the message N_pending
   field is reduced by one.

	     3.3.2 The hop-count of set to false. When N_quality goes below HYST_THRESHOLD_LOW,
   the message N_pending field is increased by one

	     3.3.3 An entry in the duplicate set to true and N_LOST_time is recorded with:

		      D_addr = originator address

		      D_seq_num = Message Sequence Number

		      D_time = set to min
   (N_time, current time + D_HOLD_TIME.

	     3.3.4 The message NEIGHB_HOLD_TIME) (the link is retransmitted (Notice: The
		   remaining fields of then consid-
   ered as lost according to the message header SHOULD
		   be left unmodified.)

   Notice: known message types are *not* forwarded "blindly" by Neighborhood and 2-hop neighborhood
   changes section and this
   algorithm. Forwarding (and setting the correct message header in
   the forwarded, known, message) may produce a neighbor loss). The condition
   for considering a link established is thus stricter than the responsibility of the
   algorithm specifying how the message is to be handled. This
   enables, e.g., condi-
   tion for loosing it.

   As a message type to be specified such that basic implementation requirement, an estimation of the
   message can link
   quality must be modified while maintained and stored in transit (e.g. to reflect the
   route the message has taken). Further, it enables that the
   optimization through the MPRs can be bypassed: if for N_quality field. If some reason
   pure flooding
   measure of the signal/noise level on a received message type is required available
   (e.g. to transmit
   control as a link layer notification), then it can be used as estima-
   tion after normalization.

   If no signal/noise information over unidirectional links), is available from the link layer, an
   algorithm
   specifying handling of these messages will simply rebroadcast such the message, regardless of MPR selectors.

   Finally, notice that following can be utilized. The algorithm is
   parametrized by a message, scaling parameter HYST_SCALING which is to be broadcast in the
   neighborhood, but not flooded into the entire network, (e.g. a
   HELLO-message) is simply specified by setting number
   fixed between 0 and 1. For each neighbor interface NI heard by inter-
   face I, the first time NI is heard by I, N_quality is set to live to
   '0' (zero), and that no duplicate entries are recorded for such
   messages.

   By defining a
   HYST_SCALING (and N_pending is set of to true).

   A tuple is updated according to two rules.  Every time an OLSR mes-
   sage emitted by NI is received by I, the stability rule is applied:

          N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING.

     When an OLSR message types, which MUST be recognized emitted by all
   implementations NI is lost by I, the instability
     rule is applied:

          N_quality = (1-HYST_SCALING)*N_quality.

   The loss of OLSR, it will be possible to extend OLSR messages is detected by tracking the protocol
   through introduction missing Message
   Sequence Numbers and by long period of additional message types, while still be
   able to maintain compatibility with older implementations. The two
   REQUIRED silence. If no HELLO message types
   has been received for OLSR are:

        - HELLO-messages, performing the task a HELLO_INTERVAL period, a loss of neighbor sensing.
        - TC-messages, performing HELLO mes-
   sage is detected.

2.2.6.2.  Optional Link layer notification

   OLSR is designed not to impose or expect any specific information
   from the task of MPR link layer. However, if information declaration.

   Extensions may e.g. be PC-messages for enabling power conservation
   / sleep mode, multicast routing, gateway announcements,
   auto-configuration/address assignment etc.

7.3. Neighbor sensing

7.3.1. Neighbor sensing from the link-layer is
   available, a node MAY use this as described in this section.

   If link layer information base

7.3.1.1 Neighbor describing connectivity to neighboring
   nodes is available (i.e. loss of connectivity such as through absence
   of a link layer acknowledgment), this information

   A node maintains is used in addition
   to the information (obtained from the HELLO messages)
   about its one hop neighbors, HELLO-messages to maintain the status of neighbor
   information base and the link with these
   neighbors, MPR selector set.

   Thus, upon receiving a list of 2-hop neighbors link-layer notification that these one hop neighbors
   give access to, and an associated holding time.

   Thus, for each neighbor, the link between
   a node records and a "Neighbor Tuple"
   (N_addr, N_status, N_time) where N_addr neighbor interface is broken, the address of the
   neighbor, N_status designates the status of following actions are
   taken:

     1    if the link with that is broken to either a symmetric or asymmetric
          neighbor (MPR, symmetric, heard) interface, the corresponding neighbor tuple is modi-
          fied: N_LOST_time and N_time specifies the are set to current time at
   which +
          NEIGHB_HOLD_TIME.

     2    this record expires is considred as a link loss and *MUST* the appropriate process-
          ing described in the neighborhood and 2-hop neighborhood
          changes section should be removed.

   Likewise, a performed.

2.3.  Topology Discovery

   The Neighbor Sensing part of the protocol basically offers to each
   node records a set list of "2-hop tuples" (N_addr,
   N_2hop_addr, N_time), describing symmetric or MPR links between
   its neighbors with which it can communicate directly and the 2-hop neighborhood. N_addr is the address of
   a neighbor, N_2hop_addr
   an optimized flooding mechanism through MPRs. Based on this mecha-
   nism, topology information is disseminated through the address network. The
   present section describes what part of a 2-hop neighbor and
   N_time specifies the time at which a tuple expires and *MUST*
   be removed.

   In a node, information given by the set of
   Neighbor Tuples are denoted the "Neighbor
   Set" Sensing is disseminated and the set of 2-hop tuples how it is used to construct
   routes.

   Routes are denoted constructed through MPR-links and links with neighbors. A
   node thus basically disseminates its MPR-selector set. If a node has
   multiple interfaces, it must also disseminate the "2-hop neighbor
   set".

7.3.1.2 MPR Selector information

   A list of its inter-
   face addresses.

2.3.1.  Multipoint Relay Information Declaration

2.3.1.1.  Topology Information Base

   Each node in the network maintains topological information (obtained from the HELLO messages) about the neighbors which have selected the node as a MPR.
   network. This information is acquired from TC-messages and is used
   for routing table calculations.

   Thus, a node records a MPR-selector tuple (MS_addr, MS_time), for each neighbor which has selected destination in the node as MPR. MS_addr network, a "Topology Tuple"
   (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main
   address of a node node, which has selected may be reached in one hop from the node as MPR, with
   the main address T_last. Typically, T_last is a MPR of T_dest. T_seq
   is a sequence number, and MS_time T_time specifies the time at which a this
   tuple expires and *MUST* be removed.

   In a node, the set of MPR-tuples Topology Tuples are denoted the "MPR selector
   set" A sequence number, MSSN, is associated with this
   set. Whenever a tuple is added or removed to this set, the MSSN is
   incremented by 1.

7.3.2. HELLO message broadcast

   Each node should detect the neighbor nodes with which it has a direct
   and symmetric link. The uncertainties over radio propagation may
   make some links asymmetric. Consequently, all links MUST be checked
   in both directions in "Topology Set".

2.3.1.2.  TC Message Generation

   In order to be considered valid.

   To accomplish this, each node broadcasts HELLO messages,
   containing information about neighbors and their link status. The
   link status may either be "symmetric", "heard" (asymmetric) or
   "MPR".  "Symmetric" indicates, that the link has been verified to
   be bi-directional, i.e. it is possible to transmit data in both
   directions. "Heard" indicates that the node can hear HELLO
   messages from a neighbor, but it is not confirmed that this
   neighbor is also able to receive messages from build the node. "MPR"
   indicates, that a node is topology information base needed, each node,
   which has been selected by the sender as a MPR. A
   status of MPR further implies that the link is symmetric.

   These control MPR, broadcasts Topology Control (TC) mes-
   sages. TC messages are broadcast flooded to all one-hop neighbors, but
   are *not relayed* to further nodes. A HELLO-message contains:

      - a list of addresses nodes in the network and take
   advantage of neighbors, to which there exists a
        symmetric link;

      - MPRs. MPRs enable a list of addresses better scalability in the distribu-
   tion of neighbors, which have been "heard";

      - topology information [1].

   A TC message is sent by a node in the network to declare its MPR
   Selector set. I.e., the TC message contains the list of neighbors, neighbors
   which have been selected the sender node as MPRs. a MPR. The sequence number
   (MSSN) associated with this MPR selector set is also sent with the
   list. The list of neighbors in a HELLO message addresses can be partial in each TC message (e.g.
   due to message size limitations, imposed by the network), the rule
   being that but parsing
   of all neighbor nodes are cited at least once TC messages describing the MPR selector set of a node MUST be
   complete within a
   predetermined certain refreshing period (HELLO_INTERVAL).

   To accommodate for (TC_INTERVAL). The infor-
   mation diffused in the above constraints, as well network by these TC messages will help each
   node calculate its routing table. A node which has an empty MPR
   selector set, i.e. nobody has selected it as a MPR, SHOULD NOT gener-
   ate any TC message.

   A node MAY transmit additional TC-messages to accommodate
   for future extensions, an approach similar increase its reactive-
   ness to link failures. I.e. when a change to the overall packet
   format (see section 6.1) MPR selector set is taken. Thus the
   detected and this change can be attributed to a link failure, a TC-
   message SHOULD be transmitted after a shorter interval than TC_INTER-
   VAL.

   The proposed format of a
   HELLO TC message is: is

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Link Type              MSSN             |           Reserved            |       Link Message Size       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Neighbor             Multipoint Relay Selector Main Address            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                             . . .                             :
   :                                                               :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Link Type   |   Reserved    |       Link Message Size       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Neighbor             Multipoint Relay Selector Main Address            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Neighbor Address                              ...                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                                                               :
   :								   :
			         (etc)
   This is sent as the data-portion of the general packet message format
   described in 6.1, with
   the "Message Type" set to HELLO_MESSAGE and
   the TTL field TC_MESSAGE.  The time to live SHOULD be set
   to 0.

7.3.2.1. 255 (maximum value) to diffuse the message into the entire net-
   work.

Description of the fields fields

     MPR Selector Sequence Number (MSSN)

          A sequence number is associated with the MPR selector set.
          Every time a node detects a change in its MPR selector set, it
          increments this sequence number. This number is sent in this
          MSSN field of the TC message to keep track of the most recent
          information. When a node receives a TC message, it can decide
          on the basis of this MPR Sequence Number, whether or not the
          received information about the MPR selectors of the originator
          node is more recent than what it already has.

     Multipoint Relay Selector Main Address

          This field contains the main address of a node, which has
          selected the Originator node (of the TC message) as a MPR.
          All addresses of the MPR selectors of the Originator node are
          put in the TC message. If the maximum allowed message size (as
          imposed by the network) is reached while there are still MPR
          selector addresses which which have not been inserted into the
          TC-message, more TC messages will be generated until the
          entire MPR Sequence Number selector set has been sent.

     Reserved

          This field indicates is reserved for future usage, and MUST be set to
          "0000000000000000" for compliance with this draft.

2.3.1.3.  TC Message Processing

   TC messages are broadcasted and retransmitted by the sequence number corresponding MPRs in order to
   diffuse the
      most recent MPR set, calculated by messages in the sender node.

   Link Message Size

      The size of entire network.

   In this section, the link message, measured term "originator" is used to designate the node
   from which the beginning of message originally originated, while the "Link Type" field and until term "sender"
   is used to designate the next "Link Type" field (or
      - if there are no more link types - node from which the end message was received
   (i.e. the "last hop" of the message).

   Link Type

      This field specifies

   The tuples in the type of link topology set are recorded with the sending node has topology infor-
   mation that is exchanged through TC messages, according to the
   following list of neighbors. As a minimum, algorithm:

     1    If the following
      three link types are REQUIRED by OLSR:

	   - ASYM_LINK - indicating that sender interface (NB: not originator) of this message
          is not in the links between symmetric neighborhood of this node, the sender
	     and message
          is discarded.

     2    A tuple is inserted into the neighbors duplicate table to prevent it
          from being processed again with:

               D_addr = originator address

               D_seq_num = Message Sequence

               D_time = current time + D_HOLD_TIME.

     3    If there exist some tuple in the following list are asymmetric
	     (i.e. the neighbor topology set where:

               T_last == originator address AND

               T_seq > MSSN,

          then no further processing of this TC message is "heard").

	   - SYM_LINK - indicating that the links between the sender performed and
          the neighbors message is silently discarded (case: message received out
          of order).

     4    All tuples in the following list topology set where:

               T_last == originator address AND

               T_seq < MSSN

          are symmetric.

	   - MPR_LINK - indicating, that the nodes in the following
	     list have been selected by the sender as MPR.
	     (Notice: this implies, that the links removed from the sender topology set.

     5    For each of the HELLO and to the nodes MPR selector address received in the list are symmetric).

      It is possible to provide additional information by specifying
      additional link-types, e.g. LOST_LINK - indicating that the link
      between the sender and the neighbors TC mes-
          sage:

          5.1  If there exist some tuple in the following list has
      been lost. Upon processing a HELLO message, a node silently
      ignores link-types, which are unknown.

   Reserved

      This field is reserved for future usage, and MUST be topology set to
      000000000000000000000000 for compliance with this draft.

   Neighbor Address

      The address where:

                    T_dest == MPR selector address, AND

                    T_last == originator address,

               then the holding time of that tuple is set to:

                    T_time = current time + TOP_HOLD_TIME.

          5.2  Otherwise, a neighbor.

7.3.3.  HELLO message processing

   Upon receiving a HELLO message, the node SHOULD update the
   neighbor information corresponding to the sender node address (a
   node may - e.g. for security reasons - wish to restrict updating new tuple is recorded in the neighbor-table, i.e. ignoring HELLO messages from some nodes).

   In this section, topology set
               where:

                    T_dest = MPR selector address,

                    T_last = originator address,

                    T_seq  = MSSN,

                    T_time = current time + TOP_HOLD_TIME.

     6    If the term "Originator Address" will be used for sender address is the link interface address of the node which sent the HELLO-message.

      1. If there exists a neighbor tuple with N_addr = Originator
         Address:

	 1.1 if for that tuple N_status == ASYM_LINK:

	     1.1.1 MPR
          selector of this node and if the node finds its own address among time to live of the
	           addresses listed in message
          is greater than '1', the HELLO message (with Link
	           Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates MUST be forwarded according
          to the N_status following:

          6.1  The TTL of the tuple to SYM_LINK and sets
		   N_time = current time + NEIGHB_HOLDING_TIME.

	     1.1.2 otherwise, if message is reduced by one.

          6.2  The hop-count of the message is increased by one

          6.3  The message is broadcasted on all interfaces (Notice: The
               remaining fields of the message header SHOULD be left
               unmodified.)

2.3.2.  Multiple Interface Association

Each node does not find its own
	           address among in the addresses listed network maintains interface information about the other
nodes in the HELLO
		   message, it sets N_time = current time +
		   NEIGHB_HOLDING_TIME.

         1.2 otherwise, if network. This information acquired from MID-messages, emit-
ted by nodes with multiple interfaces participating in the MANET, and is
used for that tuple:

	     N_status == SYM_LINK OR
	     N_status == MPR_LINK

	     then:

	     1.2.1 if routing table calculations.

2.3.2.1.  Interface Association Information Base

   For each destination in the node finds its own network, "Interface association Tuples"
   (I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter-
   face address among of a node, I_main_addr is the addresses
                   listed in main address of this node.
   I_time specifies the HELLO message (with Link Type
                   ASYM_LINK, SYM_LINK or MPR_LINK), it sets N_time =
                   current time NEIGHB_HOLDING_TIME.

      2. Otherwise, a new neighbor at which this tuple is created with:

           N_addr = Originator Address

           N_status with expires and *MUST* be
   removed.

   In a node, the value set of SYM_LINK if Interface association Tuples is denoted the
   "Interface association Set".

2.3.2.2.  MID Message Broadcast

   In order to build the interface association information base, each
   node with multiple interfaces broadcast Multiple Interface Declara-
   tion (MID) messages. MID messages are flooded to all nodes in the
   network and take advantage of MPRs.

   A MID message is sent by a node
           finds in the network to declare its own address (with Link Type ASYM_LINK, SYM_LINK
           or MPR_LINK) among multi-
   ple interfaces (if any). I.e., the MID message contains the list of
   interface addresses listed which are associated to its main address.  The
   list of addresses can be partial in the HELLO
           message, and each TC message (e.g. due to mes-
   sage size limitations, imposed by the value network), but parsing of ASYM_LINK otherwise

	   N_time = current time + NEIGHB_HOLD_TIME

   The 2-hop neighbor all
   MID messages describing a nodes interface set is updated as follows: for each 2-hop
   neighbor address listed MUST be complete within
   a certain refreshing period (MID_INTERVAL). The information diffused
   in the HELLO message with Link Type
   SYM_LINK or MPR_LINK:

      1. if network by these MID messages will help each node to calculate
   its routing table. A node which has only a 2-hop tuple exists with:

            N_addr == Originator Address AND
	    N_2hop_address == the single interface address of
   participating in the 2-hop neighbor,

	 then MANET (i.e. running OLSR), MUST NOT generate any
   MID message.

   A node with more interfaces, where only one is participating in the N_time of that tuple
   MANET and running OLSR (e.g. a node is set to:

	    N_time = current time + NEIGHB_HOLD_TIME

      2. otherwise connected to a new 2-hop tuple wired network
   as well as to a MANET) MUST NOT generate any MID messages.

   The proposed format of a MID message is created with:

	    N_addr = Originator Address,

	    N_2hop_address =

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Interface Address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Interface Address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                              ...                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the address data-portion of the 2-hop neighbor,

	    N_time = current time + NEIGHB_HOLD_TIME.

   Based on the information obtained from the HELLO messages, each
   node construct its MPR selector set.

   Thus, upon receiving a HELLO message, if a node finds its own
   address in the address list general message format with a link type of "MPR", it MUST
   update
   the MPR selector "Message Type" set to contain updated information about
   the sender of the HELLO message:

      1. If a MPR selector tuple exists with:

	    MS_addr == Originator Address

	 then the expiration MID_MESSAGE.  The time of that tuple is to live SHOULD be
   set to:

	     MS_time = current time + NEIGHB_HOLD_TIME.

      2. Otherwise, a new MPR selector tuple is created with:

             MS_addr = Originator Address

             MS_time = current time + NEIGHB_HOLD_TIME

	 2.1 MSSN is incremented by one to indicate that the MPR
	     selector table has been changed.

   If link layer information describing connectivity 255 (maximum value) to neighboring
   nodes is available (i.e. loss diffuse the message into the entire
   network.

Description of connectivity such as through
   absence the fields

     Interface Address
          This field contains the address of an acknowledgment), this MAY be used in addition to interface of the information from node
          other than its main address (already indicated in the HELLO-messages to maintain origina-
          tor address).  All interface addresses other than the neighbor
   table and main
          address of the MPR selector table as described in section 7.7.

7.4. Multipoint relay selection

   Each Originator node are put in the network selects independently its own set of
   MPRs. MPRs MID message. If
          the maximum allowed message size (as imposed by the network)
          is reached while there are used to flood control messages from that node still interface addresses which
          have not been inserted into the network while reducing the number of retransmissions that will
   occur in a region. Thus, MID-message, more MID messages
          are generated until the concept of MPRs is an optimization
   of a pure flooding mechanism.

   The MPR entire interface addresses set must be calculated has
          been sent.

2.3.2.3.  MID Message Processing

   MID messages are broadcasted and retransmitted by a node the MPRs in a way such that it,
   through order
   to diffuse the neighbors messages in the MPR-set, can reach all 2-hop
   neighbors. This means that entire network.

   In this section, the union of term "originator" is used to designate the neighbor sets node
   from which the MPR
   nodes contains message originally originated, while the entire 2-hop neighbor set. While it term "sender"
   is not
   essential that used to designate the MPR set is minimal, it is essential that all
   2-hop neighbors can be reached through node from which the selected MPR nodes. The
   smaller a MPR-set, however, message was received
   (i.e. the more optimizations are achieved.

   By default, "last hop" of the MPR message).

   The tuples in the multiple interface association set can coincide are recorded
   with the entire neighbor
   set. This will be information that is exchanged through MID messages, follow-
   ing the case at network initialization.

   The following specifies a proposed heuristic for selection of MPRs
   [2]. The following terminology will be used in describing this algorithm:

      N:      The net

     1    If the sender (NB: not originator) of neighbors with which there exists a this message is not in
          the symmetric link.

      N2:     The set neighborhood of this node, the message is dis-
          carded.

     2    A tuple is inserted into the duplicate table to prevent it
          from being processed again with:

               D_addr = originator address

               D_seq_num = Message Sequence

               D_time = current time + D_HOLD_TIME.

     3    For each of 2-hop neighbors. This the interface address received in the MID message:

          3.1  If there exist some tuple in the interface association
               set does not contain
	      any one hop neighbors.

      D(y):   Degree where:

                    I_if_addr == interface address, AND
                    I_main_addr == originator address,

               then the holding time of one hop neighbor node y (where y that tuple is set to:

                    I_time = current time + MID_HOLD_TIME.

          3.2  Otherwise, a member
              of N), new tuple is defined as recorded in the number interface asso-
               ciation set where:

                    I_if_addr = interface address,

                    I_main_addr = originator address,

                    I_time = current time + MID_HOLD_TIME.

     4    If the sender address is the link interface address of symmetric one hop
              neighbors a MPR
          selector of this node y, EXCLUDING and if the node performing time to live of the
	      computation and all its direct neighbors.

   The proposed heuristic is as follows:

      1. Start with an empty MPR set
      2. Calculate D(y), where y message
          is a member of N, for all nodes
         in N.
      3. Select as MPRs those nodes in N which provide greater than '1', the
         "only path" message MUST be forwarded according
          to some nodes in N2
      4. While there exist nodes in N2 which are not covered by MPR: the following:

          4.1 For each node in N, calculate  The TTL of the number message is reduced by one.

          4.2  The hop-count of nodes in
             N2 which are not yet covered the message is increased by MPR and are
             reachable through this one hop neighbor;
         4.2 Select as a MPR that

          4.3  The message is broadcasted on all interfaces (Notice: The
               remaining fields of the message header SHOULD be left
               unmodified.)

2.3.3.  Associated Networks and Hosts

   A node MAY provide access to a set of N which reaches associated hosts. I.e., a node
   may act as a "gateway" between the
             maximum MANET and a number of uncovered nodes associated
   hosts and/or subnets, not running OLSR and thus not participating in N2. In case of
   the MANET. Thus, a
             tie, select that node SHOULD be able to inject routing information
   describing these associated hosts or networks into MANET, as MPR whose D(y) is greater.

      5. As an optimization, process each node y in MPR.
         If MPR\{y} still covers SHOULD
   all nodes in N2, Y SHOULD be
	 removed from the MPR set.

   After selecting the MPRs among the neighbors, the link status capable of
   the corresponding one hop neighbors interpreting such information.

   Notice, that this is changed a different case from SYM_LINK to
   MPR_LINK that of "multiple inter-
   faces", described previously. Where, in the neighbor table. MPR_Seq_Num value in "Multiple Interface Asso-
   ciations", all the Neighbor
   table is also incremented by one.
   The MPR set is re-calculated when:

      - a change described interfaces were participating in the neighborhood is detected, i.e. either a
        symmetric link with
   MANET through running the OLSR protocol, this section addresses the
   interfaces which do not participate. This is, e.g., the case where a neighbor is failed, or
   node has both a new neighbor
        with wireless interface (participating in the MANET) and a symmetric link is added; or
      -
   wired interface, through which a change is detected number of hosts statically connect
   (to the nodes in the 2-hop neighborhood such that
        a symmetric link is either detected or broken between MANET).

   To accomplish this, a
	2-hop neighbor node, to which there are associated hosts
   and/or networks, periodically issues an Host and a neighbor.

7.5. Multipoint relay information declaration

7.5.1 Topology Network Association
   (HNA) message, containing sufficient information base for the recipients
   to construct an appropriate routing table.

2.3.3.1.  Host and Network Association Information Base

   Each node in the network maintains topological information about
   the network. This information is acquired from TC-messages and
   used for routing table calculations.

   Thus, for each destination in the network, a "Topology Tuple"
   (T_dest, T_last, T_seq, T_time) is recorded. T_dest concerning which nodes may act as
   "gateways" to associated hosts and networks by recording "association
   tuples" (GW_main_addr, NET_addr, NET_mask, GS_time), where
   GW_main_addr is the main address of a node, which may be reached in one hop from the node with gateway, NET_addr and
   NET_mask specifies the network address T_last. T_seq is and netmask of a sequence number, network,
   reachable through this gateway, and T_time GS_time specifies the time at
   which this tuple expires and hence *MUST* be removed.

   In a node, the

   The set of Topology Tuples are denoted the "Topology
   Set".

7.5.2. TC Message Broadcast

   In order to build the topology information base needed, each node,
   which has been selected as MPR, broadcasts Topology Control (TC)
   messages. TC messages are flooded to all nodes in the network and
   take advantage of MPRs. MPRs enable a better scalability association tuples in the
   distribution of topology information [1].

   A TC message is sent by a node in the network to declare its MPR
   Selector set. I.e., the TC message contains the list of neighbors
   which have selected the sender node as a MPR. The sequence number
   (MSSN) associated with this MPR selector set is also sent with the
   list. The list of addresses can be partial in each TC message
   (e.g. due to message size limitations, imposed by the network),
   but parsing of all TC messages describing a nodes MPR selector set
   MUST be complete within a certain refreshing period
   (TC_INTERVAL). The information diffused in called the network by these TC
   messages will help each node to calculate its routing table. A
   node which has an empty MPR selector set, i.e. nobody has selected
   it as a MPR, MUST NOT generate any TC message. "associa-
   tion set".

2.3.3.2.  Host and Network Association Message Broadcast

  A node MAY transmit additional TC-messages to increase its
   reactiveness to link failures. I.e. when with associated hosts and/or networks SHOULD periodically gen-
  erate a change Host and Network Association (HNA) message, containing pairs
  of (network address, netmask) corresponding to the MPR
   selector set is detected connected hosts and this change can be attributed to a
   link failure, a TC-message
  networks. HNA-messages SHOULD be transmitted after a shorter
   interval than TC_INTERVAL. periodically every
  HNA_INTERVAL.

  A node without any associated hosts and/or networks SHOULD NOT gener-
  ate HNA-messages.

  The proposed format of a TC message is an HNA-message is:

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |              MSSN                         Network Address                       |           Reserved
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                             Netmask                           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |               Multipoint Relay Selector                         Network Address                       |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |               Multipoint Relay Selector Address                             Netmask                           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                              ...                              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data-portion data part of the general message packet format
   described in 6.1, with the
   "Message Type" set to TC_MESSAGE.  The
   time to live SHOULD be set to 255 (maximum value) to diffuse the
   message into the entire network.

7.5.2.1. Description of the fields

   MPR Selector Sequence Number (MSSN)

      A sequence number is associated with HNA and the MPR selector
      set. Every time a node detects a change in its MPR selector
      set, it increments this sequence number. This number is sent in
      this MSSN TTL field of the TC message set to keep track of 255.

   It should be noticed, that the most
      recent information. When a node receives a TC message, it HNA-message can
      decide on the basis of this MPR Sequence Number, whether or not
      the received information about the MPR selectors of the
      originator node is more recent than what it already has.

   Multipoint Relay Selector Address (MPR-S)

      This field contains the address of a node, which has selected
      the Originator node (of the TC message) be considered as a MPR.  All
      addresses of the MPR selectors of the Originator node are put
      in the TC message. If the maximum allowed message size (as
      imposed by the network) is reached while there are still MPR
      selector addresses which which have not been inserted into a
   "generalized version" of the
      TC-message, more TC-message: the originator of both the
   HNA and TC messages will be generated until announce "reachability" to some other host(s). In
   the entire
      MPR selector set has been sent.

   Reserved

      This field TC-message, no netmask is reserved for future usage, and MUST be set required, since all reachability is
   announced on a per-host basis. In HNA-messages, announcing reachabil-
   ity to
      '0000000000000000' for compliance with this draft.

7.5.3. TC Message Processing

   TC messages are broadcasted an address sequence through a network- and retransmitted by the MPRs in order netmask address is
   typically preferred over announcing reachability to diffuse individual host
   addresses.

Description of the messages in fields

     Network Address

          The network address of the entire network. associated network

     Netmask

          The netmask, corresponding to the network address immediately
          above.

2.3.3.3.  HNA Message Processing

   In this section, the term "originator" "originator address" is used to designate
   the main address of the node from which the message originally originated, while issued the term
   "sender" is used to designate HNA-message.

   Upon receiving a HNA-message, the node from which the message was
   received (i.e. the "last hop" of performs the message).

   The tuples following:

     1    An entry in the topology duplicate set are recorded with the topology
   information that is exchanged through TC messages, following the
   following algorithm:

      1. If the sender (NB: not originator) of this message is not in
         the neighbor set of recorded for this node, the message is discarded.

      2. A tuple is inserted into the duplicate table to prevent
	 being processed again
          with:

               D_addr = originator address

               D_seq_num = Message Sequence

	   D_time = current time + D_HOLD_TIME.

      3. If there exist some tuple in the topology set where:

	   T_last == originator address AND
	   T_seq > MSSN,

	 then no further processing of this TC message is performed
	 and the message is silently discarded (case: message
	 received out of order).

      4. All tuples in the topology set where:

	    T_last == originator address AND
	    T_seq < MSSN

	 are removed from the topology set.

      5. Number

               D_time = current time + D_HOLD_TIME.

     2    For each of the MPR selector address received (network address, netmask) pair in the TC message:

         5.1 If there exist some tuple

          2.1  if an entry in the topology association set already exists, where:

                T_dest == MPR selector address, AND
                T_last

                    GW_main_addr  == originator address, address

                    NET_addr == network address
                    NET_mask == netmask

               then the holding time of for that tuple is set to:

	        T_time

                    GW_time = current time + TOP_HOLD_TIME.

         5.2 Otherwise, GW_HOLDING_TIME

          2.2  otherwise, a new tuple is recorded in the topology set
	     where:

                T_dest = MPR selector address,

                T_last = with:

                    GW_main_addr  == originator address,

                T_seq  = MSSN,

                T_time address

                    NET_addr == network address

                    NET_mask == netmask

                    GW_time = current time + TOP_HOLD_TIME.

7.6. GW_HOLDING_TIME

     3    If the sender address is the link interface address of a MPR
          selector of this node and if the time to live of the message
          is greater than '1', the message MUST be forwarded according
          to the following:

          3.1  The TTL of the message is reduced by one.

          3.2  The hop-count of the message is increased by one

          3.3  The message is broadcasted on all interfaces (Notice: The
               remaining fields of the message header SHOULD be left
               unmodified.)

2.3.3.4.  Optional Link layer notification

   Detection of a link failure between a node and one of its MPR selec-
   tors through a link-layer notification may trigger additional TC-mes-
   sages to increase the protocols reactiveness to link failures. I.e.
   when a change to the MPR selector set is detected and this change can
   be attributed to a link failure, an additional TC-message SHOULD be
   transmitted.

   Thus, if a link failure appears to be a neighbor loss with a neigh-
   bor, which has selected this node as MPR, the MPR selector set is
   updated (MSSN is thus incremented) and a TC message SHOULD be gener-
   ated.

2.3.4.  Routing table calculation Table Calculation

   Each node maintains a routing table which allows it to route the
   messages data,
   destined for the other destinations nodes in the network. The routing table is
   based on the information contained in the neighbor sensing informa-
   tion base, the interface association set and the topology set. Therefore, There-
   fore, if any of these tables is are changed, the routing table is re-calculated re-
   calculated to update the route information about each destination in
   the network. The route entries are recorded in the routing table in
   the following format:

         1.  R_dest    R_next    R_dist   R_if_id
         2.  R_dest    R_next    R_dist   R_if_id
         3.    ,,        ,,        ,,

   Each entry in the table consists of R_dest, R_next and R_next, R_dist, and
   R_if_id which specifies that the node identified by R_dest is estimated esti-
   mated to be R_dist hops away from the local node, and that the one hop sym-
   metric neighbor node with interface address R_next is the next hop
   node in the route to R_dest. R_dest, and this one hop is reachable through
   the local interface
    R_if_id.  Entries are recorded in the table for each destination in
   the network for which the route is known. All the destinations for
   which the route is broken or partially known are not entered in the
   table.

   This routing table is updated when a change is detected in the neighbor set, neigh-
   bor information base, or the topology set. More precisely, it is re-
   calculated in case of neighbor appearance or loss, or when a topology
   tuple is created or removed.  The update of this routing information
   does not generate or trigger any messages to be transmitted, neither
   in the network, nor in the one-hop neighborhood.

   To construct the routing table of node X, a shortest path algorithm
   is run on the directed graph containing the arcs X -> Y where Y is
   any one hop symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and
   the arcs U -> V where there exists an entry in the topology set with
   V as T_dest and U as T_last.

   The following procedure is given as an example to calculate (or
   re-calculate) re-
   calculate) the routing table :

   1.

     1    All the entries from the routing table are removed.

   2.

     2    The new routing entries are added starting with the one
      hop symmetric
          neighbors (h=1) as the destination nodes. For each neighbor
      entry
          tuple in the neighbor table, whose Link Type set, corresponding to a symmetric link
          (i.e. N_LOST_time is SYM_LINK or
      MPR_LINK, expired, N_pending == false and
          N_SYM_time is not expired),
           a new routing entry is recorded in the routing table where
          R_dest and is set to the main address N_main_addr of the neighbor,
          R_next are both is set to the interface address N_if_addr of the
      neighbor and neigh-
          bor interface, R_dist is set to 1.

   3. 1, and R_if_id is set to the
          value field N_if_id of the entry. If N_if_addr is distinct of
          N_main_addr, another new routing entry with R_dest =
          N_main_addr, R_next = N_if_addr, R_if_id = N_if_id and R_dist
          = 1 is added.

     3    The new route entries for the destination nodes h+1 hops away
          are recorded in the routing table. The following procedure is
          executed for each value of h, starting with h=1 and
      incrementing increment-
          ing it by 1 each time. The execution will stop if no new entry
          is recorded in an iteration.

          3.1  For each topology entry in the topology table, if its
               T_dest does not correspond to R_dest of any route entry
               in the routing table AND its T_last corresponds to R_dest
               of a route entry whose R_dist is equal to h, then a new
               route entry is recorded in the routing table where :

                - R_dest is set routing table (if it does
               not already exist) where:

                    R_dest is set to T_dest;

                    R_next is set to R_next of the recorded route entry
                    whose R_dest is equal to T_last

                    R_dist is set to h+1; and

                    R_if_id is set to the value of the R_if_id of the
                    recorded route entry whose R_dest is equal to
                    T_last.

   The routing table is further completed by using the multiple inter-
   face association set:

     1    For each entry in the multiple interface association where
          there exists a routing entry such that:

               R_dest == I_main_addr (of the multiple interface inter-
               face association entry)
          a route entry is created in the routing table with:

               R_dest  = I_if_addr (of the multiple interface associa-
               tion entry)

               R_next  = R_next (of the recorded route entry)

               R_dist  = R_dist (of the recorded route entry)

               R_if_id = R_if_id (of the recorded route entry).

   The routing table is finally completed by using the host and network
   association set:

     1    For each tuple in the routing set, record an entry in the
          routing table, with:

               R_dest     = NET_addr/NET_mask

               R_next     = the next hop on the path from the node to T_dest;
                - R_next is set
               GW_main_addr

               R_dist     = dist to GW_main_addr

               R_next of the route entry whose
                  R_dest is equal to T_last; and
                - R_dist is R_if_id are set to h+1.

7.7 Link layer notification

   OLSR is designed not to impose or expect any specific information
   from the link layer. However, if information from the link-layer
   is available, a node MAY use this as described in this section.

   If link layer information describing connectivity to neighboring
   nodes is available (i.e. loss of connectivity such same values as through
   absence of a link layer acknowledgment), this information is
   used in addition to the information
               tuple from the HELLO-messages to
   maintain the neighbor routing set and with R_dest == GW_main_addr.

3.  Node Configuration

3.1.  Address Assignment

   The nodes in the MPR selector set.

   Subsequently, detection of a link failure through MANET network SHOULD be assigned addresses within a link-layer
   notification may trigger additional TC-messages to increase
   defined address sequence. I.e., the
   protocols reactiveness to link failures. I.e. when a change to nodes in the
   MPR selector set is detected and this change can MANET SHOULD be attributed to
   addressable through a link failure, network address and a TC-message netmask.

   Likewise, the nodes in each associated network SHOULD be transmitted.

   Thus, upon receiving assigned
   addresses from a link-layer notification defined address sequence, distinct from that being
   used in the link
   between MANET.

3.2.  Routing Configuration

   MANET nodes MUST be configured such that they have a node and any neighbor is broken, the following actions
   are taken:

   1. if network route
   set up on one of the link is broken to either a symmetric or asymmetric
      neighbor, interfaces participating in the tuple MANET. I.e., in
   lack of other routing information, any incoming datagrams, destined
   for that neighbor is removed from the
      neighbor set,

   2. if a node in the link MANET address sequence, is broken transmitted onto this
   interface (efficiently: incoming data to a neighbor, MANET node, which is selected as MPR,
      the tuple for that neighbor is removed from the neighbor
      set and the MPR set is recalculated,

   3. if the link node
   cannot find an exact match for, is broken broadcast to a neighbor, which has selected this all neighbors)

   Any node as MPR, with associated networks or hosts SHOULD, in addition to the MPR selector set is updated and a
      TC message SHOULD
   configuration described above, be generated.

8. Packet forwarding

8.1. configured such that it has routes
   set up to the interfaces with associated hosts or network.

3.3.  Data packet forwarding Packet Forwarding

   OLSR itself does not perform packet forwarding. Rather, it maintains
   the routing table in the underlying operating system, which is
   assumed to be forwarding packets as specified in RFC1812.

8.2.

3.4.  Control message forwarding Message Forwarding

   Control messages, destined for flooding into the entire network,
   SHOULD be relayed by the MPR via the following rule:

      A node retransmits a message only when it is received from one
      of its MPR selector AND it is not before registered in the
      duplicate table AND the time to live is greater than zero. 1 (one).

      Before retransmitting, the hop count is incremented by one and the
      time to live is decremented by one.

9.

4.  IPv6 Considerations

   All the operations and parameters described in this document used by
   OLSR for IP version 4 are the same as those used by OLSR for IP ver-
   sion 6.  However, with IP version 6, we only need to replace all the
   4 bytes Ipv4 address field in different messages with 16 bytes Ipv6
   address format.

5.  Proposed values Values for the constants Constants

   This section list the values for the constants used in the
   description descrip-
   tion of the protocol.

          HELLO_INTERVAL   = 2 seconds

          TC_INTERVAL      = 5 seconds
          MID_INTERVAL     = TC_INTERVAL

          HNA_INTERVAL     = TC_INTERVAL

          NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL

          TOP_HOLD_TIME    = 3 x TC_INTERVAL

          D_TIME           = 30 seconds

          I_TIME           = 3 x MID_INTERVAL

          GW_TIME          = 3 x HNA_INTERVAL

          HELLO_MESSAGE    = 1

          TC_MESSAGE       = 2

          MID_MESSAGE      = 3

          HNA_MESSAGE      = 4

          ASYM_LINK        = 1

          SYM_LINK         = 2

          MPR_LINK         = 3

10.

          LOST_LINK        = 4

          HYST_THRESHOLD_HIGH   = 0.8

          HYST_THRESHOLD_LOW    = 0.3

          HYST_SCALING          = 0.5

          MAXJITTER             = 0.5

6.  Sequence Numbers

   Sequence numbers are used in OLSR with the purpose of discarding
   "old" information, i.e. messages received out of order. However with
   a limited number of bits for representing sequence numbers,
  wrap-arounds wrap-
   arounds (that the sequence number is incremented from the maximum
   possible value to zero) will occur. To prevent this from interfering
   with the operation of the protocol, the following MUST be observed.

   The term MAXVALUE designates in the following the largest possible
   value for a sequence number.

   The sequence number S1 is said to be "greater than" the sequence
  number num-
   ber S2 iff:

          S1-S2 < MAXVALUE/2 OR

          S1    < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2

   Thus when comparing two messages, it is possible - even in the
  presence pres-
   ence of wrap-around - to determine which message contains the most
   recent information.

11.

7.  Acknowledgments
   The authors would like to thank Joseph Macker and his team
   <macker@itd.nrl.navy.mil> for their valuable suggestions on the
   advanced neighbor sensing mechanism.

8.  References

1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre.  Increasing
      reliability relia-
     bility in cable free radio LANs: Low level forwarding in HIPERLAN.
     Wireless Personal Communications, 1996

2. A. Qayyum, L. Viennot, A. Laouiti.  Multipoint relaying: An efficient
     technique for flooding in mobile wireless networks.  INRIA research
     report RR-3898, 2000

3. ETSI STC-RES10 Committee.  Radio equipment and systems: HIPERLAN type
     1, functional specifications ETS 300-652, ETSI, June 1996

4. Corson et al.  Internet MANET Encapsulation Protocol. Internet
      draft, draft-ietf-manet-imep-spec-01.txt, Work Philippe Jacquet and Laurent Viennot, Overhead in progress.

   5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet
      draft, draft-ietf-manet-term-00.txt, Ad-hoc Net-
     work in progress.

   6. Corson, S.,  MANET Routing Protocol Applicability Statement,
      Internet draft, draft-ietf-manet-appl-00.txt, Work in progress.

   7. Protocols, INRIA research report RR-3965, 2000

5. S. Bradner.  Key words for use in RFCs to Indicate Requirement
      Levels. Lev-
     els.  Request for Comments (Best Current Practice) 2119, Internet
     Engineering Task Force, March 1997.

   8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc
      Network Protocols, INRIA research report RR-3965, 2000

12. Authors' Addresses

   Amir Qayyum
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5273
   Email: Amir.Qayyum@inria.fr

   Philippe Jacquet
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5263
   Email: Philippe.Jacquet@inria.fr

   Anis Laouiti
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 508832
   Email: Anis.Laouiti@inria.fr

   Laurent Viennot
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5225
   Email: Laurent.Viennot@inria.fr

   Paul Muhlethaler
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5278
   Email: Thomas.Clausen@inria.fr

   Thomas Clausen
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5133
   Email: Thomas.Clausen@inria.fr