We consider a multiclass queueing network with
$N$ customer classes, each having an arbitrary
fixed route through the
network. (Thus, the network is not necessarily
feedforward.)
We show that the largest weighted delay first (LWDF)
discipline
is an optimal scheduling discipline in the network
in the following sense.
Let $w_i$ be the (random) instantaneous
largest end-to-end delay of a class $i$ customer in the
network in stationary regime.
For any set of positive
constants $\alpha_1, \ldots, \alpha_N$, the LWDF discipline
associated with this set
maximizes (among all disciplines) the quantity
\[
(1)\hspace*{15pt}\min_{i=1,\ldots,N} \left[ \alpha_i \lim_{n\to\infty}
\frac{-1}{n} \log P \lb w_i > n \rb \right]
= \lim_{n\to\infty} \frac{-1}{n} \log P \lb r > n \rb,\hspace*{15pt}
\]
where $r \doteq \max_{i} w_i/\alpha_i$
is the maximal weighted delay in the network.
[This result is a generalization of the single-server
result proved by A. L. Stolyar and K. Ramanan in Ann. Appl.
Probab. 11 (2001) 1--48.]
¶ As the key element of the proof, we establish
the following critical node property:
In a LWDF network, there exists
a most likely path to build large
$r$, which is a most likely path to do so in one of the
network nodes in isolation.
Such a most likely path has a very simple structure:
its parameters [and the optimal
value of (1)]
can be computed by solving a finite-dimensional optimization
problem for each network node.