Flow-level network model

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$.