The persistent‐access‐caching algorithm

Caching is widely recognized as an effective mechanism for improving the performance of the World Wide Web. One of the key components in engineering the Web caching systems is designing document placement/replacement algorithms for updating the collection of cached documents. The main design objectives of such a policy are the high cache hit ratio, ease of implementation, low complexity and adaptability to the fluctuations in access patterns. These objectives are essentially satisfied by the widely used heuristic called the least‐recently‐used (LRU) cache replacement rule. However, in the context of the independent reference model, the LRU policy can significantly underperform the optimal least‐frequently‐used (LFU) algorithm that, on the other hand, has higher implementation complexity and lower adaptability to changes in access frequencies. To alleviate this problem, we introduce a new LRU‐based rule, termed the persistent‐access‐caching (PAC), which essentially preserves all of the desirable attributes of the LRU scheme. For this new heuristic, under the independent reference model and generalized Zipf's law request probabilities, we prove that, for large cache sizes, its performance is arbitrarily close to the optimal LFU algorithm. Furthermore, this near‐optimality of the PAC algorithm is achieved at the expense of a negligible additional complexity for large cache sizes when compared to the ordinary LRU policy, since the PAC algorithm makes the replacement decisions based on the references collected during the preceding interval of fixed length. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Obtaining the optimal cache document replacement policy for the caching system of an EC website

Adopting a proper cache document replacement policy is critical to the performance of a caching system. Among the existing cache document replacement policies, no one policy can surpass all the other policies in every case. Besides, the most suitable cache document replacement policy for a caching system is often chosen from the existing policies, which cannot guarantee the optimality of the chosen policy. These phenomena motivate us to construct a cache document replacement policy which content can be tailored to the specific requirements of a caching system. In this study, the optimal linear combination (OLC) cache document replacement policy tailored to the requirements of the caching system is to be found out. To evaluate the effectiveness of the proposed methodology, an experimental EC website has been constructed, and the log file of the website server was used as the data source to evaluate the performances of various cache document replacement policies under different cache sizes. In our simulation experiments, the OLC policies outperformed the other traditional policies by increasing the hit rate and the byte hit rate up to 7% and 11%, respectively.     

On the distribution of search cost for the move-to-front rule

A file of records, each with an associated request probability, is dynamically maintained as a serial list. Successive requests are mutually independent. The list is reordered according to the move-to-front (MTF) rule: The requested record is moved to the front of the list. We derive the stationary distribution of search cost (=depth of requested item) by embedding in Poisson processes and derive certain finite-time stochastic ordering results for the MTF chain so embedded. A connection with cache fault probabilities is discussed. We also establish a Schur-concavity result for stationary expected search cost. © 1996 John Wiley & Sons, Inc.     

Managing transshipments in a multi-retailer system with approximate policies

Using the right transshipment policy is important when transshipments are exercised under demand uncertainty. Optimal transshipment policy can be quite complex in a multi-firm system as optimal actions depend on all system variables. Moreover, both how to select requested retailer and how to respond to requests are in question. We introduce simple, close-to-optimal heuristic transshipment policies for multiple retailers. We first show that heuristic policies may perform even better than self-optimal policy, which is explained by Braess’s paradox. Then we test the performances of various heuristics with respect to centrally optimal policy. When retailers can observe others’ inventory levels, more effective transshipments can be made. Otherwise, a random selection performs quite well. We also observe that although always-accept respond policy is quite close to centrally optimal in small systems, the performance of pairwise-optimal holdback levels to respond requests is more clear and consistent for larger systems.     

On the asymptotics of fault probability in least‐recently‐used caching with Zipf‐type request distribution

We consider the least‐recently‐used cache replacement rule with a Zipf‐type page request distribution and investigate an asymptotic property of the fault probability with respect to an increase of cache size. We first derive the asymptotics of the fault probability for the independent‐request model and then extend this derivation to a general dependent‐request model, where our result shows that under some weak assumptions the fault probability is asymptotically invariant with regard to dependence in the page request process. In a previous study, a similar result was derived by applying a Poisson embedding technique, where a continuous‐time proof was given through some assumptions based on a continuous‐time modeling. The Poisson embedding, however, is just a technique used for the proof and the problem is essentially on a discrete‐time basis; thus, it is preferable to make assumptions, if any, directly in the discrete‐time setting. We consider a general dependent‐request model and give a direct discrete‐time proof under different assumptions. A key to the proof is that the numbers of requests for respective pages represent conditionally negatively associated random variables. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Predicting Web Users' Next Access Based on Log Data

