Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:53 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101881, version 1



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⟩



Record views


Files downloads