tech-invite   World Map
3GPP     Specs     Glossaries     UICC       IETF     RFCs     Groups     SIP     ABNFs       T+       Search     Home

RFC 3626

 
 
 

Optimized Link State Routing Protocol (OLSR)

Part 2 of 3, p. 22 to 51
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 22 
4.  Information Repositories

   Through the exchange of OLSR control messages, each node accumulates
   information about the network.  This information is stored according
   to the descriptions in this section.

4.1.  Multiple Interface Association Information Base

   For each destination in the network, "Interface Association Tuples"
   (I_iface_addr, I_main_addr, I_time) are recorded.  I_iface_addr is an
   interface address of a node, I_main_addr is the main address of this
   node.  I_time specifies the time at which this tuple expires and
   *MUST* be removed.

   In a node, the set of Interface Association Tuples is denoted the
   "Interface Association Set".

4.2.  Link Sensing: Local Link Information Base

   The local link information base stores information about links to
   neighbors.

4.2.1.  Link Set

   A node records a set of "Link Tuples" (L_local_iface_addr,
   L_neighbor_iface_addr, L_SYM_time, L_ASYM_time, L_time).
   L_local_iface_addr is the interface address of the local node (i.e.,
   one endpoint of the link), L_neighbor_iface_addr is the interface
   address of the neighbor node (i.e., the other endpoint of the link),
   L_SYM_time is the time until which the link is considered symmetric,
   L_ASYM_time is the time until which the neighbor interface is
   considered heard, and L_time specifies the time at which this record
   expires and *MUST* be removed.  When L_SYM_time and L_ASYM_time are
   expired, the link is considered lost.

   This information is used when declaring the neighbor interfaces in
   the HELLO messages.

   L_SYM_time is used to decide the Link Type declared for the neighbor
   interface.  If L_SYM_time is not expired, the link MUST be declared
   symmetric.  If L_SYM_time is expired, the link MUST be declared
   asymmetric.  If both L_SYM_time and L_ASYM_time are expired, the link
   MUST be declared lost.

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

Top      Up      ToC       Page 23 
4.3.  Neighbor Detection: Neighborhood Information Base

   The neighborhood information base stores information about neighbors,
   2-hop neighbors, MPRs and MPR selectors.

4.3.1.  Neighbor Set

   A node records a set of "neighbor tuples" (N_neighbor_main_addr,
   N_status, N_willingness), describing neighbors.  N_neighbor_main_addr
   is the main address of a neighbor, N_status specifies if the node is
   NOT_SYM or SYM.  N_willingness in an integer between 0 and 7, and
   specifies the node's willingness to carry traffic on behalf of other
   nodes.

4.3.2.  2-hop Neighbor Set

   A node records a set of "2-hop tuples" (N_neighbor_main_addr,
   N_2hop_addr, N_time), describing symmetric (and, since MPR links by
   definition are also symmetric, thereby also MPR) links between its
   neighbors and the symmetric 2-hop neighborhood.  N_neighbor_main_addr
   is the main address of a neighbor, N_2hop_addr is the main address of
   a 2-hop neighbor with a symmetric link to N_neighbor_main_addr, and
   N_time specifies the time at which the tuple expires and *MUST* be
   removed.

   In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor
   Set".

4.3.3.  MPR Set

   A node maintains a set of neighbors which are selected as MPR.  Their
   main addresses are listed in the MPR Set.

4.3.4.  MPR Selector Set

   A node records a set of MPR-selector tuples (MS_main_addr, MS_time),
   describing the neighbors which have selected this node as a MPR.
   MS_main_addr is the main address of a node, which has selected this
   node as MPR.  MS_time specifies the time at which the tuple expires
   and *MUST* be removed.

   In a node, the set of MPR-selector tuples are denoted the "MPR
   Selector Set".

Top      Up      ToC       Page 24 
4.4.  Topology Information Base

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

   Thus, for each destination in the network, at least one "Topology
   Tuple" (T_dest_addr, T_last_addr, T_seq, T_time) is recorded.
   T_dest_addr is the main address of a node, which may be reached in
   one hop from the node with the main address T_last_addr.  Typically,
   T_last_addr is a MPR of T_dest_addr.  T_seq is a sequence number, and
   T_time specifies the time at which this tuple expires and *MUST* be
   removed.

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

5.  Main Addresses and Multiple Interfaces

   For single OLSR interface nodes, the relationship between an OLSR
   interface address and the corresponding main address is trivial: the
   main address is the OLSR interface address.  For multiple OLSR
   interface nodes, the relationship between OLSR interface addresses
   and main addresses is defined through the exchange of Multiple
   Interface Declaration (MID) messages.  This section describes how MID
   messages are exchanged and processed.

   Each node with multiple interfaces MUST announce, periodically,
   information describing its interface configuration to other nodes in
   the network.  This is accomplished through flooding a Multiple
   Interface Declaration message to all nodes in the network through the
   MPR flooding mechanism.

   Each node in the network maintains interface information about the
   other nodes in the network.  This information acquired from MID
   messages, emitted by nodes with multiple interfaces participating in
   the MANET, and is used for routing table calculations.

   Specifically, multiple interface declaration associates multiple
   interfaces to a node (and to a main address) through populating the
   multiple interface association base in each node.

