Compact Routing with Stretch Factor of Less Than Three(<Special Section>Foundations of Computer Science)

概要

論文の詳細を見る
Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O (n^<2/3> log^<4/3> n) based on a simple and practical model [1]. (The table-size is later improved to O (n^<1/2> log^<3/2> n) [11].) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that : (i) There is a routing algorithm with a stretch factor of two whose table-size is (n - √<n> + 2) log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2√<n>) log n in at least one node. Thus, we can only reduce roughly an additive √<n>log n (i. e., √<n> table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i. e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.
社団法人電子情報通信学会の論文
2005-01-01