draft-ietf-manet-cbrp-spec-00.txt   draft-ietf-manet-cbrp-spec-01.txt 
INTERNET-DRAFT Mingliang Jiang INTERNET-DRAFT Mingliang Jiang
draft-ietf-manet-cbrp-spec-00.txt National University of S'pore draft-ietf-manet-cbrp-spec-01.txt Jinyang Li
Jinyang Li Y.C. Tay
National University of S'pore National University of Singapore
Yong Chiang Tay 14 August 1999
National University of S'pore
August 1998
Cluster Based Routing Protocol(CBRP) Functional Specification Cluster Based Routing Protocol(CBRP)
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
To view the entire list of current Internet-Drafts, please check the The list of current Internet-Drafts can be accessed at:
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow http://www.ietf.org/ietf/1id-abstracts.txt.
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific The list of Internet-Draft Shadow Directories can be accessed at:
Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). http://www.ietf.org/shadow.html.
Abstract Abstract
Cluster Based Routing Protocol (CBRP) is a routing protocol designed Cluster Based Routing Protocol (CBRP) is a routing protocol designed
for use in mobile ad hoc networks. The protocol divides the nodes of for use in mobile ad hoc networks. The protocol divides the nodes of
the ad hoc network into a number of overlapping or disjoint clusters the ad hoc network into a number of overlapping or disjoint 2-hop-
in a distributed manner. A cluster head is elected for each cluster diameter clusters in a distributed manner. A cluster head is elected
to maintain cluster membership information. Inter-cluster routes are for each cluster to maintain cluster membership information. Inter-
discovered dynamically using the cluster membership information kept cluster routes are discovered dynamically using the cluster
at each cluster head. By clustering nodes into groups, the protocol membership information kept at each cluster head. By clustering
efficiently minimizes the flooding traffic during route discovery and nodes into groups, the protocol efficiently minimizes the flooding
speeds up this process as well. Furthermore, the protocol takes into traffic during route discovery and speeds up this process as well.
consideration of the existence of uni-directional links and uses Furthermore, the protocol takes into consideration the existence of
these links for both intra-cluster and inter-cluster routing. uni-directional links and uses these links for both intra-cluster and
inter-cluster routing.
1 Introduction This updated draft has a more detailed description of the cluster
formation and routing process. In addition, it describes 2 major new
features that have been added to the protocol: route shortening and
local repair. Both features make use of the 2-hop-topology
information maintained by each node through the broadcasting of HELLO
messages. The route shortening mechanism dynamically shortens the
source route of the data packet being forwarded and informs the
source about the better route. Local route repair patches a broken
source route automatically and avoids route rediscovery by the
source.
1. Introduction
There are several major difficulties for designing a routing protocol There are several major difficulties for designing a routing protocol
for MANET. Firstly and most importantly, MANET has a dynamically for MANET. Firstly and most importantly, MANET has a dynamically
changing topology due to the movement of mobile nodes which favors changing topology due to the movement of mobile nodes which favors
routing protocols that dynamically discover routes over conventional routing protocols that dynamically discover routes (e.g. Dynamic
distant vector routing protocols [6], e.g. Dynamic Source Routing[4], Source Routing[4], TORA[3], ABR[5] etc.) over conventional distance
TORA[3], ABR[5] etc. Secondly, the fact that MANET lacks any vector routing protocols [6]. Secondly, the fact that MANET lacks
structure makes IP subnetting impossible. However, routing protocols any structure makes IP subnetting inefficient. However, routing
that are flat, i.e. only one level of hierarchy, might suffer from protocols that are flat, i.e. have no hierarchy, might suffer from
excessive overhead when scaled up. Thirdly, links in mobile networks excessive overhead when scaled up. Thirdly, links in mobile networks
could be asymmetric at times. Routing protocols could make use of the could be asymmetric at times. If a routing protocol relies only on
uni-directional links to improve its overall performance. bi-directional links, the size and connectivity of the network may be
severely limited; in other words, a protocol that makes use of uni-
directional links can significantly reduce network partitions and
improve routing performance.
CBRP has the following features: CBRP has the following features:
* fully distributed operation. * fully distributed operation.
* less flooding traffic during the dynamic route discovery process. * less flooding traffic during the dynamic route discovery process.
* explicit exploitation of uni-directional links that would otherwise * explicit exploitation of uni-directional links that would otherwise
be unused. be unused.
* broken routes could be repaired locally without rediscovery.
* sub-optimal routes could be shortened as they are used.
The idea of using clusters for routing in Ad hoc networks has The idea of using clusters for routing in Ad hoc networks has
appeared in [7],[8]. In these protocols clusters are introduced to appeared in [7],[8]. In these protocols clusters are introduced to
minimize updating overhead during topology change. However, the minimize updating overhead during topology change. However, the
overhead for letting each and every node maintain up-to-date overhead for maintaining up-to-date information about the whole
information about the whole network's cluster membership and inter- network's cluster membership and inter-cluster routing information at
cluster routing information in order to route a packet is each and every node in order to route a packet is considerable. As
considerable. In comparison, simpler and smaller clusters are found network topology changes from time to time due to node movement, the
in [9] and [10], however, the use of these clusters is mainly for the effort to maintain such up-to- date information is expensive and
task of channel assignment; how they can help in the routing process rarely justified as such global cluster membership information is
is not discussed. obsolete long before they are used. In comparison, simpler and
smaller clusters are found in [9] and [10]; however, the use of these
clusters is mainly for the task of channel assignment --- how they
can help in the routing process is not discussed.
CBRP adopts the cluster formation algorithm as proposed in [9], but CBRP adopts the cluster formation algorithm as proposed in [9], but
unlike [9], CBRP mainly concentrates on the use of clusters in the unlike [9], CBRP mainly concentrates on the use of clusters in the
routing process. CBRP is different from previously proposed cluster- routing process.
based routing algorithms and it uses a dynamic route discovery
strategy.
2. CBRP terminology 2. CBRP terminology
This section defines terms used in CBRP that do not appear in [2]: This section defines terms used in CBRP that do not appear in [2]:
* Node ID * Node ID
Node ID is a string that uniquely identifies a particular mobile Node ID is a string that uniquely identifies a particular mobile
node. Node IDs must be totally ordered. In CBRP, we use a node's IP node. Node IDs must be totally ordered. In CBRP, we use a node's IP
address as its ID for purposes of routing and interoperability with address as its ID for purposes of routing and interoperability with
fixed networks. fixed networks.
* Cluster * Cluster
A cluster consists of a group of nodes with one of them elected as a A cluster consists of a group of nodes with one of them elected as a
cluster head. The election procedure is described in section 5.1 and cluster head. The cluster formation procedure is described in section
5.2. A cluster is identified by its Cluster Head ID. Clusters are 6.1.
either overlapping or disjoint. Each node in the network knows its
A cluster is identified by its Cluster Head ID. Clusters are either
overlapping or disjoint. Each node in the network knows its
corresponding Cluster Head(s) and therefore knows which cluster(s) it corresponding Cluster Head(s) and therefore knows which cluster(s) it
belongs to. belongs to.
* Host Cluster * Host Cluster
A node regards itself as in cluster X if it has a bi-directional link A node regards itself as in cluster X if it has a bi-directional link
to the head of cluster X. In such a case, cluster X is a host to the head of cluster X. In such a case, cluster X is a host
cluster for this node. cluster for this node. A node could have several host clusters.
* Cluster Head * Cluster Head
A cluster head is elected in the cluster formation process for each A cluster head is elected in the cluster formation process for each
cluster. Each cluster should have one and only one cluster head. A cluster. Each cluster should have one and only one cluster head.
cluster head has complete knowledge about group membership and link
state information in the cluster within a bounded time once the The cluster head has a bi-directional link to every node in the
topology within a cluster stabalizes. In CBRP, each node in the cluster.
cluster has a bi-directional link to the cluster head.
A cluster head will have complete knowledge about group membership
and link state information in the cluster within a bounded time once
the topology within a cluster stabilizes.
Conceptually, two cluster heads are not allowed to have a direct bi-
directional link to each other. If such a link exists, one of the
cluster head will relinquish its role as cluster head to the other.
However in CBRP, we do allow two cluster heads to be able to hear
each other directly for CONTENTION_PERIOD seconds before one cluster
head has to give up its cluster head status; this delays postpones
any cluster re-organization, in case the two clusters are next to
each other only in passing.
* Cluster Member * Cluster Member
All nodes within a cluster EXCEPT the cluster head are called members All nodes within a cluster EXCEPT the cluster head are called members
of this cluster. of this cluster.
* Gateway Node * Gateway Node
A node is called a gateway node of a cluster if it KNOWS that it has Any node a cluster head may use to communicate with an adjacent
a bi-directional or uni-directional link to a node from another cluster is called a gateway node.
cluster. As shown in Figure 1, node 3 and 4 are gateway nodes of
cluster 1, node 6 is a gateway node of cluster 8.
2 5 * HELLO message
// \\
// \\ All nodes broadcast HELLO messages periodically every HELLO_INTERVAL
(1)===3==6====(8) seconds; a node's HELLO message contains its Neighbor Table and
\\ // Cluster Adjacency Table. A node may sometimes broadcast a triggered
\\ // HELLO message in response to some event that needs quick action.
4<------7
3. Conceptual Data Structures
Fig. 1
* Neighbor Table * Neighbor Table
The neighbor table is a conceptual data structure that we employ for The neighbor table is a conceptual data structure that we employ for
link status sensing and cluster formation. Each entry contains the ID link status sensing and cluster formation. Each entry contains
of a neighbor that it has connectivity with and the status of that - the ID of the neighbor that it has connectivity with and
link and the role of the neighbor (a leader or a member). - the role of the neighbor (a cluster head or a member).
- the status of that link (bi-directional or uni-directional)
3. Physical and Link Layer Assumptions * Cluster Adjacency Table
This section lists the assumptions we made about the underlying The Cluster Adjacency Table keeps information about adjacent clusters
physical and link layers when designing CBRP. Each node in MANET is and is maintained by CBRP's Adjacent Cluster Discovery procedure.
equipped with a transceiver. In general, CBRP works best with Each entry contains:
omnidirectional antennas. Each packet that a node sends is broadcast
into the region of its radio coverage.
4. Link/Connection Status Sensing Mechanism - the ID of the neighboring cluster head
- the gateway node (a member) to reach the neighboring
cluster head
- the status of the link from the gateway to the neighboring
cluster head (bi-directional or uni-directional)
* Two-hop Topology Database
In CBRP, each node broadcasts its neighbor table information periodi-
cally in HELLO packets. Therefore, by examining the neighbor table
from its neighbors, a node is able to gather `complete' information
about the network topology that is at most two-hops away from itself.
This two-hop topology information is kept in a data structure in each
node.
4. Physical and Link Layer Assumptions
This section lists the assumptions we made about the underlying phys-
ical and link layers when designing CBRP.
Each MANET node that runs CBRP is equipped with one wireless
transceiver. CBRP is capable of handling multiple transceivers per
host and multiple hosts per router if the concept of a router ID is
introduced. For example, a host with multiple transceivers may
select the smallest IP interface address as its router ID.
CBRP assumes omnidirectional antennas. Each packet that a node sends
is broadcast into the region of its radio coverage. CBRP is designed
to operate on top of a single-channel broadcast medium, however, it
also accommodates the presence of multiple channels by forming dif-
ferent sets of clusters for each channel for the same group of mobile
nodes in a manner similar to that described in [11].
5. Link/Connection Status Sensing Mechanism
In CBRP, each node knows its bi-directional links to its neighbors as In CBRP, each node knows its bi-directional links to its neighbors as
well as unidirectional links from its neighbors to itself. For this well as uni-directional links from its neighbors to itself. For this
purpose, each node maintains a Neighbor Table as follows: purpose, each node maintains a Neighbor Table as follows:
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
| NEIGHBOR_ID| LINK_STATUS | ROLE | | NEIGHBOR_ID| LINK_STATUS | ROLE |
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
| neighbor 1 | bi/unidirectional link to me? | is 1 a cluster head?| | neighbor 1 | bi/unidirectional link to me? | is 1 a cluster head?|
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
| neighbor 2 | bi/unidirectional link to me? | is 2 a cluster head?| | neighbor 2 | bi/unidirectional link to me? | is 2 a cluster head?|
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
| ... | ...
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
| neighbor N | bi/unidirectional link to me? | is N a cluster head?| | neighbor N | bi/unidirectional link to me? | is N a cluster head?|
+------------+-------------------------------+---------------------+ +------------+-------------------------------+---------------------+
Each node broadcasts its Neighbor Table periodically in a HELLO Each node periodically broadcasts its Neighbor Table in a HELLO mes-
message as shown below every HELLO_INTERVAL. sage, as shown below, every HELLO_INTERVAL.
+-----------+------------------------------------------------------+ 0 1 2 3
| MY_OWN_ID | MY_MEMBERSHIP_STATUS | 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
| | (CLUSTER_HEAD/CLUSTER_MEMBER/UNDECIDED) | +-+-+-+-+-+-+-+-+
+-----------+------------------------------------------------------+ | Length | S |
| Neighbor Table | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+------------------------------------------------------------------+ |L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|L|R|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor1 IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor2 IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
The first field specifies the ID of the sender. The second field Length The number of neighbours listed.
tells whether the sender is a cluster head, cluster member or
undecided. ("undecided" means a node is still in search of its host S(Status) The current status of the sender.
cluster) 0 --- Undecided (C_UNDECIDED)
1 --- Cluster Head (C_HEAD)
2 --- Cluster Member (C_MEMBER)
L Link Status of the corresponding neighbor of the sender.
0 --- LINK_BIDIRECTIONAL
1 --- LINK_FROM
R Role of the corresponding neighbor of the sender.
0 --- Non-Cluster-Head(C_MEMBER or C_UNDECIDED)
1 --- Cluster Head (C_HEAD)
The IP addresses of the neighbors and the L and R bits are taken from
the neighbor table. The ID of the sender is specified in the source
field of the IP header. The status field tells whether the sender is
a cluster head, member or undecided. (The state of Undecided is
defined in Section 6.1) An 4 byte long L/R bit block appears after
every 16 neighbor addresses. In the case that there are no more than
16 neighbors listed, there will be only one such L/R bit block.
Upon receiving a HELLO message from its neighbor B, node A modifies Upon receiving a HELLO message from its neighbor B, node A modifies
its own Neighbor Table as follows: its own Neighbor Table as follows:
1. It checks if B is already in the Neighbor Table, if not, it 1. It checks if B is already in the Neighbor Table; if not, it
adds one entry for B. adds one entry for B if it has heard from B in the previous
2. If B's Neighbor Table contains A, A marks the link to B as HELLO_INTERVAL before (i.e. A enters B in its Neighbor Table
bi-directional in the relevant entry. only when A has heard from B's HELLO messages twice in
3. If B is cluster head, marks B as a cluster head in the entry. HELLO_INTERVAL interval).
If B's Neighbor Table contains A,
A marks the link to B as bi-directional in the relevant
entry
else A marks the link to B as uni-directional (uni-directional
from B to A).
2. If B is already in A's Neighbor Table,
2.1. If the link_status field of B's entry says bi-directional
but A is not listed in B's hello message, then change it
to uni-directional;
2.2. If the link_status field of B's entry says uni-direc-
tional but A is listed B's hello message, then change it
to bi-directional.
3. Update the role of B in the Role field of B's entry.
Each entry in the Neighbor Table is associated with a timer. A table Each entry in the Neighbor Table is associated with a timer. A table
entry will be removed if a HELLO message from the entry's node is not entry will be removed if a HELLO message from the entry's node is not
received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing
HELLO_LOSS consecutive HELLO messages to be lost from that node. HELLO_LOSS consecutive HELLO messages to be lost from that node.
When a nodes' neighborhood topology stabilizes, each node will have When a node's neighborhood topology stabilizes, the Neighbor Table of
complete knowledge of all the nodes that it has a bi-directional link a node will have complete information of all the nodes that have a
to and all the nodes that have a uni-directional link to it within a bi-directional or uni-directional link to it within a bounded time.
bounded time. However, a node would not know to whom it has a uni- However, a node would not know to whom it has a uni-directional link.
directional link. For example in Figure 1, the Neighbor Table of node 7 will show that
4 has a uni-directional link to it, however node 4 would not know of
the existence of such a link.
Note that the 2nd and 3rd column of the neighbor table need not be 8 5
sent out for the purposes of link sensing, however, they are there // \\ ==== bi-directional link
mainly for cluster formation and other functionality of the protocol. // \\
(1)===3==6====(2) (1), (2) cluster heads
\\ //
\\ // ---> uni-directional link
4------>7
5. Protocol Operation Fig. 1
The operations of CBRP are entirely distributed. According to the Note that the 2nd and 3rd column of the neighbor table and the status
functionality, CBRP could be viewed as a combination of the three field of the hello message need not be used for the purpose of link
following sub-functions which will be discussed below. sensing; they are there mainly for cluster formation and adjacent
cluster discovery, which will be discussed in Section 6.
5.1 Cluster Formation In addition to maintaining the Neighbor Table at each node, the peri-
odic broadcasting of HELLO messages also enables each node to gain
complete information about all bi-directional links within two-hops.
Such information is kept in a data structure we call the two-hop-
topology database. By checking its 2-hop-topology database, a node
can tell who are its 2-hop bi-directionally linked neighbors and
through which intermediate nodes can they be reached. The format of
this 2-hop-topology database is implementation dependent.
The Cluster Formation algorithm is a simple "lowest ID" clustering 6. Protocol Operation
algorithm in which the node with a lowest ID is elected as the
Cluster Head [9].
A node uses the information obtained from the HELLO message for The operations of CBRP are entirely distributed. The major compo-
Cluster Formation. A node that has the lowest ID among all its bi- nents are: Cluster Formation, Adjacent Cluster Discovery and Routing.
directionally linked neighbors (a node that has given up the role as
a Cluster Head is not counted, i.e. a cluster member node ). The new
Cluster Head will change the first field in its subsequently
broadcast HELLO messages from "undecided" to "cluster head"
thereafter.
A cluster head regards all the nodes it has bi-directional links to 6.1 Cluster Formation
as its member nodes. A node regards itself as a member node for a
particular cluster if it has a bi-directional link to the
corresponding cluster head. Note that a member node may hear from
several cluster heads and therefore have several host clusters.
5.2 Cluster Maintenance The goal of Cluster Formation is to impose some kind of structure or
hierarchy in the otherwise completely disorganized ad hoc network.
The algorithm is a variation of the simple "lowest ID" clustering
algorithm in which the node with a lowest ID among its neighbors is
elected as the Cluster Head [11].
Apart from the states of C_MEMBER and C_HEAD, we define a transi-
tional state called C_UNDECIDED for smoother operation of cluster
formation. "Undecided" means that a node is still in search of its
host cluster. All nodes wake up in the Undecided state. We will refer
to a node in the undecided state as an undecided node hereafter.
A node uses the information obtained from the HELLO messages for
Cluster Formation. An Undecided node schedules a u_timer to go off in
UNDECIDED_PD seconds and broadcast a HELLO message whenever it enters
the C_UNDECIDED state. When a cluster head receives a HELLO message
from an Undecided Node, it will send out a triggered HELLO message
immediately. If an undecided node receives a HELLO message from a
Cluster Head indicating a bi-directional link in between, it aborts
its u_timer and sets its own status to C_MEMBER. When the u_timer
times out, if the node's Neighbor Table contains no bi-directional
neighbors, then it re-enters the Undecided state; otherwise it elects
itself as a Cluster Head. The new Cluster Head will change the first
field in its subsequently broadcast HELLO messages from C_UNDECIDED
to C_HEAD thereafter.
A cluster head regards all the neighbors that it has bi-directional
links to as its member nodes. A node regards itself as a member node
for a particular cluster if it has a bi-directional link to the cor-
responding cluster head. Note that a member node may hear from sev-
eral cluster heads and therefore have several host clusters; its host
cluster heads are implicitly listed in the HELLO messages it broad-
casts.
As clusters are identified by their respective cluster heads, we As clusters are identified by their respective cluster heads, we
would like to have the cluster heads change as infrequently as would like to have the cluster heads change as infrequently as possi-
possible. We use the following rules for changing cluster head, as ble. We use the following rules for changing cluster head, as
described in [10]. described in [10].
1. A non-cluster head never challenges the status of an existing 1. A non-cluster head never challenges the status of an existing
cluster head, i.e. if X is a non-cluster head node with a cluster head, i.e. if X is a non-cluster head node with a
bi-directional link to cluster head Y, X does not become bi-directional link to cluster head Y, X does not become
a cluster head even if it has an ID lower than Y's. a cluster head even if it has an ID lower than Y's.
2. Only when two cluster heads move next to each other (i.e. there 2. When two cluster heads move next to each other (i.e. there
is a bi-directional link between them), one of them loses the is a bi-directional link between them) over an extended period
role of cluster head. of time (for CONTENTION_PERIOD seconds), then only will one of
them lose its role of cluster head.
Therefore, our exact algorithm is not a strict "lowest ID" clustering As a result, whenever a cluster head hears HELLO messages from
algorithm. The cluster maintenance procedure are discussed under another cluster head indicating a bi-directional link, it sets
three subsections: c_timer to expire in CONTENTION_PERIOD seconds. When c_timer
expires, it will check if it is still in contention with the other
cluster head, by checking if the other cluster head is still in its
neighbor table. If so, it compares its own ID with that of the other
cluster head's. The one with a smaller ID will continue to act as
cluster head. The one with a bigger ID gives up its role as cluster
head and changes from C_HEAD to C_MEMBER in its subsequent HELLO
messages. This might trigger reorganization of other clusters.
* Node Removal Whenever a member node's last cluster head entry times out, this node
checks among its bi-directionally linked neighbors if it has the low-
est ID, if so it changes its state to C_HEAD and sends out a trig-
gered HELLO, otherwise it goes to C_UNDECIDED state.
A node X is removed from a host cluster either because it loses the A simplified state transition diagram without considering unidirec-
bi-directional links to the cluster head, or because of node tional links for Cluster Formation is shown in Appendix A.
failures. In either case, the cluster head and node X will time out
the corresponding entries in their Neighbor Table so that the cluster
information will be updated.
* Node Addition 6.2 Adjacent Cluster Discovery
A member node is added to a new cluster when it discovers a bi- Cluster X and cluster Y are said to be bi-directionally linked, if
directional link to the respective cluster head even if the cluster any node in cluster X is bi-directionally linked to another node in
head has a higher ID, which is consistent with rule 1. The node will cluster Y, or if there is a pair of opposite uni-directional links
know its new host cluster and the new host cluster head will know its between any 2 nodes in cluster X and cluster Y respectively. For
new member through the updated Neighbor Table. example in Figure 2, cluster 1 and cluster 2 are bi-directionally
linked by the pair of links 3->4 and 5->6.
When a node is switched on, its MY_MEMBERSHIP_STATUS field in the Cluster X is said to be uni-directionally linked to cluster Y if they
HELLO message is initially UNDECIDED for a period of UNDECIDED_PD. If are not bi-directionally linked and if there exists some node in
it discovers that it has a bi-directional link to a cluster head, it cluster X that is uni-directionally linked to some node in cluster Y.
modifies this field as CLUSTER_MEMBER. If there is no such bi- X is called Y's upstream uni-directionally linked adjacent cluster,
directional links to any cluster head, it takes the role as a cluster and vice versa. For example, in Figure 1, cluster 1 is cluster 2's
head and indicates this in the subsequent HELLO messages it sends. upstream uni-directionally linked adjacent cluster.
* Cluster Head Contention The goal of Adjacent Cluster Discovery is for a cluster to discover
all its bi-directionally linked adjacent clusters. For this purpose,
each node keeps a Cluster Adjacency Table (CAT) that records informa-
tion about all its neighboring cluster heads.
When two Cluster Heads move next to each other (till they have a bi- Note that for member nodes, neighboring cluster heads are always two
directional link in-between), one of them must give up its role as hops away and can be discovered by checking received HELLO messages.
cluster Head. As a result, whenever a cluster head hears the HELLO For a cluster head, its neighboring cluster heads could be 2 or 3
message from another cluster head indicating a bi-directional link in hops away (see Figure 2). Using the HELLO messages alone, a cluster
between, it will compare its own ID with that of the other cluster head is able to discover the cluster heads 2 hops away. However, it
head's. The one with a smaller ID will continue to act as cluster has to rely on its member nodes' Cluster Adjacency Table to discover
head. The one with a bigger ID gives up its role as cluster head and those neighboring cluster heads that are 3 hops away.
changes from "cluster head" to "member" in its subsequent HELLO
messages. This might trigger the formation of other new clusters.
5.3 Routing Considerations The format of CAT at each node is as follows:
Routing in the CBRP is based on source routing, which is similar to +--------------+ +--------+-----------+ +--------+-----------+
[4]. Therefore, it can be viewed as consisting of 3 phases: route |Adj. Cluster1 |->|gateway1|link status|->|gateway2|link status|
discovery, packets routing and stale route removal, of which packet +--------------+ +--------+-----------+ +--------+-----------+
routing is trivial. |Adj. Cluster2 |->|gateway1|link status|->|gateway2|link status|
+--------------+ +--------+-----------+ +--------+-----------+
|...
+------------------------------------------------------------+
Cluster structure is exploited to minimize the flooding traffic Gateway field contains the ID of the gateway node through which the
during route discovery phase. Furthermore, some uni-directional links neighboring cluster head could be reached. Gateway node is the mem-
are discovered and used which increases network connectivity. This is ber node of the adjacent cluster and hence always has a bi-direc-
discussed in the Gateway Discovery section. tional link to the neighboring cluster head. The link status refers
to the status of the link between a node's gateway node and itself.
The possible values are LINK_BIDIRECTIONAL, LINK_FROM, LINK_TO where
LINK_FROM means there is a uni-directional link from gateway node to
itself and LINK_TO means there is a uni-directional link from itself
to the gateway. Note that there may be several gateway nodes leading
towards a particular adjacent cluster.
5.3.1 Gateway Discovery This table is updated by the periodic HELLO messages a node hears. A
member node finds out cluster heads that are exactly 2 hops away and
records them in its CAT. In particular, whenever a node A receives a
HELLO message from B, it scans through the message's list of entries.
If there is a cluster head C and the link status of the entry is
LINK_BIDIRECTIONAL (i.e. B is a member node of cluster C) and, fur-
thermore, C is not already A's host cluster, A adds an entry in CAT
for adjacent cluster C with gateway node B and link status specifying
status of link between A and B.
Cluster X and cluster Y are said to be bi-directionally linked, if In order for cluster heads to gain information on their adjacent
any node in cluster X is bi-directionally linked to another node in clusters that are 3 hops away, each member node broadcasts its summa-
cluster Y, or if there is a pair of opposite uni-directional links rized CAT as a Cluster Adjacency Extension to the HELLO message.
between any 2 nodes in cluster X and cluster Y respectively. (Only member node will send out this information, this is not the
case with cluster heads.) The rules for summarizing is as follows:
Cluster X is said to be uni-directionally linked to cluster Y if any - If there is at least one gateway with whom the node has a
node in cluster X is uni-directionally linked to any other node in bi-directional link, it advertise the neighboring cluster as
cluster Y. Y is called X's upstream uni-directionally linked bi-directionally reachable.
neighboring cluster.
By Gateway Disvoery, a cluster head for cluster X will obtain the - If there are only uni-directional links (LINK_FROM), the
information about cluster X's bi-directionally and upstream uni- neighboring cluster will be advertised as LINK_FROM.
directionally linked neighboring clusters. (Note that, by HELLO messages alone, a node is not able to
detect any LINK_TO link to the gateway.)
For this purpose, a Cluster Adjacency table is kept at each node The format of the Cluster Adjacency Extension to HELLO message is
which is formatted as follows: shown below:
+------------------+-----------------------------------------------+ 0 1 2 3
|Adjacent Cluster1 | adjacent node|to/from/bi | 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
+------------------+-----------------------------------------------+ +-+-+-+-+-+-+-+-+
|Adjacent Cluster2 | adjacent node|to/from/bi | | Length |
+------------------+-----------------------------------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|... | |L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|
+------------------------------------------------------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Adj. Cluster Head1 IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Adj. Cluster Head2 IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ....
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This table is updated by the periodic HELLO message a node hears. Length The number of clusterheads listed in the Extension.
Note that a node may have several links to nodes in a particular
cluster and only one of them is recorded in the Cluster Adjacency
Table. The selection rule is as follows:
1. A bi-directional link takes precedence over all uni-directional L Link Status of the corresponding Adjacent Cluster
links. head. If there is at least one gateway node having
2. Of the links that have the same precedence, the one with the bi-directional link to the Adjacent Cluster head,
lowest ID wins. the Link status is specified as LINK_BIDIRECTIONAL.
Otherwise, it is LINK_FROM.
This table is periodically sent to the member node's host cluster 0 --- LINK_BIDIRECTIONAL
heads. (It could be piggybacked to the HELLO message if possible.) A 1 --- LINK_FROM
cluster head uses its members' Cluster Adjacency table to construct
its own cluster adjacency table. The construction rule is the same
as that of the member's.
Cluster head will flood its neighboring clusters with a message of In addition to using HELLO messages to construct its CAT consisting
TTL 3 in search for the "to" link that corresponds to a "from" link of 2-hop away neighboring cluster heads, a cluster head could check
in its Cluster Adjacency Table. As a result, cluster heads will have its members' Cluster Adjacency Extension to find out its 3-hop away
complete knowledge of all its bi-directionally linked neighboring neighboring cluster heads in its CAT. In particular, suppose cluster
clusters even if there is no actual bi-directional links in between. head A receives B's HELLO message. After updating its CAT with the
For example, in Fig 1, Cluster 1 knows that 2 can reach cluster 1 Neighbor Table entries in HELLO, A proceeds to check B's Cluster
through 5, but 1 does not know that cluster 2 can be reached by node Adjacency Extension in HELLO, if it finds adjacent cluster head C
3. In CBRP, cluster head 1 and 2 will discover this scenario and that is not already reachable within 2 hops, it creates a new entry
disseminate the information to node 3 and 5 respectively. in CAT for it with the gateway node as B and link status as specified
in the extension.
If a cluster head finds that some adjacent clusters are reachable
only through a LINK_FROM uni-directional link, it will flood its
neighborhood with a message of TTL 3 in search for a "to" link that
corresponds to this "from" link. This message will contain the cor-
responding entry for the adjacent cluster. When a cluster head
receives such a message searching for it, it will check if it con-
tains a corresponding LINK_FROM entry to the source cluster head. If
so, it will send out a reply with the corresponding CAT entry and
update its CAT with the new LINK_TO entry as specified in the
message. As a result, cluster heads will have complete knowledge of
all its bi-directionally linked adjacent clusters even if there is no
actual bi-directional links in between. For example, in Figure 2,
Cluster 1 knows that 2 can reach cluster 1 through 5, but 1 does not
know that cluster 2 can be reached through node 3. In CBRP, cluster
head 1 and 2 will discover this scenario and disseminate the informa-
tion to node 3 and 5 respectively.
3-->4 3-->4
// \\ 1 and 2 are heads of their respective // \\ 1 and 2 are heads of their respective
// \\ clusters, 3,4,5,6 are members. // \\ clusters, 3,4,5,6 are members.
(1) (2) (1) (2)
\\ // \\ //
\\ // \\ //
6<--5 6<--5
Fig. 2 Fig. 2
5.3.2 Route Discovery 6.3 Routing Considerations
Routing in CBRP is based on source routing. It can be viewed as con-
sisting of 2 phases: route discovery and the actual packets routing.
Cluster structure is exploited to minimize the flooding traffic dur-
ing route discovery phase. Furthermore, certain uni-directional links
are discovered and used, thus increasing the network connectivity.
6.3.1 Route Discovery
Route Discovery is the mechanism whereby a node S wishing to send a Route Discovery is the mechanism whereby a node S wishing to send a
packet to a destination D obtains a source route to D. Similar to packet to a destination D obtains a source route to D. Similar to
other MANET protocols [4] [1], the way S finds a route(or multiple other MANET protocols [4] [1], the way S finds a route(or multiple
routes) to D is also done by flooding, however, because of the routes) to D is also done by flooding, however, because of the clus-
clustering approach the number of nodes that are disturbed are much tering approach the number of times nodes are disturbed are much less
less in general. in general.
Essentially in Route Discovery, cluster heads are flooded in search Essentially, in Route Discovery, only cluster heads are flooded with
for a source route. To perform Route Discovery, the source node S Route Request Packets (RREQ) in search for a source route. The for-
sends out a Route Request Packet (RREQ), with a recorded source route mat of such a packet is shown below:
listing only itself initially. Any node that forwards this packet
will append its own ID in this RREQ. Each node forwards a RREQ 0 1 2 3
packet only once and it never forwards it to a node that has already 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
appeared in the recorded route. In CBRP, the RREQ will always follow +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
a route with the following pattern to reach destination D: |1 0| Num1 | Num2 | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Target Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Node Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighboring Cluster Head[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|..... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Node Address[Num1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighboring Cluster Head[Num1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cluster Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cluster Address[Num2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
10 type of CBRP packet (Route Request)
Num1 the number of Gateway Node Address
& Adjacent Cluster Address pairs
Num2 the number of Cluster Addresses
Identification a number the RREQ originator generates
to uniquely identify this RREQ sent by it.
Gateway Node Address the gateway node who will forward this RREQ
N'ghboring ClusterHead the corresponding cluster head the gateway
node will forward this RREQ to.
To perform Route Discovery to D, the source node S sends out an RREQ,
with the target node address field set to D. It fills the Neighboring
Cluster Head entries with its host cluster head(s) and adjacent clus-
ter head entries(from CAT), the corresponding Gateway Node Address is
either the host cluster head itself or the adjacent cluster's gateway
node. This initial RREQ is broadcast.
1. Whenever a member node M receives an RREQ,
if D is its neighbor, RREQ is just uni-cast to D.
else
if M is specified as the Gateway Node[x],
uni-cast(relay) the RREQ to Cluster Head[x].
else
discard the RREQ.
2. Whenever a cluster head C receives an RREQ,
2.1 if it has seen this RREQ before (by looking at the identification
field) discard it; otherwise, continue.
2.2 records its own address in Cluster Address list.
2.3
if D is its neighbor or is 2-hop away
uni-cast RREQ to D.
else
for each bi-directionally linked cluster head CH in C's CAT
if CH is already in previous RREQ's
Neighboring Cluster Head list,
skip
else if CH is in Cluster Address list
skip
else
record CH entry in Neighboring Clusterhead/Gateway Node pair
broadcast RREQ
Each cluster head node forwards an RREQ packet only once and it never
forwards it to a node that has already appeared in the recorded
route. In CBRP, the RREQ will always follow a route with the follow-
ing pattern to reach destination D:
S,CH1,G1,CH2,G2,G3,CH3 ..... D S,CH1,G1,CH2,G2,G3,CH3 ..... D
A detailed description of how this is achieved is presented below. The recorded route in Cluster Address list will be CH1, CH2, CH3 ...
Source always unicasts RREQ to its cluster head, say CH1. Each
cluster head will unicast RREQ to each of its bi-directionally linked
neighbors which have not yet appeared in the recorded route through
the corresponding gateway. This process continues until the target is
found or until another node that can supply a route to the target is
found.
When the target of the Request, node D, receives the RREQ, D may When the target of the Request, node D, receives the RREQ, D sends
choose to memorize the reversed source route to S. Node D then out an RREP packet to S as a reply, with the following format:
copies the recorded source route into a Route Reply packet(RREP)
which it then sends back to the initiator of the Route Request (e.g.,
node S) by reversing the recorded route and putting it in the IP
header of the Route Reply packet. The recorded route gives the
complete information about the SEQUENCE OF CLUSTERS source should
traverse in order to reach destination D. While forwarding the Route
Reply, intermediate cluster heads modifies the IP header of the
packets, substitute the inter-cluster incoming links to inter-cluster
outgoing links. Each intermediate cluster head also modifies the
recorded route in the Route Reply packet to optimize the recorded
route as much as possible using its knowledge of the cluster topology
and inter-cluster gateway information. An example of such
optimization is to connect two gateway nodes by an intra-cluster link
that does not go through the cluster head.
All source routes learned by a node are kept in a Route Cache, which 0 1 2 3
is used to further reduce the cost of Route Discovery. When a node 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
wishes to send a packet, it examines its own Route Cache and performs +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Route Discovery only if no suitable source route is found in its |0 1| Num1 |G| Num2 | Identification |
cache. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cluster Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cluster Address[Num1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Calculated Route[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Calculated Route[Num2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
5.3.3 Route Removal 01 type of CBRP packet (Route Reply)
G the flag indicating if this RREP is a
gratuitous reply packet(refer to 5.3.3)
Identification the identification number copied from the
corresponding RREQ.
Num1 the number of Cluster Addresses
Num2 the number of addresses in Calculated Route
Cluster Address copied from the corresponding RREQ. This is
the sequence of cluster heads the RREP will
traverse in order to reach RREQ originator.
(This sequence will be shortened by for-
warding cluster heads along the way and the
last address will always be the next stop
cluster head to forward this RREP).
Calculated Route A sequence of addresses of the hop by hop
source route calculated by the clusterhead.
A source route is removed from S if the network topology has changed D copies the list of Cluster Addresses into the RREP packet. (D may
such that S can no longer use the route to D because a hop along the choose to memorize the reversed list of Cluster Addresses to S so
route no longer works. If S still wants to communicate with D, it can that if D wants to find out a route to S, it may directly probe this
invoke Route Discovery again to find a new route. route of cluster heads). D also copies the identification field in
RREQ to RREP and puts its own address in Calculated Route[1].
6. Discussions and Implementation Considerations The recorded Cluster Addresses gives the complete information about
the SEQUENCE OF CLUSTERS RREP should traverse in order to reach S.
Since each cluster head has knowledge of how to reach its neighboring
CHs, the RREP packet will be routed to S eventually using IP loose
source routing.
While forwarding the Route Reply, intermediate cluster heads will
calculate an optimized hop-by-hop route according to the information
contained in the list Cluster Addresses and put it in the Calculated
Route field.
For example, 1. suppose cluster head C receives a RREP
1.1 It decrements Num1 by 1.
Cluster Address[Num1] is the neighboring cluster head
that C should forward RREP to in order to reach S.
1.2 C tries to find out a gateway node X to Cluster Address[Num1]
such that the Calculated Route[Num2] could reach X directly.
If it succeeds,
send RREP to X
else,
C increment Num2 by 1 and C records itself in Calculated
Route[Num2]. 2. suppose member node M receives a RREP
2.1 It increments Num2 by 1 and records itself in
Calculated Route[Num2].
2.2 if Cluster Address[Num1] is its Neighbor,
send RREP to it directly
else if Cluster Address[Num1] could be reached by X,
send RREP to X.
If a source does not receive any RREP after sending out RREQ for cer-
tain period of time, it goes into exponential backoff before re-send-
ing RREQ.
As usual, all source routes learned by a node are kept in a Route
Cache. When a node wishes to send a packet, it always examines its
own Route Cache first before performing Route Discovery.
6.3.2 Routing
The actual routing is done using Source Routing and the format of the
packet is shown below:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0| Num |R|S|Current Num|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[Num] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 CBRP packet type (Normal data packet containing a
source routing header.)
Num the number of addresses in the source route
Address[1..Num]
Current Num specifies the currently visited address.
R flag indicates if this route has been salvaged using local
repair
S flag indicates if this route has been shortened
* Route Shortening
Due to node movement or other reasons, a source route may become less
optimal over time and should be shortened whenever possible. The
route shortening mechanism shortens sub-optimal routes locally using
the 2-hop-topology database information.
It works as follows:
Whenever a node receives a source-routed data packet, it tries to
find out the furthest node in the unvisited route that is actually
its neighbor. If it succeeds, it shortens the source route accord-
ingly and sets the S flag before forwarding the packet.
When a destination node receives a data packet with S flag set, it
sends back a gratuitous RREP (setting the G flag in RREP) containing
the shortened route to the packet source to inform it of the better
route.
* Route Error
When a forwarding node finds out that the next hop along the source
route for an unsalvaged packet is no longer reachable, it will create
a Route Error (ERR) packet and send it back to the packet source to
notify it of the link failure. The format is shown below:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 1| Num | Current Num |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[Num] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Broken Link From_Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Broken Link To_Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
11 CBRP Packet type (Route Error packet).
Num the number of addresses in the source route.
Address the source route this ERR packet has to traverse
in order to reach its destination. It is taken from
the source route of the data packet.
From_Address the ERR originator's own address.
To_Address unreachable next hop as specified in the original
source route of the data packet.
* Local Repair
After the forwarding node detects a broken route and sends out an ERR
packet, it will try to salvage the data packet the best way it can
using its own local information:
1. It checks if the hop after next in the source route is reachable
through an intermediate node other than the one specified as the
next hop by searching through its 2-hop-topology database.
2. It checks if the unreachable next hop could be reached through
an intermediate node by checking its 2-hop-topology database.
3. If the packet could be saved, it
modifies the source route, sets the R flag and sends out the
packet to the new next hop.
Because of spatial locality, even though the next hop node moves out
of reach from the current node, it is possible that it can still be
reached within 2 hops. Our simulation shows that this Local Repair
mechanism works very well, saving a majority of data packets.
When a destination node receives a data packet with R flag set, it
sends back a gratuitous RREP (setting the G flag in RREP) containing
the repaired route to the packet source to inform it of the repaired
route, avoiding unnecessary route re-discovery.
7. Discussions and Implementation Considerations
7.1 ARP Optimization
ARP is necessary as a node needs to know the MAC address of the next
hop in order to send a packet. In CBRP, however, the next hop a node
sends the packet to is always its neighbor node. If a node records
the source MAC to IP mapping in ARP cache whenever it receives a
HELLO message, it could completely avoid ARP message exchange during
routing.
7.2 Problems with Uni-directional links
This section discusses some of the problems that we have encountered This section discusses some of the problems that we have encountered
during the design of CBRP. In particular, they are related to the use during the design of CBRP. In particular, they are related to the use
of uni-directional links in routing. of uni-directional links in routing.
6.1 ARP and Uni-directional links 7.2.1 ARP problem
In a MANET context, links between 2 nodes can be bi-directional and In a MANET context, links between 2 nodes can be bi-directional and
uni-directional. However, when the link layer does MAC-layer uni-directional. However, when the link layer does MAC-layer
address based packet filtering, (which most current technologies do), address-based packet filtering (which most current technologies do),
special care has to be taken for ARP for uni-directional links. For special care has to be taken with ARP for uni-directional links. For
example, when there is a uni-directional link from node A to node B example, when there is a uni-directional link from node A to node B
as shown in Figure 2, node A should not rely on the conventional ARP as shown in Figure 3, node A should not rely on the conventional ARP
protocol to resolve node B's MAC layer address, because node B's ARP protocol to resolve node B's MAC layer address, because node B's ARP
reply will never reach node A directly. reply will never reach node A directly.
A---->B A---->B
Fig. 3 Fig. 3
CBRP is able to use uni-directional links. For an intra-cluster uni- CBRP is able to use uni-directional links. For an intra-cluster uni-
directional link, the upstream node can be informed by its cluster directional link, the upstream node can be informed by its cluster
head of the MAC-layer address of the downstream node. For a inter- head of the MAC-layer address of the downstream node. For an inter-
cluster uni-directional link, as shown in Figure 1, node 3(5) will cluster uni-directional link, as shown in Figure 2, node 3(or 5) will
know node 4(6)'s MAC-layer address by the process of gateway know node 4(or 6)'s MAC-layer address by the process of adjacent
discovery. cluster discovery.
6.2 Rate of Stale Route Discovery and Uni-directional Links 7.2.2 802.11 Link Layer Technology
It seems hard to make good use of uni-directional links without vio-
lating the standard 7-layer OSI model. The current 802.11 MAC layer
does not consider the existence of uni-directional links, nor does it
support them. The sequence of RTS/CTS/Data/ACK exchange will auto-
matically exclude the use of any uni-directional links even if one
knows their existence.
One possible extension to this technology is to allow ACKs to be for-
warded by neighboring cluster heads back to the sender if a uni-
directional link between two clusters are being used. Such a return
path is bounded by maximum 5 hops. The forwarding of ACK could be
viewed as collapsing layer 2 and layer 3 routing functionality, a
violation of the layering model which states that lower layer should
hide details away from upper layers. Although this seems rather
inefficient at first sight, if we consider the fact the bi-direc-
tional links are preferred over uni-directional links in CBRP, we
would realize that such a uni-directional link will not be used
unless one cannot reach a specific node using bi-directional links
only.
7.3 Rate of Stale Route Discovery and Uni-directional Links
In general (not pertaining to CBRP), when uni-directional links are In general (not pertaining to CBRP), when uni-directional links are
used, discovery of stale routes can be slow. As shown in Figure 3, used, discovery of stale routes can be slow. As shown in Figure 4,
when the link between 1 and 2 breaks, node 1 will not be aware until when the link between 1 and 2 breaks, node 1 will not be aware until
a message comes from 2 by way of 3,4,5,6. This observation justifies a message comes from 2 by way of 3,4,5,6. This observation justifies
CBRP's use of inter-cluster uni-directional links only between 2 CBRP's use of inter-cluster uni-directional links only between 2
clusters. clusters.
1--->2--->3--->4--->5 1--->2--->3--->4--->5
^ | ^ |
| | | |
| | | |
| | | |
+-------- 6 <-------+ +-------- 6 <-------+
Fig. 4 Fig. 4
7. Future Directions 8. Constants and Suggested Values
These are the CBRP constant values that we have experiemented with in
the simulation.
Cluster based routing protocols (CBRP) is the first step towards a HELLO_INTEVAL 1.5s or 2s
more scalable solution using clustering approach. It also suggests HELLO_LOSS 1
how uni-directional links in Ad hoc networks can be used in routing CONTENTION_PERIOD 1.5s
and the reveals problems resulting from such use.
Several questions remain to be answered in CBRP, 9. Applicability Statement
1. How collisions can be avoided or handled effectively. Shall we This section summarizes the characteristics of CBRP, as
have spatial reuse of the channels among different clusters? specified in the Applicability Statement draft.
2. Should clusters have native support for QoS as in [10]?
3. Should clusters be made bigger than two hops diameter? If so,
what criteria should be used to form a bigger cluster? Or,
should we use a hierarchy of clusters? Will the resulted more
complex cluster formation and maintenance procedure offset the
advantage of having a bigger size?
To give satisfactory answers to these interesting questions will be 9.1 Network Context
our future directions in refining CBRP.
References The protocol is designed for medium to large networks with relatively
large average nodal degree (> 5). Nodal mobility should not be too
high, i.e. node cannot move quicker than the speed of cluster forma-
tion which is defined as 1/HELLO_INTERVAL.
This protocol is suited for networks where most of the traffic is
among a small set of sender-receiver pairs compared to the possibil-
ity of N*(N-1)/2 number of pairs. Also, the applications supported
should be able to tolerate the delay of route discovery time.
9.2 Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links?
(if so, how?)
Yes. It selectively makes use of those uni-directional links
that could give two-way-route to nodes that are otherwise
inaccessible using only bi-directional links.
* 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?)
Yes. routes are discovered in route discovery stage and will
be carried in the packet headers in actual routing. (Refer to
Section 6.2) However, source routing is actually not
essential to the correct working of CBRP. As source routing
poses a non-negligible overhead when the network sizes grow,
we are currently designing alternatives to replace it with
more efficient mechanisms.
* Does the protocol require the use of periodic messaging? (if
so, how?)
Yes. Periodically, each node in the network sends a HELLO mes-
sage containing its current neighbor table. The size of the
message is proportional to the degree of the node (i.e. the
number of neighbors), which is around 6 to 15 for networks of
average density.
* Does the protocol require the use of reliable or sequenced
packet delivery? (if so, how?)
No.
* 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
used for routing purpose.
* Does the protocol provide support for multiple hosts per
router? (if so, how?)
Yes. A number of hosts, each having a unique IP address,
could associate itself with a router that forwards packets and
participates in the routing protocol on the hosts' behalf.
* Does the protocol require link or neighbor status sensing (if
so, how?)
Yes. Neighbor status sensing is required.
* Does the protocol have dependence on a central entity? (if so,
how?)
No. All the functions are achieved in a distributed manner.
The cluster formation process differentiates the roles of
nodes as cluster heads and member nodes. Cluster heads are
flooded during the route discovery phase to find a route to
the destination. However the actual routing will try to
bypass cluster heads as intermediate nodes.
* Does the protocol function reactively? (if so, how?)
Yes. It defers getting the route information until such a
route is explicitly asked for by the application. Routing is
done on demand with 3 phases: route discovery, packet routing,
route removal.
* Does the protocol function proactively? (if so, how?)
No. But it proactively acquires its 2-hop topology informa-
tion through the exchange of HELLO messages.
* Does the protocol provide loop-free routing? (if so, how?)
Yes. Source routing records all nodes along the route that
could be easily checked for loop-freedom.
* Does the protocol provide for sleep period operation? (if so,
how?)
No.
* Does the protocol provide some form of security? (if so, how?)
Not by itself. It has to rely on other protocols (e.g. IMEP,
IPsec) to give security support.
* Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?)
Yes. Cluster-formation algorithms could be run on different
channels to yield different sets of clusters for each channel.
Routing could be done independently on each of the set of
clusters.
References
[1] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing", [1] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3, MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3,
1997. 1997.
[2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology", [2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology",
draft-ietf-manet-term-00.txt, work in progress. draft-ietf-manet-term-00.txt, work in progress.
[3] Corson, M.S., and Ephremides, A., "A Distributed Routing [3] Park V., Corson M.S, "A Highly Adaptive Distributed Routing
Algorithm for Mobile Wireless Networks", ACM/Baltzer Journal Algorithm for Mobile Wireless Networks," Proc. IEEE INFOCOM '97,
on Wireless Networks, January 1995. Kobe, Japan, Apr 1997.
[4] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in [4] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in
Ad-Hoc Wireless Networks", Mobile Computing, T.Imielinski and Ad-Hoc Wireless Networks", Mobile Computing, T.Imielinski and
H.Korth, editors, Kluwer, 1996. H.Korth, editors, Kluwer, 1996.
[5] Toh,C.K., "A Novel Distributed Routing Protocol To Support [5] Toh,C.K., "A Novel Distributed Routing Protocol To Support
Ad-Hoc Mobile Computing", International Phoenix Conference on Ad-Hoc Mobile Computing", International Phoenix Conference on
Computers and Communications (IPCCC'96), pg 480-486, March 1996. Computers and Communications (IPCCC'96), pg 480-486, March 1996.
[6] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1998. [6] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1998.
skipping to change at page 12, line 45 skipping to change at page 25, line 42
Proceedings of the Second USENIX Symposium on Mobile and Proceedings of the Second USENIX Symposium on Mobile and
Location-Independent Computing, 1995. Location-Independent Computing, 1995.
[9] Gerla, M., Tsai, T.C., "Multiculster, mobile, multimedia radio [9] Gerla, M., Tsai, T.C., "Multiculster, mobile, multimedia radio
network", ACM/Balzer Journal of Wireless Networks, 1995. network", ACM/Balzer Journal of Wireless Networks, 1995.
[10] Chiang, C.C., Wu, H.K., Liu, W., Gerla, M., "Routing in [10] Chiang, C.C., Wu, H.K., Liu, W., Gerla, M., "Routing in
Clustered Multihop, Mobile Wireless Networks with Fading Clustered Multihop, Mobile Wireless Networks with Fading
Channel", The Next Millennium, the IEEE SICON, 1997. Channel", The Next Millennium, the IEEE SICON, 1997.
[11] Ephremides A., Wieselthier J.E., Baker D.J., "A Design Concept
for Reliable Mobile Radio Networks with Frequency Hopping
Signaling", Proceedings of the IEEE, Vol.75, No.1, Jan 1987
Appendix A
+---------------------------> C_UNDECIDED
| +-------------------+------------------------+
| | | |
| +-----+----------+ +----+----------+ +------+--------+
| / receive HELLO / / u_timer times / / receive HELLO /
| / from non-head / / out / / from head /
| +---------+------+ +--------+------+ +----------+----+
| | | |
| +----------+----------+ (Neighbor Table +--------+--------+
| |update Neighbor Table| Empty?) |kill u_timer |
| +----------+----------+ YES/ \NO |update Neighbor |
| | +------------+ +----+----------+ |Table as C_MEMBER|
+-------------+-+schedule new| |send triggered | +--------+--------+
| |u_timer | |HELLO as C_HEAD| |
| +------------+ +---------+-----+ |
| | |
| +--------------------> C_HEAD <--------+ |
| | +----------------+----------------+ +------+
| | | | | |
| | +-------------+ +--------------+ +--------+ |
| | /receive HELLO/ / receive HELLO/ /c_timer / |
| | /from non-head/ / from C_HEAD / / expires/ |
| |+-----+-------+ +--------+-----+ +-----+--+ |
| | | | | |
| | | +-----------------+(Still in contention |
| |+---------------+ |receive HELLO | with the other head?) |
| ||update Neighbor| |from C_HEAD,set | NO/\ YES |
| ||Table | |c_timer | / (my ID smaller?) |
| |+-----+---------+ +-------+---------+ / / \ NO |
| | | | /YES/ +----+------------+ |
| +------+-------------------+---------+----+ |send triggered +-+
| | |HELLO as C_MEMBER| |
| | +-----------------+ |
| | C_MEMBER <---------------------------+
| | +-------+----------------------+ |
| | | | |
| | +--------+-----+ +------+-------+ |
| | /last head lost/ / receive HELLO/ |
| | +----------+---+ +--------+-----+ |
| +---------------+ | | |
| |send triggered +-YES-+(my ID smallest?) +--------+-------+ |
| |HELLO as C_HEAD| | | update Neighbor+--+
| +---------------+ NO| | Table |
| +-------+--------+ +--------+-------+
+----------------------|schedule u_timer|
+----------------+
This work was supported in part by National University of Singapore This work was supported in part by National University of Singapore
ARF grant RP960683. ARF grant RP960683.
Authors' Information Authors' Information
CBRP's URL:
Contains information on CBRP's latest development and simulation code
http://cram.comp.nus.edu.sg/cbrp/
Jiang Mingliang Jiang Mingliang
Mobile Computing Lab Mobile Computing Lab
School of Computing School of Computing
National University of Singapore National University of Singapore
Singapore 119260 Singapore 119260
Email: jiangmin@comp.nus.edu.sg Email: jiang@eudoramail.com
Li Jinyang Li Jinyang
Mobile Computing Lab Mobile Computing Lab
School of Computing School of Computing
National University of Singapore National University of Singapore
Singapore 119260 Singapore 119260
Email: lijinyan@comp.nus.edu.sg Email: lijy@acm.org
Tay Yong Chiang Y.C. Tay
Department of Mathematics Department of Mathematics
National University of Singapore National University of Singapore
Singapore 11920 Singapore 119260
Email: mattyc@leonis.nus.edu.sg Email: tay@acm.org
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/