INTERNET-DRAFT Mingliang Jiang
draft-ietf-manet-cbrp-spec-00.txt National University of S'pore
Jinyang Li
National University of S'pore
Yong Chiang Tay
National University of S'pore
August 1998
Cluster Based Routing Protocol(CBRP) Functional Specification
Status of this Memo
This document is an Internet-Draft. 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."
To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific
Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).
Abstract
Cluster Based Routing Protocol (CBRP) is a routing protocol designed
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
in a distributed manner. A cluster head is elected for each cluster
to maintain cluster membership information. Inter-cluster routes are
discovered dynamically using the cluster membership information kept
at each cluster head. By clustering nodes into groups, the protocol
efficiently minimizes the flooding traffic during route discovery and
speeds up this process as well. Furthermore, the protocol takes into
consideration of the existence of uni-directional links and uses
these links for both intra-cluster and inter-cluster routing.
Jiang, Li, Tay [Page 1]
INTERNET-DRAFT CBRP Functional Specification August 1998
1 Introduction
There are several major difficulties for designing a routing protocol
for MANET. Firstly and most importantly, MANET has a dynamically
changing topology due to the movement of mobile nodes which favors
routing protocols that dynamically discover routes over conventional
distant vector routing protocols [6], e.g. Dynamic Source Routing[4],
TORA[3], ABR[5] etc. Secondly, the fact that MANET lacks any
structure makes IP subnetting impossible. However, routing protocols
that are flat, i.e. only one level of hierarchy, might suffer from
excessive overhead when scaled up. Thirdly, links in mobile networks
could be asymmetric at times. Routing protocols could make use of the
uni-directional links to improve its overall performance.
CBRP has the following features:
* fully distributed operation.
* less flooding traffic during the dynamic route discovery process.
* explicit exploitation of uni-directional links that would otherwise
be unused.
The idea of using clusters for routing in Ad hoc networks has
appeared in [7],[8]. In these protocols clusters are introduced to
minimize updating overhead during topology change. However, the
overhead for letting each and every node maintain up-to-date
information about the whole network's cluster membership and inter-
cluster routing information in order to route a packet is
considerable. 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
unlike [9], CBRP mainly concentrates on the use of clusters in the
routing process. CBRP is different from previously proposed cluster-
based routing algorithms and it uses a dynamic route discovery
strategy.
2. CBRP terminology
This section defines terms used in CBRP that do not appear in [2]:
* Node ID
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
Jiang, Li, Tay [Page 2]
INTERNET-DRAFT CBRP Functional Specification August 1998
address as its ID for purposes of routing and interoperability with
fixed networks.
* Cluster
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
5.2. 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
belongs to.
* Host Cluster
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
cluster for this node.
* Cluster Head
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 head has complete knowledge about group membership and link
state information in the cluster within a bounded time once the
topology within a cluster stabalizes. In CBRP, each node in the
cluster has a bi-directional link to the cluster head.
* Cluster Member
All nodes within a cluster EXCEPT the cluster head are called members
of this cluster.
* Gateway Node
A node is called a gateway node of a cluster if it KNOWS that it has
a bi-directional or uni-directional link to a node from another
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
// \ // \ (1)===3==6====(8)
\\ //
\\ //
4<------7
Fig. 1
Jiang, Li, Tay [Page 3]
INTERNET-DRAFT CBRP Functional Specification August 1998
* Neighbor Table
The neighbor table is a conceptual data structure that we employ for
link status sensing and cluster formation. Each entry contains the ID
of a neighbor that it has connectivity with and the status of that
link and the role of the neighbor (a leader or a member).
3. Physical and Link Layer Assumptions
This section lists the assumptions we made about the underlying
physical and link layers when designing CBRP. Each node in MANET is
equipped with a transceiver. In general, CBRP works best with
omnidirectional antennas. Each packet that a node sends is broadcast
into the region of its radio coverage.
4. Link/Connection Status Sensing Mechanism
In CBRP, each node knows its bi-directional links to its neighbors as
well as unidirectional links from its neighbors to itself. For this
purpose, each node maintains a Neighbor Table as follows:
+------------+-------------------------------+---------------------+
| NEIGHBOR_ID| LINK_STATUS | ROLE |
+------------+-------------------------------+---------------------+
| 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 N | bi/unidirectional link to me? | is N a cluster head?|
+------------+-------------------------------+---------------------+
Each node broadcasts its Neighbor Table periodically in a HELLO
message as shown below every HELLO_INTERVAL.
+-----------+------------------------------------------------------+
| MY_OWN_ID | MY_MEMBERSHIP_STATUS |
| | (CLUSTER_HEAD/CLUSTER_MEMBER/UNDECIDED) |
+-----------+------------------------------------------------------+
| Neighbor Table |
+------------------------------------------------------------------+
The first field specifies the ID of the sender. The second field
tells whether the sender is a cluster head, cluster member or
undecided. ("undecided" means a node is still in search of its host
Jiang, Li, Tay [Page 4]
INTERNET-DRAFT CBRP Functional Specification August 1998
cluster)
Upon receiving a HELLO message from its neighbor B, node A modifies
its own Neighbor Table as follows:
1. It checks if B is already in the Neighbor Table, if not, it
adds one entry for B.
2. If B's Neighbor Table contains A, A marks the link to B as
bi-directional in the relevant entry.
3. If B is cluster head, marks B as a cluster head in the entry.
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
received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing
HELLO_LOSS consecutive HELLO messages to be lost from that node.
When a nodes' neighborhood topology stabilizes, each node will have
complete knowledge of all the nodes that it has a bi-directional link
to and all the nodes that have a uni-directional link to it within a
bounded time. However, a node would not know to whom it has a uni-
directional link.
Note that the 2nd and 3rd column of the neighbor table need not be
sent out for the purposes of link sensing, however, they are there
mainly for cluster formation and other functionality of the protocol.
5. Protocol Operation
The operations of CBRP are entirely distributed. According to the
functionality, CBRP could be viewed as a combination of the three
following sub-functions which will be discussed below.
5.1 Cluster Formation
The Cluster Formation algorithm is a simple "lowest ID" clustering
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
Cluster Formation. A node that has the lowest ID among all its bi-
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.
Jiang, Li, Tay [Page 5]
INTERNET-DRAFT CBRP Functional Specification August 1998
A cluster head regards all the nodes 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
corresponding cluster head. Note that a member node may hear from
several cluster heads and therefore have several host clusters.
5.2 Cluster Maintenance
As clusters are identified by their respective cluster heads, we
would like to have the cluster heads change as infrequently as
possible. We use the following rules for changing cluster head, as
described in [10].
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
bi-directional link to cluster head Y, X does not become
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
is a bi-directional link between them), one of them loses the
role of cluster head.
Therefore, our exact algorithm is not a strict "lowest ID" clustering
algorithm. The cluster maintenance procedure are discussed under
three subsections:
* Node Removal
A node X is removed from a host cluster either because it loses the
bi-directional links to the cluster head, or because of node
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
A member node is added to a new cluster when it discovers a bi-
directional link to the respective cluster head even if the cluster
head has a higher ID, which is consistent with rule 1. The node will
know its new host cluster and the new host cluster head will know its
new member through the updated Neighbor Table.
When a node is switched on, its MY_MEMBERSHIP_STATUS field in the
HELLO message is initially UNDECIDED for a period of UNDECIDED_PD. If
it discovers that it has a bi-directional link to a cluster head, it
modifies this field as CLUSTER_MEMBER. If there is no such bi-
directional links to any cluster head, it takes the role as a cluster
head and indicates this in the subsequent HELLO messages it sends.
Jiang, Li, Tay [Page 6]
INTERNET-DRAFT CBRP Functional Specification August 1998
* Cluster Head Contention
When two Cluster Heads move next to each other (till they have a bi-
directional link in-between), one of them must give up its role as
cluster Head. As a result, whenever a cluster head hears the HELLO
message from another cluster head indicating a bi-directional link in
between, it will compare 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 "cluster head" to "member" in its subsequent HELLO
messages. This might trigger the formation of other new clusters.
5.3 Routing Considerations
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
discovery, packets routing and stale route removal, of which packet
routing is trivial.
Cluster structure is exploited to minimize the flooding traffic
during route discovery phase. Furthermore, some uni-directional links
are discovered and used which increases network connectivity. This is
discussed in the Gateway Discovery section.
5.3.1 Gateway Discovery
Cluster X and cluster Y are said to be bi-directionally linked, if
any node in cluster X is bi-directionally linked to another node in
cluster Y, or if there is a pair of opposite uni-directional links
between any 2 nodes in cluster X and cluster Y respectively.
Cluster X is said to be uni-directionally linked to cluster Y if any
node in cluster X is uni-directionally linked to any other node in
cluster Y. Y is called X's upstream uni-directionally linked
neighboring cluster.
By Gateway Disvoery, a cluster head for cluster X will obtain the
information about cluster X's bi-directionally and upstream uni-
directionally linked neighboring clusters.
For this purpose, a Cluster Adjacency table is kept at each node
which is formatted as follows:
Jiang, Li, Tay [Page 7]
INTERNET-DRAFT CBRP Functional Specification August 1998
+------------------+-----------------------------------------------+
|Adjacent Cluster1 | adjacent node|to/from/bi |
+------------------+-----------------------------------------------+
|Adjacent Cluster2 | adjacent node|to/from/bi |
+------------------+-----------------------------------------------+
|... |
+------------------------------------------------------------------+
This table is updated by the periodic HELLO message a node hears.
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
links.
2. Of the links that have the same precedence, the one with the
lowest ID wins.
This table is periodically sent to the member node's host cluster
heads. (It could be piggybacked to the HELLO message if possible.) A
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
TTL 3 in search for the "to" link that corresponds to a "from" link
in its Cluster Adjacency Table. As a result, cluster heads will have
complete knowledge of all its bi-directionally linked neighboring
clusters even if there is no actual bi-directional links in between.
For example, in Fig 1, Cluster 1 knows that 2 can reach cluster 1
through 5, but 1 does not know that cluster 2 can be reached by node
3. In CBRP, cluster head 1 and 2 will discover this scenario and
disseminate the information to node 3 and 5 respectively.
3-->4
// \\ 1 and 2 are heads of their respective
// \\ clusters, 3,4,5,6 are members.
(1) (2)
\\ //
\\ //
6<--5
Fig. 2
Jiang, Li, Tay [Page 8]
INTERNET-DRAFT CBRP Functional Specification August 1998
5.3.2 Route Discovery
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
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
clustering approach the number of nodes that are disturbed are much
less in general.
Essentially in Route Discovery, cluster heads are flooded in search
for a source route. To perform Route Discovery, the source node S
sends out a Route Request Packet (RREQ), with a recorded source route
listing only itself initially. Any node that forwards this packet
will append its own ID in this RREQ. Each node forwards a 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 following pattern to reach destination D:
S,CH1,G1,CH2,G2,G3,CH3 ..... D
A detailed description of how this is achieved is presented below.
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
choose to memorize the reversed source route to S. Node D then
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
is used to further reduce the cost of Route Discovery. When a node
Jiang, Li, Tay [Page 9]
INTERNET-DRAFT CBRP Functional Specification August 1998
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
cache.
5.3.3 Route Removal
A source route is removed from S if the network topology has changed
such that S can no longer use the route to D because a hop along the
route no longer works. If S still wants to communicate with D, it can
invoke Route Discovery again to find a new route.
6. Discussions and Implementation Considerations
This section discusses some of the problems that we have encountered
during the design of CBRP. In particular, they are related to the use
of uni-directional links in routing.
6.1 ARP and Uni-directional links
In a MANET context, links between 2 nodes can be bi-directional and
uni-directional. However, when the link layer does MAC-layer
address based packet filtering, (which most current technologies do),
special care has to be taken for ARP for uni-directional links. For
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
protocol to resolve node B's MAC layer address, because node B's ARP
reply will never reach node A directly.
A---->B
Fig. 3
CBRP is able to use uni-directional links. For an intra-cluster uni-
directional link, the upstream node can be informed by its cluster
head of the MAC-layer address of the downstream node. For a inter-
cluster uni-directional link, as shown in Figure 1, node 3(5) will
know node 4(6)'s MAC-layer address by the process of gateway
discovery.
6.2 Rate of Stale Route Discovery and Uni-directional Links
In general (not pertaining to CBRP), when uni-directional links are
used, discovery of stale routes can be slow. As shown in Figure 3,
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
CBRP's use of inter-cluster uni-directional links only between 2
Jiang, Li, Tay [Page 10]
INTERNET-DRAFT CBRP Functional Specification August 1998
clusters.
1--->2--->3--->4--->5
^ |
| |
| |
| |
+-------- 6 <-------+
Fig. 4
7. Future Directions
Cluster based routing protocols (CBRP) is the first step towards a
more scalable solution using clustering approach. It also suggests
how uni-directional links in Ad hoc networks can be used in routing
and the reveals problems resulting from such use.
Several questions remain to be answered in CBRP,
1. How collisions can be avoided or handled effectively. Shall we
have spatial reuse of the channels among different clusters?
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
our future directions in refining CBRP.
Jiang, Li, Tay [Page 11]
NTERNET-DRAFT CBRP Functional Specification August 1998
References
[1] Perkins, C.E., "Ad-Hoc On-Demand Distance Vector Routing",
MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3,
1997.
[2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology",
draft-ietf-manet-term-00.txt, work in progress.
[3] Corson, M.S., and Ephremides, A., "A Distributed Routing
Algorithm for Mobile Wireless Networks", ACM/Baltzer Journal
on Wireless Networks, January 1995.
[4] Johnson, D.B., and Maltz, D.A., "Dynamic Source Routing in
Ad-Hoc Wireless Networks", Mobile Computing, T.Imielinski and
H.Korth, editors, Kluwer, 1996.
[5] Toh,C.K., "A Novel Distributed Routing Protocol To Support
Ad-Hoc Mobile Computing", International Phoenix Conference on
Computers and Communications (IPCCC'96), pg 480-486, March 1996.
[6] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1998.
[7] Das, B., Raghupathy, S, Vaduvur, B, "Routing in Ad Hoc Networks
Using a Spine", Proceedings of 6th International Conference on
Computer Communications and Networks, Las Vegas, USA, September,
1997.
[8] Krishna, P., Vaidya, N.H., Chatterjee, M., Pradhan, D.K., " A
Cluster-based Approach for Routing in Dynamic Networks",
Proceedings of the Second USENIX Symposium on Mobile and
Location-Independent Computing, 1995.
[9] Gerla, M., Tsai, T.C., "Multiculster, mobile, multimedia radio
network", ACM/Balzer Journal of Wireless Networks, 1995.
[10] Chiang, C.C., Wu, H.K., Liu, W., Gerla, M., "Routing in
Clustered Multihop, Mobile Wireless Networks with Fading
Channel", The Next Millennium, the IEEE SICON, 1997.
This work was supported in part by National University of Singapore
ARF grant RP960683.
Jiang, Li, Tay [Page 12]
INTERNET-DRAFT CBRP Functional Specification August 1998
Authors' Information
Jiang Mingliang
Mobile Computing Lab
School of Computing
National University of Singapore
Singapore 119260
Email: jiangmin@comp.nus.edu.sg
Li Jinyang
Mobile Computing Lab
School of Computing
National University of Singapore
Singapore 119260
Email: lijinyan@comp.nus.edu.sg
Tay Yong Chiang
Department of Mathematics
National University of Singapore
Singapore 11920
Email: mattyc@leonis.nus.edu.sg
Jiang, Li, Tay [Page 13]
