INTERNET-DRAFT Philippe Jacquet
IETF MANET Working Group Paul Muhlethaler
Expiration: 24 May 2001 Amir Qayyum
Anis Laouiti
Laurent Viennot
Thomas Clausen
INRIA Rocquencourt, France
24 November 2000
Optimized Link State Routing Protocol
draft-ietf-manet-olsr-03.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026 except that the right to
produce derivative works is not granted.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in
progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document describes the Optimized Link State Routing (OLSR)
protocol for mobile ad hoc networks. The protocol is an
optimization of the pure link state algorithm tailored to the
requirements of a mobile wireless LAN. The key concept used in the
protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are
selected nodes which forward broadcast packets during the flooding
process. This technique substantially reduces the packet overhead
as compared to pure flooding mechanism where every node retransmits
the 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. Thus a
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 1]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
second optimization is achieved by minimizing the "contents" of the
control packets 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 the OLSR protocol for route
calculation. As a consequence hereof, the routes contain only the
MPRs as intermediate nodes from a Source to a Destination. OLSR
provides optimal routes (in terms of number of hops). The protocol
is particularly suitable for large and dense networks as the
technique of multipoint relays works well in this context.
Contents
Status of This Memo 1
Abstract 1
1. Introduction 3
2. Changes 3
3. OLSR terminology 4
4. Applicability Section 5
4.1 Networking Context 5
4.2 Protocol Characteristics and Mechanisms 5
5. Protocol Overview 7
6. Multipoint relays 9
7. Protocol functioning 10
7.1 Packet format 10
7.1.1 Packet Header 11
7.1.2 Message Header 12
7.1.3 Packet Processing 12
7.2 Neighbor sensing 13
7.2.1 HELLO message broadcast 13
7.2.2 HELLO message processing 16
7.3 Multipoint relay selection 19
7.4 Multipoint relay information declaration 20
7.4.1 TC message broadcast 20
7.4.2 TC message processing 23
7.5 Routing table calculation 25
7.6.Link layer notification 27
8. Packet Forwarding 27
8.1 Data packet forwarding 27
8.2 OLSR message forwarding 28
9. Proposed values for constants 28
10. References 29
11. Authors' addresses 30
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 2]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
1. Introduction
This Optimized Link State Routing protocol inherits the concept of
forwarding and relaying from HIPERLAN (a MAC layer protocol) which
is standardized by ETSI [3]. The OLSR protocol is developed in the
IPANEMA project (part of Euclid program) and in the PRIMA project
(part of RNRT program).
This protocol is developed for mobile ad hoc networks. It operates
as a table driven or proactive protocol and exchanges topology
information with other nodes of the network at regular intervals.
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 multipoint relays to facilitate
efficient flooding of control messages in the network. In route
calculation, the multipoint relays are used to form the route from
a given node to any destination in the network.
Multipoint relays are selected by a node among its 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 the
link-layer acknowledgement for the data packets at each hop)
The OLSR protocol is developed to work independently from other
protocols. But it can be adapted to operate with a protocol (like
IMEP [4]) which could provide common functionalities such as
neighbor sensing, multipoint relaying, security authentication,
etc.
2. Changes
Major changes from version 02 to version 03
- Introduction of assigned port number for use with OLSR
- The packet format now uses "message length" rather than an
offset to the next message
- Optional section describing how link-layer notifications
can be utilized included.
Major changes from version 01 to version 02
- Introduction of a unified packet format for encapsulation of
all messages being exchanged between nodes. This also serves
to facilitate extensions in future versions of the protocol
(i.e. introduction of new protocol messages) without breaking
backwards compatibility.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 3]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
- Removal of "Power Conservation" from this draft. Power
Conservation may be considered as an extension to the basic
routing capabilities, and the information is therefore moved
to draft-ietf-manet-olsr-extensions-00.txt.
3. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC2119 [9].
The OLSR protocol uses the following terminology, in addition to
the terms defined in [5].
connection
A communication channel or medium *on the same physical
interface*, over which the nodes can communicate with each
other.
holding time
The lifetime associated with an entry in any table. An entry is
kept in the table for a period of time, equal to its holding
time. If the entry is not refreshed during this period, it is
removed from the table when the 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 receives from X,
provided that the same packet is not already received, and the
hop count field of the packet is greater than zero.
multipoint relay selector (MPR-S)
A node which has selected its one-hop neighbor, node X, as its
multipoint relay, will be called a multipoint relay selector
of node X.
node
A MANET router which implements this Optimized Link State
Routing protocol.
symmetric link
A bi-directional *link* (not connection) between two neighbor
nodes, i.e. node X and node Y where both can hear each
other. This bi-directional link can be a union of two
oppositely-directed uni-directional connections using different
interfaces.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 4]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
4. Applicability Section
This section dictates the characteristics of the OLSR protocol as
specified in the Applicability Statement draft [6].
4.1. Networking Context
The protocol is best suited to large and dense networks, as the
optimization achieved using the multipoint relays works well in
this context. The larger and more dense a network, the more
optimization can be achieved as compared to the normal link state
algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its
most recent information to route packets. Thus when a node is
moving, its speed should be such that its movement could be
followed in *at least* its neighborhood, in order to correctly
route packets to the destination.
This protocol is best suited for networks where the traffic is
random and sporadic between "several" nodes rather than being
almost exclusively between a small specific set of nodes in the
network. The performance of the protocol when comparing to a
reactive protocol is even better if these [source, destination]
pairs change with time [8]. Such changes may initiate substantial
traffic (Query flooding) in case of reactive protocol, but nothing
in OLSR, as the routes are maintained for each known destination
all the time.
4.2. Protocol Characteristics and Mechanisms
* Does the protocol provide shortest path routes ?
Yes.
* Does the protocol provide support for unidirectional links? (if
so, how?)
No. It uses only bi-directional 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.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 5]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
* Does the protocol require the use of periodic messaging? (if so,
how?)
Yes. Periodically, each node in the network sends a message
containing the addresses of the neighbors which have selected
that node as a multipoint relay. This information enables other
nodes to build routes to that node through the multipoint
relays.
* Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?)
No. As the packets are sent periodically, they need not be sent
reliably. Each packet not only contains a unique Packet Sequence
Number, but it also contains the sequence number for the most
recent information (for example "MPR Sequence Number" in the TC
packet), so 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. Each network interface is assigned a unique IP address.
* Does the protocol provide support for multiple hosts per router?
(if so, how?)
Yes. The concept of RID [4] may be used to associate to a single
RID (which can also be a unique IP address) more than one IP
addresses which represent different hosts associated to 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 protocol requires the link status sensing. This service
is provided by sending/receiving periodic HELLO messages to/from
one hop neighbors.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 6]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
* Does the protocol depend on a central entity? (if so, how?)
No. All the routers in the network have their own routing tables
and do not depend on any specific 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 multipoint
relay selectors, which helps other nodes to build routes to it.
* Does the protocol provide loop-free routing? (if so, how?)
As the protocol uses a link state algorithm, the routing is
loop-free when in a stable state.
* Does the protocol provide for sleep period operation? (if so, how?)
Yes, OLSR can provide support for sleep period operation. To
enable this feature, a node should select its multipoint relays
from among those neighbors 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. It can use other protocols (like IMEP [4]) which
provide authentication and security.
* Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?)
Yes.
5. Protocol Overview
OLSR is a proactive routing protocol for mobile ad hoc networks.
The protocol inherits the stability of a link state algorithm and
has the advantage of having the routes immediately available when
needed due to its proactive nature. OLSR is an optimization over
the pure link state protocol, tailored for mobile ad hoc networks.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 7]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
Firstly, it reduces the size of the control packets: rather than
declaring all links, a node declares only a subset of links with
its neighbors, namely the links to those nodes which are its
multipoint relay selectors (see section 6 on Multipoint Relays).
Secondly, OLSR minimizes flooding of control traffic by using only
selected nodes, called multipoint relays, to diffuse its messages.
This technique significantly reduces the number of retransmissions
in a flooding or broadcast procedure.
The protocol MAY optimize the reactivity to topological changes by
reducing the time interval for periodic control message
transmission. Furthermore, as OLSR protocol keeps the routes for
all destinations in the network, the protocol is beneficial for
traffic patterns where a large subset of nodes are communicating
with another large subset of nodes, and where the
[source,destination] pairs are changing over time. The protocol is
particularly suited for large and dense networks, as the
optimization done using the multipoint relays works well in this
context. The larger and more dense a network, the more optimization
can be achieved as compared to the normal link state algorithm.
The protocol is designed to work in a completely distributed manner
and thus does not depend on any central entity. The protocol does
NOT REQUIRE reliable transmission for control messages: each node
sends control messages periodically, and can therefore sustain an
occasional loss of some packets. Such losses occur very often in
the radio networks due to collisions or other transmission
problems. Also, the protocol does NOT REQUIRE sequenced delivery of
messages. Each control message contains a sequence number which is
incremented for each message. Thus the recipient of a control
packet can easily identify which information is newer - even if
messages have been re-ordered while in transmission.
Furthermore, OLSR provides support for protocol extensions such as
sleep mode operation, multicast-routing etc. Such extensions may be
introduced as additions to the protocol without breaking backwards
compatibility with earlier versions.
OLSR performs hop by hop routing, i.e. each node uses its most
recent information to route the packet. Hence for OLSR to be able
to route packets, the speed of mobile nodes should be limited such
that their movements can be tracked, at least by their neighborhood.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 8]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
OLSR does NOT REQUIRE any changes to the format of IP packets. Thus
any existing IP stack can be used as it is: the protocol only
interacts with routing table management.
6. Multipoint Relays
The idea of multipoint relays is to minimize flooding of broadcast
messages in the network by reducing duplicate retransmissions in
the same region. Each node in the network selects a set of nodes in
its neighborhood which may retransmit its packets. This set of
selected neighbor nodes is called the multipoint relay (MPR) set of
that node. The neighbors of node N which are *NOT* in its MPR set,
receive and process broadcast messages but do not retransmit
broadcast messages received from node N.
Each node selects its MPR set among its one hop neighbors. This set
is selected such that it covers (in terms of radio range) all the
nodes that are two hops away. The neighborhood of any node N can be
defined as the set of nodes which have a symmetric link to N. The
two hop neighborhood of N can be defined as the set of nodes which
don't have a symmetric link to N but have a symmetric link to the
neighborhood of N. The multipoint relay set of N, denoted as MPR(N),
is then an arbitrary subset of the neighborhood of N which
satisfies the following condition: every node in the two hop
neighborhood of N must have a symmetric link toward MPR(N). The
smaller the multipoint relay set is, the more optimal is the
routing protocol. [2] gives an analysis and example about
multipoint relay selection algorithms.
Each node maintains information about a set of its neighbors. This
is the set of neighbors, called the "Multipoint Relay Selectors",
which have selected the node as a MPR. A node obtain this
information from the periodic HELLO messages received from the
neighbors. A broadcast message, intended to be diffused in the
whole network, coming from these MPR Selector neighbor nodes is
assumed to be retransmitted by the node. This set can change over
time (i.e. when a node selects another MPR-set) and is indicated by
the selector nodes in their HELLO messages. Each node has a
specific Multipoint relay Selector Sequence Number (MSSN)
associated with this set. Whenever its MPR selector set is updated,
the node also increments its MSSN.
OLSR relies on selection of multipoint relays, and calculates the
routes to a destination through these nodes. I.e. MPR nodes are
selected as intermediate nodes in the path between a source and a
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 9]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
destination. To implement this, each node in the network
periodically broadcast the information describing which neighbors
have selected it as a multipoint relay. Upon receipt of this "MPR
Selectors" information, each node calculates or updates the 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.
7. Protocol Functioning
In this section we describe the details of the protocol
functioning. This includes descriptions of the format and contents
of the packets being exchanged by routers, the algorithms (e.g. for
packet handling and routing table calculation) and suggested data
structures internally in each router.
7.1. Protocol and Port Number
Packages in OLSR are communicated using UDP. Port 698 has been
assigned by IANA for exclusive usage by the OLSR protocol.
7.1. Packet Format
OLSR communicates using an unified packet format for all data
related to the protocol. Inspired by the concept of "extension
headers" from IPv6, the purpose of this is to facilitate
extensibility of the protocol without breaking backwards
compatibility as well as to provide an easy way of piggybacking
different "types" of information into a single transmission. These
packets are embedded in UDP datagrams for transmission over the
network. The present draft uses IPv4 addresses. The support for
IPv6 will be described in a future draft.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 10]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
The basic layout of any packet in OLSR will be 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Reserved for future use |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |B| Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: :
: MESSAGE :
: :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |B| Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: :
: MESSAGE :
: :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
(etc)
7.1.1. Packet Header
Packet Length
The length (in bytes) of the packet
Reserved for future use
MUST be set to '0000000000000000' to be in compliance with this
version of the draft.
The information in the header of this packet is equivalent to the
information obtainable from the UDP header.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 11]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
7.1.2. Message Header
Message Type
This field indicates which type of message are to be found in
the "MESSAGE" partition. Message types in the range of 0-127 are
reserved for messages in this draft and in
draft-ietf-manet-olsr-extensions-00.txt.
B
This field indicates to a node whether the message is meant for
diffusion into the entire network. This enables a node to
forward messages correctly, even if it doesn't recognize the
"Message Type".
Reserved
MUST be set to '0000000' to be in compliance with this
version of the draft.
Message Size
This field gives the size of this message, measured from the
beginning of the "Message Type" field and until the beginning
of the next "Message Type" field (or - if there are no
following messages - the end of the packet).
7.1.3. Packet Processing
Upon receiving such a basic packet, the protocol parser examines
each of the "extension headers". Based on the value of the "Message
Type" field, the parser can determine the faith of the data portion
of the message:
1. If the data are of a type which the receiving node can
process, then this data is processed.
2. Otherwise, if the "Message Type" indicates a type, unknown to
the node, the message SHOULD silently be dropped.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 12]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still be
able to maintain compatibility with older implementations. The two
REQUIRED message types for OLSR are:
- HELLO-messages, performing the task of neighbor sensing.
- TC-messages, performing the task of multipoint relay
information declaration.
Extensions may e.g. be PC-messages for enabling power conservation
/ sleep mode, multicast routing, gateway announcements etc.
7.2. Neighbor sensing
7.2.1. HELLO message broadcast
Each node should detect the neighbor nodes with which it has a direct
and symmetric link. The uncertainties over radio propagation may
make some links asymmetric. Consequently, all links MUST be checked
in both directions in order to be considered valid.
To accomplish this, each node broadcasts HELLO messages, containing
information about neighbors and their link status. The link status
may either be "symmetric", "heard" (asymmetric) or "MPR".
"Symmetric" indicates, that the link has been verified to be
bi-directional, i.e. it is possible to transmit data in both
directions. "Heard" indicates that the node is hearing from a
neighbor, but it is not confirmed that this neighbor is also
hearing from the node. "MPR" indicates, that a node is selected by
the sender as multipoint relay. MPR status implies that the link is
symmetric too.
These control messages are broadcast to all one-hop neighbors, but
are *not relayed* to further nodes. A HELLO-message contains at a
minimum:
- a list of addresses of neighbors, to which there exists a
symmetric link;
- a list of addresses of neighbors, which have been "heard";
- a list of neighbors, which have been selected as multipoint
relays.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 13]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
The list of neighbors in a HELLO message can be partial (e.g. due
to message size limitations, imposed by the network), the rule
being that all neighbor nodes are cited at least once within a
predetermined refreshing period (HELLO_INTERVAL).
To accommodate for the above constraints, as well as to accommodate
for future extensions, an approach similar to the overall packet
format (see section 6.1) is taken. Thus the proposed format of a
HELLO message is:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Sequence Number | MPR Sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
(etc)
This is sent as the data-portion of the general packet format
described in 6.1, with the "Message Type" set to HELLO_MESSAGE and
the broadcast field set to NO_BROADCAST.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 14]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
7.2.1.1. Description of the fields
Message Sequence Number
While generating a HELLO message, the node will assign a unique
identification number to this message. This number is put into
the Sequence Number field. This sequence number will be
different for all the messages originated by that node.
MPR Sequence Number
This field indicates the sequence number corresponding to the
most recent multipoint relay set, calculated by the sender node.
Link Type
This field specifies the type of link the sending node has to
the following list of neighbors. As a minimum, the following
three link types are REQUIRED by OLSR:
- ASYM_LINK - indicating that the links between the sender
and the neighbors in the following list are asymmetric
(i.e. the neighbor is "heard").
- SYM_LINK - indicating that the links between the sender
and the neighbors in the following list are symmetric.
- MPR_LINK - indicating, that the nodes in the following
list have been selected by the sender as multipoint
relays.
(Notice: this implies, that the links from the sender
of the HELLO and to the nodes in the list are symmetric).
It is possible to provide additional information by specifying
additional link-types, e.g. LOST_LINK - indicating that the link
between the sender and the neighbors in the following list has
been lost. Upon processing a HELLO message, a node silently
ignores link-types, which are unknown.
Reserved
This field is reserved for future usage, and MUST be set to
00000000 for compliance with this draft.
Link Message Size
The size of the link message, measured from the beginning of
the "Link Type" field and until the next "Link Type" field (or
- if there are no more link types - the end of the message).
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 15]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
Neighbor Address
The address of a neighbor.
7.2.2. HELLO message processing
The HELLO messages permit each node to acquire information about
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, a list of two hop neighbors that these one hop
neighbors give access to, and an associated holding time. The
information is recorded in the Neighbor table as a neighbor entry,
with the following field names:
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. This 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. Each entry in N_2hop_list consists
of a 2 hop neighbor address and associated holding time. The
N_status can be ASYM_LINK, SYM_LINK or MPR_LINK. A link status of
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 expiration of which it is no longer valid and hence
MUST be removed.
The node also contains a sequence number N_MPR_seq. This specifies
that the node 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, N_MPR_seq is incremented to a higher
value. This number is put into the HELLO messages as described in
6.2.1.
Upon receiving a HELLO message, the node should update the
neighbor entry corresponding to the sender node address (a node
may - e.g. for security reasons - wish to restrict updating the
neighbor-table, i.e. ignoring HELLO messages from some nodes):
1. If the entry already exists:
1.1 if the recipient of the HELLO has recorded the sender as
asymetric:
1.1.1 if the node finds its own address among the
addresses listed in the HELLO message (with Link
Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates
the status of the link to the sender node as
SYM_LINK and refreshes the N_time to
NEIGHB_HOLDING_TIME.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 16]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
1.1.2 otherwise, if the node does not find its own
address among the addresses listed in the HELLO
message, it refreshes the N_time to
NEIGHB_HOLDING_TIME.
1.2 otherwise, if the recipient of the HELLO has recorded
the sender as symetric (or MPR):
1.2.1 if the node finds its own address among the addresses
listed in the HELLO message (with Link Type
ASYM_LINK, SYM_LINK or MPR_LINK), it refreshes the
N_time to NEIGHB_HOLDING_TIME.
2. Otherwise, a new entry is recorded in the Neighbor table with:
- N_addr is set to the address of the sender node,
- N_status is set to the value of SYM_LINK if the node
finds its own address (with Link Type ASYM_LINK, SYM_LINK
or MPR_LINK) among the addresses listed in the HELLO
message, and to the value of ASYM_LINK otherwise
- N_time is set to the value of NEIGHB_HOLD_TIME
The N_2hop_list of the entry of the sender is updated, as
follows. For each address listed in the HELLO message with Link
Type SYM_LINK or MPR_LINK:
1. if an entry with this address exists in the N_2hop_list, then
the associated holding time is refreshed to NEIGHB_HOLD_TIME
2. otherwise an entry with this address and holding time
NEIGHB_HOLD_TIME is added to the N_2hop_list.
Based on the information obtained from the HELLO messages, each
node construct its MPR Selector table. In this table, the node
registers the addresses of those one hop neighbor nodes which have
selected the node as a multipoint relay. The MPR Selector table may
have the following format:
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 expiation of which it is no longer valid and
hence removed.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 17]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
A sequence number, MSSN, is associated with this table. This number
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 upon each modification.
Upon receiving a HELLO message, if a node finds its own address in
the address list with a link type of "MPR", it MUST update the
entry corresponding to the sender node's address in the MPR
Selector table:
1. If the entry already exists:
1.1 if the MPR Sequence Number field of the HELLO message is
greater than or equal to the MS_seq_num field of the
entry in the table, 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
2.4 MSSN is incremented to indicate that the MPR Selector
table has been changed.
If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through
absence of an acknowledgment), this MAY be used in addition to
the information from the HELLO-messages to maintain the neighbor
table and the MPR selector table.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 18]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
7.3. Multipoint relay selection
Each node in the network selects independently its own set of
multipoint relays. Multipoint relays are used to flood the control
messages of that node into the network. The MPR set is calculated
in a way such that it contains a subset of one hop neighbors which
covers all the two hop neighbors. This means, 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, make the
union of N_2hop_lists of all neighbors (with Link Type SYM_LINK or
MPR_LINK), then remove from this union the one-hop neighbors (with
Link Type SYM_LINK or MPR_LINK), and finally remove the node
itself. 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 a link status of
"MPR". The multipoint relay set is re-calculated when:
- a change in the neighborhood is detected, i.e. either a
symmetric link with a neighbor is failed, or a new neighbor
with a symmetric link is added; or
- a change is detected in the two-hop neighborhood such that
a symmetric link is either detected or broken between a
two-hop neighbor and a neighbor.
The MPR set needs not be optimal. However it SHOULD be small enough
to achieve the benefit of the multipoint relays. The concept of
multipoint relays is an optimization of a pure flooding mechanism.
It is not essential that the multipoint relay set be minimal or
optimal. But it is essential that all two-hop neighbors can be
reached through the selected MPR's. By default, the multipoint
relay set can coincide with the entire 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 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)
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 19]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
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, i.e.,
D(x,y) = number of elements of 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, process each node y in MPR(x), one at a time, and
if MPR(x) - {y} still covers all nodes in N2(x) then remove y from
MPR(x)
After selecting the multipoint relays 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.
7.4. Multipoint relay information declaration
7.4.1. TC Message Broadcast
In order to build the topology information database needed for
routing the packets, each relay node broadcasts specific service
messages called Topology Control (TC) messages. TC messages are
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 20]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
forwarded, like usual broadcast messages, to all nodes in the
network and take advantage of multipoint relays. Multipoint relays
enable a better scalability in the distribution of topology
information [1].
A TC message is sent by a node in the network to declare its MPR
Selector set. I.e., the TC message contains the list of neighbors
which have selected the sender node as a multipoint relay. The
sequence number (MSSN) associated with this multipoint relay
selector set is also sent with the list. The list of addresses can
be partial in each TC message (e.g. due to message size
limitations, imposed by the network), but parsing of all TC
messages describing a nodes MPR selector set MUST be complete
within a certain refreshing period (TC_INTERVAL). The information
diffused in the network by these TC messages will help each node to
calculate its routing table. A node which has an empty MPR Selector
set, i.e. nobody has selected it as a multipoint relay, MUST NOT
generate any TC message.
A node MAY transmit additional TC-messages to increase its
reactiveness to link failures. I.e. when a change to the MPR
selector set is detected and this change can be attributed to a
link failure, a TC-message SHOULD be transmitted after a shorter
interval than TC_INTERVAL.
The proposed format of a TC message is
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Sequence Number | MSSN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format
described in 6.1, with the "Message Type" set to TC_MESSAGE and
the broadcast field set to BROADCAST.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 21]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
7.4.1.1. Description of the fields
Message Sequence Number
While generating the TC message, the "originator" node will
assign a unique identification number to this message, and will
put this number in the Sequence Number field. This sequence
number will be different for all messages originated by that
node, and will be used to recognize duplicate reception of
messages.
MPR Selector Sequence Number (MSSN)
A sequence number is associated with the multipoint relay
selector set. 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 message
to keep track of the most recent information. When a node
receives a TC message, it can decide on the basis of this MPR
Sequence Number, whether or not the received information about
the multipoint relay selectors of the originator node is more
recent than what it already has.
Hop Count
This field will contain the maximum number of hops a TC message
can attain. Every time a TC message is re-transmitted, this
field is decremented by 1. When this field reaches zero, the TC
message is no more re-transmitted and is discarded.
Reserved
This field is reserved for future usage, and MUST be set to
'000000000000000000000000' for compliance with this draft.
Originator Address
This field contains the address of the node, which has
originally generated this TC message. This field MUST not be
confused with the source read in the UDP header, which is
changed each time to the address of the intermediate node which
is "re-transmitting" this TC message. The Originator Address
field is *never* changed in the retransmissions.
Multipoint Relay Selector Address (MPR-S)
This field contains the address of a node, which has selected
the Originator node (of the TC message) as a multipoint relay.
All addresses of the multipoint relay selectors of the
Originator node are put in the TC message. If the maximum
allowed message size (as imposed by the network) is reached
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 22]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
while there are still multipoint relay selector addresses which
which have not been inserted into the TC-message, more TC
messages will be generated until the entire MPR selector set has
been sent.
7.4.2. TC Message Processing
In the OLSR protocol, TC messages are broadcasted and are
retransmitted by the multipoint relays in order to diffuse the
messages in the entire network. In this process, a node MAY receive
the same TC message more than once. To avoid re-processing of a TC
message which was already received and processed, each node
maintains a Duplicate table. In this table, the node records
information about the most recently received TC messages. The
information is recorded in the Duplicate table as Duplicate
entries.
The table may have the following format:
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 message was received, originating from
the node with address D_addr, having the message sequence number
as D-seq_num. Each Duplicate entry also has an associated holding
time D_time, upon expiration of which it is no longer valid and
hence MUST be removed.
Upon receiving a TC message, a node checks in its Duplicate table
to see if it has already received the same message. If it finds a
corresponding entry, the message is discarded. Otherwise, a new
entry is recorded in the Duplicate table for this newly received TC
message, and the message is processed. When a node receives a TC
message from a neighbor node with which it has an asymmetric (or
uni-directional) link, it neither registers the message in the
Duplicate table nor it processes the message.
Each node in the network maintains a topology table, in which it
records the information about the topology of the network as
obtained from the TC messages. 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 as a topology entry, which may have the following format:
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 23]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
1. T_dest T_last T_seq T_time
2. T_dest T_last T_seq T_time
3. ,, ,, ,, ,,
Each entry in the table consists of T_dest, T_last, T_seq, and
T_time, which specifies that the node T_dest has selected the node
T_last as a multipoint relay and that the node T_last has announced
this information of its multipoint relay selector set with the
sequence number T_seq. Therefore, the node T_dest can be reached in
the last hop through the node T_last. Each topology entry has an
associated holding time T_time, upon expiration of which it is no
longer valid and hence MUST be removed.
The entries in the topology table are recorded with the topology
information that is exchanged through TC messages.
After registering a TC message in the duplicate table, 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 message and
whose T_seq is greater in value than the MSSN in the received
message, then no further processing of this TC message is
performed and it is silently discarded (case: message
received out of order).
2. All entries in the topology table with T_last corresponding
to the originator address of the TC message and whose T_seq
is lesser in value than the MSSN in the received message,
are removed.
3. For each of the MPR Selector address received in the TC
message:
3.1 If there exist some entry in the topology table whose
T_dest corresponds to the MPR Selector address and the
T_last corresponds to the originator address of the TC
message, then the holding time T_time of that topology
entry is refreshed to TOP_HOLD_TIME.
3.2 Otherwise, a new topology entry is recorded in the
topology table where:
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 24]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
- T_dest is set to this MPR Selector address,
- T_last is set to the originator address of the TC
message,
- T_seq is set to the value of MSSN received in the TC
message,
- T_time is set to the value of TOP_HOLD_TIME.
7.5. Routing table calculation
Each node maintains a routing table which allows it to route the
messages for the other destinations in the network. The routing
table is based on the information contained in the neighbor table
and the topology table. Therefore, if any of these tables is
changed, the routing table is 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 is the next hop node in the route
to R_dest. Entries are recorded in the table for each destination
in the network for which the route is known. All the destinations
for which the route is broken or partially known are not entered in
the table.
This routing table information is updated when a change is detected
in the neighbor table, or the topology table. The update
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 25]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
of this routing table does not generate or trigger any messages to
be transmitted, neither in the network, nor in the one-hop
neighborhood.
To construct the routing table of node X, a shortest path algorithm
is run on the directed graph containing the arcs X -> Y where Y is any
one hop neighbor of X (with Link Type SYM_LINK or MPR_LINK) and the
arcs U -> V where there exists an entry in the topology table with
V as T_dest and U as T_last.
The following procedure is given as an example to calculate (or
re-calculate) the routing table :
1. All the entries of the 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 Type is SYM_LINK or
MPR_LINK, a new route entry is recorded in the routing table
where R_dest and R_next are both set to the address of the
neighbor and R_dist is set to 1.
3. Then the new route entries for the destination nodes h+1 hops
away are recorded in the routing table. The following procedure
is executed for each value of h, starting with h=1 and
incrementing it by 1 each time. The execution will stop if no
new entry is recorded in an iteration.
3.1 For each topology entry in the topology table, if its
T_dest does not correspond to R_dest of any route entry
in the routing table AND its T_last corresponds to R_dest
of a route entry whose R_dist is equal to h, then a new
route entry is recorded in the routing table where :
- R_dest is set to T_dest;
- R_next is set to R_next of the route entry whose
R_dest is equal to T_last; and
- R_dist is set to h+1.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 26]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
7.6 Link layer notification
OLSR is designed to operate entirely alone, i.e. does not impose or
expect any specific information from the link layer. However, if
information from the link-layer is available, a node MAY use this
as described in this section.
If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through
absence of a link layer acknowledgment), this information is
used in addition to the information from the HELLO-messages to
maintain the neighbor table and the MPR selector
table. Subsequently, detection of a link failure through a
link-layer notification may trigger additional TC-messages to
increase the protocols reactiveness to link failures. I.e. when a
change to the MPR selector set is detected and this change can be
attributed to a link failure, a TC-message SHOULD be transmitted.
Thus, upon recieving a link-layer notification that the link
between a node and any neighbor is broken, the following actions
are taken:
1. if the link is broken to either a symetric or asymetric
neighbor, the entry for that neighbor is removed from the
neighbor table,
2. if the link is broken to a neighbor, which is selected as MPR,
the entry for that neighbor is removed from the neighbor
table and the MPR set is recalculated,
3. if the link is broken to a neighbor, which has selected this
node as MPR, the Multipoint Selector Set is updated and a
TC message SHOULD be generated.
8. Packet forwarding
8.1. Data packet forwarding
Data packets are relayed on a hop by hop basis. In the source
router and in any intermediate router, the next hop router is
identified by the entry of the destination in the host routing
table.
Whenever a data packet is received to route to a destination and
its TTL field (in IP header) is greater than zero, the node MUST
examine the final destination field in the packet. If the route is
known, i.e. an entry is found in the routing table in which R_dest
corresponds to the final destination, then the packet is
transmitted to the next hop node.
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 27]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
While forwarding a unicast packet, the originator address, and the
final destination address of the packets are not changed. The
packet traverses the intermediate source and destination pairs,
hop by hop, until it reaches its final destination.
8.2. Topology Control message forwarding
TC messages are relayed by the multipoint relays via the
following rule:
A node retransmits a TC message only when it is received from
one of its multipoint relay selector AND it is registered in the
duplicate table for the first time AND the hop count is greater
than zero.
Before retransmitting, the hop count is decremented by one.
9. Proposed values for the constants
This section list the values for the constants used in the
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
D_TIME = 30 seconds
HELLO_PACKET = 1
TC_PACKET = 2
ASYM_LINK = 1
SYM_LINK = 2
MPR_LINK = 3
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 28]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
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 RR-3898, 2000
3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN
type 1, functional specifications ETS 300-652, ETSI, June 1996
4. Corson et al. Internet MANET Encapsulation Protocol. Internet
draft, draft-ietf-manet-imep-spec-01.txt, Work 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.
7. S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, March 1997.
8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc
Network Protocols, INRIA research report RR-3965, 2000
Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 29]
INTERNET-DRAFT Optimized Link State Routing 24 November 2000
12. Authors' Addresses
Amir Qayyum
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5273
Email: Amir.Qayyum@inria.fr
Philippe Jacquet
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263
Email: Philippe.Jacquet@inria.fr
Anis Laouiti
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Anis.Laouiti@inria.fr
Laurent Viennot
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Laurent.Viennot@inria.fr
Thomas Clausen
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Thomas.Clausen@inria.fr
Jacquet, Muhlethaler, Qayyum et. al. Expires 18 May 2001 [Page 30]
