Largest weighted delay first scheduling: Large deviations and optimality

• 成果类型: Article
• 署名作者: Stolyar, AL; Ramanan, K
• 署名单位: AT&T; Alcatel-Lucent; Lucent Technologies
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/998926986
• 发表日期: 2001
• 页码: 1-48
• 关键词: queuing-networks; buffer

摘要

We consider a single server system with N input flows. We assume that each flow has stationary increments and satisfies a sample path large deviation principle, and that the system is stable. We introduce the largest weighted delay first (LWDF) queueing discipline associated with any given weight vector alpha = (alpha (1),...,alpha (N)). We show that under the LWDF discipline the sequence of scaled stationary distributions of the delay (w) over cap (i) of each flow satisfies a large deviation principle with the rate function given by a finite-dimensional optimization problem. We also prove that the LWDF discipline is optimal in the sense that it maximizes the quantity min(i=1,...,N) [alpha (i) lim(n --> proportional to) -1/n log P((w) over cap (i)>n)] , within a large class of work conserving disciplines.