Optimal Broadcasting of Two Files over an Asymmetric Channel

ISSN： 0743-7315

Source： Journal of Parallel and Distributed Computing, Vol.60, Iss.4, 2000-04, pp. : 474-493

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

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 have gained a lot of attention because they are used to model wireless ccxnmunication, teletext systems, and web caching in satellite systems. This paper addresses the two-files case. We design a simple algorithm that defines the optimal schedule given the demand probability for each file. Our solution is extended to include other important factors, such as dependencies between files, variable-length files, and other extensions, such as different priorities for the clients. For all the above 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. Copyright 2000 Academic Press.