LMD: a local minimum driven and self-organized method to obtain locators

Yonggong Wang, Gaogang Xie, Mohamed Ali Kaafar, Steve Uhlig

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

The scalability of routing architectures for large networks is one of the biggest challenges that the Internet faces today. Greedy routing, in which each node is assigned a locator used as a distance metric, recently received increased attention from researchers and is considered as a potential solution for scalable routing. In this paper, we propose LMD-A Local Minimum Driven method to compute the topology-based locator. As opposed to previous work, our algorithm employs a quasigreedy and self-organized embedding method, which outperforms similar decentralized algorithms by up to 20% in success rate. To eliminate the negative effect of the 'quasi' greedy property-transfer routes longer than the shortest routes, we introduce a two-stage routing strategy, which combines the greedy routing with source routing. The greedy routing path discovered and compressed in the first stage is then used by the following source-routing stage. Through extensive evaluations, based on synthetic topologies as well as on a snapshot of the real Internet AS topology, we show that LMD guarantees 100% delivery rate on large networks with a very low stretch.

Original languageEnglish
Title of host publicationIEEE Symposium on Computers and Communications, ISCC 2013
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages759-764
Number of pages6
ISBN (Electronic)9781479937554
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event18th IEEE Symposium on Computers and Communications, ISCC 2013 - Split, Croatia
Duration: 7 Jul 201310 Jul 2013

Conference

Conference18th IEEE Symposium on Computers and Communications, ISCC 2013
Country/TerritoryCroatia
CitySplit
Period7/07/1310/07/13

Fingerprint

Dive into the research topics of 'LMD: a local minimum driven and self-organized method to obtain locators'. Together they form a unique fingerprint.

Cite this