Compact Routing with Stretch Factor of Less Than Three

Kazuo IWAMA; Akinori KAWACHI

doi:10.1093/ietisy/e88-d.1.47

Compact Routing with Stretch Factor of Less Than Three

Kazuo IWAMA, Akinori KAWACHI

Full Text Views

0

Share
Cite this

Summary :

Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n^2/3log^4/3n) based on a simple and practical model. (The table-size is later improved to O(n^1/2log^3/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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.47-52

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.47

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Kazuo IWAMA, Akinori KAWACHI, "Compact Routing with Stretch Factor of Less Than Three" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 47-52, January 2005, doi: 10.1093/ietisy/e88-d.1.47.
Abstract: Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n^2/3log^4/3n) based on a simple and practical model. (The table-size is later improved to O(n^1/2log^3/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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.47/_p

Copy

@ARTICLE{e88-d_1_47,
author={Kazuo IWAMA, Akinori KAWACHI, },
journal={IEICE TRANSACTIONS on Information},
title={Compact Routing with Stretch Factor of Less Than Three},
year={2005},
volume={E88-D},
number={1},
pages={47-52},
abstract={Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n^2/3log^4/3n) based on a simple and practical model. (The table-size is later improved to O(n^1/2log^3/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.},
keywords={},
doi={10.1093/ietisy/e88-d.1.47},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Compact Routing with Stretch Factor of Less Than Three
T2 - IEICE TRANSACTIONS on Information
SP - 47
EP - 52
AU - Kazuo IWAMA
AU - Akinori KAWACHI
PY - 2005
DO - 10.1093/ietisy/e88-d.1.47
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n^2/3log^4/3n) based on a simple and practical model. (The table-size is later improved to O(n^1/2log^3/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.
ER -