|
|
|
|
|
|
|
6.6.2 Designing a M/M/1 Buffer Given a Mean Queue Size |
|
|
|
|
|
|
|
|
In chapter 4, we discussed two bounds on a queue (Q) exceeding a fixed buffer size (BF). |
|
|
|
|
|
|
|
|
For open queueing systems with a single server, we can introduce a third bound based on the M/M/1 model. Since the binomial request rate and the constant service rate have smaller variances than M/M/1, this bound should be safe for many memory and I/O design situations (i.e., so long as c2 < 1). Here: |
|
|
|
 |
|
|
|
|
Prob (0 items in server) = (1 - r). |
|
|
|
|
|
|
|
|
Now, intuitively, we compute the probability of exactly one item in the queue by computing the probability of an item arriving given an empty queue; i.e., |
|
|
|
|
|
|
|
|
Prob (exactly 1 item in queue or server) = r(1 - r). |
|
|
|
|
|
|
|
|
Again (intuitively) extending this, we get: |
|
|
|
|
|
|
|
|
Prob (exactly k items in queue or server) = (1 - r)rk. |
|
|
|
|
|
|
|
|
Now we can compute the probability that there are k or fewer items in the queue or server: |
|
|
|
|
|
|
|
|
This can be rewritten as: |
|
|
|
|
|
|
|
|
(1 - r)(1 + r + + rk), |
|
|
|
|
|
|
|
|
1 - rk+1, |
|
|
|
|
|
|
|
|
so that the probability that there are more than k items in the queue or servers is: |
|
|
|
|
|
|
|
|
Prob (> k items in queue awaiting service) = rk+1. |
|
|
|
|
|
|
|
|
Finally, since a buffer of size BF represents BF + 1 = k items in the queue (BF) or in the server: |
|
|
|
|
|
|
|
|
Prob (buffer of size BF overflows) = rBF+2. |
|
|
|
|
|
|
|
|
Prob (Q > BF items awaiting service) = rBF+2. |
|
|
|
|
|
|
|
|
Our Chebyshev bound (section 4.4.4) used the concept of ''buffer full or overflowed" as the point of system slowdown. This corresponds to: |
|
|
|
|
|
|
|
|
Prob (Q ³ BF) = rBF+1. |
|
|
|
|
|
