Weak duplicate address detection in mobile ad hoc networks

ABSTRACT

Auto-configuration is a desirable goal in implementing mobile ad hoc networks. Specifically, automated dynamic assignment (without manual intervention) of IP addresses is desirable. In traditional networks, such dynamic address assignment is often performed using the Dynamic Host Configuration Protocol (DHCP). Implementing DHCP, however, requires access to a DHCP server. In mobile ad hoc networks, it is difficult to guarantee access to a DHCP server, since ad hoc networks can become partitioned due to host mobility. Therefore, alternative mechanisms must be employed. One plausible approach is to allow a node to pick a tentative address randomly (or using some locally available information), and then use a "duplicate address detection" (DAD) procedure to detect duplicate addresses. The previously proposed DAD procedures make use of timeouts and do not always perform correctly in presence of partitions. In networks where message delays cannot be bounded, use of timeouts can lead to unreliability. Therefore, we propose an alternative approach (which can be used in conjunction with previously proposed schemes). We refer to the proposed approach as "weak" duplicate address detection. The goal of weak DAD is to prevent a packet from being routed to the "wrong" destination node, even if two nodes in the network happen to have chosen the same IP address. We also propose an enhanced version of the weak DAD scheme, which removes a potential shortcoming of the weak DAD approach.

REFERENCES

• 1: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 2: J. Boleng, "Efficient network layer addressing for mobile ad hoc networks," Tech. Rep. MCS--00-09, The Colorado School of Mines, 2000.
• 3: S. Cheshire and B. Adoba, "Dynamic configuration of IPv4 link-local addresses," July 2001. Internet Draft (Work in Progress).
• 4: Cisco, "Duplicate MAC addresses on Cisco 3600 series," May 1997. Web page at http://www.cisco.com/warp/public/770/7.html.
• 5: R. Droms, "Dynamic host configuration protocol," March 1997.
• 6: Yih-Chun Hu , David B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.231-242, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345952]
• 7: P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot, and T. Clausen, "Optimized link state routing protocol," March 2001. IETF MANET Internet Draft (work in progress).
• 8: D. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing (T. Imielinski and H. Korth, eds.), Kluwere Academic Publishers, 1996.
• 9: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: James F. Kurose , Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet Package, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 11: Microsoft, "How to troubleshoot duplicate MAC address conflicts," December 2001. Web page at http://support.microsoft.com/support/kb/articles/Q164/9/03.asp.
• 12: S. Nesargi and R. Prakash, "Issues pertaining to service discovery in mobile ad hoc networks," in ACM Workshop on Principles of Mobile Computing, August 2001.
• 13: S. Nesargi and R. Prakash, "MANETconf: Configuration of hosts in a mobile ad hoc network," in INFOCOM, 2002.
• 14: P. Patchipulusu, "Dynamic address allocation protocols for mobile ad hoc networks," M.S. Thesis (advisor: N. H. Vaidya), Computer Science, Texas A&M University, August 2001.
• 15: 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
• 16: C. E. Perkins, E. M. Royer, and S. R. Das, "IP address autoconfiguration for ad hoc networks," July 2000. Internet Draft, IETF Working Group MANET (Work in Progress).
• 17: Curt Schurgers , Gautam Kulkarni , Mani B. Srivastava, Distributed assignment of encoded MAC addresses in sensor networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501463]
• 18: S. Thomson and T. Narten, "IPv6 stateless address autoconfiguration," December 1998.
• 19: N. H. Vaidya, "Weak duplicate address detection in mobile ad hoc networks," tech. rep., University of Illinois at Urbana-Champaign, January 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms

Keywords:
auto-configuration, duplicate address detection, mobile ad hoc networks