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
85 results
Search Results
Item On the existence of triangles in random key graphs(2009-07-04) Yagan, Osman; Makowski, Armand M.The random key graph, also known as the uniform random intersection graph, is a random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the appearance of triangles in random key graphs by applying the method of first and second moments to the number of triangles in the graph.Item Connectivity in one-dimensional geometric random graphs: Poisson approximations, zero-one laws and phase transitions(2008-10-24) Han, Guang; Makowski, Armand M.; Makowski, Armand M.Consider n points (or nodes) distributed uniformly and independently on the unit interval [0,1]. Two nodes are said to be adjacent if their distance is less than some given threshold value.For the underlying random graph we derive zero-one laws for the property of graph connectivity and give the asymptotics of the transition widths for the associated phase transition. These results all flow from a single convergence statement for the probability of graph connectivity under a particular class of scalings. Given the importance of this result, we give two separate proofs; one approach relies on results concerning maximal spacings, while the other one exploits a Poisson convergence result for the number of breakpoint users.Item On the random graph induced by a randomized predistribution scheme under full visibility (Extended version)(2008) Yagan, Osman; Makowski, Armand M.We consider the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the absence of isolated nodes, and complement it by a Poisson convergence for the number of isolated nodes. Leveraging earlier resu lts and analogies with Erd\H{o}s-Renyi graphs, we explore similar results for the property of graph connectivity. Implications for secure connectivity are discussed.Item A strong zero-one law for connectivity in one-dimensional geometric random graphs with non-vanishing densities(2007) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISRWe consider the geometric random graph where n points are distributed independently on the unit interval [0,1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some transmission range. When F admits a continuous density f which is strictly positive on [0,1], we show that the property of graph connectivity exhibits a strong critical threshold and we identify it. This is achieved by generalizing a limit result on maximal spacings due to Levy for the uniform distribution.Item On the critical communication range under node placement with vanishing densities(2007) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISRWe consider the random network where n points are placed independently on the unit interval [0, 1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some transmission range. When F admits a continuous density f with f = inf (f(x), x [0, 1]) > 0, it is known that the property of graph connectivity for the underlying random graph admits a strong critical threshold. Through a counterexample, we show that only a weak critical threshold exists when f = 0 and we identify it. Implications for the critical transmission range are discussed.Item On zero-one laws for connectivity in one-dimensional geometric random graphs(2006) Han, Guang; Makowski, Armand M.; Makowski; ISR; CSHCNWe consider the geometric random graph where n points are distributed uniformly and independently on the unit interval [0,1]. Using the method of first and second moments, we provide a simple proof of the "zero-one" law for the property of graph connectivity under the asymptotic regime created by having n become large and the transmission range scaled appropriately with n.Item Very sharp transitions in one-dimensional MANETs(2005) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISR; CSHCNWe investigate how quickly phase transitions can occur in one-dimensional geometric random graph models of MANETs. In the case of graph connectivity, we show that the transition width behaves like 1/n (when the number n of users is large), a significant improvement over general asymptotic bounds given recently by Goel et al. for monotone graph properties. We also discuss a similar result for the property that there exists no isolated user in the network. The asymptotic results are validated by numerical computations. Finally we outline how the approach sed here could be applied in higher dimensions and or other graph properties.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.