Stability and benefits of suboptimal utility maximization

Tian Lan, Xiaojun Lin, Mung Chiang, Ruby B. Lee

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Network utility maximization has been widely used to model resource allocation and network architectures. However, in practice, often it cannot be solved optimally due to complexity reasons. Thus motivated, we address the following two questions in this paper: 1) Can suboptimal utility maximization maintain queue stability? 2) Can underoptimization of utility objective function in fact benefit other network design objectives? We quantify the following intuition: A resource allocation that is suboptimal with respect to a utility maximization formulation maintains maximum flow-level stability when the utility gap is sufficiently small and information delay is bounded, and it can still provide a guaranteed size of stability region otherwise. Utility-suboptimal rate allocation can also enhance other network performance metrics, e.g., it may reduce link saturation. These results provide a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

Original languageEnglish (US)
Article number5766796
Pages (from-to)1194-1207
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - Aug 2011

All Science Journal Classification (ASJC) codes

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


  • Network utility optimization
  • queueing analysis
  • stability analysis


Dive into the research topics of 'Stability and benefits of suboptimal utility maximization'. Together they form a unique fingerprint.

Cite this