Congestion Avoidance Routing Protocol for Ad-Hoc Networks

##plugins.themes.academic_pro.article.sidebar##

Published Jul 1, 2010
https://doi.org/10.47164/ijngc.v1i1.10
Download
PDF
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 1, Issue 1, Inaugural Issue 2010

##plugins.themes.academic_pro.article.main##

Yi Lu
One Microsoft Way, Redmond, WA, USA
Bharat Bhargava
Department of Computer Science, Purdue University, 305 N. University Street, West Lafayette, IN, USA

Abstract

The objective of this research is to bring the consideration of congestion into the design of ad hoc routing protocols. The main thrust is to avoid congestion by minimizing contentions for channel access. The intermediate delay (IMD) is proposed to replace the hop count as a routing metric. IMD estimates the delay introduced by the intermediate nodes along the route using the sum of delays from each node. It characterizes the impacts of channel contention, traffic load, and the length of a route. The self-adjusting congestion avoidance (SAGA) routing protocol is designed to use IMD as the routing metric. SAGA reduces congestion at intermediate nodes. It selects routes that bypass the hot spot where contention is intense. The packet transmission procedure of the distributed coordination function (DCF) in the IEEE 802.11 standard is analyzed and used as a study case for evaluation and experimentation. An estimate of the transmission delay is derived based on local information available at a node. The estimation takes the impact of active traffic in the neighborhood into account without exchanging messages with neighbors.The performance of SAGA is evaluated and compared with that of ad hoc on-demand distance vector (AODV), dynamic source routing (DSR), and destination-sequenced distance-vector (DSDV) protocols using simulation. TCP and two types of UDP traffic are considered: constant bit rate traffic and traffic exhibiting long range dependency. SAGA can sustain heavier traffic load and offers higher peak throughput than AODV and DSR. The overhead of SAGA can be as low as 10% as that of AODV and 12% as that of DSR. The average end-to-end delay of SAGA is the lowest among the protocols. It is shown that considerations of congestion and intermediate delay instead of the hop count can enhance routing performance significantly.

##plugins.themes.academic_pro.article.details##

