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/