Internet DraftINTERNET-DRAFT                                          Philippe Jacquet
IETF MANET Working Group                                Paul Muhlethaler
Expiration : 18 May 1999
Expiration: 7 August 2000                                    Amir Qayyum
                                              INRIA Rocquencourt, France
                                                        18 November 1998
                                                         7 February 2000

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

Status of this Memo

   This document is an Internet-Draft. 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.

   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 "work in
   progress."

   To view the entire

   The list of current Internet-Drafts, please check the
   ``1id-abstracts.txt" listing contained in the Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited. can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   This document describes a routing the Optimized Link State Routing (OLSR)
   protocol for mobile ad hoc networks. The protocol is based on an
   optimization of the pure link state algorithm. It
   uses algorithm tailored to the
   requirements of a mobile wireless LAN. The key concept used in the multi-point
   protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are
   the selected nodes which forward the broadcast packets during the
   flooding process. This technique substantially reduces the packet
   overhead as compared to calculate pure flooding mechanism where every node
   retransmits the route towards any
   destination packet when it receives the first copy of the
   packet. In OLSR protocol, the information flooded in the network
   "through" these multipoint relays is also "about" the multipoint
   relays. Hence, a second optimization is achieved here by minimizing
   the "contents" of the control packet flooded in the network. Hence,
   as contrary to the classic link state algorithm, only a small
   subset of links with the neighbor nodes are declared instead of all
   the links. This information is then used by OLSR protocol for route
   calculation, and therefore the routes contain only the MPRs as the
   intermediate nodes from Source to Destination. It results in
   providing the optimal routes (in terms of number of hops), and
   hence another optimization. The protocol is particularly suitable
   to
   for the large dense networks with high nodal mobility and
   topological changes.

Internet draft as the technique of multipoint relays
   works well in this context.

1. Introduction

   This Optimized Link State Routing       18 November 1998

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

   This routing protocol is developed to work with for the IMEP protocol. mobile adhoc networks. It uses the different functionalities provided by IMEP, like link
   status sensing with neighbors, multi-point relay forwarding, etc.

   The
   functions as a table driven or proactive protocol and exchanges
   topology information with other nodes of the network at regular
   intervals. It The nodes which are selected as a multipoint relay by
   some neighbor nodes announce this information periodically in their
   control messages. The protocol uses the multi-point multipoint relays to do
   efficient flooding of its control messages in the network. These In route
   calculation, these are only the multi-point multipoint relays which are used to form
   the route towards any destination in the network.

   Multi-point

   Multipoint relays are selected among the one hop neighbors with
   "symmetric" i.e. bi-directional link. Therefore, selecting the
   route through multi-point multipoint relays automatically avoids the problems
   associated with data packet transfer on uni-directional links; like
   the problem of getting the ACKnowledgement acknowledgement for the data packets at
   each hop, which cannot be received if there is a uni-directional
   link in the selected route.

Internet draft       Optimized Link State Routing       18 November 1998

   OLSR protocol is developed to work independently. But it can be
   modified to work with a protocol (like IMEP protocol [4]) which
   could provide common functionalities such as neighbor sensing,
   multipoint relaying, security authentication, etc.

2. Terminology OLSR terminology

   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.

   link

      A logical communication channel between two nodes over which
      they can communicate with each other.

   node

      A MANET router that implements

   holding time

      The lifetime associated to an entry in any table. That entry is
      kept in the table for a period equal to its holding time. If the
      entry is not refreshed during this Link State Routing
      protocol.

   multi-point period, it is removed from
      the table when its holding time expires.

   multipoint relay (MPR)

      A node which is selected by its one-hop neighbor node X to
      "re-transmit" all the broadcast packets that it will receive
      from X, provided that the same packet is not already received,
      and the hop count field of the packet is greater than zero.

   asymmetric link

   multipoint relay selector (MPR-S)

      A uni-directional *link* (not connection) between two node which has selected its one-hop neighbor
      nodes, i.e. node X can hear node Y, but node Y can not hear as its
      multipoint relay will be called the multipoint relay selector of
      node X. So the link X-Y is asymmetric from

   node X's perspective, and

      A MANET router that implements this link does not exist from node Y's perspective (as Y is not
      hearing X). Optimized Link State Routing
      protocol.

   symmetric link

      A bi-directional *link* (not connection) between two neighbor
      nodes, i.e. node X and node Y, both can hear each other. This
      bi-directional link can be a union of two oppositely-directed
      uni-directional connections using different interfaces.

   holding time

      The lifetime associated to an entry in any table. That entry is
      kept in

3. Applicability Section

   This section dictates the table for a period equal to its holding time. If characteristics of the
      entry is not refreshed during this period, it is removed from OLSR protocol, as
   specified in the table when its holding time expires.

Internet Applicability Statement draft       Optimized Link State Routing       18 November 1998

   refreshing an entry

      The holding time of the entry in the table is updated to a
      specified value <table_name>_HOLDING_TIME.

3. Applicability Section

   This section dictates the characteristics of the OLSR protocol, as
   specified in the Applicability Statement draft.

3.1 [6].

3.1. Networking Context

   The protocol is best suited to the large "dense" dense networks, as the
   optimization done using the multi-point multipoint relays works well in this
   context. More the network is dense and large, more optimization is
   achieved as compared to the normal link state algorithm. The
   thing which may restrict here is OLSR uses
   the size of hop-by-hop routing, i.e. each node uses its most recent
   information to route the topology table
   which is O(N**2), where N packet. So when a node is the number of nodes moving, its
   speed should be such that its movement could be followed in the network.
   (Although we have developed an algorithm which reduces *at
   least* its size neighborhood, to correctly route the packets to O(N) only). the
   destination.

   This protocol is best suited for the networks where the traffic is
   random and sporadic between "several" nodes (and NOT instead of being
   between a small specific set of nodes) nodes of the network, and network. The
   comparative performance of the protocol with a reactive protocol is
   still better if these <source, destination> [source, destination] pairs change with
   time. (These These changes
   will may initiate enormous substantial traffic (Query flooding)
   in case of source
   routing, reactive protocol, but nothing in OLSR, as the routes
   are maintained for each known destination all the time).

3.2 time.

3.2. Protocol Characteristics and Mechanisms

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

      No. It uses only bi-directional "links", links (like in 802.11), but
      these links may be composed of oppositely directed
      uni-directional "connections".

   * Does the protocol require the use of tunneling? (if so, how?)

      No.

   * Does the protocol require using some form of source routing? (if
   so, how?)

      No. The protocol uses hop-by-hop routing.

