PaperlayerView exact revision on arXiv

Source-linked AI summary

Delay Reduction via Lagrange Multipliers in Stochastic Network Optimization

Longbo Huang, Michael J. Neely

arXiv:0904.3795v1math.OC

TL;DR

The paper addresses excessive delay in stochastic network utility optimization, where QLA can approach optimal utility with large backlogs. It analyzes QLA’s backlog attractor and develops FQLA, obtaining logarithmic delay for discrete actions and a square-root tradeoff for continuous actions while retaining near-optimal utility.

  • Problem

    QLA can achieve an O(1/V) utility gap but incur O(V) network delay, motivating methods that reduce delay in stochastic network optimization.

  • Method

    The paper identifies a deterministic problem whose dual optimum attracts QLA backlogs and uses this insight to construct Fast Quadratic Lyapunov based Algorithms.

  • Results

    FQLA achieves within O(1/V) of optimal utility with O(log^2(V)) delay for discrete action options and a square-root performance-delay tradeoff for continuous options.

  • Takeaways & Limitations

    The results show that quadratic-Lyapunov algorithms can approach strong performance-delay tradeoffs while highlighting a “network gravity” role for Lagrange multipliers in scheduling.

Abstract

from arXiv · show

In this paper, we consider the problem of reducing network delay in stochastic network utility optimization problems. We start by studying the recently proposed quadratic Lyapunov function based algorithms (QLA). We show that for every stochastic problem, there is a corresponding \emph{deterministic} problem, whose dual optimal solution "exponentially attracts" the network backlog process under QLA. In particular, the probability that the backlog vector under QLA deviates from the attractor is exponentially decreasing in their Euclidean distance. This not only helps to explain how QLA achieves the desired performance but also suggests that one can roughly "subtract out" a Lagrange multiplier from the system induced by QLA. We thus develop a family of \emph{Fast Quadratic Lyapunov based Algorithms} (FQLA) that achieve an $[O(1/V), O(\log^2(V))]$ performance-delay tradeoff for problems with a discrete set of action options, and achieve a square-root tradeoff for continuous problems. This is similar to the optimal performance-delay tradeoffs achieved in prior work by Neely (2007) via drift-steering methods, and shows that QLA algorithms can also be used to approach such performance. These results highlight the "network gravity" role of Lagrange Multipliers in network scheduling. This role can be viewed as the counterpart of the "shadow price" role of Lagrange Multipliers in flow regulation for classic flow-based network problems.

I. INTRODUCTION

The paper studies delay in stochastic network utility optimization by analyzing QLA, showing that backlogs concentrate around a deterministic dual attractor and motivating FQLA algorithms with improved performance-delay tradeoffs.

  • I. INTRODUCTION: Prior QLA results obtain O(1/V) utility optimality gaps at the cost of O(V) network delay, motivating sharper backlog analysis.Earlier delay bounds focused on long-term average backlog rather than concentration around a fixed value.
  • I. INTRODUCTION: QLA typically keeps the backlog close to an attractor given by the dual optimum of a corresponding deterministic optimization problem.The deviation probability decreases exponentially with the backlog’s distance from the attractor.
  • I. INTRODUCTION: FQLA subtracts a Lagrange multiplier from the QLA-induced system to reduce delay while preserving near-optimal utility.The construction uses placeholder bits because much of the QLA backlog maintains the appropriate operating level.
  • I. INTRODUCTION: FQLA achieves an [O(1/V), O(log^2(V))] performance-delay tradeoff for discrete action sets and a square-root tradeoff for continuous action sets.These guarantees apply to general stochastic optimization problems under the stated action-set distinctions.
  • I. INTRODUCTION: The paper interprets Lagrange multipliers as providing “network gravity” in scheduling, extending their familiar role beyond flow regulation.FQLA’s relation to QLA supplies additional insight into this scheduling interpretation.

IV. QLA AND THE DETERMINISTIC PROBLEM