Top      Up      ToC       Page 25 
5.1.  MID Message Format

   The proposed format of a MID message 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 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    OLSR Interface Address                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    OLSR Interface Address                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                              ...                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data-portion of the general packet format
   described in section 3.4, with the "Message Type" set to MID_MESSAGE.
   The time to live SHOULD be set to 255 (maximum value) to diffuse the
   message into the entire network and Vtime set accordingly to the
   value of MID_HOLD_TIME, as specified in section 18.3.

     OLSR Interface Address

          This field contains the address of an OLSR interface of the
          node, excluding the nodes main address (which already
          indicated in the originator address).

   All interface addresses other than the main address of the originator
   node are put in the MID message.  If the maximum allowed message size
   (as imposed by the network) is reached while there are still
   interface addresses which have not been inserted into the MIDmessage,
   more MID messages are generated until the entire interface addresses
   set has been sent.

5.2.  MID Message Generation

   A MID message is sent by a node in the network to declare its
   multiple interfaces (if any).  I.e., the MID message contains the
   list of interface addresses which are associated to its main address.
   The list of addresses can be partial in each MID message (e.g., due
   to message size limitations, imposed by the network), but parsing of
   all MID messages describing the interface set from a node MUST be
   complete within a certain refreshing period (MID_INTERVAL).  The
   information diffused in the network by these MID messages will help
   each node to calculate its routing table.  A node which has only a
   single interface address participating in the MANET (i.e., running
   OLSR), MUST NOT generate any MID message.

Top      Up      ToC       Page 26 
   A node with several interfaces, where only one is participating in
   the MANET and running OLSR (e.g., a node is connected to a wired
   network as well as to a MANET) MUST NOT generate any MID messages.

   A node with several interfaces, where more than one is participating
   in the MANET and running OLSR MUST generate MID messages as
   specified.

5.3.  MID Message Forwarding

   MID messages are broadcast and retransmitted by the MPRs in order to
   diffuse the messages in the entire network.  The "default forwarding
   algorithm" (described in section 3.4) MUST be used for forwarding of
   MID messages.

5.4.  MID Message Processing

   The tuples in the multiple interface association set are recorded
   with the information that is exchanged through MID messages.

   Upon receiving a MID message, the "validity time" MUST be computed
   from the Vtime field of the message header (as described in section
   3.3.2).  The Multiple Interface Association Information Base SHOULD
   then be updated as follows:

     1    If the sender interface (NB: not originator) of this message
          is not in the symmetric 1-hop neighborhood of this node, the
          message MUST be discarded.

     2    For each interface address listed in the MID message:

          2.1  If there exist some tuple in the interface association
               set where:

                    I_iface_addr == interface address, AND

                    I_main_addr  == originator address,

               then the holding time of that tuple is set to:

                    I_time       = current time + validity time.

          2.2  Otherwise, a new tuple is recorded in the interface
               association set where:

                    I_iface_addr = interface address,

                    I_main_addr  = originator address,

Top      Up      ToC       Page 27 
                    I_time       = current time + validity time.

5.5.  Resolving a Main Address from an Interface Address

   In general, the only part of OLSR requiring use of "interface
   addresses" is link sensing.  The remaining parts of OLSR operate on
   nodes, uniquely identified by their "main addresses" (effectively,
   the main address of a node is its "node id" - which for convenience
   corresponds to the address of one of its interfaces).  In a network
   with only single interface nodes, the main address of a node will, by
   definition, be equal to the interface address of the node.  In
   networks with multiple interface nodes operating within a common OLSR
   area, it is required to be able to map any interface address to the
   corresponding main address.

   The exchange of MID messages provides a way in which interface
   information is acquired by nodes in the network.  This permits
   identification of a node's "main address", given one of its interface
   addresses.

   Given an interface address:

     1    if there exists some tuple in the interface association set
          where:

               I_iface_addr == interface address

          then the result of the main address search is the originator
          address I_main_addr of the tuple.

     2    Otherwise, the result of the main address search is the
          interface address itself.

6.  HELLO Message Format and Generation

   A common mechanism is employed for populating the local link
   information base and the neighborhood information base, namely
   periodic exchange of HELLO messages.  Thus this section describes the
   general HELLO message mechanism, followed by a description of link
   sensing and topology detection, respectively.

6.1.  HELLO Message Format

   To accommodate for link sensing, neighborhood detection and MPR
   selection signalling, as well as to accommodate for future
   extensions, an approach similar to the overall packet format is
   taken.  Thus the proposed format of a HELLO message is as follows:

Top      Up      ToC       Page 28 
       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             |     Htime     |  Willingness  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Link Code   |   Reserved    |       Link Message Size       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                             .  .  .                           :
      :                                                               :
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Link Code   |   Reserved    |       Link Message Size       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Neighbor Interface Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      :                                                               :
      :                                       :
   (etc.)

   This is sent as the data-portion of the general packet format
   described in section 3.4, with the "Message Type" set to
   HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly
   to the value of NEIGHB_HOLD_TIME, specified in section 18.3.

      Reserved

         This field must be set to "0000000000000" to be in compliance
         with this specification.

      HTime

         This field specifies the HELLO emission interval used by the
         node on this particular interface, i.e., the time before the
         transmission of the next HELLO (this information may be used in
         advanced link sensing, see section 14).  The HELLO emission
         interval is represented by its mantissa (four highest bits of
         Htime field) and by its exponent (four lowest bits of Htime
         field).  In other words:

              HELLO emission interval=C*(1+a/16)*2^b  [in seconds]

