On-line balanced k-channel data allocation with hybrid schedule per channel Navrati Saxena and M. Cristina Pinottti   View Paper (PDF)   Return to Session 8. Dissemination of data and context Abstract Broadcast is an efficient and scalable technique for disseminating data over wireless channels to an arbitrary large number of clients. The prime objective of broadcast schedules, both on-line and off-line, is to minimize the average amount of time a client needs to wait before receiving its desired item. In off-line schedules, it is assumed that both the entire set of data items and the demand probability for each data is known in advance. Such schedules are guaranteed to obtain the minimum average waiting time only when a skewed partition of the data among multiple-channels and flat schedules per channel are assumed. On the contrary, the on-line broadcast schedules decide which item to transmit without any a-priori knowledge of either the entire set of data or the data demand probabilities. Although no optimal solutions are known for the latter schedules, the volatility of the set of data items to be transmitted makes on-line schedules much more desirable than its off-line counterparts. In this paper, a new on-line broadcast schedule for broadcast over multiple channels is presented. The strategy partitions the data among the broadcast channels in a balanced way, and adopts a hybrid push-pull broadcast schedule per channel. Simulation experiments point out that the results of our new algorithm outperforms the minimum average waiting time achieved by the optimal off-line schedule (skewed partition of data among channels and flat schedule for channel), and the on-line broadcast schedule based on the square root rule. ©2006 Association for Computing Machinery