Compact routing schemes
Compact routing schemes
复制标题
DOI：
10.1145/378580.378581
复制
发表时间：
2001-07
期刊：
影响因子：
--
通讯作者：
M. Thorup;Uri Zwick
中科院分区：
文献类型：
--
作者：
M. Thorup;Uri Zwick
我们描述了几种适用于一般加权无向网络的紧凑路由方案。我们的方案简单且易于实现。网络节点中存储的路由表都非常小。附加在路由消息上的首部，包括目的地址，都极短。每个节点的路由决策所花时间为常数。然而，这些路由方案的伸展度，即数据包所经路径的代价与从源到目的的最便宜路径的代价之间的最坏比率，是一个小常数。我们的方案在所用路由表的大小和产生的伸展度之间实现了近乎最优的权衡。更具体地说，我们得到：
一种在具有伸展度为3的n节点网络的每个节点上仅使用O(n^(1/2))位内存的路由方案。在这样一种意义下，该空间（在对数因子范围内）是最优的：即每个伸展度为2的路由方案，以及每个伸展度为3/2的路由方案。所用的首部仅为(1 + Θ(1))log₂n位长，并且每个路由决策所花时间为常数。该方案的一个变体，其首部为[log₂n]位，其路由决策时间为Θ(log log n)。
此外，对于每个整数k > 2，一种基于通用握手的路由方案，在每个节点上使用O(n^(1/k))位内存，且伸展度为2k - 1。1963年厄尔多斯的一个猜想（已对k = 3, 5得到解决）意味着，相对于伸展度，路由表的大小近乎最优。这种握手在精神上类似于TCP/IP中的DNS查找。首部为Θ(log₂n)位长，并且每个路由决策所花时间为常数。如果没有握手，该方案的伸展度会增加到4k - 5。
用于获得上述路由方案的一个要素可能具有独立的实践和理论意义：一种针对任意度和直径的树的最短路径路由方案，它为一个n节点树的每个顶点分配一个(1 + Θ(1))log₂n位的标签。给定源节点的标签和目的节点的标签，能够在常数时间内计算出从源节点出发指向目的节点方向的边的端口号。
针对k > 2的通用方案还使用了作者最近引入的一种聚类技术。使用这种技术得到的聚类会诱导出网络的一个稀疏且低伸展度的树覆盖。这实质上是将一般网络中的路由问题简化为可以使用上述技术解决的树中的路由问题。
We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:A routing scheme that uses only O (n 1/2) bits of memory at each node of an n-node network that has stretch 3. The space is optimal, up to logarithmic factors, in the sense that every routing scheme with stretch n2), and every routing scheme with stretch n3/2). The headers used are only (1 + &Ogr;(1)) log2> n-bits long and each routing decision takes constant time. A variant of this scheme with [log2 n] -bit headers makes routing decisions in &Ogr;(log log n) time. Also, for every integer k > 2, a general handshaking based routing scheme that uses O (n1/k) bits of memory at each node that has stretch 2k - 1. A conjecture of Erdös from 1963, settled for k = 3, 5, implies that the routing tables are of near-optimal size relative to the stretch. The handshaking is similar in spirit to a DNS lookup in TCP/IP. Headers are &Ogr;(log2 n) bits long and each routing decision takes constant time. Without handshaking, the stretch of the scheme increases to 4k — 5. One ingredient used to obtain the routing schemes mentioned above, may be of independent practical and theoretical interest: A shortest path routing scheme for trees of arbitrary degree and diameter that assigns each vertex of an n-node tree a (1 + &Ogr;(1)) log2 n-bit label. Given the label of a source node and the label of a destination it is possible to compute, in constant time, the port number of the edge from the source that heads in the direction of the destination. The general scheme for k > 2 also uses a clustering technique introduced recently by the authors. The clusters obtained using this technique induce a sparse and low stretch tree cover of the network. This essentially reduces routing in general networks into routing problems in trees that could be solved using the above technique.