Path vector face routing: Geographic routing with local face information

Ben Leong, Sayan Mitra, Barbara Liskov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Existing geographic routing algorithms depend on the planarization of the network connectivity graph for correctness, and the planarization process gives rise to a well-defined notion of "faces". In this paper, we demonstrate that we can improve routing performance by storing a small amount of local face information at each node. We present a protocol, Path Vector Exchange (PVEX), that maintains local face information at each node efficiently, and a new geographic routing algorithm, Greedy Path Vector Face Routing (GPVFR), that achieves better routing performance in terms of both path stretch and hop stretch than existing geographic routing algorithms by exploiting available local face information. Our simulations demonstrate that GPVFR/PVEX achieves significantly reduced path and hop stretch than Greedy Perimeter Stateless Routing (GPSR) and somewhat better performance than Greedy Other Adaptive Face Routing (GOAFR+) over a wide range of network topologies. The cost of this improved performance is a small amount of additional storage, and the bandwidth required for our algorithm is comparable to GPSR and GOAFR+ in quasi-static networks.

Original languageEnglish (US)
Title of host publicationProceedings - 13TH IEEE International Conference on Network Protocols, ICNP 2005
Pages147-158
Number of pages12
DOIs
StatePublished - 2005
Externally publishedYes
Event13TH IEEE International Conference on Network Protocols, ICNP 2005 - Boston, MA, United States
Duration: Nov 6 2005Nov 9 2005

Publication series

NameProceedings - International Conference on Network Protocols, ICNP
Volume2005
ISSN (Print)1092-1648

Other

Other13TH IEEE International Conference on Network Protocols, ICNP 2005
CountryUnited States
CityBoston, MA
Period11/6/0511/9/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Path vector face routing: Geographic routing with local face information'. Together they form a unique fingerprint.

Cite this