Designing Networks for Low Weight, Small
Routing Diameter and Low Congestion
Van Nguyen and
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 n2 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 × Congestion Ratio = 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.