Queueing theory

Queueing theory studies how jobs accumulate while waiting for limited service: customers at a desk, requests at a computer, or calls competing for a connection. A queue model specifies how jobs arrive, their service times, the number of servers, the buffer size of a queue, and the service discipline. Its practical questions include the queue population, queueing delay, customer sojourn time, queue throughput, and server utilization.

Average spare capacity does not guarantee short waits. Even when the service rate of a queue exceeds the arrival rate, bursts of arrivals and unusually long service times can leave work waiting. The M/M/1 utilization and delay example shows that an 80 percent server utilization can turn a 12-minute mean service time into a 60-minute mean customer sojourn time. As capacity is approached, congestion grows sharply; reserving spare capacity can be much more valuable than its idle fraction suggests.

Two complementary ideas make queueing theory especially useful. Little's law converts a measured queue population and queue throughput into a mean customer sojourn time, using a counting identity rather than a particular arrival law. Poisson arrivals see time averages answers a different question: when do arriving customers see the same state frequencies as an observer sampling over time? That requires an exogenous Poisson process and a system that cannot anticipate its future arrivals. Neither result by itself determines all queueing delays; detailed models such as the M/M/1 queue and M/G/1 queue supply the remaining information.

An asymptotic description obtained by increasing queue resources or input size, or by approaching critical load while rescaling time and workload. Large-buffer queue scaling, many-source queue scaling, moderate-deviation queue scaling and the heavy-traffic limit of a queue preserve different relations between mean load, random fluctuations and storage.

For fixed independent and identically distributed arrivals of mean $\mu$ and positive finite variance ${\sigma }^2$, put service at $\mu +\epsilon d$. Rescaling net input by space $\epsilon$ and time ${\epsilon }^{-2}$ gives Brownian motion with drift $-d$ by the functional central limit theorem. The continuous Skorokhod reflection map on the half-line gives the displayed transient limit, with a correspondingly scaled initial workload. A stationary approximation additionally requires justification of limit interchange. When valid, the stationary law of negatively drifted reflected Brownian motion predicts $\mathbb{P}(Q_{\epsilon }>b/\epsilon )\approx e^{-2db/{\sigma }^2}$.

For a bufferless queue with Poisson mean input $L\lambda$, place the service margin at $C{L}^{(1+\beta )/2}$, $0<\beta <1$. It exceeds the ordinary square-root fluctuation scale but is sublinear in total input. The Poisson moderate deviation principle gives the displayed overflow exponent. This interpolates between a central-limit safety margin and a fixed per-source excess capacity.

Scale independent source count, service and buffer by the same factor $L$. For lookback horizon $n$, the source-average cumulative input has rate function $I_n$, and reaching buffer level $b$ requires input above $b+cn$. Optimizing this horizon gives the displayed exponent under uniform control of the infinite stationary supremum. For independent slots, $I_n(x)=n{I}_A(x/n)$; discrete time keeps $n$ an integer. Temporal dependence instead enters through the cumulative-input cumulant-generating function.

Hold a stable input law and service rate of a queue fixed while the buffer size of a queue grows. Under interior exponential-moment and root hypotheses, the Cramér-Lundberg workload exponent gives an exponential tail linear in buffer size. A likely overflow accumulates during a lookback horizon proportional to the buffer size.

For nondegenerate independent and identically distributed arrivals with mean below $c$, suppose the positive root is interior to the moment-generating function domain. Then ${\Lambda }_A^{\prime }({\theta }_{\ast })>c$. The Fenchel–Young inequality gives $t{I}_A(c+1/t)\ge {\theta }_{\ast }$ for every $t>0$, and equality occurs at $t=[{\Lambda }_A^{\prime }({\theta }_{\ast })-c{]}^{-1}$. The exponential workload bound from cumulative arrival moments gives the upper logarithmic tail bound for every $\theta <{\theta }_{\ast }$. A horizon of the indicated length times buffer size gives the matching lower bound by Cramér's theorem. A positive interior root is an assumption; if arrivals never exceed capacity, positive workload cannot arise.