Internet draft       Optimized Link State Routing       18 November 1998

   * Does the protocol require the use of periodic messaging? (if so,
   how?)

      Yes. Periodically, all nodes each node in the network send a message
      containing the addresses of its multi-point relays. neighbors who has selected that
      node as a multipoint relay. This information helps other nodes
      to build routes to that node through these multi-point relays. multipoint relay
      selectors.

   * Does the protocol require the use of reliable or sequenced packet
   delivery? (if so, how?)

      No. As the TC packet is packets are sent periodically, it needs they need not to be sent
      reliably. TC Each packet not only contains a unique Packet Sequence
      Number, but it also contains the sequence number of for the most
      recent information (for example "MPR Sequence Number" in the "most-recent-information" (MPR SEQ NUM), TC
      packet), so UN-sequenced un-sequenced delivery of packets will also not
      create any problem.

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

      Yes. It provides support for routing through Each network interface is assigned a multi-technology
      routing fabric by using Router IDs (see IMEP draft). RID may be
      associated with more than one unique IP addresses, representing
      different physical interfaces. address.

   * Does the protocol provide support for multiple hosts per router?
   (if so, how?)

      Yes. As mentioned in the preceding question, The concept of RID [4] may be
      associated with used to associate to a single
      RID (which can also be a unique IP address) more than one IP addresses, and these IP address
      may
      addresses which represent different hosts associated to that the
      router.

   * Does the protocol support the IP addressing architecture? (if so,
   how?)

      Yes.

   * Does the protocol require link or neighbor status sensing (if so,
   how?)

      Yes. The OLSR protocol uses RIDs, but the mapping of RIDs to IP
      addresses is provided by IMEP through its NARP service. So in
      this sense, OLSR supports the IP addressing architecture.

   * Does the protocol require link or neighbor status sensing (if so,
   how?)

      Yes. The protocol requires requires the link status sensing. It needs to
      be notified when a bi-directional link fails with a neighbor, or
      when a neighbor with a bi-directional link is added. This service
      is provided by IMEP to OLSR.

Internet draft       Optimized Link State Routing       18 November 1998 sending/receiving periodic HELLO messages to/from
      one hop neighbors.

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

      No. All the routers in the network have their own routing tables
      and does not depend on any specific node (source, etc). node.

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

      No. But it decreases and increases the interval (within certain
      limits) of sending the TC packet periodically, depending upon
      the rate of link changes in its neighborhood.

   * Does the protocol function proactively? (if so, how?)

      Yes. It periodically sends the information about its multi-point multipoint
      relay set, selectors, which helps other nodes to build routes to it.

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

      As the protocol uses link state algorithm, so implicitly, the routing is loop-free.
      loop-free in a stable state.

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

      Yes, it can provide support for sleep period operation. To
      enable this feature, the protocol should select its multi-point multipoint
      relays from only among the "p-supporters" (power conservation
      supporters) i.e. the nodes which can (or agree to) store
      its packets while it is in sleep mode.

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

      No, not itself. But it uses It can use other protocols (like IMEP [4]) which provides
      provide authentication and security.

   * Does the protocol provide support for utilizing multi-channel,
   link-layer technologies? (if so, how?)

      Yes.

Internet draft       Optimized Link State Routing       18 November 1998 Each interface has a unique IP address.

4. Protocol Overview

   This protocol

   OLSR is developed to work with a proactive routing protocol for mobile adhoc networks.
   The protocol inherits the IMEP protocol. It uses
   various functionalities stability of the IMEP, specially the a link status
   information with the neighbors, multi-point relays selection state algorithm and
   forwarding, etc. It needs from
   has the IMEP protocol to provide advantage of having the
   information about

      - routes immediately available when
   needed due to its neighbors with which the status proactive nature. OLSR protocol is an
   optimization of the pure link is symmetric
        i.e. bi-directional
      - state protocol, tailored for the list of multi-point relays along with
   mobile adhoc networks. First, it reduces the sequence number size of their selection.

   This information is kept in the Neighbor Table, and is updated
   accordingly whenever the up to date information is passed from IMEP
   to this routing protocol (OLSR).

   The protocol is pro-active in nature, and by periodic exchange control
   packets: instead of
   messages, all links, it establishes declares only a subset of links
   with its routing table in which neighbors who are its multipoint relay selectors (see
   section 5 on Multipoint Relays). Secondly, it stores the
   information minimizes flooding of
   its control traffic by using only the route selected nodes, called
   multipoint relays, to each destination node in the network. diffuse its messages. This information is updated when

      - a change in technique
   significantly reduces the neighborhood is detected concerning number of retransmissions in a
        symmetric link; flooding
   or
      - a route to any destination is expired (because broadcast procedure.

   Apart from its normal periodic control messages, the
        corresponding topology entry is expired) or
      - a better (shorter) route protocol does
   not generate extra control traffic in response to link failures and
   additions. Thus it is found suitable for networks with a destination.

   The high rate of
   topological changes. As OLSR protocol relies on the multi-point relays, and calculates keeps the routes towards each destination through these nodes. To implement
   this, each node for all the
   destinations in the network periodically broadcast so the
   information protocol is beneficial for the
   traffic patterns where a large subset of its multi-point relays. Upon receipt network nodes are
   communicating with another large subset of this MPR
   information, each node calculates (or updates) nodes, and the route towards
   each destination. So these
   [source,destination] pairs are the multi-point relays which form
   the route towards any destination. also changing with time. The
   protocol does not do the source routing, instead it performs
   hop by hop routing.

Internet draft       Optimized Link State Routing       18 November 1998

5. Multi-point relays

   The idea of multi-point relays is particularly suited to minimize the flooding of
   broadcast messages in the network by reducing/optimizing large and dense networks, as the
   duplicate re-transmissions in
   optimization done using the same region. Each node multipoint relays works well in the
   network selects this
   context. More dense and large a set of nodes in its neighborhood, who will
   re-transmit its packets. This set of selected neighbor nodes network is, more optimization is
   called
   achieved as compared to the multi-point relays of that node. Each node selects its
   multi-point relay set normal link state algorithm.

   The protocol is designed to work in a completely distributed manner to cover all the nodes that are
   two hop away from it. The neighbors which are
   and thus does not in the MPR set,
   do read and process the packet but *do not* re-transmit this
   broadcast message. For more details about the multi-point relays,
   refer to the IMEP depend upon any central entity. The protocol [1], where the multi-point relays
   selection does
   not require a reliable transmission for its control messages: each
   node sends its control messages periodically, and forwarding is implemented.

6. Interface with IMEP

6.1 OLSR registration

   To be operational, OLSR will be registered with IMEP, as specified
   by the IMEP protocol, with the protocol type value equal to OLSR, can therefore
   sustain a
   handle to receive objects loss of some packets from IMEP (implementation dependent), an
   epitaph object as null (for the time being) and to time, which arrives
   very often in the Link-level mode
   of IMEP signaling support. It also request IMEP protocol radio networks due to provide
   LCSS (Link Connection Status Sensing) collisions or other
   transmission errors and MPR (Multi Point Relay)
   support.

