--- 1/draft-ietf-manet-cbrp-spec-00.txt 2006-02-05 00:16:32.000000000 +0100 +++ 2/draft-ietf-manet-cbrp-spec-01.txt 2006-02-05 00:16:33.000000000 +0100 @@ -1,512 +1,1067 @@ - INTERNET-DRAFT Mingliang Jiang -draft-ietf-manet-cbrp-spec-00.txt National University of S'pore - Jinyang Li - National University of S'pore - Yong Chiang Tay - National University of S'pore - August 1998 +draft-ietf-manet-cbrp-spec-01.txt Jinyang Li + Y.C. Tay + National University of Singapore + 14 August 1999 - Cluster Based Routing Protocol(CBRP) Functional Specification + Cluster Based Routing Protocol(CBRP) 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, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." - To view the entire list of current Internet-Drafts, please check the - "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow - Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern - Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific - Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). + 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 clusters - in a distributed manner. A cluster head is elected for each cluster - to maintain cluster membership information. Inter-cluster routes are - discovered dynamically using the cluster membership information kept - at each cluster head. By clustering nodes into groups, the protocol - efficiently minimizes the flooding traffic during route discovery and - speeds up this process as well. Furthermore, the protocol takes into - consideration of the existence of uni-directional links and uses - these links for both intra-cluster and inter-cluster routing. + 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 + 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 for MANET. Firstly and most importantly, MANET has a dynamically changing topology due to the movement of mobile nodes which favors - routing protocols that dynamically discover routes over conventional - distant vector routing protocols [6], e.g. Dynamic Source Routing[4], - TORA[3], ABR[5] etc. Secondly, the fact that MANET lacks any - structure makes IP subnetting impossible. However, routing protocols - that are flat, i.e. only one level of hierarchy, might suffer from + 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. Routing protocols could make use of the - uni-directional links to improve its overall performance. + 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 minimize updating overhead during topology change. However, the - overhead for letting each and every node maintain up-to-date - information about the whole network's cluster membership and inter- - cluster routing information in order to route a packet is - considerable. In comparison, simpler and smaller clusters are found - in [9] and [10], however, the use of these clusters is mainly for the - task of channel assignment; how they can help in the routing process - is not discussed. + 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. CBRP is different from previously proposed cluster- - based routing algorithms and it uses a dynamic route discovery - strategy. + 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 election procedure is described in section 5.1 and - 5.2. A cluster is identified by its Cluster Head ID. Clusters are - either overlapping or disjoint. Each node in the network knows its + 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. + 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. A - cluster head has complete knowledge about group membership and link - state information in the cluster within a bounded time once the - topology within a cluster stabalizes. In CBRP, each node in the - cluster has a bi-directional link to the cluster head. + cluster. Each cluster should have one and only one cluster head. + + 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 - A node is called a gateway node of a cluster if it KNOWS that it has - a bi-directional or uni-directional link to a node from another - cluster. As shown in Figure 1, node 3 and 4 are gateway nodes of - cluster 1, node 6 is a gateway node of cluster 8. + Any node a cluster head may use to communicate with an adjacent + cluster is called a gateway node. - 2 5 - // \\ - // \\ - (1)===3==6====(8) - \\ // - \\ // - 4<------7 + * 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 - Fig. 1 * Neighbor Table The neighbor table is a conceptual data structure that we employ for - link status sensing and cluster formation. Each entry contains the ID - of a neighbor that it has connectivity with and the status of that - link and the role of the neighbor (a leader or a member). + 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) -3. Physical and Link Layer Assumptions + * Cluster Adjacency Table - This section lists the assumptions we made about the underlying - physical and link layers when designing CBRP. Each node in MANET is - equipped with a transceiver. In general, CBRP works best with - omnidirectional antennas. Each packet that a node sends is broadcast - into the region of its radio coverage. + The Cluster Adjacency Table keeps information about adjacent clusters + and is maintained by CBRP's Adjacent Cluster Discovery procedure. + Each entry contains: -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 - 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: +------------+-------------------------------+---------------------+ | NEIGHBOR_ID| LINK_STATUS | ROLE | +------------+-------------------------------+---------------------+ | neighbor 1 | bi/unidirectional link to me? | is 1 a cluster head?| +------------+-------------------------------+---------------------+ | neighbor 2 | bi/unidirectional link to me? | is 2 a cluster head?| +------------+-------------------------------+---------------------+ | ... +------------+-------------------------------+---------------------+ | neighbor N | bi/unidirectional link to me? | is N a cluster head?| +------------+-------------------------------+---------------------+ - Each node broadcasts its Neighbor Table periodically in a HELLO - message as shown below every HELLO_INTERVAL. + Each node periodically broadcasts its Neighbor Table in a HELLO mes- + sage, as shown below, every HELLO_INTERVAL. - +-----------+------------------------------------------------------+ - | MY_OWN_ID | MY_MEMBERSHIP_STATUS | - | | (CLUSTER_HEAD/CLUSTER_MEMBER/UNDECIDED) | - +-----------+------------------------------------------------------+ - | Neighbor Table | - +------------------------------------------------------------------+ + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + ... - The first field specifies the ID of the sender. The second field - tells whether the sender is a cluster head, cluster member or - undecided. ("undecided" means a node is still in search of its host - cluster) + 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) + 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. - 2. If B's Neighbor Table contains A, A marks the link to B as - bi-directional in the relevant entry. - 3. If B is cluster head, marks B as a cluster head in the entry. + 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 nodes' neighborhood topology stabilizes, each node will have - complete knowledge of all the nodes that it has a bi-directional link - to and all the nodes that have a uni-directional link to it within a - bounded time. However, a node would not know to whom it has a uni- - directional link. + When a node's neighborhood topology stabilizes, the Neighbor Table of + a node will have complete information of all the nodes that have a + 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. - Note that the 2nd and 3rd column of the neighbor table need not be - sent out for the purposes of link sensing, however, they are there - mainly for cluster formation and other functionality of the protocol. + 8 5 + // \\ ==== bi-directional link + // \\ + (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 - functionality, CBRP could be viewed as a combination of the three - following sub-functions which will be discussed below. + 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. -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 - algorithm in which the node with a lowest ID is elected as the - Cluster Head [9]. +6. Protocol Operation - A node uses the information obtained from the HELLO message for - Cluster Formation. A node that has the lowest ID among all its bi- - directionally linked neighbors (a node that has given up the role as - a Cluster Head is not counted, i.e. a cluster member node ). The new - Cluster Head will change the first field in its subsequently - broadcast HELLO messages from "undecided" to "cluster head" - thereafter. + The operations of CBRP are entirely distributed. The major compo- + nents are: Cluster Formation, Adjacent Cluster Discovery and Routing. - A cluster head regards all the nodes it has bi-directional links to - as its member nodes. A node regards itself as a member node for a - particular cluster if it has a bi-directional link to the - corresponding cluster head. Note that a member node may hear from - several cluster heads and therefore have several host clusters. +6.1 Cluster Formation -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 - would like to have the cluster heads change as infrequently as - possible. We use the following rules for changing cluster head, as + 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. Only when two cluster heads move next to each other (i.e. there - is a bi-directional link between them), one of them loses the - role of cluster head. + 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. - Therefore, our exact algorithm is not a strict "lowest ID" clustering - algorithm. The cluster maintenance procedure are discussed under - three subsections: + 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 + 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 - bi-directional links to the cluster head, or because of node - failures. In either case, the cluster head and node X will time out - the corresponding entries in their Neighbor Table so that the cluster - information will be updated. + A simplified state transition diagram without considering unidirec- + tional links for Cluster Formation is shown in Appendix A. - * Node Addition +6.2 Adjacent Cluster Discovery - A member node is added to a new cluster when it discovers a bi- - directional link to the respective cluster head even if the cluster - head has a higher ID, which is consistent with rule 1. The node will - know its new host cluster and the new host cluster head will know its - new member through the updated Neighbor Table. + 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. - When a node is switched on, its MY_MEMBERSHIP_STATUS field in the - HELLO message is initially UNDECIDED for a period of UNDECIDED_PD. If - it discovers that it has a bi-directional link to a cluster head, it - modifies this field as CLUSTER_MEMBER. If there is no such bi- - directional links to any cluster head, it takes the role as a cluster - head and indicates this in the subsequent HELLO messages it sends. + 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. - * 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- - directional link in-between), one of them must give up its role as - cluster Head. As a result, whenever a cluster head hears the HELLO - message from another cluster head indicating a bi-directional link in - between, it will compare its own ID with that of the other cluster - head's. The one with a smaller ID will continue to act as cluster - head. The one with a bigger ID gives up its role as cluster head and - changes from "cluster head" to "member" in its subsequent HELLO - messages. This might trigger the formation of other new clusters. + 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. -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 - discovery, packets routing and stale route removal, of which packet - routing is trivial. + +--------------+ +--------+-----------+ +--------+-----------+ + |Adj. Cluster1 |->|gateway1|link status|->|gateway2|link status| + +--------------+ +--------+-----------+ +--------+-----------+ + |Adj. Cluster2 |->|gateway1|link status|->|gateway2|link status| + +--------------+ +--------+-----------+ +--------+-----------+ + |... + +------------------------------------------------------------+ - Cluster structure is exploited to minimize the flooding traffic - during route discovery phase. Furthermore, some uni-directional links - are discovered and used which increases network connectivity. This is - discussed in the Gateway Discovery section. + 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. -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 - 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. + 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: - Cluster X is said to be uni-directionally linked to cluster Y if any - node in cluster X is uni-directionally linked to any other node in - cluster Y. Y is called X's upstream uni-directionally linked - neighboring cluster. + - 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. - By Gateway Disvoery, a cluster head for cluster X will obtain the - information about cluster X's bi-directionally and upstream uni- - directionally linked neighboring clusters. + - 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.) - For this purpose, a Cluster Adjacency table is kept at each node - which is formatted as follows: + The format of the Cluster Adjacency Extension to HELLO message is + shown below: - +------------------+-----------------------------------------------+ - |Adjacent Cluster1 | adjacent node|to/from/bi | - +------------------+-----------------------------------------------+ - |Adjacent Cluster2 | adjacent node|to/from/bi | - +------------------+-----------------------------------------------+ - |... | - +------------------------------------------------------------------+ + 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | .... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - This table is updated by the periodic HELLO message a node hears. - Note that a node may have several links to nodes in a particular - cluster and only one of them is recorded in the Cluster Adjacency - Table. The selection rule is as follows: + Length The number of clusterheads listed in the Extension. - 1. A bi-directional link takes precedence over all uni-directional - links. - 2. Of the links that have the same precedence, the one with the - lowest ID wins. + 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. - This table is periodically sent to the member node's host cluster - heads. (It could be piggybacked to the HELLO message if possible.) A - cluster head uses its members' Cluster Adjacency table to construct - its own cluster adjacency table. The construction rule is the same - as that of the member's. + 0 --- LINK_BIDIRECTIONAL + 1 --- LINK_FROM - Cluster head will flood its neighboring clusters with a message of - TTL 3 in search for the "to" link that corresponds to a "from" link - in its Cluster Adjacency Table. As a result, cluster heads will have - complete knowledge of all its bi-directionally linked neighboring - clusters even if there is no actual bi-directional links in between. - For example, in Fig 1, Cluster 1 knows that 2 can reach cluster 1 - through 5, but 1 does not know that cluster 2 can be reached by node - 3. In CBRP, cluster head 1 and 2 will discover this scenario and - disseminate the information to node 3 and 5 respectively. + 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 + 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 -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 packet to a destination D obtains a source route to D. Similar to other MANET protocols [4] [1], the way S finds a route(or multiple - routes) to D is also done by flooding, however, because of the - clustering approach the number of nodes that are disturbed are much - less in general. + 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, cluster heads are flooded in search - for a source route. To perform Route Discovery, the source node S - sends out a Route Request Packet (RREQ), with a recorded source route - listing only itself initially. Any node that forwards this packet - will append its own ID in this RREQ. Each node forwards a RREQ - packet only once and it never forwards it to a node that has already - appeared in the recorded route. In CBRP, the RREQ will always follow - a route with the following pattern to reach destination D: + 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: + + 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. + + 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 - A detailed description of how this is achieved is presented below. - Source always unicasts RREQ to its cluster head, say CH1. Each - cluster head will unicast RREQ to each of its bi-directionally linked - neighbors which have not yet appeared in the recorded route through - the corresponding gateway. This process continues until the target is - found or until another node that can supply a route to the target is - found. + The recorded route in Cluster Address list will be CH1, CH2, CH3 ... - When the target of the Request, node D, receives the RREQ, D may - choose to memorize the reversed source route to S. Node D then - copies the recorded source route into a Route Reply packet(RREP) - which it then sends back to the initiator of the Route Request (e.g., - node S) by reversing the recorded route and putting it in the IP - header of the Route Reply packet. The recorded route gives the - complete information about the SEQUENCE OF CLUSTERS source should - traverse in order to reach destination D. While forwarding the Route - Reply, intermediate cluster heads modifies the IP header of the - packets, substitute the inter-cluster incoming links to inter-cluster - outgoing links. Each intermediate cluster head also modifies the - recorded route in the Route Reply packet to optimize the recorded - route as much as possible using its knowledge of the cluster topology - and inter-cluster gateway information. An example of such - optimization is to connect two gateway nodes by an intra-cluster link - that does not go through the cluster head. + 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: - All source routes learned by a node are kept in a Route Cache, which - is used to further reduce the cost of Route Discovery. When a node - wishes to send a packet, it examines its own Route Cache and performs - Route Discovery only if no suitable source route is found in its - cache. + 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] | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -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 - such that S can no longer use the route to D because a hop along the - route no longer works. If S still wants to communicate with D, it can - invoke Route Discovery again to find a new route. + 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]. -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 during the design of CBRP. In particular, they are related to the use of uni-directional links in routing. -6.1 ARP and Uni-directional links +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 for ARP for uni-directional links. For + 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 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 reply will never reach node A directly. A---->B Fig. 3 CBRP is able to use uni-directional links. For an intra-cluster uni- directional link, the upstream node can be informed by its cluster - head of the MAC-layer address of the downstream node. For a inter- - cluster uni-directional link, as shown in Figure 1, node 3(5) will - know node 4(6)'s MAC-layer address by the process of gateway - discovery. + 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 + know node 4(or 6)'s MAC-layer address by the process of adjacent + 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 - 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 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 -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 - more scalable solution using clustering approach. It also suggests - how uni-directional links in Ad hoc networks can be used in routing - and the reveals problems resulting from such use. + HELLO_INTEVAL 1.5s or 2s + HELLO_LOSS 1 + CONTENTION_PERIOD 1.5s - Several questions remain to be answered in CBRP, +9. Applicability Statement - 1. How collisions can be avoided or handled effectively. Shall we - have spatial reuse of the channels among different clusters? - 2. Should clusters have native support for QoS as in [10]? - 3. Should clusters be made bigger than two hops diameter? If so, - what criteria should be used to form a bigger cluster? Or, - should we use a hierarchy of clusters? Will the resulted more - complex cluster formation and maintenance procedure offset the - advantage of having a bigger size? + This section summarizes the characteristics of CBRP, as + specified in the Applicability Statement draft. - To give satisfactory answers to these interesting questions will be - our future directions in refining CBRP. +9.1 Network Context -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", MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997. [2] Perkins, C.E., "Mobile Ad Hoc Networking Terminology", draft-ietf-manet-term-00.txt, work in progress. - [3] Corson, M.S., and Ephremides, A., "A Distributed Routing - Algorithm for Mobile Wireless Networks", ACM/Baltzer Journal - on Wireless Networks, January 1995. + [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. @@ -521,34 +1076,90 @@ 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 + +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 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: jiangmin@comp.nus.edu.sg + Email: jiang@eudoramail.com Li Jinyang Mobile Computing Lab School of Computing National University of Singapore Singapore 119260 - Email: lijinyan@comp.nus.edu.sg + Email: lijy@acm.org - Tay Yong Chiang + Y.C. Tay Department of Mathematics National University of Singapore - Singapore 11920 - Email: mattyc@leonis.nus.edu.sg + Singapore 119260 + Email: tay@acm.org