Linear flow network

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

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.