Local Memory Requirement of Universal Routing Schemes

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\Gamma 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\Gamma n 2 ) memory bits in the worst-case. Recently, Gavoille and P'erenn`es [9] showed that, in fact, in the worst-case, \Theta(n) routers of an n-node network may require up to \Omega\Gamma n log n) memory bits for shortest path routing. In this paper, we extend this result by showing t..