Adaptive pull-based policies for wide area data delivery

ABSTRACT

Wide area data delivery requires timely propagation of up-to-date information to thousands of clients over a wide area network. Applications include web caching, RSS source monitoring, and email access via a mobile network. Data sources vary widely in their update patterns and may experience different update rates at different times or unexpected changes to update patterns. Traditional data delivery solutions are either push-based, which requires servers to push updates to clients, or pull-based, which require clients to check for updates at servers. While push-based solutions ensure timely data delivery, they are not always feasible to implement and may not scale to a large number of clients. In this article, we present adaptive pull-based policies that explicitly aim to reduce the overhead of contacting remote servers, compared to existing pull-based policies, while meeting freshness requirements. We model updates to data sources using update histories, and present two novel history-based policies to estimate when updates occur; they are based on individual history and aggregate history. These policies are presented within an architectural framework that supports their deployment either client-side or server-side. We further develop two adaptive policies to handle objects that initially may have insufficient history or objects that experience changes in update patterns. Extensive experimental evaluation using three data traces from diverse applications shows that history-based policies can reduce contact between clients and servers by up to 60% compared to existing pull-based policies while providing a comparable level of data freshness. Our experiments further demonstrate that our adaptive policies can select the best policy to match the behavior of an object and perform better than any individual policy, thus they dominate standalone policies.

REFERENCES

