Distributed rate allocation for inelastic flows: Optimization frameworks, optimality conditions, and optimal algorithms

Mung Chiang, Shengyu Zhang, Prashanth Hande

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations


A common assumption behind most of the recent research on network utility maximization is that traffic flows are elastic, which implies that their utility functions are concave and there are no hard limits on the rate allocated to each flow. These critical assumptions lead to tractability of the analytic models of utility maximization, but also limits applicability of the resulting rate allocation protocols. This paper focuses on inelastic flows and removes these restrictive and often invalid assumptions. We present several optimization frameworks, optimality conditions, and optimal algorithms. First, we consider nonconcave utility functions, which turn utility maximization into nonconvex, constrained optimization problems that are well-known to be difficult. We present conditions under which the current standard price-based distributed algorithm can still converge to the globally optimal rate allocation despite nonconcavity of utility functions. In particular, continuity of price-based rate allocation at all the optimal prices is a sufficient condition for global convergence of rate allocation by the standard algorithm, and continuity at at least one optimal price is a necessary condition. In the second part of the paper, we provide a general problem formulation of rate allocation among time-sensitive flows from real-time and streaming applications, as well as a decomposition into subproblems coordinated by pricing. After simplifying the subproblems by leveraging the optimization structures, we highlight the difficult issues of causality and time-scale, and propose an effective price-based heuristics for admission control and an optimal algorithm for a special case formulation.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Number of pages12
StatePublished - 2005
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Country/TerritoryUnited States
CityMiami, FL

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


  • Congestion control
  • Network control by pricing
  • Network utility maximization
  • Optimization
  • Resource allocation


Dive into the research topics of 'Distributed rate allocation for inelastic flows: Optimization frameworks, optimality conditions, and optimal algorithms'. Together they form a unique fingerprint.

Cite this