Trap Array : A Unified Model for Scalability Evaluation of Geometric Routing

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

1 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationSIGMETRICS 2013
Subtitle of host publicationProceedings of the 2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Pages317-328
Publication statusPublished - Jun 2013
Externally publishedYes

Publication series

NamePerformance Evaluation Review
Publisher Association for Computing Machinery
Number1
Volume41
ISSN (Print)0163-5999

Conference

Title2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2013
PlaceUnited States
CityPittsburgh
Period17 - 21 June 2013

Abstract

Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sub-linear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing (geo-routing). To date the two lines of research have been largely independent, perhaps because of the distinct principles they follow. In particular, it remains unclear how they compare with each other in the worst case, despite extensive experimental results showing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified framework to uncover the limiting behavior of ten representative geo-routing algorithms [18, 21, 25, 24, 5, 12, 36, 27, 33, 32]. We present a series of new theoretical results, in comparison with the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geometric Routing (CGR) algorithm that attempts to leverage the benefits of both approaches. Theoretical analysis and simulations show the advantages of the topology model and the algorithm. Copyright © 2013 ACM.

Research Area(s)

  • Geometric routing, Scalability

Citation Format(s)

Trap Array: A Unified Model for Scalability Evaluation of Geometric Routing. / Tan, Guang; Yin, Zhimeng; Jiang, Hongbo.
SIGMETRICS 2013: Proceedings of the 2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2013. p. 317-328 (Performance Evaluation Review; Vol. 41, No. 1).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review