EMPIRICAL RELATIONSHIP FOR QUEUE LENGTH ESTIMATION IN A SYSTEM WITH FRACTAL SHOT INPUT

全文:

Introduction. In recent years the traffic of data com- munication networks, also as a part of distributed infor- mation systems, characterized by high variability and explicit correlation properties, is described by various fractal models [1-4]. Unlike geometrical fractals, determination of which is based on geometrical similarity of a part of an object to the whole, with fractal random processes - the part of a path is similar to the whole statistically: when averaging Time varying rate of FSNDP process is set by the con- tinuous accidental process - fractal shot noise which is received by filtering classical Poisson process. FSNDP process is completely defined by five numeri- cal parameters (µ, β, K, A, B), having the following value. Primary Poisson stream {ti} with constant rate µ be- comes the input to a linear filter with impulse response function ìïKt-b,t Î( A, B), by time at various scales, the process substantially keeps values of the first and second order statistics, i. e. doesn’t smooth out, doesn’t lose variability and correlation struch(t) = í ïî 0, t Ï( A, B), (1) ture. Fractal or self-similar properties of the network traffic, revealed originally on the Ethernet networks and broad- band access (BBA) in the 1990s [5; 6] explains feeble suitability of classical Markov methods and models of the queueing theory for simulation of the modern high-loaded systems and data communication networks. First of all it is about the explicit correlation structure - the phenome- non of an after-effect which by definition neglects Markov models. However, despite adequacy of traffic streams description using fractal models, receiving of expressions suitable for practical calculations for the queueing system models is connected with considerable difficulties. Several options of formulas for queueing sys- tem models with the elementary fractal sequence on the basis of fractional Brownian motion [7; 8] are known, where β is defined by the level of the process self- similarity; A, B - non-negative cut-off parameters; K - the positive constant, determining the amplitude of total proc- ess. The filter produces the fractal shot noise ¥ I (t) = å h(t - ti ), , (2) i=-¥ considered as time varying rate for the second Poisson point process, which output is the FSNDP. FSNDP process acquires steadily self-similar properties under a condition that А << B and А, close enough to zero. With practical modeling it is usually accepted that А = 0 or А = 10-7. Parameter β is connected with Hurst parameter H, i. e. defines degree of expressiveness of fractal properties of the resultant process: though this flow can be considered adequate for the description of backbone segments traffic, not for distributed H = 3 2 - b. (3) information systems at the level of individual worksta- tions and small workgroups. Also there are solutions based not on specific sequence models, but on their uni- versal statistical characteristics [9]. On the basis of simulation modeling the authors man- aged to receive the ratios suitable for calculation of queue volume in queueing systems with an input flow using the fractal shot process and therefore, for capacity of the appropriate fragments of packet-switching networks estimation. Fractal shot process (FSNDP) model. According to the result of the research of the Ethernet-traffic real traces, as the authors have shown [10-12] earlier, the adequate model of packet flow in distributed system of data proc- essing with the remote workstations, one of fractal point processes, namely the fractal shot process which is also called FSNDP (Fractal Shot Noise Driven Poisson), be- longing to the category of double stochastic Poisson point processes, can be used. For the first time the model of the network traffic based on this process was suggested by S. Lowen and B. Ryu [13, 14]. For the process there are ap- proaches to statistical parameterization on the received dumps of the real traffic, it also can be generated using the correct and moderately labor-consuming calculations within the set parameters. Hurst parameter of H is the most general characteristic of any fractal process and can accept values from an in- terval [0.5; 1). Value 0.5 means total absence of fractal properties, growth of H towards 1 - strengthening of ex- pressiveness of self-similar character. General comments on the approach to simulation modeling. Earlier, on the basis of the analysis of really operating distributed information systems network traffic dumps the fractal shot process of FSNDP was considered to be an adequate model of such traffic. Also numerous estimates of parameters of the FSNDP model on real dumps have been carried out; for generating the artificial sequences in this research the values which are close to the values characterizing some typical dumps of the real traffic [12$ 15], but rounded for simplicity were used. Values µ = 0.1, K = 10, A = 0, B = 100, β = 0.9 have been accepted as a basic set of parameters. Earlier it has also been confirmed that the stream with constant (deterministic - D) service rate corresponds the most to the real network load for client-server data proc- essing system, i. e. the FSNDP/D/1 system is the most suitable for modeling. In terms and units of information transfer the volume of a packet is accepted as 100 bytes that is also close to real estimates. The general approach to the research of influence of model parameters on the behavior of the queue is based on generating of pseudorandom sequences of FSNDP stream events with the variation of one or several parame- ters of rather basic set and use of these sequences as an input stream of simulation model of a single-channel server queueing system with simulated continuous time. All generated sequences have the symbolic duration of 7200 sec. (2 hours) and volume, depending on the varied parameters, from 25 thousand prior to 450 thousand events. Influence of process parameters on the average length of the queue. Parameter K characterizes amplitude of the resultant process’s rate bursts; therefore it is obvious that correlation between K and average queueing load ρ will be direct (fig. 1). Simulation modeling allows to assume direct proportionality of the average queue length estimation from K. Direct influence on the height of the curve queueing system load for β exponent; respectively, the reverse influence of Hurst parameter H connected with this indicator is determined. This result, which is steadily shown during the runs of simulation model for various Influence of primary (auxiliary) Poisson sequence µ on characteristics of the queue length has appeared to be significantly lower than of the two above described pa- rameters, and is demonstrated mainly in the field of high load - at ρ > 0.8. According to the earlier research, such loading at a fractal input in practice means the mode close to non-stationary, and doesn’t allow traffic and buffer parameters more or less precise estimation. Curve buffer fill for values µ, differing by factor 16 are given in fig. 3. The only parameter of FSNDP process which influence on the queue under realistic values of the other parameters has not been revealed is B. Abcense of the explicit influence corresponds to physical sense of this value: duration of the decreasing intensity intervals, after which the cut-off is done, obviously shouldn’t have dramatic impact on queueing system behavior, comparable with the influence of other parameters. Empirical ratios for the queue length estimation. By comparison of calculated values with the values received as a result of simulation modeling of queueing system behavior with a fractal shot input of FSNDP it is confirmed that under real values of the FSNDP parameters the estimation of the average queue length can be expressed by the ratio values of the FSNDP parameters, in general differs from the popular conception that for the general case of the q(r) = C K r , (4) fractal traffic a higher degree of self-similarity results in larger queue fill (buffer). The cause of alternative effect for a special FSNDP case needs a future research (fig. 2). 1 600 1 400 1 200 Подпись: Nq(p)1 000 800 600 400 200 H 1 -r where С - positive constat, Н - Hurst parameter connected with the process β parameter value by ratio (3). 1 2 3 µ 0,1 0,1 0,1 Β 0,9 0,9 0,9 K 10 5 (1/2) 20 (X2) A 0 0 0 B 100 100 100 1 2 3 0 0 0,2 0,4 r 0,6 0,8 1 Fig. 1. The average length of the queue under parameter K variation Рис. 1. Средняя длина очереди при варьировании параметра К 1 600 1 1 2 3 µ 0,1 0,1 0,1 Β 0,9 0,8▼ 0,95▲ K 10 10 10 A 0 0 0 B 100 100 100 H 0,6 0,7▲ 0,55▼ 1 400 2 3 1 200 Подпись: Nq(p)1 000 800 600 400 200 0 0 0,2 0,4 0,6 r 0,8 1 Fig. 2. The average length of the queue under parameter β variation Рис. 2. Средняя длина очереди при варьировании показателя β In the expression there are no parameters B and µ, significant effect of which on the queue under real condi- tions isn’t revealed in the simulation modeling. However, since µ under ρ > 0.8 can after all impact the queue length, it must be kept in mind that the queue estimation accuracy using this ratio in the queueing modes close to non-stationary mode, will decrease. Value of the constant which equals C = (5) in the given simulation experiments has shown rather accurate coincidence of experimental and calculated curves for various parameters of the FSNDP modeled fractal shot process. In fig. 4. examples of curves of the buffer fill q(ρ) for parameter values µ = 0.1, K = 10, A = 0, B = 100 and β = 0.8, β = 0.9 are given, under the constant value according to the assumption (5). It should be noticed that in the modes of minor load calculated values are slightly higher than those received by simulation modeling, i. e. the received estimation can be considered as the upper bound (fig. 4). 1 300 1 200 1 100 1 000 900 800 Подпись: Nq(p)700 600 500 400 300 200 100 0 0 0,2 0,4 r 0,6 1 1 2 µ 0,025 0,4 Β 0,9 0,9 K 10 10 A 0 0 B 100 100 2 0,8 1 Fig. 3. The average length of the queue for significantly different parameter µ Рис. 3. Средняя длина очереди при для существенно отличающихся значений µ 600 550 500 450 400 350 Nq(p) 300 250 200 150 100 50 0 0 0,2 0,4 r 0,6 0,8 0.9 0.9 (calculation) 0.8 0.8 (calculation) 1 Fig. 4. Simulation and calculation curves of queue lengths under various β Рис. 4. Имитационные и расчетные кривые длины очереди при различных β Having combined (3), (4) and (5), it is possible to ex- press the ratio for the average queue length estimation in single-server queueing system with fractal shot FSNDP process and determined maintenance time (FSNDP/D/1) input as: motion input. Electronics Letters. 2015, Vol. 51 (9), P. 699-701. 9. Petrov M. N., Ponomaryov D. Y. [Self-similarity in queueing systems with limited buffer]. Electrosvyaz. 2002, No. 2, P. 35-39 (In Russ.). or q(r) = 1 K r , 2 H 1 -r (6) 10. Sokolov D. E., Trenogin N. G. [The nature of the network traffic to the client site distributed client-server system]. Materialy mezhvuzovskoy nauchno-tekhnicheskoy konferentsii “Upravlyayushchie i vychislitel’nye sistemy. K r K r Novye tekhnologii” [International scientific-technical q(r) = = 2( 32 - b) 1 -r . 3 - 2b 1 -r (7) conference Informatics and problems of telecommunica- tions]. Novosibirsk, SibSUTIS Publ., 2001, P. 34-35 (In Conclusion. The offered expressions for the queue length estimation are very low resource-consuming in computation. It allows to use them both in calculation and optimization algorithms to determine throughput of data communication network elements with fractal traffic flows as well as time delays caused by these elements. Receiving explicit ratios increases the value of the FSNDP traffic model. For this process there are ways of computer parameterization, based on available process path fragments (network traffic dumps); algorithms of the artificial sequences generating with the known parame- ters. Now there is also an opportunity to calculate the queue and delays in an explicit form, i. e. to carry out a full cycle of model analysis without simulation, or with the minimum use of it. Also, there are grounds for further research, such as receiving of estimates for the queue statistical characteris- tics of the second order; and also development of defini- tion methods of queueing networks with fractal flows, in particular on the basis of tensor approaches [15], based on earlier established property of keeping a flow after servic- ing in the system with queue.

作者简介

N. Trenogin

Macroregional branch “Sibir” of PJSC Rostelecom

53, M. Gorky St., Novosibirsk, 630099, Russian Federation

M. Petrov

Reshetnev Siberian State University of Science and Technology

Email: ettk@bk.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

D. Sokolov

Macroregional branch “Sibir” of PJSC Rostelecom

53, M. Gorky St., Novosibirsk, 630099, Russian Federation

参考

补充文件