Improved Algorithms for Scheduling Data Broadcast
Nitin H. Vaidya, Sohail Hameed · 1996
With the increasing popularity of portable wireless computers, mechanisms to efficiently transmit information to such clients are of significant interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. It has been proposed that in such systems the server should broadcast the information periodically. A broadcast schedule determines what is broadcast by the server and when. In this report, we present an algorithm for scheduling broadcast in such environments. This algorithm is based on a fair queueing algorithm [6], and can be executed in O(log M) time, where M is the number of information items. The algorithm significantly improves the time-complexity over previously proposed broadcast scheduling algorithms. The algorithm also takes transmission errors into account. We evaluate performance of the algorithm and find it to be close to optimal. We also present an algorithm to coordinate broad...