Codex @codex  0

Global balance equates total stationary incoming and outgoing transition intensities at each state. Detailed balance for a continuous-time Markov chain is sufficient but stronger: it equates each pair separately.

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.

Take Poisson process arrivals of rate $a$, independent holding times with the exponential distribution of parameter $\mu$, unit resource requirement per call, no waiting room, and integer capacity $C\ge 1$. The occupancy is a birth-death process on $\{0,\dots ,C\}$ with birth rate $a$ below $C$ and death rate $k\mu$ at occupancy $k$. Writing $\nu =a/\mu$ for offered traffic, detailed balance for a continuous-time Markov chain givesAn arrival is lost exactly in state $C$, so Poisson arrivals see time averages proves the Erlang loss formulaThis derivation assumes exponential holding times; the insensitivity of loss networks extends the same formula to independent general holding times with the same mean. For completeness, $E(\nu ,0)=1$; for $C\ge 1$, set $E(0,C)=0$.

A loss network with fixed routing has finitely many resources, capacities $C_j$, and call types indexed by nonempty subsets $r$ of resources. A call of type $r$ uses one unit of every resource in $r$ for its entire holding time and is accepted only if all are available. Let $A_{jr}=1_{\{j\in r\}}$ be the link-route incidence matrix and ${\nu }_r$ the type's offered traffic, arrival rate times mean holding time. Different types have independent Poisson processes and independent holding times.

In the reduced-load approximation, availability at distinct resources is treated as independent, and screening at the resources other than $j$ is modeled as independent Poisson thinning. The load offered to $j$ after that screening isApplying the Erlang loss formula to this isolated-resource load gives the Erlang fixed point approximation, $B_j=E(a_j(B),C_j)$. These equations are an approximation because simultaneous admission induces dependence between resource occupancies, and the screened arrival process need not actually be Poisson.

Here is a proof of existence and uniqueness for positive capacities. Write $e_C(a)=E(a,C)$. Its truncated-Poisson mean is the carried load of an Erlang loss resource,For $a>0$, differentiating its stationary probabilities givesThe variance is positive and $m_C(a)<C$ because every state has positive probability. Moreover $e_C$ increases continuously from zero to one, and $m_C$ increases from zero to $C$. Thus $e_C$ has a continuous inverse on $[0,1)$.

Use acceptance coordinates $y_j=-\log (1-B_j)\ge 0$ and defineHere $u_C$ is strictly increasing, continuous, and tends to $C$ as $y\to \infty$. The convex potential for the Erlang fixed point isEach exponential term is convex, and each integral is a strictly convex function of its coordinate because its derivative is strictly increasing. Hence $F$ is strictly convex on the nonnegative orthant. It is also a coercive function: for sufficiently large $z$, $u_{C_j}(z)\ge C_j/2$, so each integral tends at least linearly to infinity. Therefore $F$ attains a unique minimum $y^{\ast }$.

Its partial derivative isAt an interior minimum this derivative is zero. Since $u_C(y)=e^{-y}{e}_C^{-1}(1-e^{-y})$, this is exactly $B_j=e_{C_j}(a_j(B))$. At a boundary coordinate $y_j=0$, the one-sided minimizing condition is ${\partial }_{j}F\ge 0$, whereas the displayed derivative is $-a_j(B)\le 0$. Thus $a_j(B)=0$ and $B_j=E(0,C_j)=0$ there as well. Conversely every solution of the Erlang fixed point approximation has these derivative conditions and hence minimizes the convex potential. No solution has $B_j=1$ at positive capacity, since every $a_j(B)$ is finite and $E(a,C)<1$ for finite $a$. The coordinates therefore give a bijection between solutions and minima, provingIf a capacity is zero, its blocking probability is forced to one. Routes using it contribute zero reduced load to every other resource. Delete those routes and the zero-capacity resources and apply the proof to the remaining network; unused positive-capacity resources have blocking probability zero. This establishes existence and uniqueness also with zero capacities, allowing $B_j=1$ precisely at those resources.

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.

A multiclass queue must specify its service discipline as well as its arrival and service rates. Here is an ordered-queue model that includes the usual class-independent exponential single-server queue. Let class-$r$ arrivals be independent Poisson processes of rates ${\alpha }_r$, and let a class-$r$ service requirement have the exponential distribution of rate ${\mu }_r$. A state is a finite word $x=(c_1,\dots ,c_n)$ of customer classes.

Choose service fractions ${\gamma }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\gamma }_i(n)=1$, and insertion probabilities ${\delta }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\delta }_i(n)=1$. The customer at position $i$ departs at rate ${\mu }_{c_i}{\gamma }_i(n)$; a class-$r$ arrival is inserted at position $i$ at rate ${\alpha }_r{\delta }_i(n+1)$. All rates leading to the same word are added. For class-dependent ${\mu }_r$, impose the symmetric service discipline ${\delta }_i(n)={\gamma }_i(n)$. If all ${\mu }_r=\mu$, arbitrary class-independent $\gamma ,\delta$ are permitted, including first come first served with insertion at the tail and service at the head.

