Browsing by Author "Liberatore, Vincenzo"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Caching and Scheduling for Broadcast Disk Systems(1998-12-03) Liberatore, VincenzoUnicast connections lead to performance and scalability problems when a large client population attemps to access the same data. Broadcast push and broadcast disk technology address the problem by broadcasting data items from a server to a large number of clients. Broadcast disk performance depends mainly on caching strategies at the client site and on how the broadcast is scheduled at the server site. An on-line broadcast disk paging strategy makes caching decisions without knowing access probabilities. In this paper, we subject on-line paging algorithms to extensive empirical investigation. The Gray algorithm [KL98] always outperformed other on-line strategies on both synthetic and Web traces. Moreover, caching limited the skewness needed from a broadcast schedule, and led to favor efficient caching algorithms over refined scheduling strategies when the cache was not small. Prior to this paper, no work had empirically investigated on-line paging algorithm and their relation with server scheduling. (Also cross-referenced as UMIACS-TR-98-71)Item Data Dissemination on the Web: Speculative and Unobtrusive(1999-05-11) Liberatore, Vincenzo; Davison, Brian D.The Web rapid growth results in heavier loads on servers/network and in increased latency experienced while retrieving Web documents. Internet traffic is further complicated by its burtiness, which complicates the design and allocation of network components. Bursty traffic alternates peak periods with lulls. The paper presents a framework that exploits idle periods in data traffic to satisfy future HTTP requests speculatively, opportunistically, and unobtrusively. Our proposal differs from previous schemes in that it is server-initiated and it is explicitly aware of current traffic loads (unobtrusive). This paper highlights several design trade-offs and details two issues: (1) server arbitration among several candidate documents, and (2) client/proxy caching. We present a theoretical analysis of arbitration, and we propose an integrated caching strategy for both requested and disseminated documents. Our approach is validated by extensive simulation on server logs, and substantial performance improvements are observed over pure on-demand strategies. (Also cross-referenced as UMIACS-TR-99-23)Item Scheduling Jobs Before Shut Down(2000-02-15) Liberatore, VincenzoDistributed systems execute background or alternative jobs while waiting for data or requests to arrive from another processor. In those cases, the following shut-down scheduling problem arises: given a set of jobs of known processing time, schedule them on m machines so as to maximize the total weight of jobs completed before an initially unknown deadline. We will present optimally competitive deterministic and randomized algorithms for shut-down scheduling. Our deterministic algorithm is parameterized by the number of machines m. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice of m. Such family of deterministic algorithm can be translated into a family of randomized algorithms that use progressively less randomization and that are optimal for the given amount of randomization. Hence, we establish a precise trade-off between amount of randomization and competitive ratios. Distributed systems execute background or alternative jobs while waiting for data or requests to arrive from another processor. In those cases, the following shut-down scheduling problem arises: given a set of jobs of known processing time, schedule them on m machines so as to maximize the total weight of jobs completed before an initially unknown deadline. We will present optimally competitive deterministic and randomized algorithms for shut-down scheduling. Our deterministic algorithm is parameterized by the number of machines m. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice of m. Such family of deterministic algorithm can be translated into a family of randomized algorithms that use progressively less randomization and that are optimal for the given amount of randomization. Hence, we establish a precise trade-off between amount of randomization and competitive ratios. (Also cross-referenced as UMIACS-TR-99-72)