multiple choice select the node which provides
reachability to the maximum number of nodes in N2. In
case of multiple nodes providing the same amount of
reachability, select the node as MPR whose D(y) is
greater. Remove the nodes from N2 which are now covered
by MPR_COVERAGE nodes in the MPR set.
5 A node’s MPR set is generated from the union of the MPR sets
for each interface. As an optimization, process each node, y,
in the MPR set in increasing order of N_willingness. If all
nodes in N2 are still covered by at least MPR_COVERAGE nodes
in the MPR set excluding node y, and if N_willingness of node
y is smaller than WILL_ALWAYS, then node y MAY be removed from
the MPR set.
When the MPR set has been computed, all the corresponding main
addresses are stored in the MPR Set.
16.3. Interoperability Considerations
The MPR set of a node MUST, according to section 8.3, be calculated
by a node in such a way that it, through the neighbors in the MPR-
set, can reach all symmetric strict 2-hop neighbors. This is
achieved by the heuristics in this section, for all values of
MPR_COVERAGE > 0. MPR_COVERAGE is a local parameter for each node.
Setting this parameter affects only the amount of redundancy in part
of the network.
Notice that for MPR_COVERAGE=1, the heuristics in this section is
identical to the heuristics specified in the section 8.3.1.
Nodes with different values of MPR_COVERAGE may coexist in a network:
control messages are carried by all nodes in accordance with section
3, and all nodes will receive at least the link-state information
required to construct routes as described in sections 9 and 10.
17. IPv6 Considerations
All the operations and parameters described in this document used by
OLSR for IP version 4 are the same as those used by OLSR for IP
version 6. To operate with IP version 6, the only required change is
to replace the IPv4 addresses with IPv6 address. The minimum packet
and message sizes (under which there is rejection) should be adjusted
accordingly, considering the greater size of IPv6 addresses.
18. Proposed Values for Constants
This section list the values for the constants used in the
description of the protocol.
18.1. Setting emission intervals and holding times
The proposed constant for C is the following:
C = 1/16 seconds (equal to 0.0625 seconds)
C is a scaling factor for the "validity time" calculation ("Vtime"
and "Htime" fields in message headers, see section 18.3). The
"validity time" advertisement is designed such that nodes in a
network may have different and individually tuneable emission
intervals, while still interoperate fully. For protocol functioning
and interoperability to work:
- the advertised holding time MUST always be greater than the
refresh interval of the advertised information. Moreover, it
is recommended that the relation between the interval (from
section 18.2), and the hold time is kept as specified
in section 18.3, to allow for reasonable packet loss.
- the constant C SHOULD be set to the suggested value. In order
to achieve interoperability, C MUST be the same on all nodes.
- the emission intervals (section 18.2), along with the
advertised holding times (subject to the above constraints)
MAY be selected on a per node basis.
Note that the timer resolution of a given implementation might not be
sufficient to wake up the system on precise refresh times or on
precise expire times: the implementation SHOULD round up the
’validity time’ ("Vtime" and "Htime" of packets) to compensate for
coarser timer resolution, at least in the case where "validity time"
could be shorter than the sum of emission interval and maximum
expected timer error.
18.2. Emission Intervals
HELLO_INTERVAL = 2 seconds
REFRESH_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds
MID_INTERVAL = TC_INTERVAL
HNA_INTERVAL = TC_INTERVAL
18.3. Holding Time
NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL
TOP_HOLD_TIME = 3 x TC_INTERVAL
DUP_HOLD_TIME = 30 seconds
MID_HOLD_TIME = 3 x MID_INTERVAL
HNA_HOLD_TIME = 3 x HNA_INTERVAL
The Vtime in the message header (see section 3.3.2), and the Htime in
the HELLO message (see section 6.1) are the fields which hold
information about the above values in mantissa and exponent format
(rounded up). In other words:
value = C*(1+a/16)*2^b [in seconds]
where a is the integer represented by the four highest bits of the
field and b the integer represented by the four lowest bits of the
field.
Notice, that for the previous proposed value of C, (1/16 seconds),
the values, in seconds, expressed by the formula above can be stored,
without loss of precision, in binary fixed point or floating point
numbers with at least 8 bits of fractional part. This corresponds
with NTP time-stamps and single precision IEEE Standard 754 floating
point numbers.
Given one of the above holding times, a way of computing the
mantissa/exponent representation of a number T (of seconds) is the
following:
- find the largest integer ’b’ such that: T/C >= 2^b
- compute the expression 16*(T/(C*(2^b))-1), which may not be a
integer, and round it up. This results in the value for ’a’
- if ’a’ is equal to 16: increment ’b’ by one, and set ’a’ to 0
- now, ’a’ and ’b’ should be integers between 0 and 15, and the
field will be a byte holding the value a*16+b
For instance, for values of 2 seconds, 6 seconds, 15 seconds, and 30
seconds respectively, a and b would be: (a=0,b=5), (a=8,b=6),
(a=14,b=7) and (a=14,b=8) respectively.
18.4. Message Types
HELLO_MESSAGE = 1
TC_MESSAGE = 2
MID_MESSAGE = 3
HNA_MESSAGE = 4
18.5. Link Types
UNSPEC_LINK = 0
ASYM_LINK = 1
SYM_LINK = 2
LOST_LINK = 3
18.6. Neighbor Types
NOT_NEIGH = 0
SYM_NEIGH = 1
MPR_NEIGH = 2
18.7. Link Hysteresis
HYST_THRESHOLD_HIGH = 0.8
HYST_THRESHOLD_LOW = 0.3
HYST_SCALING = 0.5
18.8. Willingness
WILL_NEVER = 0
WILL_LOW = 1
WILL_DEFAULT = 3
WILL_HIGH = 6
WILL_ALWAYS = 7
The willingness of a node may be set to any integer value from 0 to
7, and specifies how willing a node is to be forwarding traffic on
behalf of other nodes. Nodes will, by default, have a willingness
WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to
carry traffic for other nodes, for example due to resource
constraints (like being low on battery). WILL_ALWAYS indicates that
a node always should be selected to carry traffic on behalf of other
nodes, for example due to resource abundance (like permanent power
supply, high capacity interfaces to other nodes).
A node may dynamically change its willingness as its conditions
change.
One possible application would, for example, be for a node, connected
to a permanent power supply and with fully charged batteries, to
advertise a willingness of WILL_ALWAYS. Upon being disconnected from
the permanent power supply (e.g., a PDA being taken out of its
charging cradle), a willingness of WILL_DEFAULT is advertised. As
battery capacity is drained, the willingness would be further
reduced. First to the intermediate value between WILL_DEFAULT and
WILL_LOW, then to WILL_LOW and finally to WILL_NEVER, when the
battery capacity of the node does no longer support carrying foreign
traffic.
18.9. Misc. Constants
TC_REDUNDANCY = 0
MPR COVERAGE = 1
MAXJITTER = HELLO_INTERVAL / 4
19. Sequence Numbers
Sequence numbers are used in OLSR with the purpose of discarding
"old" information, i.e., messages received out of order. However
with a limited number of bits for representing sequence numbers,
wrap-around (that the sequence number is incremented from the maximum
possible value to zero) will occur. To prevent this from interfering
with the operation of the protocol, the following MUST be observed.
The term MAXVALUE designates in the following the largest possible
value for a sequence number.
The sequence number S1 is said to be "greater than" the sequence
number S2 if:
S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
S2 > S1 AND S2 - S1 > MAXVALUE/2
Thus when comparing two messages, it is possible - even in the
presence of wrap-around - to determine which message contains the
most recent information.
20. Security Considerations
Currently, OLSR does not specify any special security measures. As a
proactive routing protocol, OLSR makes a target for various attacks.
The various possible vulnerabilities are discussed in this section.
20.1. Confidentiality
Being a proactive protocol, OLSR periodically diffuses topological
information. Hence, if used in an unprotected wireless network, the
network topology is revealed to anyone who listens to OLSR control
messages.
In situations where the confidentiality of the network topology is of
importance, regular cryptographic techniques such as exchange of OLSR
control traffic messages encrypted by PGP [9] or encrypted by some
shared secret key can be applied to ensure that control traffic can
be read and interpreted by only those authorized to do so.
20.2. Integrity
In OLSR, each node is injecting topological information into the
network through transmitting HELLO messages and, for some nodes, TC
messages. If some nodes for some reason, malicious or malfunction,
inject invalid control traffic, network integrity may be compromised.
Therefore, message authentication is recommended.
Different such situations may occur, for instance:
1 a node generates TC (or HNA) messages, advertising links to
non-neighbor nodes:
2 a node generates TC (or HNA) messages, pretending to be
another node,
3 a node generates HELLO messages, advertising non-neighbor
nodes,
4 a node generates HELLO messages, pretending to be another
node.
5 a node forwards altered control messages,
6 a node does not broadcast control messages,
7 a node does not select multipoint relays correctly.
8 a node forwards broadcast control messages unaltered, but does
not forward unicast data traffic;
9 a node "replays" previously recorded control traffic from
another node.
Authentication of the originator node for control messages (for
situation 2, 4 and 5) and on the individual links announced in the
control messages (for situation 1 and 3) may be used as a
countermeasure. However to prevent nodes from repeating old (and
correctly authenticated) information (situation 9) temporal
information is required, allowing a node to positively identify such
delayed messages.
In general, digital signatures and other required security
information may be transmitted as a separate OLSR message type,
thereby allowing that "secured" and "unsecured" nodes can coexist in
the same network, if desired.
Specifically, the authenticity of entire OLSR control messages can be
established through employing IPsec authentication headers, whereas
authenticity of individual links (situation 1 and 3) require
additional security information to be distributed.
An important consideration is, that all control messages in OLSR are
transmitted either to all nodes in the neighborhood (HELLO messages)
or broadcast to all nodes in the network (e.g., TC messages).
For example, a control message in OLSR is always a point-to-
multipoint transmission. It is therefore important that the
authentication mechanism employed permits that any receiving node can
validate the authenticity of a message. As an analogy, given a block
of text, signed by a PGP private key, then anyone with the
corresponding public key can verify the authenticity of the text.
20.3. Interaction with External Routing Domains
OLSR does, through the HNA messages specified in section 12, provide
a basic mechanism for injecting external routing information to the
OLSR domain. Section 12 also specifies that routing information can
be extracted from the topology table or the routing table of OLSR
and, potentially, injected into an external domain if the routing
protocol governing that domain permits.
Other than as described in the section 20.2, when operating nodes,
connecting OLSR to an external routing domain, care MUST be taken not
to allow potentially insecure and un-trustworthy information to be
injected from the OLSR domain to external routing domains. Care MUST
be taken to validate the correctness of information prior to it being
injected as to avoid polluting routing tables with invalid
information.
A recommended way of extending connectivity from an existing routing
domain to an OLSR routed MANET is to assign an IP prefix (under the
authority of the nodes/gateways connecting the MANET with the exiting
routing domain) exclusively to the OLSR MANET area, and to configure
the gateways statically to advertise routes to that IP sequence to
nodes in the existing routing domain.
20.4. Node Identity
OLSR does not make any assumption about node addresses, other than
that each node is assumed to have a unique IP address.
21. Flow and congestion control
Due to its proactive nature, the OLSR protocol has a natural control
over the flow of its control traffic. Nodes transmits control
message at predetermined rates fixed by predefined refresh intervals.
Furthermore the MPR optimization greatly saves on control overhead,
and this is done on two sides. First, the packets that advertise the
topology are much shorter since only MPR selectors may be advertised.
Second, the cost of flooding this information is greatly reduced
since only MPR nodes forward the broadcast packets. In dense
networks, the reduction of control traffic can be of several orders
of magnitude compared to routing protocols using classical flooding
(such as OSPF) [10]. This feature naturally provides more bandwidth
for useful data traffic and pushes further the frontier of
congestion. Since the control traffic is continuous and periodic, it
keeps more stable the quality of the links used in routing, where
reactive protocols, with bursty floodings for route discoveries and
repairs, may damage the link qualities for short times by causing
numerous collisions on those links, possibly provoking route repair
cascades. However, in certain OLSR options, some control messages
may be intentionally sent in advance of their deadline(TC or Hello
messages) in order to increase the reactiveness of the protocol
against topology changes. This may cause a small, temporary and
local increase of control traffic.
22. IANA Considerations
OLSR defines a "Message Type" field for control messages. A new
registry has been created for the values for this Message Type field,
and the following values assigned:
Message Type Value
-------------------- -----
HELLO_MESSAGE 1
TC_MESSAGE 2
MID_MESSAGE 3
HNA_MESSAGE 4
Future values in the range 5-127 of the Message Type can be allocated
using standards action [7].
Additionally, values in the range 128-255 are reserved for
private/local use.
23. Acknowledgments
The authors would like to thank Joseph Macker
<macker@itd.nrl.navy.mil> and his team, including Justin Dean
<jdean@itd.nrl.navy.mil>, for their valuable suggestions on the
advanced neighbor sensing mechanism and other various aspects of the
protocol, including careful review of the protocol specification.
The authors would also like to thank Christopher Dearlove
<chris.dearlove@baesystems.com> for valuable input on the MPR
selection heuristics and for careful reviews of the protocol
specification.
24. Contributors
During the development of this specification, the following list of
people contributed. The contributors are listed alphabetically.
Cedric Adjih
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5215
EMail: Cedric.Adjih@inria.fr
Thomas Heide Clausen
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5133
EMail: T.Clausen@computer.org
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 5088
EMail: Anis.Laouiti@inria.fr
Pascale Minet
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5233
EMail: Pascale.Minet@inria.fr
Paul Muhlethaler
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
EMail: Paul.Muhlethaler@inria.fr
Amir Qayyum
Center for Advanced Research in Engineering Pvt. Ltd.
19 Ataturk Avenue
Islamabad, Pakistan
Phone: +92-51-2874115
EMail: amir@carepvtltd.com
Laurent Viennot
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5225
EMail: Laurent.Viennot@inria.fr
25. References
25.1. Normative References
[5] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[7] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A.
Qayyum and L. Viennot. Optimized Link State Routing Protocol.
IEEE INMIC Pakistan 2001.
25.2. Informative 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.
35th Annual Hawaii International Conference on System Sciences
(HICSS’2001).
[3] ETSI STC-RES10 Committee. Radio equipment and systems:
HIPERLAN type 1, functional specifications ETS 300-652, ETSI,
June 1996.
[4] P. Jacquet and L. Viennot, Overhead in Mobile Ad-hoc Network
Protocols, INRIA research report RR-3965, 2000.
[6] T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The
Optimized Link State Routing Protocol, Evaluation through
Experiments and Simulation. IEEE Symposium on "Wireless
Personal Mobile Communications", September 2001.
[8] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
Considerations Section in RFCs", BCP 26, RFC 2434, October
1998.
[9] Atkins, D., Stallings, W. and P. Zimmermann, "PGP Message
Exchange Formats", RFC 1991, August 1996.
[10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot. Performance
analysis of OLSR multipoint relay flooding in two ad hoc
wireless network models, INRIA research report RR-4260, 2001.
26. Authors’ Addresses
Thomas Heide Clausen
Project HIPERCOM
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5133
EMail: T.Clausen@computer.org
Philippe Jacquet,
Project HIPERCOM,
INRIA Rocquencourt, BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263,
EMail: Philippe.Jacquet@inria.fr
27. Full Copyright Statement
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.