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
[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.
[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.
[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.