Jeffrey K. MacKie-Mason

The Case for Market-based Push Caching (Download full paper)

MacKie-Mason, Jeffrey K. Chan, Yee Man Womer, Jonathan Jamin, Sugih

Published on: November, 1999

Variable QoS from Shared Web Caches: User-Centered Design and Value-Sensitive Replacement (Download full paper)

Terence P. Kelly, Sugih Jamin and Jeffrey K. MacKie-Mason

Published on: June, 1999

Abstract: Due to differences in server capacity, external bandwidth and client demand, some Web servers value cache hits more than others. Assuming that a shared cache knows the extent to which different servers value hits, it may employ a value-sensitive replacement policy in order to generate maximum aggregate value for servers. we consider both the prediction and value aspects of this problem and introduce a novel value-sensitive LFU/LRU hybrid which biases the allocation of cache space toward documents whose origin servers value caching most highly. We compare our algorithm with others from the Web caching literature and discuss from an economic standpoint the problems associated with obtaining servers' private valuation information.

Biased Replacement Policies for Web Caches: Differential Quality-of-Service and Aggregate User Value (Download full paper)

MacKie-Mason, Jeffrey K. Kelly, Terence P. Chan, Yee Man Jamin, Sugih

Published on: January, 1999

Abstract: Disk space in shared Web caches can be diverted to serve some system users at the expense of others. Cache hits reduce server loads, and if servers desire load reduction to different degrees, a replacement policy which prioritizes cache space across servers can provide differential quality-of-service (QoS). We present a simple generalization of least-frequently-used (LFU) replacement that is sensitive to varying levels of server valuation for cache hits. Through trace-driven simulation we show that under a particular assumption about server valuations our algorithm delivers a reasonable QoS relationship: higher byte hit rates for servers that value hits more. We furthermore adopt the economic perspective that value received by system users is a more appropriate performance metric than hit rate or byte hit rate, and demonstrate that our algorithm delivers higher "social welfare" (aggregate value to servers) than LRU or LFU.

One Size Doesn't Fit All: Improving Network QoS Through Preference-driven Web Caching (Download full paper)

Chan, Yee Man, Jonathan Womer, Jeffrey K. MacKie-Mason and Sugih Jamin

Abstract: In order to combat Internet congestion Web caches use replacement policies that attempt to keep the objects in a cache that are most likely to get requested in the future. We adopt the economic perspective that the objects with the greatest value to the users should be in a cache. Using trace driven simulations we implement an incentive compatible market-based Web cache for servers to push content into a cache. This system decentralizes the caching process as servers provide information in the form of bids for space in the cache. Truthful information from the server on valuations of objects and predictions of hit rates is obtained. This information is used in filling the cache, which can provide increased aggregate value and differential quality of service to servers when compared to LFU and LRU.

A Smart Market for Resource Reservation in a Multiple Quality of Service Information Network (Download full paper)

MacKie-Mason, Jeffrey K.

Abstract: The technology is nearly available to offer remarkably powerful new communications services: multiple streams, from multiple users, composed of different applications that require different qualities of service (QoS), all travelling over a single interconnected physical infrastructure. Society will benefit from integrated applications (video conferencing with interactive demos and shared whiteboards; computer-integrated telephony, etc.). However, we are a long way from from free, broadband, "anytime, anywhere" integrated services networks. Allocation of scarce resources in a multiple quality of service network may be the single greatest barrier to communications anytime, anywhere. In this paper I present a fairly general model of the problem, and, after showing that a decentralized open market will fail, I propose a "smart market" mechanism for solving the problem. The smart market implements simultaneously efficient routing and bandwidth allocation for reservations made in advance. As computing speed improves, the length of the advance reservation interval can be shortened.

A Market-Based Approach to Optimal Resource Allocation in Integrated-Services connection-Oriented Networks (Download full paper)

Panagiotis Thomas, Demosthenis Teneketzis and Jeffrey K. MacKie-Mason

Abstract: We present an approach to the admission control and resource allocation problem in connection-oriented networks that offer multiple services to users. Users' preferences are summarized by means of their utility functions, and each user is allowed to request more than one type of service. Multiple types of resources are allocated at each link along the path of a connection. We assume that the relation between Quality of Service (QoS) and resource allocation is given, and we incorporate it as a constraint into a static optimization problem. The objective of the optimization problem is to determine the amount and, required resources for each type of service to maximize the sum of the users' utilities. We prove the existence of a solution of the optimization problem, and describe a competitive market economy that implements the solution and satisfies the informational constraints imposed by the nature of the decentralized resource allocation problem. The economy consists of four different types of agents: resource providers, service providers, users, and an auctioneer that regulates the prices based on the observed aggregate excess demand. The goods that are sold are: (i) the resources at each link of the network; and (ii) services constructed from these resources and then delivered to users. We specify an iterative procedure that is used by the auctioneer to update the prices, and we show that it leads to an allocation that is arbitrarily close to a solution of the optimization problem in a finite number of iterations.