The section reviews QLA’s Lyapunov-drift construction and connects it to a deterministic optimization problem, its dual, and ordinary subgradient updates.

  • A. The QLA algorithm: QLA chooses each slot’s action by minimizing the Lyapunov-drift bound augmented with a V-weighted cost term.The controller observes the current network state and backlog, then solves the resulting state-dependent optimization.
  • B. The Deterministic Problem: The dual function q(U) is concave in the Lagrange multiplier vector, enabling efficient solution methods in settings with separable cost and rate functions.The deterministic problem itself need not be convex, so a duality gap may exist.
  • B. The Deterministic Problem: The deterministic problem fixes one action for each network state, whereas the stochastic problem may require time sharing across actions.Consequently, the deterministic formulation need not solve the stochastic problem directly.
  • B. The Deterministic Problem: The ordinary subgradient method updates the multiplier using a subgradient of q(U), providing an analysis tool for QLA’s steady-state backlog behavior.The paper uses this method to study how the backlog evolves relative to the optimal multiplier.
  • B. The Deterministic Problem: The optimal multiplier scales with V, while QLA’s time-average backlog and average cost are the performance quantities analyzed under the algorithm.The scaling result identifies V U*_0 as an optimal multiplier for the general-V formulation.

V. BACKLOG VECTOR BEHAVIOR UNDER QLA

Under QLA, the backlog is drawn toward the dual optimum of a deterministic problem, with deviation probabilities decreasing exponentially with distance. The attraction scale is O(log(V)) under local polyhedral structure and O(sqrt(V log(V))) under local smoothness.

  • A. When q0() is “locally polyhedral”: QLA makes the backlog typically remain within O(log(V)) of the scaled dual optimum under locally polyhedral conditions.The result also applies when the network state is a general time-homogeneous Markov process.
  • Implications: The attractor analysis explains QLA’s utility performance because staying near the dual optimum keeps selected actions close to optimal actions.The paper also uses the attractor backlog to motivate subtracting roughly the dual-optimal backlog in FQLA.
  • A. When q0() is “locally polyhedral”: The probability that backlog components deviate from the scaled dual optimum decreases exponentially with deviation distance.For large V, deviations larger than Θ(log(V)) are rare.
  • A. When q0() is “locally polyhedral”: For a single network state, the backlog converges to a Θ(1)-sized neighborhood of the scaled dual optimum under the stated condition.

B. When q0() is “locally smooth”

When the dual function is locally smooth, QLA still attracts backlog toward the scaled dual optimum, but the attraction is weaker than in the locally polyhedral case. The resulting concentration radius is O(sqrt(V log(V))).

  • B. When q0() is “locally smooth”: The locally smooth condition includes twice-differentiable dual functions with negative curvature and commonly arises with convex action sets.
  • B. When q0() is “locally smooth”: O(sqrt(V log(V))) is the typical distance between the backlog vector and the scaled dual optimum under local smoothness.This result holds for sufficiently large V under the theorem’s local smoothness condition.
  • B. When q0() is “locally smooth”: The paper contrasts the smooth-case radius O(sqrt(V log(V))) with the polyhedral-case radius O(log(V)).
  • B. When q0() is “locally smooth”: Local smoothness produces weaker attraction near the optimum because the drift toward the scaled dual optimum decreases as the backlog approaches it.

C. Implications of Theorem 1 and 4

The attractor results explain why QLA achieves near-optimal performance: its backlog stays near the deterministic optimum, so its chosen actions remain near optimal. The paper illustrates this for both continuous-rate and discrete-rate control.

  • C. Implications of Theorem 1 and 4: In the continuous-rate example, QLA almost always selects rates near the optimal rate and achieves average power Φ + O(1/V).
  • C. Implications of Theorem 1 and 4: The deterministic problem and KKT conditions identify the target backlog and optimal constant service rate used to interpret QLA’s behavior.
  • C. Implications of Theorem 1 and 4: With discrete rates {1/4, 1}, QLA alternates between the two rates with almost equal frequencies.
  • C. Implications of Theorem 1 and 4: QLA achieves near-optimal action selection because its backlog remains close to the scaled dual optimum, keeping chosen actions close to the optimal-action set.

