We formulate the optimal address space design problem as the task to set
node addresses in order to minimize certain network-wide entropy-related measures.
We derive tight space bounds for many well-known graph families and we propose
a simple heuristic to find optimal address spaces for general graphs. Our evaluations
suggest that in structured graphs, including most practically important network
topologies, significant memory savings can be attained by forwarding table compression
over our optimized address spaces. According to our knowledge, our work
is the first to bridge the gap between computer network scalability and information-theory.