Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sự sụp đổ không gian trạng thái với ứng dụng vào giới hạn lưu lượng nặng cho các mạng hàng đợi đa lớp
Tóm tắt
Giới hạn lưu lượng nặng cho các mạng hàng đợi đa lớp là một chủ đề vẫn được quan tâm. Hiện nay, lớp mạng mà trong đó các giới hạn này đã được chứng minh một cách nghiêm ngặt còn hạn chế. Một thành phần quan trọng trong công việc này là việc chứng minh sự sụp đổ không gian trạng thái. Trong bài báo này, chúng tôi chứng minh sự sụp đổ không gian trạng thái cho hai họ mạng, cụ thể là mạng hàng đợi loại FIFO (first-in first-out) theo kiểu Kelly và mạng chia sẻ bộ xử lý theo tỷ lệ đầu hàng (HLPPS). Sau đó, chúng tôi áp dụng kỹ thuật của mình cho các mạng tổng quát hơn. Để chứng minh sự sụp đổ không gian trạng thái cho các mạng FIFO loại Kelly và mạng HLPPS, chúng tôi sử dụng định luật số lớn để chỉ ra một dạng tính chất compact cho các nghiệm được chuẩn hóa một cách thích hợp. Các giới hạn của những nghiệm này sẽ được chỉ ra rằng thỏa mãn các phương trình mô hình lưu chất tương ứng với các mạng hàng đợi nêu trên. Kết quả từ Bramson [4,5] về hành vi tiệm cận của các giới hạn này sau đó suy ra sự sụp đổ không gian trạng thái. Các giới hạn lưu lượng nặng mong đợi cho các mạng hàng đợi loại FIFO và HLPPS sẽ theo từ điều này cũng như các tiêu chí tổng quát được nêu trong bài báo đồng hành của Williams [41]. Sự sụp đổ không gian trạng thái và các giới hạn lưu lượng nặng phát sinh cũng đúng với các mạng hàng đợi tổng quát hơn, với điều kiện rằng nghiệm của các phương trình mô hình lưu chất của chúng hội tụ. Một số kết quả từng phần được đưa ra cho các mạng như vậy, bao gồm các kỷ luật ưu tiên tĩnh.
Từ khóa
#mạng hàng đợi #lưu lượng nặng #sụp đổ không gian trạng thái #mô hình lưu chất #tỷ lệ chia sẻ bộ xử lýTài liệu tham khảo
F. Baskett, K.M. Chandy, R.R. Muntz and F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. ACM 22 (1975) 248-260.
A. Bernard and A. El Kharroubi, Régulation de processus dans le premier orthant de Rn, Stochastics and Stochastics Rep. 34 (1991) 149-167.
M. Bramson, Instability of FIFO queueing networks, Ann. Appl. Probab. 4 (1994) 414-431.
M. Bramson, Convergence to equilibria for fluid models of FIFO queueing networks, Queueing Systems 22 (1996) 5-45.
M. Bramson, Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks, Queueing Systems 23 (1997) 1-26.
M. Bramson, Stability of two families of queueing networks and a discussion of fluid limits, Queueing Systems 28 (1998) 7-31.
M. Bramson, Nonuniqueness of FIFO fluid models of Kelly type (1998), in preparation.
H. Chen and A. Mandelbaum, Discrete flow networks: Diffusion approximations and bottlenecks, Ann. Probab. 19 (1991) 1463-1519.
H. Chen and H. Zhang, Diffusion approximations for re-entrant lines with a first-buffer-first-served priority discipline, Queueing Systems 23 (1996) 177-195.
H. Chen and H. Zhang, Diffusion approximations for some multiclass queueing networks with FIFO service disciplines, preprint.
J. Dai, On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid models, Ann. Appl. Probab. 5 (1995) 49-77.
J. Dai and J.M. Harrison, The QNET method for two-moment analysis of closed manufacturing systems, Ann. Appl. Probab. 3 (1993) 968-1012.
J. Dai and T. Kurtz, A multiclass station with Markovian feedback in heavy traffic, Math. Oper. Res. 20 (1995) 721-742.
J. Dai and V. Nguyen, On the convergence of multiclass queueing networks in heavy traffic, Ann. Appl. Probab. 4 (1994) 26-42.
J. Dai and Y. Wang, Nonexistence of Brownian models for certain multiclass queueing networks, Queueing Systems 13 (1993) 41-46.
M.H.A. Davis, Piecewise deterministic Markov processes: A general class of nondiffusion stochastic models, J. Roy. Statist. Soc. Ser. B 46 (1984) 353-388.
V. Dumas, Instability cycles in fluid Bramson networks, IEEE Trans. Automat. Control (1998), to appear.
J.M. Harrison, The diffusion approximation for tandem queues in heavy traffic, Adv. in Appl. Probab. 10 (1978) 886-905.
J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, in: Stochastic Differential Systems, Stochastic Control Theory and their Applications, IMA Volumes in Mathematics and its Applications 10 (Springer, New York, 1988) pp. 147-186.
J.M. Harrison, Balanced fluid models of multiclass queueing networks: A heavy traffic conjecture, in: Stochastic Networks, IMA Volumes in Mathematics and its Applications 71 (Springer, New York, 1995) pp. 1-20.
J.M. Harrison and V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems 6 (1990) 1-32.
J.M. Harrison and V. Nguyen, Brownian models of multiclass queueing networks: Current status and open problems, Queueing Systems 13 (1993) 5-40.
J.M. Harrison and R.J. Williams, Brownian models of feedforward queueing networks: Quasireversibility and product form solutions, Ann. Appl. Probab. 2 (1992) 263-293.
D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic I, Adv. in Appl. Probab. 2 (1970) 150-177.
D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic II, Adv. in Appl. Probab. 2 (1970) 355-364.
D.P. Johnson, Diffusion approximations for optimal filtering of jump processes and for queueing networks, Ph.D. thesis, University of Wisconsin (1983).
F.P. Kelly, Networks of queues with customers of different types, J. Appl. Probab. 12 (1975) 542-554.
F.P. Kelly, Reversibility and Stochastic Networks (Wiley, New York, 1979).
S.H. Lu and P.R. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automat. Control 36 (1991) 1406-1416.
W.P. Peterson, Diffusion approximations for networks of queues with multiple customer types, Math. Oper. Res. 9 (1991) 90-118.
M.I. Reiman, Open queueing networks in heavy traffic, Math. Oper. Res. 9 (1984) 441-458.
M.I. Reiman, Some diffusion approximations with state space collapse, in: Proc. of the Internat. Seminar on Modeling and Performance Evaluation Methodology, Lecture Notes in Control and Informational Sciences, eds. F. Baccelli and G. Fayolle (Springer, New York, 1984) pp. 209-240.
M.I. Reiman, A multiclass feedback queue in heavy traffic, Adv. in Appl. Probab. 20 (1988) 179-207.
M.I. Reiman and R.J. Williams, A boundary property of semimartingale reflecting Brownian motions, Probab. Theory Related Fields 77 (1988) 87-97. (Correction 80 (1989) 633.)
S. Rybko and A. Stolyar, Ergodicity of stochastic processes that describe the functioning of open queueing networks, Problems Inform. Transmission 28 (1992) 3-26 (in Russian).
T.I. Seidman, “First come, first served” can be unstable! IEEE Trans. Automat. Control 39 (1994) 2166-2171.
A. Stolyar, On the stability of multiclass queueing networks, in: Proc. of the 2nd Conf. on Telecommunication Systems — Modeling and Analysis, Nashville (1994) pp. 1020-1028.
W. Whitt, Weak convergence theorems for priority queues: preemptive-resume discipline, J. Appl. Probab. 8 (1971) 74-94.
W. Whitt, Large fluctuations in a deterministic multiclass network of queues, Managm. Sci. 39 (1993) 1020-1028.
R.J. Williams, On the approximation of queueing networks in heavy traffic, in: Stochastic Networks, Theory and Applications, Royal Statistical Society Lecture Note Series, eds. F.P. Kelly, S. Zachary and I. Ziedlins (Clarendon Press, Oxford, 1996) pp. 35-56.
R.J. Williams, Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse, Queueing Systems 30 (1998) 27-88.