Title :
Load balancing in ad hoc networks: single-path routing vs. multi-path routing
Author :
Ganjali, Yashar ; Keshavarzian, Ali
Author_Institution :
Dept. of Electr. Eng., Stanford Univ., CA, USA
Abstract :
Multi-path routing has been studied thoroughly in the context of wired networks. Ii has been shown that using multiple paths to route messages between any source-destination pair of nodes (instead of using a single path) balances the load more evenly throughout the network. The common belief is that the same is true for ad hoc networks, i.e., multi-path routing balances the load significantly better than single-path routing. We show that this is not necessarily the case. We introduce a new model for evaluating the load balance under multi-path routing, when the paths chosen are the first K shortest paths (for a pre-specified K). Using this model, we show that unless we use a very large number of paths (which is very costly and therefore infeasible) the load distribution is almost the same as single shortest path routing. This is in contrary to the previous existing results which assume that multi-path routing distributes the load uniformly.
Keywords :
ad hoc networks; mobile radio; resource allocation; telecommunication network routing; K shortest paths; ad hoc network; load balancing; multipath routing; single-path routing; wired network; Ad hoc networks; Analytical models; Buildings; Frequency; Intelligent networks; Load management; Mobile ad hoc networks; Routing protocols; Telecommunication traffic; Traffic control;
Conference_Titel :
INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies
Print_ISBN :
0-7803-8355-9
DOI :
10.1109/INFCOM.2004.1356998