This article considers models that describe how people browse the Web. We restrict our attention to navigation patterns within a single site, and base our study on standard Web server access logs. Given a visitor's previous activities on the site, we propose models that predict their next page request. If the prediction is reasonably accurate, we might consider “prefetching” the page before the visitor requests it. A more conservative use for such predictions would be to simply update the freshness records in a proxy or network cache, eliminating unnecessary If-Modified-Since requests. Using data from the Web site for the Computing and Mathematical Sciences Research Division of Lucent Technologies (cm.bell-labs.com) we first evaluate the predictive performance of low-order Markov models. We next consider mixtures of first-order Markov models, achieving a kind of clustering of Web pages in the site. This approach is shown to perform well, while significantly reducing the space required to store the model. Finally, we explore a Bayesian approach using a Dirichlet prior on the collection of links available to a user at each stage in their travels through the site. We show that the posterior probabilities derived under this model are fairly close to the cross-validation estimates of the probability of success.     

SIMULATING COST-EFFECTIVE WETLANDS RESERVES: A COMPARISON OF POSITIVE AND NORMATIVE APPROACHES

A conceptual model of farmer behavior is used to develop analytical expressions for the costs of wetland policies in the United States. An empirical study based on the model compares normative and positive cost estimates for accomplishing a specific policy and shows that these two modeling strategies yield very different cost estimates from the same basic data. Because models such as these are frequently used to support budget requests for government programs, the choice of modeling strategy can influence whether program goals can be accomplished with the funds requested.     

Distributed caching over heterogeneous mobile networks

Sharing content over a mobile network through opportunistic contacts has recently received considerable attention. In proposed scenarios, users store content they download in a local cache and share it with other users they meet, e.g., via Bluetooth or WiFi. The storage capacity of mobile devices is typically limited; therefore, identifying which content a user should store in her cache is a fundamental problem in the operation of any such content distribution system. In this work we propose Psephos, a novel mechanism for determining the caching policy of each mobile user. Psephos is fully distributed: users compute their own policies individually, in the absence of a central authority. Moreover, it is designed for a heterogeneous environment, in which demand for content, access to resources, and mobility characteristics may vary across different users. Most importantly, the caching policies computed by our mechanism are optimal: we show that Psephos maximizes the system’s social welfare. To the best of our knowledge, our work is the first to address caching with heterogeneity in a fully distributed manner.     

A birth–death model for Web cache systems: Numerical solutions and simulation

In this paper, we study Web cache hit rates by introducing a birth–death model. A system consisting of a single Web server with a single cache stores Web pages that are classified as hot pages (popular pages) and cold pages (less popular pages). Given requested probabilities for each class, the stochastic model provides the mean hit rate for a random replacement algorithm and the upper and low bounds for other algorithms. Numerical results from the analysis are validated using the output of simulation programs that utilize the LRU algorithm.     

Dynamic fleet scheduling with uncertain demand and customer flexibility

We develop a dynamic fleet scheduling model that demonstrates how a carrier can improve fleet utilization. The fleet scheduling model presented by Lee et?al. (Eur J Oper Res 218(1):261–269, 2012) minimizes (1) a carrier’s fleet size and (2) the penalty associated with the alternative delivery times selected. The model is static since requests are collected over time and processed together. In this paper we present a stochastic, dynamic version of the fleet reduction model. As demand is revealed throughout an order horizon, decisions are made in stages by sampling anticipated demand to avoid recourse penalties in later stages. Based on computational experiments we find the following:

1. Modeling stochasticity improves the quality of solutions relative to the analogous model that does not include stochasticity. Counter-intuitively, an order lead-time distribution in which most loads are requested early can negatively impact optimal solution costs.
2. The stochastic model produces good results without requiring prohibitively large numbers of demand scenarios.
3. Consignees that place orders early in the order horizon are more often assigned their requested delivery times than those who place orders late.

     