Top      Up      ToC       Page 29 
         where a is the integer represented by the four highest bits of
         Htime field and b the integer represented by the four lowest
         bits of Htime field.  The proposed value of the scaling factor
         C is specified in section 18.

      Willingness

         This field specifies the willingness of a node to carry and
         forward traffic for other nodes.

         A node with willingness WILL_NEVER (see section 18.8, for
         willingness constants) MUST never be selected as MPR by any
         node.  A node with willingness WILL_ALWAYS MUST always be
         selected as MPR.  By default, a node SHOULD advertise a
         willingness of WILL_DEFAULT.

      Link Code

         This field specifies information about the link between the
         interface of the sender and the following list of neighbor
         interfaces.  It also specifies information about the status of
         the neighbor.

         Link codes, not known by a node, are silently discarded.

      Link Message Size

         The size of the link message, counted in bytes and measured
         from the beginning of the "Link Code" field and until the next
         "Link Code" field (or - if there are no more link types - the
         end of the message).

      Neighbor Interface Address

         The address of an interface of a neighbor node.

6.1.1.  Link Code as Link Type and Neighbor Type

   This document only specifies processing of Link Codes < 16.

   If the Link Code value is less than or equal to 15, then it MUST be
   interpreted as holding two different fields, of two bits each:

          7       6       5       4       3       2       1       0
      +-------+-------+-------+-------+-------+-------+-------+-------+
      |   0   |   0   |   0   |   0   | Neighbor Type |   Link Type   |
      +-------+-------+-------+-------+-------+-------+-------+-------+

Top      Up      ToC       Page 30 
   The following four "Link Types" are REQUIRED by OLSR:

     -    UNSPEC_LINK - indicating that no specific information about
          the links is given.

     -    ASYM_LINK - indicating that the links are asymmetric (i.e.,
          the neighbor interface is "heard").

     -    SYM_LINK - indicating that the links are symmetric with the
          interface.

     -    LOST_LINK - indicating that the links have been lost.

   The following three "Neighbor Types" are REQUIRED by OLSR:

     -    SYM_NEIGH - indicating that the neighbors have at least one
          symmetrical link with this node.

     -    MPR_NEIGH - indicating that the neighbors have at least one
          symmetrical link AND have been selected as MPR by the sender.

     -    NOT_NEIGH - indicating that the nodes are either no longer or
          have not yet become symmetric neighbors.

   Note that an implementation should be careful in confusing neither
   Link Type with Neighbor Type nor the constants (confusing SYM_NEIGH
   with SYM_LINK for instance).

   A link code advertising:

          Link Type     == SYM_LINK AND

          Neighbor Type == NOT_NEIGH

   is invalid, and any links advertised as such MUST be silently
   discarded without any processing.

   Likewise a Neighbor Type field advertising a numerical value which is
   not one of the constants SYM_NEIGH, MPR_NEIGH, NOT_NEIGH, is invalid,
   and any links advertised as such MUST be silently discarded without
   any processing.

6.2.  HELLO Message Generation

   This involves transmitting the Link Set, the Neighbor Set and the MPR
   Set.  In principle, a HELLO message serves three independent tasks:

     -    link sensing

Top      Up      ToC       Page 31 
     -    neighbor detection

     -    MPR selection signaling

   Three tasks are all are based on periodic information exchange within
   a nodes neighborhood, and serve the common purpose of "local topology
   discovery".  A HELLO message is therefore generated based on the
   information stored in the Local Link Set, the Neighbor Set and the
   MPR Set from the local link information base.

   A node must perform link sensing on each interface, in order to
   detect links between the interface and neighbor interfaces.
   Furthermore, a node must advertise its entire symmetric 1-hop
   neighborhood on each interface in order to perform neighbor
   detection.  Hence, for a given interface, a HELLO message will
   contain a list of links on that interface (with associated link
   types), as well as a list of the entire neighborhood (with an
   associated neighbor types).

   The Vtime field is set such that it corresponds to the value of the
   node's NEIGHB_HOLD_TIME parameter.  The Htime field is set such that
   it corresponds to the value of the node's HELLO_INTERVAL parameter
   (see section 18.3).

   The Willingness field is set such that it corresponds to the node's
   willingness to forward traffic on behalf of other nodes (see section
   18.8).  A node MUST advertise the same willingness on all interfaces.

   The lists of addresses declared in a HELLO message is a list of
   neighbor interface addresses computed as follows:

   For each tuple in the Link Set, where L_local_iface_addr is the
   interface where the HELLO is to be transmitted, and where L_time >=
   current time (i.e., not expired), L_neighbor_iface_addr is advertised
   with:

     1    The Link Type set according to the following:

          1.1  if L_SYM_time >= current time (not expired)

                    Link Type = SYM_LINK

          1.2  Otherwise, if L_ASYM_time >= current time (not expired)
               AND

                             L_SYM_time  <  current time (expired)

                    Link Type = ASYM_LINK

Top      Up      ToC       Page 32 
          1.3  Otherwise, if L_ASYM_time < current time (expired) AND

                             L_SYM_time  < current time (expired)

                    Link Type = LOST_LINK

     2    The Neighbor Type is set according to the following:

          2.1  If the main address, corresponding to
               L_neighbor_iface_addr, is included in the MPR set:

                    Neighbor Type = MPR_NEIGH

          2.2  Otherwise, if the main address, corresponding to
               L_neighbor_iface_addr, is included in the neighbor set:

               2.2.1
                    if N_status == SYM

                         Neighbor Type = SYM_NEIGH

               2.2.2
                    Otherwise, if N_status == NOT_SYM
                         Neighbor Type = NOT_NEIGH

   For each tuple in the Neighbor Set, for which no
   L_neighbor_iface_addr from an associated link tuple has been
   advertised by the previous algorithm,  N_neighbor_main_addr is
   advertised with:

     - Link Type = UNSPEC_LINK,

     - Neighbor Type set as described in step 2 above

   For a node with a single OLSR interface, the main address is simply
   the address of the OLSR interface, i.e., for a node with a single
   OLSR interface the main address, corresponding to
   L_neighbor_iface_addr is simply L_neighbor_iface_addr.

   A HELLO message can be partial (e.g., due to message size
   limitations, imposed by the network), the rule being the following,
   on each interface: each link and each neighbor node MUST be cited at
   least once within a predetermined refreshing period,
   REFRESH_INTERVAL.  To keep track of fast connectivity changes, a
   HELLO message must be sent at least every HELLO_INTERVAL period,
   smaller than or equal to REFRESH_INTERVAL.

