Adaptive Decentralized Routing in Small-World Networks

Author

Bakun, Oleg ; Konjevod, Goran

Author_Institution

Arizona State Univ., Tempe, AZ, USA

fYear

2010

fDate

15-19 March 2010

Firstpage

1

Lastpage

6

Abstract

We study routing in a small-world network modeled by an augmented grid, where Kleinberg´s expected polylog bound offers a theoretical explanation for the empirically observed efficiency of greedy routing. We improve upon greedy through decentralized machine learning, using (local) ensembles of experts to choose routing edges and learn from feedback. In experiments with both synthetic and real networks, we observe improvements over greedy routing even when nodes are blind (do not know their neighbors´ locations) or a fraction of nodes are uncooperative.

Keywords

greedy algorithms; learning (artificial intelligence); telecommunication computing; telecommunication network routing; Kleinberg expected polylog bound; adaptive decentralized routing; augmented grid; decentralized machine learning; greedy routing; local ensembles; small-world networks; Artificial intelligence; Communications Society; Costs; Feedback; Learning systems; Machine learning; Network topology; Peer to peer computing; Routing; Solid modeling;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM IEEE Conference on Computer Communications Workshops , 2010

Conference_Location

San Diego, CA

Print_ISBN

978-1-4244-6739-6

Electronic_ISBN

978-1-4244-6739-6

Type

conf

DOI

10.1109/INFCOMW.2010.5466704

Filename

5466704