Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 30 / 5 / Solution

Here $x_r$ is the rate per individual active flow, and $n_r{x}_r$ is its route's aggregate rate. On routes with $n_r>0$, a proportionally fair allocation is a feasible positive rate vector satisfyingfor every feasible competitor $\tilde{x}$, where feasibility means ${\sum }_{r:j\in r}{n}_r{\tilde{x}}_r\le C_j$. This is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$: its gradient gives the displayed inequality, and the supporting-tangent inequality proves sufficiency. The objective is strictly concave on active rates. Rates assigned to absent flows are irrelevant and may be set to zero.

For the linear flow network, an active local route can increase its rate if its link constraint has slack, improving the objective without affecting any other link. ThusPut $m={\sum }_{i=1}^I{n}_i$ and $N=n_0+m$. If $n_0>0$ and $m>0$, eliminate the active local rates by $x_i=(1-n_0{x}_0)/n_i$. Up to constants, the utility becomesIts derivative is $n_0/x_0-n_{0}m/(1-n_0{x}_0)$, which vanishes exactly atStrict concavity proves this is the optimum, and unused local links impose no stronger constraint because $n_0{x}_0\le 1$. If $m=0<n_0$, maximizing $n_0\log x_0$ gives $x_0=1/n_0$, the same formula. If $n_0=0$, each active local route has $x_i=1/n_i$. These are the proportionally fair allocation on a linear flow network. When $N=0$, there is no service to allocate.

The memoryless property of exponential document sizes makes a flow transmitting at rate $x_r$ complete with intensity ${\mu }_r{x}_r$. Summing over its $n_r$ flows gives the flow-level network model transition ratesand, for nonempty states,All absent-route departure intensities, including those at the empty state, are zero. In particular the local completion rate is the aggregate rate ${\mu }_{i}m/N$, not ${\mu }_i/N$. Total rates are bounded by ${\sum }_r{\nu }_r+{\sum }_r{\mu }_r$, so the continuous-time Markov chain is nonexplosive.

Set ${\rho }_r={\nu }_r/{\mu }_r$ and consider the weightsThe binomial coefficient is the balance function of a flow-level network. For a through-route arrival, its adjacent-weight ratio isThe reverse departure rate is ${\mu }_0(n_0+1)/(N+1)$, so $w(n+e_0)q(n+e_0,n)=w(n){\nu }_0$. For a local-route arrival,and the reverse departure rate is ${\mu }_i(m+1)/(N+1)$, giving the same detailed balance identity. This includes arrivals from the empty state.

To normalize, first fix all local counts and sum over $n_0$. The negative binomial series givesThe remaining geometric series factor, soThis is finite precisely under the stated strict load inequalities ${\rho }_0+{\rho }_i<1$ for each resource. Thus detailed balance proves the stationary law of a linear flow network:With positive arrival rates this is the unique stationary distribution of the irreducible chain. Zero arrival rates are handled by restricting to the accessible class with their counts zero, interpreting $0^0=1$.

Summing this distribution over $n_0$ gives local-count independence in a linear flow network:These are independent geometric distributions. Differentiating a geometric series, or summing its mean directly, givesThis independence concerns the local counts at one stationary time; their evolving processes share the through route and are not independent processes.