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
14 results
Search Results
Item Distributional convergence of path durations in MANETs with dependent link excess lives(2006) La, Richard J.; La, Richard J.; ISR; CSHCNWe investigate the issue of path selection in multi-hop wireless networks with the goal of identifying a scheme that can select a path with the largest expected duration. To this end we first study the distribution of path duration. We show that, under a set of mild conditions, when the hop count along a path is large, the distribution of path duration can be well approximated by an exponential distribution even when the distributions of link durations are dependent and heterogeneous. Secondly, we investigate the statistical relation between a path duration and the durations of the links along the path. We prove that the parameter of the exponential distribution, which determines the expected duration of the path, is related to the link durations only through their means and is given by the sum of the inverses of the expected link durations. Based on our analytical results we propose a scheme that can be implemented with existing routing protocols and select the paths with the largest expected durations.Item Opportunistic packet scheduling in cellular networks with base station antenna arrays(2006) Ren, Tianmin; La, Richard J.; ISR; CSHCNWe study the issue of designing a downlink scheduling policy for a cellular network with base station antenna arrays. We derive an optimal scheduling policy that achieves the throughput region, which is a set of feasible arrival rate vectors that can be stabilized by some scheduling policy. Then, based on the structure of the derived optimal policy whose complexity increases exponentially with the number of users in the system, we propose two heuristic scheduling algorithms with much lower complexity. We demonstrate that our proposed algorithms perform much better than other heuristic algorithms that do not take into consideration the physical layer constraints and/or queue lengths in the sense that they have a larger throughput region than other heuristic algorithms.Item Stability of rate control system with time-varying communication delays(2004) La, Richard J.; Ranjan, Priya; ISR; CSHCNWe adopt the optimization framework for the rate allocation problem proposed by Kelly and investigate the stability of the system with arbitrary communication delays between network elements with time-varying queue dynamics. We first present the conditions for the existence of a solution of the system. Second, we establish the conditions for the system stability with arbitrary delays for a family of popular utility and price functions, and then extend the results to more general utility and price functions. We demonstrate that the stability of such a system can be studied by considering a discrete time system derived from a simpler homogeneous delay case where all users have the same fixed delay. Numerical examples are provided to validate our analyses.Item Global stability conditions for rate control with arbitrary communication delays(2003) La, Richard J.; Ranjan, Priya; Abed, Eyad H.; ISR; CSHCNWe adopt the optimization framework for the rate allocation problem proposed by Kelly and investigate the stability of the system with arbitrary communication delays between network elements. It is shown that there is a natural underlying discrete time system whose stability is directly related to the stability of the given system. We first present general stability conditions of the system with arbitrary delays, and then apply these results to establish the stability of the system with a family of popular utility and resource price functions. The exponential stability of the system with the given utility and resource price functions is established. We also investigate discretized models that better approximate the packet level dynamics of the system and show that similar stability conditions can be obtained. Numerical examples are provided to validate our analyses.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 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 Trade-offs in rate control with communication delay(2003) Ranjan, Priya; La, Richard J.; Abed, Eyad H.; ISRWe adopt the optimization framework for rate allocation problem proposed by Kelly and characterize the stability condition with an arbitrary communication delay in the case of single resource. We demonstrate the existence of a fundamental trade-off between users price elasticity of demand and the responsiveness of resource through a choice of price function as well as between system stability and resource utilization. We investigate the effects of non-responsive traffic on system stability and show that the presence of non-responsive traffic enhances the stability of system. We also investigate the system behavior after the system loses its stability.Item Asymptotic Behavior of Heterogeneous TCP Flows and RED Gateway(2003) Tinnakornsrisuphap, Peerapol; La, Richard J.; ISRWe introduce a stochastic model of a bottleneck ECN/RED gateway under a large number of heterogeneous TCP flows, ie flows with diverse round-trips and session dynamics. We investigate the asymptotic behavior of the system and show that as the number of flows becomes large, the buffer dynamics and aggregate traffic simplify and can be accurately described by simple stochastic recursions independent of the number of flows, resulting in a scalable model. Based on the central limit theorem results presented in the paper we analyze the sources of fluctuations in queue size and describe the relationship between the packet marking function and variance of queue size.Item Convergence Properties For Uniform Ant Routing(2003) Yoo, Joon-Hyuk; La, Richard J.; Makowski, Armand M.; ISR; CSHCNWe study the convergence property of a family of distributed routingalgorithms based on the ant colony metaphor, which generalize the uniform ant routing algorithms proposed earlier. For a simple two-node network, we show that the probabilistic routing tables under these algorithms converge in distribution, and discuss some of implementation issues.