VI. THE FQLA ALGORITHM

FQLA reduces QLA-induced delay by reserving place-holder bits below the backlog attractor while preserving QLA-like actions through a virtual backlog process.

  • FQLA: a Single Queue Example: The motivating QLA trajectory stays close to its Θ(V) attractor after roughly 1500 slots, motivating subtraction of a large baseline backlog.The example uses a 10^4-slot sample process and illustrates the backlog, virtual process, and threshold graphically.
  • FQLA: a Single Queue Example: A simple fixed threshold may remain Θ(V) below the attractor, so it cannot by itself achieve the desired delay reduction.The example notes that the threshold may need to be U*_V − Θ(V), leaving Θ(V) average backlog.
  • FQLA: a Single Queue Example: FQLA initializes place-holder bits and uses a virtual backlog process to emulate QLA while reducing the physical backlog.The virtual process tracks the backlog that QLA would have generated, and actions are modified when it falls below the place-holder threshold.
  • FQLA: a Single Queue Example: O(log^2(V)) place-holder-bit thresholds can reduce average backlog to O(log^2(V)) while retaining O(1/V) close-to-optimal utility.The construction uses a threshold near the attractor minus a logarithmic correction, and FQLA is almost always identical to QLA.
  • FQLA-Ideal and FQLA-General: FQLA-Ideal assumes the dual optimal attractor U*_V is known, whereas FQLA-General estimates it after running QLA for a long enough period.The supplied algorithm description also includes per-queue place-holder initialization and virtual-backlog-based action selection.
  • Implementation features: FQLA may drop packets when the virtual backlog falls below its threshold, although the paper distinguishes this compensation mechanism from drift-steering packet dropping.The paper states that the dropped fraction can be made arbitrarily small in settings where dropping is not otherwise available.

C. Performance of FQLA-Ideal

FQLA-Ideal preserves near-optimal average cost while reducing backlog through place-holder bits, relying on QLA’s concentration around the attractor and requiring a sufficiently large control parameter.

  • Performance mechanism: The attractor-concentration analysis bounds threshold violations and therefore controls both packet dropping and deviations from QLA actions.The supplied proof passages connect threshold violations to the event that FQLA differs from QLA and to the packet-drop fraction.
  • Performance mechanism: The construction works because the virtual backlog behaves like a QLA backlog process, which retains the O(1/V) average-cost guarantee.Its deviations below the threshold are sufficiently rare that FQLA performs almost the same actions as QLA based on the virtual backlog.
  • FQLA-General: FQLA-General estimates the attractor from a steady-state QLA sample and achieves the same guarantees with probability 1−O(1/V^4).The estimate is formed after an initial run of duration T, followed by threshold selection and the same place-holder-bit action procedure.
  • FQLA-General: FQLA-General uses thresholds close to max[U*_V,j−log^2(V),0], with the zero-attractor case handled by the maximum operator.The threshold construction is applied separately to each queue.

E. FQLA when q0() is locally smooth

For locally smooth dual functions, FQLA retains the logarithmic performance-delay tradeoff, while the single-queue analysis provides broader directional and probabilistic backlog guarantees.

  • FQLA when q0(U) is locally smooth: For locally smooth q0(U), FQLA-Ideal achieves an [O(1/V), O(log^2(V))] performance-delay tradeoff with controlled packet dropping.FQLA-General achieves the same tradeoff with probability 1−O(1/V^4) for an appropriate sampling duration.
  • When there is a single queue: In the single-queue setting, deterministic backlog bounds hold for arbitrary network-state distributions and state evolutions, including non-ergodic processes.The resulting probabilistic deviation bound has the same form as the general attractor results without requiring their additional conditions.
  • When there is a single queue: The single-queue analysis assumes a unique optimal solution for the deterministic problem when establishing the invariant interval result.The theorem states that once the backlog enters the interval, it remains there under QLA.
  • When there is a single queue: For i.i.d. states, QLA probabilistically moves the backlog toward the unique dual-optimal attractor, and for one state the movement is deterministic.The single-queue results describe the direction of backlog movement relative to the attractor.