Let the independent arrivals satisfy $\mathrm{Pr}(G_n=j)=q{p}^j$, with $p+q=1$. During a busy period, each served customer produces $G_n$ further customers, so the total number served has the total-progeny law of a Galton-Watson process with mean $p/q$. Its extinction probability solves $s=q/(1-ps)$ and is the smaller of $1$ and $q/p$. The queue is positive recurrent for $p<1/2$, null recurrent for $p=1/2$, and transient for $p>1/2$. In the positive recurrent case its stationary distribution is ${\pi }_j=(1-p/q)(p/q{)}^j$.

Poisson arrivals of rate $\lambda$ receive independent service times distributed as $S$, with infinitely many servers so service starts on arrival. Starting empty, the occupancy at time $t$ is Poisson with mean $\lambda {\int }_0^t\mathbb{P}(S>u)du$, by independent thinning of the marked arrivals. If $\mathbb{E}S<\infty$, the equilibrium count is Poisson with mean $\lambda \mathbb{E}S$. Occupancy need not be a Markov process for a general service law; remaining service times carry additional state information.

Stop new arrivals at time $t$ in an initially empty general-service infinite-server queue. The number remaining $v$ time units later is Poisson with mean $\lambda {\int }_v^{t+v}\mathbb{P}(S>u)du$. Thus the probability that clearance has not occurred is one minus the exponential of the negative of that mean. Letting $t\to \infty$ gives the displayed equilibrium formula, since ${\int }_v^{\infty }\mathbb{P}(S>u)du=\mathbb{E}(S-v{)}_{+}$. The clearance time is zero when no customers remain at closing.

A continuous-time Markov chain may alternate between an arrival phase $C$, with upward transitions at rate $\lambda$, and a service phase $W$, with downward transitions at rate $\mu$ when the level is positive. Switching rates $C\to W$ and $W\to C$ are $\alpha ,\beta$. Its stationary balance equations give a geometric invariant tail with ratio $\theta =\lambda (\mu +\beta )/[\mu (\lambda +\alpha )]$. A stationary probability exists exactly when $\mu \alpha >\lambda \beta$, consistent with the stationary average service rate $\mu \alpha /(\alpha +\beta )$ exceeding the arrival rate $\lambda \beta /(\alpha +\beta )$.

A queue consists of customers or jobs waiting for or receiving service. An arrival process adds customers and a service rule specifies which waiting customer is served next. A stochastic model of these events is studied in queueing theory; its queue length is the number of customers waiting or in service, according to the stated convention.

The population $N(t)$ of a queue counts every admitted customer still inside the selected system at time $t$, including customers receiving service when the server is inside that boundary. Its long-run time average is $L$. The waiting population $N_q(t)$ excludes customers currently receiving service, and its long-run time average is $L_q$. For a single server that serves whenever work is present,where $\rho$ is the server utilization, assuming at most one customer receives service at a time. In a stationary process with ergodicity and finite expected values, these time averages equal $\mathbb{E}N(t)$ and $\mathbb{E}{N}_q(t)$. The workload of a queue instead counts unfinished work, so two queues with the same population can have very different remaining workloads.

The size and frequency of unusually large arrivals or sustained overload episodes. It depends on the time and threshold scales being examined, rather than just on the one-slot variance. A cap can leave smaller rare deviations unchanged while removing larger positive bursts.

A queue which retains no unfinished work between slots. Given nonnegative input $A$ and capacity $c$, its bufferless queue output is $\min (A,c)$ and its lost work is $(A-c{)}^{+}$.

For fixed Poisson mean $\lambda >0$ and capacity $c\to \infty$, set $m=\lfloor c\rfloor +1$. The optimized Chernoff bound gives $\log \mathbb{P}(X\ge m)\le -I_P(m)$. The lower bound by $\mathbb{P}(X=m)$ and Stirling's formula differs by only $O(\log m)$. Rounding $m$ to $c$ changes the cost by $O(\log c)$, proving the displayed formula and the leading scale $-c\log c$.

