On the Modeling and Analysis of Tandem Queues: independence assumption vs. No independence assumption
Computer Science and Engineering
University of South Florida
Tampa, FL 33620
I wish to study the effects of certain characteristics within a tandem queue using the independence assumption. After which, I will compare those results with the actual information from the system. In particular, I wish to analyze and then comment on the system delay and the mean queue length of the tandem queues. In addition, I wish to also briefly looked at the works of others implementing, or furthering the study of Kleinrock’s independence assumption within their own fields of expertise.
The independence assumption is defined here as:
“Each time a message is received at a node within the net, a new length v is chosen for this message from the following probability density function:
p( v ) = mu * exp( -( mu * v ) ).
It is clear that this assumption does not correspond to the actual situation in any practical communication net. Nevertheless, its mathematical consequences result in a model, which accurately describes the behavior of the message delay in many real nets[ 1 ].” This simplification of queueing systems has made analysis of such systems much more tractable than without it[ 1 ].
In this paper I will examine the implementation of this independence assumption to tandem queues. I will run a simulation of a tandem queue with two facilities( please see figure 1 ) and compare its results with Kleinrock’s independence assumption. After which, I will simulate a tandem queue with three facilities( please see figure 2. ) and continue the same analysis of it as of the system with two facilities. In both systems I will assume an M|M|1 model. An M|M|1 model assumes a poisson arrival rate and departure rate from each facility[ 1 ].
The remainder of this paper is organized as follows. Section 2 will briefly overview work that dealt with the independence assumption. Section 3 describes the strengths and weaknesses of the independent assumption. Section 4 describes the methods that are used to test the system delay and queue lengths of the tandem queues.
Section 5 will analyze and critique the affects of the tandem queues with and without the use of the independence assumption. Section 6 will present the conclusions of the analysis from Section 5.
There have been many comparisons to, implementations of, and ideas built upon Kleinrock’s independence assumption. I will briefly mention a few here.
In the field of signal processing, Butterweck states that the independence assumption is not needed anymore to create a weight-error correlation matrix[ 4 ]. The gentleman continues by saying the independence assumption is only useful for small step sizes in determining a weight-error correlation matrix[ 4 ]. However, a white additive output noise assumption will generate the same weight-error correlation matrix for small step sizes[ 4 ]. In addition, the independence assumption does poorly with the analysis of successive inputs of high coherence[ 4 ]. I believe this is similar to the idea of a network exhibiting burstiness. The use of the white additive output noise fairs better through out the system than would the use of the independence assumption[ 4 ]. He continues with other points in the paper of why the use of the independence assumption is a tool, not needed in a fully adapted LMS-type transversal filter[ 4 ].
Cantor, Ephremides, and Horton have furthered the study of the independence assumption by considering the principle of relative-entropy[ 2 ]. In the relative-entropy approach to queueing, the maximum entropy distribution is used to more realistically determine the state of “ ’real world’ systems”[ 2 ]. They believe that the arrivals and departures within “ ‘real world’ systems” do not behave exponentially[ 2 ]. Therefore, the application of the independence assumption to such systems gives the authors some reasons for concern and reasons to explore other methods to analyze non-exponential systems[ 2 ].
Lastly, Cidon, Khamisy, and Sidi wish to analyze blocks of cells or messages rather than analyze individual cells[ 3 ]. This idea of blocks of cells is similar to that of ATM cells[ 3 ]. They have implemented a new approach to examine these type of systems and would like to compare their results with the results of implementing the independence assumption[ 3 ]. In particular they would like to examine delay and jitter within the queues[ 3 ].
3. Strengths and Weaknesses
The independence assumption has many strengths and weaknesses. Its strengths include making intractable problems tractable when confronted with systems depending on one another[ 1 ]. It also simplifies many assumptions of the network by forgoing many idiosyncrasies such as its topological structure and routing procedures[ 1 ].
Some of its weaknesses include its overestimating of the utilization of the actual system if the utilization is above a certain threshold[ 1, 3, 4 ]. Also, many “real world” systems do not exhibit exponential arrivals and departures, thus the independence assumption may be a poor model to implement[ 2 ].
This analysis is simply to reaffirm the effects of the independence assumption on a network, in particular, a tandem queue network. I would like to briefly go over the input, the models, and the procedures in order to ascertain my results.
The inputs include:
· over 8000 customers,
· an arrival rate( lambda ) equal to 0.08 customers per second,
· a simulation time of over 100,000 seconds,
· a poisson arrival & departure rates,
· and a FIFO principle.
The model includes:
· a M|M|1 tandem queue system consisting of 2 facilities, and
· a M|M|1 tandem queue system consisting of 3 facilities.
Also, within each of the two systems, I would like to model:
· the system delay vs. the utilization( rho1 and rho2 ) of each facility, and
· the queue length vs. the utilization( rho1 and rho2 ) of each facility.
The following procedures will be repeated twice, once while assuming independence and once not assuming independence. The procedures include:
· for the 2-tandem queue, I have varied rho1 and rho2 from 0.1 to 0.9 to obtain 81 data points.
· For the 3-tandem queue, I have varied rho1, rho2, rho3 from 0.1 to 0.9 to obtain 729 data points.
· With each iteration of the two nested loops( three nested loops for the 3-tandem queue ), calculations will be made of
· rho3( for the tandem queue of 3 facilities ),
· the mean delay at each facility, and
· the mean queue length at each facility.
The mean system delay is computed by summing up the mean delay in each facility. The mean queue length is computed by summing up the mean queue length and then dividing by the number of facilities in the system.
After the acquisition of the data, a plot of the utilization versus the mean system delay and a plot of the utilization versus the mean queue length will be graphed.
5. Proof( by experimental results )
5.1 2-Tandem Queue
5.1.1 Mean System Delay
Graph 5.1 shows the results of the mean system delay versus the utilization.
Graph 5.1( mean system delay vs. rho2 )
First off, an unexpected result is shown when rho1 and rho2 are at 80% utilization. Some fluctuation in choosing a number will occur when randomly pulling an exponential number. The probability of pulling a higher response time for the independence assumption than without independence assumption is low. However, with the less than infinite amount of customers traversing through the system, this occurrence is possible.
Now, one can see that the independence assumption is a good tool if the utilization of both facilities is low, say less than 40%( please see graph 5.2 ). If both rhos are at and below 40% utilization, than the difference between the independent assumption and without the independence assumption is less than 6%.
Graph 5.2( diff in mean system delay vs. rho2 )
Also, if the utilization of the first server is high( rho1 = 80% ), then the utilization of the second server( rho2 ) will be inconsequential. That is, the independence assumption will not model the system well after the first server.
As expected( except for the glitch at rho1 and rho2 equaling 80% ), the independence assumption has modeled the mean system delay fairly well with a utilization of both rhos below 40%.
5.1.2 Mean Queue Length
Graph 5.3 shows the results of the mean queue length versus the utilization of the two servers. The mean queue length is also shown with the independence assumption turned on and off.
Figure 5.3( mean queue length vs. rho2 )
The results are similar to those of the mean system delay. If both rho1 & rho2 are below 40% utilization then
The independence assumption maps well to the whole simulated mean queue length. Please see graph 5.4. One can also see if the first facility has a high utilization, than no matter what the utilization of the second facility is, the difference between the independence assumption and the simulated mean queue length will remain high. In this case, the difference is close to 15%( graph 5.4 ).
Figure 5.4( diff. in mean queue length vs. rho2 )
5.2 3-Tandem Queue
5.2.1 Mean Queue Length
I would like to see if by varying the first facility’s utilization, how that would affect the mean queue length of the next two facilities. The effect of the system delay is similar to that of the mean queue length. However, for space constraints, it is not discussed in detail. Graphs 5.5 and 5.6 show the results of the mean queue length of a 3-tandem queue( see figure 2 ). I have varied rho1 to be 80% in graph 5.5. In graph 5.6 rho1 is set to 10%.
Graph 5.5( rho1 = 0.8 )
As expected, in graph 5.5, the variation between the independence assumption turned on and the variation when turned off is rather high for rho2 at 40% and for rho2 at 10%. However, I am not sure how to interpret the results of rho2 set at 80% of the mean queue length.
In graph 5.6, the results( after setting rho1 to 10% now ), also came close to my expectations. That is, a facility having low variability will not effect the service of facilities in front of it. Again, I’m not sure how to
interpret the results of rho at 80%. The overall results are similar to that of graph 5.3.
Graph 5.6( rho1 = 0.1 )
6. Conclusions and Future Work
This paper took a look at a few tandem queues. I have looked at the effects on the queues with the independence assumption on and off. At the same time, I varied the utilization of various facilities to study the effects of the system delay and on their queue lengths.
The results from the experiment are as follows. With a high utilization in the parent facility, any successor will also exhibit a high utilization rate if the successors’ utilization is below 50%. If the parent facility experiences a low utilization, then the parent will have little effect on its successors’ utilization rate.
Future work can examine why a parent’s high utilization rate would substantially diminish a successor’s high utilization.
I would like to thank Dr. Ken Christensen, Hiroshi Fujinoki, Nan Zhang, and Zornitza Geneva of the University of South Florida for their helpful suggestions.
[ 1 ] Kleinrock, Leonard. Communication Nets. NewYork: Dover Publications, 1972 : pp. 50-56.
[ 2 ] Cantor, J., A. Ephremides, and D. Horton.”Information Theoretic Analysis for a general queueing system at Equilibrium with Application to Queues in Tandem.” ACTA Information. Vol.23( 1986 ): 657-678.
[ 3 ] Cidon, Israel, Asad Khamisy and Moshe Sidi. “Dispersed Messages in Discrete-Time Queues: Delay, Jitter and Threshold Crossing.” IEEE INFOCOM( 1994 ): 218-223.
[ 4 ] Butterweck, H.J., “The Independence Assumption: A Dispensable Tool in Adaptive Filter Theory.” Signal Processing. Vol.57, No.3( March 1997 ):305-310.