CaltechAUTHORS
  A Caltech Library Service

Splitting schedules for Internet broadcast communication

Foltz, Kevin and Bruck, Jehoshua (2002) Splitting schedules for Internet broadcast communication. IEEE Transactions on Information Theory, 48 (2). pp. 345-358. ISSN 0018-9448. https://resolver.caltech.edu/CaltechAUTHORS:FOLieeetit02

[img]
Preview
PDF
See Usage Policy.

547Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:FOLieeetit02

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.


Item Type:Article
Additional Information:“©2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.” Manuscript received July 25, 2000; revised September 18, 2001. Communicated by T. E. Fuja, Associate Editor At-Large.
Subject Keywords:Asymmetric communication, broadcast disk, mobile computing, scheduling, splitting, wireless
Issue or Number:2
Record Number:CaltechAUTHORS:FOLieeetit02
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:FOLieeetit02
Alternative URL:http://dx.doi.org/10.1109/18.978728
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1178
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:02 Jan 2006
Last Modified:02 Oct 2019 22:40

Repository Staff Only: item control page