Media streams scheduling for synchronization in distributed multimedia systems

In this paper, we consider the problem of multimedia synchronization based on scheduling the transmission of multimedia documents in a networked envir onment. Assuming channels with different bandwidth and delay characteristic s are established between the multimedia server and the client, we formulat e the scheduling problem to ensure interstream and intrastream synchronizat ion as a parallel processor scheduling problem. Since the heterogeneous par allel processor scheduling problem is NP-hard, we propose two heuristic alg orithms with time complexity of O(n log n + nm), where n is the number of d ata units to be scheduled and m the number of channels available. We also d evelop an enumerative algorithm to obtain the exact solutions. Extensive co mputational simulations reveal that the heuristics consistently obtain near -optimal solutions. From the simulation results, we also identify special s tructures of multimedia documents along with characteristics of the availab le channels which affect the relative performance of the algorithms. (C) 19 99 Academic Press, Inc.