Cache Oblivious Algorithms for the RMQ and the RMSQ Problems

In the Range Minimum/Maximum Query (RMQ) and Range Maximum-Sum Segment Query (RMSQ) problems, we are given an array which we can preprocess in order to answer subsequent queries. In the RMQ query, we are given a range on the array and we need to find the maximum/minimum element within that range. On the other hand, in RMSQ query, we need to return the segment within the given query range that gives the maximum sum. In this paper, we present cache oblivious optimal algorithms for both of the above problems. In particular, for both the problems, we have presented linear time data structures having optimal cache miss. The data structures can answer the corresponding queries in constant time with constant cache miss.     

Optimal access control for broadband services: Stochastic knapsack with advance information

Suppose that call reservation requests of K different types arrive randomly at a single capacitated link where each in turn must be accepted or rejected. Each request requires an amount of bandwidth and a random duration, both depending on its type. An accepted call generates an immediate fixed revenue followed by a variable revenue per unit time. We assume that each call's requested duration is known when it arrives and that the state of the link is constantly monitored. The problem is to find a call acceptance policy that maximizes the long-run average revenue per unit time generated by the accepted calls. We propose and investigate threshold-type control policies that use the known duration of arriving calls as well as the current link status. Two main contributions result. First are interpretable analytical results for the case of K = 1 that can also be applied to the case of K > 1 using complete partitioning scheme. Second, we illustrate how to apply stochastic optimization techniques to compute optimal thresholds in the general case. We also include the results of initial simulation experiments.     

Optimal mapping in direct mapped cache environments

In this paper we study positioning strategies for improving the performance of a memory system with a direct mapped cache. A positioning technique determines for every program item, (instruction or data), its address in main memory.Assuming the Independent Reference Model, we break the general positioning problem into two, the collision minimization and the grouping problems and show optimal algorithms for both problems. Using these algorithms we derive an optimal algorithm for the general positioning problem.Since the optimal positioning is of very special structure we consider other, less restricted, positionings. We show that the quality of a class of natural assignments that distribute the items almost arbitrarily is good as long as the optimal hit ratio is sufficiently large. Another possible requirement is that the items should be distributed as evenly as possible. We find an optimal assignment for the special case of the pair assignment.In addition we look at the expected performance gain of two frequently suggested cache features. The cache bypass feature supports the access of items in memory without loading the item into the cache. We show an assignment with best possible hit ratio. Also it is shown that a cache which employs a random assignment policy, i.e., the assignment of an item is determined randomly, does not improve the expected hit ratio.     

A solution method for a car fleet management problem with maintenance constraints

The problem retained for the ROADEF’99 international challenge was an inventory management problem for a car rental company. It consists in managing a given fleet of cars in order to satisfy requests from customers asking for some type of cars for a given time period. When requests exceed the stock of available cars, the company can either offer better cars than those requested, subcontract some requests to other providers, or buy new cars to enlarge the available stock. Moreover, the cars have to go through a maintenance process at a regular basis, and there is a limited number of workers that are available to perform these maintenances. The problem of satisfying all customer requests at minimum cost is known to be NP-hard. We propose a solution technique that combines two tabu search procedures with algorithms for the shortest path, the graph coloring and the maximum weighted independent set problems. Tests on benchmark instances used for the ROADEF’99 challenge give evidence that the proposed algorithm outperforms all other existing methods (thirteen competitors took part to this contest).     

How to Pack Trees

In a virtual memory system, the address space is partitioned into pages, and the main memory serves as a cache to the disk. In this setting, we address the following problem: Given a tree, find an allocation of its nodes to pages, so-called a packing, which optimizes the cache performance for some access pattern to the tree nodes. We investigate a model for tree access in which a node is accessed only via the path leading to it from the root. Two cost functions are considered: the total number of different pages visited in the search, and the number of page faults incurred. It is shown that both functions can be optimized simultaneously. An efficient dynamic programming algorithm to find an optimal packing is presented. The problem of finding an optimal packing which also uses the minimum number of pages is shown to be NP-complete. However, an efficient approximation algorithm is presented. This algorithm finds a packing that uses the minimum number of pages and requires at most one extra page fault per search. Finally, we study this problem in the context of dynamic trees which allow insertions and deletions.     

