For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Compact Routing with Stretch Factor of Less Than Three
Kazuo IWAMA Akinori KAWACHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
distributed algorithms, compact routing, stretch factor,
Full Text: PDF(172.2KB)
>>Buy this Article
Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n2/3log4/3n) based on a simple and practical model. (The table-size is later improved to O(n1/2log3/2n).) 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 -+ 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)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., 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.