A practical algorithm for constructing oblivious routing schemes
A practical algorithm for constructing oblivious routing schemes
复制标题
一种构建不经意路由方案的实用算法
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Harald Räcke
中科院分区：
文献类型：
--
作者：
Marcin Bienkowski;M. Korzeniowski;Harald Räcke
在（随机的）遗漏路由方案中，为源s和目标t之间的请求选择的路径独立于网络中的当前流量。因此，这样的方案由网络中的每个源目标对，t，t的s-t路径上的概率分布组成。在最近的结果[11]中，表明，对于任何无方向的网络，都有一个忽略的路由方案，可以实现一个多属性的路由方案相对于拥塞的竞争比率。随后，Azar等人。 [4]给出了一种多项式时间算法，对于给定的网络构建了最佳的遗忘路由方案，即保证最佳竞争比率的计划。不幸的是，后一个结果基于椭圆形算法。因此，对于大型网络而言，这是不可行的。在本文中，我们提出了一种组合算法，用于构建一种忽略的路由方案，该方案保证了无向网络的O（log4n）的竞争比率。此外，我们的方法可以证明存在具有竞争比（log3n）的遗忘路由方案，这比[11]的原始证据要简单得多。
In a (randomized) oblivious routing scheme the path chosen for a request between a source s and a target t is independent from the current traffic in the network. Hence, such a scheme consists of probability distributions over s-t paths for every source-target pair s,t in the network.In a recent result [11] it was shown that for any undirected network there is an oblivious routing scheme that achieves a polylogarithmic competitive ratio with respect to congestion. Subsequently, Azar et al. [4] gave a polynomial time algorithm that for a given network constructs the best oblivious routing scheme, i.e. the scheme that guarantees the best possible competitive ratio. Unfortunately, the latter result is based on the Ellipsoid algorithm; hence it is unpractical for large networks.In this paper we present a combinatorial algorithm for constructing an oblivious routing scheme that guarantees a competitive ratio of O(log4n) for undirected networks. Furthermore, our approach yields a proof for the existence of an oblivious routing scheme with competitive ratio O(log3n), which is much simpler than the original proof from [11].