Browsing by Author "Vanichpun, Sarut"
Results Per Page
Sort Options
Item Comparing locality of reference - Some folk theorems for the miss rates and the output of caches(2004) Makowski, Armand M.; Vanichpun, Sarut; ISR; CSHCNThe performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference. We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. We focus on two ``folk theorems," namely (i) The stronger locality of reference, the smaller the miss rate of the cache; (ii) Good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream of requests. We discuss these two folk theorems in the context of a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). As we propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, we introduce the notion of majorization as a mean for capturing this degree of skewness. We show that these folk theorems hold for caches operating under a large class of cache replacement policies, including he optimal policy A_0 and the random policy, but may fail under the LRU policyItem Comparing Strength of Locality of Reference: Popularity, Temporal Correlations, and Some Folk Theorems for the Miss Rates and Outputs of Caches(2005-03-11) Vanichpun, Sarut; Makowski, Armand M; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference. We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. We focus on two ``folk theorems," that is, (i) The stronger the locality of reference, the smaller the miss rate of the cache; and (ii) Good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream of requests. These two folk theorems are explored in the context of demand-driven caching for the two main contributors of locality of reference, namely popularity and temporal correlations. We first focus exclusively on popularity by considering the situation where there are no temporal correlations in the stream of requests, as would be the case under the Independent Reference Model (IRM). As we propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, we introduce the notion of majorization as a means for capturing this degree of skewness. We show that these folk theorems hold for caches operating under a large class of replacement policies, the so-called Random On-demand Replacement Algorithms (RORA), which includes the optimal policy $A_0$ and the random policy. However, counterexamples prove that this is not always the case under the (popular) Least-Recently-Used (LRU) and CLIMB policies. In such cases, conjectures are offered (and supported by simulations) as to when the folk theorems would hold under the LRU or CLIMB caching, given that the IRM input has a Zipf-like popularity pmf. To compare the strength of temporal correlations in streams of requests, we define the notion of Temporal Correlations (TC) ordering based on the so-called supermodular ordering, a concept of positive dependence which has been successfully used for comparing dependence structures in sequences of random variables. We explore how the TC ordering captures the strength of temporal 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 establish the folk theorem to the effect that the stronger the strength of temporal correlations, the smaller the miss rate for the PMM under certain assumptions on the caching policy. Conjectures and simulations are offered as to when this folk theorem would hold under the HOMM and under the LRUSM. In addition, the validity of this folk theorem for general request streams under the Working Set algorithm is studied. Lastly, we investigate how the majorization and TC orderings can be translated into comparisons of three well-known locality of reference metrics, namely the working set size, the inter-reference time and the stack distance.Item Comparing Strength of Locality of Reference: Popularity, Temporal Correlations, and Some Folk Theorems for the Miss Rates and Outputs of Caches(2005) Vanichpun, Sarut; Makowski, Armand M.; ISR; CSHCNThe performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference. We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. We focus on two ``folk theorems," that is, (i) The stronger the locality of reference, the smaller the miss rate of the cache; and (ii) Good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream of requests. These two folk theorems are explored in the context of demand-driven caching for the two main contributors of locality of reference, namely popularity and temporal correlations. We first focus exclusively on popularity by considering the situation where there are no temporal correlations in the stream of requests, as would be the case under the Independent Reference Model (IRM). As we propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, we introduce the notion of majorization as a means for capturing this degree of skewness. We show that these folk theorems hold for caches operating under a large class of replacement policies, the so-called Random On-demand Replacement Algorithms (RORA), which includes the optimal policy $A_0$ and the random policy. However, counterexamples prove that this is not always the case under the (popular) Least-Recently-Used (LRU) and CLIMB policies. In such cases, conjectures are offered (and supported by simulations) as to when the folk theorems would hold under the LRU or CLIMB caching, given that the IRM input has a Zipf-like popularity pmf. To compare the strength of temporal correlations in streams of requests, we define the notion of Temporal Correlations (TC) ordering based on the so-called supermodular ordering, a concept of positive dependence which has been successfully used for comparing dependence structures in sequences of random variables. We explore how the TC ordering captures the strength of temporal 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 establish the folk theorem to the effect that the stronger the strength of temporal correlations, the smaller the miss rate for the PMM under certain assumptions on the caching policy. Conjectures and simulations are offered as to when this folk theorem would hold under the HOMM and under the LRUSM. In addition, the validity of this folk theorem for general request streams under the Working Set algorithm is studied. Lastly, we investigate how the majorization and TC orderings can be translated into comparisons of three well-known locality of reference metrics, namely the working set size, the inter-reference time and the stack distance.Item Dynamic Resource Allocation of GPS Queues with Leaky Buckets(2003) Tinnakornsrisuphap, Peerapol; Vanichpun, Sarut; La, Richard J.; La, Richard J.; ISR; CSHCNWe 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 in this paper.Theoretically, the 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 the delay and dropped packets.
Item The Effect of Positive Correlations on Buffer Occupancy: Comparison and Lower Bounds via Supermodular Ordering(2001) Vanichpun, Sarut; Makowski, Armand M.; ISR; CSHCNWe use recent advances from the theory of multivariate stochastic orderings to formalize the "folk theorem" to the effect that positive correlations leads to increased buffer occupancy and larger buffer levels at a discrete time multiplexer queue of infinite capacity. We do so by comparing input sequences in the supermodular (sm) ordering and the corresponding buffer contents in the increasing convex (icx) ordering, respectively.Three popular classes of (discrete-time) traffic models are considered here, namely, the fractional Gaussian noise (FGN) traffic model, the on-off source model and the M|G|infinity traffic model. The independent version of an input process in each of these classes of traffic models is a member of the same class. We show that this independent version is smaller than the input sequence itself and that the corresponding buffer content processes are ordered in the same direction. For each traffic model, we show by simulations that the first and second moments of buffer levels are ordered in agreement with the comparison results.
The more general version of the folk theorem, namely "the larger the positive correlations of input traffic, the higher the buffer occupancy levels" is established in some cases. For the FGN traffic models, we show that the process with higher Hurst parameter is larger than the process with smaller Hurst parameter. In the case of the M|G|infinity model, the effect of session-duration variability is discussed and the comparison result is obtained in the bivariate case.
Item Modeling locality of reference via notions of positive dependence -- Some mixed news!(2005) Vanichpun, Sarut; Makowski, Armand M.; ISR; CSHCNWe 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.Item Modeling strength of locality of reference via notions of positive dependence(2005) Vanichpun, Sarut; Makowski, Armand M.; Makowski, Armand M.; ISR; CSHCNThe performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formally {em compare} streams of requests on the basis of their locality of reference. We take on this issue by introducing the notion of Temporal Correlations (TC) ordering for comparing strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence which has been successfully used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal 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 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 as to when this folk theorem should hold under the HOMM and under the LRUSM. Lastly, we investigate the validity this folk theorem for general input streams under the Working Set algorithm.Item The output of a cache under the independent reference model - Where did the locality of reference go?(2004) Vanichpun, Sarut; Makowski, Armand M.; ISR; CSHCNWe 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 cache replacement policies, including standard on-demand replacement algorithms such as the policy A_0 and the random policy, as well as the LRU and CLIMB 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 the degree of skewness, we show that for the policy A_0 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.Item When Are On-Off Sources SIS? Conditions and Applications(2002) Vanichpun, Sarut; Makowski, Armand M.; ISR; CSHCNRecent advances from the theory of multivariate stochastic orderings can be used to formalize the lqlq folk theorem" to the effect that positive correlations lead to larger buffer levels at a discrete-time infinite capacity multiplexer queue. For instance, it is known that if the input traffic is larger than its independent version in the supermodular (sm) ordering, then their corresponding buffer contents are similarly orderedin the increasing convex (icx) ordering.A sufficient condition for the aforementioned sm comparison is the stochastic increasingness in sequence (SIS) property of the input traffic.In this paper, we provide conditions for the stationary on-off source tobe SIS. We then use this result to find conditions under which the superposition of independent on-off sources and the $M|G|infty$ input model are each sm greater than their respective independent version.Similar but weaker SIS conditions are also obtained for renewal on-off processes.