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

Put $\mu ={\mu }_1+{\mu }_2$. In this heterogeneous two-server queue, the total population alone is not a Markov process: when only one customer is present, its departure rate depends on which server is occupied. Use states $0,a,b,2,3,\dots$, where $a$ and $b$ distinguish the two single-customer possibilities, and $n\ge 2$ records the total population. The memoryless property of the exponential distributions gives these nonzero transition rates:and $q_{n,n+1}=\nu$ for $n\ge 2$, $q_{n,n-1}=\mu$ for $n\ge 3$. In particular, a departure from state $2$ leaves the other server occupied.

The detailed balance equations suggestFor example, both ${\pi }_a\nu ={\pi }_2{\mu }_2$ and ${\pi }_b\nu ={\pi }_2{\mu }_1$ hold; these are the two transitions that would be lost by using only population as the state. All other adjacent-state detailed balance equations hold as well. Since $\nu /\mu <1$, the geometric series converges, and normalization givesThus the stationary distribution exists, and the requested probability isWith equal server rates ${\mu }_1={\mu }_2=m$, this reduces to ${\nu }^2/[m(2m+\nu )]$, as for an M-M-s queue with two servers.

To prove the output claim, put the continuous-time Markov chain in its stationary distribution. The preceding detailed balance equations make it a reversible Markov chain: time reversal of a continuous-time Markov chain has the same transition rates. A forward departure becomes a reversed arrival. In every reversed state, the total rate of such arrivals is $\nu$: from $0$ the rates $\nu /2$ add, from $a$ or $b$ the upward rate is $\nu$, and from every $n\ge 2$ it is also $\nu$. The reversed process can therefore be constructed with an independent rate-$\nu$ Poisson process of arrival epochs, choosing the idle server by a fair coin when appropriate. Consequently reversed arrival counts on disjoint time intervals are independent Poisson random variables with the corresponding means. Reversing those intervals proves that the stationary departure stream is a rate-$\nu$ Poisson process, rather than merely a stream with mean rate $\nu$.

Stationarity matters here. If the queue starts empty, a departure by time $h$ requires both an arrival and a completed service time, so its probability is $O(h^2)$; a rate-$\nu$ Poisson process would have probability $\nu h+O(h^2)$. Thus the output assertion is the equilibrium assertion in the context of the preceding stationary calculation.

An open migration process has finitely many colonies and state $n\in {\mathbb{N}}^J$. External arrivals to colony $j$ form independent Poisson processes with rates ${\nu }_j$. When $n_j=k>0$, individuals leave that colony at total rate $g_j(k)>0$, with $g_j(0)=0$. A departing individual moves to $k$ with probability $p_{jk}$ or exits with probability $p_{j0}=1-{\sum }_k{p}_{jk}$. The routing choices and all arrival and service randomness are independent. The routing matrix $P=(p_{jk})$ is substochastic and transient: every individual eventually exits, equivalently its spectral radius is less than one. Self-routing is allowed, but creates no state change.

The traffic equations of an open migration process, using row vectors, areThe inverse matrix exists because ${\sum }_{m\ge 0}{P}^m$ converges; its $(k,j)$ entry counts expected visits to $j$ by an individual entering at $k$. Thus ${\alpha }_j$ includes both external arrivals and internal migrations. Restrict first to the accessible colonies with ${\alpha }_j>0$.

SetIf each $Z_j<\infty$, the candidate product-form stationary distribution of an open migration process isHere is a global balance for a continuous-time Markov chain proof, which does not incorrectly assume that the routing is reversible. The weight ratio is $\pi (n+e_j)/\pi (n)={\alpha }_j/g_j(n_j+1)$. After dividing the incoming balance equation at $n$ by $\pi (n)$, external arrivals contribute ${\sum }_{j:n_j>0}{\nu }_j{g}_j(n_j)/{\alpha }_j$, exits contribute ${\sum }_j{\alpha }_j{p}_{j0}$, and migrations from $k$ to $j\ne k$ contribute ${\sum }_{j:n_j>0}{\sum }_{k\ne j}{g}_j(n_j){\alpha }_k{p}_{kj}/{\alpha }_j$. Combining the first and third contributions using the traffic equations of an open migration process yields ${\sum }_j{g}_j(n_j)(1-p_{jj})$. Summing those same traffic equations of an open migration process gives ${\sum }_j{\alpha }_j{p}_{j0}={\sum }_j{\nu }_j$. The incoming rate is therefore exactly the outgoing rateThis proves stationarity. With finite arrival rates, finite service rates in each state and transient routing, the process is nonexplosive: only finitely many individuals enter in a finite interval, and each makes finitely many routing transitions before exit, almost surely. On the accessible irreducible Markov chain, a finite normalizer gives the unique stationary distribution and positive recurrence. Colonies with zero effective arrivals are empty in this equilibrium. For a nonempty accessible colony, a divergent $Z_j$ prevents normalization of the equilibrium weights.