The work served in one slot is capped at the service rate of a queue. The remainder is lost, so output is input minus its positive part above capacity. Every downstream threshold below the cap has exactly the same overflow event for input and output; thresholds at or above the cap cannot be exceeded by the output.

Clip Poisson input of mean $L\lambda$ at $L\lambda +C{L}^{(1+\beta )/2}$. The Poisson moderate deviation principle and contraction principle for large deviations give the displayed output rate at the clipping scale. At smaller exponents the output retains the original rate by moderate deviations below a bufferless queue cap. At larger positive-deviation scales every overflow event is eventually impossible because the requested threshold exceeds the cap.

For Poisson input and $u_L=L\lambda +C{L}^{(1+\beta )/2}$ with $C>0$, clipping occurs with logarithmic probability $-C^2{L}^{\beta }/(2\lambda )$. At any smaller exponent $0<\alpha <\beta$, this is superexponentially small at speed $L^{\alpha }$. Dividing the input and output difference by $L^{(1+\alpha )/2}$ therefore gives exponential equivalence. More directly, for every threshold $r_L<u_L$, the events $\{\min (S_L,u_L)>r_L\}$ and $\{S_L>r_L\}$ are identical.

An arrival exceeds the available service and storage capacity, causing work to be lost or blocked. For a bufferless queue with capacity $c$ per slot, overflow means input work strictly greater than $c$. Stationary queue workload tails in an infinite-buffer comparison model are often used to estimate finite-buffer overflow probabilities.

The maximum stored work or number of waiting jobs, according to the model's convention. A bufferless queue has no room to retain excess input for a later slot.

The amount of work a queue can serve per unit of time. In a slotted model the same units can describe work served per slot.

The queueing delay is the time between a customer's arrival and the start of its service, excluding its own service time. Under first come first served with service rate $C$, its queueing delay is the queue workload ahead of it divided by $C$. The customer sojourn time also includes the customer's own service. In a preemptive priority queue with a shared buffer, a voice customer's initial waiting time depends only on the voice queue workload already present.

The queue workload of a queue is the total remaining service work of all present customers, including residual work in service. With a work-conserving server of rate $C$ and stationary input $A$, the stationary queue workload is represented byThis is the amount by which past offered work exceeds available service, maximized over possible starts of a busy period. It is the reflection of net input at zero. Under first come first served, an arriving infinitesimal customer waits $W/C$; a priority customer instead waits for the remaining work ahead of it under its service discipline.

For independent and identically distributed arrivals with finite mean below service $c$, the strong law of large numbers makes the net cumulative input tend to minus infinity, so the supremum is finite almost surely. Applying the same formula to the past input gives a stationary solution of the Lindley recursion. This representation turns queue workload overflow into an event involving some lookback horizon.

For a stable input with path action $I(a)={\int }_{-\infty }^{0}g({\dot{a}}_s)ds$, a workload x requires some interval of length t with average input near $C+x/t$. Jensen inequality bounds its cost below by $tg(C+x/t)$; taking the supremum workload and then the infimum over t yields the displayed lower bound. Constant-rate burst paths give the matching upper bound. At zero the typical-rate path has zero cost; negative workloads have infinite rate. If no finite-cost rate exceeds C, every positive workload has infinite rate.

Use arrival rate v during the last t time units and the normal stable rate mu before that, where $\mu <C$. The lookback net input increases from zero to x over the burst, then decreases because the earlier net drift is negative. Its infinite-buffer workload is x, as is the finite-buffer workload map for capacity at least x. For a local convex path cost with density g and $g(\mu )=0$, its cost is $tg(v)=xg(v)/(v-C)$. These paths realize or approximate the optimal workload cost even if an optimizing duration is not attained.

With lookback net input $z(s)=a(-s,0]-Cs$, the stable finite-buffer workload is ${\sup }_{t\ge 0}\min ({\sup }_{0\le s\le t}z(s),B+{\inf }_{0\le s\le t}z(s))$. Since $z(0)=0$, it lies between zero and B, and is at most the infinite-buffer supremum $q(a)={\sup }_{s\ge 0}z(s)$. For a constant-rate burst which builds exactly x work from an empty queue, no upper reflection occurs when $x\le B$ and both workloads equal x.

