A new hybrid broadcast scheduling algorithm for asymmetric communication systems

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 individually. We propose a novel hybrid scheduling algorithm which uses both pull- and push-based schemes. In our approach, data items are divided, by a suitable cut-off point, 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. A cut-off point is said to be optimal when it minimizes the expected access time in the system. The optimal cut-off point is derived analytically and validated by simulation experiments. Results show that the proposed hybrid push- and pull-based scheduling performs always better than a pure push-based scheduling and improves on the expected access time of an existing hybrid scheduling scheme.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Measurement, Theory