For the single-server specialization, $g_j(k)={\varphi }_j$ for $k>0$. Each colony has the stationary distribution of an M-M-1 queue:requiring ${\varphi }_j>{\alpha }_j$ on every colony with positive traffic. The service rates do not change the traffic equations of an open migration process.

For positive ${\alpha }_j$, write $B=F-{\sum }_j{\alpha }_j$ and $s_j={\varphi }_j-{\alpha }_j$. A stable allocation requires $B>0$ and $s_j>0$, with ${\sum }_j{s}_j=B$. The Cauchy-Schwarz inequality givesEquality holds precisely when $s_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence the unique optimal service-capacity allocation in an open migration process and its mean population areThere is no stable allocation when $F\le {\sum }_j{\alpha }_j$ and some traffic is positive. If some ${\alpha }_j=0$, those empty colonies contribute no population; allocate the spare capacity to the positive-traffic colonies by the same rule. Allowing zero capacity at an unused colony attains this optimum. If strictly positive ${\varphi }_j$ are required even there, the displayed value is only an infimum, approached as their capacities tend to zero. If every ${\alpha }_j=0$, the equilibrium is empty and any admissible allocation minimizes its mean population at zero.

For a fixed routing loss network, let $C_j$ be finite integer resource capacities and $A_{jr}$ the integer resource requirement of one route-$r$ call. Assume each route uses a resource, independent Poisson processes of calls with rates ${\nu }_r$, independent exponential distributions of holding times with parameters ${\mu }_r$, and immediate rejection when any required resource is unavailable. There is no waiting. The continuous-time Markov chain of call counts has feasible setPut ${\rho }_r={\nu }_r/{\mu }_r$ andThe ratios of adjacent weights satisfy $\pi (n){\nu }_r=\pi (n+e_r){\mu }_r(n_r+1)$ whenever the arrival is feasible. Thus detailed balance proves the product-form stationary distribution of a loss network,An arriving route-$r$ call is admitted precisely when $An\le C-A_{\cdot r}$. By Poisson arrivals see time averages, its exact blocking probability isDefine $Z$ to be zero if a capacity is negative. This is an exact finite sum, not an independence approximation for resource blocking events.

For the triangle, denote the physical link capacities by $C_{12},C_{13},C_{23}$ and the numbers of calls between the pairs by $n_{12},n_{13},n_{23}$. Assume unit capacity per call on each traversed link, unrestricted instantaneous rearrangement of existing calls, no interruption or extra resource cost during rearrangement, and independent exponential distributions of holding times whose parameters depend on the endpoint pair but not on the chosen path. Arrivals for each pair are independent Poisson processes, and admission occurs whenever some routing of all calls is feasible. These assumptions make the count vector a Markov process even though individual paths can change.

The necessary cut constraints areEach counts calls that must cross the two links separating one node from the others. They are also sufficient. If every pair count is at most its direct capacity, route all calls directly. Otherwise at most one pair can exceed its direct capacity: two such excesses would contradict their pairwise cut constraint. Suppose it is $12$, and put $d=n_{12}-C_{12}>0$. Route $C_{12}$ of these calls directly and divert the remaining $d$ through node $3$. Route the other calls directly. The loads on links $13$ and $23$ are respectively $n_{13}+d\le C_{13}$ and $n_{23}+d\le C_{23}$ by the two cut constraints involving $n_{12}$. This is an integer routing of every call. The other cases follow by relabelling.

Consequently the rearrangeable triangular loss network is equivalent, at the level of call counts and blocking, to a fixed routing loss network with three virtual node resources:The columns correspond to $12,13,23$, and a call uses its two endpoint resources. Its normalizer isWith $e_j$ now indexing virtual resources, the three exact answers areThe preceding detailed balance proof applies because departures occur at rates ${\mu }_{ab}{n}_{ab}$ regardless of the current routing. Without unrestricted rearrangement, feasibility can depend on the existing path assignments and this equivalence need not hold.

Let $R_s$ be the routes serving source-sink pair $s$. The source-sink route incidence matrix and link-route incidence matrix areThus $Hx=f$ fixes the demands, and $y=Ax$ gives link throughputs. Assume a finite route set with at least one route for each positive demand. A Wardrop equilibrium is a feasible flow for which every used route has minimum delay among the routes for its source-sink pair. Writingthis means that, for each $s$, there is a number ${\lambda }_s$ with $c_r(x)\ge {\lambda }_s$ for $r\in R_s$, with equality whenever $x_r>0$. No individual user can reduce its delay by switching routes while treating the aggregate throughputs as fixed.