6.2 IMEP Signalling Support

   For OLSR to perform problems. The protocol also does not need a
   sequenced delivery of its task messages, as each control message
   contains a sequence number of calculating the routes to any
   destination in most recent information. So the network, it does
   re-ordering at the receiving end can not require to know if a link
   is composed affect the functioning of bi-directional connections on
   the same physical
   interface or protocol. Furthermore, it provides support for the sleep mode
   operation, which is using two (or more) oppositely directed
   uni-directional connections on different interfaces to form a
   symmetric link between two one-hop neighbor nodes. All quite advantageous for the battery operated
   small terminals.

   OLSR protocol does not do the source routing. Instead it requires performs
   hop by hop routing, i.e. each node uses its most recent information
   to know is whether a link with route the packet. Hence, when a neighbor node is asymmetric or
   symmetric. So moving, its speed should
   be such that its movement could be followed in at least its
   neighborhood, to correctly route the time of registration, the "Link-level"
   signaling support will be indicated packets to IMEP, and OLSR will take the
   advantage of
   destination.

   The protocol does not require any change in the links composed IP format of multiple interface connections.

6.3 Connection Notification mode

   OLSR is sensitive
   packets and classical IP stack can be used as it is, since the
   protocol only impacts the routing table management.

5. Multipoint relays

   The idea of multipoint relays is to minimize the symmetric links with its one-hop
   neighbors. OLSR computes flooding of
   broadcast messages in the routes using network by reducing duplicate
   retransmissions in the multi-point relays, same region. Each node in the network
   selects a set of nodes in its neighborhood, which are retransmit its
   packets. This set of selected among neighbor nodes is called the one hop
   multipoint relay (MPR) set of that node. The neighbors with symmetric link
   only. So of node N
   which are *NOT* in its MPR set, read and process the UNI-directional connection notification mode will be
   demanded packet but do
   not retransmit the broadcast message received from IMEP.

Internet draft       Optimized Link State Routing       18 November 1998

6.4 Broadcast signaling modes

   OLSR will select Multiple Interface (MI) mode, node N.

   Each node selects its multipoint relay set among its one hop
   neighbors in order to be able
   to establish route to/through such a manner that it covers (in terms of radio range)
   all the nodes having different physical
   interfaces or technologies, but that are operating in two hops away. We define the same MANET.

6.5 Neighbor Broadcast Reliability

   OLSR will request BROADCAST (implicit) delivery for its control
   packets (TC packets) neighborhood of
   any node N as it does not need the reliable mode. The TC
   packets are sent periodically so if set of nodes which have a packet is lost, symmetric link to N. We
   define the
   information is assumed two hop neighborhood of N as the set of nodes which
   don't have a symmetric link to N but have a symmetric link to be passed in the successive packets.

7. Information data bases

   To perform
   neighborhood of N. The multipoint relay set of N (we can call as
   MPR(N) ) is an arbitrary subset of the task neighborhood of routing N which
   satisfies the packets, each node manages some
   tables. Each following condition: every node maintains four tables: Duplicate table, Neighbor
   table, Topology table and Routing table.

7.1 Duplicate Table

   In in the duplicate table, each node records two hop
   neighborhood of N must have a symmetric link toward MPR(N). The
   smaller the information about multipoint relay set is, the
   packets it has already received. This information helps more optimal is the
   routing protocol. [2] gives an analysis and example about
   multipoint relay selection algorithms.

   Each node to
   identify the already received packets, so that it does not waste
   time in processing again has a set of its neighbors which are called the packet, and silently discards
   "Multipoint Relay Selectors" of the
   packet. The node. A node obtain this
   information is recorded in the duplicate table as a
   duplicate entry.

   The duplicate table has from the following format periodic HELLO messages of its neighbors. A
   broadcast message intended to record these entries:

      1.     D_addr     D_seq     D_time
      2.     D_addr     D_seq     D_time
      3.       ,,         ,,        ,,

   Each entry be diffused in the table consists of D_addr, D_seq and D_time, which
   specifies that whole network
   coming from these MPR Selector neighbor nodes is assumed to be
   retransmitted by the packet with sequence number D_seq node. This set can change over time, which is already
   received from
   indicated by the selector nodes in their HELLO messages. Each node
   has a specific Multipoint relay Selector Sequence Number (MSSN)
   associated with the address D_addr. If the same packet
   is received again during the time D_time, this "duplicate" packet
   will be silently discarded without any processing. The D_time set. Whenever its MPR selector set is updated,
   the holding time of the entry in node also increments its MSSN.

   OLSR protocol relies on the table, upon expiry selection of which
   the entry is no longer valid multipoint relays, and hence removed. This life time of
   calculates the entries helps routes to keep a destination through these nodes, i.e.
   MPR nodes are selected as intermediate nodes. To implement this,
   each node in the size of network periodically broadcast the table limited, by
   discarding information
   describing which neighbors have selected it as a multipoint relay.
   Upon receipt of this "MPR Selectors" information, each node
   calculates or updates the old entries about route to each known destination. So
   principally, the route is a sequence of hops through the multipoint
   relays from source to the destination.

   Multipoint relays are selected among the one hop neighbors with
   "symmetric" i.e. bi-directional link. Therefore, selecting the
   route through multipoint relays automatically avoids the problems
   associated with data packet transfer on uni-directional links such
   as the problem of getting an acknowledgement for the data packets
   at each hop which are less likely
   to cannot be received again, after keeping these entries for if there is a sufficient
   time.

Internet draft       Optimized Link State Routing       18 November 1998

7.2 uni-directional
   link in the selected route.

6. Protocol functioning

   OLSR protocol carry out different functions which are required to
   perform the task of routing. Here we discuss these functionalities
   of the protocol.

6.1. Neighbor Table

   In sensing

6.1.1. HELLO message broadcast

   Each node must detect the neighbor table, 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 order to be considered valid.

   To accomplish this, each node records periodically broadcasts its HELLO
   messages, containing the information about its neighbors and their
   link status. These control packets are transmitted in the broadcast
   mode. These are received by all one-hop neighbors, and but they are
   *not relayed* to further nodes. A HELLO message contain:

      - list of addresses of the status neighbors to which there exists a
        valid symmetric link;
      - list of addresses corresponding to heard nodes, i.e., the
        nodes which are heard by this node (a HELLO has been received)
        but the link with these neighbors.
   This table is constructed from the information given by IMEP
   through Connection-notification and MPR information. not yet validated as symmetric
   The
   information is recorded list of neighbors in the Neighbor table as a HELLO packet can be partial, the rule
   being that all neighbor nodes are cited at least once within a
   predetermined refreshing period (HELLO_INTERVAL).

   The proposed format of a HELLO packet 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Destination Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Source Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |     Packet Sequence Number    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Packet Type  |    Unused     |      MPR Sequence number      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        Neighbor Status        |           Neighbor
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                Address            |        Neighbor Status        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

6.1.1.1. Description of the fields

   Destination address

      For all the HELLO packets, this 4-bytes address field is always
      set to the broadcast address of the network, so that when this
      packet is transmitted, each neighbor node get this information
      and hence update its neighbor table.

   Source address

      It is set to the address of the node transmitting this HELLO
      packet.

   Packet Length

      This field contains the length of the HELLO packet in bytes,
      starting from the Packet Type field, i.e., length of rest of the
      packet.

   Packet Sequence Number

      While generating the HELLO packet, the node will assign a unique
      identification number to this packet, and will put this number
      in the Sequence Number field. This sequence number will be
      different for all the packets originated by that node.

   Packet Type

      The Packet Type field is set to the HELLO_PACKET value.

   Unused

      This unused one byte field is reserved for the future use.

   MPR Sequence Number

      This field indicates the sequence number with which the most
      recent multipoint relay set is calculated by the sender node.

   [Neighbor Address, Neighbor Status]

      These pairs of fields contain, one by one, all the addresses of
      the neighbor nodes present in the neighbor table, along with
      their link status.

