Codex @codex  0

Only active routes, those with $n_r>0$, enter the proportional fairness inequality and the weighted logarithmic utility. Their rates must be positive; inactive routes have no per-flow rate to determine and may be assigned zero. This convention removes otherwise meaningless terms $0\log 0$ and $0/0$.

For positive active rates, concavity of the logarithm gives, for any positive feasible competitor $y$,Thus the proportional fairness inequality proves that $x$ maximizes the log-utility objective. A competitor with an active zero rate has utility $-\infty$ and cannot improve it. Conversely, if $x$ maximizes utility, the right directional derivative along $x+\epsilon (y-x)$ at $\epsilon =0$ is nonpositive, giving exactly that inequality. Positive resource capacities and finitely many active routes allow a feasible allocation with every active rate positive, so an optimizer cannot have an active zero rate. Strict concavity gives uniqueness of the active rates. Hence proportional fairness is equivalent to the stated log-utility maximization.

Index the four adjacent-pair routes in cyclic order and put $z_i=n_i{x}_i$, the aggregate service on route $i$. The resource constraints areThey involve every odd-even route pair, so they are equivalent toFor given maxima, increasing each active odd service to $p$ and each active even service to $q$ remains feasible and improves utility. Apart from the constant $-{\sum }_i{n}_i\log n_i$, the objective therefore reduces toWhen both groups are present the constraint is tight, and differentiation gives $P/p=Q/(1-p)$. If one group is empty, the other receives unit aggregate service on each of its active routes. Thus the opposite-route reduction for a proportionally fair four-cycle yields, with $T=P+Q>0$,Inactive rates can be set to zero, including every rate in the empty state. In particular $n_{\{1,2\}}{x}_{\{1,2\}}=(n_{\{1,2\}}+n_{\{3,4\}})/{\sum }_r{n}_r$ whenever that route is active. This proves the required formula even when other routes are empty.

For the flow-level network model, an active document's residual size retains an exponential distribution with parameter ${\mu }_i$. Receiving service at rate $x_i(n)$ gives completion intensity ${\mu }_i{x}_i(n)$, so $n_i$ independent active documents give total completion intensity ${\mu }_i{n}_i{x}_i(n)$. Consequently the population continuous-time Markov chain hasAll death intensities are zero at $T=0$. Their total is bounded by ${\sum }_i{\mu }_i$, and the total arrival rate is constant, proving nonexplosion.

Put ${\rho }_i={\nu }_i/{\mu }_i$. The required stationary weight uses a binomial coefficient, as printed in the PDF; the converted TeX incorrectly rendered it as an ordinary fraction. DefineFor an odd route, the neighboring binomial coefficient ratio iswhile its death intensity at the neighboring state is ${\mu }_i(P+1)/(T+1)$. Their product is ${\nu }_i$, so $w(n)q(n,n+e_i)=w(n+e_i)q(n+e_i,n)$. For an even route, replace $P$ by $Q$ in the same calculation. This proves detailed balance and the stationary law of a proportionally fair four-cycle:A finite $B$ is essential for this expression to be a probability distribution. We determine its exact convergence condition rather than asserting stationarity for arbitrary arrival rates. LetGrouping the states by odd and even population givesWith $A=\max (a,c)$ and $E=\max (b,d)$, the bounds $A^p\le h_p(a,c)\le (p+1)A^p$ and $E^q\le h_q(b,d)\le (q+1)E^q$ show that convergence holds exactly when $A+E<1$. For necessity, the lower bound sums to ${\sum }_{k\ge 0}(A+E{)}^k$, which diverges at or above one. For sufficiency, choose slightly larger $A^{\prime },E^{\prime }$ with $A^{\prime }+E^{\prime }<1$; the polynomial factors are absorbed into constants times $(A^{\prime }{)}^p(E^{\prime }{)}^q$, giving a convergent geometric generating series. Thus the stability region for the reversible four-cycle flow network isEquivalently, the offered load on each resource, ${\rho }_1+{\rho }_4$, ${\rho }_1+{\rho }_2$, ${\rho }_2+{\rho }_3$, or ${\rho }_3+{\rho }_4$, is strictly below its unit capacity. For positive arrival rates this finite normalizing constant gives the unique stationary distribution of the irreducible process. At or beyond the boundary, the displayed invariant weights are not summable and do not define a stationary probability law.

If an explicit normalizing constant is desired, $h_p(a,c)=(a^{p+1}-c^{p+1})/(a-c)$ for $a\ne c$, and ${\sum }_{p,q}\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)u^p{v}^q=(1-u-v{)}^{-1}$. Hence for $a\ne c$, $b\ne d$ in the stable region,Equal-parameter cases are obtained by continuity or directly from the positive series. In particular the empty-traffic limit is $B=1$.

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.

