Dynamic scheduling of multimedia documents in a single server multiple clients environment

In a typical single server and multiple client distributed multimedia syste m, clients may send sporadic requests to the server for certain multimedia documents. The requests must be served with a fast response time and with t he required quality of service guarantee. This requires the server to deter mine the transmission schedule of each multimedia stream while ensuring nec essary inter- and intrastream synchronizations. There are two major drawbac ks in the existing scheduling algorithms. First, it is assumed that all cha nnels are available at the beginning of the scheduling, but in reality, req uests arrive when others are in service; second, the cost of the scheduling itself is usually ignored. In general a feasible scheduling algorithm shou ld have the following features: (1) the schedule must be generated in real time, (2) it should have small scheduling cost, and (3) it must be capable of handling multiple requests from multiple clients. In this paper, we prop ose two dynamic scheduling algorithms whose worst time complexity is O(n lo g nm + nm), where n is the total number of data units in a retrieved multim edia document and m denotes the number of available channels. The salient f eature of the proposed algorithms is their inherent dynamic nature which ca n adjust the scheduling times for each individual request according to the slack time between consecutive requests. If the slack time between two requ ests is large, the scheduler can run longer in an attempt to find a better solution. This reduces the response time while maintaining a good quality o f presentation. Through both simulation and analysis, we evaluate our algor ithms and demonstrate their applicability in a realistic environment. (C) 1 999 Academic Press.