6.1.2.  HELLO message processing

   The HELLO messages permit each node to learn the knowledge of its
   neighborhood up to two hops. A node maintains a Neighbor table in
   which it records the information obtained from the HELLO messages,
   about its one hop neighbors, the status of the link with these
   neighbors, and a list of two hop neighbors that these one hop
   neighbors give access to. The information is recorded in the
   Neighbor table as a neighbor entry, which may have the following
   format to record these entries:

              N_MPR_seq
      1.  N_addr    N_status    N_2hop_list    N_time
      2.  N_addr    N_status    N_2hop_list    N_time
      3.    ,,         ,,            ,,          ,,
   Each entry in the table consists of N_addr, N_status, N_2hop_list,
   and N_time, which specifies that the node with address N_addr is a
   one-hop neighbor to this node, the status of the link between them
   is N_status, and this neighbor provides access to the two hop
   neighbors listed in N_2hop_list. The N_status can be ASYM_LINK,
   SYM_LINK or MPR_LINK. The link status as MPR_LINK implies that the
   link with the neighbor node N_addr is symmetric *AND* the node
   N_addr is selected as a multipoint relay by this node. Each
   neighbor entry has an associated holding time N_time, upon expiry
   of which it is no longer valid and hence removed.

   The neighbor table also contains a sequence number N_MPR_seq which
   specifies that the node keeping this neighbor table has selected
   its most recent MPR set with the sequence number N_MPR_seq. Every
   time a node selects or updates its multipoint relay set, this
   N_MPR_seq is incremented to a higher value.

   On reception of a HELLO message, the node updates the neighbor
   entry corresponding to the sender node address:

      1. If the entry already exists:

         1.1 the holding time of the entry is refreshed to
             NEIGHB_HOLD_TIME
         1.2 if the node finds its own address in one of the
             [Neighbor, Status] pairs in the HELLO message, it updates
             the status of the link to the sender node as SYM_LINK if
             it was ASYM_LINK before.

      2. Otherwise a new entry is recorded in the Neighbor table with:

         2.1 N_addr is set to the sender node address
         2.2 N_status is set to the value of ASYM_LINK (asymmetric
             link)
         2.3 N_2hop_list is filled with the list of addresses
             contained in the HELLO message in the [Neighbor, Status]
             pairs for which the Status is *NOT* asymmetric and which
             are not already present in the Neighbor table (i.e., they
             are not one-hop neighbors). If a node finds its own
             address in the [Neighbor, Status] pair, it does not
             register itself in the N_2hop_list, and it changes the
             link status to the sender node from ASYM_LINK to
             SYM_LINK.
         2.4 N_time is set to the value of NEIGHB_HOLD_TIME
   With information obtained from the HELLO messages, each node also
   construct its MPR Selector table, in which it puts the addresses of
   its one hop neighbor nodes which has selected it as a multipoint
   relay. The MPR Selector table may have the following format to
   record the entries:

                 MSSN
      1.  MS_addr    MS_seq_num    MS_time
      2.  MS_addr    MS_seq_num    MS_time
      3.     ,,          ,,          ,,

   Each entry in the table consists of MS_addr, MS_seq_num and
   MS_time, which specifies that the node with address MS_addr has
   selected this node as its multipoint relay with the MPR sequence
   number equal to MS_seq_num. Each entry has an associated holding
   time MS_time, upon expiry of which it is no longer valid and hence
   removed.

   A sequence number MSSN is associated to this table which specifies
   that the multipoint relay selector set of the node keeping
   this MPR Selector table is most recently modified with the sequence
   number MSSN. The node modifies its MPR Selector set according to
   the information it receives in the HELLO messages, and increment
   this sequence number on each modification.

   On the reception of a HELLO message, if a node finds its own
   address in the [Neighbor, Status] pair with the Status field equal
   to "MPR", then it updates the entry corresponding to the sender
   node's address in the MPR Selector table:

      1. If the entry exists already:

         1.1 if the MPR Sequence Number field of the HELLO message is
             greater than or equal to the MS_seq_num field of that
             entry, then the MS_time is refreshed to NEIGHB_HOLD_TIME.
         1.2 if the MPR Sequence Number field of the HELLO message is
             greater than the MS_seq_num field of that entry, the
             MS_seq_num field is updated to the value of MPR Sequence
             Number field of the HELLO message.

      2. Otherwise, a new entry is recorded in the MPR Selector table,
         with:

         2.1 MS_addr is set to the address of sender of the HELLO
             message
         2.2 MS_seq_num is set to the MPR Sequence Number field of the
             HELLO message
         2.3 MS_time is set to the value of NEIGHB_HOLD_TIME

6.2. Multipoint relay selection

   Each node of the network selects independently its own set of
   multipoint relays. Multipoint relays are used to flood the control
   messages of that node. The MPR set is calculated in a manner to
   contain a subset of one hop neighbors which covers all the two hop
   neighbors. By this we mean that the union of the neighbor sets of
   all MPRs contains the entire two hop neighbor set. In order to
   build the list of the two hop nodes from a given node, it suffices
   to track the list of symmetric link nodes found in the HELLO
   packets received by this node (this two-hop neighbor information is
   recorded in the neighbor table as N_2hop_list). Multipoint relays
   of a given node are declared in the subsequent HELLOs transmitted
   by this node, so that the information reaches the multipoint relays
   themselves. These selected multipoint relays are indicated in the
   HELLO messages with the link status as "MPR". The multipoint relay
   set is re-calculated when:

      - a change in the neighborhood is detected when either a
        symmetric link with a neighbor is failed, or a new neighbor
        with a symmetric link is added; or
      - a change in the two-hop neighbor set with symmetric link is
        detected.

   The MPR set need not be optimal, however it should be small enough
   to achieve the benefit of the multipoint relays. Multipoint relays
   is an optimization of the pure flooding mechanism; it is not
   essential that the multipoint relay set be minimal or optimal. But
   it is essential that it covers the two hop nodes. By default, the
   multipoint relay set can coincide with the whole neighbor set. This
   will be the case at network initialization. Each node will manage a
   dedicated sequence number in order to track the changes in its
   multipoint relay set. This sequence number will also appear, along
   with the MPR list, in the HELLO messages.

   We propose here a heuristic for the selection of multipoint relays
   [2]. We use the following terminology in describing this algorithm:

      MPR(x): Multipoint relay set of node x which is running this
              algorithm
      N(x):   One hop neighbor set of node x (containing only symmetric
              neighbors)
      N2(x):  Two hop neighbor set of node x (containing only symmetric
              neighbors of nodes in N(x) ). The two hop neighbor set
              N2(x) of node x does not contain any one hop neighbor of
              node x
      D(x,y): Degree of one hop neighbor node y (where y is a member
              of N(x) ), is defined as the number of symmetric one hop
              neighbors of node y EXCLUDING the node x and all the
              symmetric one hop neighbors of node x which exit also
              in N(y), i.e.,
                 D(x,y) = N(y) - x - N(x)

   The proposed heuristic is as follows:

      1. Start with an empty MPR(x)
      2. Calculate D(x,y), where y is a member of N(x), for all nodes
         in N(x)
      3. First select as MPRs those nodes in N(x) which provide the
         "only path" to reach some nodes in N2(x)
      4. While there still exist some nodes in N2(x) that are not
         covered by MPR(x):

         4.1 For each node in N(x), calculate the number of nodes in
             N2(x) which are not yet covered by MPR(x) and are
             reachable through this one hop neighbor;
         4.2 Select as a MPR that node of N(x) which reaches the
             maximum number of uncovered nodes in N2(x). In case of a
             tie, select that node as MPR whose D(x,y) is greater.

      5. To optimize, remove each node in MPR(x), one at a time, and
         check if MPR(x) still covers all nodes in N2(x)

   After selecting the multipoint relays from among the neighbors, the
   link status of the corresponding one hop neighbors is changed from
   SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in
   the Neighbor table is also incremented by one.

