论文标题
跳闸的遗忘路线
Hop-Constrained Oblivious Routing
论文作者
论文摘要
我们证明存在$ \ mathrm {poly}（\ log n）$的遗忘路由方案的存在 - 在$（Excestion + Extration）$方面具有竞争力，从而解决了一个著名的问题中的众所周知的问题。 具体而言，考虑一个无向网络和一组带有其源和目的地的数据包。目的是为每个数据包选择一条路径，从其源到目的地，以最大程度地减少$（拥塞 +扩张）$，定义为如下：扩张是最大路径跳高长度，并且拥塞是包含任何单个边缘的最大路径数量。路由方案遗忘和随机选择了每个数据包的路径，而不是（存在）其他数据包的存在。尽管存在这种遗忘，但所选路径在$ \ mathrm {poly}（\ log n）$最佳价值的因子中具有$（拥塞 +扩张）$。更准确地说，对于任何整数型啤酒花$ h $，这种遗忘的路由方案最多最多可以选择$ h \ cdot \ cdot \ mathrm {poly}（\ log n）$，并且是$ \ mathrm {poly}（\ log log}（\ log log n）$ - 在$ coption $ coption $ a coption $ $ $ $ hept的竞争中，可以通过$ $ $ heorev oppation $ heorev heorev。这些路径可以在多项式时间内采样。 该结果可以看作是Räcke[Focs 2002，STOC 2008]的著名遗忘路线结果的类似物，该结果是$ O（\ log n）$ - 在$ costeption $方面具有竞争力，但在$ jealation $方面没有竞争力。
We prove the existence of an oblivious routing scheme that is $\mathrm{poly}(\log n)$-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 a $\mathrm{poly}(\log n)$ factor of the best possible value. More precisely, for any integer hop-bound $h$, this oblivious routing scheme selects paths of length at most $h \cdot \mathrm{poly}(\log n)$ and is $\mathrm{poly}(\log n)$-competitive in terms of $congestion$ in comparison to the best possible $congestion$ achievable via paths of length at most $h$ hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of Räcke [FOCS 2002, STOC 2008], which are $O(\log n)$-competitive in terms of $congestion$, but are not competitive in terms of $dilation$.
