1## Copyright (C) 2008, 2009, 2010, 2011, 2012, 2016, 2018 Moreno Marzolla 2## 3## This file is part of the queueing toolbox. 4## 5## The queueing toolbox is free software: you can redistribute it and/or 6## modify it under the terms of the GNU General Public License as 7## published by the Free Software Foundation, either version 3 of the 8## License, or (at your option) any later version. 9## 10## The queueing toolbox is distributed in the hope that it will be 11## useful, but WITHOUT ANY WARRANTY; without even the implied warranty 12## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13## General Public License for more details. 14## 15## You should have received a copy of the GNU General Public License 16## along with the queueing toolbox. If not, see <http://www.gnu.org/licenses/>. 17 18## -*- texinfo -*- 19## 20## @deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{D} ) 21## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V} ) 22## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V}, @var{m} ) 23## @deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z} ) 24## 25## @cindex bounds, PB 26## @cindex PB bounds 27## @cindex closed network, single class 28## 29## Compute PB Bounds (C. H. Hsieh and S. Lam, 1987) for single-class, 30## closed networks with @math{K} service centers. 31## 32## @strong{INPUTS} 33## 34## @table @code 35## 36## @item @var{} 37## number of requests in the system (scalar, @code{@var{N} > 0}). 38## 39## @item @var{D}(k) 40## service demand of service center @math{k} (@code{@var{D}(k) @geq{} 0}). 41## 42## @item @var{S}(k) 43## mean service time at center @math{k} (@code{@var{S}(k) @geq{} 0}). 44## 45## @item @var{V}(k) 46## visit ratio to center @math{k} (@code{@var{V}(k) @geq{} 0}). 47## 48## @item @var{m}(k) 49## number of servers at center @math{k}. This function only supports 50## @math{M/M/1} queues, therefore @var{m} must be 51## @code{ones(size(S))}. 52## 53## @item @var{Z} 54## external delay (think time, @code{@var{Z} @geq{} 0}). Default 0. 55## 56## @end table 57## 58## @strong{OUTPUTS} 59## 60## @table @code 61## 62## @item @var{Xl} 63## @itemx @var{Xu} 64## Lower and upper bounds on the system throughput. 65## 66## @item @var{Rl} 67## @itemx @var{Ru} 68## Lower and upper bounds on the system response time. 69## 70## @end table 71## 72## @strong{REFERENCES} 73## 74## @itemize 75## @item 76## C. H. Hsieh and S. Lam, @cite{Two classes of performance bounds for 77## closed queueing networks}, Performance Evaluation, Vol. 7 Issue 1, 78## pp. 3--30, February 1987, DOI 79## @uref{http://dx.doi.org/10.1016/0166-5316(87)90054-X, 80## 10.1016/0166-5316(87)90054-X}. Also available as 81## @uref{ftp://ftp.cs.utexas.edu/pub/techreports/tr85-09.pdf, Technical 82## Report TR-85-09}, Department of Computer Science, University of Texas 83## at Austin, June 1985 84## @end itemize 85## 86## This function implements the non-iterative variant described in G. 87## Casale, R. R. Muntz, G. Serazzi, @cite{Geometric Bounds: a 88## Non-Iterative Analysis Technique for Closed Queueing Networks}, IEEE 89## Transactions on Computers, 57(6):780-794, June 2008. 90## 91## @seealso{qncsaba, qbcsbsb, qncsgb} 92## 93## @end deftypefn 94 95## Author: Moreno Marzolla <moreno.marzolla(at)unibo.it> 96## Web: http://www.moreno.marzolla.name/ 97 98function [X_lower X_upper R_lower R_upper] = qncspb( varargin ) 99 if ( nargin < 2 || nargin > 5 ) 100 print_usage(); 101 endif 102 103 [err N S V m Z] = qncschkparam( varargin{:} ); 104 isempty(err) || error(err); 105 106 ( N>0 ) || ... 107 error("N must be positive"); 108 all(m==1) || ... 109 error("qncspb only supports single server nodes"); 110 111 D = S .* V; 112 113 D_tot = sum(D); 114 X_max = 1/max(D); 115 X_min = 0; 116 X_lower = N/( Z + D_tot + ... 117 ( sum( D .^ N * (N-1-Z*X_min) ) / sum( D .^ (N-1) ) ) ); 118 X_upper = N/( Z + D_tot + ... 119 ( sum( D .^ 2 * (N-1-Z*X_max) ) / sum( D ) ) ); 120 X_upper = min( X_upper, X_max ); # cap X upper bound to 1/max(D) 121 R_lower = N/X_upper-Z; 122 R_upper = N/X_lower-Z; 123endfunction 124 125%!test 126%! fail( "qncspb( 1, [] )", "vector" ); 127%! fail( "qncspb( 1, [0 -1])", "nonnegative" ); 128%! fail( "qncspb( 0, [1 2] )", "positive" ); 129%! fail( "qncspb( -1, [1 2])", "nonnegative" ); 130%! fail( "qncspb( 1, [1 2], [1,1], [2, 2])", "single server" ); 131%! fail( "qncspb( 1, [1 2], [1,1], [1, 1], -1)", "nonnegative" ); 132 133%!# shared test function 134%!function test_pb( D, expected, Z=0 ) 135%! for i=1:rows(expected) 136%! N = expected(i,1); 137%! [X_lower X_upper] = qncspb(N,D,ones(size(D)),ones(size(D)),Z); 138%! X_exp_lower = expected(i,2); 139%! X_exp_upper = expected(i,3); 140%! assert( [N X_lower X_upper], [N X_exp_lower X_exp_upper], 1e-4 ) 141%! endfor 142 143%!test 144%! # table IV 145%! D = [ 0.1 0.1 0.09 0.08 ]; 146%! # N X_lower X_upper 147%! expected = [ 2 4.3174 4.3174; ... 148%! 5 6.6600 6.7297; ... 149%! 10 8.0219 8.2700; ... 150%! 20 8.8672 9.3387; ... 151%! 80 9.6736 10.000 ]; 152%! test_pb(D, expected); 153