Local memory requirement of universal routing schemes.

Pierre Fraigniaud (1) , Cyril Gavoille (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Dans cet article, nous abordons le problème du routage compact, qui est la mise en oeuvre des stratégies de routages utilisant une taille mémoire minimum pour chaque routeur. Une stratégie de routage universel est une stratégie qui s'applique à tous les réseaux. Dans [13], Peleg et Upfal ont montré qu'il n'y a aucun espoir de la réaliser avec moins de Omega(n^{1+1/(2s+4)}) bits mémoire au total pour toute stratégie de routage dont le rapport maximum entre la longueur des chemins de routage et la longueur des plus courts chemins, le facteur d' élongation, est borné par s. Dans [6], Fraigniaud et Gavoille améliorent cette borne en montrant que toute stratégie de routage universel de facteur d'élongation au plus 2 utilise un total de Omega(n^2) bits mémoire dans le pire cas. Récemment, Gavoille et Pérennès [9] ont montré, en fait, que Theta(n) routeurs d'un réseau de n noeuds peuvent chacun nécessiter localement de Omega(n log n) bits pour toute fonction de routage de plus courts chemins. Dans cet article, nous étendons ce résultat en montrant que, pour toute constante e, 0 < e < 1, Omega(n^e) routeurs d'un réseau de n noeuds nécessitent jusqu'à Omega(n log n) bits chacun si la longueur des chemins de routage est au plus deux fois plus longue que la longueur des plus courts chemins.

Mots clés: Communication on Parallel and Distributed Networks; Compact Routing Tables; Interval Routing; Shortest Path Routing

Mots clés: Communication sur réseaux parallèles et distribués; Routages de plus courts chemins; Tables de routages compactes

Domaines: Informatique [cs]

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⟩