6.3. Multipoint relay information declaration

6.3.1. TC Packet Broadcast

   In order to build the topology information database needed for
   routing packets, each relay node broadcasts specific service
   packets called Topology Control (TC) packets. TC packets are
   forwarded like usual broadcast packets to all nodes in the network
   and take advantage of multipoint relays. Multipoint relays enable a
   better scalability of topology information [1].

   A TC message is sent by a node in the network at regular intervals
   to declare its MPR Selector set, i.e., the message contains the
   list of neighbors who have selected the sender node as a multipoint
   relay. The sequence number (MSSN) associated to this multipoint
   relay selector set is also sent with the list. The list of
   addresses can be partial in each TC packet due to maximum size
   limitation, but parsing must be complete within a certain
   refreshing period (TC_INTERVAL). The information diffused in the
   network by these TC packets 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 multipoint relay, does NOT generate the
   TC packet.

   The interval between the transmission of two TC packets depends
   upon whether the MPR Selector set is changed or not, since the last
   TC packet transmitted. If no change occur in the MPR Selector set,
   the TC packet is sent after its normal interval (TC_INTERVAL). When
   a change occur in the MPR Selector set, the next TC packet is sent
   after a pre-specified minimum interval (TC_MIN_INTERVAL),
   starting from the time the last TC packet was sent. If this much
   time has already elapsed, the next TC packet is transmitted
   immediately. After sending a TC packet with that minimum interval,
   the default value for the interval again becomes the normal
   interval (TC_INTERVAL) for sending TC packets, until the MPR
   Selector set is changed again.

   The proposed format of a TC packet 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Destination Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Source Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |    Packet Sequence Number     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Packet Type  |   Hop Count   |              MSSN             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Originator Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |               Multipoint Relay Selector Address               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |               Multipoint Relay Selector Address               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

6.3.1.1. Description of the fields

   Destination address

      For all the TC packets, this 4-bytes address field is always
      set to the broadcast address of the network, so that when this
      packet is diffused in the network, every node get this
      information and hence update its topology table.

   Source address

      It is set to the address of the node *transmitting*
      this TC packet. This field should not be confused with the
      Originator Address of the TC packet. Whenever a node
      "re-transmit" the TC packet, this field is updated to that
      transmitter node's address.

   Packet Length

      This field contains the length of the TC packet in bytes,
      starting from the Packet Type field, i.e., the length of rest of
      the packet.

   Packet Sequence Number

      While generating the TC packet, the "originator" node will
      assign a unique identification number to this packet, and will
      put this number in the Sequence Number field. This sequence
      number will be different for all the packets originated by that
      node, which will help to recognize the duplicate reception of
      the packets.

   Packet Type

      The Packet Type field is set to the TC_PACKET value.

   Hop Count

      This field will contain the maximum number of hops a TC packet
      can attain. Every time a TC packet is re-transmitted, this field
      is decremented by 1. When this field reaches zero, the TC packet
      is no more re-transmitted and is discarded.

   MPR Selector Sequence Number (MSSN)

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

   Originator Address

      This field contains the address of the node which has originally
      generated this TC packet to declare its multipoint relay selector's
      information. This field should not be confused with the Source
      Address field, which is changed each time to the address of the
      intermediate node which is "re-transmitting" this TC packet,
      while the Originator Address field in never changed in the
      retransmissions.

   Multipoint Relay Selector Address (MPR-S)

      This field contains the address of the node which has selected
      the Originator node (of the TC packet) as a multipoint relay.
      All the node addresses of the multipoint relay selectors of the
      Originator node are put in the TC packet, one after another. If
      the maximum allowed packet size (of IP protocol) is attained and
      there are still some multipoint relay selector addresses which
      remain in the MPR Selector set, then more TC packets will be
      generated, until all addresses in the multipoint relay selector
      set are transmitted.

