|
|
|
|
|
|
|
The essential issue in determining BF is that for us, BF is the value at which the system slows down. If we have a buffer of size 3 but the system does not slow down unless there are 4 items, then we are looking for the probability that Q > 3 or Q ³ 4, which in either case is r5. |
|
|
|
|
|
|
|
|
In our modeling assumptions for using Chebyshev's bound, we used the mean arrival rate as an estimate of the queue size. Assuming unit departures (m = 1), this is a safe estimate so long as r < 0.5 (i.e., so long as l < 0.5). |
|
|
|
|
|
|
|
|
For most cases, we will find that the M/M/1 buffer "full or overflowed" estimate is superior to the Chebyshev bound. |
|
|
|
|
|
|
|
|
For closed queues, we replace r with ra |
|
|
|
|
|
|
|
|
EXAMPLE 6.4 BUFFER OVERFLOW 1 |
|
|
|
|
|
|
|
|
Suppose we wish to ensure that the probability of buffer overflow (Q > BF) is less than 7% for queue occupancy of r = 0.5: |
|
|
|
 |
|
|
|
|
Prob (Q > BF = 2) = (.5)4 = 0.0625. |
|
|
|
|
|
|
|
|
Note that the above bound is derived for a buffer plus a server, so that BF = 0 means that there is still a server in the system. If an item must enter, say, a pipelined buffer stage before it can proceed, one storage element is regarded as the server, while additional storage elements compose the buffer. |
|
|
|
|
|
|
|
|
Using this bound in memory systems is limited by the single server requirement; after all, the case of m = 1 memory module is uninteresting! |
|
|
|
|
|
|
|
|
If, indeed, we had a separate buffer for each module, then we could determine the probability of overflow in any module as: |
|
|
|
|
|
|
|
|
|
Prob (Q > BF in any of m buffers) |
|
|
|
| | | | | |
|
|
|
|
|
|
EXAMPLE 6.5 BUFFER OVERFLOW 2 |
|
|
|
|
|
|
|
|
Let us consider the preceding example for m = 2. Again r = 0.5 and we wish to ensure Prob (Q > BF) ³ 0.07. Instead of BF = 2, let us try BF = 3 (buffer of three entries for each module): |
|
|
|
|
|
|
|
|
rBF+2 = r5 = (0.5)5 = 0.03125 |
|
|
|
|
|
|
|
|
Prob (Q > BF in either module) = 1 - [1 r5]2 = 0.062. |
|
|
|
|
|
|
|
|
The obvious alternative is to pool the buffers into a larger buffer, BFP, that holds requests for all modules, so that: |
|
|
|
|
|
|
|
|
BFP = m BF. |
|
|
|
|
|