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

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

doi:10.1109/ISCC.2013.6755040

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 proceeding › Conference proceeding contribution

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 language	English
Title of host publication	IEEE Symposium on Computers and Communications, ISCC 2013
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	759-764
Number of pages	6
ISBN (Electronic)	9781479937554
DOIs	https://doi.org/10.1109/ISCC.2013.6755040
Publication status	Published - 2013
Externally published	Yes
Event	18th IEEE Symposium on Computers and Communications, ISCC 2013 - Split, Croatia Duration: 7 Jul 2013 → 10 Jul 2013

Conference

Conference	18th IEEE Symposium on Computers and Communications, ISCC 2013
Country	Croatia
City	Split
Period	7/07/13 → 10/07/13

Access to Document

10.1109/ISCC.2013.6755040

Link to publication in Scopus

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

@inproceedings{b17749e955244ded90441b192f058c48,

title = "LMD: a local minimum driven and self-organized method to obtain locators",

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.",

author = "Yonggong Wang and Gaogang Xie and Kaafar, {Mohamed Ali} and Steve Uhlig",

year = "2013",

doi = "10.1109/ISCC.2013.6755040",

language = "English",

pages = "759--764",

booktitle = "IEEE Symposium on Computers and Communications, ISCC 2013",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Wang, Y, Xie, G, Kaafar, MA & Uhlig, S 2013, LMD: a local minimum driven and self-organized method to obtain locators. in IEEE Symposium on Computers and Communications, ISCC 2013., 6755040, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, pp. 759-764, 18th IEEE Symposium on Computers and Communications, ISCC 2013, Split, Croatia, 7/07/13. https://doi.org/10.1109/ISCC.2013.6755040

LMD : a local minimum driven and self-organized method to obtain locators. / Wang, Yonggong; Xie, Gaogang; Kaafar, Mohamed Ali; Uhlig, Steve.

IEEE Symposium on Computers and Communications, ISCC 2013. Piscataway : Institute of Electrical and Electronics Engineers (IEEE), 2013. p. 759-764 6755040.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

TY - GEN

T1 - LMD

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

AU - Wang, Yonggong

AU - Xie, Gaogang

AU - Kaafar, Mohamed Ali

AU - Uhlig, Steve

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84897411437&partnerID=8YFLogxK

U2 - 10.1109/ISCC.2013.6755040

DO - 10.1109/ISCC.2013.6755040

M3 - Conference proceeding contribution

SP - 759

EP - 764

BT - IEEE Symposium on Computers and Communications, ISCC 2013

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway

ER -