6.5 Quasihierarchical Routing

6.5 Quasihierarchical Routing

Quasihierarchical routing is mainly intended to provide routing efficiency in ad hoc and other networks. As shown in Figure 6.13, N nodes are arranged into m level hierarchy of clusters. Clusters at a certain level i (0 ≤ i < m) are typically assumed to be disjointed. Each node is assigned an address of the form bcd, which is the succession of the ID of each cluster starting with b, i.e., the ID of (m - 1)th cluster, and ending with the zero-th level cluster ID, which is the node ID within its first cluster, and with the ID of the parent cluster.

Figure 6.13: The nested cluster architecture.

A cluster head ^[17] generates and distributes routing information for the cluster. The cluster head summarizes the cluster condition and relays this to neighboring clusters. The mobility or downtimes of this cluster head may disrupt both routing and clustering functionality unless hot standbys are provided. In quasihierarchical routing, a node seeks to minimize the number of hops by sending the message to the boundary of that highest level cluster that encloses the destination node.

Figure 6.14 shows an example with c_j the lowest level cluster having both source and destination nodes s₀, d₀, and j = 3. Source packets are sent directly from s₀ to d₂, which is the highest level cluster that includes the destination node, then to d₁, then d₀.

Figure 6.14: Quasihierarchical routing versus strict hierarchical routing. (Source— Perkins, C.E., Ad Hoc Networks, Addison-Wesley, Reading, MA, 2001.)

In order to build the forwarding tables based on which routing commences, the cluster head broadcasts to all neighbors its routing cost, which is the average it has to all nodes within its cluster. ^[18] This cost will be used distributively by all nodes to determine the least cost from a typical node to every level i cluster, 0 ≤ i < m, lying inside the node i + 1 cluster. This cost information is updated and propagated by nodes per the following steps, which pertain to two neighboring nodes, x and y, belonging to the same j + 1 level parent cluster but a different j-th cluster level. Node x receives from another neighbor, node z, a new cost in regard to cluster c, i.e., one of the i-th cluster levels, where 0 ≤ i < m. Node x has to determine if it needs to update its cost in regard to c:

1. If c is not a parent cluster of x, then x will add the advertised cost received from node z to the cost of its link to z. If the sum is less than the cost that node x has stored for cluster c before, it will replace this cost with the new reduced cost, and update its forwarding tables accordingly. If not, the forwarding table entry in regard to cluster c remains the same and no change is broadcast from x to the neighbors.

2. If c is a parent cluster of x, x does not update its forwarding tables accordingly.

3. The new updated information at node x in Step 1 is broadcast to the neighbors of lowest level cluster of node x only if i ≥ j, and sent to node y if the forwarding point from x to cluster c is not y, or looping may take place.

In a uniform hierarchical network of N nodes and m levels where every cluster has the same number of lower level clusters, the size of the forwarding tables at each node is of the order of mN^l/m, while for the quasihierarchical clustering this becomes of the order of mC_max, where C_max is the maximum number of inner clusters within the parent (j + 1) level cluster.

Propagating the cost information according to the steps mentioned previously does not necessarily yield optimum shortest path to any node; in this regard, Kamoun and Kleinrock ^[19] and Lauer ^[20] try to treat this shortcoming of quasihierarchical clustering. In the literature, all clusters at a certain level were assumed to be nonoverlapping. Overlapping clusters may provide better amenability to roaming because a node will not lose connection as it switches from cluster to cluster (if that node happened to belong to the overlapping clusters).

Allowing cluster overlap adds to the complexity of establishing clustering and routing tables for all nodes, not just nodes belonging to more than one cluster at the same level. ^[21]

^[17]Perkins, C.E., Ad Hoc Networks, Addison-Wesley, Reading, MA, 2001.

^[18]Kleinrock, L. and Kamoun, F., Hierarchical routing for large networks: performance evaluation and optimization, Comput. Networks, 1 (1), 155–174, 1977.

^[19]Kamoun, F. and Kleinrock, L., Stochastic performance evaluation of hierarchical routing for large networks, Comput. Networks, 3 (5), 337–353, 1979.

^[20]Lauer, G.S., Hierarchical routing design for SURAN, IEEE International Communications Conference (ICC), June 1986, pp. 93–102.

^[21]Garcia-Luna-Aceves, J.J. and Shacham, N., Analysis of routing strategies for packet radio networks, IEEE Infocom Conference, March 1985, pp. 292–302.