Yale University
Department of Statistics

Monday, April 1, 2002

 Optimal Queue Control in Multi-Access Communications

Prof. Edmund Yeh
Department of Electrical Engineering
Yale University

The development of communication technology over the last few decades has led to a dramatic shift from point-to-point circuit-switched analog networks to multiplexed packet-switched digital networks.  Within this context, the problem of multi-access (many-to-one) communications has gained in prominence.  A multi-access communication situation arises whenever multiple senders of information, such as mobile phones in a cellular network or ground stations in a satellite network, attempt to transmit to a single receiver, such as a base station or a satellite, at the same time and in the same frequency range.  There are a number of different perspectives on this question, each addressing only a part of the overall problem.  Multi-access network theory (ALOHA, CSMA, etc.) has give sophisticated analyses of “network-layer” issues such as source burstiness, network delay, and buffer overflow, but do not adequately address “physical-layer” concerns such as channel modeling, coding, and detection.  In contrast, multi-access information theory has generated significant insights on the impact of noise and interference on communication rate and error probability at the physical layer.   By adhering to the conventional source-channel-destination model, however, information theory ignores the random arrival of messages and thereby renders meaningful analysis of network delay impossible.

In this work, we adopt an “inter-layer” approach to multi-access communications which treats physical-layer issues of noise, interference, error probability, and network-layer issues of source burstiness and delay in a more cohesive framework.  We consider a multi-access communication model where multiple information sources generate packets of variable lengths according to Poisson processes.  The packets are queued in the users' respective buffers until being sent by the corresponding transmitters.  All packets are then decoded at a common receiver, which receives the sum of the transmitted signals plus Gaussian noise.  It is further assumed that optimal coding can somehow be performed at the physical layer so that all rates in the information-theoretic multi-access capacity region are achievable.  The objective is then to design the rate allocation policy to minimize the overall average packet delay and bit delay in the system.  We show that under certain conditions of symmetry, this ``inter-layer'' multi-access problem admits an elegant solution based on the idea of load-balancing.  The proofs involve interesting applications of ideas from the theory of majorization, stochastic coupling, and dynamic programming.


Edmund Yeh received his Bachelor of Science in Electrical Engineering with Distinction from Stanford University in 1994.  In the same year, he was awarded one of ten Winston Churchill Scholarships for overseas study in science and engineering at Churchill College, University of Cambridge, in the United Kingdom.  He received his Master of Philosophy in Electrical Engineering from the University of Cambridge in 1995.  As a doctoral student, he studied under Professor Robert Gallager at the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology.  He received his Ph.D. in Electrical Engineering from MIT in 2001.  Since July 2001, he has been an Assistant Professor of Electrical Engineering at Yale University, New Haven, Connecticut.

Dr. Yeh was the recipient of the National Science Foundation and Office of Naval Research Fellowships for graduate study, and is a member of Phi Beta Kappa, Tau Beta Pi, and IEEE.  He has spent a number of summers working at industrial labs, including the Mathematical Sciences Research Center at Bell Laboratories, Murray Hill, New Jersey.

Seminar to be held in Room 107, 24 Hillhouse Avenue at 4:15 pm