Communications & Networking Seminar Series:     

Upcoming Talk:

Future Talks:

Srisankar Kunniyur (University of Pennsylvania)

Feb 18, 2004

Title: Designing a low-loss, low-delay Internet with Service Differentiation

Abstract:

Our goal is to design a differentiated service for elastic users in the
Internet using only a FIFO queue and an Active Queue Management (AQM)
scheme. AQM schemes in Internet routers provide congestion information to
end sources by marking or dropping packets.  We will propose and analyze a
class of AQM schemes that, in conjunction with TCP and other congestion
controllers, allow the router to provide service differentiation and
achieve a high level of utilization and small queue lengths. We will then
propose a specific AQM scheme that can be easily implemented in routers.

Francesco Bullo ( UIUC )

Feb 25, 2004

Leandros Tassiulas (UMD)

Feb 26, 2004

Lang Tong (Cornell University)

Mar. 3, 2004

John Baillieul (Boston University)

Mar. 24, 2004

Navin Kaneja (Harvard University)

Mar. 31, 2004

Vincent Chan (MIT)

Apr. 7, 2004

Toby Berger (Cornell University)

Apr. 14, 2004

Peter Marbach (University of Toronto)

Apr. 21, 2004

Past Talks:

Venkatesh Saligrama (Boston University)

November 19, 2003

4:00pm Watson Rm 400

Title: Distributed Hypothesis Testing in Sensor Networks

Abstract:

Recent advances in sensor and computing technologies provide impetus for deploying wireless sensor networks---a network of massively distributed tiny devices capable of sensing, processing and exchanging data over a wireless medium. Such networks are envisioned to provide real-time information in such diverse applications as building safety, environmental control, power systems, and manufacturing.

In our talk we will focus on two typical but diametrically opposite scenarios encountered in sensor networks. In the first scenario, N distributed noisy sensors observe independent aspects of a global event and must collaborate through a network to provide information about the global event. In the secondscenario, N distributed noisy sensors observe a single event and can collaborate by exchanging information through a network. The task is to arrive at a consensus about the event after exchanging such messages. We characterize conditions for reaching a consensus among all the nodes and derive conditions for convergence to the centralized MAP estimate. This leads to an understanding of network topologies that enhance consensus building and conflict avoidance. The two opposite scenarios serve to highlight the differences encountered in problems involving sensor networks. While in the latter scenario judicious data/information sharing among all the sensors appears to be essential, the former requires judiciously limiting the data/information transmission to the relevant sensors.

Sem Borst (Bell Labs)

Wednesday, November 12, 2003

4:00pm, Watson 400

Title: Flow-Level Performance of Channel-Aware Scheduling Algorithms in Wireless Data Networks.

Abstract:

Channel-aware scheduling strategies, such as the Proportional Fair algorithm for the CDMA 1xEV-DO system, provide an effective mechanism for improving throughput performance in wireless data networks by exploiting channel fluctuations. The performance of channel-aware scheduling algorithms has mostly been explored at the packet level for a static user population, often assuming infinite backlogs. In this talk, we focus on the performance at the flow level in a dynamic setting with random finite-size service demands. We show that in certain cases the user-level performance may be evaluated by means of a multi-class Processor-Sharing model where the total service rate varies with the total number of users. The latter model provides explicit formulas for the distribution of the number of active users of the various classes, the mean response times, the blocking probabilities, and the mean throughput. In addition we show that, in the presence of channel variations, greedy, myopic strategies which maximize throughput in a static scenario, may result in sub-optimal throughput performance for a dynamic user configuration and cause potential instability effects.

Sergio Verdu (Princeton University)

Wednesday, November 5th, 2003

4:00 p.m., Watson 400

Title: Error Correcting Codes for Noiseless Data Compression

Abstract:

Mung Chiang (Princeton University)

October 29, 2003

Title: Balancing Transport and Physical Layers in Wireless Ad Hoc Networks: Jointly Optimal TCP Congestion Control and Power Control.

Abstract:

In a wireless ad hoc network with multihop transmissions and interference-limited link rates, power control in the physical layer changes bandwidth supply, and congestion control in the transport layer regulates bandwidth demand. Can we balance the two through a cross layer design to enhance the overall network performance, while maintaining the stability, robustness, and architectural modularity of the network?

We present a distributive power control algorithm that couples with the original TCP protocols to increase the end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained optimization, we prove the convergence of this coupled system to the global optimality of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when the congestion control mechanism is TCP Vegas, we show that a simple utilization in the physical layer of the router buffer occupancy information suffices to achieve the joint and global optimality of this cross layer design. Both analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading-off performance optimality for implementation simplicity.

Anthony Ephremides (University of Maryland)

Wednesday, October 8th, 2003

4:00 p.m., Watson 400

Title: Some Trade-offs in Sensor Networks

