Scalable dissemination: what's hot and what's not

ABSTRACT

A major problem in web database applications and on the Internet in general is the scalable delivery of data. One proposed solution for this problem is a hybrid system that uses multicast push to scalably deliver the most popular data, and reserves traditional unicast pull for delivery of less popular data. However, such a hybrid scheme introduces a variety of data management problems at the server. In this paper we examine three of these problems: the push popularity problem, the document classification problem, and the bandwidth division problem. The push popularity problem is to estimate the popularity of the documents in the web site. The document classification problem is to determine which documents should be pushed and which documents must be pulled. The band-width division problem is to determine how much of the server bandwidth to devote to pushed documents and how much of the server bandwidth should be reserved for pulled documents. We propose simple and elegant solutions for these problems. We report on experiments with our system that validate our algorithms.

REFERENCES

• 1: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 2: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 3: K. C. Almeroth, M. H. Ammar, and Z. Fei. Scalable delivery of Web pp. using cyclic best-effort (UDP) multicast. In INFOCOM, pp. 1214--1221, 1998.
• 4: Mehmet Altinel , Demet Aksoy , Thomas Baby , Michael Franklin , William Shapiro , Stan Zdonik, DBIS-toolkit: adaptable middleware for large scale data delivery, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.544-546, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Mehmet Altinel , Qiong Luo , Sailesh Krishnamurthy , C. Mohan , Hamid Pirahesh , Bruce G. Lindsay , Honguk Woo , Larry Brown, DBCache: database caching for web application servers, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564765]
• 6: Yossi Azar , Meir Feder , Eyal Lubetzky , Doron Rajwan , Nadav Shulman, The Multicast Bandwidth Advantage in Serving a Web Site, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.88-99, November 07-09, 2001
• 7: P. Chrysanthis, K. Pruhs, and V. Liberatore. Middleware support for multicast-based data dissemination: a working reality. In WORDS, 2003.
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773182]
• 10: Anindya Datta , Kaushik Dutta , Krithi Ramamritham , Helen Thomas , Debra VanderMeer, Dynamic content acceleration: a caching solution to enable scalable dynamic Web page generation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.616, May 21-24, 2001, Santa Barbara, California, United States
• 11: Anindya Datta , Kaushik Dutta , Helen Thomas , Debra VanderMeer , Suresha , Krithi Ramamritham, Proxy-based acceleration of dynamically generated content on the world wide web: an approach and implementation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564703]
• 12: 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
• 13: Yufei Guo , M. Cristina Pinotti , Sajal K. Das, A new hybrid broadcast scheduling algorithm for asymmetric communication systems, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.39-54, July 2001 [doi>10.1145/584051.584055]
• 14: A. Hall and H. Taubig. Comparing push- and pull-based broadcasting or: Would "microsoft watches" profit from a transmitter? LCNS, 2647, January 2003.
• 15: J. Jannotti, D. Gifford, K. Johnson, M. Kaashoek, and J. O'Toole, Jr. Overcast: Reliable multicasting with an overlay network. In OSDI, pp. 197--212, 2000.
• 16: Shudong Jin , Azer Bestavros, Temporal locality in Web request streams (poster session) (extended abstract): sources, characteristics, and caching implications, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.110-111, June 18-21, 2000, Santa Clara, California, United States
• 17: Alexandros Labrinidis , Nick Roussopoulos, WebView materialization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.367-378, May 15-18, 2000, Dallas, Texas, United States
• 18: A. Labrinidis and N. Roussopoulos. Webview balancing performance and data freshness in web database servers. In VLDB, pp. 393--404, 2003.
• 19: Qiong Luo , Sailesh Krishnamurthy , C. Mohan , Hamid Pirahesh , Honguk Woo , Bruce G. Lindsay , Jeffrey F. Naughton, Middle-tier database caching for e-business, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564763]
• 20: Jörg Nonnenmacher , Ernst W. Biersack, Scalable feedback for large groups, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.375-386, June 1999 [doi>10.1109/90.779206]
• 21: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 22: V. S. Pai, L. Wang, K. Park, R. Pang, and L. Peterson. The dark side of the Web: An open proxy's view. In HotNets-II, 2004.
• 23: V. Penkrot, J. Beaver, M. Sharaf, S. Roychowdhury, W. Li, W. Zhang, P. Chrysanthis, K. Pruhs, and V. Liberatore. An optimized multicast-based data dissemination middleware: A demonstration. In ICDE 2003, pp. 761--764, 2003.
• 24: P. Rosenzweig, M. Kadansky, and S. Hanna. The java reliable multicast service: A reliable multicast library. SMLI TR-98-68, Sun Microsystems, 1998.
• 25: Konstantinos Stathatos , Nick Roussopoulos , John S. Baras, Adaptive Data Broadcast in Hybrid Networks, Proceedings of the 23rd International Conference on Very Large Data Bases, p.326-335, August 25-29, 1997
• 26: Peter Triantafillou , R. Harpantidou , M. Paterakis, High performance data broadcasting systems, Mobile Networks and Applications, v.7 n.4, p.279-290, August 2002 [doi>10.1023/A:1015411311496]
• 27: W. Zhang, W. Li, and V. Liberatore. Application-perceived multicast push performance. In IPDPS, 2004.