Designing Low Cost Networks with Short Routes and Low Congestion
Văn Đức Nguyễn, Charles U. Martel · 2006
Abstract — We design network topologies and routing strategies which optimize several measures simultaneously: low cost, small routing diameter, bounded degree and low congestion. This set of design issues is broader than traditional network design and hence, our work is useful and relevant to a set of traditional and emerging design problems. Surprisingly, a simple idea from the research on small-world models, inspires a fruitful approach and useful techniques here. Starting with a simple model we consider adding long links to an n×n grid graph. Ideally, for a given budget to buy additional long links, we consider mechanisms for choosing links such that the routing diameter is small enough (poly-log of n) while the congestion ratio (between the most used link and the average one) is minimized, assuming uniform traffic between any two of the n 2 nodes. We show that by adding O(1) long links to each node we achieve an almost logarithmic routing diameter and maintain a near optimal trade-off between congestion ratio and average weight (of long links): Weight×CongestionRatio = O(n). Our results are comparable to the best similar network structures when the trade-off space we consider is reduced to those in the compared designs (with fewer trade-off factors). We also consider extensions of our results to more general settings. We propose two construction schemes: 1) a static (fixed link) design and 2) a dynamic (random link) design. While the former provides our best trade-off results, the later is more scalable, better suited for dynamic and fault-tolerance issues, and can be useful for wireless ad-hoc networks. I.