A new hybrid broadcast scheduling algorithm for asymmetric communication systems

It is believed that broadcast is an efficient way to transmit data in an asymmetric communication system. Most of the previous work focused on either pnll-based or push-based scheduling. However, for systems with a very large number of data items, none of these schemes is efficient. We propose a novel scheduling algorithm which uses both pull- and ush-based schemes. In our approach,data items are divided into two disjoint sets: one consisting of more-popular items and the other of less-popular items. The items in the former set are broadcast by a push-based schedule, while those in the latter set by a pnll-based schedule. By optimally electing the cut-off point to distinguish these two sets, the new hybrid scheduling algorithm achieves a lower expected access time than other existing schedules.