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 aJiang, Li, Tay                                                  [Page 7]INTERNET-DRAFT        CBRP Functional Specification            July 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 itsJiang, Li, Tay                                                  [Page 8]INTERNET-DRAFT        CBRP Functional Specification            July 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 HELLOJiang, Li, Tay                                                  [Page 9]INTERNET-DRAFT        CBRP Functional Specification            July 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                                                 [Page 10]INTERNET-DRAFT        CBRP Functional Specification            July 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                                                 [Page 11]INTERNET-DRAFT        CBRP Functional Specification            July 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 theJiang, Li, Tay                                                 [Page 12]INTERNET-DRAFT        CBRP Functional Specification            July 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. 26.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                                                 [Page 13]INTERNET-DRAFT        CBRP Functional Specification            July 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)