The feasible set $K=\{x\ge 0:Hx=f\}$ is a nonempty compact convex set: within each source-sink pair its route flows lie in a simplex of total $f_s$. The Beckmann potentialis continuous and convex, and has $\partial \Phi /\partial x_r=c_r(x)$. It therefore attains a minimum on $K$. For a differentiable convex function, $x$ minimizes $\Phi$ exactly whenIndeed necessity follows by differentiating along the feasible segment from $x$ to $z$, and sufficiency follows from the supporting-tangent inequality. This condition is equivalent to Wardrop equilibrium. Necessity of the route condition follows by moving a small amount of positive flow from a used route to any other route of the same pair. Conversely, under the route condition,because the terms involving $x_r$ vanish and both flows have the same pair totals. This proves both existence and the claimed convex optimization characterization, with $y=Ax$.

Since each $D_j$ is strictly increasing, its primitive is strictly convex. Thus ${\sum }_j{\int }_0^{y_j}{D}_j(u)du$ is strictly convex in $y$. If two minimizing flows had different link throughputs, their midpoint would have strictly smaller potential. Hence the equilibrium link throughputs are unique.

The route flows need not be unique. Consider one unit of demand through two successive stages, each with two parallel links, labelled $a,b$ in the first stage and $c,d$ in the second. The four routes are $ac,ad,bc,bd$, and all link delays are $D_j(u)=u$. For any $0\le t\le 1/2$, chooseEvery link then carries $1/2$ and every route has delay one, so each vector is a Wardrop equilibrium. They all produce the same link throughputs but give distinct route decompositions.

For the toll construction, put $F={\sum }_s{f}_s>0$. The total delay is $L(x)={\sum }_j{y}_j{D}_j(y_j)$ and the average delay is $L(x)/F$, so they have the same minimizers. Compactness of $K$ gives a global minimizer $x^{\ast }$, with $y^{\ast }=A{x}^{\ast }$. Its differentiable objective satisfies the necessary route-flow inequalityThis inequality is necessary even when total delay is not convex, since it follows from the right derivative along each feasible segment.

Use optimal-flow calibrated congestion tolling:Here $(v{)}_{+}=\max (v,0)$. The toll is nonnegative, continuously differentiable and nondecreasing, because $D_j^{\prime }\ge 0$. The perceived cost ${\hat{D}}_j(u)=D_j(u)+T_j(u)$ is strictly increasing. At $y_j^{\ast }$ it equals $D_j(y_j^{\ast })+y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$, so the displayed necessary inequality makes $x^{\ast }$ a Wardrop equilibrium for these perceived costs, by the preceding Beckmann potential argument. Their strictly increasing costs give unique equilibrium link throughputs. Therefore every tolled equilibrium has link loads $y^{\ast }$ and minimizes average delay. Constant tolls $T_j(u)=y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$ also suffice; the added positive-part term makes them genuinely traffic-dependent without moving the optimum. Zero total demand is the trivial empty-flow case.

The usual marginal external cost toll $T_j(u)=u{D}_j^{\prime }(u)$ makes its Beckmann potential equal $L$, but concluding that all its equilibria minimize $L$ requires convexity of $L$. Strict increase of delays alone does not supply this. For example, on two parallel links with $D(u)=1-e^{-u}$ and demand six, the equal split $(3,3)$ is an equilibrium under marginal-cost tolls, while its total delay $6(1-e^{-3})$ exceeds $4(1-e^{-4})+2(1-e^{-2})$, the delay at $(4,2)$. The calibrated construction avoids adding a hypothesis absent from the printed question.

Each user maintains a transmission rate $x_r$. Resource $j$ measures its aggregate load $y_j={\sum }_{r:j\in r}{x}_r$ and returns the resource congestion price ${\mu }_j=p_j(y_j)$. The user adds these feedback signals to form its route congestion price $c_r={\sum }_{j\in r}{\mu }_j$. Its increase term is the constant ${\kappa }_r{w}_r$, while its decrease term ${\kappa }_r{x}_r{c}_r$ is proportional to both its current rate and the congestion signal. This is a distributed congestion control algorithm: resources need only local loads, and users need only prices along their own routes.

