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

45 Scopus citations

Abstract

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
Pages2679-2690
Number of pages12
DOIs
StatePublished - Oct 7 2005
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

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

Other

OtherIEEE INFOCOM 2005
CountryUnited States
CityMiami, FL
Period3/13/053/17/05

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint 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

    Chiang, M., Zhang, S., & Hande, P. (2005). Distributed rate allocation for inelastic flows: Optimization frameworks, optimality conditions, and optimal algorithms. In K. Makki, & E. Knightly (Eds.), Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 2679-2690). (Proceedings - IEEE INFOCOM; Vol. 4). https://doi.org/10.1109/INFCOM.2005.1498551