The Successive Approximation Approach for NUM Frameworks with Elastic and Inelastic Traffic

Phuong Luu Vo, Nguyen H. Tran, Choong Seon HongarXiv 2011 · DOI · arXiv

TL;DR

This paper tackles the challenge of optimizing network resource allocation (Network Utility Maximization or NUM) when dealing with "inelastic" traffic (like real-time video streams) that doesn't behave nicely with standard convex optimization methods. They introduce a novel successive approximation algorithm that can efficiently find good solutions for these complex, non-convex problems, even in wireless networks with dynamic power and rate control.

What Problem Does This Paper Address?

The core problem is optimizing network resource allocation, a field known as Network Utility Maximization (NUM). Traditionally, NUM problems assume "elastic" traffic (like file downloads) where user satisfaction (utility) increases predictably with more bandwidth, and this relationship is mathematically "concave." This concavity makes optimization problems solvable with well-established, efficient algorithms. However, many modern applications involve "inelastic" traffic (e.g., video conferencing, online gaming) where the utility function is often sigmoidal and non-concave. This non-concavity transforms the NUM problem into a "non-convex optimization problem," which is notoriously difficult to solve, especially in a distributed manner where individual network components make decisions without a central controller. Existing methods often fail to converge or only find suboptimal solutions, particularly when network link capacities are limited. This paper aims to bridge this gap by providing a distributed algorithm that can handle both elastic and inelastic traffic, even under challenging network conditions.

Methods

The authors propose a "successive approximation" approach. The key idea is to transform the difficult non-convex problem into a series of simpler, convex problems that can be solved using standard distributed algorithms. Specifically, they leverage the property that the logarithm of a log-concave function is concave. By taking the logarithm of the utility functions and applying the arithmetic-geometric mean inequality, they create an approximate problem with a concave objective. This approximate problem can then be efficiently solved using dual decomposition and gradient projection methods, which are standard for convex optimization. The algorithm iteratively refines these approximations, with the solutions converging towards the KKT (Karush-Kuhn-Tucker) conditions of the original non-convex problem. They also extend this framework to a more complex scenario involving joint rate and power control in wireless networks, again by transforming non-convex capacity constraints into convex approximations.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using defined network topologies and utility functions.

Key Insights and Ideas

  • Logarithm as a Convexifier: Taking the logarithm of the utility function is a powerful technique to transform non-concave (but log-concave) functions into concave ones, making them amenable to standard optimization. This is a central insight for handling sigmoidal utilities.
  • Successive Approximation for Non-Convexity: The iterative nature of the algorithm, where each step solves a convex approximation of the previous step's problem, is crucial for tackling the inherent non-convexity. This allows for distributed computation and convergence.
  • Universality for Log-Concave Utilities: The proposed method is not limited to specific sigmoidal functions but can be applied to any utility function that is "log-concave," broadening its applicability.
  • Wireless Extension: Successfully extending the framework to joint rate and power control in wireless networks highlights its flexibility and practical relevance in dynamic environments.

Key Results

The paper demonstrates that their successive approximation algorithm:

  • Converges to Suboptimal Solutions: For all link capacities, the algorithm converges to a suboptimal solution of the original non-convex NUM problem.
  • Achieves Global Optimality in Simulations: In many experimental scenarios, the algorithm converges to the globally optimal solution, outperforming standard dual-based algorithms that may fail to converge or find only suboptimal solutions, especially under "under-provisioning" (limited link capacity).
  • Handles Inelastic Traffic Effectively: The algorithm shows convergence for networks with inelastic traffic, which is a significant improvement over methods that rely on concave utilities.
  • Wireless Performance: In wireless network experiments, the algorithm successfully allocates rates and power, demonstrating its effectiveness in more complex, dynamic environments.

Limitations and Future Work

  • Suboptimal vs. Global Optimum: While the paper shows convergence to the KKT conditions and often global optimum in simulations, the theoretical guarantee is for convergence to a suboptimal solution. The conditions under which it always achieves the global optimum are not fully elaborated beyond experimental observations.
  • Convergence Speed: The paper mentions using diminishing step-sizes for convergence, but a detailed analysis of the convergence rate of the successive approximation algorithm itself is not the primary focus.
  • Practical Implementation Details: While the algorithm is designed for distributed implementation, specific challenges in real-world network deployment (e.g., communication overhead, synchronization) are not deeply explored.

Future work could involve more rigorous theoretical analysis of global optimality guarantees, detailed convergence rate analysis, and exploring practical implementation aspects for large-scale networks. The authors also suggest that the techniques can be applied to other log-concave utilities, implying further exploration of different utility function types.

Summary updated

Abstract

The concave utility in the Network Utility Maximization (NUM) problem is only suitable for elastic flows. However, the networks with the multiclass traffic, the utility of inelastic traffic is usually represented by the sigmoidal function which is a nonconcave function. Hence, the basic NUM problem becomes a nonconvex optimization problem. Solving the nonconvex NUM distributively is a difficult problem. The current works utilize the standard dual-based algorithm for the convex NUM and find the criteria for the global optimal convergence of the algorithm. It turns out that the link capacity must higher than a certain value to achieve the global optimum. We propose a new distributed algorithm that converges to the suboptimal solution of the nonconvex NUM for all of link capacity. We approximate the logarithm of the original problem to the convex problem which is solved efficiently by the standard dual-base distributed algorithm. After a sequence of approximations, the solutions converge to the KKT solution of the original problem. In many of our experiments, it also converges to the global optimal solution of the NUM. Moreover, we extend our work to solve the joint rate and power NUM problem with elastic and inelastic traffic in a wireless network. Our techniques can be applied to any log-concave utilities.
BibTeX
@misc{vo2011successive,
  author = {Phuong Luu Vo and Nguyen H. Tran and Choong Seon Hong},
  title = {{The Successive Approximation Approach for NUM Frameworks with Elastic and Inelastic Traffic}},
  year = {2011},
  eprint = {1108.3732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1108.3732},
}
Figure