Use the clipped Lindley recursion $q_{t+1}=\min (B,\max (0,q_t+x_t-C))$ and the weighted cumulative-input topology for a slotted queue. If cumulative past input $S_x(T)\le \lambda T$ eventually with $\lambda <C$, choose a finite $T$ so $S_x(T)-CT<-B$. Starting with a full buffer at time $-T$, the queue must hit zero before the present, since otherwise its final workload is at most $B+S_x(T)-CT<0$. Monotonicity couples all initial workloads by that zero, establishing a finite memory horizon. The same horizon works for sufficiently close input $y$. Since $|x_{-k}-y_{-k}|\le (2k-1)\Vert x-y\Vert$ and clipping is Lipschitz continuous with constant one, the two finite recursions started empty differ by at most ${\sum }_{k=1}^T(2k-1)\Vert x-y\Vert =T^2\Vert x-y\Vert$.

For the local convex action defining the linear workload rate for a local convex action, continuity and the contraction principle for large deviations give workload rate functions. The pointwise bound ${\bar{q}}_B\le q$ makes ${\bar{J}}_B(x)\ge {\inf }_{y\ge x}J(y)=J(x)$ on nonnegative workloads. Constant-rate burst paths produce the reverse bound for x at most B. Values outside the buffer interval are impossible. This statement concerns the rate at the workload value, rather than equality of exact finite-buffer and infinite-buffer stationary distributions.

For arrivals added before the slot's offered service, $Z_k$ is the arriving work minus that service. With independent identically distributed increments of negative mean, the stationary queue workload has the law ${\sup }_{m\ge 0}{\sum }_{j=1}^m{Z}_j$. Iterating the recursion from the past gives this supremum; the strong law makes it finite. A different arrival/service ordering changes slot-boundary workload but requires its convention to be stated.

Consider two work-conserving slotted queues in tandem, with upstream service $c$ and downstream service $d<c$, where upstream departures can be served downstream in the same slot. Put $D_t=\min \{c,Q_{t-1}+a_t\}$. Then $Q_t=Q_{t-1}+a_t-D_t$ and $R_t=(R_{t-1}+D_t-d{)}^{+}$. If $R_{t-1}+D_t\ge d$, addition gives $(Q_{t-1}+R_{t-1}+a_t-d{)}^{+}$. Otherwise $D_t<d<c$, so the upstream queue empties and both sides of that identity are zero. Thus total workload obeys the Lindley recursion with service $d$. Starting empty in the remote past yields the displayed identity whenever the upstream workload is finite. Both workloads, and hence their difference, are continuous in the weighted cumulative-input topology for a slotted queue under strictly subcritical mean input $\lambda <d<c$.

A queue with a Poisson process of arrivals and two independent service times with exponential distributions of different rates must distinguish the two possible single-customer states. If an arrival chooses either idle server with probability $1/2$, the continuous-time Markov chain is reversible. Write $a,b$ for the states with only server one or two busy, and $n\ge 2$ for total population. Its detailed balance equations give ${\pi }_a={\pi }_0\nu /(2{\mu }_1)$, ${\pi }_b={\pi }_0\nu /(2{\mu }_2)$ and ${\pi }_n={\pi }_0{\nu }^2(\nu /\mu {)}^{n-2}/(2{\mu }_1{\mu }_2)$. These weights normalize exactly when $\nu <\mu$. In equilibrium, reversed upward transitions have total rate $\nu$ in every state, so time reversal of a continuous-time Markov chain makes the departure stream a Poisson process of rate $\nu$. This output conclusion requires stationarity.

A busy period is the interval from an arrival that finds the system empty until the next departure leaving it empty. It excludes the preceding idle waiting time. In a stable M/G/1 queue with arrival rate $\lambda$ and mean service time $m$, its mean is $m/(1-\lambda m)$.

