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

• 成果类型: Article
• 署名作者: Stolyar, AL
• 署名单位: Alcatel-Lucent; Lucent Technologies; AT&T
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1060202838
• 发表日期: 2003
• 页码: 1151-1206
• 关键词: queuing-networks; Markovian processes; due-date; STABILITY; CONVERGENCE; criteria

摘要

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), . . . , alpha(N), the LWDF discipline associated with this set maximizes (among all disciplines) the quantity (1) (min)(i=1,)(,N) [alpha(1) lim(n-->infinity) (-1)/(n) log P (w(i) > n)] = lim(n-->infinity) (-1)/(n) log P (r > n), where r = 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.