Balancing push and pull for data broadcast

ABSTRACT

The increasing ability to interconnect computers through internet-working, wireless networks, high-bandwidth satellite, and cable networks has spawned a new class of information-centered applications based on data dissemination. These applications employ broadcast to deliver data to very large client populations. We have proposed the Broadcast Disks paradigm [Zdon94, Acha95b] for organizing the contents of a data broadcast program and for managing client resources in response to such a program. Our previous work on Broadcast Disks focused exclusively on the “push-based” approach, where data is sent out on the broadcast channel according to a periodic schedule, in anticipation of client requests. In this paper, we study how to augment the push-only model with a “pull-based” approach of using a backchannel to allow clients to send explicit requests for data to the server. We analyze the scalability and performance of a broadcast-based system that integrates push and pull and study the impact of this integration on both the steady state and warm-up performance of clients. Our results show that a client backchannel can provide significant performance improvement in the broadcast environment, but that unconstrained use of the backchannel can result in scalability problems due to server saturation. We propose and investigate a set of three techniques that can delay the onset of saturation and thus, enhance the performance and scalability of the system.

REFERENCES

• Acha95a: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• Acha95b: S. Acharya, M. Franklin, S. Zdonik, "Dissemination-based Data Delivery Using Broadcast Disks", IEEE Personal Communications, 2(6), December, 1995.
• Acha96a: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Prefetching from Broadcast Disks, Proceedings of the Twelfth International Conference on Data Engineering, p.276-285, February 26-March 01, 1996
• Acha96b: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• Amma85: M. Ammar, J. Wong, "The Design of Teletext Broadcast Cycles", Perf. Evaluation, 5 (1985).
• Best96: A. Bestavros, C. Cunha, "Server-initiated Document Dissemination for the WWW", IEEE Data Engineering Bulletin, 19(3), September, 1996.
• Bowe92: T. F. Bowen , G. Gopal , G. Herman , T. Hickey , K. C. Lee , W. H. Mansfield , J. Raitz , A. Weinrib, The Datacycle architecture, Communications of the ACM, v.35 n.12, p.71-81, Dec. 1992 [doi>10.1145/138859.138868]
• Dao96: S. Dao, B. Perry, "Information Dissemination in Hybrid Satellite/Terrestrial Networks", IEEE Data Engineering Bulletin, 19(3), September, 1996.
• Dire96: Hughes Network Systems, DirecPC Home Page, http://www.direcpc, com/, Oe~, 1996.
• Erik94: Hans Eriksson, MBONE: the multicast backbone, Communications of the ACM, v.37 n.8, p.54-60, Aug. 1994 [doi>10.1145/179606.179627]
• Fran96: M. Franklin, S. Zdonik, "Dissemination-Based Information Systems", IEEE Data Engineering Bulletin, 19(3), September, 1996.
• Giff90: David K. Gifford, Polychannel systems for mass digital communications, Communications of the ACM, v.33 n.2, p.141-151, Feb. 1990 [doi>10.1145/75577.75580]
• Glan96: D. Glance, "Multicast Support for Data Dissemination in OrbixTalk", IEEE Data Engineering Bulletin, 19(3), September, 1996.
• Herm87: Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States
• Imie94a: Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994 [doi>10.1145/194313.194317]
• Imie94b: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• Imie94c: T. Imielinski, S. Viswanathan, "Adaptive Wireless Information Systems", Proc. of SIGDBS Conf., Tokyo, October, 1994.
• Knut81: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Oki93: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• Schw86: Herb Schwetman, CSIM: a C-based process-oriented simulation language, Proceedings of the 18th conference on Winter simulation, p.387-396, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318464]
• Shek96: S. Shekhar, A. Fetterer, D. Liu, "Genesis: Aa Approach to Data Dissemination in Advanced Traveller Information Systems", IEEE Data Engineering Bulletin, 19(3), September, 1996.
• Wong88: J. Wong, "Broadcast Delivery", Proceedings of the IEEE, 76(12), December, 1988.
• Vish94: Subramaniyam R. Viswanathan, Publishing in wireless and wireline environments, Rutgers University, New Brunswick, NJ, 1996
• Yan95: T. "fan, H. Garcia-Molina, "SIFT- A Tool for Wide-area Information Dissemination", Proc. 1995 USENIX Technical Conference, 1995.
• Zdon94: S. Zdonik, M. Franklin, R. Alonso, S. Acharya, "Are 'Disks in the Air' Just Pie in the Sky?", IEEE Workshop on Mobile Computing Systems and Applications, Santa Cruz, CA, December, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Performance and usage measurement

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory