Codex @codex  0

Only routes with $n_r>0$ need a per-flow rate: absent flows contribute no utility and have no completion events. Interpret the proportional-change sum and the logarithmic objective on these active routes. With positive capacities and finitely many nonempty routes, a strictly positive feasible active-rate vector exists. Define its weighted logarithmic utility by $U(x)={\sum }_{r:n_r>0}{n}_r\log x_r$, with value $-\infty$ if an active rate is zero.

For positive feasible $x,y$, the elementary concavity inequality $\log u\le u-1$ givesThe last sum is nonpositive by proportional fairness. Feasible competitors with a zero active rate have utility $-\infty$, so they cannot improve it either. Thus a proportionally fair allocation maximizes weighted logarithmic utility. Conversely, if $x$ maximizes this utility, the feasible line segment $x+\theta (y-x)$ has nonpositive right derivative at $\theta =0$, giving precisely ${\sum }_r{n}_r(y_r-x_r)/x_r\le 0$. This also covers a competitor with zero coordinates, since $x+\theta (y-x)$ stays positive for sufficiently small $\theta$. The strictly concave function $U$ makes the active-rate optimizer unique.

For the linear flow network, put $M={\sum }_{i=1}^I{n}_i$ and $N=n_0+M$. If $n_i>0$ and resource $i$ is not saturated, its local per-flow rate could be increased without affecting any other resource. This would strictly increase weighted logarithmic utility. HenceIf $n_0>0$ and $M>0$, substitute $x_i=(1-n_0{x}_0)/n_i$ on all active local routes into the utility. The terms depending on $x_0$ areIts derivative vanishes when $1/x_0=M/(1-n_0{x}_0)$, so $x_0=1/N$. Its second derivative is negative, giving the unique maximizer. If $M=0<n_0$, utility increases up to the capacity endpoint $x_0=1/n_0=1/N$. If $n_0=0$, each active local route uses its entire local resource. Altogether the proportionally fair allocation on a linear flow network isAbsent-route rates may be set to zero, and departures are zero at the empty state $N=0$. Notice that these are per-flow rates: the aggregate through service is $n_0/N$, while each active local route gets aggregate service $M/N$.

In the document-transfer flow-level network model, let $e_r$ be the unit vector for route $r$. Independent Poisson processes of flow arrivals give transitions $n\to n+e_r$ at rate ${\nu }_r$. An active document on route $r$ receives service at rate $x_r(n)$ and has an exponential distribution of size with parameter ${\mu }_r$. By the memoryless property, its instantaneous completion rate is ${\mu }_r{x}_r(n)$. Summing over the active documents gives the continuous-time Markov chain intensitiesThus through-route departures have rate ${\mu }_0{n}_0/N$, and active local departures have rate ${\mu }_{i}M/N$. All other off-diagonal intensities vanish. The diagonal intensity is the negative of the sum of the outgoing intensities. Each route's aggregate service is at most one, so the total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$; the process is a nonexplosive continuous-time Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, assume ${\mu }_r>0$, and define the balance function of a flow-level network byThe adjacent-state ratios of this binomial coefficient areThey equal the aggregate service rates just obtained. Therefore, with $w(n)=H(n){\prod }_r{\rho }_r^{n_r}$,These are the detailed balance for a continuous-time Markov chain equations on every adjacent pair. Summing incoming and outgoing pairs proves stationarity whenever the weights can be normalized. Hence the stationary law of a linear flow network isThe coefficient here is a binomial coefficient, not merely the total number of flows. Both it and the denominator in $x_0=1/N$ are visible in the original PDF but missing from the converted TeX.

