PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural properties of proportional fairness: stability and insensitivity

Laurent Massoulié

arXiv:0707.4542v1math.PR

TL;DR

The paper addresses how network bandwidth allocation can combine maximal stability with insensitivity, while retaining the implementability of proportional fairness. It characterizes proportional fairness through convex duality, proves ergodicity for more general routed dynamics, and introduces a reversible modification with matching large-deviations behavior relative to balanced fairness. These results support proportional fairness as an attractive allocation criterion combining implementation, performance, and insensitivity.

  • Problem

    Existing utility-based allocations are implementable and stable but do not appear insensitive, whereas balanced fairness is insensitive but lacks a generally known simple distributed implementation.

  • Method

    The paper characterizes proportional fairness using the Fenchel–Legendre transform of the capacity region, uses a Lyapunov function for stability, and constructs modified proportional fairness.

  • Results

    Modified proportional fairness is asymptotically aligned with proportional fairness, reversible and insensitive, while its stationary distributions share large-deviations characteristics with balanced fairness; proportional fairness is ergodic under Markovian users routing.

  • Takeaways & Limitations

    Proportional fairness combines distributed implementability with stability, phase-type robustness, performance, and an asymptotic connection to insensitive allocation criteria.

  • Takeaways & Limitations

    The paper does not establish the existence of the balanced-fairness scaling limit in general, except when |R| = 2.

Abstract

from arXiv · show

In this article we provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel--Legendre transform of the network capacity region. We use this characterization to prove stability (i.e., ergodicity) of network dynamics under proportionally fair sharing, by exhibiting a suitable Lyapunov function. Our stability result extends previously known results to a more general model including Markovian users routing. In particular, it implies that the stability condition previously known under exponential service time distributions remains valid under so-called phase-type service time distributions. We then exhibit a modification of proportional fairness, which coincides with it in some asymptotic sense, is reversible (and thus insensitive), and has explicit stationary distribution. Finally we show that the stationary distributions under modified proportional fairness and balanced fairness, a sharing criterion proposed because of its insensitivity properties, admit the same large deviations characteristics. These results show that proportional fairness is an attractive bandwidth allocation criterion, combining the desirable properties of ease of implementation with performance and insensitivity.

1. Introduction.

Network bandwidth allocation is motivated by both static fairness principles and dynamic performance requirements. The paper develops proportional fairness as an implementable criterion with stability, phase-type robustness, and a close asymptotic relationship to insensitive allocation schemes.

  • Network model: Network bandwidth allocation assigns aggregate rates to user types subject to a convex capacity region representing physical network constraints.The capacity region can model fixed routes, multiple routes, and more general convex constraints.
  • Motivation: Proportional fairness is supported by utility-decomposition and bargaining-theoretic rationales, including Nash’s four allocation axioms.The cited axioms are affine-transformation invariance, Pareto optimality, independence of irrelevant alternatives, and symmetry.
  • Dynamic requirements: Dynamic network models require stability, and ergodicity is impossible when load lies outside the capacity region or on its boundary.When load lies in the interior, prior Lyapunov-based results establish ergodicity for all (w,α)-fair criteria.
  • Dynamic requirements: Insensitivity requires stationary user-count distributions to remain unchanged when service-time distributions change while their means remain fixed.This property extends stability under natural conditions from exponential to phase-type service times.
  • Paper contribution: The resulting combination of distributed implementability, performance, and insensitivity makes proportional fairness an attractive default allocation criterion.The paper connects this assessment to decomposition, bargaining axioms, and approximation to balanced fairness.
  • Paper contribution: The paper introduces modified proportional fairness, which is reversible and insensitive while coinciding asymptotically with proportional fairness.Its stationary distributions and those of balanced fairness share the same large-deviations characteristics.

2. Characterization of proportional fairness via convex duality.

The paper characterizes proportional fairness through the Fenchel–Legendre conjugate of the capacity-set indicator, yielding a compact description of the allocation map. This convex-duality framework supports stability analysis and motivates modified proportional fairness, whose stationary behavior is explicitly tractable.

  • Convex-duality setup: The capacity region is transformed into logarithmic allocation coordinates, with K containing the feasible logarithms of allocated capacities.The paper works with γr = log λr rather than λr directly.
  • Convex-duality setup: The Fenchel–Legendre conjugate of the indicator δK provides the convex function used to characterize proportional fairness.The indicator δK is zero on K and +∞ outside K.
  • Convex-duality setup: The paper gives a compact characterization of the proportional-fair allocation map through this convex-dual construction.The resulting characterization connects the allocation vector to subgradients and gradients of the conjugate.
  • Properties of the allocation map: On the strictly positive orthant, the proportional-fair allocation is uniquely defined and varies continuously with the state.Strict concavity gives uniqueness, while differentiability of the conjugate identifies the allocation with its gradient.
  • Modified proportional fairness: Modified proportional fairness is introduced as an alternative allocation rule, and its stationary measure can be normalized under the stability condition to yield ergodicity.The paper also conjectures that proportional fairness and modified proportional fairness share the same large-deviations rate function after rescaling.
  • Stability application: The convex-duality characterization is applied to fluid limits, where the function L serves as a Lyapunov function for proving stability under the natural load condition.The resulting stability statement concerns the original Markov process through the fluid-limit approach.

