Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality (Q1425489)

One considers the queueing network control problem to find a scheduling discipline such that \( P\{w_i>T_i\}\leq \delta _i\), \(i=1,\dots ,N, \) where \(N\) is the number of traffic flows, \(w_i\) is the steady-state end-to-end delay for flow \(i\), \(T_i>0\) is a predefined delay threshold and \(\delta _i\) is the maximal acceptable deadline violation probability. It has been shown that the largest weighted delay first (LWDF) discipline is optimal to satisfy these requirements in the large deviation and heavy traffic asymptotic regimes in single-server systems. The LWDF discipline picks up for service the customer \(c^*=\text{arg}\max_c W(c)/\alpha _{i(c)},\) where the maximum is taken over the customers \(c\) available for service, \(W(c)\) is the customer's current delay and \(i(c)\) is its class. The above mentioned scheduling discipline is replaced by asymptotic ``tail'' conditions, and the satisfaction of these conditions is equivalent to solving an optimization problem. The main result of the paper: the LWDF discipline (with parameters \(\alpha _i\)) is the optimal solution of this optimization problem in a queueing network of arbitrary topology. The paper is a generalization of \textit{A. L. Stolyar's} and \textit{K. Ramanan's} result for single-server system [Ann. Appl. Probab. 11, No. 1, 1--48 (2001; Zbl 1024.60012)].