How to Cite
Yi Lu, & Bharat Bhargava. (2010). Congestion Avoidance Routing Protocol for Ad-Hoc Networks. International Journal of Next-Generation Computing, 1(1), 124–145. https://doi.org/10.47164/ijngc.v1i1.10
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. The network simulator - ns-2. http://www.isi.edu/nsnam/ns/ . 1996. WaveLAN/PCMCIA card user’s guide, Lucent Technologies.
  2. Bertossi, A. A. and Bonuccelli, M. A. 1995. Code assignment for hidden terminal interference avoidance in multihop packet radio networks. IEEE/ACM Transactions on Networking (TON) 3, 4, 441–449.
  3. Biaz, S. and Vaidya, N. H. 1998. Distinguishing congestion losses from wireless transmission losses: A negative result. In Proceedings of IEEE ICCCN. New Orleans, 722–731.
  4. Boukerche, A. and Das, S. K. 2003. Congestion control performance of R-DSDV protocol in multihop wireless ad hoc networks. Wireless Networks 9, 3, 261–270.
  5. Brakmo, L. S., O'Malley, S. W., and Peterson, L. L. 1994. TCP Vegas: New techniques for congestion detection and avoidance. In Proceedings of SIGCOMM. 24–35.
  6. Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y., and Jetcheva, J. 1998. A performance comparison of multihop wireless ad hoc network routing protocols. In Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). 85–97.
  7. Cen, S., Cosman, P. C., and Voelker, G. M. 2003. End-to-end differentiation of congestion and wireless losses. IEEE/ACM Transactions on Networking (TON) 11, 5, 703–717.
  8. Chandran, K., Raghunathan, S., Venkatesan, S., and Prakash, R. 2001. A feedback-based scheme for improving TCP performance in ad hoc wireless networks. IEEE Personal Communications 8, 1, 34–39.
  9. Chen, S. and Nahrstedt, K. 1999. Distributed quality-of-service routing in ad hoc networks. IEEE Journal on Selected Areas in Communications 17, 8, 1488–1505.
  10. Cordeiro, C., Das, S. R., and Agrawal, D. P. 2002. COPAS: Dynamic contention-balancing to enhance the performance of TCP over multi-hop wireless networks. In Proceedings of the 10th International Conference on Computer Communication and Networks (IC3N). Miami, 382–387.
  11. Corson, S. and Macker, J. 1999. Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations. RFC 2501, http://www.ietf.org/rfc/rfc2501.txt.
  12. De Couto, D. S. J., Aguayo, D., Bicket, J., and Morris, R. 2003. A high-throughput path metric for multihop wireless routing. In Proceedings of the 9th International Conference on Mobile Computing and Networking (MobiCom). 134–146.
  13. De Couto, D. S. J., Aguayo, D., Chambers, B. A., and Morris, R. 2003. Performance of multihop wireless networks: Shortest path is not enough. ACM SIGCOMM Computer Communication Review 33, 1, 83–88.
  14. Gelenbe, E. and Pujolle, G. 1998. Introduction to Queueing Networks, Second Edition. John Wiley & Sons.
  15. Hassanein, H. and Zhou, A. 2001. Routing with load balancing in wireless ad hoc networks. In Proceedings of the 4th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems. 89–96.
  16. Jacobson, V. 1988. Congestion avoidance and control. In Proceedings of Symposium on Communications Architectures and Protocols. 314–329.
  17. Jaffe, J. and Moss, F. 1982. A responsive distributed routing algorithm for computer networks. IEEE Transactions on Communications 30, 7, 1758–1762.
  18. Johansson, P., Larsson, T., Hedman, N., Mielczarek, B., and Degermark, M. 1999. Scenario-based performance analysis of routing protocols for mobile ad-hoc networks. In Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). Seattle, 195–206.
  19. Johnson, D. B. and Maltz, D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, T. Imielinski and H. Korth, Eds. Kluwer Academic Publishers, Chapter 5, 153–181.
  20. Kunniyur, S. and Srikant, R. 2003. End-to-end congestion control schemes: Utility functions, random losses and ECN marks. IEEE/ACM Transactions on Networking (TON) 11, 5, 689–702.
  21. Lee, S.-J. and Gerla, M. 2001. Dynamic load-aware routing in ad hoc networks. In Proceedings of ICC. Vol. 10. 3206–3210.
  22. Lin, C. 2001. On-demand QoS routing in multihop mobile networks. In Proceedings of INFOCOM. Vol. 3. 1735–1744.
  23. Liu, J. and Singh, S. 2001. ATCP: TCP for mobile ad hoc networks. IEEE Journal on Selected Areas in Communications 19, 7, 1300–1315.
  24. Lu, Y. and Bhargava, B. 2003. Self-adjusting congestion avoidance routing protocol for ad hoc networks. Technical Report CSD 03-018, Department of Computer Sciences, Purdue University.
  25. Lu, Y., Zhong, Y., and Bhargava, B. 2003. Packet loss in mobile ad hoc networks. Technical Report CSD 03-009, Department of Computer Sciences, Purdue University.
  26. Luo, H., Medvedev, P., and Lu, S. 2001. A self-coordinating approach to distributed fair queueing in ad hoc wireless networks. In Proceedings of INFOCOM. Vol. 3. 1370–1379.
  27. Marina, M. K. and Das, S. R. 2001. On-demand multipath distance vector routing in ad hoc networks. In Proceedings of the International Conference on Network Procotols (ICNP). Riverside, 14–23.
  28. Mendenhall, W. and Beaver, R. J. 1991. Introduction to Probability and Statistics, 8th ed. PWS-Kent Pub. Co., Boston.
  29. Mo, J., La, R., Anantharam, V., and Walrand, J. 1999. Analysis and comparison of TCP Reno and Vegas. In Proceedings of INFOCOM. 1556–1563.
  30. Padhye, J., Firoiu, V., Towsley, D. F., and Kurose, J. F. 2000. Modeling TCP Reno performance: A simple model and its empirical validation. IEEE/ACM Transactions on Networking (TON) 8, 2, 133–145.
  31. Parsa, C. and Garcia-Luna-Aceves, J. J. 2000. Improving TCP performance over wireless networks at the link layer. Mobile Networks and Applications 5, 1, 57–71.
  32. Perkins, C. E., Belding-Royer, E. M., and Das, S. R. 2003. Ad hoc on-demand distance vector (AODV) routing. RFC 3561, http://www.ietf.org/rfc/rfc3561.txt.
  33. Perkins, C. E. and Bhagwat, P. 1994. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In Proceedings of the ACM Conference on Communications Architectures, Protocols and Applications (SIGCOMM). 234–244.
  34. Perkins, C. E., Royer, E. M., Das, S. R., and Marine, M. K. 2001. Performance comparison of two on-demand routing protocols for ad hoc networks. IEEE Personal Communications 8, 1, 16–28.
  35. Sheu, S.-T., Tsai, Y., and Chen, J. 2003. MR2RP: The multi-rate and multi-range routing protocol for IEEE 802.11 ad hoc wireless networks. Wireless Networks 9, 2, 165–177.
  36. Toh, C.-K. 1997. Associativity-based routing for ad-hoc mobile networks. Wireless Personal Communications Journal 4, 2, 103–139.
  37. Tseng, Y.-C., Li, Y.-F., and Chang, Y.-C. 2003. On route lifetime in multihop mobile ad hoc networks. IEEE Transactions on Mobile Computing 2, 4, 366–376.
  38. Tsirigos, A. and Haas, Z. 2001. Multipath routing in the presence of frequent topological changes. IEEE Communications Magazine 39, 11, 132–138.
  39. Wang, F. and Zhang, Y. 2002. Improving TCP performance over mobile ad-hoc networks with out-of-order detection and response. In Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc). 217–225.
  40. Willinger, W., Taqqu, M. S., Sherman, R., and Wilson, D. V. 1997. Self-similarity through high-variability: Statistical analysis of ethernet LAN traffic at the source level. IEEE/ACM Transactions on Networking (TON) 5, 1, 71–86.
  41. Wu, X., Ding, G., and Bhargava, B. 2004. Impact of link distance on end-to-end throughput in multi-rate ad hoc networks. Tech. Rep. TR-04-026), Department of Computer Sciences, Purdue University.
  42. Xu, S. and Saadawi, T. 2002. Revealing the problems with 802.11 medium access control protocol in multi-hop wireless ad hoc networks. Journal of Computer Networks 38, 4, 531–548.
  43. Zhang, C. and Tsaoussidis, V. 2001. TCP-Real: Improving real-time capabilities of TCP over heterogeneous networks. In Proceedings of the 11th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV). 189–198.
  44. Zhang, Y. and Li, W. 2002. An integrated environment for testing mobile ad-hoc networks. In Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc). 104–111.
  45. Zhu, C. and Corson, M. 2002. QoS routing for mobile ad hoc networks. In Proceedings of INFOCOM. Vol. 2. 958–967.