Queueing properties of feedback flow control systems

In this paper, we consider a network with both controllable and uncontrollable flows. Uncontrollable flows are typically generated from applications with stringent QoS requirements and are given high priority. On the other hand, controllable flows are typically generated by elastic applications and can adapt to the available link capacities in the network. We provide a general model of such a system and analyze its queueing behavior. Specially, we obtain a lower bound and an asymptotic upper bound for the tail of the workload distribution at each link in the network. These queueing results provide us with guidelines on how to design a feedback flow control system. Simulation results show that the lower bound and asymptotic upper bound are quite accurate and that our feedback control method can effectively control the queue length in the presence of both controllable and uncontrollable traffic. Finally, we describe a distributed strategy that uses the notion of Active Queue Management (AQM) for implementing our flow control solution.     

Admission control for statistical QoS: theory and practice

In networks that support quality of service, an admission control algorithm determines whether or not a new traffic flow can be admitted to the network such that all users will receive their required performance. Such an algorithm is a key component of future multiservice networks because it determines the extent to which network resources are utilized and whether the promised QoS parameters are actually delivered. The goals in this article are threefold. First, we describe and classify a broad set of proposed admission control algorithms. Second, we evaluate the accuracy of these algorithms via experiments using both on-off sources and long traces of compressed video; we compare the admissible regions and QoS parameters predicted by our implementations of the algorithms with those obtained from trace-driven simulations. Finally, we identify the key aspects of an admission control algorithm necessary for achieving a high degree of accuracy and hence a high statistical multiplexing gain     

A utility-based power-control scheme in wireless cellular systems

Distributed power-control algorithms for systems with hard signal-to-interference ratio (SIR) constraints may diverge when infeasibility arises. We present a power-control framework called utility-based power control (UBPC) by reformulating the problem using a softened SIR requirement (utility) and adding a penalty on power consumption (cost). Under this framework, the goal is to maximize the net utility, defined as utility minus cost. Although UBPC is still noncooperative and distributed in nature, some degree of cooperation emerges: a user will automatically decrease its target SIR (and may even turn off transmission) when it senses that traffic congestion is building up. This framework enables us to improve system convergence and to satisfy heterogeneous service requirements (such as delay and bit error rate) for integrated networks with both voice users and data users. Fairness, adaptiveness, and a high degree of flexibility can be achieved by properly tuning parameters in UBPC.     

Management of thoracolaryngopelvic dysplasia

