Designing Low Cost Networks with Short Routes and Low Congestion
Designing Low Cost Networks with Short Routes and Low Congestion
复制标题
设计具有短路由和低拥塞的低成本网络
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
C. Martel
中科院分区：
文献类型：
--
作者：
V. Nguyen;C. Martel
我们设计的网络拓扑和路由策略同时优化了多项措施：低成本、小路由直径、有界度和低拥塞。这组设计问题比传统的网络设计更广泛，因此，我们的工作是有用的，相关的一组传统和新兴的设计问题。令人惊讶的是，小世界模型研究中的一个简单想法，启发了这里富有成效的方法和有用的技术。从一个简单的模型开始，我们考虑将长链接添加到n×n网格图。理想情况下，对于给定的预算购买额外的长链路，我们考虑选择链路的机制，使得路由直径足够小（n的poly-log），而拥塞率（最常用的链路和平均链路之间）最小化，假设n个节点中的任何两个节点之间的流量均匀。我们表明，通过向每个节点添加O（1）长链路，我们实现了几乎对数的路由直径，并在拥塞率和平均权重（长链路）之间保持了接近最优的权衡：权重×拥塞率= O（n）。当我们考虑的权衡空间减少到比较设计中的那些（具有更少的权衡因素）时，我们的结果与最好的相似网络结构相当。我们还考虑我们的结果扩展到更一般的设置。我们提出了两种施工方案：1）静态（固定链接）设计和2）动态（随机链接）设计。虽然前者提供了我们最好的权衡结果，后者更具可扩展性，更适合于动态和容错问题，并可用于无线ad-hoc网络。
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 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.