Notes:

This paper subsumes the results of Compact routing with name independence, Arias, Cowen, Laing, Rajaraman, Taka, SPAA'03
Key ingredients are "vicinity balls" (vs. balls of fixed radius) and "partial shortest path trees" (very clever)
For derandomization (which is besides the point of routing) this paper uses techniques of:
- RL ⊆ SC, Nisan, STOC'92
- Pseudo-random generators for space-bounded computation, Combinatorica'92, and
- Algorithmic derandomization via complexitytheory, Sivakumar, STOC'02
which techniques seem interesting, and worth looking at.
Finally, the paper uses a beautiful trick of Storing a sparse table, Tarjan, Yao, CACM'79 for producing a balanced hash function $h:[n]\\rightarrow[\\sqrt{n}]$ that can be evaulated in constant time and stored in $O(\\sqrt{n})$ bits.