We compare exact and approximate performance evaluation methods of the Least Recently Used (LRU) caching strategy, which is widely applied in local caches and in distributed web cache architectures in core and edge networks. Based on the independent reference model (IRM), the LRU startup behaviour and convergence time (CT) is derived. The result is related to hit ratio approximations by Fagin and Che et al. We evaluate the precision of the approximations by identifying maximum errors, which are shown to decrease with the cache size. For different object sizes, we extend the analytical LRU hit ratio formula, which is tractable for small caches. The Che and CT approximations are subject to larger deviations for high variability of the object sizes and small caches due to partially unused cache space. We propose an estimation scheme for the fraction of unused LRU cache space, which is shown to improve the accuracy.

We compare web caching strategies based on the least recently used (LRU) and the least frequently used (LFU) replacement principles with optimum caching according to Belady's algorithm. The achievable hit rates of the strategies are shown to improve with the exploited knowledge about the request pattern while the computation effort is also increasing. The results give an overview of performance tradeoffs in the whole relevant range for web caching with Zipf request pattern. In a second part, we study a combined approach of the optimum strategy for a limited look-ahead with LRU, LFU or other non-predictive methods. We evaluate the hit rate gain depending on the extent of the look-ahead for request traces and for the independent reference model (IRM) via simulation and derive an analytic confirmation of the observed behaviour. It is shown that caching for video streaming can benefit from the proposed look-ahead technique, when replacement decisions can be partly revised due to new requests being encountered during long lasting content updates.

Wikipedia is one of the most popular information platforms on the Internet. The user access pattern to Wikipedia pages depends on their relevance in the current worldwide social discourse. We use publically available statistics about the top-1000 most popular pages on each day to estimate the efficiency of caches for support of the platform. While the data volumes are moderate, the main goal of Wikipedia caches is to reduce access times for page views and edits. We study the impact of most popular pages on the achievable cache hit rate in comparison to Zipf request distributions and we include daily dynamics in popularity.

Two-state Markov models are applied in many performance evaluation studies as a simple form of autocorrelated processes, starting with Gilbert-Elliott channels for the analysis of transmission protocols subject to error bursts. We derive an explicit formula for the 2nd order statistics of 2state semi-Markov processes in order to adapt them to correlated traffic and error processes. State and transition specific distribution functions are included in a general representation covering the special cases being usually studied in the literature. The results reveal the influence of model parameters on short and long term dependency and give rise to a straightforward procedure for parameter adaption. In general, 2-state models provide a 2-dimensional fitting space, whereas special 2-state cases often have only one parameter left to fit the shape of the 2nd order statistics. In our evaluation of IP packet measurements on aggregation links we experienced that adaptations by general 2state Markov models achieve a much closer fit to the traffic variability in different time scales than self-similar processes.

Real-time Internet services are gaining in popularity due to rapid provisioning of broadband access technologies. Delivery of high quality of experience (QoE) is important for consumer acceptance of multimedia applications. IP packet level errors affect QoE and the resulting quality degradations have to be taken into account in network operation. We derive the second order statistics of the number of packet losses in finite Markov models over several relevant time scales and adapt them to loss processes visible in wired and wireless transmission channels. Higher order Markov chains offer a large set of parameters to be exploited by complex fitting procedures. We experience that the 2-state Gilbert-Elliott model already captures a wide range of observed loss pattern appropriately and discuss how such models can be used to examine the quality degradations caused by packet losses.

Peer-to-peer (P2P) networks have introduced a distributed communication paradigm, which is useful for many communication services and still accounts for a considerable fraction of the Internet traffic. We discuss the efficiency of P2P content distribution as compared to alternative content delivery overlays.

We investigate a selection of usual approaches to determining the bandwidth demand for IP backbone links with regard to the traffic pattern in the environment of IP platforms of large Internet providers. A comparison of dimensioning methods is based on traffic characterization providing the relevant parameters for the considered methods. TCP transmissions are modeled by distinguishing 3 phases at different source rates as observed by monitoring the TCP throughput when the access speed of the TCP client is the bottleneck on the transmission path. On-off versus 3-state source models are compared for varying traffic correlation in time ranging from self-similarity to Markovian and bufferless modeling. The evaluation of bandwidth requirements assumes statistical multiplexing to be applicable for a large user population.

Non-renewal traffic appears in various shapes as the input to nodes in ATM networks. Adequate models of traffic types are required to analyze the performance of ATM switches. Among them are approaches assuming self-similarity, TES processes or semi-Markovian processes (SMP). We study approximate representations of traffic by semi-Markovian processes, which include autocorrelated arrival intervals depending on the states of an underlying Markov chain. The properties of the SMP autocorrelation function are derived, which are helpful to construct SMP adaptations. ATM switches with SMP input are analyzed using efficient algorithms for the discrete time SMP/G/1 queue. The method is applied to evaluate the performance of an ATM multiplexer with traffic superposed from a number of on-off sources.