Abstract
A hybrid scheduling that effectively combines broadcasting for very popular data (push data) and dissemination upon-request for less popular data (pull data) in asymmetric communication environments is introduced. In this solution, the server continuously broadcasts one push item and disseminates one pull item. The clients send their requests to the server, which queues-up them for the pull items. At any instant of time, the item to be broadcast is designated applying a pure-push scheduling, while the item to be pulled is the one stored in the pull-queue, which has accumulated, so far, the highest number of pending requests. The value of the average expected waiting time spent by a client in the hybrid system is evaluated analytically, and the cut-off point between push and pull items is chosen so that such a waiting time is minimized. It is found out that by doing so the cut off point decreases to a value, which is much less than the total number of items present in the system, improving upon the average waiting time spent by a client in a pure push system and also on that spent in some of the hybrid systems already proposed in literature.
This work has been supported by the MIUR under the “REAL-WINE” research grant and by Computer Networks and Distributed Algorithms, DIT Research grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Acharya, M. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. IEEE Personal Communications, pages 50–60, Dec 1995.
S. Acharya, M. Franklin, and S. Zdonik. Prefetching from a broadcast disk. In Proceedings of 12th International Conference on Data Engineering, pages 276–285, 1996.
S. Acharya, M. Franklin, and S. Zdonik. Balancing push and pull for data broadcast. In Proceedings of ACM SIGMOD Int. Conference on Management of Data, pages 183–193. ACM SIGMOD, 1997.
S. Acharya and S. Muthukrishnan. Scheduling on-demand broadcasts: New metrics and algorithms. In Proceedings of the Fourth Annual ACM/IEEE MobiCom, pages 43–54. ACM MobiCom, 1998.
A. Bar-Noy, B. Patt-Shamir, and I. Ziper. Broadcast disks with polynomial cost functions. In IEEE INFOCOM 2000, pages 575–584, 2000.
D. Barbara and T. Imielinski. Sleepers and workaholics: Caching strategies in mobile environments. In Proceedings of ACM SIGMOD Int. Conference, pages 1–12, 1994.
S. Baruah and A. Bestavros. Pinwheel scheduling for fault-tolerant broadcast disks in real-time database systems. In Proceedings of IEEE International Conference on Data Engineering, 1997.
S. Baruah and A. Bestavros. Real-time mutable broadcast disks. In Proceedings of Second International Workshop on Real-Time Databases, Burlington, VT, 1997.
J. C. R. Bennett and H. Zhang. Hierarchical packet fair queueing algorithms. In Proceedings of ACM SIGCOMM, pages 43–56, 1996.
A. Bestavros. Aida-based real-time fault-tolerant broadcast disks. In Proceeding Second IEEE Real-Time Technology and Applications Symposium, 1996.
J. Gecsei. The architecture of videotex systems. Prentice-Hall, Englewood Cliffs, NJ, 1983.
Y. Guo, S. K. Das, and M. C. Pinotti. A new hybrid broadcast scheduling algorithm for asymmetric communication systems: Push and pull data based on optimal cutoff point. Mobile Computing and Communications Review (MC2R), 5(4), 2001.
S. Hameed and N. H. Vaidya. Efficient algorithms for scheduling data broadcast. Wireless Networks, 5:183–193, 1999.
S. Hameed and N. H. Vaidya. Scheduling data broadcast in asymmetric communication environments. Wireless Networks, 5:171–182, 1999.
R. Jain and J. Werth. Airdisks and airraid: Modeling and scheduling periodic wireless data broadcast (extended abstract). In DIMACS Technical Report 95-11, Rutgers University. DIMACS, 1995.
K. Stathatos, N. Roussopoulos, and J. S. Baras. Adaptive data broadcast in hybrid networks. In Proceedings of 23rd International Conference on Very Large Data Bases, Athens, Greece, pages 326–335, 1997.
J. Xu, Q. Hu, L. Lee, and W. C. Lee. Saiu: An efficient cache replacement policy for wireless on-demand broadcasts. In Private Communication.
J. X. Yu, T. Sakata, and K. Tan. Statistical estimation of access frequencies in data broadcasting environments. Wireless Networks, 6:89–98, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pinotti, C.M., Saxena, N. (2002). Push Less and Pull the Current Highest Demanded Data Item to Decrease the Waiting Time in Asymmetric Communication Environments. In: Das, S.K., Bhattacharya, S. (eds) Distributed Computing. IWDC 2002. Lecture Notes in Computer Science, vol 2571. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36385-8_21
Download citation
DOI: https://doi.org/10.1007/3-540-36385-8_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00355-7
Online ISBN: 978-3-540-36385-9
eBook Packages: Springer Book Archive