Skip to main content
SpringerLink
Log in

Providing Fault-Tolerant Ad hoc Routing Service in Adversarial Environments

  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

Abstract

Most existing designs of ad hoc networks are based on the assumption of non-adversarial environments, where each node in the network is cooperative and well-behaved. When misbehaving nodes exist in the network, the performance of current routing protocols degrades significantly. Since ad hoc networks, consisting of autonomous nodes, are open and distributed in nature, maintaining a fault-free network environment is extremely difficult and expensive.

In this paper, we propose a new routing service named best-effort fault-tolerant routing (BFTR). The design goal of BFTR is to provide packet routing service with high delivery ratio and low overhead in presence of misbehaving nodes. Instead of judging whether a path is good or bad, i.e., whether it contains any misbehaving node, BFTR evaluates the routing feasibility of a path by its end-to-end performance (e.g. packet delivery ratio and delay). By continuously observing the routing performance, BFTR dynamically routes packets via the most feasible path. BFTR provides an efficient and uniform solution for a broad range of node misbehaviors with very few security assumptions. The BFTR algorithm is evaluated through both analysis and extensive simulations. The results show that BFTR greatly improves the ad hoc routing performance in the presence of misbehaving nodes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Royer and C. Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks”, IEEE Personal Communications Magazine pp. 46–55, 1999.

  2. D.B. Johnson and D.A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks”, Mobile Computing pp. 153–181, 1996.

  3. J. Kong, P. Zerfos, H. Luo, S. Lu and L. Zhang, “Providing Robust and Ubiquitous Security Support for Mobile AdHoc Networks" in International Conference on Network Protocols (ICNP), Riverside, CA, November 11–14, 2001.

  4. L. Zhou and Z.J. Haas, “Securing Ad Hoc Networks”, IEEE Network Magazine Vol. 13, 1999.

  5. W. Diffie and M. E. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, 1976.

  6. P. Papadimitratos and Z.J. Haas, “Secure Routing for Mobile Ad Hoc Networks”, in SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), 2002.

  7. S. Yi, P. Naldurg and R. Kravets, “Security-Aware Ad-Hoc Routing for Wireless Networks”, in Technical Report No. UIUCDCS-R-2001-2241, UILU-ENG-2001-1748, 2001.

  8. Y.-C. Hu, A. Perrig and D.B. Johnson, “Ariadne: ASecure on-Demand Routing Protocol for AdHoc Networks”, in The Eighth Annual International Conference on Mobile Computing and Networking, 2002.

  9. S. Marti, T. J. Giuli, Kevin Lai and Mary Baker, “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks”, in The Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM), Boston, Massachussets, August 6–11, 2000.

  10. A. Perrig, R. Canetti, D. Song and D. Tygar, “Efficient and Secure Source Authentication for Multicast”, in Network and Distributed System Security Symposium (NDSS), San Diego, California, February 8–9, 2001.

  11. Y.-C. Hu, D.B. Johnson and A. Perrig, “SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks”, in The 4th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2002), pp. 3–13, 2002.

  12. F. Stajano and R. Anderson, “The Resurrecting Duckling: Security Issues for Ad hoc Wireless Networks”, in The 7th International Workshop on Security Protocols, 1999.

  13. H. Luo, J. Kong, P. Zerfos, S. Lu and L. Zhang, “Selfsecuring Ad Hoc Wireless Networks”, in IEEE Symposium on Computers and Communications(ISCC),Taorima, Italy, July 1–4, 2002.

  14. J.P. Hubaux, L. Buttyan and S. Capkun, “The Quest for Security in Mobile Ad Hoc Networks”, in Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), Long Beach, CA, USA, 146–155, October 4–5, 2001.

  15. J. Kong, H. Luo, K. Xu, D.L. Gu, M. Gerla and S. Lu, “Adaptive Security for Multi-layer Ad-hoc Networks”, in Wireless Communications and Mobile Computing, Special Issue on Mobile Ad Hoc Networking, 2002.

  16. Y. Zhang and W. Lee, “Intrusion Detection in Wireless Ad-hoc Networks”, in The Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM), Boston, Massachussets, August 6–11, 2000.

  17. S. Buchegger and J.Y.L. Boudec, “Performance Analysis of the CONFIDANT Protocol (Cooperation of Nodes-Fairness in Dynamic Ad-hoc NeTworks)”, in Proceedings of MobiHoc, Lausanne, Switzerland, June 9–11, 2002.

  18. P. Michiardi and R. Molva, “Core: A Collaborative Reputation Mechanism to Enforce Node Cooperation in Mobile Ad Hoc Networks”, in Proceedings of Communications and Multimedia Security pp. 107–121, 2002.

  19. S.J. Lee, and M. Gerla, “Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks”, in ICC pp. 3201–3205, 2001.

  20. M. Marina, and S.R. Das, “On-Demand Multipath Distance Vector Routing in Ad Hoc Networks”, in Proceedings of the 9th International Conference on Network Protocols, 2001.

  21. R. Leung, J. Liu, E. Poon, A. Chan, and B. Li, “On-Demand Multipath Routing for Mobile Ad Hoc Networks”, in Proceedings of the 26th International Conference on Local Computer Network, 2001.

  22. K. Wu and J. Harms, “Performance Study of a Multipath Routing Method for Wireless Mobile Ad Hoc Networks”, in Proceedings of the 9th Internation Symposium on Modeling, Analysis and Simulation, 2001.

  23. L. Buttyan, and J.P. Hubaux, “Enforcing Service Availability in Mobile Ad-Hoc WANs”, in Proceedings of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing (MobiHOC), Boston, Massachusetts, August 6–11, 2002.

  24. L. Buttyan, and J.P. Hubaux, “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks”, ACM/Kluwer Mobile Networks and Applications Vol. 8, No.5 2003.

  25. S. Sundaramurthy and E.M. Belding-Royer, “The AD-MIX Protocol for Encouraging Participation in Mobile Ad hoc Networks”, in Proceedings of the International Conference on Network Protocols (ICNP), Atlanta, USA, pp. 156–167, November 4–7, 2003.

  26. V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao, “Cooperation in Wireless Ad Hoc Networks”, in Proceedings of IEEE INFOCOM, 2003.

  27. S. Zhong, Y. Yang, and J. Chen, “Sprite: A Simple, Cheat-proof, Credit-Based System for Mobile Ad Hoc Networks”, in Proceedings of IEEE INFOCOM, 2003.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801, U.S.A.

    Yuan Xue & Klara Nahrstedt

Authors
  1. Yuan Xue
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klara Nahrstedt
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xue, Y., Nahrstedt, K. Providing Fault-Tolerant Ad hoc Routing Service in Adversarial Environments. Wireless Personal Communications 29, 367–388 (2004). https://doi.org/10.1023/B:WIRE.0000047071.75971.cd

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:WIRE.0000047071.75971.cd

Search

Navigation