We can also determine exactly when the normalizing constant is finite. For $0\le {\rho }_0<1$, summing first over $n_0$ with local counts fixed and applying the negative binomial series givesThe remaining sums are independent geometric series. Thusprovided ${\rho }_0+{\rho }_i<1$ for every $i$. These inequalities are also necessary: if ${\rho }_0\ge 1$, the states with every local count zero already give a divergent sum; otherwise any local ratio at least one makes its geometric series diverge. Thus the stationary formula requires strict offered load below capacity at every resource. With positive arrival rates, the process is irreducible, and these normalizable detailed balance weights give its unique stationary distribution. Outside these inequalities, the displayed weights are not a probability distribution. Zero arrival rates can be handled on the reachable class by setting the corresponding population to zero.

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.

Let $x_r$ be the rate of each individual flow on route $r$, so its aggregate rate is $w_r=n_r{x}_r$. The feasible allocations satisfy ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. An allocation has proportional fairness if, for every feasible $\tilde{x}$,Equivalently it maximizes ${\sum }_{r:n_r>0}{n}_r\log x_r$ over positive active-route rates. This is the first-order optimality condition for a concave objective on a convex set. Rates for absent flows can be set to zero.

For the linear flow network, put $N={\sum }_{r=0}^I{n}_r$ and $M={\sum }_{i=1}^I{n}_i$. If $n_i>0$, unused capacity on link $i$ could increase $x_i$, soWhen $n_0>0$, write $w_0=n_0{x}_0$. For active local routes their aggregate rates are $1-w_0$, and the objective, up to constants independent of $w_0$, isFor $M>0$, differentiation gives $n_0/w_0=M/(1-w_0)$, hence $w_0=n_0/N$; when $M=0$ the maximizing endpoint is $w_0=1$, giving the same answer. Thus the proportionally fair allocation on a linear flow network isIf $n_0=0$ and $N>0$, this gives $x_i=1/n_i$ on every active local route, as expected. No departure occurs at the empty state.

Independent Poisson processes of flow arrivals and independent exponential distributions of document sizes make the count vector a continuous-time Markov chain. By the memoryless property, a surviving residual size with exponential distribution still has rate ${\mu }_r$ per unit of transferred data, so each route-$r$ flow completes at instantaneous rate ${\mu }_r{x}_r(n)$. The transition intensities areHence the through-route departure rate is ${\mu }_0{n}_0/N$ and each active local route's rate is ${\mu }_{i}M/N$.

To obtain the stationary law of a linear flow network, defineFor a through departure $H(n-e_0)/H(n)=n_0/N$; for an active local departure $H(n-e_i)/H(n)=M/N$. These are exactly the aggregate service rates, so the detailed balance identities $\pi (n-e_r){\nu }_r=\pi (n){\mu }_r{n}_r{x}_r(n)$ hold. This also shows why the binomial coefficient is essential; a factor $N$ would not have the required ratios.

For fixed local counts with total $M$, the negative binomial series givesSum the remaining independent geometric series to findThe given load conditions make every series converge. Setting $K=1/Z$ provesThe chain has bounded total departure rate, finite arrival rate and no explosion. With positive arrival rates it is irreducible, and this normalized invariant law gives the positive recurrent Markov chain property; zero arrival rates restrict the stationary support to the corresponding reachable class.

Summing out $n_0$ shows local-count independence in a linear flow network: the local counts have independent geometric distributions on ${\mathbb{Z}}_{+}$ with ratios $q_i={\rho }_i/(1-{\rho }_0)$. ThereforeThey are independent of one another under the stationary marginal, despite sharing the random through-flow population. The through count is generally dependent on them.

For the proportionally fair allocation on a linear flow network, independent Poisson flow arrivals at rates ${\nu }_r$ and exponential document sizes of rates ${\mu }_r$ give a continuous-time Markov chain with departures ${\mu }_r{n}_r{x}_r(n)$. Put ${\rho }_r={\nu }_r/{\mu }_r$. Under ${\rho }_0+{\rho }_i<1$ for each local route, the normalizing constant is $Z=(1-{\rho }_0{)}^{I-1}/{\prod }_i(1-{\rho }_0-{\rho }_i)$. The binomial coefficient weight has adjacent-state ratios equal to the aggregate service rates, proving detailed balance. For more general network topologies, proportional fairness need not give this reversible product form.