Locating cache proxies in manets

ABSTRACT

Caching Internet based services is a potentially important application for MANETs, as it can improve mobile users' perceived quality of service, reduce their energy consumption, and lower their air-time costs. This paper considers the problem of locating cache proxies in MANETs using several search techniques. The paper first examines several existing and a few novel search techniques including flooding, constrained flooding, a novel dynamic variation of probabilistic flooding, and BFS. These are superimposed on a Maximal Independent Set (MIS), a Connected Dominating Set (DS), and a novel adaptation of BFS-tree based overlays, where each of these overlays is maintained in a self stabilizing manner. The paper also includes a comparison of the performance of these search techniques and overlays by extensive simulations.

REFERENCES

• 1: M. Abrams, C. R. Standridge, G. Abdulla, S. Williams, and E. A. Fox. Caching proxies: Limitations and potentials. In Proceedings of the 4th International WWW Conference, December 1995.
• 2: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Weakly-Connected Dominating Sets and Sparse Spanners in Wireless Ad Hoc Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.96, May 19-22, 2003
• 3: C. Mic Bowman , Peter B. Danzig , Darren R. Hardy , Udi Manber , Michael F. Schwartz, The Harvest information discovery and access system, Computer Networks and ISDN Systems, v.28 n.1-2, p.119-125, Dec. 1995 [doi>10.1016/0169-7552(95)00098-5]
• 4: Gregory V. Chockler , Danny Dolev , Roy Friedman , Roman Vitenberg, Implementing a caching service a distributed COBRA objects, IFIP/ACM International Conference on Distributed systems platforms, p.1-23, April 03-07, 2000, New York, New York, United States
• 5: T. Clause, P. Jacquet, and A. Laouti. Optimized link state routing protocol. INMIC'01, Pakistan, 2001.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 8: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 9: Roy Friedman, Caching web services in mobile ad-hoc networks: opportunities and challenges, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584508]
• 10: Gnutella. Gnutella website. http://gnutella.wego.com.
• 11: T. Herman and S. Tixeuil. A distributed TDMA slot assignement for wireless sensor networks. Technical Report no.1370, LRI, Universite Paris SUD, 2003.
• 12: 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]
• 13: D.B. Johnson and D.A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 14: 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
• 15: M.V. Marathe, H. Breu, H.B. Hund III, S.S. Ravi, and D.J. Rosenkrantz. Simple heuristics for unit disck graphs. Networks, 25:59--68, 1995.
• 16: Jean-Marc Menaud , Valérie Issarny , Michel Banâtre, A Scalable and Efficient Cooperative System for Web Caches, IEEE Concurrency, v.8 n.3, p.56-62, July 2000 [doi>10.1109/4434.865894]
• 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: Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 19: W. Peng and X. Lu. An efficient broadcast protocol for mobile adhoc networks. Journal of Science and Technology, 2002.
• 20: C. Perkins. Ad hoc on demand distance vector (AODV) routing. Internet Draft, draft-ietf-manet-aodv-00.txt, citeseer.nj.nec.com/article/perkins99ad.html, 1997.
• 21: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 22: Romit RoyChoudhury , S. Bandyopadhyay , Krishna Paul, A distributed mechanism for topology discovery in ad hoc wireless networks using mobile agents, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 23: Françoise Sailhan , Valérie Issarny, Cooperative Caching in Ad Hoc Networks, Proceedings of the 4th International Conference on Mobile Data Management, p.13-28, January 21-24, 2003
• 24: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 25: Y. Tseng, S. Ni, and E. Shih. Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad-hoc network. IEEE Transactions on Computers, 52(5):545--557, 2003.
• 26: V. Valloppillil and K.W. Ross. Cache array routing protocol, internet draft. http://ircache.nlanr.net/Cache/ICP/carp.txt, 1998.
• 27: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]
• 28: Jie Wu , Ming Gao , Ivan Stojmenovic, On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.346-356, September 03-07, 2001
• 29: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 30: Philip S. Yu , Edward A. MacNair, Performance study of a collaborative method for hierarchical caching in proxy servers, Proceedings of the seventh international conference on World Wide Web 7, p.215-224, April 1998, Brisbane, Australia
• 31: Haas Z. A new routing protocol for the reconfigurable wireless networks. ICUP'97, 1997.
• 32: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Measurement, Performance

Keywords:
MANET, cache proxy, distributed lookup