Greedy Routing by Network Distance Embedding

摘要

Greedy routing has been applied to both wireline and wireless networks due to its scalability of routing state and resiliency to network dynamics. In this work, we solve a fundamental problem in applying greedy routing to networks with arbitrary topologies, i.e., how to construct node coordinates such that greedy routing can find near-optimal routing paths for various routing metrics. We propose Greedy Distance Vector (GDV), the first greedy routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no physical location information. Instead, it relies on a novel virtual positioning protocol, VPoD, which provides network distance embedding. Using VPoD, each node assigns itself a position in a virtual space such that the Euclidean distance between any two nodes in the virtual space is a good estimate of the routing cost between them. Experimental results using both real and synthetic network topologies show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a greedy routing protocol, the routing state of GDV per node remains small as network size increases. We also show that GDV and VPoD are highly resilient to dynamic topology changes.