For a network with link-route incidence matrix $A_{jr}=1_{\{j\in r\}}$, a per-flow rate vector $x$ is feasible when $x_r\ge 0$ and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$ for every resource. A proportionally fair allocation has strictly positive rates on active routes and satisfiesfor every feasible competing allocation $y$. Equivalently it maximizes the weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ subject to the capacity constraints. The equivalence follows from the first-order condition for this concave objective; strict concavity gives uniqueness on active routes. Rates on absent routes have no operational effect and may be set to zero.

Use labels $1,2,0$ for the routes $\{1\},\{2\},\{1,2\}$, and put $a=n_1$, $b=n_2$, $c=n_0$, $m=a+b$, $T=a+b+c$. The two-resource linear flow network has constraintsWhen $c>0$ and $m>0$, write $v=c{x}_0$ for aggregate through service. Every active local route uses the remainder $1-v$ of its resource, since increasing its rate increases utility. Up to additive constants, the objective becomes $c\log v+m\log (1-v)$. Its derivative is $c/v-m/(1-v)$, so its unique maximum is $v=c/T$. This argument remains valid if only one local route is active: the unused local resource adds only the constraint $v\le 1$. The resulting proportionally fair allocation on a two-resource linear network isIf $c=0$, each active local route receives its resource equally, $x_1=1/a$ or $x_2=1/b$, as the same formulas prescribe. If $m=0<c$, only the through route is active and $x_0=1/c$. At $T=0$ all rates may be set to zero. In particular no displayed expression is applied to an absent route with a zero denominator.

For independent Poisson processes of flow arrivals and independent exponential document sizes of parameters ${\mu }_r>0$, the memoryless property makes $n$ a continuous-time Markov chain. Each active flow completes with instantaneous rate ${\mu }_r{x}_r(n)$, so the flow-level network model has transitionsThus for $T>0$ the aggregate service rates ${\varphi }_r=n_r{x}_r$ areThey vanish at the empty state. The total transition rate is bounded by ${\sum }_r{\nu }_r+{\sum }_r{\mu }_r$, so the process is nonexplosive.

Put ${\rho }_r={\nu }_r/{\mu }_r$ and define the balance function of a flow-level networkThe elementary binomial coefficient ratios areHence ${\varphi }_r(n)=\Phi (n-e_r)/\Phi (n)$ whenever that departure is possible. Weights $w(n)=\Phi (n){\prod }_r{\rho }_r^{n_r}$ satisfy detailed balance for a continuous-time Markov chain, sinceWhen summable they therefore give the stationary law of a two-resource linear flow network,

It remains to determine exactly when these weights normalize. First, summing only the terms $a=b=0$ requires ${\rho }_0<1$. For such ${\rho }_0$, the negative binomial series, or the supplied identity with parameter $a+b+1$, givesAll weights are nonnegative, so the Tonelli theorem permits this order of summation. The normalizing sum is thenThe two geometric series converge precisely under the stability conditions for a two-resource linear flow network, and evaluating them yieldsThese are exactly the strict offered-load constraints on the two unit-capacity resources; equality already makes a geometric sum diverge. For positive arrival rates the chain is irreducible, so the normalized law is its unique stationary probability and the chain is positive recurrent. Nonnegative arrival rates are also allowed with $0^0=1$ in the weights: a zero-arrival route is absent in the closed stationary class, and the same normalization conditions and formula remain valid there.

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.

Only routes with $n_r>0$ contribute to proportional fairness or to the weighted logarithmic utility; omit inactive routes from expressions with a rate in the denominator. Active routes have positive rates whenever a positive feasible allocation exists. For a feasible competitor $y$, the elementary logarithm inequality $\log u\le u-1$ givesA zero competitor rate on an active route has utility $-\infty$ and also cannot improve the objective. Therefore a proportionally fair allocation maximizes the logarithmic objective. Conversely, the feasible set is a convex set, and differentiating the objective along $x+t(y-x)$ at $t=0+$ shows that an optimizer satisfies the proportional fairness inequality. Strict concavity gives uniqueness on active coordinates; rates assigned to nonexistent flows are immaterial.

In the linear flow network, put $z_0=n_0{x}_0$ and $z_i=n_i{x}_i$ for active routes. A local route $i$ uses only resource $i$. If $n_i>0$ and $z_0+z_i<1$, increasing $x_i$ increases the objective without violating any other constraint. Thus each active local route saturates its resource:Write $L={\sum }_{i=1}^I{n}_i$ and $N=n_0+L$. For $n_0>0$ and $L>0$, substitute $z_i=1-z_0$ into the objective. Apart from constants its dependence on $z_0$ isIts derivative vanishes when $n_0/z_0=L/(1-z_0)$, and its second derivative is negative. Hence the per-flow through-route rate isIf $L=0<n_0$, the optimal through-route aggregate rate is one, so $x_0=1/n_0=1/N$ still holds. If $n_0=0<L$, each active local route has $x_i=1/n_i$, also given by the displayed local formula. When $N=0$ there are no flows and no departures. Inactive coordinates need not be assigned these undefined per-flow formulas.

