Browsing by Author "Gal, Avigdor"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Adaptive Pull-Based Data Freshness Policies for Diverse Update Patterns
    (2004-01-29) Bright, Laura; Gal, Avigdor; Raschid, Louiqa
    An important challenge to effective data delivery in wide area environments is maintaining the data freshness of objects using solutions that can scale to a large number of clients without incurring significant server overhead. Policies for maintaining data freshness are traditionally either push-based or pull-based. Push-based policies involve pushing data updates by servers; they may not scale to a large number of clients. Pull-based policies require clients to contact servers to check for updates; their effectiveness is limited by the difficulty of predicting updates. Models to predict updates generally rely on some knowledge of past updates. Their accuracy of prediction may vary and determining the most appropriate model is non-trivial. In this paper, we present an adaptive pull-based solution to this challenge. We first present several techniques that use update history to estimate the freshness of cached objects, and identify update patterns for which each technique is most effective. We then introduce adaptive policies that can (automatically) choose a policy for an object based on its observed update patterns. Our proposed policies improve the freshness of cached data and reduce costly contacts with remote servers without incurring the large server overhead of push-based policies, and can scale to a large number of clients. Using trace data from a data-intensive website as well as two email logs, we show that our adaptive policies can adapt to diverse update patterns and provide significant improvement compared to a single policy. (UMIACS-TR-2004-01)
  • Thumbnail Image
    Item
    Adaptive Pull-Based Policies for Wide Area Data Delivery
    (2005-10-19T16:15:35Z) Bright, Laura; Gal, Avigdor; Raschid, Louiqa
    Wide area data delivery requires timely propagation of up-to-date information to thousands of clients over a wide area network. Applications include web caching, RSS source monitoring, and email access via a mobile network. Data sources vary widely in their update patterns and may experience different update rates at different times or unexpected changes to update patterns. Traditional data delivery solutions are either push-based, which requires servers to push updates to clients, or pull-based, which require clients to check for updates at servers. While push-based solutions ensure timely data delivery, they are not always feasible to implement and may not scale to a large number of clients. In this paper we present adaptive pull-based policies that can reduce the overhead of contacting remote servers compared to existing pull-based policies. We model updates to data sources using update histories, and present novel history-based policies to estimate when updates occur. We present a set of architectures to enable rapid deployment of the proposed policies. We develop adaptive policies to handle changes in update patterns, and present two examples of such policies. Extensive experimental evaluation using three data traces from diverse applications shows that history-based policies can reduce contact between clients and servers by up to 60% compared to existing pull-based policies while providing a comparable level of data freshness. Our adaptive policies are further shown to dominate individual history based policies.
  • Thumbnail Image
    Item
    A Dual Framework and Algorithms for Targeted Data Delivery
    (2005-11-03T15:18:56Z) Roitman, Haggai; Raschid, Louiqa; Gal, Avigdor; Bright, Laura
    A variety of emerging wide area applications challenge existing techniques for data delivery to users and applications accessing data from multiple autonomous servers. In this paper, we develop a framework for comparing pull based solutions and present dual optimization approaches. Informally, the first approach maximizes user utility of profiles while satisfying constraints on the usage of system resources. The second approach satisfies the utility of user profiles while minimizing the usage of system resources. We present a static optimal solution (SUP) for the latter approach and formally identify sufficient conditions for SUP to be optimal for both. A shortcoming of static solutions to pull-based delivery is that they cannot adapt to the dynamic behavior of Web source updates. Therefore, we present an adaptive algorithm (fbSUP) and show how it can incorporate feedback to improve user utility with only a moderate increase in probing. Using real and synthetic data traces, we analyze the behavior of SUP and fbSUP under various update models.