
For FullText 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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E88D
No.1
pp.4752 Publication Date: 2005/01/01
Online ISSN:
DOI: 10.1093/ietisy/e88d.1.47
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Keyword: distributed algorithms, compact routing, stretch factor,
Full Text: PDF(172.2KB) >>Buy this Article
Summary:
Cowen gave a universal compact routing algorithm with a stretch factor of three and tablesize of O(n^{2/3}log^{4/3}n) based on a simple and practical model. (The tablesize is later improved to O(n^{1/2}log^{3/2}n).) This paper considers, using the same model, how the necessary tablesize 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 tablesize 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 tablesize of (n  2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., tableentries) from the trivial tablesize of n log n which obviously enables shortestpath routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one tableentry) 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 tablesize.