Top      Up      ToC       Page 33 
   Notice that for limiting the impact from loss of control messages, it
   is desirable that a message (plus the generic packet header) can fit
   into a single MAC frame.

6.3.  HELLO Message Forwarding

   Each HELLO message generated is broadcast by the node on one
   interface to its neighbors (i.e. the interface for which the HELLO
   was generated).  HELLO messages MUST never be forwarded.

6.4.  HELLO Message Processing

   A node processes incoming HELLO messages for the purpose of
   conducting link sensing (detailed in section 7), neighbor detection
   and MPR selector set population (detailed in section 8)

7.  Link Sensing

   Link sensing populates the local link information base.  Link sensing
   is exclusively concerned with OLSR interface addresses and the
   ability to exchange packets between such OLSR interfaces.

   The mechanism for link sensing is the periodic exchange of HELLO
   messages.

7.1.  Populating the Link Set

   The Link Set is populated with information on links to neighbor
   nodes.  The process of populating this set is denoted "link sensing"
   and is performed using HELLO message exchange, updating a local link
   information base in each node.

   Each node should detect the links between itself and neighbor nodes.
   Uncertainties over radio propagation may make some links
   unidirectional.  Consequently, all links MUST be checked in both
   directions in order to be considered valid.

   A "link" is described by a pair of interfaces: a local and a remote
   interface.

   For the purpose of link sensing, each neighbor node (more
   specifically, the link to each neighbor) has an associated status of
   either "symmetric" or "asymmetric".  "Symmetric" indicates, that the
   link to that neighbor node has been verified to be bi-directional,
   i.e., it is possible to transmit data in both directions.
   "Asymmetric" indicates that HELLO messages from the node have been

Top      Up      ToC       Page 34 
   heard (i.e., communication from the neighbor node is possible),
   however it is not confirmed that this node is also able to receive
   messages (i.e., communication to the neighbor node is not confirmed).

   The information, acquired through and used by the link sensing, is
   accumulated in the link set.

7.1.1.  HELLO Message Processing

   The "Originator Address" of a HELLO message is the main address of
   the node, which has emitted the message.

   Upon receiving a HELLO message, a node SHOULD update its Link Set.
   Notice, that a HELLO message MUST neither be forwarded nor be
   recorded in the duplicate set.

   Upon receiving a HELLO message, the "validity time" MUST be computed
   from the Vtime field of the message header (see section 3.3.2).
   Then, the Link Set SHOULD be updated as follows:

     1    Upon receiving a HELLO message, if there exists no link tuple
          with

               L_neighbor_iface_addr == Source Address

          a new tuple is created with

               L_neighbor_iface_addr = Source Address

               L_local_iface_addr    = Address of the interface
                                       which received the
                                       HELLO message

               L_SYM_time            = current time - 1 (expired)

               L_time                = current time + validity time

     2    The tuple (existing or new) with:

               L_neighbor_iface_addr == Source Address

          is then modified as follows:

          2.1  L_ASYM_time = current time + validity time;

          2.2  if the node finds the address of the interface which
               received the HELLO message among the addresses listed in
               the link message then the tuple is modified as follows:

Top      Up      ToC       Page 35 
               2.2.1
                    if Link Type is equal to LOST_LINK then

                         L_SYM_time = current time - 1 (i.e., expired)

               2.2.2
                    else if Link Type is equal to SYM_LINK or ASYM_LINK
                    then

                         L_SYM_time = current time + validity time,

                         L_time     = L_SYM_time + NEIGHB_HOLD_TIME

          2.3  L_time = max(L_time, L_ASYM_time)

   The above rule for setting L_time is the following: a link losing its
   symmetry SHOULD still be advertised during at least the duration of
   the "validity time" advertised in the generated HELLO.  This allows
   neighbors to detect the link breakage.

8.  Neighbor Detection

   Neighbor detection populates the neighborhood information base and
   concerns itself with nodes and node main addresses.  The relationship
   between OLSR interface addresses and main addresses is described in
   section 5.

   The mechanism for neighbor detection is the periodic exchange of
   HELLO messages.

8.1.  Populating the Neighbor Set

   A node maintains a set of neighbor tuples, based on the link tuples.
   This information is updated according to changes in the Link Set.

   The Link Set keeps the information about the links, while the
   Neighbor Set keeps the information about the neighbors.  There is a
   clear association between those two sets, since a node is a neighbor
   of another node if and only if there is at least one link between the
   two nodes.

   In any case, the formal correspondence between links and neighbors is
   defined as follows:

          The "associated neighbor tuple" of a link tuple, is, if it
          exists, the neighbor tuple where:

