Optimal Broadcasting of Two Files over an Asymmetric Channel
✍ Scribed by Amotz Bar-Noy; Yaron Shilo
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 180 KB
- Volume
- 60
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
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, variablelength 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.