Stochastic network

A stochastic network combines resource constraints, routing, and random arrivals or service requirements. Loss networks reject requests that cannot acquire all required resources; flow-level network models let ongoing transfers share capacities.

The useful infinite-horizon path space for a stable queue isFor $\delta ,\sigma >0$, the workload functional $R(f)={\sup }_{t\ge 0}(\sigma f(t)-\delta t)$ is finite and continuous. Fix $f$, and choose $T\ge 1$ so that $|\sigma f(t)|\le \delta t/4$ for $t\ge T$. If $\Vert g-f{\Vert }_{\mathrm{sl}}<\delta /(4\sigma )$, then $\sigma g(t)-\delta t<0$ for $t\ge T$. Both suprema can thus be taken over $[0,T]$, whereUniform convergence on bounded time intervals alone does not give this continuity: a pulse escaping to later times can produce a large workload while tending locally to zero.

For one-sided past inputs, let $A_n(a)={\sum }_{j=0}^{n-1}{a}_{-j}$ and $A_0=0$. The displayed metric controls cumulative differences over every past window, including the latest arrival. On the affine class $A_n(a)/n\to \lambda <c$, the queue workload $Q(a,c)={\sup }_{n\ge 0}(A_n(a)-cn)$ is locally Lipschitz continuous. To prove this, choose $\epsilon =(c-\lambda )/4$ and $N\ge 1$ such that $A_n(a)/n\le \lambda +\epsilon$ for $n\ge N$. If $d_{\#}(a,b)<\epsilon /2$, then $A_n(b)-cn\le n(\lambda +2\epsilon -c)<0$ for all such $n$. Both suprema reduce to $0\le n<N$, and their difference is at most $(N+1)d_{\#}(a,b)$. Ignoring the latest coordinate makes this assertion false for a post-slot workload of a queue.

Let a centered Gaussian process $Z$ satisfy $Z(a\cdot )\stackrel{d}{=}{a}^{H}Z$ with $0<H<1$, and suppose $Z/\sqrt{L}$ has a large deviation principle in the sublinear path space for fluid queues, with speed $L$ and good rate function $I$. For $\delta ,\sigma >0$, put $r={\sup }_{t\ge 0}(\sigma Z(t)-\delta t)$ and $\kappa =2(1-H)$. Self-similarity gives $Z(N\cdot )/N\stackrel{d}{=}Z/\sqrt{N^{\kappa }}$. Time substitution and the contraction principle for large deviations therefore give an LDP for $r/N$ with speed $N^{\kappa }$ andThe same family $r/(aN)$ has rate function $J(aq)$ by contraction, and $a^{\kappa }J(q)$ by replacing $N$ with $aN$ and expressing the speed again as $N^{\kappa }$. Uniqueness of a rate function gives $J(aq)=a^{\kappa }J(q)$, hence $J(q)=q^{\kappa }J(1)$ for $q>0$, with $J(0)=0$.

A closed migration process is a continuous-time Markov chain of populations moving between colonies with a conserved total number of individuals. A colony containing $k$ individuals has departure rate ${\varphi }_j(k)$, with ${\varphi }_j(0)=0$, and each departure chooses its next colony using a fixed routing matrix. Its colony populations can represent stages of a service system, including an idle stage.

// Target: probability-and-statistics.bigb

Represent $N$ telephone lines by a closed migration process with free-line, operator and automated-service colonies. Accepted arrivals have rate $\nu$ when a free line exists, $c$ operators complete at rate $\lambda \min (k,c)$, and $i$ automated calls complete at rate $\mu i$. Define $D_c(k)={\prod }_{h=1}^k\min (h,c)$ andThe product-form stationary distribution of a closed migration process and Poisson arrivals see time averages give the displayed blocking probability. This extends a single-operator model without treating the independent operators as a server with rate $c\lambda$ when fewer than $c$ calls are present.

// Target: probability-and-statistics.bigb

In a one-operator closed migration process representing a finite-line switchboard, let $K$ count calls waiting for or receiving the operator's connection service and let $I$ count connected calls. At a stationary distribution, the expected drift of $K$ is $\nu \mathrm{Pr}\{K+I<N\}-\lambda \mathrm{Pr}\{K>0\}=0$, and that of $I$ is $\lambda \mathrm{Pr}\{K>0\}-\mu \mathbb{E}[I]=0$. Poisson arrivals see time averages identifies the full-state probability with $P_{\mathrm{loss}}$. Thus the accepted arrival rate, operator throughput and completed-call rate coincide. This is a useful independent check on the product-form stationary distribution of a closed migration process.

For an irreducible closed migration process with finite population $N$, positive departure rates and routing matrix $P$, choose positive traffic weights satisfying $\theta =\theta P$. On ${\sum }_j{n}_j=N$, its stationary distribution has the displayed form. For a predecessor $m=n+e_j-e_k$, its weighted transition into $n$ is $\pi (n)({\theta }_j/{\theta }_k)P_{jk}{\varphi }_k(n_k)$. Summing over $j$ gives $\pi (n){\varphi }_k(n_k)$ by the traffic equation, and summing over $k$ proves global balance for a continuous-time Markov chain. The distribution need not satisfy detailed balance.

// Target: probability-and-statistics.bigb

Connect multiclass single-server queues by Markovian routing. Each node must either have common exponential service parameters across its classes or use a symmetric service discipline. If the traffic equations for a multiclass queueing network give loads ${\rho }_j={\sum }_r{\lambda }_{jr}/{\mu }_{jr}<1$, its equilibrium word law is the product of the individual queue laws. Queue populations are independent at a fixed equilibrium time. A proof reverses routing with $p_{ba}^{\ast }={\lambda }_a{p}_{ab}/{\lambda }_b$, external arrivals with ${\nu }_a^{\ast }={\lambda }_a{p}_{a0}$, and exits with $p_{a0}^{\ast }={\nu }_a/{\lambda }_a$, and interchanges the insertion and service position rules. Weight ratios verify each reversed transition, and the traffic equations match total rates. This is a quasireversibility construction. A standard ordered-queue formulation is described in Walton's paper on multiclass queueing networks, Section 2.

For queue-class pairs $a$, external arrival rates ${\nu }_a$, and routing probabilities $p_{ab}$, the effective throughputs satisfy ${\lambda }_a={\nu }_a+{\sum }_b{\lambda }_b{p}_{ba}$. In an open network with routing spectral radius less than one, $\lambda =(I-P^T{)}^{-1}\nu$ is the unique nonnegative solution. Summing gives ${\sum }_a{\lambda }_a{p}_{a0}={\sum }_a{\nu }_a$, balancing total entrances and exits.

Congestion control adjusts user transmission rates in response to load signals from shared resources. A resource can compute its price from local aggregate load, while each user sums prices along its route. Primal congestion potential and dual congestion potential formulations explain equilibrium and stability for suitable monotone response functions.

Maximize a sum of increasing strictly concave utilities $U_r(x_r)$ subject to $Ax\le C$, $x\ge 0$. Suppose capacities are positive, every route is nonempty, and $U_r^{\prime }(0)=\infty$. At its unique positive optimizer $x^{\ast }$, the Karush-Kuhn-Tucker conditions give nonnegative resource congestion prices $p^{\ast }$ and route congestion prices $y_r^{\ast }=U_r^{\prime }(x_r^{\ast })$. Choosing ${\nu }_r^{\ast }=x_r^{\ast }{e}^{y_r^{\ast }}$ makes each user maximize $U_r({\nu }_r{e}^{-y_r^{\ast }})-y_r^{\ast }{\nu }_r{e}^{-y_r^{\ast }}$ at ${\nu }_r^{\ast }$. It also makes $x^{\ast }$ maximize the entropy maximization for loss-network occupancy objective, since its gradient is $\log ({\nu }_r^{\ast }/x_r^{\ast })=(A^T{p}^{\ast }{)}_r$. Thus user and network optima implement the same system optimum.

A resource congestion price signals scarcity at a capacity-constrained link. Under multiplicative resource-price dynamics, its increase indicates excess demand and its decrease indicates spare capacity. A route pays the sum of these prices, its route congestion price. A zero resource congestion price at an optimum satisfies complementary slackness with possible spare capacity.

The total price seen by a route is the sum of resource congestion prices on its links. With weighted logarithmic utility $w_r\log x_r$, maximizing utility minus linear expenditure gives the demand $x_r=w_r/p_r$. This relation links user decisions to multiplicative resource-price dynamics.

For route prices $p=A^T\mu$, logarithmic users demand $x_r=w_r/p_r$, while resource prices adjust asThis model raises prices under excess demand and lowers them under spare capacity. Positive capacities and nonempty routes are standard well-definedness assumptions. Positive initial prices approach the dual optimum; zero prices are invariant and can create boundary equilibria of multiplicative price dynamics that overload a resource.

Routes with positive logarithmic utility weights choose rates inversely proportional to their total resource price. Each resource changes its price multiplicatively according to demand minus its increasing supply. For continuous strictly increasing $q_j$ with $q_j(0)=0$, the potential $V={\sum }_r{w}_r\log ({\sum }_{j\in r}{\mu }_j)-{\sum }_j{\int }_0^{{\mu }_j}{q}_j(u)du$ is strictly concave and has nonnegative derivative along the dynamics. Positive-price convergence for increasing resource supplies requires positivity on used resources; zero-price faces are invariant.

For finite nonempty routes and positive weights, the potential of increasing-supply resource-price dynamics has a unique maximum. Increasing supplies give a linear penalty at large prices, so its superlevel sets are compact, and logarithmic route terms exclude zero route totals. Used resources have uniformly positive demand on a trapped set; a sufficiently small positive price therefore increases, giving a positive lower bound. The potential derivative is ${\sum }_j{\kappa }_j{\mu }_j({\partial }_{j}V{)}^2$. It has finite integral and is uniformly continuous, so it tends to zero by uniformly continuous integrable functions vanish at infinity. Every limit point then satisfies the unique stationary equations. Unused resource prices decay to zero. Only continuity and strict increase of the supply functions are needed.

In multiplicative resource-price dynamics, a zero price remains zero even if demand exceeds supply there. For one route using two resources, unit weight and supplies $q_j(u)=u$, both $(0,1)$ and $(1,0)$ are equilibria, while the unique positive equilibrium is $(1/\sqrt{2},1/\sqrt{2})$. Thus uniqueness on the positive price domain cannot be extended to every nonnegative price trajectory without an extra boundary rule.

For a complementary-slackness optimum ${\mu }^{\ast }$, defineinterpreting a zero-reference summand as ${\mu }_j/{\kappa }_j$. This is a nonnegative generalized reverse-relative-entropy expression for positive resource prices. Along multiplicative resource-price dynamics, with $p=A^T\mu$ and $g=Ax-C$,Its sublevel bounds keep all route prices away from zero and permit the LaSalle invariance principle, including optima with some zero individual prices.

For multiplicative resource-price dynamics with positive capacities, nonempty routes and strictly positive initial prices, full row rank of the link-route incidence matrix makesstrictly concave. There is a unique optimizing price vector, possibly on the boundary, and the relative-entropy Lyapunov function for resource prices proves convergence to it. Row-rank deficiency still gives unique optimal route prices and rates, but resource prices may depend on the initial state. Full column rank alone and unrestricted zero initial prices do not yield the same uniqueness theorem.

In ${\dot{\mu }}_j={\kappa }_j{\mu }_j(y_j-q_j({\mu }_j))$, a zero price remains zero even if resource demand exceeds supply. Such a boundary equilibrium need not minimize the dual congestion potential; uniqueness of its positive minimizer does not imply uniqueness on the nonnegative orthant.

For strictly increasing continuous supply functions $q_j$ with $q_j(0)=0$, this potential is strictly convex on prices with positive route-price sums. Its minimum is interior for every used resource and gives the unique positive-price equilibrium. Multiplicative price dynamics can also have boundary equilibria of multiplicative price dynamics if zero prices are permitted.

This potential subtracts integrated resource prices from weighted logarithmic utility. Continuous nonnegative nondecreasing prices make it strictly concave on positive rates. If every route meets a resource with a nonzero price function, its superlevel sets are compact and its maximizer is unique. The rate adjustment ${\dot{x}}_r={\kappa }_r{x}_r{\partial }_{r}U$ increases it strictly away from equilibrium.

Assume finitely many nonempty routes, positive weights and adjustment rates, and continuous nonnegative nondecreasing resource prices. Each route must meet a resource whose price is positive somewhere. Then the primal congestion potential has compact superlevel sets inside the positive orthant and a unique maximum. Along gradient flow with diagonal mobility, $\dot{U}={\sum }_r{\kappa }_r{x}_r({\partial }_{r}U{)}^2$. The substitution $x_r={\kappa }_r{z}_r^2/4$ makes the dynamics ordinary gradient flow ascent for $V(z)=U(({\kappa }_r{z}_r^2/4{)}_r)$. This $V$ is strictly concave: the logarithmic terms are strictly concave, and each integrated price is convex and nondecreasing, composed with a convex quadratic load. Thus its continuous gradient is monotone decreasing, which proves uniqueness of trajectories even without differentiability of the prices. Compact trapping and the dissipation identity force every limit point to be the unique maximizer. If every price on some route vanishes identically, its rate instead grows linearly and there is no equilibrium.

For positive rates in congestion control, put $x_r={\kappa }_r{z}_r^2/4$ and $V(z)=U(x(z))$, where $U$ is the primal congestion potential. The equation ${\dot{x}}_r={\kappa }_r{x}_r{\partial }_{r}U$ becomes ${\dot{z}}_r={\partial }_{r}V$. Positive logarithmic utility weights make ${\sum }_r{w}_r\log ({\kappa }_r{z}_r^2/4)$ strictly concave on the positive orthant. Each integrated nonnegative nondecreasing resource price is a convex nondecreasing function of its load; composing it with the convex quadratic load in $z$ preserves convexity. Hence $V$ is a strictly concave function, even for prices that are merely continuous. For two solutions, $\frac{1}{2}\frac{d}{dt}\Vert z-\tilde{z}{\Vert }^2=(z-\tilde{z})\cdot [\nabla V(z)-\nabla V(\tilde{z})]\le 0$. This proves uniqueness of the flow without assuming local Lipschitz continuity of the price functions.

Effective bandwidth describes the exponential-moment traffic rate at a specified time scale and tail parameter. Independent sources have additive effective bandwidths. The Chernoff bound connects their sum to overflow bounds. For a single time unit, the small-parameter limit is the expected value and the large-parameter limit is the essential supremum, with appropriate moment or extended-value conventions.

For independent Poisson arrival counts of mean $\nu$ per slot, with one unit of work per arrival, the cumulant-generating function is $\nu (e^{\theta }-1)$. Its effective bandwidth is the displayed expression. If $c>\nu$, the equation $\nu (e^{\theta }-1)=c\theta$ has a unique positive root: strict convexity, negative initial derivative after subtracting $c\theta$, and divergence to infinity prove existence and uniqueness. Independent Poisson streams combine by replacing $\nu$ with the sum of their intensities.

Independent slots carry either zero work or $r>0$ units, the latter with probability $p$. Their effective bandwidth is the displayed expression, with small-parameter limit $pr$ and large-parameter limit $r$ when $0<p<1$. For $pr<c<r$, the positive root of $\log (1-p+p{e}^{\theta r})=c\theta$ determines the optimized exponential overflow bound. In the special case $r=2,c=1,p<1/2$, the stationary queue workload is geometric with ratio $p/(1-p)$, and the root is ${\theta }_{\ast }=\log ((1-p)/p)$, giving exactly $\mathbb{P}(Q\ge k)=e^{-{\theta }_{\ast }k}$ for integers $k\ge 0$.

Let a slotted queue have stationary input, constant service $c$, and finite stationary queue workload $Q={\sup }_{n\ge 0}(A_n-cn)$. Write $K_n(\theta )=\log \mathbb{E}{e}^{\theta A_n}$ for its past cumulative arrivals. The union bound and Chernoff bound give the displayed inequality for $B>0$. It requires no temporal independence. If each $K_n(\theta )$ is finite and $K_n(\theta )/n\to \kappa (\theta )<c\theta$, the series is finite: its tail is bounded by a geometric series. Consequently ${\mathrm{limsup}}_{L\to \infty }{L}^{-1}\log \mathbb{P}(Q>Lb)\le -\theta b$ for $b>0$. The condition is that the asymptotic effective bandwidth $\kappa (\theta )/\theta$ be less than service capacity.

For a nondecreasing process $A$ with stationary increments and independent increments, suppose $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, then $e^{\theta (A(t)-Ct)}$ is a nonnegative supermartingale. Applying the maximal inequality for a nonnegative supermartingale up to time $T$ and then letting $T\to \infty$ givesThe stationary workload of a stable queue fed by $A$ has this supremum distribution, using the past input and stationary increments and independent increments. For independent flows, the constraint is ${\sum }_j{a}_j(\theta )\le C$, where $a_j(\theta )={\Lambda }_j(\theta )/\theta$ is the long-time effective bandwidth. The result bounds a continuous-time supremum directly; a one-time Chernoff bound by itself does not do that.

For $s>0$ in the finite moment-generating function domain and integrable $X$, Jensen inequality gives the lower bound and $X\le \mathrm{esssup}X$ almost surely gives the upper bound. The Holder inequality makes $K(s)=\log \mathbb{E}{e}^{sX}$ convex with $K(0)=0$. Thus $K(t)\le (t/s)K(s)$ for $0<t<s$, and the effective bandwidth is nondecreasing. It need not be strictly increasing: deterministic traffic gives a constant bandwidth. Infinite peaks or exponential moments require extended-value conventions.

For independent identically distributed traffic increments and constant service $C$, let $a(s)=\mathbb{E}[e^{s(X-C)}]$. If $a(s)<1$, apply the Chernoff bound at each candidate workload window and sum a geometric series. This bounds the stationary random-walk supremum. It explains the effective bandwidth criterion $\alpha (s)<C$ and distinguishes a queue's infinite-horizon overflow event from a single-window traffic event.

For nonnegative traffic with exponential moments near zero, its effective bandwidth has expansion $\mathbb{E}X+s\mathrm{Var}(X)/2+O(s^2)$. For bounded traffic with essential supremum $M$, it increases toward $M$: the exponential moment is at most $e^{sM}$, and any positive probability of $X>a$ gives $\alpha (s)\ge a+s^{-1}\log \mathbb{P}(X>a)$. Unbounded traffic has an infinite large-parameter limit when all positive exponential moments exist; a finite moment domain must be respected.

For a normal distribution $N(\lambda ,{\sigma }^2)$, the logarithm of its moment-generating function is $s\lambda +s^2{\sigma }^2/2$. Dividing by $s>0$ gives its effective bandwidth. Independent demands add these bandwidths. For total mean $m$ and positive total variance $v$, optimizing a Chernoff bound with target $e^{-\gamma }$, $\gamma >0$, yields the sufficient margin $C\ge m+\sqrt{2\gamma v}$.

For a normal distribution with mean $m$, positive variance $v$, and $\gamma >0$, the target $\mathbb{P}(X\ge C)\le e^{-\gamma }$ is equivalent to the displayed constraint, where $\Phi$ is the standard normal distribution function. This follows from $\mathbb{P}(X\ge C)=1-\Phi ((C-m)/\sqrt{v})$ and strict monotonicity of $\Phi$. Unlike the sufficient Chernoff bound margin $\sqrt{2\gamma v}$, this constraint is necessary as well as sufficient. The exact quantile can be negative when $e^{-\gamma }>1/2$.

If a random variable has variance zero and mean $m$, it equals $m$ almost surely. For a target probability strictly between zero and one, $\mathbb{P}(X\ge C)$ meets the target exactly when $m<C$. Substituting zero variance into a positive-variance non-strict quantile constraint incorrectly includes $m=C$, where the overflow probability is one. The distinction comes from the atom at the threshold.

An open migration process is a continuous-time Markov chain of colony populations with external Poisson processes, state-dependent departure rates, and fixed probabilistic routing that eventually exits the system. Its traffic equations of an open migration process determine the total arrival rates, and its equilibrium has a product-form stationary distribution of an open migration process when the normalizing sums are finite.

For a stationary open migration process with local total departure rate ${\varphi }_i(n_i)$ and traffic rates ${\alpha }_i$, adjacent product-weight ratios give the displayed reversed parameters. The traffic equations of an open migration process make each reversed routing row sum to one, while total external arrival rates agree in the two directions. Thus the reversed process has the same local departure functions and is again an open migration process.

If no directed routing path returns from $k$ to $j$, the set of colonies reachable from $k$ has no outgoing edge to its complement. The complement is an autonomous open migration process, and the marked $j\to k$ transition is an exit from it. In time reversal of an open migration process, that exit is a state-independent Poisson immigration channel of rate ${\alpha }_j{p}_{jk}$. Reversing a stationary two-sided Poisson process preserves its law, proving the forward stream is Poisson. This argument does not assert Poisson internal streams for networks with feedback.

For positive traffic rates in single-server colonies, a total service budget $F>{\sum }_j{\alpha }_j$ minimizes the stationary mean population when the spare rates ${\varphi }_j-{\alpha }_j$ are proportional to $\sqrt{{\alpha }_j}$. The Cauchy-Schwarz inequality proves the optimum directly.

For an open migration process, colony $j$ with population $k$ has total departure rate ${\varphi }_j(k)$. Its stationary weight is $b_j(k)={\alpha }_j^k/{\prod }_{h=1}^k{\varphi }_j(h)$. The colony weights factor independently and normalize when ${\sum }_{k\ge 0}{b}_j(k)<\infty$ for every colony. Global balance for a continuous-time Markov chain proves the formula even when routing is not reversible.

With row vectors, external arrival rates $\nu$ and transient routing matrix $P$, the total arrival rates satisfy $\alpha =\nu +\alpha P=\nu (I-P{)}^{-1}$. These include all internal migrations and do not depend on colony service speeds.

A flow-level model treats each document transfer as a flow whose rate depends on the current occupancy and resource capacities. With independent Poisson processes for arrivals and independent unit-mean exponential distributions for sizes, a route's total completion rate equals its allocated aggregate service.

A positive balance function $\Phi$ expresses each active route's aggregate service as this ratio. With independent Poisson arrivals and exponential document sizes, detailed balance yields stationary weights $\Phi (n){\prod }_r{\rho }_r^{n_r}$, provided their sum is finite.

The proportionally fair allocation on a four-cycle has aggregate service $P/(P+Q)$ on each active odd route and $Q/(P+Q)$ on each active even route. With Poisson arrival rates ${\nu }_r$ and exponential document-size parameters ${\mu }_r$, the departure intensity is ${\mu }_r{n}_r{x}_r$. The adjacent ratios of the displayed binomial coefficient weight cancel those intensities in detailed balance, with ${\rho }_r={\nu }_r/{\mu }_r$.

For offered loads on consecutive routes $a,b,c,d$ of the reversible proportionally fair allocation on a four-cycle, the normalizing sum of the stationary distribution isThis formula applies in the stability region for the reversible four-cycle flow network. Grouping populations on opposite routes gives ${\sum }_{s,t}\left(\genfrac{}{}{0ex}{}{s+t}{s}\right)h_s(a,c)h_t(b,d)$, where $h_s(a,c)={\sum }_{i=0}^s{a}^i{c}^{s-i}$. For distinct opposite loads, substituting $h_s=(a^{s+1}-c^{s+1})/(a-c)$ and summing the four geometric generating series proves the formula; continuity covers coincident loads. If all four loads equal $z<1/2$, it reduces to $(1-2z+2z^2)/(1-2z{)}^3$.

Group the normalizing sum by its odd and even flow counts. The coefficient sums are $h_p({\rho }_1,{\rho }_3)={\sum }_{i=0}^p{\rho }_1^i{\rho }_3^{p-i}$ and the analogous $h_q$ for even routes. If $a$ and $b$ are the two maximum loads, then $a^p\le h_p\le (p+1)a^p$ and similarly for $b$. The generating identity ${\sum }_{p,q}\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)a^p{b}^q=(1-a-b{)}^{-1}$ proves necessity and sufficiency of the displayed strict inequality. It is equivalent to strictly subunit offered load on each of the four resources.