3. Stability properties of proportional fairness.

The section characterizes fluid limits for proportional-fair network dynamics and uses a Lyapunov function to establish ergodicity under the stated stability condition.

  • Fluid-limit approach: The stability proof applies fluid-limit methods to the Markov process describing user populations under proportional fairness.The function L defined earlier is used as a Lyapunov function for the fluid limits.
  • Stability conclusion: Theorem 1 concludes that the Markov process with Markovian user routing is ergodic under condition (8).The proof uses the fluid-limit characterization and the Lyapunov decrease property.
  • Fluid-limit approach: Fluid trajectories are defined through nondecreasing, Lipschitz-continuous cumulative functions governing the user dynamics.The trajectory set S(x) contains continuous trajectories with initial condition x, but uniqueness is not established.
  • Fluid-limit approach: Rescaled processes converge in probability, uniformly on compact time intervals, to the set of fluid trajectories with the corresponding initial condition.This convergence is stated for sequences whose rescaled initial conditions converge.
  • Lyapunov decrease: Under the stability condition, the Lyapunov function decreases by at least ε after a fixed positive time from any state normalized by L(x(0)) = 1.Theorem 3 supplies the uniform decrease needed to prove stability of the original process.

4. Application to phase-type service distributions.

The phase-type model represents each service as transitions among finitely many exponential phases, allowing the general Markovian-routing stability result to apply. Consequently, proportional-fair allocation is ergodic under the usual load condition based on mean service times.

  • Phase-type model: Phase-type service times are modeled as successive visits to finitely many phases, with exponential holding times and probabilistic transitions between phases.An initial phase distribution specifies where service begins.
  • Reduction to Markovian routing: Each class-phase pair becomes a class in a Markov process covered by the general ergodicity theorem.External arrivals, service parameters, routing probabilities, and the expanded capacity set are defined from the original phase-type model.
  • Stability conclusion: Theorem 5 states that proportional-fair allocation is ergodic for Poisson arrivals and phase-type service distributions when ρr = νrσr satisfies the usual condition (8).This extends the stability conclusion from exponential service times to phase-type service times.
  • Load condition: The aggregate phase visits yield the mean service time σr for each original class r.The sum over visits to phases equals νrσr, completing the load calculation.

5. Relationships between balanced fairness and proportional fairness.

This section characterizes balanced fairness through an inductively defined balance function and relates its stationary distribution to modified proportional fairness. It also establishes asymptotic agreement and shared large-deviation behavior with proportional fairness.

  • Balanced fairness: Balanced fairness is defined through a balance function ψ constructed inductively over nonnegative user-count vectors.The construction starts from ψ(0)=1 and sets ψ(x)=0 outside the nonnegative orthant.
  • Balanced fairness: The logarithmic allocation vector γBF(x) is represented by discrete increments of φ(x)=−logψ(x), acting as an approximate gradient.The discrete-gradient representation links balanced-fair allocations to the function governing the stationary measure.
  • Stationarity: The reversible process has an explicit stationary measure expressed through φ, and the same measure remains stationary under Markovian routing.The routing extension follows as a consequence of reversibility.
  • Characterization: The function φ admits an alternative optimization characterization, established by induction using monotonicity and the defining constraints.The proof compares φ with the optimization value and shows equality recursively over x.
  • Asymptotic relationship: The balanced-fairness stationary distribution has large-deviation asymptotics governed by the Lyapunov function L used for proportional fairness.The paper concludes that it therefore shares the same large-deviation characteristics as the stationary distribution under modified proportional fairness.
  • Asymptotic relationship: If the scaled balanced-fair allocation converges, its limit equals the proportional-fair allocation; existence is established only when |R|=2.The authors state that existence in more general cases remains unproved, although plausible.

APPENDIX A: PROOF OF THEOREM 2