Top      Up      ToC       Page 36 
               N_neighbor_main_addr == main address of
                                       L_neighbor_iface_addr

          The "associated link tuples" of a neighbor tuple, are all the
          link tuples, where:

               N_neighbor_main_addr == main address of
                                       L_neighbor_iface_addr

   The Neighbor Set MUST be populated by maintaining the proper
   correspondence between link tuples and associated neighbor tuples, as
   follows:

     Creation

          Each time a link appears, that is, each time a link tuple is
          created, the associated neighbor tuple MUST be created, if it
          doesn't already exist, with the following values:

               N_neighbor_main_addr = main address of
                                      L_neighbor_iface_addr
                                      (from the link tuple)

          In any case, the N_status MUST then be computed as described
          in the next step

     Update

          Each time a link changes, that is, each time the information
          of a link tuple is modified, the node MUST ensure that the
          N_status of the associated neighbor tuple respects the
          property:

               If the neighbor has any associated link tuple which
               indicates a symmetric link (i.e., with L_SYM_time >=
               current time), then

                    N_status is set to SYM

               else N_status is set to NOT_SYM

     Removal

          Each time a link is deleted, that is, each time a link tuple
          is removed, the associated neighbor tuple MUST be removed if
          it has no longer any associated link tuples.

Top      Up      ToC       Page 37 
   These rules ensure that there is exactly one associated neighbor
   tuple for a link tuple, and that every neighbor tuple has at least
   one associated link tuple.

8.1.1.  HELLO Message Processing

   The "Originator Address" of a HELLO message is the main address of
   the node, which has emitted the message.  Likewise, the "willingness"
   MUST be computed from the Willingness field of the HELLO message (see
   section 6.1).

   Upon receiving a HELLO message, a node SHOULD first update its Link
   Set as described before.  It SHOULD then update its Neighbor Set as
   follows:

     -    if the Originator Address is the N_neighbor_main_addr from a
          neighbor tuple included in the Neighbor Set:

               then, the neighbor tuple SHOULD be updated as follows:

               N_willingness = willingness from the HELLO message

8.2.  Populating the 2-hop Neighbor Set

   The 2-hop neighbor set describes the set of nodes which have a
   symmetric link to a symmetric neighbor.  This information set is
   maintained through periodic exchange of HELLO messages as described
   in this section.

8.2.1.  HELLO Message Processing

   The "Originator Address" of a HELLO message is the main address of
   the node, which has emitted the message.

   Upon receiving a HELLO message from a symmetric neighbor, a node
   SHOULD update its 2-hop Neighbor Set.  Notice, that a HELLO message
   MUST neither be forwarded nor be recorded in the duplicate set.

   Upon receiving a HELLO message, the "validity time" MUST be computed
   from the Vtime field of the message header (see section 3.3.2).

   If the Originator Address is the main address of a
   L_neighbor_iface_addr from a link tuple included in the Link Set with

          L_SYM_time >= current time (not expired)

   (in other words: if the Originator Address is a symmetric neighbor)
   then the 2-hop Neighbor Set SHOULD be updated as follows:

Top      Up      ToC       Page 38 
     1    for each address (henceforth: 2-hop neighbor address), listed
          in the HELLO message with Neighbor Type equal to SYM_NEIGH or
          MPR_NEIGH:

          1.1  if the main address of the 2-hop neighbor address = main
               address of the receiving node:

                    silently discard the 2-hop neighbor address.

               (in other words: a node is not its own 2-hop neighbor).

          1.2  Otherwise, a 2-hop tuple is created with:

                    N_neighbor_main_addr =  Originator Address;

                    N_2hop_addr          =  main address of the
                                            2-hop neighbor;

                    N_time               =  current time
                                            + validity time.


               This tuple may replace an older similar tuple with same
               N_neighbor_main_addr and N_2hop_addr values.

     2    For each 2-hop node listed in the HELLO message with Neighbor
          Type equal to NOT_NEIGH, all 2-hop tuples where:

               N_neighbor_main_addr == Originator Address AND

               N_2hop_addr          == main address of the
                                       2-hop neighbor

          are deleted.

8.3.  Populating the MPR set

   MPRs are used to flood control messages from a node into the network
   while reducing the number of retransmissions that will occur in a
   region.  Thus, the concept of MPR is an optimization of a classical
   flooding mechanism.

   Each node in the network selects, independently, its own set of MPRs
   among its symmetric 1-hop neighborhood.  The symmetric links with
   MPRs are advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in
   HELLO messages.

Top      Up      ToC       Page 39 
   The MPR set MUST be calculated by a node in such a way that it,
   through the neighbors in the MPR-set, can reach all symmetric strict
   2-hop neighbors.  (Notice that a node, a, which is a direct neighbor
   of another node, b, is not also a strict 2-hop neighbor of node b).
   This means that the union of the symmetric 1-hop neighborhoods of the
   MPR nodes contains the symmetric strict 2-hop neighborhood.  MPR set
   recalculation should occur when changes are detected in the symmetric
   neighborhood or in the symmetric strict 2-hop neighborhood.

   MPRs are computed per interface, the union of the MPR sets of each
   interface make up the MPR set for the node.

   While it is not essential that the MPR set is minimal, it is
   essential that all strict 2-hop neighbors can be reached through the
   selected MPR nodes.  A node SHOULD select an MPR set such that any
   strict 2-hop neighbor is covered by at least one MPR node.  Keeping
   the MPR set small ensures that the overhead of the protocol is kept
   at a minimum.

   The MPR set can coincide with the entire symmetric neighbor set.
   This could be the case at network initialization (and will correspond
   to classic link-state routing).

8.3.1.  MPR Computation

   The following specifies a proposed heuristic for selection of MPRs.
   It constructs an MPR-set that enables a node to reach any node in the
   symmetrical strict 2-hop neighborhood through relaying by one MPR
   node with willingness different from WILL_NEVER.  The heuristic MUST
   be applied per interface, I.  The MPR set for a node is the union of
   the MPR sets found for each interface.  The following terminology
   will be used in describing the heuristics:

       neighbor of an interface

              a node is a "neighbor of an interface" if the interface
              (on the local node) has a link to any one interface of
              the neighbor node.

       2-hop neighbors reachable from an interface

              the list of 2-hop neighbors of the node that can be
              reached from neighbors of this interface.

