Memory requirement for universal routing schemes
Pierre Fraigniaud, Cyril Gavoille · 1995
In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In [20], Peleg and Upfal showed that there is no hope to do that with less than a total \\Omega\\Gamma n 1+1=(2s+4) ) memory bits for any stretch factor s 1. We improve this bound for stretch factors s ! 2 by proving that any near-shortest path routing scheme uses a total of \\Omega\\Gamma n 2 ) memory bits.