Queueing theory

The long-run fraction of time a work-conserving server is busy. Applying Little's law to the server alone gives utilization equal to admitted queue throughput times mean service time. In a finite-buffer queue, the blocking probability must be included in that throughput.

For a work-conserving single-server queue with independent Poisson arrivals, finite buffer and independent identically distributed admitted service times of mean $\mu$, Poisson arrivals see time averages give admitted rate $\lambda (1-P_n)$. Little law for the server alone then gives the displayed busy fraction. The time parameter is the mean service duration, and need not be exponentially distributed.

The long-run rate at which admitted customers complete service. In a stable queue without abandonment it equals the admitted arrival rate, which may be less than the offered rate because of blocking. Little's law uses this actual rate for the chosen subsystem.

The total time between admission to a selected queueing system and departure. It includes waiting and service if both are inside the chosen system, and only service time if the selected system consists of the server alone. Little's law relates its mean to mean population and admitted queue throughput.

The time a customer occupies a server while receiving service. Its mean is a duration; its reciprocal is a service rate. An exponential distribution is convenient for Markov queue models, but Little's law can use a general finite mean.

In equilibrium, a queue is quasireversible when its present state is independent of subsequent arrival times and preceding departure times, for each customer class. For an M-M-s queue, detailed balance and time reversal of a continuous-time Markov chain show that past departures become future arrivals generated independently of the present state. This backward independence is useful in tandem calculations where downstream occupancy is determined by earlier departures.

Poisson arrivals of rate $\lambda$ and $s$ independent exponential servers of rate $\mu$ give a birth-death chain with departure rate $\mu \min (n,s)$. The process is positive recurrent for $\lambda <s\mu$, null recurrent at equality, and transient above capacity.

A stable equilibrium M-M-s queue has a Poisson process of departures with the same rate as its input. Its present population is also independent of past departures, a component of quasireversibility. The birth-death process satisfies detailed balance; reversed upward jumps have a constant arrival rate, so they are generated by an independent Poisson process.

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.

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.

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.

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

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

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.

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.

After failures, a transmitter increases its random retry window by a multiplicative factor, so its access behavior depends on its collision history. This reduces immediate repeated contention, but its stability and delay properties depend on the exact rule and traffic model.

After $k$ collisions a packet chooses an independent counter uniformly from $\{0,\dots ,2^k-1\}$ and retries when it expires. The window doubles after a further collision. This is an example of exponential backoff with a nonconstant retry rule, contrasting with constant-probability slotted ALOHA.

Throughput is the long-run rate of successful work. In an ideal stationary activation model with unit transmission speed, station $r$ has throughput equal to its stationary active fraction $\mathbb{E}[n_r]$.

Carrier-sense multiple access lets a station attempt transmission only when interfering neighbors are inactive. An ideal continuous-time model gives inactive station $r$ an exponential attempt rate $e^{{\theta }_r}$ and unit-rate exponential transmission completions. Detailed balance then gives activation weights $e^{\theta \cdot n}$ on the independent sets of the interference graph.

An interference graph has one graph vertex for each station and an edge for every pair that cannot transmit simultaneously. Feasible activation schedules are the graph's independent sets.

For feasible independent set activation vectors $S$, the throughput region is their convex hull. Its downward closure is the same set because deleting active vertices preserves feasibility. Ideal carrier-sense multiple access can supply strict margins above every vector in its interior by adjusting attempt rates.

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.

With independent Poisson arrivals of any positive rate and a fixed retry probability $0<f\le 1$, the infinite-population slotted ALOHA model eventually has collisions in every slot almost surely. For $f<1$, an exponential-supermartingale escape bound proves transience of the backlog chain. Bounded martingale increments then give backlog growth at the arrival rate, and the Conditional Borel-Cantelli lemma makes the exponentially unlikely noncollision slots finite in number. At $f=1$, two old packets suffice for permanent collisions. At $f=0$ the assertion is false.

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.

This feedback family in slotted ALOHA gives $g(\kappa )=A\{2/(e-2)-[e/(e-2)](1+\kappa )e^{-\kappa }\}$, which changes sign at contention ratio one. For $0\le \nu <e^{-1}$, the ratio drift $h=\nu -\kappa e^{-\kappa }-\kappa g$ is strictly negative on $[1,\infty )$ and on some interval beginning below one. The ratio time change for a homogeneous fluid model traps the ratio in a region where $g<0$ and proves finite-time draining. For $\nu >e^{-1}$, backlog drift is at least $\nu -e^{-1}>0$ regardless of this controller. These are statements about the interior fluid model, not a stand-alone theorem of stochastic stability.

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.

Adding a link to a nonatomic traffic flow network can increase the equilibrium travel delay. Extra routes change the incentives defining a Wardrop equilibrium, so the new equilibrium need not retain an earlier good allocation. The system-optimal delay cannot worsen when the old allocation remains feasible; the paradox concerns selfish equilibrium.

