Knowledge Base & Community Wiki
Queuing Theory – Tutorial I
Introduction : Queuing theory provides us tools to deal with problems which involve queuing or waiting. Typical examples might be:
- Banks or Supermarkets where customers wait to be serviced
- Web applications where users submit a query and are wait for a response
- Public transport where users wait in lines for the trains or buses to arrive
As we all agree queues are a common every-day experience. Queues form because resources on any given system are limited. In fact it makes economic sense to have queue built into a system. Queues help manage the traffic into and out of the system while optimizing how the system resources are allocated to user requests.
For example how many supermarket use till and queues in front of them to manage customer who need to be services. Have a think and work out how many customer tills you would need at your local supermarket to avoid queuing at peak times and if was feasible to maintain those tills throughout the year? How many buses or trains would be needed if queues were to be avoided/eliminated across all stations and bus depots?
In designing queuing systems we need to aim for a balance between service to customers (short queues implying many servers) and economic considerations (not too many servers). It’s not always possible to build and design queuing systems to deliver zero wait times. Queuing theory is the science of working out the appropriate balance between wait times and cost of the wait times for a particular service. All queuing systems can be broken down into individual sub-systems consisting of entities queuing for some activity:
Typically we can talk of the above system as dealing with customers queuing for service. To analyze this system using Queuing Theory you would need information relating to:
- Arrival Processes
- Service Center
- Queue Characteristics
- Probability of Outcomes
If you are interested in learning more about Queuing Theory we would recommend you visit the following link on the VisualizeIT Community Wiki & Knowledgebase. The VisualizeIT Community Wiki and Knowledge Base has a few interesting articles providing an introduction on the subject while also delving into the Queuing Notation used for purposes of representing different types of Queuing systems.
Types Of Models : There are various ways we could classify systems i.e. open or closed, stable or unstable, etc., but for purposes of this conversation we’ll stick to classification between CPU based systems or IO based systems. CPU based systems are systems which is defined by the following characteristic –
- Single or multiple Service Counters or CPU’s
- Single Queue for the entire system
IO based systems are defined by the following characteristic –
- Single of multiple Service Counters of IO Devices
- Single Queue per device
Your choice of a CPU or IO model completely changes the Queuing Characteristics of the system. So be careful and select the appropriate type of system.
Please note for IO model’s CPU = 1 irrespective of value entered. This assumes that you are modelling for a single IO device.
Let’s Look At An Example : Let’s review the results for the Queuing Theory model using the above inputs.
Let’s look at an example to understand how Queuing Theory can be applied to a system and how one might use Queuing Theory to understand the behavior of a system.
- Processors or Number of CPU’s (M) = 8
- Service Time (S) in Seconds = 0.4
- Arrival Rate (Lamda or λ) = 3
Please note that Input is required for all 3 of the inputs i.e. Arrival Rate (λ) , Number of CPU’s (M) and Service Time S(secs).
Interpreting Results : The resulting plots for this model are:
- Arrival Rate (λ) v/s Queue Time (Qt)
- Arrival Rate (λ) v/s Utilization (Q)
- Arrival Rate (λ) v/s Queue Length (Ql)
- Arrival Rate (λ) v/s Response Time (R)
- Arrival Rate (λ) v/s Probability Of Waiting (PoW)
- Arrival Rate (λ) v/s Probability Of Zero Waiting (PoZW)
- Arrival Rate (λ) v/s Queue Time Standard Deviation (QtStdev)
- Arrival Rate (λ) v/s Queue Length Standard Deviation (QlStdev)
- Utilization (U) v/s Queue Length (Ql)
The model computes the behavior of the system for an assumed gradual increase in Throughput (X). These resulting values are then plot on the graphs presented to you.
The resulting graphs very clearly tells us that as the number of arrivals into the system i.e. Arrival Rate (λ) increases the system Utilization tends to increase. With increase in system Utilization comes a direct increase in Queue Length and associated Wait Times. Eventually we get to a point where the system enters the Zone of Non Linear Performance (ZNLP) where the following happes –
- Request Queues start to build up
- Response Times start increasing
- Wait times for each of the requests starts increasing
- Which again leads to an increase in System Utilization
In any sphere of life when dealing with systems i.e. a bank with tellers as processors and customers lining up for services or a fast food store with counters as processors and customers lining up for service, you avoid getting into the Zone of Non Linear Performance. Technically speaking the Zone of Non Linear Performance (ZNLP) is typically the entire region past 75% utilization. You’ll note from the graphs below that once a system has entered the Zone of Non Linear Performance the “Request Queues” begin to increase in size and the Transaction Response times increase.
Analytical Modelling Solution: VisualizeIT offers access to a bunch of Analytical Models, Statistical Models and Simulation Models. Access to all the Analytical (Mathematical) models is free. We recommend you try out the Queuing Theory models at VisualizeIT and drop us a note with your suggestions, input and comments.
Conclusion : On any system you want to avoid getting into the Zone Of Non Linear Performance (ZNLP) i.e. > 75% Utilization. This applies not just to IT (Information Technology) systems but generally systems across the board i.e. a bank with tellers as processors and customers lining up for services or a fast food store with counters as processors and customers lining up for service. Use Queuing Theory to understand to translate User Concurrency into detailed system performance metrics and expected End User Performance.
Queuing Theory models are the comprehensive in terms of coverage (output performance metrics) and most importantly the most accurate of all the analytical models in terms of visualization of system performance. Queuing Theory also provides you a view of the Probability of the outcomes which isn’t available on any of the other analytical models. Use Queuing Theory to validate your design decisions, validate your Non Functional Requirements and confirm if the architectural principles you are applying is going to help you deliver the scalability and performance you desire.