A linear flow network has a through route using all resources and one local route for each individual resource. Under proportional fairness with unit resource capacities, the per-flow through rate is $1/N$, where $N$ is the total number of flows. Its exponential-document model has a balance function of a flow-level network given by $\left(\genfrac{}{}{0ex}{}{N}{n_0}\right)$.

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.

Summing the stationary law of a linear flow network over its through-flow count gives independent local geometric distributions with ratios $q_i={\rho }_i/(1-{\rho }_0)$. This gives the displayed means. The local counts are independent of one another in this marginal distribution; the through count is generally dependent on them. The independence is a stationary distributional fact, not an assertion that their dynamics evolve independently.

On unit-capacity links $1,\dots ,I$, route zero uses every link and route $i$ uses only link $i$. Let $N={\sum }_{r=0}^I{n}_r$ and $M={\sum }_{i=1}^I{n}_i$. Under proportional fairness, every active local route has $n_0{x}_0+n_i{x}_i=1$. Maximizing $n_0\log w_0+M\log (1-w_0)$ for $w_0=n_0{x}_0$ gives $w_0=n_0/N$ and the displayed per-flow rates on active routes. At the empty state departures vanish, and rates of absent flows may be set to zero.

A two-resource linear flow network has one local route on each of two resources and one through route using both. With unit capacities and proportional fairness, its exponential-document flow-level network model has the stationary law of a two-resource linear flow network. The local counts are independent in equilibrium despite their dependence on the shared through-route count.

