Printer Friendly

Performance analysis of an unreliable queuing system with buffer threshold control and a reserved channel/Nepatikimos eiliavimo sistemos su valdomu buferio slenksciu ir rezerviniu kanalu nasumo analize.

Introduction

In this article we propose an exact analysis of a queuing system with threshold control and a reserved transmission channel. Our main goal in this paper is to develop an efficient method for computing the steady state probabilities of a queuing system with threshold control, which will allow computation of system performance measures. Two types of the queuing system with a reliable and unreliable main transmission channel are analyzed. Analysis of the systems is based on Markov birth and death processes. Our proposed analytical models are used for analysis of processes in a queuing system which uses main and reserved channels and serves data packets arriving in Poisson flows. We proposed the buffer threshold control method to improve the data packet delay parameter. Much research efforts has been and remains devoted to improving the performance measures of data packet transmission networks [1]. A queuing system with batch Markovian arrival processes and several operation modes, which are controlled by means of threshold strategy, is investigated by Kim C.S. [2]. Asymptotic optimality of a threshold policy is applied for dynamic scheduling of a queuing system with two parallel servers in [4]. A dynamic control policy of threshold queuing and Markov chain analysis is employed in [5] by Larsen R.L.

Most research to date has focused on supporting quality of service (QoS) within a single network node, and analysis of such a queuing data network node is currently an active area of research.

Accurate modeling of the offered traffic and its transmission via an unreliable system with reservation and buffer threshold control is the first step in analysis of such system quality of service parameters [3,6]. QoS parameters in our models are expressed in the following parameters: data packet losses, channel utilization parameters, probabilities of channel and system failures, mean value of waiting time, average number of data packets in the buffer.

Unfortunately, most queuing problems are not available in analytic form. Therefore, we propose the simulation model of the G/G/2/(N)K system to evaluate the performance parameters of an unreliable system with buffer threshold control and a reserved channel.

Analytical model of an M/M/2/(N)K system with threshold control.

We will investigate a queuing system with finite buffer K capacity and threshold control at the level N<K. First we present the analytical model of the Markov birth-death system when the main transmission channel is without failures. Data packet length [l.sub.p] is exponentially distributed and packets arrive to the system in accordance with a Poisson process. Data packet buffer capacity K = 4, and threshold control level N = 2. Main transmission and reserve channel data packet transmission intensities are respectively equal to [[mu].sub.1], [[mu].sub.2], main channel failure rate is [gamma], mean time between failures is exponentially distributed, main channel repair intensity r, and repair time is exponentially distributed. The structure of such a system is shown in Fig. 1.

[FIGURE 1 OMITTED]

Data packets are transmitted only via the main transmission channel until the buffer achieves threshold level N. The reserve channel is used in two cases: when the number of packets in the buffer is equal to the threshold N, and when the main channel has failed. When the main channel has failed all arriving packets are served by the reserve channel without considering the number of data packets placed in the buffer. A birth-death Markov model of such a system when the main channel is without failures is shown in Fig. 2.

Each system steady state is described by the vector of three parameters XYZ. Main channel state parameter X=0 when the main channel is free, and X=1 when the channel is busy. Reserve channel state parameter Y=0 when the reserve channel is free, and Y=1 when the channel is occupied. System buffer state parameter Z indicates the number of data packets placed in the buffer and may vary from 0 to full buffer capacity K.

[FIGURE 2 OMITTED]

Data packet transmission intensity for each channel is given by [[mu].sub.1] = [C.sub.1] /[[bar.l].sub.p]; [[mu].sub.2] = [C.sub.2]/[[bar.l].sub.p], where [C.sub.1], [C.sub.2] is the transmission bit rate of each channel, [[bar.l].sub.p] is the mean value of data packet length in bits. Let [[mu].sub.1] + [[mu].sub.2] = [mu].

In this case, using the global balance concept, we can easily write down the following equations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

