Broadcast Disks have been proposed as a means to efficiently deliver data to clients in "asymmetric" environments where the available bandwidth from the server to the clients greatly exceeds the bandwidth in the opposite direction. A previous study investigated the use of cost-based caching to improve performance when clients access the broadcast in a demand-driven manner [AAF95]. Such demand-driven access however, does not fully exploit the dissemination-based nature of the broadcast, which is particularly conducive to clientprefeetching. With a Broadcast Disk, pages continually flow past the clients so that, in contrast to traditional environments, prefetching can be performed without placing additional load on shared resources. We argue for the use of a simple prefetch heuristic called P 7 and show that P 7 balances the cache residency time of a data item with its bandwidth allocation. Because of this tradeoff, P'T is very tolerant of variations in the broadcast program. We describe an implementable approximation for P'T and examine its sensitivity to access probability estimation errors. The results show that the technique is effective even when the probability estimation is substantially different from the actual values. htrQdUCtiQn Many new network-based applications must address the problem of communications asymmerry, in which there is significantly more bandwidth from the server to the client than in the opposite direction. In the presence of such asymmetry, applications must conserve the use of the limited back-channel capability. Communications asymmetry can arise as a property of the hardware. as in cable television networks, or as a property of the application environment, as in Advanced Traffic Information Systems (ATIS) [ShL94] , in which hundreds of thousands of motorists may simultaneously require data from the server. In some extreme cases, such as disconnection in mobile computing environments, there may be no upstream (from clients to servers) communication capacity at all. Broadcast Disks ([AAF95], [AFZ95]) was introduced as a technique for delivering data to clients in asymmetric environments. It is a push-based technique-data transfer from the server to clients is initiated by the server, rather than hy explicit client requests (as in a traditional pull-bawd system). Data items (i.e., pages) are broadcast to the client population optimistically, in anticipation of the need for those items at the clients. The broadcast is repetitive -simulating a rotating storage medium or a disk. In this scheme, groups of pages with different broadcast frequencies are multiplexed on the same channel to create the illusion of multiple disks each spinning at a different speed. The fastest disk is closest to the client in the sense that the expected wait time for a particular page is lowest, while the pages on the slowest disk are farthest since they will, in general, take a longer time to access. A designer has the flexibility to choose the number of disks, the size of each disk, the relative spinning speed of each disk, and the placement of pages across disks. Thus, a designer can create an arbitrarily fine-grained memory hierarchy that is tailored to meet the needs of any particular client population. In [AAF95], we demonstrate how the multi-disk scheme can produce performance improvements over a flat (one-disk) broadcast when the client access pattern is skewed. We also show that performance can be improved further for the multi-disk case if the client uses a cost-based caching policy that is sensitive to the frequency of broadcast as well as the access probability. We propose such a policy (called P Z X ) that chooses as a victim the cached page with lowest value for the quantity p/x where p is the page's access probability and x is its frequency of broadcast. We also present an algorithm, LCZX, that approximates PZX and is easily implementable. In this paper, we explore the use of prefetching to further improve client performance in the broadcast environment. The Broadcast Disks technique is particularly conducive to prefetching because pages are continuously presented to clients via the broadcast, allowing the client to bring some of these pages into its cache in anticipation of future accesses. The dissemination-oriented nature of the environment changes the tradeoffs commonly associated with prefetching in more traditional environments, such as database and file systems. In particular, prefetching in a traditional system places additional load on shared resources (disks, network etc.), which can be potential bottlenecks. In contrast, prefetching from a Broadcast Disk only impacts the local client resources. Thus, the risks in prefetching are significantly lower than in a more traditional system.
In REF , a simple prefetching heuristic, called PT, computes the value of a page by taking the product of the probability (P) of accessing of the page with the time (T) that will elapse before that page appears on the broadcast again.
Prefetching from a broadcast disk
Proceedings of the Twelfth International Conference on Data Engineering
Proceedings of the Twelfth International Conference on Data Engineering
Computer Science