A new hybrid broadcast scheduling algorithm for asymmetric communication systems: push and pull data based on optimal cut-off point

ABSTRACT

It is believed that broadcast is an efficient way to transmit data in an asymmetric communication system. Most of the previous work focused on either pull-based or push-based scheduling. However, for systems with a very large number of data items, none of these schemes is efficient. We propose a novel scheduling algorithm which uses both pull- and push-based schemes. In our approach, data items are divided into two disjoint sets: one consisting of more-popular items and the other of less-popular items. The items in the former set are broadcast by a push-based schedule, while those in the latter set by a pull-based schedule. By optimally selecting the cut-off point to distinguish these two sets, the new hybrid scheduling algorithm achieves a lower expected access time than other existing schedules.

REFERENCES

• 1: 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
• 2: 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
• 3: 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
• 4: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 5: 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]
• 6: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.1-12, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: Amotz Bar-Noy , Yaron Shilo, Optimal broadcasting of two files over an asymmetric channel, Journal of Parallel and Distributed Computing, v.60 n.4, p.474-493, April 2000 [doi>10.1006/jpdc.1999.1618]
• 8: Jon C. R. Bennett , Hui Zhang, Hierarchical packet fair queueing algorithms, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.143-156, August 28-30, 1996, Palo Alto, California, United States
• 9: Jan Gecsei, The Architecture of Videotex Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1983
• 10: Sohail Hameed , Nitin H. Vaidya, Efficient algorithms for scheduling data broadcast, Wireless Networks, v.5 n.3, p.183-193, May 1999 [doi>10.1023/A:1019194826654]
• 11: 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
• 12: R. Jain , J. Werth, Airdisks and AirRAID: Modeling and scheduling periodic wireless data broadcast, Certer for Discrete Mathematics & Theoretical Computer Science, 1995
• 13: 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
• 14: Chi-Jiun Su , Leandros Tassiulas , Vassilis J. Tsotras, Broadcast scheduling for information distribution, Wireless Networks, v.5 n.2, p.137-147, March 1999 [doi>10.1023/A:1019134607998]
• 15: Chi-Jiun Su , Leandros Tassiulas, Joint broadcast scheduling and user's cache management for efficient information delivery, Wireless Networks, v.6 n.4, p.279-288, July 2000 [doi>10.1023/A:1019102017510]
• 16: Nitin H. Vaidya , Sohail Hameed, Scheduling data broadcast in asymmetric communication environments, Wireless Networks, v.5 n.3, p.171-182, May 1999 [doi>10.1023/A:1019142809816]
• 17: J.W. Wong, "Broadcast delivery", Proceedings of IEEE, pp. 1566-1577, December 1988.
• 18: Jeffrey Xu Yu , Toshio Sakata , Kian-Lee Tan, Statistical estimation of access frequencies in data broadcasting environments, Wireless Networks, v.6 n.2, p.89-98, 1999 [doi>10.1023/A:1019117026171]

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling
  I.6 SIMULATION AND MODELING

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

Keywords:
asymmetric communication systems, broadcast scheduling, cut-off point, hybrid algorithm, pull-based scheduling, push-based scheduling