Summary

  • Proportional fairness is a counterfactual property of an entire feasible rate vector. It asks whether any alternative allocation can produce a positive aggregate of relative changes from the chosen rates. A single flow's throughput cannot answer that question.
  • Frank Kelly's 1997 model separated user utility from the network's capacity-constrained allocation. The 1998 paper with Aman Maulloo and David Tan then connected a weighted logarithmic objective to decentralised primal and dual rate-control algorithms.
  • Shadow prices and Lyapunov stability are disciplined model evidence, not deployment receipts. Their meaning depends on flow identity, weights, route and capacity assumptions, feedback functions, delay and stochastic behaviour; none automatically proves a retail charge, low latency or Internet-wide adoption.

Fairness was not written on either flow

Imagine two elastic transfers sharing a bottleneck. One receives six units of rate and the other four. The first can report six. The second can report four. Neither observation reveals whether another feasible allocation exists that would improve the total balance of relative gains and losses.

Proportional fairness begins with that missing comparison. For a chosen allocation, take any other feasible allocation. For every flow, measure the proposed change as a fraction of its chosen rate, then add those fractions. The chosen vector is proportionally fair if that sum can never be positive. The test does not ask whether one flow is satisfied. It asks whether the whole vector can be displaced by an alternative whose aggregate percentage gain is positive.

At a single bottleneck with equal weights and otherwise simple conditions, the result may indeed give equal rates. That familiar case is easy to mistake for the definition. It is not. When routes traverse different resources, weights differ or the feasible region changes, a proportionally fair allocation need not look equal. The word “proportional” describes the changes being compared, not a promise that capacity will be divided in visually matching shares.

This is why one rate cannot prove fairness. The evidence object includes every relevant rate, the feasible alternatives, the route-resource matrix and the capacities that define what “feasible” means. Change the flow identities or allow one user to split itself into several apparent flows, and the optimization problem changes before any algorithm runs.

The 1997 model separated desire from capacity

Kelly's corrected 1997 paper, Charging and rate control for elastic traffic, starts with increasing, strictly concave utility functions for users and finite capacities for network resources. It calls traffic elastic when a user's value can be represented as a function of an adjustable rate. Aggregate utility is then maximised subject to the routes and link capacities.

That formulation is deliberately abstract. The network does not need to know each utility function in the proposed decomposition. A user solves a local problem; the network solves a capacity-constrained allocation problem. Lagrange multipliers connect the two. A multiplier at a constrained link can be interpreted as the implied cost of another unit of flow or as the shadow price of additional capacity.

The paper also studies a preferred version in which a user chooses a charge per unit time and the network assigns rate so that rates per unit charge are proportionally fair. When user choices and network allocation meet in equilibrium, the system optimum can emerge. The result is not a factual claim that subscribers in 1997 declared their utilities or received such bills. It is a model of how private preferences and shared constraints can be decomposed without giving one central actor every utility function.

That distinction prevents two common errors. A shadow price is not necessarily money collected. It is first an optimization variable marking scarcity inside a constrained problem. And “willingness to pay” is not an identity-neutral fact. If weights encode payment, priority or some other entitlement, whoever defines the weight has already made a governance decision about what counts.

Kelly, Maulloo and Tan gave the objective two local mechanisms

The 1998 paper Rate control for communication networks: shadow prices, proportional fairness and stability is jointly authored by Frank Kelly, Aman Maulloo and David Tan. It asks how proportional fairness could be approached in a large network without a reliable central solver whose communications would themselves be exposed to delay and failure.

Their network problem maximises a weighted sum of logarithmic rates under capacity constraints. The logarithm matters because its derivative turns an absolute rate change into a relative one. The Lagrangian decomposes the global constraint into local terms associated with resources and routes.

The primal view keeps much of the averaging at the endpoints. A resource produces congestion indications as its load rises; a source increases steadily and reduces in response to the feedback it receives. The paper relates this family to additive-increase and multiplicative-decrease thinking without claiming that every real TCP instance exactly implements the mathematical system.

