Closed-Form Formulas for Cluster Sizing for Two-Level Hierarchical Networks with Source Routing
研究了两级分层网络中如何选择集群数量以最小化路径计算总复杂度，给出了闭式解估计和复杂度下界，适用于网络设计者优化路由性能。
Abstract In a two-level hierarchical network, nodes are grouped into clusters. A node in one cluster sees the entire topology of that cluster, but only a summarized view of other clusters. With source routing, the source node of a connection does an initial route computation based on its view of the network, and additional route computations are performed as the connection makes its way towards the destination. We study the problem of choosing the number of clusters to minimize the total complexity of all the path computations required to compute a path from a source node to a destination node. We show that, under mild conditions, for all sufficiently large networks two-level hierarchical routing is superior to flat network routing. Utilizing the duality theory of geometric programming, we provide a closed-form solution estimate for the number of clusters to minimize the total routing complexity. We also provide a closed-form expression for a lower bound on the minimal total complexity. We illustrate the modelling assumptions for a variety of networks. Computational results for a range of network sizes and parameters show that our solution estimate yields near-optimal results.