Memory requirement for routing in distributed networks
Cyril Gavoille, Stéphane Pérennès · 1996
In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node.We prove that for every shortest path routing scheme, for any constant e, O < c < 1, and for every integer d such that 3 ~d < En, there exists a n-node network of maximum degree d that locally requires @(n log d) bits of memory on El(n) nodes.This optimal lower bound means that whatever you choose the routing scheme (interval routing, boolean routing, prefix routing, ...).there exists a network on which one can not do better than routing tables.