This appendix proves Theorem 2 by showing that scaled stochastic trajectories have fluid-trajectory accumulation points. Compactness, continuity, and Poisson-process bounds provide the required convergence argument.

  • Stochastic control: Poisson-process maximal-deviation bounds control stochastic fluctuations around their means during the scaling argument.The bound uses the Cramér transform of a unit-mean centered Poisson random variable.
  • Compactness: Uniform control and subsequence extraction yield Lipschitz limits for rescaled trajectory components.A variation of Arzelà–Ascoli supplies uniformly convergent subsequences on every finite interval.
  • Continuity: The proportional-fair allocation is continuous at states whose corresponding coordinates are positive.This continuity is used when passing limits through the allocation terms.
  • Identification of limits: At differentiability points, dominated convergence identifies derivatives of the limiting integrated processes with proportional-fair allocations.The positive-coordinate case uses Lipschitz continuity of trajectories and continuity of the allocation function.
  • Identification of limits: For coordinates equal to zero, upper-semicontinuity and nonnegativity constrain the corresponding derivatives.These boundary arguments complete the verification that the limits satisfy the fluid dynamics.
  • Conclusion: Because every subsequential limit is a fluid trajectory, the assumed contrary behavior contradicts the fluid-limit result and proves Theorem 2.The contradiction is obtained after extracting a further subsequence converging uniformly on finite intervals.

APPENDIX B: PROOF OF LEMMA 5

This appendix proves Lemma 5 by analyzing fluid trajectories with zero and positive coordinates and by reducing routing through states with zero populations. The reduced routing matrix has a unique solution because its relevant spectral radius is below one.

  • Fluid-trajectory analysis: The proof separates active coordinates from the zero-coordinate set I and analyzes the resulting fluid derivatives.For positive coordinates, the derivative is identified with the proportional-fair allocation; zero coordinates require one-sided bounds.
  • Reduced routing: Removing excursions into I produces a reduced routing matrix that captures the next visit among the remaining states.Its entries represent transition probabilities after eliminating intermediate visits to zero-population states.
  • Reduced routing: The submatrix (P^T)II has spectral radius strictly below one, ensuring a unique solution for the associated zero-coordinate derivatives.Otherwise the original routing matrix would have spectral radius at least one.
  • Reduced routing: The reduced-chain interpretation preserves mean visit counts to the active states after excursions into I are removed.This probabilistic identity establishes the needed relation between the original and reduced routing descriptions.
  • Inequality bounds: The remaining inequalities follow by combining continuity of proportional-fair allocations, nonnegativity, and bounds on the fluid derivatives.The proof treats positive and zero coordinates separately before combining the resulting estimates.

APPENDIX C: PROOF OF LEMMA 6

This appendix establishes the variation-based analytic result needed in the paper by decomposing a continuous function into increasing and decreasing variation. Measure decomposition and almost-everywhere differentiability complete the proof.

  • Differentiability: Almost-everywhere differentiability of the continuous function and its variation components yields the announced derivative relation.The proof uses the derivative of the increasing component and the analogous decomposition for the decreasing component.
  • Variation decomposition: The proof introduces increasing variation V+ as the supremum of increments over finite partitions.The same partition-based construction is used to characterize variation over arbitrary subintervals.
  • Variation decomposition: The relevant variation functions are nondecreasing, allowing them to define associated nonnegative measures.This measure-theoretic representation supports the subsequent decomposition.
  • Measure decomposition: Radon–Nikodym decomposition splits the measure into an absolutely continuous component and a singular component supported on a null Lebesgue-measure set.The density of the absolutely continuous part is denoted g−(t).

APPENDIX D: PROOF OF LEMMA 7

The appendix proves Lemma 7 by reducing its inequality to a Hoeffding-type inequality for identically distributed random variables and then characterizing the equality case. The proof also establishes sign-based reductions and a generalization replacing the exponential term with a strictly increasing function.

  • Sign reduction: The expansion establishes that the last two terms are nonnegative and permits restricting claims (i) and (iii) to variables u_s having the same sign.This reduction follows from the sign decomposition involving (e^{u_s}−1)^±u_s^∓.
  • Remaining inequality: The proof verifies the remaining condition by replacing M with N in the left-hand side, using the nonnegativity of their difference under the common-sign assumption.It then reduces the argument to an inequality involving N and notes that N has coinciding marginals.
  • Inequality proof: The proof reduces the needed inequality to Hoeffding’s inequality for identically distributed random variables and nondecreasing functions.It uses f(U)=U and g(U)=e^U−1; finiteness of variances follows because the variables take finitely many values.
  • Equality case: Equality in the key inequality forces the joint distributions of (U,V) and (U,U) to coincide, partitioning the support so cross-partition terms vanish.Because f and g are strictly increasing, equality in the transformed inequality implies equality of these joint distributions.
  • Equality case: The equality conditions ultimately require u_r=u_s wherever r_s>0 and then u_r(e^{u_r}−1)=0, yielding u_r=0.The final condition completes the proof of the lemma.
  • Generalization: Lemma 7 remains valid when e^{u_s}−1 is replaced by any strictly increasing function f satisfying f(0)=0.This is stated as Remark A.1.
Loading 0707.4542v1…