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
18 results
Search Results
Item Coloring Rooted Subtrees on a Bounded Degree Host Tree(2007) Rawat, Anuj; Shayman, Mark; La, Richard J.; Marcus, Steven I.We consider a rooted tree R to be a rooted subtree of a given tree T if the tree obtained by replacing the directed arcs of R by undirected edges is a subtree of T. In this work, we study the problem of assigning colors to a given set of rooted subtrees of a given host tree such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The objective is to minimize the total number of colors used in the coloring. The problem is NP hard even in the case when the degree of the host tree is restricted to 3. This problem is motivated by the problem of assigning wavelengths to multicast traffic requests in all-optical tree networks. We present a greedy coloring scheme for the case when the degree of the host tree is restricted to 3 and prove that it is a 5/2-approximation algorithm. We then present another simpler coloring scheme and prove that it is an approximation algorithm for the problem with approximation ratio 10/3, 3 and 2 for the cases when the degree of the host tree is restricted to 4, 3, and 2, respectively.Item Distributional Convergence of Inter-Meeting Times Under Generalized Hybrid Random Walk Mobility Model(2008-01-14) La, Richard J.The performance of a mobile wireless network depends on the time-varying connectivity of the network as nodes move around. Therefore, there has been a growing interest in the distribution of inter-meeting times between two nodes in mobile wireless networks. We study the distribution of inter-meeting times under the (generalized) Hybrid Random Walk mobility model. We show that when the (conditional) probability that the two nodes can communicate directly with each other given that they are in the same cell is small, the distribution of inter-meeting times can be well approximated using an exponential distribution. In addition, the mean of the inter-meeting times can be estimated using the number of cells in the network and the aforementioned conditional probability of having a communication link when the two nodes are in the same cell. We also show that such an approximation does not hold for the Random Walk mobility model.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 Robust Routing with Unknown Traffic Matrices(2006) Tabatabaee, Vahid; Kashyap, Abhishek; Bhattacharjee, Bobby; La, Richard J.; Shayman, Mark; Shayman, Mark; ISRItem Single-path routing of time-varying traffic(2006) Kashyap, Abhishek; Bhattacharjee, Bobby; La, Richard J.; Shayman, Mark; Tabatabaee, Vahdi; Shayman, Mark; ISRItem 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.