Greedy Routing by Network Distance Embedding
| Autor: | Chen Qian, Simon S. Lam |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Routing protocol
Dynamic Source Routing Computer Networks and Communications Computer science Equal-cost multi-path routing Routing table Distributed computing Enhanced Interior Gateway Routing Protocol Wireless Routing Protocol Geographic routing 02 engineering and technology Metrics Network topology Hop (networking) Routing Information Protocol Computer Science::Networking and Internet Architecture 0202 electrical engineering electronic engineering information engineering Destination-Sequenced Distance Vector routing Electrical and Electronic Engineering Hierarchical routing Static routing Zone Routing Protocol Wireless network business.industry ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS 020208 electrical & electronic engineering Policy-based routing Path vector protocol 020206 networking & telecommunications Computer Science Applications Distance-vector routing protocol Optimized Link State Routing Protocol Routing domain Link-state routing protocol Multipath routing Hazy Sighted Link State Routing Protocol business Software Computer network |
| Zdroj: | IEEE/ACM Transactions on Networking. 24:2100-2113 |
| ISSN: | 1558-2566 1063-6692 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|