6.3.2. TC Packet Processing

   In OLSR protocol, TC packets are sent in broadcast and are
   retransmitted by the selected nodes to diffuse the packet in the
   whole network. In this process, a node may receive more than once
   the same TC packet. To avoid the re-processing of the TC packet
   which was already received and processed, each node maintains a
   Duplicate table in which it records the information about the most
   recently received TC packets. The information is recorded in the
   Duplicate table as a Duplicate entry. The table may have
   the following format to record these entries:

      1.  D_addr    D_seq_num    D_time
      2.  D_addr    D_seq_num    D_time
      3.    ,,          ,,         ,,
   Each entry in the table consists of D_addr, D_seq_num and D_time,
   which specifies that a TC packet was received from the node with
   address D_addr, having the packet sequence number as D-seq_num.
   Each Duplicate entry has an associated holding time D_time, upon
   expiry of which it is no longer valid and hence removed.

   On reception of a TC packet, a node checks in its Duplicate table
   if it has already received the same packet or not. If it finds a
   corresponding entry, the packet is discarded. Otherwise, a new
   entry is recorded in the Duplicate table for this newly received TC
   packet, and the packet is then processed further. When a node
   receives a TC packet from its neighbor node with an asymmetric (or
   uni-directional) link, it does not register the packet in the
   Duplicate table neither it processes the packet.

   Each node of the network maintains a topology table, in which it
   records the information about the topology of the network obtained
   from the TC packets. Based on this information, the routing table
   is calculated. A node records information about the multipoint
   relays of other nodes in the network in its topology table has as a
   topology entry, which may have the following format to record these entries:

         --- N_MPR_seq --- format:

      1.   N_addr     N_status  T_dest    T_last    T_seq    T_time
      2.   N_addr     N_status  T_dest    T_last    T_seq    T_time
      3.    ,,        ,,        ,,       ,,

   Each entry in the table consists of N_addr T_dest, T_last, T_seq, and N_status,
   T_time which specifies that the node with address N_addr is a one-hop neighbor
   to this local T_dest has selected the node
   T_last as a multipoint relay and that the status node T_last has announced
   this information of its multipoint relay selector set with the link between them is
   N_status. N_status
   sequence number T_seq. Therefore, the node T_dest can be asymmetric, symmetric or MPR. reached in
   the last hop through the node T_last. Each topology entry has an
   associated holding time T_time, upon expiry of which it is no
   longer valid and hence removed.

   The link
   status as MPR specifies that entries in the link status topology table are recorded with the neighbor node
   N_addr topology
   information that is "symmetric" *AND* exchanged among the network nodes through TC
   packets. Upon receipt of a TC packet, the following procedure is
   executed to record the information in the topology table:

      1. If there exist some entry in the topology table whose T_last
         corresponds to the originator address of the TC packet and
         whose T_seq is greater in value than the MSSN in the received
         packet, then no further more, processing of this N_addr TC packet is also
   selected as a multi-point relay by this local node.

   Neighbor done
         and it is silently discarded (case: packet received out of
         order).

      2. If there exist some entry in the topology table also keeps a sequence number whose T_last
         corresponds to the originator address of the TC packet and
         whose T_seq is lesser in value N_MPR_seq which
   specifies than the MSSN in the received
         packet, then that topology entry is removed.

      3. For each of the local node keeping this neighbor table has
   selected its most recent MPR set with the sequence number
   N_MPR_seq. The nodes Selector address received in the MPR set are indicated TC
         packet:

         3.1 If there exist some entry in the neighbor topology table with their N_status equal whose
             T_dest corresponds to MPR. Every time a node selects
   or updates its multi-point relay set, this N_MPR_seq is incremented the MPR Selector address and the
             T_last corresponds to a higher value. This multi-point relay set is re-calculated each
   time when:

      - a change in the neighborhood is detected when either a
        symmetric link with a neighbor originator address of the TC
             packet, then the holding time T_time of that topology
             entry is failed, or refreshed to TOP_HOLD_TIME.

         3.2 Otherwise, a new neighbor
        with a symmetric link topology entry is added; or
      - a change recorded in the two-hop neighbor set (with either symmetric or
        asymmetric link)
             topology table whereas:

                - T_dest is detected.

   The selection of MPRs set to the MPR Selector address,
                - T_last is done by IMEP, and OLSR just uses that
   information as such.

Internet draft       Optimized Link State Routing       18 November 1998

7.3 Topology Table

   In set to the topology table, each node records originator address of the information about TC
                  packet,
                - T_seq is set to the
   topology value of MSSN received in the network, and on TC
                  packet,
                - T_time is set to the basis value of this, the routing TOP_HOLD_TIME.

6.4. Routing table is calculated.

   A calculation

   Each node records maintains a routing table which allows it to route the information about each
   packets for the other destinations in the network. The nodes which
   receive the TC packet parse and store some of the multi-point relays connected pairs
   of other nodes in the network in its topology table as a topology
   entry. The topology entries form [node, source] where "nodes" are recorded in the topology table in identified with the following format:

      1.   T_dest     T_last     T_seq    T_time
      2.   T_dest     T_last     T_seq    T_time
      3.     ,,         ,,         ,,       ,,

   Each entry
   addresses found in the TC packet list. The routing table consists of T_dest, T_last, T_seq, and
   T_time which specifies that is built
   from this database by tracking the connected pairs in a descending
   order. To find a path from a given origin to a remote node T_dest R, one
   has selected the node
   T_last as to find a multi-point relay connected pair (R,X), then a connected pair (X,Y),
   and so forth until one finds a node Y in the multi-point relay neighbor set with of the
   sequence number T_seq. Therefore,
   origin. In order to restrict to optimal paths, the node T_dest relay nodes will
   consider only the connected pairs on the minimal path. This
   selection can be reached done dynamically and with minimal storage
   facilities. The sequence numbers are used to detect connected pairs
   which have been invalidated by further topology changes. The
   information contained in the last hop through the node T_last.

   Each topology entry has an associated holding time T_time, upon
   expiry of database, which it has not been
   refreshed is no longer valid and hence removed.

7.4 Routing discarded.

   The routing table

   On the basis of is based on the information contained in the topology
   neighbor table and the neighbor table, a topology table. Therefore, if any of these
   tables is changed, the routing table is 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
      2.  R_dest    R_next    R_dist
      3.    ,,        ,,        ,,

   Each entry in the table consists of R_dest, R_next and R_dist,
   which specifies that the node identified by R_dest is estimated to
   be R_dist hops away from the local node, and that the one hop
   neighbor node with address R_next in the next hop node in the route
   to R_dest.

   The routing table is re-calculated each time the neighbor table or
   the topology table or both are changed.

Internet draft       Optimized Link State Routing       18 November 1998

8. Multi-point Relay Information Declaration

   A message the one hop
   neighbor node with address R_next is sent by each the next hop node in the network at regular intervals route
   to declare its multi-point relay set. This message is called TC
   (Topology Control) packet. The information diffused R_dest. Entries are recorded in the network
   by these TC packets will help table for each node to calculate its routing
   table. The interval between destination
   in the transmission of two TC packets
   depends upon whether network for which the MPR set route is changed or not, since known. All the last
   TC packet transmitted. If no change occur in destinations
   for which the MPR set, route is broken or partially known are not entered in
   the TC
   packet will be sent after MAX_TC_PKT_INTERVAL. When table.

   This routing table information is updated when

      - a change occur in the MPR set, the next TC packet will be sent after the
   MIN_TC_PKT_INTERVAL. Then the default value for the interval again
   becomes MAX_TC_PKT_INTERVAL, until the MPR set neighborhood is changed again.

   The proposed format of detected concerning a TC packet
        symmetric link;
      - a route to any destination 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Destination Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Source Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |  Packet Type  |   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Packet Sequence Number    |      MPR Sequence Number      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Originator Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Multi-point Relay Address                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   Multi-point Relay Address                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

8.1 Description of expired (because the
        corresponding topology entry is expired) or
      - a better (e.g. shorter) route is found for a destination.

   Therefore, the fields

   Destination address

      For all routing table is re-calculated locally each time the TC packets,
   neighbor table or the topology table or both are changed. The
   update of this 4-bytes address field routing table does not generate or trigger any
   packets to be transmitted, neither in the network, nor in the
   one-hop neighborhood.

   The following procedure is always
      set executed to calculate (or re-calculate)
   the broadcast address routing table :

   1. All the entries of the network, so that when this
      packet routing table are removed.

   2. The new entries are recorded in the table starting with the one
      hop neighbors (h=1) as the destination nodes. For each neighbor
      entry in the neighbor table, whose link status is diffused not
      asymmetric, a new route entry is recorded in the network, every node get this
      information routing table
      where R_dest and hence update its topology table.