By solving (1) equations we obtain the system state probabilities [P.sub.XYZ]. This can be used to find such queuing system performance measures as:

1) Channel utilization:

[Y.sub.1] = 1 - [P.sub.000]; (2)

[Y.sub.2] = [P.sub.010] + [P.sub.110] + [P.sub.111] + [P.sub.112] + [P.sub.113] + [P.sub.114]. (3)

2) Mean number of data packets in a buffer [[bar.N].sub.q] :

[[bar.N].sub.q] = [P.sub.101] + [P.sub.111] + 2([P.sub.102] + [P.sub.112]) + 3[P.sub.113] + 4[P.sub.114]. (4)

3) Data packet loss probability:

[P.sub.l] = [P.sub.114]. (5)

4) The average time spent by data packets in a buffer (delay) in accordance with Little's law:

[bar.W] = [[bar.N].sub.q]/[lambda](1 - [P.sub.l]) = [[bar.N].sub.q]/[lambda](1 - [P.sub.114]). (6)

5) The probability that a data packet arriving to the system must wait:

Pr{W > 0} = [P.sub.101] + [P.sub.102] + [P.sub.111] + [P.sub.112] + [P.sub.113] + [P.sub.114]. (7)

Continuous time and discrete state Markov process for the system processes when the main transmission channel is subject to failure and repair is shown in Fig. 3. In this case each system steady state is described by the vector of three parameters XYZ. Main channel state parameter X=0 when the main channel is free, X=1 when the channel is busy, and X=x when the main channel has failed. Reserve channel state parameter Y=0 when the reserve channel is free, and Y=1 when the channel is occupied. System buffer state parameter Z indicates the number of data packets placed in the buffer and may vary from 0 to full buffer capacity K=4.

[FIGURE 3 OMITTED]

When the main channel has failed all arriving packets are served by the reserve channel without considering the number of data packets placed in the buffer. Data packet transmission intensity when both channels are operating properly is [mu] = [[mu].sub.1] + [[mu].sub.2].

Using the global balance concept, we can easily write down the following equations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

Queuing system performance measures are calculated by solving the underlying system of linear equations and some results of these performance measures are obtained:

1) Data packet loss probability in the system:

[P.sub.l] = [P.sub.114] + [P.sub.114]. (9)

2) Channel utilization:

[Y.sub.1] = [P.sub.100] + [P.sub.101] + [P.sub.102] + [P.sub.112] + [P.sub.113] + + [P.sub.114] + [P.sub.110] + [P.sub.111], (10)

[Y.sub.2] = [P.sub.112] + [P.sub.113] + [P.sub.114] + [P.sub.X10] + [P.sub.X11] + [P.sub.X12] + [P.sub.X13] + [P.sub.X14] + [P.sub.010] + [P.sub.110] + [P.sub.111]. (11)

3) Mean value of the number of data packets in the buffer:

[[bar.N].sub.q] = [P.sub.101] + [P.sub.X11] + [P.sub.111] + 2([P.sub.102] + [P.sub.112] + [P.sub.X12]) + 3([P.sub.113] + [P.sub.X13]) + 4([P.sub.114] + [P.sub.X14]) (12)

or according to Little's law

[[bar.N].sub.q] = [lambda](1 - [P.sub.l]) x [bar.W]. (13)

4) Mean waiting time in the buffer for data packets:

[bar.W] = [[bar.N].sub.q]/[lambda](1 - [P.sub.1]) = [[bar.N].sub.q]/[lambda](1 - [P.sub.114] - [P.sub.X14]). (14)

5) Mean number of data packets in the system:

[[bar.N].sub.s] = [[bar.N].sub.q] + [Y.sub.1] + [Y.sub.2]. (15)

6) Main channel fault probability:

[P.sub.1f] = [P.sub.X00] + [P.sub.X10] + [P.sub.X11] + [P.sub.X12] + [P.sub.X13] + [P.sub.X14]. (16)