For a differentiable link delay $D_j(y)$, the toll $T_j(y)=y{D}_j^{\prime }(y)$ charges a user for the additional delay imposed on the other users. Its perceived link cost is the derivative of $y{D}_j(y)$. The resulting Beckmann potential equals total travel delay. If total delay is convex, its Wardrop equilibria minimize that delay globally. Strict increase of $D_j$ alone does not imply this convexity; optimal-flow calibrated congestion tolling avoids that extra requirement.

Let $y^{\ast }$ be a globally delay-minimizing feasible vector of link throughputs. For continuously differentiable strictly increasing delays, calibrated tollsmake the marginal social costs at $y^{\ast }$ equal the perceived route costs there. First-order route-exchange conditions make $y^{\ast }$ a tolled Wardrop equilibrium. The nonnegative nondecreasing penalty vanishes at the optimum; choosing ${\epsilon }_j>0$ makes the toll genuinely traffic-dependent. The perceived link delays remain strictly increasing, so their Beckmann potential gives unique equilibrium link loads. Every tolled Wardrop equilibrium therefore has the globally optimal $y^{\ast }$, even when the total-delay objective is not convex.

Strictly increasing link delays make Wardrop equilibrium link throughputs unique, but route decompositions of those throughputs can differ. With unit demand through two successive stages of two parallel links each and link delay $D(u)=u$, the four-route vectors $(t,1/2-t,1/2-t,t)$ for $0\le t\le 1/2$ all induce link loads $1/2$. All routes then have equal delay one.

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

On a three-node loss network, each pair offers direct calls of load $v$ to its link of capacity $C$. If blocked, the call tries the two-link path through the remaining node. The symmetric reduced-load approximation gives a link its direct load and two overflow contributions $vB(1-B)$, hence the displayed equation. For $C=1000$, $v=940$, its residual has alternating signs at $B=0,0.01,0.10,0.25$, giving at least three distinct roots. This multiplicity belongs to the Erlang fixed point approximation, not to the exact stationary law of a finite reachable Markov chain.

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

For offered load $a$ and capacity $C\ge 1$, the carried load equals the mean occupancy:Differentiating the truncated-Poisson equilibrium weights gives $m_C^{\prime }(a)={\mathrm{Var}}_a(N)/a>0$ for $a>0$. The carried load increases from zero to $C$. This monotonicity supplies the strictly increasing term in the convex potential for the Erlang fixed point.

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.

Set $y_j=-\log (1-B_j)$ and let $e_C(a)=E(a,C)$. For positive integer capacities,The function $U$ is the carried load of an Erlang loss resource evaluated at its inverse blocking parametrization. It is continuous and strictly increasing from zero to $C$. Hence $F$ is a coercive function and a strictly convex function on the nonnegative orthant. Its first-order conditions are the fixed-routing Erlang fixed point equations, including zero prices at unused links.

Update one link blocking probability at a time using the reduced load accepted by all other links, then cycle through the links. In logarithmic acceptance coordinates this is exact coordinate descent for the convex potential for the Erlang fixed point. Potential values decrease within a compact sublevel set. Continuity of a whole-sweep update forces every limit point to minimize every coordinate, hence to equal the unique global minimizer. This proves convergence without requiring a simultaneous substitution scheme.

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.

The Poisson arrivals see time averages property says that an external Poisson process independent of a stationary system sees the system-state distribution at its arrival times. Thus the fraction of arrivals that accept a state-dependent admission rule $p(n)$ is ${\sum }_n{\pi }_{n}p(n)$.

An $M/G/1$ queue has Poisson arrivals, independent identically distributed service times, and one server. If service has mean $m$ and $\lambda m<1$, its mean busy period isThis follows by decomposing the busy period into the first service and the busy-period descendants of arrivals during that service.

An M-D-1 queue has a Poisson process of arrivals, a deterministic service time $\tau$, and one work-conserving server. With arrival rate $\lambda$ and $\lambda \tau <1$, its equilibrium idle probability is $1-\lambda \tau$: the stationary completed work per unit time is $\lambda \tau$. Its output generally need not be a Poisson process.

Let $Q_n$ be the number left immediately after departure $n$, and let $A_n$ be the arrivals during the next service. ThenConditional on service duration $S$, $A_n$ is Poisson with parameter $\lambda S$, so

For a stable $M/G/1$ queue with traffic intensity $\rho =\lambda \mathbb{E}S<1$, the mean waiting time before service isEquivalently, the mean number in the system is

In a stable regenerative queue,where $L$ is mean population, $\lambda$ is throughput, and $W$ is mean sojourn time. Renewal reward proves it by identifying the area under the population path with the sum of customer sojourn times.