We report a family in which three members have thoracolaryngopelvic dysplasia (Barnes' syndrome). This family illustrates the phenotypic variability seen in this rare clinical entity and highlights the medical and surgical management necessary in such cases.     

A central-limit-theorem-based approach for analyzing queue behaviorin high-speed networks

In this paper, we study P(𝒬>x), the tail of the steady-state queue length distribution at a high-speed multiplexer. In particular, we focus on the case when the aggregate traffic to the multiplexer can be characterized by a stationary Gaussian process. We provide two asymptotic upper bounds for the tail probability and an asymptotic result that emphasizes the importance of the dominant time scale and the maximum variance. One of our bounds is in a single-exponential form and can be used to calculate an upper bound to the asymptotic constant. However, we show that this bound, being of a single-exponential form, may not accurately capture the tail probability. Our asymptotic result on the importance of the maximum variance and our extensive numerical study on a known lower bound motivate the development of our second asymptotic upper bound. This bound is expressed in terms of the maximum variance of a Gaussian process, and enables the accurate estimation of the tail probability over a wide range of queue lengths. We apply our results to Gaussian as well as multiplexed non-Gaussian input sources, and validate their performance via simulations. Wherever possible, we have conducted our simulation study using importance sampling in order to improve its reliability and to effectively capture rare events. Our analytical study is based on extreme value theory, and therefore different from the approaches using traditional Markovian and large deviations techniques     

Performance of Random Access Scheduling Schemes in Multi-Hop Wireless Networks

The scheduling problem in multi-hop wireless networks has been extensively investigated. Although throughput optimal scheduling solutions have been developed in the literature, they are unsuitable for multi-hop wireless systems because they are usually centralized and have very high complexity. In this paper, we develop a random-access based scheduling scheme that utilizes local information. The important features of this scheme include constant-time complexity, distributed operations, and a provable performance guarantee. Analytical results show that it guarantees a larger fraction of the optimal throughput performance than the state-of-the-art. Through simulations with both single-hop and multi-hop traffics, we observe that the scheme provides high throughput, close to that of a well-known highly efficient centralized greedy solution called the greedy maximal scheduler.     

Biocompatible force sensor with optical readout and dimensions of 6 nm3

We have developed a nanoscopic force sensor with optical readout. The sensor consists of a single-stranded DNA oligomer flanked by two dyes. The DNA acts as a nonlinear spring: when the spring is stretched, the distance between the two dyes increases, resulting in reduced F?rster resonance energy transfer. The sensor was calibrated between 0 and 20 pN using a combined magnetic tweezers/single-molecule fluorescence microscope. We show that it is possible to tune the sensor's force response by varying the interdye spacing and that the FRET efficiency of the sensors decreases with increasing force. We demonstrate the usefulness of these sensors by using them to measure the forces internal to a single polymer molecule, a small DNA loop. Partial conversion of the single-stranded DNA loop to a double-stranded form results in the accumulation of strain: a force of approximately 6 pN was measured in the loop upon hybridization. The sensors should allow measurement of forces internal to various materials, including programmable DNA self-assemblies, polymer meshes, and DNA-based machines.     

Channel Sharing Scheme for Packet-Switched Cellular Networks

In this paper, we study an approach for sharing channels to improve network utilization in packet-switched cellular networks. Our scheme exploits unused resources in neighboring cells without the need for global coordination. We formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. We develop a measurement-based distributed algorithm to achieve this objective and study its convergence. We illustrate, via simulation results, that the distributed channel sharing scheme performs significantly better than the fixed channel scheme over a wide variety of traffic conditions. This research was supported in part by the National Science Foundation through grants ECS-0098089, ANI-0099137, ANI-0207892, ANI-9805441, ANI-0099137, and ANI-0207728, and by an Indiana 21st century grant. A conference version of this paper appeared in INFOCOM 99. This work was done when all the authors were at Purdue University. Suresh Kalyanasundaram received his Bachelors degree in Electrical and Electronics Engineering and Masters degree in Physics from Birla Institute of Technology and Science, Pilani, India in 1996. He received his Ph.D. from the School of Electrical and Computer Engineering, Purdue University, in May 2000. Since then he has been with Motorola, working in the area of performance analysis of wireless networks. Junyi Li received his B.S. and M.S. degrees from Shanghai Jiao Tong University, and Ph.D. degree from Purdue University. He was with the Department of Digital Communications Research at Bell Labs, Lucent Technologies from 1998 to 2000. In 2000 as a founding member he jointed Flarion Technologies, where he is now Director of Technology. He is a senior member of IEEE. Edwin K.P. Chong received the B.E.(Hons.) degree with First Class Honors from the University of Adelaide, South Australia, in 1987; and the M.A. and Ph.D. degrees in 1989 and 1991, respectively, both from Princeton University, where he held an IBM Fellowship. He joined the School of Electrical and Computer Engineering at Purdue University in 1991, where he was named a University Faculty Scholar in 1999, and was promoted to Professor in 2001. Since August 2001, he has been a Professor of Electrical and Computer Engineering and a Professor of Mathematics at Colorado State University. His current interests are in communication networks and optimization methods. He coauthored the recent book, An Introduction to Optimization, 2nd Edition, Wiley-Interscience, 2001. He was on the editorial board of the IEEE Transactions on Automatic Control, and is currently an editor for Computer Networks. He is an IEEE Control Systems Society Distinguished Lecturer. He received the NSF CAREER Award in 1995 and the ASEE Frederick Emmons Terman Award in 1998. Ness B. Shroff received his Ph.D. degree from Columbia University, NY in 1994. He is currently an Associate Professor in the School of Electrical and Computer Engineering at Purdue University. His research interests span the areas of wireless and wireline communication networks. He is especially interested in fundamental problems in the design, performance, scheduling, capacity, pricing, and control of these networks. His research is funded by various companies such as Intel, Hewlett Packard, Nortel, AT&T, and L. G. Electronics; and government agencies such as the National Science Foundation, Indiana Dept. of Transportation, and the Indiana 21st Century fund. Dr. Shroff is an editor for IEEE/ACM Trans. on Networking and the Computer Networks Journal, and past editor of IEEE Communications Letters. He was the conference chair for the 14th Annual IEEE Computer Communications Workshop (in Estes Park, CO, October 1999) and program co-chair for the symposium on high-speed networks, Globecom 2001 (San Francisco, CA, November 2000). He is also the Technical Program co-chair for IEEE INFOCOM'03 and panel co-chair for ACM Mobicom'02. He received the NSF CAREER award in 1996.     

On updating signal subspaces

The authors develop an algorithm for adaptively estimating the noise subspace of a data matrix, as is required in signal processing applications employing the `signal subspace' approach. The noise subspace is estimated using a rank-revealing QR factorization instead of the more expensive singular value or eigenvalue decompositions. Using incremental condition estimation to monitor the smallest singular values of triangular matrices, the authors can update the rank-revealing triangular factorization inexpensively when new rows are added and old rows are deleted. Experiments demonstrate that the new approach usually requires O(n²) work to update an n×n matrix, and that it accurately tracks the noise subspace     

FEC-based AP downlink transmission schemes for multiple flows: Combining the reliability and throughput enhancement of intra- and inter-flow coding

We consider downlink access point (AP) networks and the corresponding reliable transmission schemes. It is well known that one can protect the network traffic against packet erasures by forward-error-correcting-codes (FEC). In addition to ensuring reliable delivery, FECs could substantially reduce the amount of feedback traffic, which is critical when designing high-performance AP protocols.In this work, we generalize the FEC-based schemes, also known as intra-flow coding schemes, for multiple downlink flows. In contrast with the classic approach that performs FEC separately on individual flows, we propose a new protocol MU-FEC, which incorporates the recent idea of inter-flow coding to further enhance the achievable throughput. Specifically, MU-FEC guarantees 100% reliability, is oblivious and robust to the underlying erasure probabilities, has near-optimal throughput higher than any existing inter-flow coding protocols, and can be practically implemented on top of 802.11. The design of MU-FEC consists of three components: batch-based operations, a systematic phase-based network coding decision policy, and smooth integration of inter-flow and intra-flow coding. We analytically show that MU-FEC can achieve much higher throughput than intra- or inter-flow coding alone, and validate its performance gain via extensive simulations. To our knowledge, MU-FEC is the first practical protocol that leverages both intra-flow and inter-flow network coding to solve a real-world problem in single-hop wireless networks.