Top      Up      ToC       Page 40 
       MPR set of an interface

              a (sub)set of the neighbors of an interface with a
              willingness different from WILL_NEVER, selected such that
              through these selected nodes, all strict 2-hop neighbors
              reachable from that interface are reachable.

       N:
              N is the subset of neighbors of the node, which are
              neighbor of the interface I.

       N2:
              The set of 2-hop neighbors reachable from the interface
              I, excluding:

               (i)   the nodes only reachable by members of N with
                     willingness WILL_NEVER

               (ii)  the node performing the computation

               (iii) all the symmetric neighbors: the nodes for which
                     there exists a symmetric link to this node on some
                     interface.

    D(y):
              The degree of a 1-hop neighbor node y (where y is a
              member of N), is defined as the number of symmetric
              neighbors of node y, EXCLUDING all the members of N and
              EXCLUDING the node performing the computation.

   The proposed heuristic is as follows:

     1    Start with an MPR set made of all members of N with
          N_willingness equal to WILL_ALWAYS

     2    Calculate D(y), where y is a member of N, for all nodes in N.

     3    Add to the MPR set those nodes in N, which are the *only*
          nodes to provide reachability to a node in N2.  For example,
          if node b in N2 can be reached only through a symmetric link
          to node a in N, then add node a to the MPR set.  Remove the
          nodes from N2 which are now covered by a node in the MPR set.

     4    While there exist nodes in N2 which are not covered by at
          least one node in the MPR set:

Top      Up      ToC       Page 41 
          4.1  For each node in N, calculate the reachability, i.e., the
               number of nodes in N2 which are not yet covered by at
               least one node in the MPR set, and which are reachable
               through this 1-hop neighbor;

          4.2  Select as a MPR the node with highest N_willingness among
               the nodes in N with non-zero reachability.  In case of
               multiple choice select the node which provides
               reachability to the maximum number of nodes in N2.  In
               case of multiple nodes providing the same amount of
               reachability, select the node as MPR whose D(y) is
               greater.  Remove the nodes from N2 which are now covered
               by a node in the MPR set.

     5    A node's MPR set is generated from the union of the MPR sets
          for each interface.  As an optimization, process each node, y,
          in the MPR set in increasing order of N_willingness.  If all
          nodes in N2 are still covered by at least one node in the MPR
          set excluding node y, and if N_willingness of node y is
          smaller than WILL_ALWAYS, then node y MAY be removed from the
          MPR set.

   Other algorithms, as well as improvements over this algorithm, are
   possible.  For example, assume that in a multiple-interface scenario
   there exists more than one link between nodes 'a' and 'b'.  If node
   'a' has selected node 'b' as MPR for one of its interfaces, then node
   'b' can be selected as MPR without additional performance loss by any
   other interfaces on node 'a'.

8.4.  Populating the MPR Selector Set

   The MPR selector set of a node, n, is populated by the main addresses
   of the nodes which have selected n as MPR.  MPR selection is signaled
   through HELLO messages.

8.4.1.  HELLO Message Processing

   Upon receiving a HELLO message, if a node finds one of its own
   interface addresses in the list with a Neighbor Type equal to
   MPR_NEIGH, information from the HELLO message must be recorded in the
   MPR Selector Set.

   The "validity time" MUST be computed from the Vtime field of the
   message header (see section 3.3.2).  The MPR Selector Set SHOULD then
   be updated as follows:

Top      Up      ToC       Page 42 
     1    If there exists no MPR selector tuple with:

                    MS_main_addr   == Originator Address

               then a new tuple is created with:

                    MS_main_addr   =  Originator Address

     2    The tuple (new or otherwise) with

               MS_main_addr   == Originator Address

          is then modified as follows:

               MS_time        =  current time + validity time.

   Deletion of MPR selector tuples occurs in case of expiration of the
   timer or in case of link breakage as described in the "Neighborhood
   and 2-hop Neighborhood Changes".

8.5.  Neighborhood and 2-hop Neighborhood Changes

   A change in the neighborhood is detected when:

     -    The L_SYM_time field of a link tuple expires.  This is
          considered as a neighbor loss if the link described by the
          expired tuple was the last link with a neighbor node (on the
          contrary, a link with an interface may break while a link with
          another interface of the neighbor node remains without being
          observed as a neighborhood change).

     -    A new link tuple is inserted in the Link Set with a non
          expired L_SYM_time or a tuple with expired L_SYM_time is
          modified so that L_SYM_time becomes non-expired.  This is
          considered as a neighbor appearance if there was previously no
          link tuple describing a link with the corresponding neighbor
          node.

   A change in the 2-hop neighborhood is detected when a 2-hop neighbor
   tuple expires or is deleted according to section 8.2.

   The following processing occurs when changes in the neighborhood or
   the 2-hop neighborhood are detected:

     -    In case of neighbor loss, all 2-hop tuples with
          N_neighbor_main_addr == Main Address of the neighbor MUST be
          deleted.

Top      Up      ToC       Page 43 
     -    In case of neighbor loss, all MPR selector tuples with
          MS_main_addr == Main Address of the neighbor MUST be deleted

     -    The MPR set MUST be re-calculated when a neighbor appearance
          or loss is detected, or when a change in the 2-hop
          neighborhood is detected.

     -    An additional HELLO message MAY be sent when the MPR set
          changes.