The dual view makes the resource's scarcity signal more explicit. A resource adjusts a shadow price according to excess demand, while a route's rate responds to the sum of resource prices along it. Economists may recognise a tâtonnement process; operators may see a feedback loop. In either vocabulary, no node computes the entire allocation. Local measurements and reactions collectively move the vector.

These are two mechanisms attached to one objective, not interchangeable packet formats. A primal receipt must show which congestion indications reached which source and how the source reacted. A dual receipt must show which resource prices were computed, how they were combined over a route and which explicit rate followed. Merely observing the final throughput hides the path by which the allocation was selected.

The proof depended on a visible model boundary

Under stated regularity assumptions, Kelly, Maulloo and Tan construct a function that acts as a Lyapunov function for their differential-equation system. It increases toward a stable point and connects the behaviour of local rate updates to a relaxed version of the network optimization problem. That is powerful evidence: a decentralised process is not merely hoped to behave globally; the model supplies a mathematical witness for convergence.

The paper is equally valuable for what it does not hide. The first continuous system omits stochastic perturbations and time lags. The authors then examine small random disturbances and delayed feedback. Faster gain can produce quicker convergence while increasing variation around equilibrium; a steeper response can improve one aspect and compromise stability when lags are present. If a price function is not increasing, an interior maximum may disappear or multiple stationary points may appear.

Frank Kelly's later review makes the boundary still clearer. An individual flow knows its own congestion experience and feedback delay, not the number of competing flows or even every resource on its path. Delay instability and stochastic instability impose different constraints. Primal and dual schemes may trade fairness against utilisation, and later results belong to a much wider research community.

A Lyapunov function is therefore a receipt for a specified dynamical system. It is not proof that arbitrary queues, RTTs, route changes, short flows, strategic senders and implementation errors will preserve the same behaviour. Nor does convergence to an equilibrium certify low delay, low loss or application value during the journey.

The fairness unit was also a control decision

The papers' weighted constructions expose a difficulty that modern systems still face. If one user can present itself as several users, the allocator may grant it several shares. If an operator aggregates many users into one flow, the same people may receive one share. Neither outcome can be judged from rate vectors until the identity boundary is stated.

Weights intensify the question. A weight may represent a chosen payment, a cooperative resource entitlement or another policy variable. Different interpretations can generate the same algebra and very different institutions. An allocation can be proportionally fair with respect to the declared weights while the weight-setting process remains opaque or contested.

The evidence must therefore name both the mathematical subject and the operational principal. Is fairness being measured among TCP connections, five-tuples, subscribers, applications, organisations or routes? Can one principal create more subjects cheaply? Who chooses a weight, and can another party audit it? Which capacities and routes were treated as fixed while the allocation was calculated?

Those questions do not invalidate proportional fairness. They locate its authority. The criterion can judge a vector under explicit premises. It cannot select the legitimate identities and entitlements that make the premises true.

Frank Kelly joined an objective to running reactions

The Royal Society records Kelly's work across random processes, networks, optimization and the self-regulation of large systems. His network papers endure because they connect three languages that are often kept apart: an economic account of utility and scarcity, an optimization account of constraints and multipliers, and an engineering account of feedback and stability.

The connection should be attributed carefully. The 1998 rate-control paper belongs to Kelly, Maulloo and Tan. Its antecedents include congestion-control and fairness work by many others, and the later network-utility-maximization literature is collective. Recognition of Kelly's role does not turn him into the sole inventor of congestion control or of every algorithm later written in this framework.

Heng Lu's later Minimum Initial Specification principle supplies a useful present-day test, not a historical source. What must participants share for a fairness claim to be locally checked? They need common meanings for flow identity, capacity, feedback, weight and compatibility. They need not surrender every local utility or adopt one universal control law. Later change becomes real through running implementations and observable reactions, not through the declaration that an allocation is fair.

The lasting lesson is therefore stricter than a slogan. A global objective can be approached through local signals. But the claim survives only when the system keeps the receipts: whose flows were counted, which alternatives were feasible, what weights and constraints applied, what feedback moved the endpoints and how the dynamics behaved before equilibrium. Without them, “proportionally fair” is an attractive label attached to an invisible experiment.

Sources