DocumentCode :
307277
Title :
Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints
Author :
Kumar, Sunil ; Srikant, R. ; Kumar, P.R.
Author_Institution :
Graduate Sch. of Bus., Stanford Univ., CA, USA
Volume :
1
fYear :
1996
fDate :
11-13 Dec 1996
Firstpage :
779
Abstract :
We propose a new technique for upper and lower bounding the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e, where some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its steady state, we obtain linear programs whose values upper and lower bound the performance measure of interest, namely throughput or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a model for further analysis, for the M/M/s/s queue, we establish that the bounds on the blocking probability are asymptotically tight, i.e., they asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity
Keywords :
computational complexity; directed graphs; linear programming; probability; queueing theory; M/M/s/s queue; asymptotically tight bounds; blocking probabilities; buffer capacity constraints; communication networks; computational complexity; finite capacity; infinite capacity; linear programs; lower bound; manufacturing systems; multinomials; queueing network throughput; upper bound; Capacity planning; Communication networks; Computational complexity; Ear; H infinity control; History; Intelligent networks; Queueing analysis; Steady-state; Throughput;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 1996., Proceedings of the 35th IEEE Conference on
Conference_Location :
Kobe
ISSN :
0191-2216
Print_ISBN :
0-7803-3590-2
Type :
conf
DOI :
10.1109/CDC.1996.574479
Filename :
574479
Link To Document :
بازگشت