9.  Topology Discovery

   The link sensing and neighbor detection part of the protocol
   basically offers, to each node, a list of neighbors with which it can
   communicate directly and, in combination with the Packet Format and
   Forwarding part, an optimized flooding mechanism through MPRs.  Based
   on this, topology information is disseminated through the network.
   The present section describes which part of the information given by
   the link sensing and neighbor detection is disseminated to the entire
   network and how it is used to construct routes.

   Routes are constructed through advertised links and links with
   neighbors.  A node must at least disseminate links between itself and
   the nodes in its MPR-selector set, in order to provide sufficient
   information to enable routing.

9.1.  TC Message Format

   The proposed format of a TC message 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 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |              ANSN             |           Reserved            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |               Advertised Neighbor Main Address                |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |               Advertised Neighbor Main Address                |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                              ...                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data-portion of the general message format with
   the "Message Type" set to TC_MESSAGE.  The time to live SHOULD be set
   to 255 (maximum value) to diffuse the message into the entire network
   and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified
   in section 18.3.

Top      Up      ToC       Page 44 
     Advertised Neighbor Sequence Number (ANSN)

          A sequence number is associated with the advertised neighbor
          set.  Every time a node detects a change in its advertised
          neighbor set, it increments this sequence number ("Wraparound"
          is handled as described in section 19).  This number is sent
          in this ANSN 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 Advertised Neighbor Sequence
          Number, whether or not the received information about the
          advertised neighbors of the originator node is more recent
          than what it already has.

     Advertised Neighbor Main Address

          This field contains the main address of a neighbor node.  All
          main addresses of the advertised neighbors 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 advertised neighbor addresses which have not
          been inserted into the TC-message, more TC messages will be
          generated until the entire advertised neighbor set has been
          sent.  Extra main addresses of neighbor nodes may be included,
          if redundancy is desired.

     Reserved

          This field is reserved, and MUST be set to "0000000000000000"
          for compliance with this document.

9.2.  Advertised Neighbor Set

   A TC message is sent by a node in the network to declare a set of
   links, called advertised link set which MUST include at least the
   links to all nodes of its MPR Selector set, i.e., the neighbors which
   have selected the sender node as a MPR.

   If, for some reason, it is required to distribute redundant TC
   information, refer to section 15.

   The sequence number (ANSN) associated with the advertised neighbor
   set is also sent with the list.  The ANSN number MUST be incremented
   when links are removed from the advertised neighbor set; the ANSN
   number SHOULD be incremented when links are added to the advertised
   neighbor set.

Top      Up      ToC       Page 45 
9.3.  TC Message Generation

   In order to build the topology information base, 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 in the distribution of
   topology information [1].

   The list of addresses can be partial in each TC message (e.g., due to
   message size limitations, imposed by the network), but parsing of all
   TC messages describing the advertised link set of a node MUST be
   complete within a certain refreshing period (TC_INTERVAL).  The
   information diffused in the network by these TC messages will help
   each node calculate its routing table.

   When the advertised link set of a node becomes empty, this node
   SHOULD still send (empty) TC-messages during the a duration equal to
   the "validity time" (typically, this will be equal to TOP_HOLD_TIME)
   of its previously emitted TC-messages, in order to invalidate the
   previous TC-messages.  It SHOULD then stop sending TC-messages until
   some node is inserted in its advertised link set.

   A node MAY transmit additional TC-messages to increase its
   reactiveness to link failures.  When a change to the MPR selector set
   is detected and this change can be attributed to a link failure, a
   TC-message SHOULD be transmitted after an interval shorter than
   TC_INTERVAL.

9.4.  TC Message Forwarding

   TC messages are broadcast and retransmitted by the MPRs in order to
   diffuse the messages in the entire network.  TC messages MUST be
   forwarded according to the "default forwarding algorithm" (described
   in section 3.4).

9.5.  TC Message Processing

   Upon receiving a TC message, the "validity time" MUST be computed
   from the Vtime field of the message header (see section 3.3.2).  The
   topology set SHOULD then be updated as follows (using section 19 for
   comparison of ANSN):

     1    If the sender interface (NB: not originator) of this message
          is not in the symmetric 1-hop neighborhood of this node, the
          message MUST be discarded.

Top      Up      ToC       Page 46 
     2    If there exist some tuple in the topology set where:

               T_last_addr == originator address AND

               T_seq       >  ANSN,

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


     3    All tuples in the topology set where:

               T_last_addr == originator address AND

               T_seq       <  ANSN

          MUST be removed from the topology set.

     4    For each of the advertised neighbor main address received in
          the TC message:

          4.1  If there exist some tuple in the topology set where:

                    T_dest_addr == advertised neighbor main address, AND

                    T_last_addr == originator address,

               then the holding time of that tuple MUST be set to:

                    T_time      =  current time + validity time.

          4.2  Otherwise, a new tuple MUST be recorded in the topology
               set where:

                    T_dest_addr = advertised neighbor main address,

                    T_last_addr = originator address,

                    T_seq       = ANSN,

                    T_time      = current time + validity time.

