On the impact of alternate path routing for load balancing in mobile ad hoc networks

ABSTRACT

Alternate path routing (APR) can provide load balancing and route failure protection by distributing traffic among a set of diverse paths. These benefits make APR appear to be an ideal candidate for the bandwidth limited and mobile ad-hoc networks. However, we find that APR's potential is not fully realized in ad-hoc networks because of route coupling resulting from the geographic proximity of candidate paths between common endpoints. In multiple channel networks, coupling occurs when paths share common intermediate nodes. The coupling problem is much more serious in single channel networks, where coupling also occurs where one path crosses the radio coverage area of another path. The network's inherent route coupling is further aggravated by the routing protocol, which may provide an incomplete view of current network connectivity.Through analysis and simulation, we demonstrate the impact of route coupling on APR's delay performance in ad-hoc networks. In multiple channel environments, APR is able to provide a 20% reduction in end-to-end delay for bursty data streams. Though these gains are appreciable, they are about half what we would expect from APR with independently operating routes. Route coupling is so severe in single channel networks that APR provides only negligible improvements in quality of service.

REFERENCES

• 1: Richard J. Gibbens , Frank P. Kelly , Peter B. Key, Dynamic alternative routing, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 2: S-W Lee and C-S Wu, A k-Best Paths Algorithm for Highly Reliable Communication Networks, IEICE Transactions on Communications, vol. E82-B, no. 4, p. 586-590, April 1999.
• 3: R. Ogier and N. Shacham, A Distributed Algorithm for Finding Shortest Pairs of Disjoint Paths, IEEE INFOCOM '89.
• 4: Deepinder Sidhu , Raj Nair , Shukri Abdallah, Finding disjoint paths in networks, Proceedings of the conference on Communications architecture & protocols, p.43-51, September 03-06, 1991, Zurich, Switzerland
• 5: N. Taft-Plotkin, B. Bellur and R. Ogier, Quality-of-Service Routing Using Maximally Disjoint Paths, IEEE IWQoS '99, June 1999.
• 6: Sandeep Sibal , Antonio DeSimone, Controlling alternate routing in general-mesh packet flow networks, Proceedings of the conference on Communications architectures, protocols and applications, p.168-179, August 31-September 02, 1994, London, United Kingdom
• 7: R.G. Gallager, A Minimum Delay Routing Algorithm Using Distributed Computation, IEEE Transactions on Communication, vol. 25, pp. 73-84, Jan. 1977.
• 8: J.J. Garcia-Luna-Aceves, S. Vutukury and W.T. Zaumen, A Practical Approach to Minimizing Delays in Internet Routing, IEEE ICC'99, June 1999.
• 9: Flaminio Borgonovo, Deflection routing, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 10: Z. Wang , J. Crowcroft, Shortest path first with emergency exits, Proceedings of the ACM symposium on Communications architectures & protocols, p.166-176, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 11: R. Krishnan and J. Silvester, Choice of Allocation Granularity in Multipath Source Routing Schemes, IEEE INFOCOM'93, pp. 322-329, March 1993.
• 12: N. Gogate and S. Panwar, Assigning Customers to Two Parallel Servers with Resequencing, IEEE Transactions on Communications Letters, vol. 3, num. 4, p. 119, April 1999.
• 13: N. Gogate and S.S. Panwar, Supporting Applications in a Mobile Multihop Radio Environment Using Route Diversity, I. Non-Real Time Data, IEEE ICC'98, Atlanta, GA, June 1998.
• 14: N. Gogate, D. Chung, S. Panwar, Y. Wang, Supporting Image/Video Applications in a Mobile Multihop Radio Environment Using Route Diversity, IEEE ICC'99, Vancouver, BC, June, 1999.
• 15: N.F. Maxemchuk, Dispersity Routing, IEEE ICC'75, San Francisco, CA, June 1975.
• 16: E. Ayanoglu, I. Chih-Lin, R.Gitlin, J. Mazo, Diversity Coding for Self-Healing and Fault Tolerant Communication Networks, IEEE Trans. on Communication, vol. COM-41, pp. 1677-1688, Nov. 1993.
• 17: H. Siraj, On the Relationship Between Route Selection Policies and Route Demand in Ad-Hoc Networks, M. Eng. Design Project Report, Cornell University, May 1999.
• 18: Nasipuri, A. and Das, S.R., "On-Demand Multipath Routing for Mobile Ad Hoc Networks," IEEE ICCCN, Boston, MA, October, 1999.
• 19: Moy, J., "OSPF version 2," IETF RFC 2328, April 1998.
• 20: Johnson, D.B., and Maltz, D.A. , "Dynamic Source Routing in Ad-Hoc Wireless Networking," in Mobile Computing, T. Imielinski and H. Korth, editors, Kluwer Academic Publishing, 1996.
• 21: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 22: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 23: Pearlman, M.R. and Haas, Z.J., "Determining the Optimal Configuration of the Zone Routing Protocol," IEEE JSAC, vol. 17, num. 6, Aug. 1999.
• 24: M. Pearlman and Z. Haas, Improving the Performance of Query-Based Routing Protocols Through 'Diversity Injection', WCNC'99, New Orleans, LA, Sept. 1999.
• 25: Z.J. Haas and J. Deng, "Dual Busy Tone Multiple Access (DBTMA): A Medium Access Control for Multihop Networks," WCNC'99, New Orleans, LA, Sept. 1999.