Mobile Ad hoc Networking (MANET) Y. Lacharite
Internet-Draft M. Wang
Intended status: Experimental Communications Research Centre
Expires: January 14, 2010 Canada
P. Minet
INRIA
T. Clausen
LIX, Ecole polytechnique
July 13, 2009
Hierarchical OLSR
draft-lacharite-manet-holsr-02
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
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.
This Internet-Draft will expire on January 14, 2010.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Lacharite, et al. Expires January 14, 2010 [Page 1]
Internet-Draft HOLSR July 2009
Abstract
This document describes the Hierarchical Optimized Link State Routing
(HOLSR) mechanism for heterogeneous mobile ad hoc networks. In this
specification a heterogeneous mobile ad hoc network is defined as a
network of mobile routers that are characterized by different
communication capabilities, such as communication channels,
processing powers or energy levels.
The HOLSR mechanism is an extension to the OLSRv2 protocol. HOLSR
takes advantage of the router's distinct communications capabilities
to reduce the routing control overhead in large heterogeneous ad hoc
networks, thus improving the performance of the routing mechanism.
More precisely, HOLSR defines a hierarchy in the network and presents
a routing scheme for this hierarchical structure with a better
scalability.
Lacharite, et al. Expires January 14, 2010 [Page 2]
Internet-Draft HOLSR July 2009
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8
4.1. Hierarchy Building . . . . . . . . . . . . . . . . . . . . 8
4.2. Hierarchy Routing . . . . . . . . . . . . . . . . . . . . 11
5. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 11
5.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 11
5.1.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 12
5.1.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 12
5.2. Information Validity Times . . . . . . . . . . . . . . . . 13
5.2.1. CIA Validity Times . . . . . . . . . . . . . . . . . . 13
5.2.2. HTC Validity Times . . . . . . . . . . . . . . . . . . 13
5.3. Cluster Intersection Depth . . . . . . . . . . . . . . . . 14
5.4. Cluster Critical Path . . . . . . . . . . . . . . . . . . 14
6. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 14
6.1. Description of HOLSR Logical Topology Levels . . . . . . . 15
6.1.1. Example . . . . . . . . . . . . . . . . . . . . . . . 15
6.2. Cluster Formation . . . . . . . . . . . . . . . . . . . . 16
6.2.1. Particular Case: Cluster Intersections . . . . . . . . 17
6.2.2. Cluster ID Announcement Validity Timer . . . . . . . . 17
6.3. Cluster Interaction . . . . . . . . . . . . . . . . . . . 18
6.3.1. Types of Hierarchical Topology Control Message . . . . 18
6.3.2. HTC and TC Message Propagation . . . . . . . . . . . . 19
6.4. Clusters Decommission . . . . . . . . . . . . . . . . . . 19
6.5. HOLSR Repositories . . . . . . . . . . . . . . . . . . . . 20
6.6. HOLSR Messages . . . . . . . . . . . . . . . . . . . . . . 21
6.6.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 21
6.6.1.1. CIA Message TLVs . . . . . . . . . . . . . . . . . 22
6.6.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 22
6.6.2.1. HTC Message TLVs . . . . . . . . . . . . . . . . . 23
6.7. HOLSR Algorithm . . . . . . . . . . . . . . . . . . . . . 23
6.7.1. Processing and Broadcasting CIA Message . . . . . . . 23
6.7.2. Processing and Forwarding HTC Message . . . . . . . . 24
6.7.3. Cluster Intersection Handling . . . . . . . . . . . . 25
7. Proposed Values for Parameters . . . . . . . . . . . . . . . . 26
7.1. Message Intervals Parameter Defaults . . . . . . . . . . . 26
7.1.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 26
7.1.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 27
7.2. Information Validity Times Parameters . . . . . . . . . . 27
7.2.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 27
7.2.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 27
7.3. Cluster Intersection Depth . . . . . . . . . . . . . . . . 27
7.4. Cluster Critical Path . . . . . . . . . . . . . . . . . . 27
8. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 27
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28
Lacharite, et al. Expires January 14, 2010 [Page 3]
Internet-Draft HOLSR July 2009
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28
10.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 28
10.2. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 29
10.3. HTC_MSG_TYPE Values . . . . . . . . . . . . . . . . . . . 29
11. Security Considerations . . . . . . . . . . . . . . . . . . . 30
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30
12.1. Normative References . . . . . . . . . . . . . . . . . . . 30
12.2. Informative References . . . . . . . . . . . . . . . . . . 30
Appendix A. Example of Data Transfer using Clusters . . . . . . . 30
Appendix B. Example of Cluster Decommission Handling . . . . . . 33
Appendix C. Packet and Message Layout . . . . . . . . . . . . . . 35
C.1. Packet and Message Options . . . . . . . . . . . . . . . . 35
C.2. Example CIA Message . . . . . . . . . . . . . . . . . . . 35
C.3. Example HTC Message . . . . . . . . . . . . . . . . . . . 36
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 37
Lacharite, et al. Expires January 14, 2010 [Page 4]
Internet-Draft HOLSR July 2009
1. Introduction
The Hierarchical Optimized Link State Routing Protocol (HOLSR) is
designed for heterogeneous ad hoc networks, and is an extension to
the OLSRv2 [I-D.ietf-manet-olsrv2] routing protocol. HOLSR has two
main functionalities:
o Hierarchy building: HOLSR organizes routers into hierarchical
levels according to their capacities (e.g. radio, energy,
processing) and dynamically groups routers into clusters at each
level.
o Hierarchical routing: HOLSR provides a hierarchical routing that
supports random movement of the routers among and between
clusters, and can dynamically adapt to topology changes at
different levels. Within each cluster, the OLSRv2 routing
protocol, as specified in [I-D.ietf-manet-olsrv2], is used.
The main improvements realized by the HOLSR protocol are a reduction
in the amount of topology control information that needs to be
exchanged at different levels of the hierarchical network topology,
and the efficient use of high capacity routers. Another significant
benefit is a reduction in routing computational cost: if a link in
one part of the network is broken, only those routers within the
cluster in which the link exists need to re-calculate the routing
table, while routers in other clusters are not affected. HOLSR is
versatile in that it does not require a logical hierarchical
addressing scheme but can accommodate one if required.
In an HOLSR network structure, the routers equipped with high
capacity links form the higher-level network, while the routers with
low capacity links form the lower-level network. At a given level,
cluster heads are selected from the routers with higher capabilities.
The choice of the cluster head or the establishment of its capability
criteria (e.g. multiple interfaces, more processing power, increased
memory, etc.), is out of scope of this document. It is left to the
implementer or the administrator, who can select the best criteria
adapted to the specific network deployment. Routers can move from
one cluster to another, and can associate with the nearest cluster
head, while the cluster heads propagate updated membership
information among each other using Hierarchical Topology Control
(HTC) messages.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
Lacharite, et al. Expires January 14, 2010 [Page 5]
Internet-Draft HOLSR July 2009
"OPTIONAL" in this document are to be interpreted as described in
[RFC2119].
This document uses OLSR terminology as defined in OLSRv1 [RFC3626]
and OLSRv2 [I-D.ietf-manet-olsrv2]. MANET specific terminology is to
be interpreted as described in [RFC5444] and NHDP
[I-D.ietf-manet-nhdp].
Additionally, this document uses the following terminology:
Cluster
A small group or gathering of MANET routers that have the same
cluster head.
Cluster Head
A MANET router can become a cluster head at level i if:
* it possesses a "higher capability" besides the one it shares
with its cluster neighbor routers, and
* it participates in communication level i+1.
The definition of "higher capability" is a deployment issue, out
of scope of this document.
Cluster Member
A MANET router that is associated with a cluster head.
CIA
Cluster Id Announcement. A control message initiated periodically
by a cluster head to declare its leadership and invite other
routers to join its cluster. Cluster members generate CIA
messages including a distance field set to their distance (in
terms of number of hops) to the cluster head). The message is
generated by cluster members until it reaches the edge of the
cluster.
Cluster Edge
Cluster Edge. Distinguishes routers belonging to the cluster from
others.
Cluster Intersection Depth
When routers from one cluster can hear Cluster Id Announcements
from another cluster, it is said that these two clusters
intersect, i.e. a router on the edge of one cluster is in radio
communication range from the edge of a neighbor cluster. The
depth of the intersection depends on the permissions given to edge
routers from different clusters to inter-communicate without going
Lacharite, et al. Expires January 14, 2010 [Page 6]
Internet-Draft HOLSR July 2009
through (and bypassing) their respective cluster heads. For a
depth value of '1', edge routers from two different clusters
within radio range can communicate, but they cannot forward
messages from each other within their own cluster. For a depth
value of '2', the same two edge routers are permitted to forward
neighbor cluster's messages once (Time to live (TTL) = '1'). For
a depth value of '3', TTL = '2', etc.
HTC
Hierarchical Topology Control (TC). A control message sent
periodically that is used to propagate the membership information
of a cluster to the higher hierarchical level routers.
OLSRv2
The Optimized Link State Routing protocol version 2 is an update
to OLSRv1 as published in [RFC3626].
Router
A MANET router which implements the Hierarchical OLSRv2 protocol
as specified in this document.
Topology level
A logical level that is composed of links and routers that share
similar characteristics (e.g. bandwidth, transmission range,
energy capacity, processing capacity). The higher the level gets,
the "better" the characteristics are.
3. Applicability Statement
Many contemporary ad hoc wireless networks are heterogeneous in
nature, being comprised of mobile devices with heterogeneous
capacities. For instance, these devices can have distinct
communications capabilities with respect to data rate, radio range,
frequency band, etc. They can also have different energy capacities
and different processing capacities. We can cite two examples of
networks where HOLSR provides high benefits: military networks and
sensor networks.
In military networks for instance, soldiers, tanks and headquarters
might each be given wireless communication equipment that is
appropriate to their communication needs. Soldiers are usually
equipped with wireless communication devices characterized by limited
resources in terms of radio bandwidth, energy capacity and processing
capacity. Those devices can only handle limited transmission range
and have restricted communications bandwidth. Vehicles, on the other
hand, are outfitted with more powerful equipments providing extended
communication coverage with higher communication bandwidth
Lacharite, et al. Expires January 14, 2010 [Page 7]
Internet-Draft HOLSR July 2009
capability.
In data gathering applications supported by wireless sensor networks,
the aim is to maximize network lifetime. Energy efficient strategies
are used such as clustering. Cluster heads are selected among the
routers with a sufficient energy level, and rotate in order to
balance energy consumption. Cluster heads can also be chosen with an
additional applicative criterion: they represent routers having the
same data value to transmit to the data sink.
HOLSR is also beneficial to mesh networks in general, where there can
be limited or no mobility such as sensor networks. HOLSR can manage
a combination of mobile and non-mobile components.
Scalability is one of the most important factors governing the
efficiencies of heterogeneous wireless networks. Scalability may be
defined as the ability of a network to adjust or maintain its
performance when its size increases. That also includes the increase
in traffic load that is handled. Yet under a "flat" routing
protocol, the performance of an ad hoc network tends to degrade as
the number of mobile routers increases. When a flat routing protocol
is used, the resulting control overhead increases, depending on the
number of interfaces possessed by each router since more links need
to be propagated for each router in order to share the topology
information. Concerning data gathering applications, the use of
hierarchical routing enables reducing the amount of data transferred
to the sink, and hence to maximize network lifetime.
4. Protocol Overview and Functioning
HOLSR consists of 2 main functionalities: enabling the creation of a
hierarchy structure on top of a standard OLSR network; and providing
the control messaging tools to transmit the hierarchy topology and
enable routing through the use of gateway routers, defined as cluster
heads.
The criteria used to define and select cluster heads unto which to
construct the HOLSR hierarchical structure is outside the scope of
this protocol.
4.1. Hierarchy Building
In HOLSR, a hierarchical structure is constructed over the network
based on its member routers' capabilities. In the following
description, the criteria selected for higher capabilities is linked
to the amount and properties of each router's wireless interfaces.
Lacharite, et al. Expires January 14, 2010 [Page 8]
Internet-Draft HOLSR July 2009
Let us demonstrate the idea using figures 1 and 2, composed of 23
MANET routers. In figure 1, routers are denoted by letters, and
their preceding character determines their capabilities and available
interfaces. Thus a "." identifies regular MANET routers, a "#"
identifies routers with 2 interfaces ("low" and "medium" range
radio); a "&" identifies routers with 3 interfaces (low, medium, and
"long" range radio); and a "@" identifies routers with 2 interfaces
(medium and long range radios).
For this example, it is decided that the routers with multiple
interfaces be used as cluster heads. From then on, MANET routers
start organizing themselves into clusters around their cluster heads.
There are 4 cluster heads (a, f, p, and t) that have dual low and
medium transmission range interfaces. These form 4 intersecting
clusters at level 1 (see figure 2). Routers are identified with
their cluster id (capital character followed by a number, or 'H' for
a cluster head), cluster A members are now AH, A1, A2, and A3
(respectively a, b, c and d), etc. Clusters at level 2 are formed by
routers that possess at least one interface with medium transmission
range. This requirement is matched by routers a, f, p, r, and u.
From these routers, the ones that contain an additional long
transmission range radio interface (level 3) become cluster heads at
level 2 (this applies to routers f and r). Hence 2 clusters are
created at level 2 (E and F with cluster heads EH and FH). The level
3 "overall" cluster is formed by routers f and r, since they share
the long transmission range capabilities. No cluster head is
required at level 3 since 1) there is no higher level; 2) the 2
members are in transmission range of each other.
Lacharite, et al. Expires January 14, 2010 [Page 9]
Internet-Draft HOLSR July 2009
_.--------------------------.
_.------'' .h .m #p `--------.
,--'' &f .k @r `---.
,-' `-.
/ .d .g .j .o .s .v \
( #a .e .l #u )
\ .q /
`-. .b .i .w ,-'
`---. .c .n .t _.--'
`--------. _.------''
`--------------------------''
Figure 1 - Typical MANET Example
. . . . . . . . .. .. .. . . .. .
| | | | | | | | || || || | | || |
+--- ---+
_.--------------------------.
L _.----'' `------.
e ,-'' `--.
v ,' `.
e ( E.f.....................F.r )
L `. | | ,'
`--. | | _.-'
3 `------. | |_.----''
`---+----------------------''
+--- | Overall Cluster | ---+
_.----------| _.---+------.
L ,-'' |`--. ,-'' ,'FH.r. `--.
e / | \ / ,' '-. \
v ( A.a.............EH.f ) ( C.p..........D.u )
e \| | / \ | | /
l |--. |_.-' `--.| |.-'
| `----------'| |----------''|
2 | Cluster E | ,------+. Cluster F |
| ,---+-------.,-' | `-. |
+--- | ,-' | B1.h,'`-. C1.m CH.p `. | ---+
| ,----,'---. BH.f / C4.k. \,----+----.
L ,+' / `-. ; \ ,-': | `-.
e / | ( A3.d \B2.g| B5.j ) C2.o /C6.s| | D1.v\
v / AH.a \ B4.e\ : C5.l/ / ; DH.u \
e ( `. ) \ ,' (D4.q/ )
l \ A1.b '-. / B3.i`.,-' \ ,' D2.w /
\ A2.c `---+-------''-. C3.n ,-\ D3.t /
1 `-. ,-'Cluster B `-------' `-. ,-'
`---------' Cluster C `---------'
+--- Cluster A Cluster D ---+
Figure 2 - Hierarchical MANET Example
Lacharite, et al. Expires January 14, 2010 [Page 10]
Internet-Draft HOLSR July 2009
Cluster formation of the hierarchy structure is made possible by the
addition of Cluster Id Announcement (CIA) messages. Every router
selected as a cluster head sends CIA messages periodically to declare
its leadership and invite other routers to join its cluster.
Section 6 provides complete details.
4.2. Hierarchy Routing
In HOLSR, at a given level, routers can move from one cluster to
another and associate with the nearest cluster head. For routing
purposes, the information about cluster membership is transmitted to
higher levels by the cluster heads. The following denotes the
routing structure within HOLSR:
o Within each cluster, OLSRv2 [I-D.ietf-manet-olsrv2] runs
unaltered, providing routing topology information about router
destinations within the same cluster. TC message propagation is
limited within the local cluster.
o Between clusters, the information about cluster membership and
topology information is transmitted to higher levels by the
cluster heads using Hierarchical Topology Control (HTC) messages.
o For routers located in overlapping regions of multiple clusters,
OLSRv2 TC messages can (with restrictions) be propagated not only
within the cluster but to the neighbor clusters as well. This
feature is controlled by the C_INTER_DEPTH parameter defined in
Section 5.3. Section 6.7.3provides complete details.
o Traffic from one cluster with destination to another cluster will
travel up the levels through cluster heads (acting as gateways)
and then down to reach their destination. Routers set their
cluster head as default gateway in their routing table. Hence,
every traffic request for destinations outside of their cluster
will go through their cluster head.
5. Protocol Parameters
The parameters used in this specification are those defined in OLSRv2
[I-D.ietf-manet-olsrv2] plus those described in this section.
5.1. Message Intervals
The following parameters regulate CIA and HTC message transmissions
by a router.
Lacharite, et al. Expires January 14, 2010 [Page 11]
Internet-Draft HOLSR July 2009
5.1.1. CIA Messages
CIA messages are transmitted periodically to advertise a router's
cluster head id and its distance from that cluster head. The
frequency of these advertisements is regulated by the parameters
CIA_INTERVAL and CIA_MIN_INTERVAL.
Specifically, these parameters are as follows:
CIA_INTERVAL
the maximum time between the transmission of two successive CIA
messages by a given cluster head. If using periodic transmission
of CIA messages for a given cluster head, these SHOULD be at a
separation of CIA_INTERVAL, and MAY be modified by jitter as
specified in [RFC5148].
CIA_MIN_INTERVAL
the minimum interval between transmission of two successive CIA
messages by a given cluster head. (This minimum interval MAY be
modified by jitter, as defined in [RFC5148].)
The following constraints apply to these parameters:
o CIA_INTERVAL > 0
o CIA_MIN_INTERVAL >= 0
o CIA_INTERVAL >= CIA_MIN_INTERVAL
o If INTERVAL_TIME message TLVs as defined in [RFC5497] are included
in CIA messages, then CIA_INTERVAL MUST be representable as
described in [RFC5497].
5.1.2. HTC Messages
HTC messages are transmitted periodically by a cluster head to
advertise its membership information to routers at the higher
hierarchical level. The frequency of these advertisements is
regulated by the parameters HTC_INTERVAL and HTC_MIN_INTERVAL. HTC
messages are an extension to the TC messages from OLSRv2
[I-D.ietf-manet-olsrv2], and as such they MAY use the same message
interval parameters, and the same message validity times:
HTC_INTERVAL
the maximum time between the transmission of two successive HTC
messages by a cluster head. When no HTC messages are sent in
response to local network changes under the cluster head, then HTC
messages SHOULD be sent at a regular interval HTC_INTERVAL,
Lacharite, et al. Expires January 14, 2010 [Page 12]
Internet-Draft HOLSR July 2009
possibly modified by jitter as specified in [RFC5148].
HTC_MIN_INTERVAL
the minimum interval between transmission of two successive HTC
messages by a cluster head. (This minimum interval MAY be
modified by jitter, as defined in [RFC5148].)
The following constraints apply to these parameters:
o HTC_INTERVAL > 0
o HTC_MIN_INTERVAL >= 0
o HTC_INTERVAL >= HTC_MIN_INTERVAL
o If INTERVAL_TIME message TLVs as defined in [RFC5497] are included
in HTC messages, then HTC_INTERVAL MUST be representable as
described in [RFC5497].
5.2. Information Validity Times
5.2.1. CIA Validity Times
The following parameters manage the validity time of CIA information:
CIA_HOLD_TIME
the value in the VALIDITY_TIME message TLV included in the CIA
message.
The following constraints apply to this parameter:
o CIA_HOLD_TIME >= CIA_INTERVAL
o CIA_HOLD_TIME MUST be representable as described in [RFC5497].
5.2.2. HTC Validity Times
HOLSR HTC messages SHOULD use the same validity time parameters as
for TC messages in OLSRv2 [I-D.ietf-manet-olsrv2].
OLSRv2 TC parameters for validity times are (refer to OLSRv2
[I-D.ietf-manet-olsrv2] for definitions):
o T_HOLD_TIME
o A_HOLD_TIME
Lacharite, et al. Expires January 14, 2010 [Page 13]
Internet-Draft HOLSR July 2009
o RX_HOLD_TIME
o P_HOLD_TIME
o F_HOLD_TIME
5.3. Cluster Intersection Depth
The following parameter regulates the communication between clusters
that are intersecting. This parameter has a direct impact on the
decision to route traffic through cluster heads are directly between
clusters at the same level.
C_INTER_DEPTH
the maximum depth that routers from different clusters in an
intersected area can include routers from another cluster than
their own in their routing tables (routers can only select one
cluster head ID).
The following constraints apply to this parameter:
C_INTER_DEPTH >= 0
5.4. Cluster Critical Path
The following parameter is used to identify cluster heads located on
critical paths on the HOLSR architecture. A router is considered to
be on a critical path if its failure causes network partition.
C_CRITICAL_PATH
- identifies a cluster head as being on the critical path of the
hierarchical structure.
The following constraints apply to this parameter:
C_CRITICAL_PATH = [0,1], where 0 is 'false', and 1 is 'true'
6. Protocol Details
This section describes the HOLSR routing protocol by specifying:
o HOLSR logical topology levels
o Cluster formation
o Cluster interaction
Lacharite, et al. Expires January 14, 2010 [Page 14]
Internet-Draft HOLSR July 2009
o Cluster decommission
o HOLSR repositories
o HOLSR Algorithm
6.1. Description of HOLSR Logical Topology Levels
Based on different communication capacities, routers are organized
into logical topology levels. A logical topology level is
constituted by routers having similar capacities (e.g. radio
bandwidth, radio interface, energy capacity, processing capacity).
The grouping and ordering of routers with similar capacities (to
determine which to assign to higher or lower layers) is an
administrator and deployment issue. Since one router can have
multiple communication capacities (by possessing different wireless
interfaces, for example), it can be visible as a router in different
logical topology levels. Usually, low-power routers are equipped
with only one interface offering limited data rate and transmission
range. Such routers participate at the lowest topology Level 1.
Routers at topology level i+1, with i greater than or equal to 1,
have higher capacities than routers at level i. Any router at level
i must be able to communicate, via a multi-hop path if necessary,
with a router at level i that is able to communicate with a router at
level i+1. In the same manner, if the level i+2 exists, then any
router at level i+1 must be able to communicate with a router at
level i+1 that is able to communicate with a router at level i+2.
6.1.1. Example
An example of a three levels hierarchy can be described as follows.
Routers at topology level 2 are equipped with a wireless interface
that can provide a higher data rate and longer transmission range
than the interfaces present on the level 1 routers. Some of the
routers in topology level 2 possess up to two wireless interfaces,
one of which is a wireless interface capable of communicating with
level 1 routers. These routers can relay messages at topology level
2 using a frequency band or a medium access control (MAC) protocol
that can differ from the one used for communication at topology level
1.
Topology level 3 routers represent routers with the highest capacity.
These routers can be equipped with up to three wireless interfaces
capable of communicating in turn with level 1 and 2 routers and with
other level 3 routers via high-speed point-to-point direct wireless
links. It should be noted that routers in level 3 or 2 can have
fewer than three or two wireless interfaces, respectively, and the
Lacharite, et al. Expires January 14, 2010 [Page 15]
Internet-Draft HOLSR July 2009
only requirement is that level 3 or 2 routers should be equipped with
at least one wireless interface for communications at level 3 or 2,
respectively. For example, a level 3 router could possess only one
high-speed point-to-point interface for ensuring communication with
level 3 routers.
The rules governing these first three levels can be scaled to
additional topology levels, as the HOLSR network increases in size.
6.2. Cluster Formation
Under the HOLSR mechanism, in each logical topology level, (the last
one possibly excepted), the mobile routers form multiple clusters
upon cluster heads' invitation, which in turn can be organized into a
hierarchical architecture. Unlike (flat) OLSRv2, HOLSR routers can
restrict exchange of Topology Control (TC) messages within clusters,
thus reducing the amount of control information that is broadcast
throughout the entire network. The topology control information
between clusters is exchanged via specialized HOLSR routers
designated as cluster heads.
The HOLSR cluster heads are selected among those higher-capacity
routers. However, the choice of the cluster head is not ruled by
HOLSR, it is left to the administrator of the network. Similarly,
the level at which a router exists or can exist is determined and
assigned administratively, and according to specific network
deployment requirements.
Mobile routers can be organized into clusters at different topology
levels. A cluster comprises a group of mobile routers (at the same
topology level) that are associated with a common cluster head.
At each level, the multiple mobile routers that have been selected as
cluster heads declare their status and thereby invite other routers
to join their cluster by periodically sending out Cluster ID
Announcement (CIA) messages. CIA messages contain two fields:
cluster head, which identifies the interface address of the cluster
head generating the CIA message, and distance (in hops) to that
cluster head. CIA messages are sent with Time to live (TTL) = '1',
i.e. they only travel one hop. When a cluster head generates a CIA
message, it identifies itself within the cluster head field, with
distance being 0.
After reception of a CIA message, the routers in proximity to the
cluster head will join that cluster, given that these routers are not
part of any cluster, or that the distance to this advertized cluster
head is less than the distance to another cluster head they might
already be associated with.
Lacharite, et al. Expires January 14, 2010 [Page 16]
Internet-Draft HOLSR July 2009
Once a router joins a cluster, it begins to broadcast CIA messages,
where the cluster head field contains the ID of the cluster head it
is associated with, and the distance field containing the distance,
in hops, from that router to the cluster head.
In a nutshell, every router within a cluster, once associated with a
cluster head, generates CIA messages with ID field set to cluster
head ID, the distance field set to the distance from the router and
its cluster head (in hops), and a TTL value of '1'.
6.2.1. Particular Case: Cluster Intersections
A given router may receive CIA messages from different cluster heads,
indicating that it is located in the overlapping regions of multiple
clusters. In such cases, the router joins whichever cluster is
closer in terms of hop count and generates CIA messages only with the
ID of the cluster head chosen.
There may also be scenarios where multiple routers with the same
capabilities are located in the vicinity of each other. In this
situation, a lower-level router may receive CIA messages with the
same hop count from various cluster heads. The router will on this
case attach itself to the cluster head from which it receives the
first CIA and remain with that cluster head for as long as the
topology does not change. It should be noted that given the random
movement of mobile routers, a router might find a cluster head closer
that the one to which it is currently attached. In this case, the
mobile router will proceed to change its cluster and attach itself to
the closest cluster head. Following this process, each router in the
lowest level joins a selected cluster, and the mechanism is in turn
applied at the different topology levels.
6.2.2. Cluster ID Announcement Validity Timer
A built-in diagnostic feature helps ensure the robustness of the
HOLSR clustering mechanism: each router registers a timeout value for
the CIA messages received. Should a cluster head become inactive or
move away, routers in its cluster will stop receiving the CIA
messages. Eventually the CIA message timeout value will expire and
cached CIA information will become invalid. At this point the mobile
routers will start to process CIA messages from another cluster and
join that cluster, should an opportunity present itself. If no more
CIA messages are received, then the routers will behave following the
OLSRv2 specifications.
Lacharite, et al. Expires January 14, 2010 [Page 17]
Internet-Draft HOLSR July 2009
6.3. Cluster Interaction
One of the main challenges in the HOLSR hierarchical architecture is
support for exchange of topology information between clusters at the
same or different topology levels without introducing too much
overhead. In HOLSR, a cluster head acts as a gateway through which
messages from cluster members are relayed to other parts of the
network. Under the HOLSR network architecture each cluster head at
level i needs to advertise the membership information of routers
under its hierarchy to level i+1. This is done with the use of the
Hierarchical TC message.
6.3.1. Types of Hierarchical Topology Control Message
A Hierarchical Topology Control (HTC) message is generated by a
cluster head and used to transmit the membership information of a
cluster (under this cluster head) to the higher hierarchical level
routers. Three basic types of HTC messages are used:
Full membership
Full membership messages are periodically transmitted by a cluster
head to provide information about its cluster members, including
members of any lower-level clusters beneath it.
Update
Update HTC messages provide information with respect to cluster
membership changes (i.e., the update HTC messages are used when
mobile routers join or leave a cluster).
Request
As HTC messages carry a sequence number field, it is possible to
determine whether any HTC packet loss has occurred, in which case
a request for retransmission of a full membership HTC message is
sent by the receiving router.
In topological terms, the higher a given router is located, the more
information it obtains about the network. Routers at the highest
topology level possess full knowledge of all the routers in the
network; consequently, the sizes of their routing tables are as large
as they would be under OLSRv2. Routers at lowest topology level are
limited in scope; and consequently the size of their routing tables
are reduced. I.e. They set their cluster head as default gateway in
their routing tables, and all traffic route requests for routers
outside their cluster is routed through the cluster head; which is
exactly the way it is intended to be.
Lacharite, et al. Expires January 14, 2010 [Page 18]
Internet-Draft HOLSR July 2009
6.3.2. HTC and TC Message Propagation
Routers at each hierarchical level independently select MPRs in their
respective cluster level. HTC is generated by a cluster head at
level i for the level i+1, if this level exists. It is forwarded by
MPRs at level i+1 within this single cluster. At each hierarchical
level, TC messages are generated independently. The propagation of
the TC is restricted within a cluster, unless a router is located in
the overlapping regions of several clusters. Therefore, an HOLSR
router's location directly determines the required scope of its
knowledge of network topology: for routers located toward the center
of the cluster, TC propagation is limited to the local cluster; for
routers located in overlapping regions of multiple clusters, the TC
message is propagated not only within the local cluster but one hop
further to the neighbor routers in other clusters as well. This
approach offers two main advantages:
o The control message reflecting local movement is restricted within
the local area, which largely reduces protocol overhead as well as
routing table computation overhead
o Nearby routers in different clusters at the same topology level
can communicate directly without having to follow the strict
clustering hierarchy, which decreases delay and reduces the load
on the cluster head.
6.4. Clusters Decommission
To increase robustness of the HOLSR architecture and to avoid
possible network partitions, cluster heads are permitted, in very
specific cases, to abandon their "head" status.
If a router that was initialized as a cluster head satisfies the
requirements for decommissioning, it starts to emit CIA message
announcements with the distance parameter (CLUSTER_HEAD_DIST) set to
'255'. Cluster members, with matching cluster head ID, receiving
such a message will de-associate from that cluster head. A router
that is de-associated will then be able to process CIA messages from
neighbor clusters.
The requirements to decommission are (i) to have the parameter
C_CRITICAL_PATH set to "true" on one level/interface, and (ii) to
lose all connections/links on that interface. It is up to the
network administrator to determine what routers on what interfaces
could cause network partition if failure occurs.
A decommissioned cluster head will revive its "head" status when the
interface with the C_CRITICAL_PATH set to "true" has at least one
Lacharite, et al. Expires January 14, 2010 [Page 19]
Internet-Draft HOLSR July 2009
link successfully reinstated. The cluster head will then publish CIA
announcements with the distance parameter set to '0'. As a result,
routers closer to this cluster head will re-associate with it.
6.5. HOLSR Repositories
In addition to the repositories maintained by OLSRv2, HOLSR maintains
the following repositories:
o A Cluster Information Base.
It contains one entry describing the head of the cluster to which
that routers belongs, its relative distance (in hop counts) to the
cluster head, and an expiry time. This repository is populated
and updated upon receipt of a Cluster Identifier Announcement
(CIA) message. The repository entry is timestamped with the time
of the last update +<expiry_time>. When the repository entry
expires (as consequence of not receiving any CIA message for an
<expiry_time> period), the entry is deleted, and the router looses
its association to its cluster head. Particular cases:
* At the cluster head: Cluster ID is one-self, distance is '0',
and expiry_time is 0 or ignored.
* At the cluster members: Cluster Head ID is cluster head,
distance is ]0, 255[, and expiry_time is > 0.
o Hierarchical Topology Information Base (cluster membership).
This repository is populated and updated upon receipt of
Hierarchical Topology Control messages. It contains one entry for
each HTC message originator (cluster head) received. Each entry
is tupled with the list of member routers, the sequence number it
was assigned by the cluster head, and the interface it was
retrieved from. Each repository entry is timestamped with the
time of the last update +<expiry_time>. Particular cases:
* At the cluster head: one of the HTC originator entry contains
information about this cluster head router membership. This
entry is generated by the router without reception of an HTC
message.
* At the cluster member routers that are not cluster heads
themselves: none of the originator entries matches the router's
own address.
Lacharite, et al. Expires January 14, 2010 [Page 20]
Internet-Draft HOLSR July 2009
6.6. HOLSR Messages
HOLSR uses the Generalized MANET Packet/Message Format as defined in
[RFC5444], and adds 2 new message types and 4 new TLVs, as described
below.
6.6.1. CIA Messages
At each level, the multiple mobile routers that have been defined to
become cluster heads declare their status and invite other routers to
join their cluster by periodically sending out Cluster ID
Announcement (CIA) messages. CIA messages MUST NOT be forwarded, as
their expected recipients are the immediate neighbors of the emitting
router(s).
CIA messages MUST contain the following 2 TLV messages:
o CLUSTER_HEAD_ID message TLV identifying the interface address of
the cluster head generating the CIA message
o CLUSTER_HEAD_DIST message TLV specifying the distance in hops to
that cluster head. There are 3 particular cases for
CLUSTER_HEAD_DIST values;
* CLUSTER_HEAD_DIST = '0': Identifies and is generated by the
cluster head.
* CLUSTER_HEAD_DIST is '255': Cluster decommission message
generated by the cluster head first, and consequently by its
member routers.
* CLUSTER_HEAD_DIST is > '0' and < '255': Generated by routers
associating with the cluster head, and which are not themselves
cluster heads.
CIA messages MAY contain the following 2 TLV messages:
o VALIDITY_TIME message TLV as specified in [RFC5497], representing
CIA_HOLD_TIME for the transmitting MANET interface. The options
included in time in [RFC5497], for representing zero and infinite
time MUST NOT be used.
o INTERVAL_TIME message TLV as specified in [RFC5497], representing
CIA_INTERVAL for the transmitting MANET interface. The options
included in time in [RFC5497], for representing zero and infinite
time MUST NOT be used.
Lacharite, et al. Expires January 14, 2010 [Page 21]
Internet-Draft HOLSR July 2009
6.6.1.1. CIA Message TLVs
In a CIA message, a router must include a single CLUSTER_HEAD_ID
message TLV and a single CLUSTER_HEAD_DIST, as specified in Table 1.
+-------------------+--------+--------------------------------------+
| Type | Value | Value |
| | Length | |
+-------------------+--------+--------------------------------------+
| CLUSTER_HEAD_ID | 1 | Specifies the cluster head ID |
| | octet | selected by this router (generator |
| | | of the CIA message) |
| CLUSTER_HEAD_DIST | 1 | Specifies the distance, in hops, |
| | octet | between the cluster head and this |
| | | router (generator of the CIA |
| | | message) |
+-------------------+--------+--------------------------------------+
Table 1
6.6.2. HTC Messages
A Hierarchical TC (HTC) message is used to transmit membership
information of a cluster to higher hierarchical level routers.
There are 3 basic types of HTC messages:
o FULL_MEMBERSHIP
Full membership HTC messages are periodically transmitted by a
cluster head to provide information about its cluster members,
including members of any lower-level clusters beneath it.
o UPDATE
Update HTC messages provide information with respect to cluster
membership changes (i.e., the update HTC messages are used when
mobile routers join or leave a cluster). As HTC messages carry a
sequence number field, it is possible to determine whether any HTC
packet loss has occurred, in which case a request for
retransmission of a full membership HTC message is sent by the
receiving router. HTC forwarding is enabled by MPRs, and is
restricted within a cluster.
o REQUEST
Request HTC messages are used to request retransmission of full
membership HTC messages.
An HTC message MUST contain an HTC message type TLV:
Lacharite, et al. Expires January 14, 2010 [Page 22]
Internet-Draft HOLSR July 2009
o HTC_MSG_TYPE message TLV that is one of FULL_MEMBERSHIP, UPDATE or
REQUEST.
An HTC message of type FULL_MEMBERSHIP or UPDATE MUST contain a
sequence number message TLV. REQUEST type message do not need to
include this TLV:
o HTC_SEQ_NUM message TLV, specified by an incrementing counter on
the HTC message generation at the cluster head router.
6.6.2.1. HTC Message TLVs
TLV messages used within the HTC messages:
+--------------+--------+-------------------------------------------+
| Type | Value | Value |
| | Length | |
+--------------+--------+-------------------------------------------+
| HTC_MSG_TYPE | 1 | Specifies the type of HTC message |
| | octet | |
| HTC_SEQ_NUM | 2 | Specifies the sequence number of the HTC |
| | octets | generator counter at the cluster head |
| | | router |
+--------------+--------+-------------------------------------------+
Table 2
6.7. HOLSR Algorithm
6.7.1. Processing and Broadcasting CIA Message
A CIA message is periodically generated and sent by a router that has
been configured as cluster head. A CIA message generated from a
cluster head has its distance value set to 0.
Routers that join the cluster identified by the cluster head also
generate CIA messages periodically. CIA message generated from these
routers are sent with their distance value equal to the hop count
between themselves and the cluster head.
When a router receives a CIA message, three cases are possible:
o the router does not yet belong to a cluster: it joins the cluster
by (i) populating its cluster head repository and (ii) starting to
broadcast CIA messages, inviting other routers to join this
cluster. The cluster head distance value stored in its repository
is the value received from the CIA message processed plus one.
Lacharite, et al. Expires January 14, 2010 [Page 23]
Internet-Draft HOLSR July 2009
o the router already belongs to a cluster: it checks if its distance
to the cluster head indicated in the received CIA message is
smaller than its distance to its current cluster head. If yes, it
joins the new cluster, updates its cluster head repository and
starts broadcasting CIA messages with the newly selected cluster
ID (and distance set accordingly). Otherwise, it continues to
broadcast CIA messages with the distance and cluster ID values
from its repository.
o the router receives a decommission message (CLUSTER_HEAD_DIST =
255). If the router's cluster head matches the cluster's ID from
the CIA message, it will de-associate from that cluster head. The
router will forward that decommission message until it associates
itself with another cluster head.
6.7.2. Processing and Forwarding HTC Message
Cluster heads generate different types of HTC messages. For all
message types, only one sequence number is stored. Every time an HTC
message is generated, the sequence number is incremented and included
in that message (regardless of its type).
Cluster heads generate HTC messages of type FULL_MEMBERSHIP and
UPDATE.
Cluster members generate HTC messages of type REQUEST.
Concerning HTC messages, we distinguish:
o a HTC message with full membership that is periodically generated
and sent by a cluster head of level i to the level i+1. This
message contains a sequence number that is incremented, as well as
the list of routers in the cluster membership (hierarchical
topology information base) repository.
o an update HTC message is generated by a cluster head of level i to
notify cluster membership changes to level i+1. This message
contains a sequence number that is incremented, as well as the new
routers having joined the cluster and the old routers having left.
It is computed from the cluster membership repository, after
addition or removal of a member router entry.
o a request HTC message is generated by a router that has received a
HTC message with a sequence number higher than its last one plus
one. This router asks for transmission of a full membership
message.
Upon receipt of a full membership HTC message, a router checks the
Lacharite, et al. Expires January 14, 2010 [Page 24]
Internet-Draft HOLSR July 2009
received sequence number:
o if it is smaller or equal, the message is silently discarded.
o otherwise, the received membership information replaces the old
one in the cluster membership repository. The message is
forwarded according to the OLSRv2 forwarding rule.
Upon receipt of an update HTC message, a router checks the received
sequence number:
o if it is smaller or equal, the message is silently discarded.
o if it is greater by 1 than the sequence number maintained in the
repository, the received membership information is used to update
the information in the cluster membership repository. The message
is forwarded according to OLSRv2 forwarding rule.
o otherwise, if it is greater by more than 1, a request HTC message
is generated and sent to get the missing HTC messages.
Upon receipt of a request HTC message, a router checks if it is the
originator of the HTC message for which a request is made (usually
the originator router is a cluster head):
o if yes, it sends a full membership message back to the sender.
o otherwise, this message is forwarded according to OLSR forwarding
rule.
6.7.3. Cluster Intersection Handling
Routers located within the intersecting domain of 2 or more clusters
are allowed to communicate directly (by-passing their respective
cluster heads) by setting the C_INTER_DEPTH parameter to a value
greater than 0.
In the intersection domain, routers SHOULD process all HELLO and TC
messages, even those not pertaining to their own cluster Id. The use
of a neighbor cluster's HELLO and TC message information to build up
the routing tables is constrained by the C_INTER_DEPTH parameter.
If C_INTER_DEPTH is greater than 1, an MPR in the intersecting domain
is allowed to forward a TC message originating from a router not
pertaining to its own cluster.
Lacharite, et al. Expires January 14, 2010 [Page 25]
Internet-Draft HOLSR July 2009
Example where Clusters A and B have routers in an intersection
vicinity.
_.--------------.
,--'' `---.
,' `.
( .A---------------------B. )
`./ \,'
`---. _.--'
| `--------------'' |
|cluster A cluster B |
_|----------. _.----------.|
,-'' | A2 ,-''--. |--.
,' A1 | ,' `. B1 B2| `.
/ AH .'A6. \ | \
( A3..+ ( `>B7......B3 BH )
\ A4 \`-.A7' / B4 /
`. A5 `. ,' B5 ,'
'--. '--..-' B6 _.-'
`----------'' `----------''
Figure 3 - Intersecting Clusters Example
Clusters A and B intersect because routers in the intersection area
(A6, A7, B7) are able to hear CIA announcements from 2 different
cluster heads (AH and BH).
If C_INTER_DEPTH is set to 1, then the direct communication between
A6 <--> B7, and A7 <--> B7 is enabled. If routers A7 wants to
communicate with router B3, it will have to do so going through its
cluster head AH (A7 -> A3 -> AH -> BH -> B3).
If C_INTER_DEPTH is set to 2, then router A7 is allowed to
communicate directly with router B3 (bypassing its cluster head) by
using the path provided by router B7; Hence A7 -> B7 -> B3.
7. Proposed Values for Parameters
This section lists the parameters and their default proposed values
used in the specification of the protocol.
7.1. Message Intervals Parameter Defaults
7.1.1. CIA Messages
By default these parameters are set to be identical to those used
within NHDP [I-D.ietf-manet-nhdp] for HELLO messages and intervals.
Lacharite, et al. Expires January 14, 2010 [Page 26]
Internet-Draft HOLSR July 2009
o CIA INTERVAL = 2 seconds
o CIA_MIN_INTERVAL = CIA_INTERVAL/4 = 0.5 seconds
7.1.2. HTC Messages
By default these parameters are set to be identical to those used
within OLSRv2 [I-D.ietf-manet-olsrv2] for TC messages and intervals.
o HTC_INTERVAL = 5 seconds
o HTC_MIN_INTERVAL = HTC_INTERVAL/4 = 1.25 seconds
7.2. Information Validity Times Parameters
7.2.1. CIA Messages
o CIA_HOLD_TIME = 3 x CIA_INTERVAL
7.2.2. HTC Messages
Since HTC validity times parameter refer to TC parameters, their
default parameters SHOULD use the same values at the ones used in
OLSRv2 [I-D.ietf-manet-olsrv2].
o T_HOLD_TIME = 3 x TC_INTERVAL
o A_HOLD_TIME = T_HOLD_TIME
o RX_HOLD_TIME = 30 seconds
o P_HOLD_TIME = 30 seconds
o F_HOLD_TIME = 30 seconds
7.3. Cluster Intersection Depth
o C_INTER_DEPTH = 1
7.4. Cluster Critical Path
o C_CRITICAL_PATH = 0 (false)
8. Contributors
This specification is the result of the joint efforts of the
following contributors, listed alphabetically.
Lacharite, et al. Expires January 14, 2010 [Page 27]
Internet-Draft HOLSR July 2009
o Thomas Heide Clausen, LIX, France, <T.Clausen@computer.org>
o Ying Ge, CRC, Canada, <ying.ge@crc.ca>
o Yannick Lacharite, CRC, Canada <yannick.lacharite@crc.ca>
o Pascale Minet, INRIA, France, <pascale.minet@inria.fr>
o Maoyu Wang, CRC, Canada, <maoyu.wang@crc.ca>
9. Acknowledgements
The authors would like to acknowledge the authors of OLSRv2 for their
guidance in the production of this specification.
We want to acknowledge the work done by Ying Ge (CRC), who
implemented a version HOLSR for OLSRv1 for her numerous inputs,
reviews and comments. Also the authors would like to gratefully
acknowledge the following people for intense technical discussions,
early reviews and comments on the specification and its components
(listed alphabetically): Ulrich Herberg (LIX), Louise Lamont (CRC),
Henning Rogge (FGAN), and the entire IETF MANET working group.
This document was written with the xml2rfc tool described in
[RFC2629].
10. IANA Considerations
10.1. Message Types
This specification defines two message types, which must be allocated
from the "Assigned Message Types" repository of [RFC5444] with
assignment as specified in Table 3.
+------+------+---------------------------------------+
| Name | Type | Description |
+------+------+---------------------------------------+
| CIA | TBD | Cluster ID Announcement message |
| HTC | TBD | Hierarchical Topology Control message |
+------+------+---------------------------------------+
Table 3
Lacharite, et al. Expires January 14, 2010 [Page 28]
Internet-Draft HOLSR July 2009
10.2. TLV Types
This specification defines four message TLV types, which must be
allocated from the "Message TLV Types" namespace defined in
[RFC5444]. IANA are requested to make allocations in the 8-127 range
for these types. This will create four new type extension registries
with assignments as specified in Table 4. Specifications of these
TLVs are in Section 6.6.1 and Section 6.6.2.
+-------------------+------+-----------+----------------------------+
| Name | Type | Type | Description |
| | | Extension | |
+-------------------+------+-----------+----------------------------+
| CLUSTER_HEAD_ID | TBD | 0 | Specifies the cluster head |
| | | | ID selected by this router |
| | | | (generator of the CIA |
| | | | message) |
| | | 1-255 | RESERVED |
| CLUSTER_HEAD_DIST | TBD | 0 | Specifies the distance, in |
| | | | hops, between the cluster |
| | | | head and this router |
| | | | (generator of the CIA |
| | | | message) |
| | | 1-255 | RESERVED |
| HTC_MSG_TYPE | TBD | 0 | Specifies the type of HTC |
| | | | message |
| | | 1-255 | RESERVED |
| HTC_MSG_NUM | TBD | 0 | Specifies the sequence |
| | | | number of the HTC |
| | | | generator counter at the |
| | | | cluster head router |
| | | 1-255 | RESERVED |
+-------------------+------+-----------+----------------------------+
Table 4
10.3. HTC_MSG_TYPE Values
The values which HTC_MSG_TYPE can use are the following:
o FULL_MEMBERSHIP = 0
o UPDATE = 1
o REQUEST = 2
Lacharite, et al. Expires January 14, 2010 [Page 29]
Internet-Draft HOLSR July 2009
11. Security Considerations
All drafts are required to have a security considerations section.
12. References
12.1. Normative References
[I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-09 (work in progress), July 2009.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter
Considerations in Mobile Ad Hoc Networks (MANETs)",
RFC 5148, February 2008.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009.
[RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value
Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497,
March 2009.
12.2. Informative References
[I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-10 (work in progress), July 2009.
[RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629,
June 1999.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
Appendix A. Example of Data Transfer using Clusters
This appendix gives an example of data transfer in a hierarchical
network with three levels. It reuses the figure presented in the
Protocol Overview (Section 4).
Lacharite, et al. Expires January 14, 2010 [Page 30]
Internet-Draft HOLSR July 2009
+--- ---+
_.--------------------------.
L _.----'' `------.
e ,-'' `--.
v ,' `.
e ( E.f.....................F.r )
l `. | | ,'
`--. | | _.-'
3 `------. | |_.----''
`---+----------------------''
+--- | Overall Cluster | ---+
_.----------| _.---+------.
L ,-'' |`--. ,-'' ,'FH.r. `--.
e / | \ / ,' '-. \
v ( A.a.............EH.f ) ( C.p..........D.u )
e \| | / \ | | /
l |--. |_.-' `--.| |.-'
| `----------'| |----------''|
2 | Cluster E | ,------+. Cluster F |
| ,---+-------.,-' | `-. |
+--- | ,-' | B1.h,'`-. C1.m CH.p `. | ---+
| ,----,'---. BH.f / C4.k. \,----+----.
L ,+' / `-. ; \ ,-': | `-.
e / | ( A3.d \B2.g| B5.j ) C2.o /C6.s| | D1.v\
v / AH.a \ B4.e\ : C5.l/ / ; DH.u \
e ( `. ) \ ,' (D4.q/ )
l \ A1.b '-. / B3.i`.,-' \ ,' D2.w /
\ A2.c `---+-------''-. C3.n ,-\ D3.t /
1 `-. ,-'Cluster B `-------' `-. ,-'
`---------' Cluster C `---------'
+--- Cluster A Cluster D ---+
Figure 4 - Data Transfer using Hierarchical Structure
Routing information is updated by all the routers in a given cluster.
Thus, communication between routers in a cluster is achieved via the
routing information in the routing tables. For data transmissions
outside the cluster, the cluster heads are used as gateways. To
describe the communication between clusters, lets look at an example
network with 3 levels.
First, lets specify the terminology of the example. Routers are
represented by a "." followed by a lowercase letter. Figure 4
contains 23 routers labeled from ".a" to ".w". Prefixed to the
router id is a capital character followed by a number, or an H. It
defines the cluster membership of a router and its cluster head
status. In the case where a router is involved in many clusters, on
many levels (because it contains multiple interfaces), the capital
Lacharite, et al. Expires January 14, 2010 [Page 31]
Internet-Draft HOLSR July 2009
letter references the cluster membership from the lowest level. For
example "AH.a" denotes router "a" which is the cluster head "H" of
cluster "A". Similarly, "D3.t" denotes router "t", the 3rd router
member of cluster D, and not a cluster head. On level 2, "C.p" is
member of cluster F, but it is also the same router as level 1 "CH.p"
which is the cluster head of cluster C. A bit more complex, router
"BH.f" is the cluster head of cluster B at level 1, it is the same
router as "EH.f" which is a cluster head of cluster E at level 2, and
it is also the same router as "E.f" which is a member of the overall
cluster at level 3. Hence for the purpose of our example, router .f
has 3 interfaces each one participating at a different level of the
hierarchy. Additionally, in the text description we denote levels
with the prefix <l#->, e.g. <l1-> applies to level 1.
Now, the example: Starting from the base topology level 1, when a
router .b (l1-A1.b) of cluster A wants to transmit data to router .t
(l1-D3.t) from another cluster D; it will route through the hierarchy
levels instead of communicating directly at level 1. Here is the
actual path taken by the data. Router l1-A1.b first sends its
traffic to its cluster head router AH.a (l1-AH.a) -- On the next
topology level 2, cluster head l1-AH.a corresponds to l2-A.a and is a
member of Cluster E -- Router l2-A.a transmits in turn to its cluster
head router l2-EH.f -- which corresponds to l3-E.f on level 3 --
Router l3-E.f transmits to its neighbor l3-F.r -- equivalent to l2-
FH.r on level 2 -- l2-FH.r forwards to l2-D.u -- cluster head of
level one l1-DH.u -- Finally l1-DH.u transmits data to its
destination l1-D3.t. In summary, the data path can be represented
by: l1-D3.t --> l1-AH.a == l2-A.a --> l2-EH.f == l3-E.f --> l3-F.r ==
l2-FH.r --> l2-D.u == l1-DH.u --> l1-D3.t. Or, abstracting the
level/cluster information, traffic traversed 5 hops: .t --> .a --> .f
--> .r --> .u --> .t.
As we trace the path traveled by the data packets, we see that the
cluster head is always used as the gateway by its member routers at
lower hierarchical levels, for destinations outside the cluster. The
rules governing the three levels network can be scaled to a network
with additional topology levels.
Normally, data transmission between clusters follows clustering
hierarchy described above. However, a different transmission path is
used when transmitting data between neighboring routers that belong
to different clusters at the same topology level; in this situation,
the cluster head is not used as a gateway to relay the information to
the destination router in a different cluster. Instead, data is sent
to the neighbor router directly since TC messages are propagated one
hop further on cluster edges to neighbor routers in other clusters.
The depth of the routing infiltration at the edge of clusters is
configurable via the C_INTER_DEPTH parameter. With this strategy the
Lacharite, et al. Expires January 14, 2010 [Page 32]
Internet-Draft HOLSR July 2009
HOLSR makes efficient use of the high-capacity routers without
overloading them.
Appendix B. Example of Cluster Decommission Handling
This appendix gives an example of cluster decommission handling in a
hierarchical network with three levels. It reuses the figure
presented in the Protocol Overview (Section 4). In this example,
node .f has an interface at level 3 that is set to C_CRITICAL_PATH =
'1' (true).
+--- ---+
_.-------\ \----------.
L _.----'' `------.
e ,-'' \ \ `--.
v ,' `.
e ( _.f......\ \......F.r )
L `. | | ,'
`--. | \ \ | _.-'
3 `------. | |_.----''
`---+------------\ \-''
+--- | Overall Cluster | ---+
| _.---+------.
L | ,-'' ,'FH.r. `--.
e | / ,' '-. \
v _.a............._.f ( C.p..........D.u )
e | <--CIA-1--> | \ | | /
l | | `--.| |.-'
| | |----------''|
2 | | ,------+. Cluster F |
| | ,-' | `-. |
+--- | | _.h,' C1.m CH.p `. | ---+
| _.f / C4.k \,----+----.
L | <--CIA-1-->; ,-': | `-.
e | _.d _.g| _.j C2.o /C6.s| | D1.v\
v _.a _.e : C5.l / ; DH.u \
e <--CIA-1--> \ (D4.q/ )
l _.b _.i`. \ ,' D2.w /
_.c '-. C3.n ,-\ D3.t /
1 `-------' `-. ,-'
Cluster C `---------'
+--- Cluster D ---+
Figure 5 - Cluster Head Decommissioning
When the link on layer 3 in-between router .f and .r is broken, the
decommission requirement on router .f is met. Hence, router .f stops
Lacharite, et al. Expires January 14, 2010 [Page 33]
Internet-Draft HOLSR July 2009
being a cluster head on layer 2 and layer 1, and starts to generate
CIA decommission message (CIA-1 in the example, as shown in Figure
5). The immediate impact, is that we see clusters A, B and E de-
associate completely. De-associated routers will now process and
generate CIA messages from cluster C.
+--- ---+
_.-------\ \----------.
L _.----'' `------.
e ,-'' \ \ `--.
v ,' `.
e ( C11.f......\ \......F.r )
L `. | | ,'
`--. | \ \ | _.-'
3 `------. | |_.----''
`---+------------\ \-''
+--- | Overall Cluster | ---+
| _.---+------.
L | ,-'' ,'FH.r. `--.
e | / ,' '-. \
v | ( C.p..........D.u )
e | \ | | /
l | `--.| |.-'
| |----------''|
2 _,,...+----------....__ | Cluster F |
_,,-'' | ``+.._ |
+--- ,-' | C8.h C1.m CH.p`-. | ---+
,-' _,.........-C11.f C4.k `,=---+----.
L / / ,-' \ | `-.
e | | C13.d C10.g C7.j C2.o /C6.s | | D1.v\
v '.C16.a C12.e C5.l / .' DH.u \
e `. (D4.q ,' )
l C15.b C9.i \ ,' D2.w /
`-._C14.c C3.n _.-' D3.t /
1 ``-...__ _,,.,-'' `-. ,-'
`''-----------''' `---------'
+--- Cluster C Cluster D ---+
Figure 6 - Updated Architecture
As shown Figure 6, de-associated routers end up joining cluster C,
which now contains all routers from previous clusters A, B, and E.
Routers .a and .f still are still linked via their second interface
(higher capabability), but their multiple interfaces are now handled
by OLSRv2 (no more HTC messaging required from routers .a and .f
since they are no longer cluster heads).
Note. From this example, it can also be shown that routers .f and .r
Lacharite, et al. Expires January 14, 2010 [Page 34]
Internet-Draft HOLSR July 2009
at level 1 shall not be both set with parameter C_CRITICAL_PATH = 1.
Doing so, if the link in-between these 2 routers fails, all the
network cluster heads would be decommission. It it the
responsibility of the network administrator to ensure that the
C_CRITICAL_PATH parameter gets set properly on strategically selected
routers.
Appendix C. Packet and Message Layout
This appendix illustrates the translation from the abstract
descriptions of packets employed in the protocol specification, and
the bit-layout packets actually exchanged between MANET routers.
C.1. Packet and Message Options
The basic layout of an HOLSR packet, message body, address block, TLV
block, and TLV is as described in [RFC5444], allowing all options.
C.2. Example CIA Message
An example CIA message, using IPv4 (four octet) addresses is as
follows. The overall message length is 37 octets.
The message has the mhasorig, mhashoplimit, mhashopcount, and
mhasseqnum flags of its four-bit flags field set (value 15), and
hence includes an Originator Address, a Hop Limit, a Hop Count, and a
Message Sequence Number (which is type independent). Its four-bit
message Address Length field has value 3, indicating that the message
uses IPv4 address. Thus, the overall message flags octet is of value
243. The message has a Message TLV block with content length 16
octets, containing four message TLVs. These TLVs represent message
validity time, message interval time, CIA Cluster Head Id, and CIA
Cluster Head Distance. Each message TLV has the thasvalue flag of
its flag octet set (value 16), and hence contains a Value field, with
preceding Value Length 1 octet.
The message has one Address Block. It contains the interface address
of the cluster head. The first octet indicates that it contains one
address. The flags octet has the ahashead flag set indicating it has
a head. Its head length is 4, this is equal to the address length,
it thus has no mid section. This Address Block has no TLVs (TLV
block content length is 0 octets).
Lacharite, et al. Expires January 14, 2010 [Page 35]
Internet-Draft HOLSR July 2009
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CIA |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Limit | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | CLUSTER_HD_ID |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | CLUSTER_HD_DST|0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 0 1|1 0 0 0 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 1 0 0| Head |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head (cont) |
+-+-+-+-+-+-+-+-+
C.3. Example HTC Message
An example HTC message, using IPv4 (four octet) addresses, is as
follows. The overall message length is 48 octets.
The message has the mhasorig, mhashoplimit, mhashopcount, and
mhasseqnum flags of its four-bit flags field set (value 15), and
hence includes an Originator Address, a Hop Limit, a Hop Count, and a
Message Sequence Number (which is type independent). Its four-bit
message Address Length field has value 3, indicating that the message
uses IPv4 address. Thus, the overall message flags octet is of value
243. The message has a Message TLV block with content length 17
octets containing four TLVs. The first two TLVs are validity and
interval times as for the CIA message above. The third TLV is the
HTC message type. The fourth TLV is the HTC sequence number TLV used
to carry the 2 octet HTC_SEQ_NUM. Each message TLV has the thasvalue
flag of its flag octet set (value 16), and hence contains a Value
field. First three TLVs have a preceding Value Length 1 octet, and
the last TLV has a preceding Value Length 2 octets.
The message has one Address Block. It contains 6 cluster members'
addresses. The first octet indicates that it contains 6 addresses.
The flag octet has the ahashead flag set indicating it has a head.
Its head length is 2 octets, hence mid sections length is two octets.
Lacharite, et al. Expires January 14, 2010 [Page 36]
Internet-Draft HOLSR July 2009
This Address Block has no TLVs (TLV block content length 0 octets).
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HTC |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Limit | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1| VALIDITY_TIME |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | HTC_MSG_TYPE |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | HTC_SEQ_NUM |0 0 0 1 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 1 0| Value |0 0 0 0 0 1 1 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0| Head |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid | Mid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid | Mid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid | Mid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Authors' Addresses
Yannick Lacharite
Communications Research Centre Canada
3701 Carling Avenue
Ottawa, Ontario K2H 8S2
Canada
Phone: +1 613 998 1207
Fax:
Email: yannick.lacharite@crc.gc.ca
URI:
Lacharite, et al. Expires January 14, 2010 [Page 37]
Internet-Draft HOLSR July 2009
Maoyu Wang
Communications Research Centre Canada
3701 Carling Avenue
Ottawa, Ontario K2H 8S2
Canada
Phone: +1 613 991 1671
Fax:
Email: maoyu.wang@crc.gc.ca
URI:
Pascale Minet
INRIA
Rocquencourt, 78153 Le Chesnay Cedex
France
Phone: +33 1 3963 5233
Fax:
Email: pascale.minet@inria.fr
URI: http://hipercom.inria.fr/~minet
Thomas Clausen
LIX, Ecole polytechnique
92128 Palaiseau Cedex
France
Phone: +33 6 6058 9349
Fax:
Email: t.clausen@computer.org
URI: http://www.thomasclausen.org
Lacharite, et al. Expires January 14, 2010 [Page 38]