• 1: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• 2: Amiri, K., Tewari, R., Park, S., and Padmanabhan, S. 2002. On space management in a dynamic edge data cache. In Proceedings of the 5th International Workshop on the Web and Databases (WebDB). 37--42.
• 3: Arlitt, M. and Jin, T. 1998. 1998 world cup web site access logs. (Available at http://www.acm.org/sigcomm/ITA/).
• 4: Elena Baralis , Stefano Paraboschi , Ernest Teniente, Materialized Views Selection in a Multidimensional Database, Proceedings of the 23rd International Conference on Very Large Data Bases, p.156-165, August 25-29, 1997
• 5: BlackBerry. 2005. BlackBerry Wireless Handhelds. http://www.blackberry.com.
• 6: Laura Bright , Louiqa Raschid , Bobby Bhattacharjee, Improving data delivery in wide area and mobile environments, 2003
• 7: Laura Bright , Samrat Bhattacharjee , Louiqa Raschid, Supporting diverse mobile applications with client profiles, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570805]
• 8: Bright, L. and Raschid, L. 2002. Using latency-recency profiles for data delivery on the web. In Proceedings of the 28th Conference on Very Large Data Bases (VLDB). 550--561.
• 9: K. Selçuk Candan , Wen-Syan Li , Qiong Luo , Wang-Pin Hsiung , Divyakant Agrawal, Enabling dynamic content caching for database-driven web sites, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.532-543, May 21-24, 2001, Santa Barbara, California, United States
• 10: Carney, D., Lee, S., and Zdonik, S. 2003. Scalable application-aware data freshening. In Proceedings of the 19th International Conference on Data Engineering (ICDE). 481--492.
• 11: Cate, V. 1992. Alex---A global filesystem. In Proceedings of the USENIX File System Workshop. 1--12.
• 12: Challenger, J., Iyengar, A., and Dantzig, P. 1999. A scalable system for consistently caching dynamic web data. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 294--303.
• 13: Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
• 14: Junghoo Cho , Hector Garcia-Molina, Estimating frequency of change, ACM Transactions on Internet Technology (TOIT), v.3 n.3, p.256-290, August 2003 [doi>10.1145/857166.857170]
• 15: Cho, J. and Ntoulas, A. 2002. Effective change detection using sampling. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB). 514--525.
• 16: Cohen, E. and Kaplan, H. 2001. Refreshment policies for web content caches. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 1398--1406.
• 17: Pavan Deolasee , Amol Katkar , Ankur Panchbudhe , Krithi Ramamritham , Prashant Shenoy, Adaptive push-pull: disseminating dynamic web data, Proceedings of the 10th international conference on World Wide Web, p.265-274, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372066]
• 18: Eckstein, J., Gal, A., and Reiner, S. 2005. Optimal information monitoring under a politeness constraint. Tech. Rep. RRR 16-2005, RUTCOR, Rutgers University, Piscataway, NJ.
• 19: Michael J. Franklin , Michael J. Carey , Miron Livny, Transactional client-server cache consistency: alternatives and performance, ACM Transactions on Database Systems (TODS), v.22 n.3, p.315-363, Sept. 1997 [doi>10.1145/261124.261125]
• 20: Michael Franklin , Stan Zdonik, “Data in your face”: push technology in perspective, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.516-519, June 01-04, 1998, Seattle, Washington, United States
• 21: Avigdor Gal , Jonathan Eckstein, Managing periodically updated data in relational databases: a stochastic modeling approach, Journal of the ACM (JACM), v.48 n.6, p.1141-1183, November 2001 [doi>10.1145/504794.504797]
• 22: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• 23: Gwertzman, J. and Seltzer, M. 1996. World wide web cache consistency. In Proceedings of the USENIX Technical Conference. 141--152.
• 24: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 25: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 26: Yixiu Huang , Robert H. Sloan , Ouri Wolfson, Divergence caching in client-server architectures, Proceedings of the third international conference on on Parallel and distributed information systems, p.131-139, October 1994, Autin, Texas, United States
• 27: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 28: Balachander Krishnamurthy , Craig E. Wills, Piggyback server invalidation for proxy cache coherency, Proceedings of the seventh international conference on World Wide Web 7, p.185-193, April 1998, Brisbane, Australia
• 29: Alexandros Labrinidis , Nick Roussopoulos, Update Propagation Strategies for Improving the Quality of Data on the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.391-400, September 11-14, 2001
• 30: Lai, T. and Shan, J. 1999. Efficient recursive algorithms for detection of abrupt changes in signal and control systems. IEEE Trans. Automat. Control 44, 952--964.
• 31: Jeong-Joon Lee , Kyu-Young Whang , Byung Suk Lee , Ji-Woong Chang, An Update-Risk Based Approach to TTL Estimation in Web Caching, Proceedings of the 3rd International Conference on Web Information Systems Engineering, p.21-29, December 12-14, 2002
• 32: C. Liu , P. Cao, Maintaining Strong Cache Consistency in the World-Wide Web, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.12, May 27-30, 1997
• 33: Mason, R., Chou, Y.-M., Sullivan, J., Stoumbos, Z. G., and Young, J. C. 2003. Systematic patterns in T2 charts. J. Qual. Tech. 35, 47--58.
• 34: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 35: Nishina, K. 1992. A comparison of control charts from the viewpoint of change-point estimation. Qual. Reliab. Eng. Internat. 8, 537--541.
• 36: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 37: Chris Olston , Jennifer Widom, Best-effort cache synchronization with source cooperation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564701]
• 38: Pandey, S., Dhamdhere, K., and Olston, C. 2004. WIC: A general purpose algorithm for monitoring web information sources. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 360--371.
• 39: Sandeep Pandey , Krithi Ramamritham , Soumen Chakrabarti, Monitoring the dynamic web to respond to continuous queries, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775245]
• 40: Reynolds, Jr., M. and Stoumbos, Z. 2000. A general approach to modeling CUSUM charts for a proportion. IIE Transactions on Quality and Reliability Engineering 32, 515--535.
• 41: Ross, S. 1995. Stochastic Processes, second ed. Wiley, New York.
• 42: Stoumbos, Z., Jr., M. R., and Woodall, W. 2003. Control chart schemes for monitoring the mean and variance of processes subject to sustained shifts and drifts. The Handbook of Statistics: Statistics in Industry 22. C.R. Rao and R. Khattree (eds.).
• 43: Taylor, H. and Karlin, S. 1994. An Introduction to Stochastic Modeling. Academic Press, Orlando, FL.
• 44: Wessels, D. 1996. Squid internet object cache. http://www.squid-cache.org.
• 45: Emmanuel Yashchin, Estimating the current mean of a process subject to abrupt changes, Technometrics, v.37 n.3, p.311-323, Aug. 1995 [doi>10.2307/1269915]
• 46: Jian Yin , Lorenzo Alvisi , Mike Dahlin , Arun Iyengar, Engineering server-driven consistency for large scale dynamic Web services, Proceedings of the 10th international conference on World Wide Web, p.45-57, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371935]
• 47: Zhu, H. and Yang, T. 2001. Class-based cache management for dynamic web content. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 1215--1224.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

Keywords:
Pull-based, caching, data delivery, update models