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

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.