Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 30 (Stochastic Networks)

Write the clock states modulo $M$. The detailed balance equations are $p_m{\lambda }_m=\nu p_{m-1}$. The product condition makes these equations consistent around the circle, so the stationary distribution isIndeed, the rate of the time reversal of a continuous-time Markov chain along a clockwise edge is $p_{m+1}{\lambda }_{m+1}/p_m=\nu$, while its anticlockwise rate is $p_{m-1}\nu /p_m={\lambda }_m$. Thus the clock is a reversible Markov chain.

The reversed clockwise transitions can be driven by a single independent rate-$\nu$ Poisson process, since their rate does not depend on the clock state. They correspond to the original anticlockwise transitions. Consequently the anticlockwise event times form a stationary Poisson process of rate $\nu$. Its events before a given time are independent of the clock state at that time, which is the relevant quasireversibility property. If clockwise and anticlockwise transitions have the same destination, their direction is retained as an event mark when reversing the process.

Let $(m,n)$ denote the clock position and the queue population, including any customer in service. By the memoryless property of the exponential distribution, the nonzero transition rates areSet $\rho =\nu /\mu <1$. We claim thatwhere $p_m$ is the clock's stationary distribution from part (a). To check global balance for a continuous-time Markov chain, divide the incoming probability flux by $\pi (m,n)$. The clockwise contribution is $\nu p_{m-1}/p_m={\lambda }_m$. The arrival contribution, present only for $n>0$, is ${\lambda }_{m+1}(p_{m+1}/p_m){\rho }^{-1}=\mu$. The service contribution is $\mu \rho =\nu$. Their sum is the outgoing rate $\nu +{\lambda }_m+\mu 1_{\{n>0\}}$.

The proposed probability distribution is normalized, so it is the equilibrium law. In particular, the clock position and queue population are independent random variables at any fixed equilibrium time, and the population has the geometric distribution of a stable M/M/1 queue. Independence of these two random variables does not assert independence of the two entire processes.

There is now no separate rate-$\nu$ clockwise transition. The only transitions areBoth preserve $m+n$ modulo $M$. The initial state therefore selects the closed communicating class $m+n\equiv 0(\mathrm{mod}M)$, on which $m\equiv -n(\mathrm{mod}M)$. The population is a birth-death process with birth rate ${\lambda }_{-n}$ and death rate $\mu$.

Define $a_0=1$ and $a_r={\mu }^{-r}{\prod }_{j=0}^{r-1}{\lambda }_{-j}$ for $1\le r<M$. The detailed balance for a birth-death process weights areWriting $n=kM+r$ with $0\le r<M$, the product condition gives $w_n=a_r{\rho }^{kM}$. Summing the resulting geometric series yieldsThis is also the law in part (b) conditioned on $m+n\equiv 0(\mathrm{mod}M)$: the ratio of its weights at consecutive accessible populations is ${\lambda }_{-n}/\mu$. The stability condition is $\mu >\nu$, which uses the product of the periodic birth rates; it does not require $\mu >{\lambda }_m$ for every $m$.

A multiclass queue must specify its service discipline as well as its arrival and service rates. Here is an ordered-queue model that includes the usual class-independent exponential single-server queue. Let class-$r$ arrivals be independent Poisson processes of rates ${\alpha }_r$, and let a class-$r$ service requirement have the exponential distribution of rate ${\mu }_r$. A state is a finite word $x=(c_1,\dots ,c_n)$ of customer classes.

Choose service fractions ${\gamma }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\gamma }_i(n)=1$, and insertion probabilities ${\delta }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\delta }_i(n)=1$. The customer at position $i$ departs at rate ${\mu }_{c_i}{\gamma }_i(n)$; a class-$r$ arrival is inserted at position $i$ at rate ${\alpha }_r{\delta }_i(n+1)$. All rates leading to the same word are added. For class-dependent ${\mu }_r$, impose the symmetric service discipline ${\delta }_i(n)={\gamma }_i(n)$. If all ${\mu }_r=\mu$, arbitrary class-independent $\gamma ,\delta$ are permitted, including first come first served with insertion at the tail and service at the head.

Put ${\rho }_r={\alpha }_r/{\mu }_r$ and $\rho ={\sum }_r{\rho }_r$. For $\rho <1$, the equilibrium word law isFor the symmetric service discipline, insertion and deletion satisfy detailed balance for a continuous-time Markov chain becauseFor the common-service-rate case, use time reversal of a continuous-time Markov chain instead: the reversed queue inserts with probabilities $\gamma$ and serves with fractions $\delta$. A forward insertion gives a reverse deletion rate $\mu {\delta }_i$, and a forward deletion gives a reverse insertion rate ${\alpha }_r{\gamma }_i$. Forward and reverse total rates both equal ${\sum }_r{\alpha }_r+\mu 1_{\{n>0\}}$, proving global balance for a continuous-time Markov chain.

