IEEE Transactions on Automatic Control, Vol.49, No.6, 976-981, 2004
Pricing and congestion management in a network with heterogeneous users
This note presents 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. Following Kelly et al. (1998), we introduce dynamic rate-control algorithms, based on the users' utility functions and delay sensitivities, as well as tolls charged by the system, and examine the behavior of these algorithms. We show that allowing heterogeneity with respect to delay sensitivity introduces a fundamental nonconvexity into the congestion-cost functions. As a result, there are often multiple stationary points of the aggregate net utility function. 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. Moreover, the dynamic rate-control algorithm may converge to a local rather than global maximum, depending on the starting point. We present examples with different user utility functions, including some in which the only interior stationary point is a saddlepoint which is dominated by all the single-user optimal allocations. We also consider variants of the dynamic algorithm and their performance in a network with heterogeneous users. Our results suggest that applying a rate-control algorithm such as TCP (Transmission Control Protocol), even when augmented by some form of implicit or explicit pricing, may have unexpected and perhaps undesirable effects on the allocation of flows among heterogeneous delay-sensitive users.
Keywords:communication network;congestion pricing;dynamic rate-control algorithm;elastic users;heterogeneous users