Splitting schedules for Internet broadcast communication

Abstract

The broadcast disk provides an effective way to transmit information from a server to many clients. Work has been done to schedule the broadcast of information in a way that minimizes the expected waiting time of the clients. Much of this work has treated the information as indivisible blocks. We look at splitting items into smaller pieces that need not be broadcast consecutively. This allows us to have better schedules with lower expected waiting times. We look at the case of two items of the same length, each split into two halves, and show how to achieve optimal performance. We prove the surprising result that there are only two possible types of optimal cyclic schedules for items 1, and 2. These start with 1122 and 122122. For example, with demand probabilities p1= 0.08 and p2= 0.92, the best order to use in broadcasting the halves of items 1 and 2 is a cyclic schedule with cycle 122122222. We also look at items of different lengths and show that much of the analysis remains the same, resulting in a similar set of optimal schedules.

Files

Additional details