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.

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.

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.

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.

A random access network lets stations make transmission attempts independently using a shared medium. A collision can prevent all attempted packets from being delivered; slotted ALOHA adjusts attempt probabilities using slot feedback.

Time is divided into slots, and a slot succeeds exactly when one station transmits. With backlog $N$ and independent attempt probability $p$, the success probability is $Np(1-p{)}^{N-1}$. Fluid approximation of slotted ALOHA replaces the large-system binomial probabilities by Poisson probabilities.

When backlog $N$ and attempt-control scale $S$ are large with $N/S\approx \kappa$, idle and success probabilities approach $e^{-\kappa }$ and $\kappa e^{-\kappa }$. Expected update increments then motivate a fluid model described by ordinary differential equations.

For $N\ge 2$ backlogged stations, the largest one-slot success probability is $(1-1/N{)}^{N-1}$, attained at $p=1/N$. Its limit is $e^{-1}$; the exact finite-$N$ maximum is larger, and for $N=1$ it is one.

A Wardrop equilibrium assigns positive traffic only to routes with minimum delay for their source-sink pair. With fixed demands and continuous increasing link delays, it minimizes the Beckmann potential. Strictly increasing delays make link throughputs unique, while route flows can remain nonunique.

In an elastic-demand Wardrop equilibrium, demand $f_s$ responds to the minimum route delay ${\lambda }_s$ through $f_s=B_s({\lambda }_s)$. An inverse demand function supplies the utility term that must be subtracted from the Beckmann potential.

A strictly decreasing demand function has a decreasing inverse on its range. The utility primitive $\int P_s(u)du$ is a concave function. A positive interior reference value avoids assuming that an improper integral from zero is finite.

The Beckmann potential integrates each link's delay function. Its gradient with respect to route flows is the corresponding vector of route delays, making Wardrop equilibrium a convex optimization problem.

This matrix has $H_{sr}=1$ when route $r$ serves source-sink pair $s$, and zero otherwise. Thus $Hx=f$ aggregates route flows into source-sink demands.

The link-route incidence matrix records how much resource $j$ is used by one call or flow on route $r$. For unit requirements $A_{jr}\in \{0,1\}$; the product $Ax$ gives resource throughputs from route flows.

A loss network admits a call only when all its required resources have enough free capacity. Rejected calls do not queue. Under fixed routing and independent Poisson processes, its exact occupancy law has a product-form stationary distribution of a loss network.

Alternative routing lets a call try another resource path when its preferred route is blocked. Overflow onto longer paths can create feedback and multiple solutions of the Erlang fixed point approximation, even though an exact finite irreducible occupancy Markov chain has a unique stationary distribution.

A symmetric triangle with direct calls and two-link overflow routes has Erlang fixed point approximation equation $B=E(\lambda [1+2B(1-B)],C)$. For $C=1000$ and $\lambda =950$, this has at least three solutions, certified by the intermediate value theorem using signs at $B=0,0.01,0.1,0.4$.

For capacity $C$ and offered traffic $a$, the probability of a full single-resource loss system is $E(a,C)=(a^C/C!)/({\sum }_{k=0}^C{a}^k/k!)$. The stable recursion is $E(a,0)=1$, $E(a,k)=aE(a,k-1)/(k+aE(a,k-1))$.

The Erlang fixed point approximation treats resource blocking as independent and applies the Erlang loss formula to traffic screened by other resources. Its self-consistency equations have a unique fixed point under fixed routing, but can have several under alternative routing.

For unit resource requirements in a loss network, the effective offered traffic to resource $j$ is $a_j={\sum }_{r:j\in r}{\alpha }_r{\prod }_{k\in r\setminus \{j\}}(1-B_k)$, where $B_k$ are approximate resource blocking probabilities. The resource being modeled is excluded from its own screening product.

For calls arriving at rate ${\nu }_r$ with mean holding time $1/{\mu }_r$, offered traffic is the dimensionless load ${\alpha }_r={\nu }_r/{\mu }_r$, often measured in Erlangs. The Erlang loss formula distinguishes this offered traffic from the mean traffic actually carried.

Under fixed routing, each call type always requests the same collection of resources. The link-route incidence matrix records those requirements. This differs from alternative routing, in which a rejected direct request can try another route.

For a loss network with feasible occupancies $An\le C$, its stationary distribution is proportional to ${\prod }_r{\alpha }_r^{n_r}/n_r!$. It is the law of independent Poisson random variables conditioned on the resource constraints. With exponential holding times, detailed balance for a continuous-time Markov chain proves the formula directly.

For the standard fixed routing loss network with independent Poisson processes, the stationary occupancy law depends on independent holding-time distributions only through their means. The occupancy process alone need not be a Markov process when those holding times lack the memoryless property.