Manycast: exploring the space between anycast and multicast in ad hoc networks

ABSTRACT

The characteristics of ad hoc networks naturally encourage the deployment of distributed services. Although current networks implement group communication methods, they do not support the needs of a mobile node that must locate one or more distributed servers. A node should not need detailed knowledge of network topology to choose servers with which it can communicate efficiently.To this end, manycast is a group communication scheme that enables communication with an arbitrary (user specified) number of group members. Anycast and multicast communication are special cases of manycast in which the target number of group members is one and infinity, respectively. We present manycast and discuss its use as a communication primitive, with specific attention to ad hoc networks. We advocate manycast support at the network layer. A manycast routing protocol enables an application to contact several nearby network nodes that implement a distributed service.We analyze some approaches to manycast, including some application layer implementations. This evaluation supports our claim that manycast must be implemented in the network layer for effective operation in ad hoc networks. We present several extensions to ad hoc routing protocols that can provide manycast support with minimal implementation effort. Through analysis and extensive simulation, we explore the behavior of these approaches to manycast, finally providing recommendations to implementors.

REFERENCES

• 1: R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms, and O. Paridaens. Explicit multicast (Xcast) basic specification. Internet Draft (Work in Progress) draft-ooms-xcast-basic-spec-04.txt, Internet Engineering Task Force, January 2003.
• 2: C. Carter, S. Yi, and R. Kravets. ARP considered harmful: Manycast transactions in ad hoc networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2003.
• 3: I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. Lecture Notes in Computer Science, 2009:46+, 2001.
• 4: S. Deering. Host extensions for IP multicasting. Request for Comments (Standard) RFC 1112, Internet Engineering Task Force, August 1989.
• 5: Gnutella peer-to-peer file sharing system. http://www.gnutella.com.
• 6: Christopher Ho , Katia Obraczka , Gene Tsudik , Kumar Viswanath, Flooding for reliable multicast in multi-hop ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.64-71, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313291]
• 7: Jorjeta G. Jetcheva , David B. Johnson, Adaptive demand-driven multicast routing in multi-hop wireless ad hoc 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/501422.501423]
• 8: L. Ji and M. S. Corson. Differential destination multicast--a MANET multicast routing protocol for small groups. In Proceedings of IEEE INFOCOM, April 2001.
• 9: D. B. Johnson, D. A. Maltz, and Y.-C. Hu. The dynamic source routing protocol for mobile ad hoc networks (DSR). Internet Draft (Work in Progress) draft-ietf-manet-dsr-08.txt, Internet Engineering Task Force, February 2003.
• 10: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 11: U. C. Kozat and L. Tassiulas. Network layer support for service discovery in mobile ad hoc networks. In Proceedings of IEEE INFOCOM 03, 2003.
• 12: D. L. Mills. Automatic NTP configuration options. http://www.eecis.udel.edu/~mills/ntp/html/manyopt.html.
• 13: D. L. Mills. The network time protocol (NTP) distribution. http://www.eecis.udel.edu/~mills/ntp/html/.
• 14: D. L. Mills. Network time protocol (version 3). Request for Comments (Draft Standard) RFC 1305, Internet Engineering Task Force, March 1992.
• 15: P. Mockapetris. Domain names - implementation and specification. Request for Comments (Standard) RFC 1035, Internet Engineering Task Force, November 1987.
• 16: Network simulator 2. http://www.isi.edu/nsnam/ns/.
• 17: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 18: K. Obraczka, G. Tsudik, and K. Viswanath. Pushing the limits of multicast in ad hoc networks. Technical Report 00-735, USC Computer Science Department, June 2000.
• 19: Pushing the Limits of Multicast in Ad Hoc Networks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.719, April 16-19, 2001
• 20: C. Partidge, T. Mendez, and W. Milliken. Host anycasting service. Request for Comments (Informational) RFC 1546, Internet Engineering Task Force, November 1993.
• 21: C. E. Perkins, E. M. Belding-Royer, and S. R. Das. Ad hoc on-demand distance vector (AODV) routing. Internet Draft (Work in Progress) draft-ietf-manet-aodv-13.txt, Internet Engineering Task Force, February 2003.
• 22: J. Postel. Transmission control protocol. Request for Comments (Standard) RFC 793, Internet Engineering Task Force, September 1981.
• 23: Manuel Román , Christopher Hess , Renato Cerqueira , Anand Ranganathan , Roy H. Campbell , Klara Nahrstedt, A Middleware Infrastructure for Active Spaces, IEEE Pervasive Computing, v.1 n.4, p.74-83, October 2002 [doi>10.1109/MPRV.2002.1158281]
• 24: Sun Microsystems. System and Network Administration. March 1990.
• 25: T. Wu, M. Malkin, and D. Boneh. Building intrusion tolerant applications. In Proceedings of the 8th USENIX Security Symposium, 1999.
• 26: S. Yi and R. Kravets. MOCA: Mobile certificate authority for wireless ad hoc networks. In 2nd Annual PKI Research Workshop (PKI03), April 2003.
• 27: L. Zhou and Z. J. Haas. Securing ad hoc networks. IEEE Network Magazine, November 1999.
• 28: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Reliability

Keywords:
ad hoc routing, manycast, service location