Finding Routing Shortcuts using an Internet Coordinate System

Cantin, François; Leduc, Guy

doi:10.1007/978-3-642-19167-1_6

Download

Paper published in a journal (Scientific congresses and symposiums)

Finding Routing Shortcuts using an Internet Coordinate System

Cantin, François; Leduc, Guy

2011 • In Lecture Notes in Computer Science, 6557, p. 56-67

Peer reviewed

Permalink
https://hdl.handle.net/2268/78793

DOI
10.1007/978-3-642-19167-1_6

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

FC-iwsos2011-final.pdf

Author postprint (690.4 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Overlay routing; Coordinate system

Abstract :

[en] Overlay routing is a promising way to improve the quality of service in the Internet but its main drawback is scalability: measuring the characteristics of the paths, exchanging the measurement results between the nodes and computing the best routes in the full mesh overlay network generally imply a high consumption of resources. In this paper, we design the basis of a lightweight self-organising one-hop overlay routing mechanism improving the latencies: we define criteria that rely on the information provided by an Internet Coordinate System (ICS) in order to provide a small set of potential one-hop shortcuts for any given path in the network with a small measurement cost. Our best criterion does not guarantee to find the best shortcut for any given path in a network but, even in networks with hundreds or thousands of nodes, it will restrict the search for potential shortcuts to about one or two percent of the total number of nodes.

Disciplines :

Computer science

Author, co-author :

Cantin, François ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques

Leduc, Guy ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques

Language :

English

Title :

Finding Routing Shortcuts using an Internet Coordinate System

Publication date :

23 February 2011

Event name :

Fifth International Workshop on Self-Organizing Systems (IWSoS)

Event place :

Karlsruhe, Germany

Event date :

23-24 Feb. 2011

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Volume :

6557

Pages :

56-67

Peer reviewed :

Peer reviewed

European Projects :

FP7 - 223936 - ECODE - Experimental COgnitive Distributed Engine

Funders :

CE - Commission Européenne

Available on ORBi :

since 07 December 2010

Statistics

Number of views

143 (16 by ULiège)

Number of downloads

220 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Andersen, D., Balakrishnan, H., Kaashoek, F., Morris, R.: Resilient overlay networks. SIGOPS Oper. Syst. Rev. 35(5), 131-145 (2001)
Dabek, F., Cox, R., Kaashoek, F., Morris, R.: Vivaldi: A decentralized network coordinate system. In: Proc. of SIGCOMM, Portland, OR, USA (August 2004)
Gummadi, K.P., Madhyastha, H.V., Gribble, S.D., Levy, H.M., Wetherall, D.: Improving the reliability of internet paths with one-hop source routing. In: Proceedings of OSDI. USENIX Association, Berkeley (2004)
Kaafar, M., Cantin, F., Gueye, B., Leduc, G.: Detecting triangle inequality violations for internet coordinate systems. In: Proc. of Future Networks 2009 Workshop, Dresden, Germany (June 2009)
Ledlie, J., Gardner, P., Seltzer, M.I.: Network coordinates in the wild. In: Proc of NSDI, Cambridge, UK (April 2007)
Liao, Y., Kaafar, M., Gueye, B., Cantin, F., Geurts, P., Leduc, G.: Detecting triangle inequality violations in internet coordinate systems by supervised learning - work in progress. In: Proc. of Networking 2009, Aachen, Germany (May 2009)
Lumezanu, C., Baden, R., Levin, D., Spring, N., Bhattacharjee, B.: Symbiotic relationships in internet routing overlays. In: Proceedings of NSDI, pp. 467-480. USENIX Association, Berkeley (2009)
Nakao, A., Peterson, L., Bavier, A.: A routing underlay for overlay networks. In: Proceedings of SIGCOMM, pp. 11-18. ACM, New York (2003)
Nakao, A., Peterson, L., Bavier, A.: Scalable routing overlay networks. SIGOPS Oper. Syst. Rev. 40(1), 49-61 (2006)
Ng, T.S.E., Zhang, H.: Predicting Internet network distance with coordinates-based approaches. In: Proc. of INFOCOM, New York, NY, USA (June 2002)
A simulator for peer-to-peer protocols, http://www.pdos.lcs.mit.edu/ p2psim/index.html
PlanetLab: An open platform for developing, deploying, and accessing planetary-scale services, http://www.planet-lab.org
Savage, S., Anderson, T., Aggarwal, A., Becker, D., Cardwell, N., Collins, A., Hoffman, E., Snell, J., Vahdat, A., Voelker, G., Zahorjan, J.: Detour: Informed internet routing and transport. IEEE Micro. 19(1), 50-59 (1999)
Savage, S., Collins, A., Hoffman, E., Snell, J., Anderson, T.: The end-to-end effects of internet path selection. SIGCOMM Comput. Commun. Rev. 29(4), 289-299 (1999)
Sontag, D., Zhang, Y., Phanishayee, A., Andersen, D.G., Karger, D.: Scaling all-pairs overlay routing. In: Proceedings of CoNEXT, Rome, Italy (December 2009)
Wong, B., Slivkins, A., Sirer, E.: Meridian: A lightweight network location service without virtual coordinates. In: Proc. of the ACM SIGCOMM (August 2005)
Zheng, H., Lua, E.K., Pias, M., Griffin, T.G.: Internet routing policies and round-trip-times. In: Dovrolis, C. (ed.) PAM 2005. LNCS, vol. 3431, pp. 236-250. Springer, Heidelberg (2005)