7) Mean time spent in the system by each data packet:

[[bar.T].sub.s] = [bar.W] + [[Y.sub.1]/([Y.sub.1] + [Y.sub.2]) [[mu].sub.1] + [Y.sub.2]/([Y.sub.1] + [Y.sub.2]) [[mu].sub.2]] (17)

or in accordance with Little's law

[[bar.T].sub.s] = [[bar.N].sub.s]/[lambda](1 - [P.sub.l]). (18)

8) The probability that a data packet arriving in the system must wait:

Pr{W > 0} = [P.sub.101] + [P.sub.102] + [P.sub.111] + [P.sub.112] + [P.sub.113] + + [P.sub.114] + [P.sub.X11] + [P.sub.X12] + [P.sub.X13] + [P.sub.X14]. (19)

The numerical evaluation of a queuing system performance measures as a function of traffic intensity using the analytical model (17, 9, 14, 10, 11, 12) is shown in Fig. 4-7. Calculation results show how [[bar.T].sub.s], [[bar.N].sub.q], [Y.sub.1], [Y.sub.2] and [P.sub.l] values depend on [rho] ([rho] = [lambda]/[mu]) and how it is related to the [[mu].sub.1]/[[mu].sub.2] ratio.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

[FIGURE 7 OMITTED]

Simulation model of a G/G/2/(N)K system with buffer threshold control

It is clear from the material above, that the analytical model of M/M/2/(N)K will be very complicated for bigger K and N values. Another problem is that the given model is suitable only if data packet arrival and service processes are Poisson. Therefore, in this chapter we present the simulation model of a G/G/2/(N)K system with buffer's threshold control, which doesn't have these mentioned shortcomings.

The long-term reliability of the system's channels can be described by their availability coefficients [6]:

[A.sub.j] = [r.sub.j]/[[gamma].sub.j] + [r.sub.j]; (20)

here j--channel number. Then the 1-st and 2-nd channel states (1--working state, 0--failure state) over the i-th time moment can be modeled by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (21)

here: "[left arrow]"--value assignment symbol, if(a, b, c)--conditional operator (a--condition statement, b--result if a = TRUE, c--result if a = FALSE), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are random uniformly distributed values over (0, 1) interval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The number of data packets ([[lambda].sub.i]), which arrive in the system over the i-th time moment, can be constant or random.

Many mathematical calculation programs have built-in random number generation functions. For example, in MathSoft's MathCad package the set of n random [[lambda].sub.i] values (here i [member of] 1, 2, ..., n), which are Poisson distributed, can be generated by rpois(n, [lambda]). It is clear, that using the programs it is very easy to model the system with desired [lambda], [[mu].sub.1] and [[mu].sub.2] distributions.

Having the sets {[lambda]}, {[[mu].sub.1]}, {[[mu].sub.2]}, {[p.sub.1]}, {[p.sub.2]} of random [[lambda].sub.i], [[mu].sub.1i], [[mu].sub.2i], [p.sub.1i] and [p.sub.2i] values, it is possible to continue the simulation process.

In case of a Bernoulli channel failure process, the {[[mu].sub.1]} and {[[mu].sub.2]} values are recalculated by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (22)

Therefore, if the 1-st or 2-nd channel is in a state of failure then its packet transmission intensity is equal to zero.

The maximum possible number of packets which can be transmitted over the i-th time moment is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (23)

here [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]--the number of packets in the queue at the beginning of the i-th time moment (or at the end of the (i-1)-th time moment).

Then the number of data packets transmitted over the 1-st channel during the i-th time moment is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (24)

The number of data packets transmitted over the 2-nd channel during i-th time moment is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (25)

Therefore, the total number of data packets transmitted over the system during the i-th time moment is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (26)

Then the number of data packets in the queue at the end of i-th time moment is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (27)

Then the number of lost data packets at the end of i-th time moment is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

The system simulation consists of the cycle of n calculations. Therefore, it can be written by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (29)

