Note the new location for the seminar.


Thursday, February 26th 2004.
Room Packard 202

 Utility maximization, routing, fairness

 

Prof. Steven Low

California Institute of Technology

About the talk:
 
It turns out that TCP-AQM can be interpreted as a distributed primal-dual algorithm over the Internet to maximize aggregate utility over source rates.   Indeed an allocation policy can be defined in terms of a class of utility funtions characterized by a scalar parameter alpha.  A allocation is fair if alpha is large, and efficient if the aggregate source rate is large.  All examples in the literature suggest that a fair allocation is necessarily inefficient.  We characterize exactly the tradeoff between fairness and throughput in general networks. The characterization allows us both to produce the first counter-example and trivially explain all the previous supporting examples. Surprisingly, the class of networks in our counter-example is such that a fairer allocation is always more efficient.   CHOKe is a stateless AQM to protect TCP flows against unresponsive flows.   We present a simple model that predicts the throughput behavior of CHOKe, and explains the spatial characteristics of the queue, the underlying mechanism through which CHOKe protects TCP.

Will TCP-AQM/IP turn out to maximize aggretate utility over both source rates and routes? We show that the problem is NP-hard and therefore cannot be solved by minimum cost routing in general.  We exhibit inevitable tradeoff between routing stability and achievable utility.

(Joint work with J. Doyle, L. Li, A. Tang, J. Wang)

About the speaker:
 
Steven. H. Low received his B.S. degree from Cornell University and PhD from the University of California -- Berkeley, both in electrical engineering.  He was with AT\&T Bell Laboratories, Murray Hill, from 1992 to 1996 and with the University of Melbourne, Australia, from 1996 to 2000. He is now an Associate Professor at the California Institute of Technology, Pasadena. He was a co-recipient of the IEEE William R. Bennett Prize Paper Award in 1997 and the 1996 R&D 100 Award. He is on the editorial boards of IEEE/ACM Transactions on Networking and Computer Networks Journal.  He has been a guest editor of the IEEE Journal on Selected Areas in Communications, and on the program committee of major conferences.  His research interests are in the control and optimization of networks and protocols.  His home is netlab.caltech.edu and email is slow@caltech.edu.