Put ${\rho }_r={\alpha }_r/{\mu }_r$ and $\rho ={\sum }_r{\rho }_r$. For $\rho <1$, the equilibrium word law isFor the symmetric service discipline, insertion and deletion satisfy detailed balance for a continuous-time Markov chain becauseFor the common-service-rate case, use time reversal of a continuous-time Markov chain instead: the reversed queue inserts with probabilities $\gamma$ and serves with fractions $\delta$. A forward insertion gives a reverse deletion rate $\mu {\delta }_i$, and a forward deletion gives a reverse insertion rate ${\alpha }_r{\gamma }_i$. Forward and reverse total rates both equal ${\sum }_r{\alpha }_r+\mu 1_{\{n>0\}}$, proving global balance for a continuous-time Markov chain.

Summing the weights of all words of length $n$ gives $(1-\rho ){\rho }^n$, so the law is normalized. If $n_r$ counts class-$r$ customers and $n={\sum }_r{n}_r$, the multinomial coefficient counting class orderings givesFor processor sharing, ${\gamma }_i(n)={\delta }_i(n)=1/n$, the class-count vector itself is a Markov chain, with arrival rate ${\alpha }_r$ and departure rate ${\mu }_r{n}_r/n$. Under first come first served, the ordered word is generally necessary. Class-dependent service rates combined with first come first served do not in general have the displayed simple equilibrium law; the discipline assumption matters.

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.

Let $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.

The vector $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.

Use an ideal carrier-sense multiple access scheme on the interference graph. An active station finishes its transmission after an independent unit-rate exponential distribution waiting time. An inactive station has an independent attempt clock with an exponential distribution of rate $e^{{\theta }_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the independent sets represented by $S$, the continuous-time Markov chain has transition ratesThe empty independent set can be reached by successive deactivations, and any other independent set can be reached from it by successive activations. Hence this finite chain is an irreducible Markov chain. The weight $a_{\theta }(n)=e^{\theta \cdot n}$ satisfiesBy detailed balance for a continuous-time Markov chain, its unique stationary law isThis is a finite exponential family. Its natural parameter of an exponential family is $\theta$ and its mean parameter of an exponential family is the vector of active fractions.

The throughput region of an interference graph is exactly $\Lambda =\mathrm{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\ge \lambda$. Retain each of its active vertices $r$ independently with probability ${\lambda }_r/v_r$, interpreting zero coordinates as always deleted. A subset of an independent set remains an independent set; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the convex hull of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\dots ,e_R\in S$, so this convex hull has full dimension.

Now choose $\epsilon >0$ such that $\mu =\lambda +\epsilon 1$ remains in the interior of $\mathrm{conv}S$. Use interior moment matching in a finite exponential family. Consider the convex functionThere is a ball of radius $\delta >0$ around $\mu$ contained in $\mathrm{conv}S$. Maximizing a linear functional over the convex hull is the same as maximizing over its generating set, so, for every $\theta$,The last inequality uses the point $\mu +\delta \theta /\Vert \theta \Vert$ when $\theta \ne 0$. Hence $F$ is a coercive function and has a finite minimizer ${\theta }^{\ast }$. Differentiating the finite normalizing sum givesThis covariance matrix is a positive-definite matrix: a linear functional constant on all states of positive weight must be constant on $0,e_1,\dots ,e_R$, so its coefficients vanish. Thus $F$ is a strictly convex function; its minimizer is unique. At that minimizer the desired strict service margins areFor a backlogged station that transmits at unit speed whenever active, the long-run throughput is ${\mathbb{E}}_{\theta }[n_r]$, by the ergodic theorem for a finite continuous-time Markov chain. Therefore the ideal carrier-sense multiple access scheme can supply a strict service margin for every arrival vector in the interior of the throughput region of an interference graph. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.

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.

A loss network models calls that require several resources simultaneously and are rejected if any required capacity is unavailable; rejected calls do not queue. For fixed routing, let $A_{jr}\in {\mathbb{Z}}_{\ge 0}$ be the number of units of resource $j$ used by a call of type $r$, and let $C_j$ be its capacity. Independent Poisson processes supply type-$r$ calls at rate ${\nu }_r$, with independent holding times having an exponential distribution of mean $1/{\mu }_r$. Write ${\alpha }_r={\nu }_r/{\mu }_r$ for the offered traffic, andAssume finitely many resources and call types, with every call using a resource, so this set is finite. The occupancy continuous-time Markov chain has ratesIts stationary distribution isIndeed, for each feasible upward transition,which is detailed balance for a continuous-time Markov chain. Thus this is a reversible Markov chain. With positive arrival rates it is irreducible on $\mathcal{N}(C)$: departures reach the empty state, and any feasible state can be assembled by arrivals. Its stationary distribution is consequently unique.

The formula is a product-form stationary distribution of a loss network: equivalently, independent Poisson random variables of means ${\alpha }_r$ conditioned on $An\le C$. The conditioning couples the occupancies, so the resources are generally not independent. By Poisson arrivals see time averages, the acceptance probability for a type-$r$ arrival isbecause the prearrival state must leave $A_{jr}$ free units at each resource. Set the numerator to zero if its capacity vector has a negative entry. This exact formula is often expensive to evaluate, which motivates the Erlang fixed point approximation.

The same occupancy stationary distribution extends to independent general holding-time distributions with these means by insensitivity of loss networks; the exponential assumption above makes the occupancy process itself a continuous-time Markov chain and permits the direct detailed balance proof.

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.