There is a needed distinction in the word increasing. If it permits nondecreasing price functions, the all-zero prices are allowed. Then ${\dot{x}}_r={\kappa }_r{w}_r>0$, so there is no equilibrium. The intended convergence statement holds when each nonempty route meets at least one resource whose price is positive at some load. This is automatic if every price is strictly increasing and nonnegative. We prove it under the more general nondecreasing assumption with this explicit condition, for finite sets of nonempty routes and nonnegative initial rates.

Write $P_j(y)={\int }_0^y{p}_j(u)du$. Each $P_j$ is convex and nondecreasing, and the primal congestion potential isOn positive rates this is strictly concave: the sum of positive-weight logarithms is strictly concave, while the resource term is convex. Its derivatives areConsequently the gradient flow with diagonal mobility satisfieswith equality exactly at an equilibrium.

We must also prove trapping and existence of the equilibrium. For each route choose a resource on it and constants $M_r,c_r^0>0$ such that its price is at least $c_r^0$ beyond load $M_r$. Finiteness gives common constants $M,c>0$. If $X={\max }_r{x}_r$ is large, a resource on a maximizing route has load at least $X$, so the resource penalty is at least $c(X-M)$. With $W={\sum }_r{w}_r$, therefore,Once all rates are bounded above, a rate tending to zero also makes $U\to -\infty$ through its positive-weight logarithm. Thus every nonempty superlevel set of $U$ is compact inside the positive orthant. A maximum exists by restricting to such a superlevel set, and strict concavity makes it unique, say $x^{\ast }$. It is interior and satisfies ${\partial }_{r}U(x^{\ast })=0$, equivalentlyConversely every positive equilibrium is a stationary point of the strictly concave function $U$ and hence is this maximum.

Only continuity of the price functions is given, so it is useful to justify trajectories without silently assuming differentiability. Put $z_r=2\sqrt{x_r/{\kappa }_r}$ and $V(z)=U(({\kappa }_r{z}_r^2/4{)}_r)$. The dynamics become ordinary gradient flow ascent, $\dot{z}=\nabla V(z)$. The function $V$ is strictly concave on the positive orthant: its user terms are $2w_r\log z_r$ plus constants, and each penalty is a convex nondecreasing function $P_j$ composed with the convex load ${\sum }_{r:j\in r}{\kappa }_r{z}_r^2/4$. Hence the supporting-tangent inequalities giveThe squared distance between two solutions is nonincreasing, proving uniqueness even though the vector field need only be continuous.

Nonnegative initial rates enter the positive orthant immediately: along a solution, variation of constants in ${\dot{x}}_r+{\kappa }_r{c}_r(t)x_r={\kappa }_r{w}_r$ expresses $x_r(t)$ as a positive exponential times $x_r(0)$ plus a strictly positive integral. Also ${\dot{x}}_r\le {\kappa }_r{w}_r$, so rates cannot become infinite in finite time. The distance argument applies after any positive time and, by taking that time down to zero, also proves uniqueness for initial zero rates.

For a positive starting time, the increasing $U$ traps the trajectory in a compact superlevel set. Its derivative has finite integral since $U$ is bounded above there. It is uniformly continuous in time, being a continuous function of the state on a compact set with bounded velocity. By uniformly continuous integrable functions vanish at infinity, $\dot{U}(t)\to 0$. Every limit point consequently has ${\partial }_{r}U=0$ for every $r$, since all rates are bounded away from zero. There is only the limit point $x^{\ast }$, soThis establishes global convergence of primal congestion control with the needed nonzero-price condition, and supplies the zero-price counterexample when increasing is read in the weak sense.

For the alternative increasing-supply resource-price dynamics, consider the dual congestion potentialIts domain is ${\mu }_j\ge 0$ with every $c_r>0$. Each integrated supply is strictly convex, because $q_j$ is strictly increasing, and each negative logarithm of a positive linear function is convex. Thus $H$ is strictly convex. Its sublevel sets are bounded: for each $j$, $q_j(1)>0$ gives a linear lower bound on the supply primitive at large ${\mu }_j$, whereas the negative logarithmic terms grow only logarithmically in ${\max }_j{\mu }_j$. A route-price sum tending to zero makes $H\to +\infty$ on a bounded set. A minimum therefore exists in this domain.

The derivatives areIf a used resource had ${\mu }_j=0$ at the minimum, then $q_j(0)=0$ but $y_j>0$, so increasing that coordinate would strictly lower $H$. Therefore the minimizer has strictly positive prices at every used resource. An unused resource has its unique minimizing price zero. At used resources its equations areThe multiplicative dynamics are ${\dot{\mu }}_j=-{\kappa }_j{\mu }_j{\partial }_{j}H$. On strictly positive used-resource prices, equilibrium is equivalent to these equations, and strict convexity proves existence and uniqueness of the positive equilibrium. No full-row-rank assumption on $A$ is needed here: the strictly increasing individual supplies already give strict convexity.