For route offered loads ${\rho }_1,{\rho }_2,{\rho }_0$, the balance function of a flow-level network $\Psi (a,b,c)=\left(\genfrac{}{}{0ex}{}{a+b+c}{c}\right)$ gives the stationary distributionThe negative binomial series sums over $c$, and two geometric sums give $B=(1-{\rho }_0-{\rho }_1)(1-{\rho }_0-{\rho }_2)/(1-{\rho }_0)$ under the stability conditions for a two-resource linear flow network.

In the stationary law of a two-resource linear flow network, the local counts are independent geometric variables with parameters $q_i={\rho }_i/(1-{\rho }_0)$. Conditional on local counts $a,b$, the through count has a negative binomial distribution with mean ${\rho }_0(a+b+1)/(1-{\rho }_0)$. With positive loads, it is correlated with each local count, even though those two local counts are independent. Degenerate zero-load cases must be distinguished from the positive-load assertion.

The stationary law of a two-resource linear flow network is normalizable exactly whenThese are the strict offered-load constraints on the two unit-capacity resources. Summing first over the through-route count reduces normalization to two geometric series, which diverge at equality. With positive arrival rates, the nonexplosive continuous-time Markov chain is then positive recurrent.

For local counts $a,b$, through count $c$, and $N=a+b+c>0$, proportional fairness gives aggregate through service $c/N$. Every active local route receives aggregate service $(a+b)/N$, divided equally among its active flows. Inactive routes receive zero aggregate service. This maximizes weighted logarithmic utility subject to both unit-capacity constraints.

