INTERNET-DRAFT Mingliang Jiang draft-ietf-manet-cbrp-spec-01.txt Jinyang Li Y.C. Tay National University of Singapore 14 August 1999 Cluster Based Routing Protocol(CBRP) Status of this Memo 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, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at: http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at: http://www.ietf.org/shadow.html. 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 2-hop- diameter 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 the existence of uni-directional links and uses these links for both intra-cluster and Jiang, Li, Tay Expires 14 Feb 2000 [Page 1]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 inter-cluster routing. 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 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 (e.g. Dynamic Source Routing[4], TORA[3], ABR[5] etc.) over conventional distance vector routing protocols [6]. Secondly, the fact that MANET lacks any structure makes IP subnetting inefficient. However, routing protocols that are flat, i.e. have no hierarchy, might suffer from excessive overhead when scaled up. Thirdly, links in mobile networks could be asymmetric at times. If a routing protocol relies only on 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: * fully distributed operation. * less flooding traffic during the dynamic route discovery process. * explicit exploitation of uni-directional links that would otherwise 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 appeared in [7],[8]. In these protocols clusters are introduced to Jiang, Li, Tay Expires 14 Feb 2000 [Page 2]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 minimize updating overhead during topology change. However, the overhead for maintaining up-to-date information about the whole network's cluster membership and inter-cluster routing information at each and every node in order to route a packet is considerable. As network topology changes from time to time due to node movement, the effort to maintain such up-to- date information is expensive and rarely justified as such global cluster membership information is 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 unlike [9], CBRP mainly concentrates on the use of clusters in the routing process. 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 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 cluster formation procedure is described in section 6.1. 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. A node could have several host clusters. * 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. Jiang, Li, Tay Expires 14 Feb 2000 [Page 3]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 The cluster head has a bi-directional link to every node in the cluster. 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 All nodes within a cluster EXCEPT the cluster head are called members of this cluster. * Gateway Node Any node a cluster head may use to communicate with an adjacent cluster is called a gateway node. * HELLO message All nodes broadcast HELLO messages periodically every HELLO_INTERVAL 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. 3. Conceptual Data Structures * 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 the neighbor that it has connectivity with and - the role of the neighbor (a cluster head or a member). - the status of that link (bi-directional or uni-directional) * Cluster Adjacency Table The Cluster Adjacency Table keeps information about adjacent clusters Jiang, Li, Tay Expires 14 Feb 2000 [Page 4]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 and is maintained by CBRP's Adjacent Cluster Discovery procedure. Each entry contains: - 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 well as uni-directional links from its neighbors to itself. For this purpose, each node maintains a Neighbor Table as follows: Jiang, Li, Tay Expires 14 Feb 2000 [Page 5]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 +------------+-------------------------------+---------------------+ | 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 periodically broadcasts its Neighbor Table in a HELLO mes- sage, as shown below, every HELLO_INTERVAL. 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 +-+-+-+-+-+-+-+-+ | Length | S | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Length The number of neighbours listed. S(Status) The current status of the sender. 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) Jiang, Li, Tay Expires 14 Feb 2000 [Page 6]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 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 if it has heard from B in the previous HELLO_INTERVAL before (i.e. A enters B in its Neighbor Table only when A has heard from B's HELLO messages twice in 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 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 node's neighborhood topology stabilizes, the Neighbor Table of a node will have complete information of all the nodes that have a Jiang, Li, Tay Expires 14 Feb 2000 [Page 7]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 bi-directional or uni-directional link to it within a bounded time. However, a node would not know to whom it has a uni-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. 8 5 // \\ ==== bi-directional link // \\ (1)===3==6====(2) (1), (2) cluster heads \\ // \\ // ---> uni-directional link 4------>7 Fig. 1 Note that the 2nd and 3rd column of the neighbor table and the status field of the hello message need not be used for the purpose of link sensing; they are there mainly for cluster formation and adjacent cluster discovery, which will be discussed in Section 6. 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. 6. Protocol Operation The operations of CBRP are entirely distributed. The major compo- nents are: Cluster Formation, Adjacent Cluster Discovery and Routing. 6.1 Cluster Formation 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 8]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 would like to have the cluster heads change as infrequently as possi- ble. 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. When two cluster heads move next to each other (i.e. there is a bi-directional link between them) over an extended period of time (for CONTENTION_PERIOD seconds), then only will one of them lose its role of cluster head. As a result, whenever a cluster head hears HELLO messages from another cluster head indicating a bi-directional link, it sets 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 9]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 messages. This might trigger reorganization of other clusters. 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 simplified state transition diagram without considering unidirec- tional links for Cluster Formation is shown in Appendix A. 6.2 Adjacent Cluster 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. For example in Figure 2, cluster 1 and cluster 2 are bi-directionally linked by the pair of links 3->4 and 5->6. Cluster X is said to be uni-directionally linked to cluster Y if they are not bi-directionally linked and if there exists some node in cluster X that is uni-directionally linked to some node in cluster Y. X is called Y's upstream uni-directionally linked adjacent cluster, and vice versa. For example, in Figure 1, cluster 1 is cluster 2's upstream uni-directionally linked adjacent cluster. 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. Note that for member nodes, neighboring cluster heads are always two hops away and can be discovered by checking received HELLO messages. For a cluster head, its neighboring cluster heads could be 2 or 3 hops away (see Figure 2). Using the HELLO messages alone, a cluster head is able to discover the cluster heads 2 hops away. However, it has to rely on its member nodes' Cluster Adjacency Table to discover those neighboring cluster heads that are 3 hops away. The format of CAT at each node is as follows: Jiang, Li, Tay Expires 14 Feb 2000 [Page 10]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 +--------------+ +--------+-----------+ +--------+-----------+ |Adj. Cluster1 |->|gateway1|link status|->|gateway2|link status| +--------------+ +--------+-----------+ +--------+-----------+ |Adj. Cluster2 |->|gateway1|link status|->|gateway2|link status| +--------------+ +--------+-----------+ +--------+-----------+ |... +------------------------------------------------------------+ Gateway field contains the ID of the gateway node through which the neighboring cluster head could be reached. Gateway node is the mem- ber node of the adjacent cluster and hence always has a bi-direc- 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. 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. In order for cluster heads to gain information on their adjacent clusters that are 3 hops away, each member node broadcasts its summa- rized CAT as a Cluster Adjacency Extension to the HELLO message. (Only member node will send out this information, this is not the case with cluster heads.) The rules for summarizing is as follows: - If there is at least one gateway with whom the node has a bi-directional link, it advertise the neighboring cluster as bi-directionally reachable. - If there are only uni-directional links (LINK_FROM), the neighboring cluster will be advertised as LINK_FROM. (Note that, by HELLO messages alone, a node is not able to detect any LINK_TO link to the gateway.) The format of the Cluster Adjacency Extension to HELLO message is shown below: Jiang, Li, Tay Expires 14 Feb 2000 [Page 11]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 +-+-+-+-+-+-+-+-+ | 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | .... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Length The number of clusterheads listed in the Extension. L Link Status of the corresponding Adjacent Cluster head. If there is at least one gateway node having bi-directional link to the Adjacent Cluster head, the Link status is specified as LINK_BIDIRECTIONAL. Otherwise, it is LINK_FROM. 0 --- LINK_BIDIRECTIONAL 1 --- LINK_FROM In addition to using HELLO messages to construct its CAT consisting of 2-hop away neighboring cluster heads, a cluster head could check its members' Cluster Adjacency Extension to find out its 3-hop away neighboring cluster heads in its CAT. In particular, suppose cluster head A receives B's HELLO message. After updating its CAT with the Neighbor Table entries in HELLO, A proceeds to check B's Cluster Adjacency Extension in HELLO, if it finds adjacent cluster head C that is not already reachable within 2 hops, it creates a new entry 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 12]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 // \\ 1 and 2 are heads of their respective // \\ clusters, 3,4,5,6 are members. (1) (2) \\ // \\ // 6<--5 Fig. 2 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 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 clus- tering approach the number of times nodes are disturbed are much less in general. Essentially, in Route Discovery, only cluster heads are flooded with Route Request Packets (RREQ) in search for a source route. The for- mat of such a packet is shown below: Jiang, Li, Tay Expires 14 Feb 2000 [Page 13]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 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. Jiang, Li, Tay Expires 14 Feb 2000 [Page 14]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 The recorded route in Cluster Address list will be CH1, CH2, CH3 ... When the target of the Request, node D, receives the RREQ, D sends out an RREP packet to S as a reply, with the following format: Jiang, Li, Tay Expires 14 Feb 2000 [Page 15]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 1| Num1 |G| Num2 | Identification | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cluster Address[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cluster Address[Num1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Calculated Route[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Calculated Route[Num2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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. D copies the list of Cluster Addresses into the RREP packet. (D may choose to memorize the reversed list of Cluster Addresses to S so that if D wants to find out a route to S, it may directly probe this route of cluster heads). D also copies the identification field in RREQ to RREP and puts its own address in Calculated Route[1]. 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. Jiang, Li, Tay Expires 14 Feb 2000 [Page 16]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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: Jiang, Li, Tay Expires 14 Feb 2000 [Page 17]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 18]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 19]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 during the design of CBRP. In particular, they are related to the use of uni-directional links in routing. 7.2.1 ARP problem 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 with ARP for uni-directional links. For example, when there is a uni-directional link from node A to node B 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 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 an inter- cluster uni-directional link, as shown in Figure 2, node 3(or 5) will Jiang, Li, Tay Expires 14 Feb 2000 [Page 20]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 know node 4(or 6)'s MAC-layer address by the process of adjacent cluster discovery. 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 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 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 clusters. 1--->2--->3--->4--->5 ^ | | | | | | | +-------- 6 <-------+ Fig. 4 8. Constants and Suggested Values Jiang, Li, Tay Expires 14 Feb 2000 [Page 21]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 These are the CBRP constant values that we have experiemented with in the simulation. HELLO_INTEVAL 1.5s or 2s HELLO_LOSS 1 CONTENTION_PERIOD 1.5s 9. Applicability Statement This section summarizes the characteristics of CBRP, as specified in the Applicability Statement draft. 9.1 Network Context 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 22]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 23]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 24]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 [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] Park V., Corson M.S, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," Proc. IEEE INFOCOM '97, Kobe, Japan, Apr 1997. [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. [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 Jiang, Li, Tay Expires 14 Feb 2000 [Page 25]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 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| +----------------+ Jiang, Li, Tay Expires 14 Feb 2000 [Page 26]
INTERNET-DRAFT CBRP Functional Specification 14 August 1999 This work was supported in part by National University of Singapore ARF grant RP960683. Authors' Information CBRP's URL: Contains information on CBRP's latest development and simulation code http://cram.comp.nus.edu.sg/cbrp/ Jiang Mingliang Mobile Computing Lab School of Computing National University of Singapore Singapore 119260 Email: jiang@eudoramail.com Li Jinyang Mobile Computing Lab School of Computing National University of Singapore Singapore 119260 Email: lijy@acm.org Y.C. Tay Department of Mathematics National University of Singapore Singapore 119260 Email: tay@acm.org Jiang, Li, Tay Expires 14 Feb 2000 [Page 27]