If zero prices at used resources are allowed, the unqualified uniqueness assertion is false because of boundary equilibria of multiplicative resource prices. For one unit-weight route using two resources and $q_1(u)=q_2(u)=u$, all three price vectorsare equilibria. At $(1,0)$ the user rate is one; the first resource has demand equal to supply, while the second has zero derivative because its price is zero. The last two vectors do not minimize $H$. Thus the positive-price domain, or a boundary rule preventing a used resource from remaining at zero price, is essential.

Finally, the primal and dual equilibrium equations agree when $q_j$ and $p_j$ are inverse functions on the relevant ranges. For example, continuous strictly increasing prices with $p_j(0)=0$ and $p_j(y)\to \infty$ have inverses satisfying the stated supply assumptions. Then ${\mu }_j=p_j(y_j)$ is equivalent to $y_j=q_j({\mu }_j)$, while both systems have $x_r=w_r/c_r$. With inverse price and supply functions, the two equilibria describe the same rates and prices. Without this relation they need not agree: for one route and one resource with $w=1$, $p(y)=y$ and $q(\mu )=2\mu$, the primal equilibrium is $(x,\mu )=(1,1)$ while the dual equilibrium is $(\sqrt{2},1/\sqrt{2})$.

Here $x_r$ is the rate per individual active flow, and $n_r{x}_r$ is its route's aggregate rate. On routes with $n_r>0$, a proportionally fair allocation is a feasible positive rate vector satisfyingfor every feasible competitor $\tilde{x}$, where feasibility means ${\sum }_{r:j\in r}{n}_r{\tilde{x}}_r\le C_j$. This is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$: its gradient gives the displayed inequality, and the supporting-tangent inequality proves sufficiency. The objective is strictly concave on active rates. Rates assigned to absent flows are irrelevant and may be set to zero.

For the linear flow network, an active local route can increase its rate if its link constraint has slack, improving the objective without affecting any other link. ThusPut $m={\sum }_{i=1}^I{n}_i$ and $N=n_0+m$. If $n_0>0$ and $m>0$, eliminate the active local rates by $x_i=(1-n_0{x}_0)/n_i$. Up to constants, the utility becomesIts derivative is $n_0/x_0-n_{0}m/(1-n_0{x}_0)$, which vanishes exactly atStrict concavity proves this is the optimum, and unused local links impose no stronger constraint because $n_0{x}_0\le 1$. If $m=0<n_0$, maximizing $n_0\log x_0$ gives $x_0=1/n_0$, the same formula. If $n_0=0$, each active local route has $x_i=1/n_i$. These are the proportionally fair allocation on a linear flow network. When $N=0$, there is no service to allocate.

The memoryless property of exponential document sizes makes a flow transmitting at rate $x_r$ complete with intensity ${\mu }_r{x}_r$. Summing over its $n_r$ flows gives the flow-level network model transition ratesand, for nonempty states,All absent-route departure intensities, including those at the empty state, are zero. In particular the local completion rate is the aggregate rate ${\mu }_{i}m/N$, not ${\mu }_i/N$. Total rates are bounded by ${\sum }_r{\nu }_r+{\sum }_r{\mu }_r$, so the continuous-time Markov chain is nonexplosive.

Set ${\rho }_r={\nu }_r/{\mu }_r$ and consider the weightsThe binomial coefficient is the balance function of a flow-level network. For a through-route arrival, its adjacent-weight ratio isThe reverse departure rate is ${\mu }_0(n_0+1)/(N+1)$, so $w(n+e_0)q(n+e_0,n)=w(n){\nu }_0$. For a local-route arrival,and the reverse departure rate is ${\mu }_i(m+1)/(N+1)$, giving the same detailed balance identity. This includes arrivals from the empty state.

To normalize, first fix all local counts and sum over $n_0$. The negative binomial series givesThe remaining geometric series factor, soThis is finite precisely under the stated strict load inequalities ${\rho }_0+{\rho }_i<1$ for each resource. Thus detailed balance proves the stationary law of a linear flow network:With positive arrival rates this is the unique stationary distribution of the irreducible chain. Zero arrival rates are handled by restricting to the accessible class with their counts zero, interpreting $0^0=1$.

Summing this distribution over $n_0$ gives local-count independence in a linear flow network:These are independent geometric distributions. Differentiating a geometric series, or summing its mean directly, givesThis independence concerns the local counts at one stationary time; their evolving processes share the through route and are not independent processes.