Internet draft       Optimized Link State Routing       18 November 1998

   Source address

      It is R_next are both set to the address (Router ID) of the node *transmitting*
      this TC packet. This field should not be confused with
      neighbor and R_dist is set to 1.

   3. Then the
      Originator Address of new route entries for the TC packet. Whenever a node
      "re-transmit" destination nodes h+1 hops
      away are recorded in the TC packet, this field routing table. The following procedure
      is updated to that
      transmitter node's address (RID).

   Packet Length

      This field contains executed for each value of h, starting with h=1 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 length topology table, if its
             T_dest does not correspond to R_dest of the whole TC packet any route entry
             in bytes,
      starting from the Destination Address field.

   Packet Type

      The Packet Type field is set routing table AND its T_last corresponds to the TC_PACKET value.

   Hop Count

      This field will contain the maximum number R_dest
             of hops a TC packet
      can attain. Every time when route entry whose R_dist is equal to h, then a new
             route entry is recorded in the TC packet routing table where :

                - R_dest is re-transmitted,
      this field set to T_dest;
                - R_next is decremented by 1. When this field reaches zero, set to R_next of the TC packet route entry whose
                  R_dest is no more re-transmitted equal to T_last; and
                - R_dist is destroyed.

   Sequence Number

      While generating set to h+1.

   4. After calculating the TC packet, routing table, the "originator" node will
      assign a unique identification number to this packet, and will
      put this number topology table entries
      which are not used in calculating the Sequence Number field. This sequence
      number will routes may be different for all the removed, if
      there is a need to save memory space. Otherwise, these entries
      may provide multiple routes.

7. Packet forwarding

7.1. Data packet forwarding

   Data packets originated are relayed on a hop by that
      node, which will help to recognize hop basis. In the duplicate reception of source
   router and in any intermediate router, the packets.

   Originator Address

      This field contains next hop router is
   identified by the address entry of the node which has originally
      generated this TC destination in the host routing
   table.

   Whenever a data packet is received to declare route to a destination and
   its multi-point relay set.
      This TTL field should not be confused with the Source Address field,
      which is changed each time to the address of (in IP header) is greater than zero, the intermediate node which is "re-transmitting" this TC packet, while must
   look at the
      Originator Address final destination field in never changed.

Internet draft       Optimized Link State Routing       18 November 1998

   Multi-point Relay Sequence Number

      A sequence number is associated with the multi-point relay set
      and every time a node selects/updates its multi-point relay set,
      it increments this sequence number. This number packet. If the route is sent
   known, i.e. an entry is found in this
      MPR Sequence Number field of the TC routing table in which R_dest
   corresponds to the final destination, then the packet is
   transmitted to keep track of the
      most recent information. When a node receives next hop node. While forwarding a TC unicast
   packet, it
      can decide on the basis originator address, and the final destination address
   of this MPR Sequence Number field,
      whether the information about packets are not changed. The packet traverses the
   intermediate source and destination pair, hop by hop, until it
   reaches its final destination.

7.2. Topology Control (TC) packet forwarding

   TC packets are relayed by the multi-point multipoint relays of via the
      originator
   following rule:

      A node is more recent than that retransmits a TC packet only when it already have, or not.

   Multi-point Relay Address (MPR)

      This field contains the address of the receives its first
      copy from a node which is selected as
      a multi-point its multipoint relay by the Originator node (of the selector.

   When a TC packet).
      All the node addresses of packet is received and its hop count is greater than
   zero, then it is retransmitted by the multi-point multipoint relays of the
      Originator node are put in the TC packet, one after another. If
      the maximum allowed size of
   sender node. Before retransmitting, the TC packet (MAX_TC_PKT_SIZE) hop count is
      attained and there are still some multi-point relay addresses
      which remain in the MPR set, then more TC packets will be
      generated, with different "Packet Sequence Number" but having decremented by
   one.

8. Power Conservation or Sleep mode operation

   Power conservation mode is very desirable for the same "MPR Sequence Number", until all addresses in low capacity,
   battery operated small terminals. With the
      multi-point relay set are transmitted.

Note: This protocol is designed constraint on the power
   consumption, nodes may wish to work with IMEP protocol with
      multi-point relay conserve their battery power by
   going into "sleep mode". The sleep mode "enabled". Nevertheless, if it is not
      enabled may simply be a pause in
   the IMEP protocol (for what so ever reason), then
      instead operation of a node, or it may be some intermittent sleep and
   wake periods of multi-point relays, a node will declare all to economically use its
      neighbors with battery resources.

8.1. Sleep mode initiation

   When a symmetric link, in the TC packet. Nothing else
      will be required node plans to change go in this protocol sleep mode, it has to calculate stop sending its
      routes.

9 Information recording in the tables

9.1 Duplicate table

   Each time a packet
   periodic control messages:

      - HELLO messages: so that it is received no more selected as a multipoint
        relay by OLSR, the protocol checks if this
   packet its neighbor nodes, and
      - TC messages: so that it is already received earlier. no more used as an intermediate
        node while calculating a route.

   Then it looks its MPR Selector set. If the Originator Address of
   the packet corresponds to D_addr this set is not empty, it
   means that some of an entry in the duplicate
   table, its neighbors are using it as a multipoint
   relay, and the value of the Sequence Number field secondly, other nodes of the packet is network may calculate the same
   route to some destinations using this node as an intermediate
   node. In this case, the corresponding D_seq node can not go into sleep mode immediately
   because it is assumed to function as a multipoint relay of some
   node. The node must wait until its MPR Selector set becomes
   empty. As the duplicate entry, then
   the packet node is silently discarded and sending no further processing is done.

Internet draft       Optimized Link State Routing       18 November 1998

   Otherwise, a new duplicate entry is recorded more HELLOs, so it will not be
   selected as a multipoint relay further more, and hence the entries
   in the duplicate table
   with :

      - D_addr is MPR Selector set to will be expired.

   After terminating the Originator Address transmission of its periodic messages, the packet,
      - D_seq is set
   node has to the Sequence Number of the packet, and
      - D_time negotiate with its multipoint relays to keep its data
   packets while it is in sleep mode. The node has to keep only those
   MPRs in its MPR set which agree to keep its packets.

   To initiate the holding time of negotiation for the duplicate entries,
        which is power conservation mode, the
   node has to transmit a pre-specified value DUPLICATE_HOLD_TIME.

   The packet is then processed further.

9.2 Neighbor table power conservation (PC) message. This table PC
   message is updated broadcast to one hop neighbors only with packet type
   equal to PC_PACKET. It contains the information provided by the IMEP
   protocol through Link/Connection notification and MRA packets.
   Hence list of the entries will contain MPRs of the one hop neighbors as N_addr sender
   node, along with the link status N_status as asymmetric, symmetric or
   MPR. To keep this information up intended duration of the sleep period (in
   milliseconds). The Request/Reply field is set to date, IMEP 1 by the sender
   node who is supposed requesting to
   update this information whenever keep its packets while it is in sleep
   mode.

   The proposed format of a PC packet 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Destination Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Source Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Packet Length         |     Packet Sequence Number    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Packet Type  | Request/Reply |     Sleep period (in msec)    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          MPR Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          MPR Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   When a change occur in its neighborhood
   (concerning node receives a symmetric link only) or PC message with Request/Reply field equal to
   1, then:

      1. if its MPR set.

