Enhancing interactive web applications in hybrid networks

ABSTRACT

Mobile Internet users have several options today including high bandwidth cellular data services such as 3G, that may be the choice for many. However, the ubiquity and low cost of WiFi suggests an attractive alternative, namely, opportunistic use of open WiFi access points (APs) or planned municipal mesh networks. Unfortunately, for vehicular users, the intermittent nature of WiFi connectivity makes it challenging to support popular interactive applications such as Web search and browsing.

Our work is driven by two questions. 1) How can we enable system support for interactive web applications to tolerate disruptions in WiFi connectivity from mobile nodes? 2) Can opportunistic mobile-to-mobile (m2m) transfers enhance application performance over only using APs, and if so, under what conditions and by how much?

We present Thedu, a system that enables access to Web search from moving vehicles. The key idea is to use aggressive prefetching to transform the interactive Web search application into a one-shot request/response process. We deployed a prototype of Thedu on the DieselNet testbed in Amherst, MA, consisting of transit buses averaging 21 on the road at a time. Our deployment results show that Thedu can deliver 4 times as many relevant web pages than not using Thedu. A bus receives relevant web pages with a mean delay of 2.3 minutes and within 0.55 minutes in areas with high AP density. Thedu augments AP connectivity with m2m transfers using a utility-driven DTN routing algorithm and uses caching to exploit query locality. Our analytic model and trace-driven simulations suggest that m2m routing yields little benefit over using APs alone even under moderately dense AP deployment such as in Amherst. With sparsely deployed APs as may be the case in rural areas, our conclusions are more mixed: m2m routing with caching improves the number of relevant responses delivered per bus by up to 58%, but the mean delay is significantly high at 6.7 minutes, calling into question its practicality for interactive applications.

REFERENCES

• 1: One Laptop Per Child. http://laptop.org/.
• 2: Text Retrieval Conference (TREC). http://trec.nist.gov.
• 3: UMass DieselNet. http://prisms.cs.umass.edu/dome.
• 4: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 5: Aruna Balasubramanian , Ratul Mahajan , Arun Venkataramani , Brian Neil Levine , John Zahorjan, Interactive wifi connectivity for moving vehicles, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 6: Aruna Balasubramanian , Yun Zhou , W. Bruce Croft , Brian Neil Levine , Aruna Venkataramani, Web search from a bus, Proceedings of the second ACM workshop on Challenged networks, September 14-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1287791.1287803]
• 7: Nilanjan Banerjee , Mark D. Corner , Don Towsley , Brian N. Levine, Relays, base stations, and meshes: enhancing mobile networks with infrastructure, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409955]
• 8: N. Banerjee, M. D. Corner, and B. N. Levine. An Energy-Efficient Architecture for DTN Throwboxes. In Proc. IEEE Infocom, May 2007.
• 9: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 10: J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE Infocom, April 2006.
• 11: Bharat Chandra , Mike Dahlin , Lei Gao , Amjad-Ali Khoja , Amol Nayate , Asim Razzaq , Anil Sewani, Resource management for scalable disconnected access to Web services, Proceedings of the 10th international conference on World Wide Web, p.245-256, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372059]
• 12: Xin Chen , Xiaodong Zhang, A Popularity-Based Prediction Model for Web Prefetching, Computer, v.36 n.3, p.63-70, March 2003 [doi>10.1109/MC.2003.1185219]
• 13: Jakob Eriksson , Hari Balakrishnan , Samuel Madden, Cabernet: vehicular content delivery using WiFi, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409968]
• 14: Fon. http://www.fon.com/.
• 15: D. J. Goodman, J. Borras, N. B. Mandayam, and R. D. Yates. Infostations: A New System for Data and Messaging Siervices. In Proc. Vehicular Technology Conference, pages 969--973, May 1997.
• 16: David Hadaller , Srinivasan Keshav , Tim Brecht , Shubham Agarwal, Vehicular opportunistic communication under the microscope, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247685]
• 17: Bret Hull , Vladimir Bychkovsky , Yang Zhang , Kevin Chen , Michel Goraczko , Allen Miu , Eugene Shih , Hari Balakrishnan , Samuel Madden, CarTel: a distributed mobile sensor computing system, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182821]
• 18: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 19: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 20: Z. Jiang and L. Kleinrock. Web prefetching in a mobile environment. In IEEE Personal Communications, volume 5, pages 25--34, September, 1998.
• 21: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 22: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860449]
• 23: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.213-225, October 13-16, 1991, Pacific Grove, California, United States
• 24: Ming Li , Tingxin Yan , Deepak Ganesan , Eric Lyons , Prashant Shenoy , Arun Venkataramani , Michael Zink, Multi-user data sharing in radar sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322287]
• 25: A. Lindgren, A. Doria, and O. Schelén. Probabilistic routing in intermittently connected networks. In Proc. SAPIR Wrkshp, 2004.
• 26: Ratul Mahajan , John Zahorjan , Brian Zill, Understanding wifi-based connectivity from moving vehicles, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298351]
• 27: R. Manmatha , T. Rath , F. Feng, Modeling score distributions for combining the outputs of search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-275, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384005]
• 28: Mehul Motani , Vikram Srinivasan , Pavan S. Nuggehalli, PeopleNet: engineering a wireless virtual social network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080855]
• 29: J. Ott and D. Kutscher. A Disconnection-Tolerant Transport for Drive-thru Internet Environments. In Proc. IEEE Infocom, March 2005.
• 30: J. Ott and D. Kutscher. Bundling the Web: HTTP over DTN. In Proc. Workshop on Networking in Public Transport, August 2006.
• 31: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]
• 32: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 33: W. T. S. A. Libby Levison. Searching the World Wide Web in Low-Connectivity Communities. In 2002 International Symposium on Technology and Society, June 2002.
• 34: The Sami Network Connectivity Project. http://www.snc.sapmi.net.
• 35: A. Seth , D. Kroeker , M. Zaharia , S. Guo , S. Keshav, Low-cost communication for rural internet kiosks using mechanical backhaul, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161127]
• 36: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 37: T. Strohman, D. Metzler, H. Turtle, and W. B. Croft. Indri: A Language Model-Based Search Engine for Complex Queries. In Proc. Intl. Conf. on Intelligence Analysis, May 2005.
• 38: Y. Xie and D. R. O'Hallaron. Locality in Search Engine Queries and Its Implications for Caching. In Proc. IEEE Infocom, pages 1238--1247, June 2002.
• 39: Xiaolan Zhang , Jim Kurose , Brian Neil Levine , Don Towsley , Honggang Zhang, Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287876]
• 40: Y. Zhou, B. N. Levine, and W. B. Croft. Distributed Information Retrieval For Disruption-Tolerant Mobile Networks. CIIR Technical Report IR-412, University of Massachusetts Amherst, 2005.

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.1 Network Architecture and Design
          Subjects: Store and forward networks

General Terms:
Design, Performance

Keywords:
application, mobile networking, testbed, web search