Top      Up      ToC       Page 47 
10.  Routing Table Calculation

   Each node maintains a routing table which allows it to route data,
   destined for the other nodes in the network.  The routing table is
   based on the information contained in the local link information base
   and the topology set.  Therefore, if any of these sets are changed,
   the routing table is recalculated 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_addr    R_next_addr    R_dist   R_iface_addr
         2.  R_dest_addr    R_next_addr    R_dist   R_iface_addr
         3.      ,,             ,,           ,,          ,,

   Each entry in the table consists of R_dest_addr, R_next_addr, R_dist,
   and R_iface_addr.  Such entry specifies that the node identified by
   R_dest_addr is estimated to be R_dist hops away from the local node,
   that the symmetric neighbor node with interface address R_next_addr
   is the next hop node in the route to R_dest_addr, and that this
   symmetric neighbor node is reachable through the local interface with
   the address R_iface_addr.  Entries are recorded in the routing table
   for each destination in the network for which a route is known.  All
   the destinations, for which a route is broken or only partially
   known, are not recorded in the table.

   More precisely, the routing table is updated when a change is
   detected in either:

     -    the link set,

     -    the neighbor set,

     -    the 2-hop neighbor set,

     -    the topology set,

     -    the Multiple Interface Association Information Base,

   More precisely, the routing table is recalculated in case of neighbor
   appearance or loss, when a 2-hop tuple is created or removed, when a
   topology tuple is created or removed or when multiple interface
   association information changes.  The update of this routing
   information does not generate or trigger any messages to be
   transmitted, neither in the network, nor in the 1-hop neighborhood.

   To construct the routing table of node X, a shortest path algorithm
   is run on the directed graph containing the arcs X -> Y where Y is
   any symmetric neighbor of X (with Neighbor Type equal to SYM), the

Top      Up      ToC       Page 48 
   arcs Y -> Z where Y is a neighbor node with willingness different of
   WILL_NEVER and there exists an entry in the 2-hop Neighbor set with Y
   as N_neighbor_main_addr and Z as N_2hop_addr, and the arcs U -> V,
   where there exists an entry in the topology set with V as T_dest_addr
   and U as T_last_addr.

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

     1    All the entries from the routing table are removed.

     2    The new routing entries are added starting with the
          symmetric neighbors (h=1) as the destination nodes. Thus, for
          each neighbor tuple in the neighbor set where:

               N_status   = SYM

          (there is a symmetric link to the neighbor), and for each
          associated link tuple of the neighbor node such that L_time >=
          current time, a new routing entry is recorded in the routing
          table with:

               R_dest_addr  = L_neighbor_iface_addr, of the
                              associated link tuple;

               R_next_addr  = L_neighbor_iface_addr, of the
                              associated link tuple;

               R_dist       = 1;

               R_iface_addr = L_local_iface_addr of the
                              associated link tuple.

          If in the above, no R_dest_addr is equal to the main address
          of the neighbor, then another new routing entry with MUST be
          added, with:

               R_dest_addr  = main address of the neighbor;

               R_next_addr  = L_neighbor_iface_addr of one of the
                              associated link tuple with L_time >=
               current time;

               R_dist       = 1;

               R_iface_addr = L_local_iface_addr of the
                              associated link tuple.

Top      Up      ToC       Page 49 
     3    for each node in N2, i.e., a 2-hop neighbor which is not a
          neighbor node or the node itself, and such that there exist at
          least one entry in the 2-hop neighbor set where
          N_neighbor_main_addr correspond to a neighbor node with
          willingness different of WILL_NEVER, one selects one 2-hop
          tuple and creates one entry in the routing table with:

               R_dest_addr  =  the main address of the 2-hop neighbor;

               R_next_addr  = the R_next_addr of the entry in the
                              routing table with:

                                  R_dest_addr == N_neighbor_main_addr
                                                 of the 2-hop tuple;

               R_dist       = 2;

               R_iface_addr = the R_iface_addr of the entry in the
                              routing table with:

                                  R_dest_addr == N_neighbor_main_addr
                                                 of the 2-hop tuple;


     3    The new route entries for the destination nodes h+1 hops away
          are recorded in the routing table.  The following procedure
          MUST be executed for each value of h, starting with h=2 and
          incrementing 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_addr does not correspond to R_dest_addr of any
               route entry in the routing table AND its T_last_addr
               corresponds to R_dest_addr of a route entry whose R_dist
               is equal to h, then a new route entry MUST be recorded in
               the routing table (if it does not already exist) where:

                    R_dest_addr  = T_dest_addr;

                    R_next_addr  = R_next_addr of the recorded
                                   route entry where:

                                   R_dest_addr == T_last_addr

                    R_dist       = h+1; and

Top      Up      ToC       Page 50 
                    R_iface_addr = R_iface_addr of the recorded
                                   route entry where:

                                      R_dest_addr == T_last_addr.

          3.2  Several topology entries may be used to select a next hop
               R_next_addr for reaching the node R_dest_addr.  When h=1,
               ties should be broken such that nodes with highest
               willingness and MPR selectors are preferred as next hop.

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

               R_dest_addr  == I_main_addr  (of the multiple interface
                                            association entry)

          AND there is no routing entry such that:

               R_dest_addr  == I_iface_addr

          then a route entry is created in the routing table with:

               R_dest_addr  =  I_iface_addr (of the multiple interface
                                             association entry)

               R_next_addr  =  R_next_addr  (of the recorded
                                             route entry)

               R_dist       =  R_dist       (of the recorded
                                             route entry)

               R_iface_addr =  R_iface_addr (of the recorded
                                                route entry).

11.  Node Configuration

   This section outlines how a node should be configured, in order to
   operate in an OLSR MANET.

11.1.  Address Assignment

   The nodes in the MANET network SHOULD be assigned addresses within a
   defined address sequence, i.e., the nodes in the MANET SHOULD be
   addressable through a network address and a netmask.

Top      Up      ToC       Page 51 
   Likewise, the nodes in each associated network SHOULD be assigned
   addresses from a defined address sequence, distinct from that being
   used in the MANET.

11.2.  Routing Configuration

   Any MANET node with associated networks or hosts SHOULD be configured
   such that it has routes set up to the interfaces with associated
   hosts or network.

11.3.  Data Packet Forwarding

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



(page 51 continued on part 3)

Next RFC Part