Acquisition of Stability in Queueing Networks – A Survey
By
Rana Sohail Saleem
MSCS (Networking), MIT, Virtual University of Pakistan
The paper is organized into sections. In section II, QN basics are described. Section III deals with scheduling policies and performance parameters. In section IV, stability and its related challenges faced by QN are highlighted along with a proposed solution. In section V, the discussion will be concluded.
4) Multiple Class Multiple Chain: This is a QN wherein multiple chains there is a number of classes as in [10]. Figure 5 shows the concept where Chain 1 is an OQN which is formed by classes 1 and 3 and chain 2 is CQN which is formed by class 2 as illustrated below:-
Abstract— Today is the era of high-speed networking where everyone wanted to be connected immediately without any delay. The immediate connection is not possible because of the increased number of customers trying to be connected at once. Resultantly a waiting situation is created which is resolved by making a queue where everybody gets the turn. The theory of queueing is very helpful in this regard where the model is constructed and bounded by prescribed scheduling policies. These policies are made keeping in view the network environment. The network is connected through a single or multiple queues upon which everybody has to be dependent. The queueing networks (QN) are stable till the time not overcrowded, but once overloaded the stability might be outclassed. The stability of the QN is related to the finite number of customers and the policies of their scheduling. There are a number of ways through which scheduling could be done to acquire stability in QN.
In this paper, the scheduling techniques, a number of challenges, and reasons for un-stability are discussed. Furthermore, remedial measures will be suggested to overcome the highlighted issues.
Keywords— Queueing Networks, stability, customers, scheduling policies
I. INTRODUCTION
The concept of queueing network is based upon the queueing theory. The theory is about a study that is mathematical in nature and deals with the waiting queues. A model is constructed which calculates the length of a queue and waiting time of each component in it. The model also follows a prescribed schedule through the components or customers are getting in and out of the queue. The scheduling is based on certain factors or policies which are dependent upon time, priority, or nature of the job of the waiting customers. At times queues follow the policies like First Come First Served (FCFS) as in [1] or First in First out (FIFO) as in [2], Last come First Served (LCFS) or Last in First out (LIFO), Shortest Job First as in [3], Processor Sharing (PS), Infinite Serves (IS), etc.
When the queues are connected in a network where customers are getting service at one place or node and moving to another node then such a system is known as queueing network. These networks are stable till the time there is a traffic load within a given parameter but once any of the parameters is overruled then the system will be unstable. This paper is organized to highlight the fundamentals of QN and stability with challenges in general and techniques of scheduling and acquiring of stability in particular. The available solutions will also be mentioned and the best among will be declared.The paper is organized into sections. In section II, QN basics are described. Section III deals with scheduling policies and performance parameters. In section IV, stability and its related challenges faced by QN are highlighted along with a proposed solution. In section V, the discussion will be concluded.
II. BASICS OF QUEUEING NETWORKS
The network which deals with multiple queues is handled by a model known as Queueing Network Model (QNM) and it belongs to the Jackson Networks. There are a number of service stations that are inter-connected through the directed paths and the customers move around. The customers also are known as jobs get service at one station, move ahead, line up in another queue for another service from another station. These service stations hold a number of services required by the customers as in [4]. Figure 1 shows the QNM as under:-
A. Types of QN
There are three categories of QN which can be classified as under:-
1) Closed Queueing Network (CQN): In this sort of QN there is a close circuit in which no arrival or departure is possible. The population of customers in the network is constant and keeps on circulating as in [5]. The customers may visit any queue twice as per requirement. CQN models are good for analyzing those networks which deal with flow controls of windows and scheduling of CPU jobs as in [6]. Figure 2 depicts the CQN in detail as follows:-
2) Open Queueing Network (OQN): In this sort of QN the customers arrive in the network from an external source and visit the number of queues, may repeat some queues as well, and depart the network after getting desired information. The customers’ numbers are not constant but a number of arrivals are always equal to the number of departures. There can be a described pattern of route following by the customers or maybe in an acyclic fashion. OQN models are good for packet switching (PS) and circuit switching (CS) data networks analysis as in [6]. Figure 3 depicts the OQN in detail as follows:-
3) Semi-open Queueing Network (SQN): This sort of QN holds the properties of both CQN and OQN. The OQN keep all the function less the customers' numbers are limited to finite jobs. In case of reaching the limit, the arrivals from external resources will be blocked, and once the job leaves the network the blocking of new arrivals will be over. So once the network is blocked then it behaves like CQN otherwise OQN as in [7].
B. Types of Customers
Although all customer is taken as alike but according to their categorization, they seem different from each other. The difference is measured in terms of the required service timing by them and the probability of their routing in the network as in [8]. Following are types of customers:-
1) Chains: Customers having the same nature of jobs are grouped in a chain where the jobs are categorized permanently. Once this categorization of the job is done then one job of one chain can’t move or switch to the other chain. This is customers’ permanent categorization where a customer has to stay in a chain whole the time till departure.
2) Classes: The jobs of customers go through different phases like loading of a program and then its execution are two different phases. These phases are classified as classes and there may be many classes. The main fact is that these classes are within a specified chain. This is a customers’ temporary classification where a customer may switch within classes but in the same chain.
3) Multiple Class Single Chain: This is a QN wherein a single chain there is a number of classes as in [9]. Figure 4 shows the concept where Chain 1 is an OQN which is formed by one class and chain 2 is CQN which is formed by one class as illustrated below:-
4) Multiple Class Multiple Chain: This is a QN wherein multiple chains there is a number of classes as in [10]. Figure 5 shows the concept where Chain 1 is an OQN which is formed by classes 1 and 3 and chain 2 is CQN which is formed by class 2 as illustrated below:-
III. POLICIES AND PERFORMANCE
In this section two important aspect are highlighted; the scheduling policies of QNs and certainly adopted parameters through which better performance is achieved. Following are the details:-
A. Scheduling Policies of QNs
There are a number of different policies that are adopted for QNs. Their details are under:-
1) First in First out (FIFO): It is also known as First Come First Served (FCFS). A buffer or queue is organized where the customers keep on coming and line up in a waiting lane. They are served according to their turn and after getting the required service from the server they keep on leaving the queue. The one who comes first is served first and the second one next and so on as in [11].
2) Last in First out (LIFO): A stack is organized where the customers keep on coming and stacking up. There are two operations namely Push and Pop through which the customers keep on getting in and out of the stack. Push adds the customers in the stack whereas pop removes them. The one who comes last is served first and the second last one next and so on as in [12].
3) Shortest Job First (SJF): It is a scheduling policy where that customer is selected whose job has the smallest time of execution. It is quite helpful that smaller time-consuming customers are moving frequently. But at times customers with a longer time may keep on waiting for their turn and could not get a turn because less time requiring customers to keep on coming. It creates process starvation. It is only useful where the aging technique is used for estimating the time of the job’s execution as in [13].
4) Processor Sharing (PS): It is a policy where the services are available to all the customers simultaneously. All the jobs are getting an equal share from the servers. In such a case there is no customer who has to wait for the turn, therefore, there are no queues as in [14].
5) Infinite Server (IS): In this scheduling policy when the customers enter the network they receive the serves right from the outset at rate 1. So there is a number of servers in the network which are unoccupied and their services are available all the time as in [15].
6) Random Selection for Service (RSS): In this, the customers are selected randomly without taking into care of their arrival or waiting time, etc.
B. QN Performance Parameters
Once the performance of QN is to be judged then there is a need to check out certain parameters of QN. The parameters are related to the arrivals or inputs and departures or outputs of the QN. Like inputs include the number of stations, some scheduling discipline with service time distribution, population (CQN) or inter-arrival time (OQN) etc. Whereas outputs include the length of queues, response time, throughput, utilization, etc. as in [16]. Irrespective of input or out parameters, these are highlighted as under:-
- Average service time spent at a station for a customer.
- External arrival time in OQN only at which customers are arriving at the network from an external source.
- Routing probability of customers from one station to another.
- Throughput or completed services by the stations.
- Average the response time taken by customers at any station.
- Average waiting time taken by customers at any station.
- Average queue length of any station holding customers for waiting or serving.
- Average the waiting line length of customers waiting to be served excluding those who are under processing service.
- Utilization of any station in terms of time.
- Queue length distribution among customers at stations.
IV. STABILITY AND THEIR RELATED ISSUES
The QN is expected to be stable all the time which is not possible due to certain factors that are elaborated in the subsequent paragraphs. There are a number of related issues faced by the QN as well which are also highlighted within the stability scenario.
A. Stability of QN
The stability of QN depends upon certain stationary distribution factors like disciplines, non-exponential inter-arrival and service times. The invariant distribution is determined explicitly to establish QN stability as in [17]. For single-class networks and single-server multi-class networks, the stability could be easily established through the routine conditions of traffic where intensity is expected less than one at all stations. But it is not true for multi-server multi-class QNs. This is proven by number of counter examples as in [18], [19], [20], [21], [22] & [23].
The fact has been established by these counter examples that traffic intensity may not be the only network factor responsible for affecting the stability but there are others as well. These are as under:-
· The policy of scheduling
· The network routing
· The processes of routing
· At one server classes have different service rates
· The arrivals are dependent
Furthermore, another fact is established by these counter examples that resources are not utilized at their maximum. There are three conclusions drawn through this whole operation which are as follows:-
· By increasing the capacity of service would not stabilize the network because of the stability of global region is not in continuation as explained in [18], [24].
· Utilization does not have any concern with the stability of QN. There may be a bottleneck server due to the low utilization.
· If customers are prioritized through scheduling then there will be a situation where few customers get service earlier than others. There will be few customers who keep on waiting in the queue for a longer period.
B. Assessment of Stability
The stability of QN can be determined through the following way as expounded in [25]:-
1) Sub-Networks: Stability of network is based on the stability of all the stations in that network. Same way if a customer at a station is unstable then the station will be unstable and so the network will be as well.
2) Little’s Law: The algorithm which is checking the stability of a QN is based on the time spent by the customers in the network. It also based on the number of customers present at one time in the network. Little law is applied either at the whole model of network or maybe to some part of it.
3) Linear Growth: Through this, the customers’ growth rate in linear fashion can be determined. The results give out whether the network is stable or unstable.
C. Acquisition of Stability
A detailed working has been done to acquire a stability formula in the field of QNs. These are highlighted in subsequent paragraphs in this sub-section.
Once the stability assessment is over with then it can be achieved by removing the hurdles. The performance of a QN can be gauged by two metrics; the throughput and the stability of the network. Both are inter-related to each other. If throughput is enhanced then the stability of the network is reduced and vice versa. Maximization of throughput is not possible in an unstable environment of QN, therefore, throughput could be compromised in order to attain stability as in [26].
Stability is also related to the effective rate of arrivals (internals and externals) of customers and the intensity of traffic. There are two types; path-wise stability and global or system stability. Path-wise stability is related to internal and external arrivals and this is considered weaker than system stability. However path-wise stability has to be achieved for global stability as in [27].
There is also another concept that exact conditions can’t be determined by which the stability of a QNs under prescribed scheduling policies can be judged, checked, and resolved. So the concept evolved around the un-decidability of QN algorithmically. This is true for both the infinite and finite sizes of the buffers as in [28].
Another approach is considered in [29] where parallel server systems are in focus. To acquire the stability of a system the nominal condition of traffic is mandatory under the condition of generalized distribution of service and inter-arrival timing of customers.
If the queue’s length is time bounded with initial conditions then it is stable otherwise not. The stability of QNs is dependent upon the processes’ distributions stochastically as in [30].
In one of the considerations, it was assumed that the queue is having an infinite space. But the system would be stable if there is no increase in the queues. This is possible with some controlled policies. The policy of stabilizing the system is concerned with the rate of customers’ arrival the service rate provided to them. It also includes the policy of maximum throughput where a method of link activation is provided by the queueing model to stabilize the network as in [35].
In short, a lot of research work has been carried out to establish that queueing network stability can be achieved. All such experiments and their results are based on three networks namely Jackson, Generalized Jackson, and Kelly networks as in [31]. These networks less generalized are stable in an environment where invariant distribution is determined explicitly as in [32] & [33]. Whereas the Generalized Jackson network’s stability is based on the proof of Harris recurrence (positive) of the Markov process as in [34]. A Lyapunov function is constructed where Poisson arrivals with exponential service times are used to establish the stability of queueing networks which are multi-class as in [17]. D. Proposed Solution
The research on the topic has been carried out by a number of researchers in the last three decades. Only a few worthwhile papers from 1992 till 2014 are referred here which have done remarkable research in the field of QNs stability as in [15], [35], [36], [37], [38], [39], [40], [41] & [42]. This paper has surveyed and highlighted the previous studies and suggests the following solution:-
· By increasing the capacity of queues, more customers can be entertained.
· By increasing the number of queues more customers can be entertained in less time frame.
· By adding more servers in the service centers less time will be spent in executing more customers.
· An algorithm can be devised which could speed up the service time at service centers.
Nexus to above the proposals could be used in isolation or in combination as well as the capacity of buffers and the number of queues can be increased for clearing more jobs on a reduced scale of time. A faster algorithm with more number of servers in service centers is also a beneficial approach.
I. Conclusion
This paper has been organized in order to highlight and survey the basic concepts of QNs along with existing scheduling policies and parameters to achieve better performance. It also mentions the factors required to maintain the stability of QNs and reasons for instability. Actually, the stability of the network depends upon load over the network. Whenever prescribed capacity of a buffer is full then arriving customers are piled up at queues and the system becomes unstable. Different scheduling policies or disciplines are tested and adopted to cater for such eventuality and it is observed that still system derail from the stability factor very often. Although a lot has been improved keeping in view where we stand in the 1990s and now in present-day but room for improvement is still there.
In a nutshell, this paper encompasses QNs in general and their stability, instability factors along with a proposed solution in particular. References
[1] U. Schwiegelshohn and R. Yahyapout, “Analysis of First-Come-First-Serve Parallel Job Scheduling”, SODA, Zwsisk, 1998, pp. 1-10.
[2] A.G. Fraser and Bernardsville, “First-in, First-out (FIFO) Memory Configuration for Queue Storage”, USA, 1985, pp. 1-7.
[3] S. Lupetti and D. Zagorodnov, “Data Popularity and Shortest-Job-First Scheduling of Network Transfers”, Tromso Uni. Norway, 2006, pp. 1-7.
[4] P.J. Denning and J.P. Buzen, “The Operational Analysis of Queueing Network Models”, CSUR, vol. 10, no. 3, Sep. 1978, Purdue Uni. USA, pp. 1-37.
[5] S. Balsamo et. al. “Analysis of Queueing Networks with Blocking”, Springer, Stanford Uni. USA, 2001, pp. 8-9.
[6] N.C. Hock and S.B. Hee, “Closed Queueing Networks”, 2nd ed. Singapore, 2008, pp. 169-214.
[7] H. Chen and D.D. Yao, “Fundamentals of Queueing Networks- Performance, Asymptotics, and Optimization”, Springer, New York, 2001, pp 21-23.
[8] W. Whitt, “The Queueing Network Analyzer”, TBSTJ, vol. 62, no. 9, Nov. 1983, USA, pp. 1-37.
[9] S. Ramesh and H.G. Perros, “A Multi-Layer Client-Server Queueing Network Model with Synchronous and Asynchronous Messages”, North Carolina Uni. USA, 1998, pp. 1-13.
[10] F. Baskett et. al. “Open, Closed, and Mixed Networks of Queues with Different Classes of Customers”, Taxas Uni. USA, 1975, pp. 1-13.
[11] “FIFO (computing and electronics)”, [online]. Available: https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics).
[12] “FIFO and LIFO Accounting”, [online]. Available: https://en.wikipedia.org/wiki/FIFO_and_LIFO_accounting.
[13] “Shortest Job Next”, [online]. Available: https://en.wikipedia.org/wiki/Shortest_job_next.
[14] “Processor Sharing”, [online]. Available: https://en.wikipedia.org/wiki/Processor_sharing.
[15] M. Bramson, “Stability of Queueing Networks”, Springer, Minnesota Uni. USA, 2008, pp. 24.
[16] E.D. Lazowska et. al. “Quantitative System Performance”, chap. 4, pub. Prentice-Hall, 1984, pp. 57- 68.
[17] P.R. Kumar and S.P. Meyn, “Stability of Queueing Networks and Scheduling Policies”, IEEE, TOAC, vol. 40, no. 2nd Feb. 1995, USA, pp. 251-260.
[18] P.R. Kumar and T.I. Seidman, “Dynamic Instabilities and Stabilization
Methods in Distributed Real-Time Scheduling of Manufacturing Systems”, IEEE TOAC, vol. 35, Mar. 1990, USA, pp. 289-298.
Methods in Distributed Real-Time Scheduling of Manufacturing Systems”, IEEE TOAC, vol. 35, Mar. 1990, USA, pp. 289-298.
[19] A.N. Rybko and A.L. Stolyar, “Ergodicity Stochastic Processes Describing Operations of Open Queueing Networks”, PIT, vol. 28, no. 3, 1992, pp. 199–220.
[20] T.I. Seidman, “First Come, First Served can be Unstable!” IEEE TOAC, vol. 39, no. 10, 1994, USA, pp. 2166–2171.
[21] M. Bramson, “Instability of FIFO Queueing Networks”, TAAP, vol 4, no. 2, 1994, USA, pp. 414–431.
[22] M. Bramson, “Instability of FIFO Queueing Networks with Quick Service Times”, TAAP, vol. 4, no. 3, 1994, pp. 693–718.
[23] J. Banks and J.G. Dai, “Simulation Studies of Multiclass Queueing Networks”, IIE Trans. Vol. 29, 1997, pp. 213–219.
[24] A. Sharifnia, “Instability of the Join-the-Shortest Queue and FCFS Policies in Queueing Systems and their Stabilization”, INFORMS, vol. 45, no. 2, 1997, USA, pp. 309–314.
[25] J.R. Wieland et. al. “Queueing Network Stability: Simulation-Based Checking”, proc. of winter sim. Conf. Purdue Uni. USA, 2003, pp. 520-527.
[26] P. Chaporkar and S. Sarka, “Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems”, IEEE TOAC, vol. 53, no. 8, Sept. 2008, Pennsylvania Uni. USA, pp. 1913-1931.
[27] J.J. Hasenbein, “Stability, Capacity, and Scheduling of Multiclass Queueing Networks”, thesis, Georgia, 1998, chap. 3, pp. 21-27.
[28] D. Gamarnik and D. Katz, “On Deciding Stability of Multiclass Queueing Networks under Buffer Priority Scheduling”, TAAP, vol. 19, no. 5, 2009, USA, pp. 2008–2037
[29] G. Baharian and T. Tezcan, “Stability Analysis of Parallel Server Systems under Longest Queue First”, Springer, USA, 2011, pp. 258.
[30] D. Armbruster et. al. “On the Stability of Queueing Networks and Fluid Models”, Eindhoven Uni. USA, 2010, pp. 1-8.
[31] H. Chen, “Fluid Approximations and Stability of Multiclass Queueing Networks: Work-Conserving Disciplines”, TAAP, vol. 5, no. 3, 1995, USA, pp. 637-665.
[32] J.R. Jackson, “Jobshop-like Queueing Systems”, JIMIMSORS, Uni. of California, 1963, USA, pp. 1-31.
[33] F.P. Kelly and J. Walrand, “Networks of Quasi-Reversible Nodes”, Springer, 1982, pp. 1-15.
[34] S.P. Meyn and D. Down, “Stability of Generalized Jackson Networks”, TAAP, vol. 4, no. 1, Uni. of Illinois, USA, 1994, pp. 124-148.
[35] L. Tassiulas and A. Ephremides, “Stability Properties of Constrained Queueing Systems and Scheduling Polices for Maximum Throughput in Multi-hop Radio Networks”, IEEE, TOAC, vol. 37, no. 2, Dec. 1992, Maryland Uni., USA, pp. 1-14.
[36] C.S. Chang, “Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks”, IEEE, TOAC, vol. 39, 1994, USA, pp. 913-931.
[37] J. Dai and S. Meyn, “Stability and Convergence of Moments for Multiclass Queueing Networks via Fluid Limit Models”, IEEE, TOAC, vol. 40, 1995, USA, pp. 1889-1904.
[38] A.L. Stoylar, “Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm”, Springer, Queueing Syst. vol. 50, 2005, USA, pp. 401-457.
[39] J.G. Dai et. al. “Stability of Join the Shortest Queue Network”, Springer, Queueing Syst. vol. 57, USA, 2007, pp. 129-145.
[40] M. Bramson, “Stability of Join the Shortest Queue Network”, TAAP, vol. 21, no. 4, Uni. of Minnesota, USA, 2010, pp. 1568-1625.
[41] P. Wang and I.F. Akyildiz, “Network Stability of Cognitive Radio Networks in the Presence of Heavy Tailed Traffic”, Georgia, 2012, pp. 1-9.
[42] S.T. Maguluri et. al. “The Stability of Longest-Queue-First Scheduling with Variable Packet Sizes”, IEEE, TOAC, Uni. of Illinois, USA, 2014, pp. 1-8.
0 comments:
Post a Comment