Abstract:

Many sensor networks are designed to perform detection of a central event through multiple measurements that are made distributedly. At the same time, the measuring devices (sensors) rely on small batteries and must expend energy in a parsimonious way. The problem we consider is the interplay between detection performance and energy expenditure. This problem arises since there are many options for implementing the detection process. One is for each sensor to perform the detection and transmit only the single-bit decision to the control center that then "fuses" the decisions it receives into the final one. Another option is for each sensor to transmit its entire set of measurements to the control center and let that center make the optimal decision. Clearly the second option will involve serious RF transmission energy expenditure. Finally, it is possible for each sensor to "compress" its data to something between the extreme two cases outlined above. We evaluate the trade-offs involved in considering these options and we discuss the additional complication of selecting routes to the control center in a multi-hop environment.  Finally we present some related security concerns and express some thoughts regarding this type of sensor networks.

Yannis Paschalidas (Boston University)

April 23, 2003

Title: Revenue and Welfare Maximization in Multiservice Communication Networks

Abstract:

We consider a communication network that can accommodate multiple service classes, differing in bandwidth requirements, demand pattern, session duration, and routing. The network charges a fee per session which can depend on the current congestion level, and which affects user's demand. We are interested in either maximizing long-term average revenue or social welfare. The optimal policy is dynamic (spot pricing) where prices depend on instantaneous congestion. We show that a simple "static pricing" policy is asymptotically optimal in a regime of many, relatively small, users. This implies that pricing and resource allocation decisions should evolve on the time-scale of changes in demand statistics rather than the short time-scale of instantaneous congestion. The result is surprisingly general and holds even when we allow dynamic routing and incorporate demand substitution effects into the demand model. Demand substitution effects model the situation where price increases for a class of service might lead users to use another class as an imperfect substitute. 

For both revenue and welfare maximization objectives we characterize the structure of the asymptotically optimal static prices, expressing them as a function of a parsimonious number of parameters. Effective parameter values can be found by solving a deterministic optimization problem summarizing the network dynamics or by employing simulation-based optimization methods.  In the case of welfare maximization our proposed policy can be computed in a distributed and asynchronous manner, which opens the door to large, realistic implementations.

Eytan Modiano (MIT)

April 16, 2003

Title: Dynamic Resource Allocation in Satellite and Wireless Networks

Abstract:

This talk will discuss new architectures for satellite networks and algorithms for resource  allocation in these networks.  For example, we will discuss the problem of optimal energy allocation for communication satellites and provide a dynamic programming algorithm for optimal energy allocation. We will also discuss the problems of routing and  scheduling in a  multi-beam satellite systems.  These include adaptive power and rate  control techniques for time-varying satellite channels to achieve greatly improved data throughputs and optimal packet routing and scheduling algorithms for multi-beam satellite systems. Finally, while motivated by satellite networking, much of our work is directly applicable or can be extended to wireless networks.  As an example, we will discuss the problem of joint routing and power allocation in a wireless network to maximize network throughput.

Piyush Gupta (Lucent Technologies, Bell Labs)

April 9, 2003

Title: Capacity Analysis of Large Wireless Networks

Abstract:

Multi-hop wireless networks, also known as ad hoc networks, consist of a group of nodes that communicate with each other over a wireless channel without any centralized control.  Some example scenarios of such networks are in coordinating an emergency rescue operation, networking mobile computer users on a campus, sensor networks, and automated transportation systems. 

In this talk, we first discuss some recent results on the traffic-carrying capacity of large multi-hop wireless networks under some models of noninterference motivated by current technology.  We then present an information-theoretic constructive scheme for obtaining an achievable rate region in wireless networks of arbitrary size and topology.

Randall Berry (Northwestern University)

March 26, 2003

Title: Channel Aware Resource Allocation in Wireless Networks-Centralized and Distributed Approaches

Abstract:

A basic characteristic of wireless networks is that channel conditions vary across the user population and over time.  One consequence of this is that different users will require different resources, such as bandwidth or power, to achieve the same performance (e.g. transmission rate) at any given time.  This talk will address several different resource allocation problems that arise in this context. First, we consider a transmission scheduling problem in a wireless network. The goal here is to allocate resources to users over time to minimize delay, while also conserving long-term average power. We characterize the trade-off between these quantities and show that this trade-off has very different behavior in the regimes of large delay versus the regime of low delay. 

Next, we consider a multiple access setting where a distributed group of users are attempting to send data to a common receiver. We consider a distributed random access protocol that is only based on local channel knowledge. We study the throughput in this situation as the number of users increases, and show that users can distributively exploit "multi-user diversity" resulting in a sum capacity that is increasing in the number of users.  The rate of this increase is the same as that achieved if a centralized scheduler was coordinating the users.  Moreover, we show that asymptotically this random access protocol outperforms a deterministic TDM schedule.

