A dynamic scheduler for the infinite air-cache

摘要

In a wireless environment, data objects can be delivered to clients with powerful palmtops in two modes: the broadcasting mode and the on-demand mode. By varying the number of data objects to be broadcast, we can arrive at different scheduling algorithms. Existing work has largely focused on exclusive broadcasting and exclusive on-demand scheduling. In the former, all the data objects are broadcast periodically, while the latter approach provides all data objects on demand. A hybrid approach that partitions air-time between broadcasting popular data objects continuously and providing less frequently accessed data upon request has also been proposed recently. However, none of these techniques performs well in all cases since access to data objects is unpredictable in a highly mobile environment. One of these unpredictable factors is the number of clients. When the number of clients is very large, exclusive broadcasting is the most effective way. On the other hand, when the number of clients is very small, then providing the data objects on demand is superior. Finally, the hybrid strategy turns out to perform well under moderate load provided the appropriate number of data objects is broadcast. In this paper, we propose a dynamic scheduler that is robust to the workload (number of clients). As the workload increases, the scheduler pushes more objects into the air, and as the workload decreases, it pulls objects from the air. We present heuristics for pushing objects into and pulling objects from the air. A simulation study is conducted, and we report on the results in this paper. The results demonstrate the effectiveness and necessity of the dynamic scheduler.