Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
19 results
Search Results
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 Resequencing delays under multipath routing -- Asymptotics in a simple queueing model(2005) Han, Yijie; Makowski, Armand M.; ISR; CSHCNWe study the resequencing delay caused by multipath routing. We use a queueing model which consists of parallel queues to model the network routing behavior. We define a new metric denoted by $gamma$, to study the impact of resequencing on the customer end-to-end delay. Our results characterize some properties of $gamma$ with respect to different service time distributions. In particular, the resequencing delay can be negligible when the delay along each path is light-tailed, but can be of major concern when it is heavy-tailed.Item On the behavior of ECN/RED gateways under a large number of TCP flows: Limit theorems(2005) Tinnakornsrisuphap, Peerapol; Makowski, Armand M.; Makowski; ISR; CSHCNWe consider a stochastic model of an ECN/RED gateway with competing TCP sources sharing the capacity. As the number of competing flows becomes large, the asymptotic queue behavior at the gateway can be described by a simple recursion and the hroughput behavior of individual TCP flows becomes asymptotically independent. In addition, a Central Limit Theorem complement is presented, yielding a more accurate characterization of the asymptotic queue. These results suggest a scalable yet accurate model of the complex large-scale stochastic feedback system, and crisply reveal the sources of queue fluctuations.Item Asymptotic optimality of the Round--Robin policy in multipath routing with resequencing(2005) Tsoukatos, Konstantinos P.; Makowski, Armand M.; Makowski, Armand M.; ISR; CSHCNWe consider a model of a multipath routing system, where arriving customers are routed to a set of identical, parallel, single server queues, according to balancing policies operating without state information. After completion of service, customers are required to leave the system in their order of arrival, thus incurring an additional resequencing delay. We are interested in minimizing the end-to-end delay (including time at the resequencing buffer) experienced by arriving customers. To that end, we establish optimality of the Round--Robin routing assignment in two asymptotic regimes, namely heavy and light traffic: In heavy traffic, Round--Robin customer assignment is shown to achieve the smallest (in the increasing convex stochastic ordering) end-to-end delay amongst all routing policies operating without queue state information. In light traffic, and for the special case of Poisson arrivals, we show that Round--Robin is again an optimal (in the strong stochastic ordering) routing policy. We illustrate these and suggest other stochastic comparison results in a number of simulation examples.Item Consistency analysis and evaluation of TTL-based Internet caches(2005) Bahat, Omri; Makowski, Armand M.; Makowski, Armand M.; ISRConsistency algorithms have been proposed for a wide range of applications that include distributed shared memories (DSM), distributed file systems, and databases. Fundamental definitions and operational constraints that are specific for each system do not necessarily translate well to Internet caches. A Web object is consistent if it is identical to the master document at the origin server, at the time it is served to users, therefore cached objects become stale immediately after the master is modified. Stale cache copies remain served to users until the cache is refreshed, subject to the network transmit delays. However, the performance of Internet consistency algorithms is evaluated through the corresponding cache hit rate and network traffic load that do not inform on the service of stale data, and are therefore inadequate, as outlined in numerous studies. To date, neither an analytical framework nor a suitable measure are available to model the service of stale data to users. In this paper we seek to remedy this state of affairs by formalizing both a framework and the novel hit* rate consistency measure, which captures non-stale downloads from the cache. To demonstrate this new methodology, we analyze and evaluate the consistency performance of a well studied TTL algorithm, under both zero and non-zero download latency. We conclude that data consistency can be significantly degraded even when a high hit rate is achieved, by calculating the incurred hit and hit* rates. The proposed procedure can be used to evaluate additional TTL and other (e.g., polling and invalidation) Web consistency protocols, as well as those retained by other applications (e.g., virtual shared memories).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 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 Convergence of ant routing algorithms -- Results for a simple parallel network and perspectives(2003) Yoo, Joon-Hyuk; La, Richard J.; Makowski, Armand M.; ISR; CSHCNWe study the convergence property of a family of distributed routing algorithms based on the ant colony metaphor, namely the uniform and regular ant routing algorithms discussed by Subramanian et al. For a simple two-node network, we show that the probabilistic routing tables converge in distribution (resp. in the a.s. sense) for the uniform (resp. regular) case. To the best of the authors' knowledge, the results given here appear to be the first formal convergence results for ant routing algorithms. Although they hold only for a very limited class of networks, their analysis already provide some useful lessons for extending the results to more complicated networks. We also discuss some of implementation issues that naturally arise from the convergence analysis.Item Distribution of path durations in mobile ad-hoc networks - Palm's Theorem at work(2003) Han, Yijie; La, Richard J.; Makowski, Armand M.; ISR; CSHCNWe study the distribution of a path duration in multi-hop wireless networks. We show that as the number of hops along a path increases, the path duration distribution can be accurately approximated by an exponential distribution under a set of mild conditions, even when the link duration distributions are not identical.Item Bounding superposed on-off sources - Variability ordering and majorization to the rescue(2003) Makowski, Armand M.; ISR; CSHCN