An evaluation of availability latency in carrier-based wehicular ad-hoc networks

ABSTRACT

On-demand delivery of audio and video clips in peer-to-peer vehicular ad-hoc networks is an emerging area of research. Our target environment uses data carriers, termed zebroids, where a mobile device carries a data item on behalf of a server to a client thereby minimizing its availability latency. In this study, we quantify the variation in availability latency with zebroids as a function of a rich set of parameters such as car density, storage per device, repository size, and replacement policies employed by zebroids. Using analysis and extensive simulations, we gain novel insights into the design of carrier-based systems. Significant improvements in latency can be obtained with zebroids at the cost of a minimal overhead. These improvements occur even in scenarios with lower accuracy in the predictions of the car routes. Two particularly surprising findings are: (1) a naive random replacement policy employed by the zebroids shows competitive performance, and (2) latency improvements obtained with a simplified instantiation of zebroids are found to be robust to changes in the popularity distribution of the data items.

REFERENCES

• 1: Federal Highway Administration. Corridor simulation. Version 5.1, http://www.ops.fhwa.dot.gov/trafficanalysistools/cors im.htm.
• 2: D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. Under preparation.
• 3: A. Bar-Noy, I. Kessler, and M. Sidi. Mobile Users: To Update or Not to Update. In IEEE Infocom, 1994.
• 4: J. Burgess, B. Gallagher, D. Jensen, and B. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networking. In IEEE Infocom, April 2006.
• 5: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: A. Dan , D. M. Dias , R. Mukherjee , D. Sitaram , R. Tewari, Buffering and caching in large-scale video servers, Proceedings of the 40th IEEE Computer Society International Conference, p.217, March 05-09, 1995
• 7: Shahram Ghandeharizade , Shyam Kapadia , Bhaskar Krishnamachari, PAVAN: a policy framework for content availabilty in vehicular ad-hoc networks, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023885]
• 8: Shahram Ghandeharizadeh , Shyam Kapadia , Bhaskar Krishnamachari, Comparison of replication strategies for content availability in C2P2 networks, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071262]
• 9: S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. An Evaluation of Availability Latency in Carrier-based Vehicular Ad-hoc Networks. Technical report, Department of Computer Science, University of Southern California,CENG-2006-1, 2006.
• 10: S. Ghandeharizadeh and B. Krishnamachari. C2p2: A peer-to-peer network for on-demand automobile information services. In Globe. IEEE, 2004.
• 11: T. Hara. Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility. In IEEE Infocom, 2001.
• 12: H. Hayashi, T. Hara, and S. Nishio. A Replica Allocation Method Adapting to Topology Changes in Ad Hoc Networks. In DEXA, 2005.
• 13: P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet. SIGARCH Comput. Archit. News, 2002.
• 14: Alex (Sandy) Pentland , Richard Fletcher , Amir Hasson, DakNet: Rethinking Connectivity in Developing Nations, Computer, v.37 n.1, p.78-83, January 2004 [doi>10.1109/MC.2004.1260729]
• 15: 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
• 16: R. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks. Elsevier Ad Hoc Networks Journal, 1, September 2003.
• 17: T. Spyropoulos, K. Psounis, and C. Raghavendra. Single-Copy Routing in Intermittently Connected Mobile Networks. In SECON, April 2004.
• 18: Andrew S. Tanenbaum, Modern Operating Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 19: A. Vahdat and D. Becker. Epidemic routing for partially-connected ad hoc networks. Technical report, Department of Computer Science, Duke University, 2000.
• 20: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 21: M. Zonoozi and P. Dassanayake. User Mobility Modeling and Characterization of Mobility Pattern. IEEE Journal on Selected Areas in Communications, 15:1239--1252, September 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
AutoMata, Markov model, data carriers, latency, mobility, replacement policy, vehicular networks