Having the values of {[[lambda].sub.s1]}, {[[lambda].sub.s2]}, {[N.sub.q]} and {[[lambda].sub.l]} sets, it is possible to calculate the following parameters:

1) Probability of data packet loss in the system:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (30)

2) Channel utilization:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (31)

3) Mean value of the number of data packets in the buffer ([[bar.N].sub.q]) can be calculated by (13).

4) Mean waiting time in the buffer for data packets ([bar.W]) can be calculated by (14).

5) Mean number of data packets in the system ([[bar.N].sub.s]) is given by (15).

6) Mean time spent in the system by each data packet ([[bar.T].sub.s]) is given by (18).

Parameter evaluation using the simulation model

In this chapter we illustrate how the proposed model could be used for practical applications. For that purpose, let's take an example of the network connection used for VoIP transmission services (Fig. 8). Here the proposed model of buffer threshold control is implemented in the router, which is in the disposition of calls originating VoIP operator. Two internet service providers (ISP1 and ISP2) for appropriate 1-st and 2-nd channels are used to ensure the better availability and quality parameters of VoIP transmission services. The 2-nd channel is used in case of the 1-st channel's failure, or if the number of VoIP packets in the buffer is equal to or greater than N. The VoIP transmission quality parameters (such as data packet loss ([P.sub.l]), delay ([T.sub.s])) and the level of 1-st and 2-nd channel utilization ([Y.sub.1] and [Y.sub.2]) also depend on the selected N value. Therefore, the selection of the optimal N value and the estimation of VoIP transmission quality parameters are very important.

[FIGURE 8 OMITTED]

Due to paper size limitations it is not possible to present the whole complex of calculations that can be made using the given model. We have already presented the methods of VoIP system reliability estimation in [6]. Therefore, to evaluate the buffer threshold control mechanism, we took case when the channels are reliable.

Let's take case when VoIP packet arrival and transmission processes are Poisson. Other initial parameters are given in the Table 1.

In the given case, the channels are reliable. Therefore, packet losses are caused only by buffer overflow (when [lambda] > [[mu].sub.1] + [[mu].sub.2]). It is shown in Fig. 9.

[FIGURE 9 OMITTED]

Simulation results, which show how the [[bar.N].sub.q]], [[bar.T].sub.s]], [Y.sub.1] and [Y.sub.2] values depend on [lambda] and how it is related to the selected buffer threshold values, are presented in Fig. 10-12.

It is shown in the Fig. 10 that the mean number of VoIP packets in the buffer ([[bar.N].sub.q]) is related to the selected buffer threshold (N) values: [[bar.N].sub.q] = N when [[mu].sub.1] < [lambda] < [[mu].sub.1] + [[mu].sub.2]. It is obvious that it also affects the [[bar.T].sub.s] values (Fig. 11).

[FIGURE 10 OMITTED]

It is shown in the Fig. 11 that it is possible to determine the [[bar.T].sub.s] values by selecting the appropriate [[mu].sub.1], [[mu].sub.2] and N values.

[FIGURE 11 OMITTED]

It may be applied in the practical VoIP systems to ensure the non-critical VoIP packet transmission delay and to optimize the channel bandwidth usage. It is very important if the VoIP operator wants to minimize the reserve channel usage expenses.

[FIGURE 12 OMITTED]

For example, the simulation results show (Fig. 11-12) that it is necessary to choose 512 Kb/s bandwidth for both channels and N=10 pack. to ensure the [[bar.T].sub.s] < 30 ms and [Y.sub.2] [less than or equal to] 0.1 for 20 simultaneous VoIP calls ([lambda] = 1000 pack./s if 20 ms of voice is placed in a packet).

Conclusions

The system analytical models are accurate only in case of Poisson traffic and exponential data packet transmission time in channel. An exact analytical model becomes complicated when the system has an unreliable main transmission channel and size of buffer is large. More general study of system performance measures may be achieved by means of simulation.

