TCS / Research / Publications / Balanced multipath source routing
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Balanced multipath source routing


Shreyas Prasad, André Schumacher, Harri Haanpää, and Pekka Orponen. Balanced multipath source routing. In T. Vazão, M. M. Freire, and I. Chong, editors, Proceedings of the 21st International Conference on Information Networking (ICOIN'07, Estoril, Portugal, January 2007), volume 5200 of Lecture Notes in Computer Science, pages 315–324, Berlin Heidelberg, 2008. Springer-Verlag.


We consider the problem of balancing the traffic load ideally over a wireless multihop network. In previous work, a systematic approach to this task was undertaken, starting with an approximate optimisation method that guarantees a provable congestion performance bound, and then designing a distributed implementation by modifying the DSR protocol. In this paper, the performance of the resulting Balanced Multipath Source Routing (BMSR) protocol is validated in a number of simulated networking scenarios. In particular, we study the effect of irregular network structure on the performance of the protocol, and compare it to the performance of DSR and an idealised shortest-path routing algorithm in setups with several source-destination pairs. For all network scenarios we consider, BMSR outperforms DSR significantly. BMSR is also shown to be more robust than the shortest-path algorithm, in that it can distribute the traffic load more evenly in cases where shortest-path routing is impeded by radio interference between proximate paths.


sensor networks, ad hoc networks, routing, load balancing, distributed optimisation

Suggested BibTeX entry:

    address = {Berlin Heidelberg},
    author = {Shreyas Prasad and Andr\'e Schumacher and Harri Haanp\"a\"a and Pekka Orponen},
    booktitle = {Proceedings of the 21st International Conference on Information Networking (ICOIN'07, Estoril, Portugal, January 2007)},
    editor = {T. Vaz{\~a}o and M. M. Freire and I. Chong},
    pages = {315--324},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Balanced multipath source routing},
    volume = {5200},
    year = {2008},

See ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.