B. Probabilistic bound of U(t)’s deviation from U ∗V

Theorem 9 establishes an exponential tail bound for deviations of the QLA backlog from the dual-optimal attractor, and simulations show FQLA behavior consistent with the predicted scaling.

  • P(d, m) ≤ a*e^-ρ*m bounds the probability that U(t) deviates from U*_V by more than d + m.Theorem 9 specifies positive constants d, a*, and ρ*, possibly dependent on V.
  • The proof strategy uses drift inequalities showing that states farther from U*_V have stronger drift toward the attractor.
  • When the relevant conditions hold globally, U(t) is mostly within O(log(V)) of U*_V.
  • FQLA simulations show average queue sizes close to 5 log^2(V), packet drops below 10^-4 for V ≥ 500, and average power near the optimal 3.75.The experiments use a five-queue power-allocation system and compare FQLA-Ideal with FQLA-General.

IX. LAGRANGE MULTIPLIER: “SHADOW PRICE” AND “NETWORK GRAVITY”

The paper connects Lagrange multipliers’ shadow-price role in flow regulation with backlog-driven scheduling in discrete networks, where backlogs act as network gravity.

  • Lagrange multipliers regulate flows as shadow prices in flow-based resource-allocation problems.
  • In discrete networks, backlog vectors act as network gravity for constructing optimal scheduling decisions.
  • QLA backlogs play the same role as Lagrange multipliers in a time-invariant network and relate closely to dual subgradient updates.
  • Given the same U(t) and state s_i, QLA and RISM choose actions identically under the stated update correspondence.The passage also notes that RISM selects states artificially, whereas the stochastic network observes physical states randomly.

APPENDIX A- PROOF OF LEMMA 2

The appendix proves Lemma 2 by relating queue updates to projected subgradient steps and then applying bounded-drift and conditional-expectation arguments.

  • The queueing dynamics obtain U(t + 1) by projecting U(t) − μ(t) onto the nonnegative orthant and adding A(t).
  • For a fixed network state, A(s_i)(t) − μ(s_i)(t) is a subgradient of the corresponding dual function at U(t).
  • The proof uses bounded increments and the nonexpansiveness of projection to control changes in the backlog process.
  • Conditioning on the history and current backlog, the argument averages state-specific dual quantities over a time interval before taking expectations.
  • Auxiliary exponential-drift bounds are established using Taylor expansion and properties of the function g(y).

APPENDIX C-PROOF OF LEMMA 3

The appendix proves Lemma 3 by induction, bounding the auxiliary process U_j(t) above and below relative to the shifted queue backlog W_j(t).

  • The upper bound is U_j(t) ≤ max[W_j(t) − W_j, 0] + δmax.
  • The induction separates cases according to whether W_j(k) is above or below its threshold W_j.
  • The lower bound is U_j(t) ≥ max[W_j(t) − W_j, 0].
  • When W_j(k) ≥ W_j, the shifted arrival equals the original arrival, supporting the inductive lower-bound step.
  • When W_j(k) < W_j, the proof uses the adjusted arrival expression and nonnegative queue terms to complete the induction.

APPENDIX D-PROOF OF LEMMA 4

The appendix proves Lemma 4 and related lemmas by comparing the QLA-selected action with the dual-function definitions and deriving inequalities that establish the stated parts.

  • Lemma 4: QLA minimizes the relevant conditional expected quantity for a given U(t) by selecting an action that achieves the infimum in (12).The proof compares this minimization with the definition of q(U) in (13).
  • Lemma 4: The proof establishes Lemma 4(b) after showing that the right-hand side of the derived inequality is non-positive.The argument then concludes explicitly that Part (b) follows.
Loading 0904.3795v1…