The proportionally fair allocation on a four-cycle produces a reversible Markov chain with stationary distribution proportional to $\left(\genfrac{}{}{0ex}{}{n_1+n_2+n_3+n_4}{n_1+n_3}\right){\prod }_r{\rho }_r^{n_r}$. This is normalizable exactly when every resource's offered load is strictly below capacity, equivalently $\max ({\rho }_1,{\rho }_3)+\max ({\rho }_2,{\rho }_4)<1$.

A fluid model replaces discrete counts by continuous quantities whose evolution follows averaged large-scale drifts. A heuristic drift calculation motivates such a model; proving a fluid limit requires a separate convergence argument.

For a two-coordinate fluid model with $\dot{s}=g(n/s)$, $\dot{n}=f(n/s)$ and $s>0$, set $\kappa =n/s$ and $du/dt=1/s$. Then $d\kappa /du=f(\kappa )-\kappa g(\kappa )$ and $d\log s/du=g(\kappa )$. A bounded ratio eventually confined where $g\le -\eta <0$ makes $s$ decay exponentially in the new time. Since $dt/du=s$, the original fluid time has a finite terminal value and both coordinates tend to zero. This is a useful finite-time draining of a fluid model argument; the singular origin is treated by a stopped trajectory.

A nonnegative fluid model drains in finite time if all its coordinates approach zero at a finite terminal time. A ratio-based ordinary differential equation can become undefined at that endpoint; an absorbing extension is an additional modeling convention.

A fluid limit is a scaling limit of a stochastic process obtained by scaling space and time so that random fluctuations vanish and a deterministic trajectory remains. It can justify a fluid model when the required convergence conditions hold.

For a density-dependent Markov jump process with finitely many jump vectors, bounded nonnegative rates and Lipschitz drift $F(x)={\sum }_{\ell }\ell {\beta }_{\ell }(x)$, an initial state converging in probability to $x_0$ gives uniform convergence in probability on every finite horizon to the ODE $\dot{x}=F(x)$, $x(0)=x_0$. The compensated martingale has expected maximal squared size $O(N^{-1})$ by the Doob L2 maximal inequality; Gronwall's inequality transfers that estimate to the solution error.

// Target: probability-and-statistics.bigb

If the rate functions are bounded and Lipschitz on an invariant compact state space, the Poisson time-change representation of a Markov chain has drift $F={\sum }_j{v}_j{\beta }_j$. Each centered Poisson term is uniformly small after division by $n$. The Gronwall inequality then bounds the distance to $\dot{z}=F(z)$ by the initial error and the centered counting error, multiplied by $e^{LT}$. A Poisson maximal concentration bound gives exponentially decreasing error probabilities for a fixed horizon and fixed error tolerance.