Summing the weights of all words of length $n$ gives $(1-\rho ){\rho }^n$, so the law is normalized. If $n_r$ counts class-$r$ customers and $n={\sum }_r{n}_r$, the multinomial coefficient counting class orderings givesFor processor sharing, ${\gamma }_i(n)={\delta }_i(n)=1/n$, the class-count vector itself is a Markov chain, with arrival rate ${\alpha }_r$ and departure rate ${\mu }_r{n}_r/n$. Under first come first served, the ordered word is generally necessary. Class-dependent service rates combined with first come first served do not in general have the displayed simple equilibrium law; the discipline assumption matters.

Index the queue-class pairs by $a=(j,r)$. Let ${\nu }_a$ be the external Poisson process arrival rate, let $p_{ab}$ be the routing probability after class $a$ completes service, and put $p_{a0}=1-{\sum }_b{p}_{ab}$ for the exit probability. An open network has a transient routing matrix $P$, equivalently spectral radius less than one. The effective throughputs solve the traffic equations for a multiclass queueing network:At each queue use the ordered multiclass single-server queue model of part (a), with parameters ${\mu }_{jr},{\gamma }_{ji},{\delta }_{ji}$. An external class-$a$ customer is inserted at position $i$ with rate ${\nu }_a{\delta }_{ji}(N_j+1)$. A customer of class $a$ in position $i$ completes at rate ${\mu }_a{\gamma }_{ji}(N_j)$: it exits with probability $p_{a0}$ or changes to class $b$ and is inserted at its destination with probability $p_{ab}{\delta }_{k\ell }(N_k^{\prime }+1)$. Here $N_k^{\prime }$ is the destination population after the origin deletion, so this also defines routes returning to the same queue. At each node, either service rates are common to its classes or insertion and service fractions form a symmetric service discipline.

Let ${\rho }_j={\sum }_r{\lambda }_{jr}/{\mu }_{jr}<1$. The product-form stationary distribution of a multiclass queueing network isTo prove it by time reversal of a continuous-time Markov chain, interchange each node's insertion and service fractions, and usePairs with ${\lambda }_b=0$ can be deleted. The traffic equations for a multiclass queueing network ensure ${\sum }_a{p}_{ba}^{\ast }+p_{b0}^{\ast }=1$. The ratio of the product weights for an insertion is ${\lambda }_a/{\mu }_a$; for a deletion it is its reciprocal. Consequently every routing, entrance, and exit transition satisfies $\pi (x)q(x,x^{\prime })=\pi (x^{\prime })q^{\ast }(x^{\prime },x)$. The symmetric or common-rate hypothesis makes each node's total service rate identical forward and backward. Summing the traffic equations for a multiclass queueing network also gives ${\sum }_a{\nu }_a^{\ast }={\sum }_a{\nu }_a$. Thus the total transition rates match, proving global balance for a continuous-time Markov chain; each factor is normalized by part (a).

For the class counts the equilibrium law isUnder processor sharing these counts have explicit transition rates ${\nu }_a$ for $n\to n+e_a$, ${\mu }_a{n}_a/N_j{p}_{a0}$ for $n\to n-e_a$, and ${\mu }_a{n}_a/N_j{p}_{ab}$ for $n\to n-e_a+e_b$. Under a closed network, remove external entrances and exits and normalize the same product weights on the conserved customer populations, using a positive solution of the homogeneous traffic equations for a multiclass queueing network. That finite-state normalization does not require the open-network conditions ${\rho }_j<1$.

Start from the Erlang loss formula and reverse the order in its denominator:For each fixed $j$, the product tends to $(C/\nu {)}^j$. If $\nu >C$, it is bounded by this same summable geometric series. Extend the summand by zero for $j>NC$ and apply the dominated convergence theorem with counting measure to obtainIf $\nu \le C$, retain the first $K+1$ summands. Their limiting sum is at least $K+1$, so the reciprocal tends to infinity as $K$ can be arbitrarily large. This includes $\nu =C$ without a separate normal approximation. ThereforeHere $C$ and $N$ are positive integers, as appropriate for circuit counts; taking $\lfloor NC\rfloor$ gives the same limit for a positive real capacity scale. This is the proportional scaling limit of the Erlang loss formula.

For the link-route incidence matrix $A$, the reduced-load approximation and Erlang loss formula giveIntroduce $y_j=-\log (1-B_j)$ and accepted route flows $x_r={\nu }_r{e}^{-(A^{T}y{)}_r}$. Multiplying the reduced load by the link's own acceptance probability givesThese are precisely the first-order optimality conditions for the convex potential for the Erlang fixed point, sinceEach exponential term is a convex function, and the integral of the strictly increasing function $U(\cdot ,C_j)$ is a strictly convex function. Hence $F$ is a strictly convex function. Moreover $U(z,C_j)\to C_j>0$ as $z\to \infty$, by the saturation of the carried load of an Erlang loss resource. Its integrals tend to infinity at least linearly, so $F$ is a coercive function on the nonnegative orthant and has a unique minimizer.

