Optimal broadcasting of two files over an asymmetric channel

We study the problem of scheduling files over a broadcast channel in an asymmetric environment. The goal is to minimize the mean response time for clients who access the broadcast channel. Asymmetric channels gained a lot of attention since they are used to model wireless communication, Teletext systems, and Web caching in satellite systems. This paper addresses the 2-files case. We design a simple algorithm that defines the optimal schedule given the demand probability for each file. The solution is extended to include two other important factors: dependencies between files and variable-length files. Adding dependencies is important in particular in the Web caching environment since clients may wish to access more than one file in the broadcast channel. For these extensions, we prove the surprising result that there exists a simple optimal schedule. Such a schedule is composed of a repeated pattern of AA...AB where A is the more “popular” file and B is the less “popular” file