Spring 2002

ME/IE 8773-8774

PRICING AND CONGESTION MANAGEMENT IN A NETWORK WITH HETEROGENEOUS USERS

by

Shaler Stidham
Professor, Department of Operations Research
University of North Carolina-Chapel Hill

Wednesday, May 1, 2002
3:30-4:30 p.m.
Room 108 ME
Broadcast on UNITE Channel A
Coffee and cookies will be available in 125 ME following the seminar

We consider an economic model for a communication network with utility-maximizing elastic users who adapt to congestion by adjusting their flows. Users are heterogeneous with respect to both the utility they attach to different levels of flow and their sensitivity to delay or other measures of congestion. Following Kelly at al, we introduce dynamical rate-control algorithms, based on the users' utility functions and delay sensitivities, as well as tolls charged by the system, and examine their behavior. (These algorithms model some of the features of the TCP/IP protocol used by the Internet.) We show that allowing heterogeneity with respect to delay sensitivity introduces a fundamental non-convexity into the congestion-cost functions. As a result, there are typically multiple stationary points of the social objective function (total net utility for all users). Hence marginal-cost pricing -- equating users' marginal utilities to their marginal costs -- may identify a local maximum or even a saddle point, rather than a global maximum. We present a simple example in which the only interior stationary point is a saddlepoint, which is dominated by all the single-user optimal allocations. Thus, heterogeneity of users can lead to class dominance: a situation in which the system is dominated by a single user or class of users under an optimal flow allocation. It follows that the dynamical-system rate-control algorithm may converge to a local maximum or saddlepoint rather than a global maximum, depending on the starting point.

The main focus of Dr. Stidham's research has been on optimal design and control and distribution-free analysis of queues and other stochastic systems, with special emphasis on stochastic networks. He is particularly interested in applications to computer/communication systems, revenue management, and finance. His research has been supported by N.Y. State Science and Technology Foundation, U.S. Department of Transportation, Statens Samfundsvidenskabelige Forskningsraad (Denmark), National Science Foundation, N.C. Department of Corrections, NATO, Science and Engineering Research Council (U.K.), U.S. Army Research Office, IBM, Centre Internationale des Etudiants et Stagiares (France), and INRIA (France). He has held visiting positions at Aarhus University (Denmark), Stanford University, Technical University of Denmark, Bell Laboratories, University of Cambridge, INRIA Sophia Antipolis (France), and Australian National University. He has been Associate Editor of Management Science and Operations Research, Area Editor for Stochastic Processes for Operations Research, and is currently Associate Editor of QUESTA. He was program co-chair of the Conference on Applied Probability (Chapel Hill, 1988) and the TIMS XXIX International Meeting (Osaka, 1989). In 1990-91 he served as chair of the TIMS/ORSA College/Technical Section on Applied Probability. He is currently chair of the Expository Writing Award committee of INFORMS. Dr. Stidham has been a keynote speaker at conferences in the U.S., Germany, Japan, and the Netherlands. He is author of over 60 refereed or invited papers. His book, Sample-Path Analysis of Queueing Systems (co-authored with M. El-Taha) was awarded the 1999 Best Publication Award by the Applied Probability Society of INFORMS.

Informal Faculty Luncheon: Wednesday, May 1, 2002, 12:00 noon Prof. Stidham will be able to attend.