Transshipment and rebalancing policies for library books

Library customers can soon order books online and specify a location to collect them from. Libraries exchange books between locations to meet these requests. Two types of exchanges take place: transshipments from library to library to fulfill the requests and rebalancing to redistribute books between libraries. This research determines optimal decisions for transshipments and rebalancing, so that logistic costs in the library system are minimized. In current practice, libraries typically send the book back to the original library after return. We consider a more general policy, in which we rebalance books in anticipation of demand. Moreover, we determine the optimal location from which to transship a book when it is unavailable at the location of demand. By means of stochastic dynamic programming, we derive the optimal policy for small instances. For larger instances we present two heuristics: the cluster and the expected shortage reduction (ESR) heuristic. The ESR heuristic proves to be near-optimal and significantly outperforms current practice.     

High‐performance direct algorithms for computing the sign function of triangular matrices

Algorithms and implementations for computing the sign function of a triangular matrix are fundamental building blocks for computing the sign of arbitrary square real or complex matrices. We present novel recursive and cache‐efficient algorithms that are based on Higham's stabilized specialization of Parlett's substitution algorithm for computing the sign of a triangular matrix. We show that the new recursive algorithms are asymptotically optimal in terms of the number of cache misses that they generate. One algorithm that we present performs more arithmetic than the nonrecursive version, but this allows it to benefit from calling highly optimized matrix multiplication routines; the other performs the same number of operations as the nonrecursive version, suing custom computational kernels instead. We present implementations of both, as well as a cache‐efficient implementation of a block version of Parlett's algorithm. Our experiments demonstrate that the blocked and recursive versions are much faster than the previous algorithms and that the inertia strongly influences their relative performance, as predicted by our analysis.     

Investment decisions in the rent-to-own industry in the absence of inventory

This study addresses the product investment decision faced by firms in the rent-to-own industry. In this setting, a customer arrives according to a random process and requests one unit of a product to rent (and eventually own should he/she choose to make all the required payments). At the time of request, if the product is available in inventory, the firm enters into a contractual agreement (by accepting the customer's offer) and rents the merchandise. More interesting and the case considered here, if the requested item is not in inventory, the firm must decide whether to purchase the item in order to rent it out or to simply reject the request. The customer's offer specifies the desired maximum contract length and the payment frequency—from which the firm determines the fixed periodic payment charged. The firm makes its investment decision based on the characteristics of the offer as well as those of the product (eg, initial and resale values, useful life and carrying costs) in essence performing a complicated cost benefit analysis. An extension is also considered whereby instead of simply rejecting the request the firm can adjust the required payment amount. Dynamic programming techniques are used to address the problem and to solve for the firm's optimal decision.     

Optimal location of dwell points in a single loop AGV system with time restrictions on vehicle availability

Since the workload of a manufacturing system changes over time, the material handling equipment used in the facility will be idle at certain time intervals to avoid system overload. In this context, a relevant control problem in operating an automated guided vehicle (AGV) system is where to locate idle vehicles. These locations, called dwell points, establish the response times for AVG requests. In this article, a dynamic programming algorithm to solve idle vehicle positioning problems in unidirectional single loop systems is developed to minimize the maximum response time considering restrictions on vehicle time available to travel and load/unload requests. This polynomial time algorithm finds optimal dwell points when all requests from a given pick-up station are handled by a single AGV. The proposed algorithm is used to study the change in maximum response time as a function of the number of vehicles in the system.     

Two-stage stochastic problems with correlated normal variables: computational experiences

Two-stage models are frequently used when making decisions under the influence of randomness. The case of normally distributed right hand side vector – with independent or correlated components – is treated here. The expected recourse function is computed by an enhanced Monte Carlo integration technique. Successive regression approximation technique is used for computing the optimal solution of the problem. Computational issues of the algorithm are discussed, improvements are proposed and numerical results are presented for random right hand side and a random matrix in the second stage problems.