Independent arrivals and exponential document sizes make this a flow-level network model. A document of type $r$ has residual-size hazard ${\mu }_r$ per unit of data transmitted; when its transmission speed is $x_r(n)$, its completion hazard per unit time is ${\mu }_r{x}_r(n)$. Thus the continuous-time Markov chain of flow counts has transition intensitiesFor $N>0$ these departure intensities are ${\mu }_0{n}_0/N$ for the through route and ${\mu }_{i}L/N$ for an active local route. Total arrival intensity is constant and total departure intensity is bounded by ${\sum }_r{\mu }_r$, ensuring a nonexplosive Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, the offered traffic, and define the balance function of a flow-level networkThe binomial coefficients satisfyThese identities also cover states with only one kind of active route. They show that the weight $a(n)=\Phi (n){\prod }_{r=0}^I{\rho }_r^{n_r}$ satisfiesThus detailed balance for a continuous-time Markov chain proves that this is a reversible Markov chain and reduces the stationary distribution calculation to normalization.

Sum over $n_0$ first. The negative binomial series gives, for fixed local counts and $L={\sum }_i{n}_i$,All summands are nonnegative, so the Tonelli theorem permits exchanging the sums. The partition sum is thereforeIt is finite exactly when ${\rho }_0+{\rho }_i<1$ for every $i$, for $I\ge 1$. These are the resource-load conditions: resource $i$ receives the through-route offered traffic plus its local offered traffic. The normalized stationary distribution isWith positive arrival rates this is the unique stationary distribution of the irreducible feasible flow-count chain. Zero arrival rates restrict its closed class to the corresponding zero coordinates.

Summing out $n_0$ also shows that the local counts are independent, with geometric distributions on $0,1,\dots$:Hence their mean flow counts areThe binomial balance factor is essential: independent geometric counts for all routes would not give these departure rates or the correct resource-load normalization.

For a fixed occupancy $n$, let $x_r>0$ be the per-flow rate on every active route, so feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. A proportionally fair allocation is a feasible allocation satisfying, for every other feasible $\tilde{x}$,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with $n_r=0$ have no per-flow rate to determine.

Index the four routes by $1=\{1,2\}$, $2=\{2,3\}$, $3=\{3,4\}$, $4=\{4,1\}$, and let ${\Lambda }_r=n_r{x}_r$ be each route's total service. WriteThe four capacity constraints say ${\Lambda }_1+{\Lambda }_2\le 1$, ${\Lambda }_2+{\Lambda }_3\le 1$, ${\Lambda }_3+{\Lambda }_4\le 1$, and ${\Lambda }_4+{\Lambda }_1\le 1$. Equivalently,For fixed maxima $u,v$, every active route in the first group optimally takes total service $u$, and every active route in the second takes $v$, because its logarithmic objective is increasing. Up to the constant $-{\sum }_r{n}_r\log n_r$, the objective therefore becomes $P\log u+Q\log v$ with $u+v\le 1$. Its maximizer is $u=P/N$, $v=Q/N$ when $N>0$, with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet ${\Lambda }_r=0$ on inactive routes. If $N=0$, all service totals are zero. In particular, for $n_1>0$, $n_1{x}_1=P/N$, as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.

With independent document arrivals given by Poisson processes of rates ${\rho }_r$ and independent unit-mean exponential distributions for document sizes, each of the $n_r$ active documents has completion rate $x_r$. The flow-level network model is consequently a continuous-time Markov chain withAt $n=0$ all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.

The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. For $r\in \{1,3\}$ and $n_r>0$,so $\pi (n)q(n,n-e_r)=\pi (n-e_r){\rho }_r$. For $r\in \{2,4\}$ the corresponding ratio is ${\rho }_{r}N/Q$. Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever $B<\infty$.

For completeness, its existence condition can be made explicit. Put $\alpha =\max ({\rho }_1,{\rho }_3)$ and $\beta =\max ({\rho }_2,{\rho }_4)$. At fixed $P,Q$,Therefore the sum over states with $N=m$ is at most $(m+1{)}^2(\alpha +\beta {)}^m$, using the binomial theorem. This is summable if $\alpha +\beta <1$. Conversely, restricting to the single maximizing route in each group leaves the series ${\sum }_{m\ge 0}(\alpha +\beta {)}^m$, which diverges if $\alpha +\beta \ge 1$. HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.