Sanjeev Kulkarni (Princeton University)

February 26, 2003 

Title: On the Throughput of Wireless and Heterogeneous Networks

Abstract:

We address the problem of how throughput in a wireless network scales as the number of users grows.  Following the model of Gupta and Kumar, we consider n identical nodes placed in a fixed area.  Pairs of transmitters and receivers wish to communicate but are subject to interference from other nodes.  Throughput is measured in bit-meters per second.  We provide a very elementary deterministic approach that gives achievability results in terms of three key properties of the node locations.  As a special case, we obtain Gupta and Kumar's O(sqrt{n}) throughput for a general class of configurations.  Previous results for random node locations can be strengthened and some new results for interesting non-i.i.d. node locations can be obtained as special cases. 

We also extend our approach to analyze the performance of a heterogeneous network consisting of wireless nodes together with access points to a wired infrastructure.  This brings into sharp focus the tension between the interference limited simultaneous communication between the nodes and crowding to access the wired infrastructure.  When n nodes are randomly placed in a fixed area, our upper and lower bounds on the transport capacity are tight and we show that the access points have to be closer than a distance O(1/n^{1/4}) apart for the wired infrastructure to be beneficial.

Robert Gallager (MIT)

February 18, 2003

Title: Claude Shannon's Legacy: Information Theory to the Information Age

Abstract:

Information theory started in 1948 with Shannon's landmark papers on the 

mathematical theory of communication.  Over a period of 40 years, this theory

revolutionized the architecture and technology of communication systems.  Shannon

also laid the foundations for switching technology and was a major pioneer in artificial

intelligence and computer science.  More than anyone, he created the foundations for

the Information Age.

Along with discussing these contributions, we contrast Shannon's research style with

that of other more common styles and show why nurturing this approach to research

is so important in the information sciences and related fields.  We also speculate

about some of the positive and negative effects of this new age on the research and

academic community.

Philip Whiting (Bell Labs)

March 26, 2002

Title: Dimensioning the Wavelength Converters of an Optical Packet

Switch and the Classical Occupancy Problem

Abstract:

Urn models find wide application in computer science, engineering, biology, physics and statistics. One of the most well known is the classical occupancy problem, in which there are n urns and r balls and the problem is to determine the distribution of empty urns with the balls being thrown independently and at random (see Probability Theory and its Applications, Volume 1 W.Feller, Urn Models and their Applications, Johnson and Kotz.) In this talk we show that this problem arises in the dimensioning of a proposed optical packet switch which uses a pool of wavelength converters to reduce contention between packets at the fibre output.

The switch operates by providing wavelength converters as a pool at an extended switch output which allows packets to be redirected to their destination fibre after conversion. In this way contention between packets with the same wavelength and output fibre is reduced whilst a limited number of converters are used. The switch consists of passive optical devices, the core component being a space switch which interconnects the input and output ports (fibre,frequency). Further ports on the space switch are used to allow access to a pool of fully tuneable wavelength converters (any wavelength to any wavelength). They need to be rapidly tuneable for this appliation. Control is effected by bleeding optical power from incoming packets, which data is used to set up the space switch and tune the input/output wavelengths of the converters.

Packet losses as low as 10^{-10} (or lower) may be required in such a switch and exhaustion of the wavelength converter pool is a primary contribution to this loss. As we show an urn model allows us to evaluate this probability. ``Exact methods'' for obtaining it, however, can prove numerically intractable because of rounding error and the need for taking the convolution of the converter requirements over the wavelengths being used by the switch. Large deviations represents an alternative approach and, as we show, the rate function for classical occupancy can be obtained directly from a sum of independent (but not identically distributed) geometric random variables. Determination of the exponent for converter exhaustion then leads to a tradeoff between the component for packets being routed to fewer fibres than average and the component for an above average number of arrivals. This then allows an asymptotic upper bound on packet loss to be obtained as we describe. Numerical results are presented to illustrate the accuracy of the approximations and extensions to the dimensioning problem are discussed.

Gerhard Kramer (Bell Labs)

Jan 18, 2002

Title: Bits and Pieces of a Network Information Theory

Abstract:

The talk is intended as an introduction to some basics of network information theory. We begin by developing a simple but general model called the discrete memoryless network (DMN). This model is probabilistic, and we propose that two restrictions are needed on the joint probability distribution of the random variables occurring in the DMN. We show that the apparent simplicity of the model is not a restriction: the model subsumes most channels that have been studied in information theory. The second part of the talk focusses on two commonly used coding techniques: Shannon's random coding and superposition coding. The third part of the talk is more technical in nature: we do a case study on so-called multiple-relay channels which occur, e.g., in mobile ad-hoc networks. Two coding schemes are investigated that achieve good performance for this scenario.