Joint Optimization of Complexity and Overhead for the Routing in Hierarchical Networks

The hierarchical network structure was proposed in the early 80s and becomes popular nowadays. The routing complexity and the routing table size are the two primary performance measures in a dynamic route guidance system. Although various algorithms exist for finding the best routing policy in a hierarchical network, hardly exists any work in studying and evaluating the aforementioned measures for a hierarchical network. In this paper, a new mathematical framework to carry out the averages of the routing complexity and the routing table size is proposed to express the routing complexity and the routing table size as the functions of the hierarchical network parameters such as the number of the hierarchical levels and the subscriber density (cluster-population) for each hierarchical level.