Distributed rate allocation for inelastic flows

Prashanth Hande, Shengyu Zhang, Mung Chiang

Research output: Contribution to journalArticle

109 Scopus citations

Abstract

A common assumption behind most of the recent research on network rate allocation is that traffic flows are elastic, which means that their utility functions are concave and continuous and that there is no hard limit on the rate allocated to each flow. These critical assumptions lead to the tractability of the analytic models for rate allocation based on network utility maximization, but also limit the applicability of the resulting rate allocation protocols. This paper focuses on inelastic flows and removes these restrictive and often invalid assumptions. First, we consider nonconcave utility functions, which turn utility maximization into difficult, nonconvex optimization problems. We present conditions under which the 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.We then show how to provision link capacity to guarantee convergence of the standard distributed algorithm. Second, we model real-time flow utilities as discontinuous functions. We show how link capacity can be provisioned to allow admission of all real-time flows, then propose a price-based admission control heuristics when such link capacity provisioning is impossible, and finally develop an optimal distributed algorithm to allocate rates between elastic and real-time flows.

Original languageEnglish (US)
Pages (from-to)1240-1253
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume15
Issue number6
DOIs
StatePublished - Dec 1 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Capacity provisioning
  • Congestion control
  • Inelastic flow
  • Network control by pricing
  • Network utility maximization
  • Optimization
  • Resource allocation
  • Telecommunication congestion control
  • Telecommunication network management
  • Telecommunication traffic

Fingerprint Dive into the research topics of 'Distributed rate allocation for inelastic flows'. Together they form a unique fingerprint.

  • Cite this