At $y_j=0$, $U(0,C_j)=0$. If link $j$ is used by any positive-rate route, then ${\partial }_{j}F<0$, excluding a boundary minimizer there. An unused link instead minimizes at $y_j=0$ and has zero derivative. Thus the minimizer satisfies the displayed flow equations for every link. Conversely, those equations imply $\nabla F=0$ and therefore minimize the convex potential for the Erlang fixed point. Finally $U(y,C)=a[1-E(a,C)]$ with $y=-\log (1-E(a,C))$ converts the flow equations back to $B_j=E(a_j,C_j)$. The Erlang fixed point approximation has exactly one solution under fixed routing.

The alternative routing term feeds additional traffic back into the link. We can prove the existence of three solutions rather than relying on an iteration that happens to find different answers. Choose ${\nu }_N=20N$, $C_N=21N$, and define the continuous residualBy the proportional scaling limit of the Erlang loss formula, at each fixed $B$,At $B=1/100$, the multiplier is $1.0198<21/20$, so $G_{\infty }(1/100)=-1/100$. At $B=1/8$ it is $39/32$, givingAlso $G_N(0)>0$ and $G_N(1)<0$ for every $N$, since a finite-capacity Erlang loss formula gives a blocking probability strictly between zero and one. For all sufficiently large $N$, the signs at $0,1/100,1/8,1$ therefore alternate. Applying the intermediate value theorem in the three disjoint intervening intervals proves at least three distinct fixed points. This supplies a fluid scaling proof of multiple Erlang fixed points.

This multiplicity concerns the Erlang fixed point approximation. It does not imply several equilibrium laws for an exact finite irreducible Markov chain, which has a unique stationary distribution.

The objective approximates the logarithm of the product-form stationary distribution of a loss network. To make the approximation precise, multiply arrival rates and capacities by $N$ and write $x=n/N$. The Stirling formula gives, uniformly on the feasible compact set,with $0\log 0=0$. The feasible set is $K=\{x\ge 0:Ax\le C\}$. Positive capacities and a nonempty route for each class make $K$ compact with a strictly positive feasible point. Since $H_{\nu }$ is a strictly concave function, its maximizer $x^{\ast }$ is unique; its infinite inward derivative at $x_r=0$ makes every component positive.

The Karush-Kuhn-Tucker conditions give nonnegative link Lagrange multipliers $z_j$ satisfyingFor any neighborhood of $x^{\ast }$, continuity and uniqueness give a strictly positive objective gap outside it. There are only polynomially many feasible lattice states, while their weights differ exponentially in $N$. The feasible point $\lfloor N{x}^{\ast }\rfloor$ has objective tending to $H_{\nu }(x^{\ast })$. It follows that the stationary law concentrates at $x^{\ast }$ on the scale $n/N$; in particular,Thus NETWORK predicts the dominant occupancy and mean occupancy in a large loss network. For unscaled inputs it gives a continuous approximation to the modal integer state.

It also gives an exact useful change of variables. Substituting ${\nu }_r=x_r^{\ast }{e}^{(A^{T}z{)}_r}$ into the equilibrium weights yieldsThis is Poisson exponential tilting for a loss network: independent Poisson random variables centered at the predicted occupancies, restricted to the feasible region and penalized for slack in positively priced resources. It explains why an unconstrained Gaussian approximation should not automatically be applied at a saturated capacity boundary.

Let $x^{\ast }$ maximize SYSTEM. Under the usual positive-capacity, nonempty-route assumptions, the feasible set is compact, contains a positive point, and has a Slater condition point. Strict concavity makes the optimum unique. The condition $U_r^{\prime }(0)=\infty$ forces $x_r^{\ast }>0$: moving from any optimum with a zero component slightly toward a positive feasible point gives an infinite positive directional derivative in that component and only finite losses in the positive components.

By the Karush-Kuhn-Tucker conditions, there are link Lagrange multipliers $p_j^{\ast }\ge 0$ withSet the route congestion price $y_r^{\ast }=(A^T{p}^{\ast }{)}_r=U_r^{\prime }(x_r^{\ast })$ and chooseThen $x_r^{\ast }={\nu }_r^{\ast }{e}^{-y_r^{\ast }}$, as required. For USER with fixed $y_r^{\ast }$, the substitution $x={\nu }_r{e}^{-y_r^{\ast }}$ is a bijection of the nonnegative half-line, and its objective becomes $U_r(x)-y_r^{\ast }x$. This is a strictly concave function whose derivative vanishes at $x_r^{\ast }$, so its unique maximizer is $x_r^{\ast }$ and the corresponding USER optimizer is ${\nu }_r^{\ast }$.

For NETWORK at ${\nu }^{\ast }$, its objective derivative at $x^{\ast }$ isThus $x^{\ast },p^{\ast }$ obey its Karush-Kuhn-Tucker conditions, with the same feasibility and complementary slackness. The NETWORK objective is a strictly concave function, so $x^{\ast }$ is also its unique maximizer. The triple $(x^{\ast },y^{\ast },{\nu }^{\ast })$ solves all three problems simultaneously. This is a user-network decomposition of concave utility maximization.