9.3 Topology table

   The entries in the topology table are recorded with set contains the routing
   information that is exchanged among sender node's address, this
         address must be removed from the network nodes through TC
   packets. On MPR set and the receipt of a TC packet, receiver
         must re-calculate its MPR set;
      2. if the following procedure receiver is
   executed to record the information listed as an MPR address in the topology table:

   Step 1:

      If PC
         message, it will decide if it can keep the Originator Address of packets for the received TC packet corresponds
      to T_dest of a topology entry in
         sender node during the topology table, then

         If T_seq of that topology entry is higher sleep period mentioned in value than the
         MPR Sequence Number field of the received TC packet, PC
         message:

            2.1 if it does not agree to keep sender node's packets,
                then no further processing of the TC packet PC message is done, and done;
            2.2 otherwise, if it is
         silently discarded.

         If T_seq of that topology entry precedes the value of the
         sequence number field of the received TC packet, that
         topology entry is removed.

   Step 2:

      For each MPR address in the received TC packet

         If the MPR Address corresponds agrees to keep the T_last packets of the topology
         entry whose T_dest corresponds to
                sender node for the Originator Address of intended sleep mode duration,
                then:

                   2.2.1 it will add the TC packet, then intended sleep period time to
                         the holding time T_time of that the entry is
         updated to TOPOLOGY_HOLD_TIME.

Internet draft       Optimized Link State Routing       18 November 1998

         If in the MPR address does not corresponds to T_last of any
         topology entry whose T_dest corresponds
                         Selector table corresponding to the Originator
         Address of the TC packet, then

            a new topology entry is recorded in the topology table
            with:

            - T_dest is set sender
                         node's address
                   2.2.2 it will reply to the Originator Address of sender node with a PC
                         message in unicast, with the TC
              packet,
            - T_last is Request/Reply
                         field set to the MPR address,
            - T_seq is set 2. The sleep period field will
                         be equal to that in the value received PC message
                         and there will be no list of MPR Sequence Number in Addresses.

   When the TC packet,
            - T_time is set node who intends to go in sleep mode receives a reply of
   its PC message from one or more of its MPRs, it should keep only
   these addresses (of the TOPOLOGY_HOLD_TIME

9.4 Routing MPRs) in its neighbor table

   Each and remove all
   others. It can now go in sleep mode.

   If the node maintains does not receive a routing table with reply after one HELLO_INTERVAL, it which allows
   can re-send its PC message and wait for the reply. If still no
   reply is received, the node can not go in sleep mode, OR, it can go
   in sleep mode with a risk to
   route loose its own packets. A "sleeping"
   node does not affect the routing of packets for which are not destined
   to it. In OLSR, packets are routed hop-by-hop. So the other destinations in neighbor
   nodes of the network. sleeping node will not send the packets to it, and
   will route the packet towards its destination according to their
   own most recent information.

8.2. Wake up procedure

8.2.1. Wake up to resume activities after sleep mode

   The
   routing table is based on sleeping node must wake up before the information contained sleep period (mentioned
   in its PC message) expires. It should start its normal operation,
   i.e. sending periodic HELLO and TC messages. At the same time, it
   should look in its neighbor table and the topology table. Therefore, if any addresses of its MPR nodes
   who agreed to keep its packets. Then it should request those
   neighbors to send these tables is
   changed, kept packets, by sending a PC message to
   all of them, one after another. This PC message will have the routing table is re-calculated
   Request/Reply field equal to update the route
   information about each destination in zero and the network.

   The following procedure is executed sleep period equal to calculate (or re-calculate)
   the routing table in case of
   zero. A node who receives a change in PC message containing Request/Reply
   field equal to zero the neighbor table or sleep period equal to zero, should send all
   the
   topology table or both:

   1. All packets, which it has kept for the entries sender node.

   This method of requesting its kept packets to its MPRs one by one,
   when a node wakes up, may avoid the routing table are removed.

   2. Then new entries are recorded in the table high packet flow towards a node
   who wakes up.

   If a node A is keeping packets for each destination
      in any node B, and the network for which intended
   sleep period arrives at its expiration, node A should see if the
   route to node B is known. All the
      destinations for which known, i.e. if node B is alive or not. If the
   route is broken or partially known known, all the packets are not entered in send to the table. This information is recorded node B, otherwise,
   node A will discard all packets of node B.

8.2.2. Wake up in the following manner:

         2.1 intermittent wake-and-sleep periods

   The new entries are recorded sleeping node must wake up before the sleep period (mentioned
   in its PC message) expires. As the table starting node intends to re-go into sleep
   mode after a small wake up period, it does not resume sending HELLO
   and TC packets. To collect its packets from its MPR neighbors, it
   will send a PC message with the one hop neighbors as the destination nodes.

             For each neighbor entry in Destination address set to the neighbor table, whose link
             status is symmetric (or MPR), a new route entry is
             recorded in
   broadcast address, the routing table where R_dest Request/Reply field set to zero and R_next are
             both the
   Sleep period field set to the address zero. There will be no list of the neighbor and R_dist is set MPR
   addresses attached to 1.

         2.2 Then the new route entries for PC packet. A node who receives this PC
   message will send all the destination nodes k+1
             hops away, where k>0, are recorded in packets it has kept for the routing table.

Internet draft       Optimized Link State Routing       18 November 1998

             For each topology entry in sender node
   of the topology table, PC message.

   To go again into sleep mode after processing (and replying to, if its
             T_dest does not correspond
   necessary) the packets it receives, the node has to R_dest of any route entry
             *AND* re-negotiate
   with its T_last corresponds to R_dest MPRs as mentioned in section 8.1. (Future versions of a route entry
             whose R_dist is k, then a new route entry is recorded the
   draft may explain if sending an intermittent wake-and-sleep pattern
   in the routing table where R_dest is set to T_dest, R_next
             is set to R_next first negotiation could avoid the repetitive negotiations).

   To end the intermittent wake-and-sleep operation, the node should
   follow the procedure of section 8.2.1 when it wakes up.

9.  Proposed values for the route entry whose R_dest is
             T_last, and R_dist is set to k+1.

   3. After calculating constants

   This section list the routing table, values for the topology table entries
      which are not constants used in calculating the routes may be removed, if
      there is a need to save memory space. Otherwise, these entries
      may provide redundant routes.
   description of the protocol.

   HELLO_INTERVAL   = 2 seconds
   TC_INTERVAL      = 5 seconds
   TC_MIN_INTERVAL  = 2 seconds

   NEIGHB_HOLD_TIME = 6 seconds
   TOP_HOLD_TIME    = 15 seconds

   HELLO_PACKET     = 1
   TC_PACKET        = 2
   PC_PACKET        = 3

   ASYM_LINK        = 1
   SYM_LINK         = 2
   MPR_LINK         = 3

10. References

   1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre.  Increasing
      reliability 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, 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, August 21, 1998 Work in progress.

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

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

11. Authors' Addresses

   Philippe Jacquet

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

   Paul Muhlethaler Amir.Qayyum@inria.fr

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

   Amir Qayyum Philippe.Jacquet@inria.fr

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