We introduce the notion of Temporal Correlations (TC) ordering as a way to compare strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal c correlations in several Web request models, namely, the higher-order Markov chain model (HOMM), the partial Markov chain model (PMM) and the Least-Recently-Used stack model (LRUSM). We also show how the comparison in the TC ordering is compatible with comparisons of some well-known locality of reference metrics, namely, the working set size and the inter-reference time. We establish a folk theorem to the effect that the stronger the temporal correlations, the smaller the miss rate for the PMM. Conjectures and simulations are offered regarding this folk theorem under the HOMM and under the LRUSM. The validity of this folk theorem is also discussed for general input streams under the Working Set algorithm.

We present and show the correctness of two algorithms called Q-Composer and CpR. Q-Composer is a probabilistic traffic-synthesizer and CpR is a probabilistic traffic-regulator. Given a cumulative distribution function F, Q-Composer synthesizes a flow that when fed into a single-input single-output network element, the distribution of the queue-size probability at the element closely follows F. CpR regulates an arbitrary traffic so that when the regulated traffic (i.e. the output of CpR) is fed into a single-input single-output network element, the distribution of the queue-size probability at the element closely follows a pre-specified cdf F. CpR can be viewed as a probabilistic generalization of deterministic Leaky-bucket regulators. Q-Composer and CpR are straightforward algorithms to implement and have applications in providing end-to-end probabilistic quality-of-service guarantees, multimedia encoding/decoding, and resource allocation and in simulation studies, beside other areas.

The performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In particular, it is expected that the stronger the locality of reference, the smaller the miss rate of the cache. For the independent reference model, this amounts to a smaller miss rate when the popularity distribution of requested objects in the stream is more skewed. We formalize this "folk theorem" through the companion concepts of majorization and Schur-concavity. This folk theorem is established for caches operating under a random on-demand replacement algorithm (RORA). However, the result fails to hold in general under the (popular) LRU and CLIMB policies, but can he established when the input has a Zipf-like popularity pmf with large skewness parameter. In addition, we explore how the majorization of popularity distributions translates into comparisons of three well-known locality of reference metrics, namely the inter-reference time, the working set size and the stack distance.

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of demand-driven cache replacement policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture this degree of skewness, we show that for the policy A0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference.

We study the problem of dynamic resource allocation of a GPS server with two traffic classes when the leaky bucket scheme is employed as a traffic policing mechanism. Three popular input traffic models - independent Poisson arrival, autoregressive model, and partially observed traffic (hidden Markov model) - are investigated. Theoretically, optimal control can be obtained by a basic dynamic programming algorithm. However, such a solution is computationally prohibitive due to the curse of dimensionality. Instead, we propose several heuristic policies with improvements using rollout, parallel rollout, and hindsight optimization techniques under the aforementioned traffic models and show that these techniques can significantly reduce the penalty associated with delays and dropped packets.

Research has shown that TCP Vegas performs better than TCP Reno with respect to overall network utilization, stability, fairness, throughput, packet loss, and burstiness. We analyze and improve the transient behavior of TCP Vegas, an important issue in today's large "bandwidth-delay product" networks. To quantify of our analysis, we introduce a new metric that captures the transient performance of TCP, namely, the (normalized) convergence time. We then consider the slow-start mechanism in TCP Vegas and show that, with a properly configured /spl gamma/ parameter, the transient behavior of TCP Vegas improves with respect to convergence time.

We use recent advances from the theory of multivariate stochastic orderings to formalize the "folk theorem" to the effect that positive correlations lead to increased buffer occupancy and larger buffer levels at a discrete-time infinite capacity multiplexer queue. Input sequences are compared in the supermodular (sm) ordering and buffer contents in the increasing convex (icx) ordering, respectively. Three popular classes of (discrete-time) traffic models are discussed, namely the fractional Gaussian noise traffic model, the on-off source model and the M|G|/spl infin/ traffic model. The independent version of an input process in each of these classes of traffic models is a member of the same class. In varying degree of generality, we show that this independent version is smaller than the input sequence itself, and that the corresponding buffer content processes are similarly ordered.