A dynamic hybrid scheduling algorithm for heterogeneous asymmetric environments

摘要

The rapid growth of web services has already given birth to a set of data dissemination applications. Efficient scheduling techniques are necessary to endow such applications with advanced data processing capability, In this paper, we have developed a new hybrid scheduling scheme by effectively combining broadcasting of very popular (push) data and dissemination of less popular (pull) data to develop a new, ideal hybrid scheduling scheme, Our algorithm assumes no prior knowledge of the data access probability, i.e.. which items are being pushed or pulled. Instead, data access probabilities and the cut-off-point to segregate the push and the pull sets are computed dynamically. The data items are assumed to be of variable lengths. The clients send their requests to the server, which ignores the requests for the push items but queues those for the pull items. An ideal behavior of the clients is assumed: a client, after making a request, patiently waits without taking any action. Every client is assumed to have a priority. The priority of a data item is determined by adding the priorities of all the clients requesting that item. At every instant, the item to be broadcast is selected with the help of a pure-push scheduling. On the other hand, the item to be pulled is the one stored in the pull-queue, having the optimal stretch value (max-request min-service time), When more than one data item has the same stretch value, the influence of the priorities of different clients on data dissemination is considered. A suitable modelling technique using the birth-and-death process is developed to analyze the performance of the system. Simulation results corroborate the average system performance and exhibit significant improvement over a pure push and existing hybrid systems in terms of average waiting time spent by a client.