Optimal Oblivious Routing in Hole-Free Networks
Optimal Oblivious Routing in Hole-Free Networks
复制标题
无孔网络中的最优不经意路由
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Magdon
中科院分区：
文献类型：
--
作者：
C. Busch;M. Magdon
我们研究了忽略的路由算法，其中数据包路径彼此独立构建。遗忘算法是固有的分布，可以设计为有效平衡网络利用率。我们为无孔网络类提供了一种遗忘的路由算法，其中节点在拓扑上嵌入了平面的简单区域。这些网络经常出现在无线和传感器网络拓扑中。该算法实现了最佳的拥塞和伸展。所得路径的拉伸是恒定的。拥塞是O（c * logn），其中c *是最佳的非合理拥塞，n是节点的数量。这种拥堵结合是渐近最差的，对于遗忘的路由算法最佳。
We study oblivious routing algorithms in which the packet paths are constructed independently of each other. Oblivious algorithms are inherently distributed and they can be designed to efficiently balance the network utilization. We give an oblivious routing algorithm for the class of hole-free networks, in which the nodes are topologically embedded in simple areas of the plane. Such networks appear frequently in wireless and sensor network topologies. The algorithm achieves optimal congestion and stretch. The stretch of the resulting paths is constant. The congestion is O(C * logn), where C * is the optimal non-oblivious congestion and n is the number of nodes. This congestion bound is asymptotically worst-case optimal for oblivious routing algorithms.