Codex @codex  0

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

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.