In an M/G/1 queue, arrivals during the first service generate independent subtrees of work. Conditional on service time $S=s$, the number of descendants is Poisson with mean $\lambda s$. Thus $B\stackrel{d}{=}S+{\sum }_{j=1}^{N(S)}{B}_j$, with independent descendant busy periods. Conditioning and the Poisson generating function give the displayed transform equation wherever its moment-generating functions are finite. Taking expectations yields $\mathbb{E}B=\mathbb{E}S+\lambda \mathbb{E}S\mathbb{E}B$ in the stable regime.

An ordered state $x=(c_1,\dots ,c_n)$ records the classes and positions of customers at a single server. Class-$r$ arrivals have rate ${\alpha }_r$ and exponential service parameter ${\mu }_r$. Under a symmetric service discipline, its stationary distribution is $(1-\rho ){\prod }_i({\alpha }_{c_i}/{\mu }_{c_i})$, where $\rho ={\sum }_r{\alpha }_r/{\mu }_r<1$. If every ${\mu }_r=\mu$, class-independent insertion and service position rules need not be equal: time reversal of a continuous-time Markov chain interchanges them and proves the same law. Aggregating words gives $(1-\rho )n!{\prod }_r[({\alpha }_r/{\mu }_r{)}^{n_r}/n_r!]$ by the multinomial coefficient. With class-dependent service rates, first come first served need not have this product law.

A two-class queue has one total buffer but serves the high-priority class before the other. A preemptive-resume service discipline interrupts low-priority work immediately and later resumes it without wasting completed work. Under first come first served within the high-priority class, a new high-priority packet waits $V/C$ when $V$ is the high-priority workload immediately before its arrival. The total workload determines shared-buffer overflow, while $V$ determines the high-priority waiting time. An additional admission gate rejects high-priority packets when $V/C$ exceeds a prescribed delay limit. Finite packets require a fit test against the remaining buffer space, and nonpreemptive service adds residual low-priority service time.

Assume independent stationary Compound Poisson process inputs, preemptive-resume priority for voice, first come first served within each class, capacity $C$, a shared buffer of $B$ units of work, packet sizes bounded by $s_{\max }<B$, and voice delay gate $D>0$. Write $B_0=B-s_{\max }$ and $K=CD$. For $n_v,n_d$ flows with per-flow effective bandwidths $a_v,a_d$, the continuous-time exponential workload bound givesprovided $n_v{a}_v({\theta }_T)+n_d{a}_d({\theta }_T)\le C$ and $n_v{a}_v({\theta }_V)\le C$. To prove this, couple with the unthinned infinite-buffer aggregate and voice queues driven by the same offered packets. Dropping work reduces both the total and voice workloads under this service discipline. A buffer-fit failure implies total workload greater than $B_0$, and a voice-gate failure implies voice workload at least $K$. Apply the two bounds and a union bound; Poisson arrivals see time averages converts stationary prearrival probabilities to offered-packet loss fractions. For target losses ${\ell }_d,{\ell }_v$, choose $0<{\eta }_B<\min ({\ell }_d,{\ell }_v)$ and ${\eta }_V={\ell }_v-{\eta }_B$, then setThe two effective bandwidth constraints, together with strict aggregate mean-load stability, define a sufficient integer admission region. Voice loss includes the shared-buffer term, even though data packets have lower service priority.

A service discipline specifies which customers receive the server's capacity and where newly arriving customers join the queue. First come first served and processor sharing give different sample paths even when their equilibrium populations agree.

In an ordered queue, let ${\gamma }_i(n)$ be the fraction of service capacity assigned to position $i$ when $n$ customers are present. A symmetric discipline inserts an arrival into position $i$ with probability ${\gamma }_i(n+1)$. The same position rule for service and insertion makes transitions satisfy detailed balance for the word weights ${\prod }_i{\alpha }_{c_i}/{\mu }_{c_i}$. It accommodates class-dependent exponential service rates; processor sharing is an example.

A nonempty server divides its capacity equally among all customers present. With class-$r$ exponential service parameter ${\mu }_r$, population $n_r$, and total population $n$, the class departure rate is ${\mu }_r{n}_r/n$. The resulting class-count process is a continuous-time Markov chain.

