Practical Compact Routing on Random Unit Disk Graphs

We describe a simple and practical algorithm for compact routing on connected random unit disk graphs. Using a recursive nested dissection of an n -vertex graph based on compact and balanced vertex separators, we construct routing tables with an average of O (log 2 n ) entries per vertex in a preprocessing step. The routing tables then support handshaking-based routing, where the handshaking can be implemented similarly to a DNS lookup. Our routing algorithm is guaranteed to deliver on the graph, while incurring moderate stretch. We describe a basic version of the algorithm that requires modifiable headers and a more advanced version that eliminates this need and incurs less stretch.