论文标题
在加权图中紧凑的遗忘路由
Compact Oblivious Routing in Weighted Graphs
论文作者
论文摘要
路由表的空间要求是路由方案的重要特征。为了最大程度地减少总网络负载的成本衡量，存在各种结果，这些结果表明路由表的拉伸和所需尺寸之间的权衡。本文设计了紧凑的路由方案，以用于成本量的拥堵，其目标是最大程度地减少网络中链接的最大相对负载（链接的相对负载是其流量除以其带宽）。我们表明，对于任意的无向图，我们可以获得具有竞争比$ \ tilde {\ Mathcal {o}}}（1）$具有header长$ \ tilde {\ Mathcal {o}}（O}}（O}}（1）$的$ \ tilde $ \ tilde $ {Oution-Mathablem}的utiane-Mathcal-y Mathcal-y Mathcal-y Mathcal-y Mathcal-y Mathcal-Mathcal-Mathcal-MAUSE-OUSER， $ \ tilde {\ Mathcal {o}}（\ operatorAtorName {deg}（v））$在图中的每个顶点$ v $上。 这改善了Räcke和Schmid的结果，他们证明了未加权图的结果。
The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of results that show tradeoffs between stretch and required size for the routing tables. This paper designs compact routing schemes for the cost-measure congestion, where the goal is to minimize the maximum relative load of a link in the network (the relative load of a link is its traffic divided by its bandwidth). We show that for arbitrary undirected graphs we can obtain oblivious routing strategies with competitive ratio $\tilde{\mathcal{O}}(1)$ that have header length $\tilde{\mathcal{O}}(1)$, label size $\tilde{\mathcal{O}}(1)$, and require routing-tables of size $\tilde{\mathcal{O}}(\operatorname{deg}(v))$ at each vertex $v$ in the graph. This improves a result of Räcke and Schmid who proved a similar result in unweighted graphs.
