Local memory requirement of universal routing schemes.

Abstract : In this paper, we deal with the compact routing problem, that is the problem of implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all networks. In [13], Peleg and Upfal showed that one can not implement a universal routing scheme with less than a total of Omega(n^{1+1/(2s+4)}) memory bits for any routing scheme satisfying that the maximum ratio between the lengths of the routing paths and the lengths of the shortest paths, that is the stretch factor, is bounded by s. In [6], Fraigniaud and Gavoille improve this bound by proving that universal routing schemes of stretch factors at most 2 use a total of Omega(n^2) memory bits in the worst-case. Recently, Gavoille and Pérennès [9] showed that, in fact, in the worst-case, Theta(n) routers of an n-node network may require up to Omega(n log n) memory bits for shortest path routing. In this paper, we extend this result by showing that, for any constant e, 0 < e < 1, Omega(n^e) routers of an n-node network may require up to Omega(n log n) memory bits even if each routing path is of length up to twice the distance between its source and its destination.
Document type :
Reports
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101881
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:53 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR1996-01.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101881, version 1

Collections

Citation

Pierre Fraigniaud, Cyril Gavoille. Local memory requirement of universal routing schemes.. [Research Report] LIP RR-1996-01, Laboratoire de l'informatique du parallélisme. 1996, 2+8p. ⟨hal-02101881⟩

Share

Metrics

Record views

7

Files downloads

20