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² 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.