An Adaptive Hierarchical Routing Protocol

This paper proposes an adaptive hierarchical routing protocol based on the extension of the new Arpanet scheme and presents its performance by simulation. Our objective is to design efficient and adaptive routing protocols for large and dynamic computer networks. The proposed protocol can adapt to rapidly changing environments and works for arbitrarily large networks. We have simulated a number of existing schemes (both hierarchical and nonhierarchical) and the proposed scheme under many different environments and clustering structures. From our simulations, the proposed protocol emerges superior to the other protocols tested in many different network traffics and topological configurations. We have also observed many interesting results. For example, it is essential that intercluster links be reliable, because the failures of these links can significantly degrade the routing performance, even though the proposed protocol does not degrade as badly as the existing scheme. Furthermore, hierarchical routing protocols usually prefer small (but not too small) clusters. But for a given network, small clusters mean that there will be many intercluster links and all of them must be reliable. The designer of a hierarchical network will need to balance these two costs. The tradeoff between two conflicting performance criteria, response speed and communication overhead, is also shown.