A queue serves customers in arrival order. For multiple classes, retaining this order generally requires an ordered multiclass single-server queue state, rather than only a vector of class counts.

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. If customers leave without completing service, service completions alone cannot replace the admission rate when measuring the customer sojourn times of all admitted customers.

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.

The useful infinite-horizon path space for a stable queue isFor $\delta ,\sigma >0$, the workload functional $R(f)={\sup }_{t\ge 0}(\sigma f(t)-\delta t)$ is finite and continuous. Fix $f$, and choose $T\ge 1$ so that $|\sigma f(t)|\le \delta t/4$ for $t\ge T$. If $\Vert g-f{\Vert }_{\mathrm{sl}}<\delta /(4\sigma )$, then $\sigma g(t)-\delta t<0$ for $t\ge T$. Both suprema can thus be taken over $[0,T]$, whereUniform convergence on bounded time intervals alone does not give this continuity: a pulse escaping to later times can produce a large workload while tending locally to zero.

For one-sided past inputs, let $A_n(a)={\sum }_{j=0}^{n-1}{a}_{-j}$ and $A_0=0$. The displayed metric controls cumulative differences over every past window, including the latest arrival. On the affine class $A_n(a)/n\to \lambda <c$, the queue workload $Q(a,c)={\sup }_{n\ge 0}(A_n(a)-cn)$ is locally Lipschitz continuous. To prove this, choose $\epsilon =(c-\lambda )/4$ and $N\ge 1$ such that $A_n(a)/n\le \lambda +\epsilon$ for $n\ge N$. If $d_{\#}(a,b)<\epsilon /2$, then $A_n(b)-cn\le n(\lambda +2\epsilon -c)<0$ for all such $n$. Both suprema reduce to $0\le n<N$, and their difference is at most $(N+1)d_{\#}(a,b)$. Ignoring the latest coordinate makes this assertion false for a post-slot workload of a queue.

Let a centered Gaussian process $Z$ satisfy $Z(a\cdot )\stackrel{d}{=}{a}^{H}Z$ with $0<H<1$, and suppose $Z/\sqrt{L}$ has a large deviation principle in the sublinear path space for fluid queues, with speed $L$ and good rate function $I$. For $\delta ,\sigma >0$, put $r={\sup }_{t\ge 0}(\sigma Z(t)-\delta t)$ and $\kappa =2(1-H)$. Self-similarity gives $Z(N\cdot )/N\stackrel{d}{=}Z/\sqrt{N^{\kappa }}$. Time substitution and the contraction principle for large deviations therefore give an LDP for $r/N$ with speed $N^{\kappa }$ andThe same family $r/(aN)$ has rate function $J(aq)$ by contraction, and $a^{\kappa }J(q)$ by replacing $N$ with $aN$ and expressing the speed again as $N^{\kappa }$. Uniqueness of a rate function gives $J(aq)=a^{\kappa }J(q)$, hence $J(q)=q^{\kappa }J(1)$ for $q>0$, with $J(0)=0$.

A closed migration process is a continuous-time Markov chain of populations moving between colonies with a conserved total number of individuals. A colony containing $k$ individuals has departure rate ${\varphi }_j(k)$, with ${\varphi }_j(0)=0$, and each departure chooses its next colony using a fixed routing matrix. Its colony populations can represent stages of a service system, including an idle stage.

// Target: probability-and-statistics.bigb

Represent $N$ telephone lines by a closed migration process with free-line, operator and automated-service colonies. Accepted arrivals have rate $\nu$ when a free line exists, $c$ operators complete at rate $\lambda \min (k,c)$, and $i$ automated calls complete at rate $\mu i$. Define $D_c(k)={\prod }_{h=1}^k\min (h,c)$ andThe product-form stationary distribution of a closed migration process and Poisson arrivals see time averages give the displayed blocking probability. This extends a single-operator model without treating the independent operators as a server with rate $c\lambda$ when fewer than $c$ calls are present.

// Target: probability-and-statistics.bigb

In a one-operator closed migration process representing a finite-line switchboard, let $K$ count calls waiting for or receiving the operator's connection service and let $I$ count connected calls. At a stationary distribution, the expected drift of $K$ is $\nu \mathrm{Pr}\{K+I<N\}-\lambda \mathrm{Pr}\{K>0\}=0$, and that of $I$ is $\lambda \mathrm{Pr}\{K>0\}-\mu \mathbb{E}[I]=0$. Poisson arrivals see time averages identifies the full-state probability with $P_{\mathrm{loss}}$. Thus the accepted arrival rate, operator throughput and completed-call rate coincide. This is a useful independent check on the product-form stationary distribution of a closed migration process.

For an irreducible closed migration process with finite population $N$, positive departure rates and routing matrix $P$, choose positive traffic weights satisfying $\theta =\theta P$. On ${\sum }_j{n}_j=N$, its stationary distribution has the displayed form. For a predecessor $m=n+e_j-e_k$, its weighted transition into $n$ is $\pi (n)({\theta }_j/{\theta }_k)P_{jk}{\varphi }_k(n_k)$. Summing over $j$ gives $\pi (n){\varphi }_k(n_k)$ by the traffic equation, and summing over $k$ proves global balance for a continuous-time Markov chain. The distribution need not satisfy detailed balance.

// Target: probability-and-statistics.bigb

Connect multiclass single-server queues by Markovian routing. Each node must either have common exponential service parameters across its classes or use a symmetric service discipline. If the traffic equations for a multiclass queueing network give loads ${\rho }_j={\sum }_r{\lambda }_{jr}/{\mu }_{jr}<1$, its equilibrium word law is the product of the individual queue laws. Queue populations are independent at a fixed equilibrium time. A proof reverses routing with $p_{ba}^{\ast }={\lambda }_a{p}_{ab}/{\lambda }_b$, external arrivals with ${\nu }_a^{\ast }={\lambda }_a{p}_{a0}$, and exits with $p_{a0}^{\ast }={\nu }_a/{\lambda }_a$, and interchanges the insertion and service position rules. Weight ratios verify each reversed transition, and the traffic equations match total rates. This is a quasireversibility construction. A standard ordered-queue formulation is described in Walton's paper on multiclass queueing networks, Section 2.

For queue-class pairs $a$, external arrival rates ${\nu }_a$, and routing probabilities $p_{ab}$, the effective throughputs satisfy ${\lambda }_a={\nu }_a+{\sum }_b{\lambda }_b{p}_{ba}$. In an open network with routing spectral radius less than one, $\lambda =(I-P^T{)}^{-1}\nu$ is the unique nonnegative solution. Summing gives ${\sum }_a{\lambda }_a{p}_{a0}={\sum }_a{\nu }_a$, balancing total entrances and exits.

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.

Fair queueing separates traffic into queues and schedules their service to control sharing, reducing the ability of an unresponsive sender to dominate unrelated traffic merely by filling one common queue.

A congestion window bounds a sender's outstanding data according to congestion control. In TCP it is local sender state, distinct from the advertised receive window.

Maximize a sum of increasing strictly concave utilities $U_r(x_r)$ subject to $Ax\le C$, $x\ge 0$. Suppose capacities are positive, every route is nonempty, and $U_r^{\prime }(0)=\infty$. At its unique positive optimizer $x^{\ast }$, the Karush-Kuhn-Tucker conditions give nonnegative resource congestion prices $p^{\ast }$ and route congestion prices $y_r^{\ast }=U_r^{\prime }(x_r^{\ast })$. Choosing ${\nu }_r^{\ast }=x_r^{\ast }{e}^{y_r^{\ast }}$ makes each user maximize $U_r({\nu }_r{e}^{-y_r^{\ast }})-y_r^{\ast }{\nu }_r{e}^{-y_r^{\ast }}$ at ${\nu }_r^{\ast }$. It also makes $x^{\ast }$ maximize the entropy maximization for loss-network occupancy objective, since its gradient is $\log ({\nu }_r^{\ast }/x_r^{\ast })=(A^T{p}^{\ast }{)}_r$. Thus user and network optima implement the same system optimum.

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.