Hop-constrained oblivious routing
Hop-constrained oblivious routing
复制标题
跳数约束的不经意路由
DOI：
10.1145/3406325.3451098
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zuzic, Goran
中科院分区：
文献类型：
--
作者：
Ghaffari, Mohsen;Haeupler, Bernhard;Zuzic, Goran
我们证明了一个在(拥塞+扩张)方面是多(LogN)竞争的不经意路由方案的存在性，从而解决了不经意路由中的一个众所周知的问题.具体地说，考虑一个无向网络和一组分组，每个分组都有它自己的源和目的.目标是为每个分组选择一条从其源到其目的地的路径，以便最小化(拥塞+扩张)，定义如下：扩张是最大路径跳长，拥塞是包括任何单边的路径的最大数目。该路由方案不经意地和随机地为每个分组选择路径，而与其他分组(是否存在)无关。尽管这种忽略，所选择的路径具有(拥塞+扩张)在最佳可能值的(Logn)因子内。更准确地说，对于任何整数跳边界，该不经意的路由方案选择在拥塞方面与通过最短跳数的长度的路径可实现的最佳可能连接相比在拥塞方面具有竞争性的最短聚(LogN)和等聚(LogN)的长度的路径。这些路径可以在多项式时间内采样，这一结果可以看作是R‘acke[FOCS 2002，STEC 2008]著名的不经意路由结果的类比，该结果在拥塞方面是竞争的，而在扩张方面是不竞争的。
We prove the existence of an oblivious routing scheme that ispoly(logn)-competitive in terms of (congestion+dilation), thus resolving a well-known question in oblivious routing.Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion+dilation), defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion+dilation) within apoly(logn) factor of the best possible value. More precisely, for any integer hop-boundh, this oblivious routing scheme selects paths of length at mosth·poly(logn) and ispoly(logn)-competitive in terms ofcongestionin comparison to the best possiblecongestionachievable via paths of length at mosthhops. These paths can be sampled in polynomial time.This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which areO(logn)-competitive in terms ofcongestion, but are not competitive in terms ofdilation.
登录
查看更多内容
无孔网络中的最优不经意路由
DOI：
--
发表时间：
2010
期刊：
Quality of Service in Heterogeneous Wired/Wireless Networks
影响因子：
--
作者：
C. Busch;M. Magdon
通讯作者：
M. Magdon
DOI：
10.1145/828.1892
发表时间：
1984
期刊：
J. ACM
影响因子：
--
作者：
E. Upfal
通讯作者：
E. Upfal
一种构建不经意路由方案的实用算法
DOI：
--
发表时间：
2003
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Marcin Bienkowski;M. Korzeniowski;Harald Räcke
通讯作者：
Harald Räcke
分布式计算中的八个开放问题
DOI：
--
发表时间：
2006
期刊：
Bull. EATCS
影响因子：
--
作者：
J. Aspnes;C. Busch;S. Dolev;P. Fatourou;Chryssis Georgiou;Alexander A. Shvartsman;P. Spirakis;Roger Wattenhofer
通讯作者：
Roger Wattenhofer
影响因子：
3.1
作者：
C. Scheideler
通讯作者：
C. Scheideler