Data packet loss probability can be substantially decreased by increasing system's queue length, when the losses happen due to queue's overflow. It is possible to calculate optimal queue length (K) for a given performance values.

The buffer threshold control mechanism may be applied in the practical real-time data transmission systems to ensure the non-critical packet transmission delay and to optimize the data transmission channel bandwidth usage.

By increasing the number of independent working channels for a network node it is possible to increase its availability and traffic serving possibilities. For maximum efficiency the optimal number of network channels should be selected for required (demanded) system performance values.

Received 2008 10 17

References

[1.] Rykov V., Efrosinin D. Optimal Control of Queuing System with Heterogeneous Servers. Queuing Systems, vol. 46, No3-4, 2004,--P.389-407.

[2.] Kim C. S., Konechny A., Dudin A. Treshold Control by a Single-Server Retrial Queue with Batch Arrivals and Group Services. Operations Research Letters, vol.34, issue5, September 2006, P. 548-556.

[3.] Rindzevicius R., Adlys G. Performance Measures of Data Network Node with Buffer Threshold Control // Electronics and Electrical Engineering.--Kaunas: Technologija, 2007. No. 8(80).--P. 29-34.

[4.] Bell S. L., Williams R. J. Dynamic Scheduling of a System with Two Parallel Servers in Heavy Traffic with Resource Polling: Asymptotic Optimality of a Threshold Policy. Annals of Applied Probability, vol.11, No.3, 2001,--P.608-649.

[5.] Larsen R. L., Agrawala A. K. Control of a Heterogeneous Two-Server Exponential Queuing System. IEEE Transactions on Software Engineering, vol.9, No.4, 1983, P.522-526.

[6.] Rindzevicius R., Tervydis P., Narbutaite L., Pilkauskas V. Performance Analysis of Data Packet Transmission Network with the Unreliable Channels. Electronics and Elecrical Engineering.--Kaunas: Technologija, 2008.--No. 4(84).--P. 53-58.

R. Rindzevicius, P. Tervydis

Department of Telecommunications, Kaunas University of Technology Studentu str. 50-423, LT-51368 Kaunas, Lithuania, e-mail: Ramutis.Rindzevicius@ktu.lt
Table 1. VoIP transmission system parameters

VoIP packet size    74 B (G.729 codec with 20 ms payload)

Data transmission   1)   256 Kb/s [right arrow]
rate over ISP1           [[mu].sub.1.sup.(1)] = 442.8 pack./s
channel
                    2)   512 Kb/s [right arrow]
                         [[mu].sub.1.sup.(2)] = 855.6 pack./s

                    3)   768 Kb/s [right arrow]
                         [[mu].sub.1.sup.(3)] = 1328.4 pack./s

Data transmission   1)   768 Kb/s [right arrow]
rate over ISP2           [[mu].sub.1.sup.2(1)] = 1328.4 pack./s
channel
                    2)   512 Kb/s [right arrow]
                         [[mu].sub.1.sup.2(2)] = 855.6 pack./s

                    3)   256 Kb/s [right arrow]
                         [[mu].sub.1.sup.2(3)] = 442.8 pack./s

Buffer size            4 KB [right arrow] K = 55 pack.
COPYRIGHT 2009 Kaunas University of Technology, Faculty of Telecommunications and Electronics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:TELECOMMUNICATIONS ENGINEERING/ TELEKOMUNIKACIJU INZINERIJA
Author:Rindzevicius, R.; Tervydis, P.
Publication:Elektronika ir Elektrotechnika
Article Type:Report
Geographic Code:4EXLT
Date:Feb 1, 2009
Words:3314
Previous Article:Lighting of workplaces and health risks/Darbo vietu apsvietimas ir jo sukeliama rizika sveikatai.
Next Article:A platform for adaptive equalization prototyping/Adaptyviojo vienodintuvo aparatinio modeliavimo platforma.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters