Features of Processing Various Self-Similar Traffic of Telecommunication Networks Volodymyr Nakonechnyi 1, Valery Kozlovskyi 2, Andrii Toroshanko 2 and Ivan Shvets 2 1 Taras Shevchenko National University of Kyiv, 60 Volodymyrska str., Kyiv, 01601, Ukraine 2 National Aviation University, 1 Lubomyra Huzara Avenue, Kyiv, 03680, Ukraine Abstract Considered models of mass service systems of self-similar traffic of telecommunication networks. The differences of the main ratios of mass service theory for self-similar traffic in comparison with random processes with a classical Poisson distribution, as well as with distributions with so-called "heavy tails": Pareto, Weibull, log-normal distribution, gamma distribution, beta distribution, are analyzed. Analytical expressions for evaluating the key parameters of mass service systems of self-similar traffic under conditions of stationarity and ergodicity of the request arrival process are presented. Considered models of a single-channel and multi-channel service system with shared and shared buffer memory for the incoming request queue. For self-similar traffic, the analytical dependence of the average queue length on the average network utilization rate is determined. The Hurst parameter was used to estimate the correlation function of self-similar processes. The necessity of managing the packet arrival period and other parameters of the self-similar incoming flow is shown, reducing the risk of overloading individual routes and autonomous network segments. Graphs are shown that illustrate the dependence of the required buffer memory on the utilization ratio, as well as the growth of the queue for deterministic and quasi-deterministic traffic. Keywords 1 Telecommunication network, self-similar traffic, mass service theory, multi-channel system, Hurst parameter, network utilization factor 1. Introduction The processes of the functioning of networks and communication systems can be represented as a set of mass service systems (MSS), for which the characteristics of QoS service quality [1] and other performance indicators are determined. The assessment of traffic service quality indicators requires taking into account many factors in order to build adequate, scientifically based methods of calculation. For components used to build telecommunication networks (computers, operating systems, network technologies, etc.), analytical models based on mass service theory (MST) provide an acceptable convergence of theory and practice. The accuracy of simulation results is in all cases limited by the accuracy of the input data. In addition, even in the presence of many assumptions introduced when using MST, the obtained results are close to those that would be obtained with more detailed simulation modelling [2-6]. In addition, analysis based on MST can be performed in a shorter time than simulation. 2. Formulation of the research task In the mathematical models of MSS, the type of input flow, the scheme of the system and the discipline of service are taken into account 1, 2. Information Technology and Implementation (IT&I-2023), November 20-21, 2023, Kyiv, Ukraine EMAIL: vv_k@nau.edu.ua (V. Kozlovskyi); atoroshanko@ukr.net (A. Toroshanko); ivan.shvets@gmail.com (I. Shvets); volodym.nakonechnyi@knu.ua (V. Nakonechnyi) ORCID: 0000-0002-8301-5501 (V. Kozlovskyi); 0000-0002-0816-657X (A. Toroshanko); 0000-0001-7546-764X (I. Shvets); 0000-0002- 0247-5400 (V. Nakonechnyi) ©️ 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 248 Requests arrive at MSS with some average intensity  (number of requests per second). At any given time, there will be a certain number of requests (zero or more) in the queue; denote the average number of requests in the queue by w , the average number of requests served – by ρ, and the average waiting time is 𝑇𝑤 . This time is averaged over all requests received at the entrance. Average service time of one request 𝑇𝑠 ̶ this is the time interval between sending the request to the server and leaving the serviced request from the server. Service intensity 𝜇 – this is the number of requests served per unit of time. The total average number of requests in the system is defined as 𝑟. Average time of finding a request in the system (waiting in the queue and service) – 𝑇𝑟 . If the capacity of the queue is infinite, then requests in the system are never lost; they are only delayed during waiting and service times. Under these circumstances, the average number of sent requests is equal to the average number of incoming requests per unit of time. When the intensity of the arrival of requests at the entrance of the system increases, the time of finding requests in the system also increases, which leads to traffic jams (overload). The queue is getting longer, the waiting time is increasing. When 𝜌 = 1 , i.e 𝜆 = 𝜇, the server is saturated, working 100% of the time [1]. Therefore, the theoretical maximum intensity of the incoming flow is related to the average service time 𝑇𝑠 as 𝜆max = 1⁄𝑇 . 𝑠 In the first approximation, the length of the request stream is taken as an infinite stream. This means that the average frequency of applications does not change when they are lost. If the length of the stream is limited, then the amount of requests that can be expected at the system entrance is reduced by the number of requests currently in the system; this usually results in a proportional decrease in the average frequency of applications. If an infinite queue size is assumed, the waiting time can grow to infinity. Under the conditions of a limited queue, some applications in the system may be lost. In practice, of course, any queue is limited. In many cases, this does not lead to a significant difference in the analysis [1, 2]. 3. Models of mass service systems The simplest and most frequently used in MSS are service disciplines FIFO (First came In – First came Out) and LIFO (Last In – First Out) 3, 6, 8]. In computer and telecommunication networks, other service disciplines can also be chosen [9], for example: ̶ FIRO (First came In ̶ in Random order came Out. Another name ̶ SIRO (Service In Random Order); – SPT (Shortest requests are Processing First); – PRS (Priority Requests Service), service according to priority. In practice, the service discipline is chosen for reasons of acceptable service time. For example, in a node with packet switching, it is possible to provide for the sending of the shortest packets first or, conversely, the longest packets. This choice is determined by the nature of traffic and quality of service requirements. 3.1. Single-channel MSS model This is the simplest model of SMO [10, 11] (Figure 1). The central element of the system is a server that serves the incoming flow of applications. These applications enter the service system. If the server is free, the request is served immediately. Otherwise, the application becomes a queue for service. Figure 1: Single-channel MSS model 249 When the server has finished servicing the current request, it is removed from the queue. If there are requests in the queue, one of them immediately enters the server according to the service discipline used. The server in this model can perform some auxiliary services in processing requests. Examples: a processor provides a service to processes; the data transmission line provides the service of transmission of packets or frames; an I/O device provides read or write requests. When the system is saturated, when 𝜌 → 1, the queue grows to infinity. In practice, in a single-channel system, the intensity of the input flow is limited to 70% to 90% relative to the theoretical maximum. 3.2 A model of a multi-channel system with a common queue In figure 2 shows a model of a multi-channel service system with a shared buffer memory of the input queue of requests. A common queue with a given service discipline is used for all requests. If a request arrives at a time when at least one server is free, it is immediately sent to that server. All servers are assumed to be identical; therefore, if more than one server is available, it does not matter which server is selected for service. If all servers are busy, a queue begins to form. As soon as one server becomes free, the request is dequeued according to the current service discipline. Figure 2: Multi-channel service system with a common queue Except for service intensity 𝜌, all parameters used in the analysis of a single-channel system have the same meaning. If used 𝑁 identical servers, then the average intensity of maintenance of the system as a whole is equal to 𝑁𝜌. This term is often associated with traffic intensity 𝑢, which is numerically equal to the intensity of the incoming flow of requests  . The theoretical maximum of the relative service intensity is equal to 𝑁 × 100%, and the theoretical maximum intensity of the incoming flow is 𝜆max = 𝑁⁄𝑇 . 𝑠 3.3 A model of a multichannel system with a split queue In figure 3 shows a multi-channel system with a separate buffer memory. Such a system can be interpreted as a parallel structure of single-channel service systems. Although the structural changes are not fundamental, the operating characteristics of the depicted system may differ from those previously discussed. The key characteristics of a queue with multiple serving devices are similar to those of a single-channel system. An infinite volume of buffer memory and an infinite size of the queue are assumed, with the distribution of the queue among all serving devices (servers). It is commonly believed that the discipline of service in the order of arrival (FIFO) is implemented. In the case of a multi-channel service system, if all servers are assumed to be identical, the choice of a specific server for the next request does not affect the service time. 4. Determination of key parameters of self-similar traffic To estimate the average queue size r under conditions of stationarity and ergodicity of the 250 application arrival process, Little's formula is used 1, 9, 11: - for a single-channel service system: 𝑟 = 𝜆𝑇, 𝑟 = 𝑤 + 𝜌; (1) - for 𝑁 -channel service system: 𝜆𝑇𝑟⁄ (2) 𝜌= 𝑁, 𝑢 = 𝜆𝑇𝑠 = 𝜌𝑁, 𝑟 = 𝑤 + 𝑁𝜌, де 𝑇𝑟 = 𝑇𝑤 + 𝑇𝑠 . Accordingly, Little's formulas can be used to connect the number ρ with the intensity of incoming requests 𝜆 and the time the request was in the system 𝑇𝑠 : 𝜌 = 𝜆𝑇𝑠 . Figure 3: Multi-channel service system with split buffer queue Thus, the following a priori information is necessary for the analysis of MSS: the intensity of the incoming flow of requests, the average service time, and the number of service channels. Based on this information, you can get asymptotic estimates of the average number of requests in the queue, the average waiting time, and the total time the requests are in the system. It should be taken into account that request flows may not be distributed according to Poisson's law, but according to other probabilistic laws with so-called "heavy tails" [11]. These are the Pareto, Weibull, log-normal distribution, gamma distribution, beta distribution, and some other less popular ones. For example, for the Pareto distribution, the main relations have the following form: - probability density 𝛼+1 (3) 𝑓 (𝑥 ) = 𝛼⁄𝑘 (𝑘⁄𝑥) , (𝑘 і 𝛼 < 0) ̶ distribution parameters; - probability function: 𝛼 𝐹(𝑥 ) = 1 − 𝑘⁄𝑥 , (𝑥 > 𝑘, 𝛼 > 0); (4) - average value 𝐸 [𝑋] = 𝛼⁄𝛼 − 1 𝑘, (𝛼 > 1). (5) Real random processes, of course, preserve the property of self-similarity only up to a certain limit. This measure of the statistical stability of the process under multiple scaling is defined by the so-called Hurst parameter or related self-similarity parameter. A random process x(t) is statistically self-similar 𝑥(𝑎𝑡)⁄ with the Hurst parameter H (0,5  H  1), if for any a > 0 process 𝑎𝐻 has the same statistical x t  characteristics as the process itself: - mathematical expectation 𝑀[𝑥(𝑎𝑡)]⁄ (6) 𝑀[𝑥(𝑡)] = 𝑎𝐻 - dispersion 𝐷[𝑥(𝑎𝑡)]⁄ (7) 𝐷[𝑥(𝑡)] = 𝑎2𝐻 - correlation function 𝑅(𝑎𝑡, 𝑎𝜏)⁄ (8) 𝑅(𝑡, 𝑎) = 𝑎2𝐻 251 The more 𝐻, the longer the property of self-similarity is preserved under multiple scaling. At 𝐻 = 0,5 this property is practically absent. Correlation functions of self-similar processes with a large Hurst parameter decay more slowly than those of ordinary random processes, and the decay has, as a rule, an oscillatory character. It was established that the constant component of the correlation function decreases according to the law 𝑐1 𝑡 −𝑐2 𝑎 , where 𝑐1 , 𝑐2 ̶ constants, 𝑎 ̶ scale parameter. Accordingly, the spectral density of the process theoretically tends to infinity at a frequency approaching zero. Ratios (1-7) can be useful as asymptotic approximations of real processes. Such specific characteristics are inherent not only to data traffic (TCP, FTP protocols), but also to signal traffic (SS7 protocol), VBR-video, Ethernet/ISDN and some others. Physically, they are caused by a high degree of grouping of packets at client sites, in routers and switching nodes of information communication networks. Even if the source generates a regular stream of packets, the data is delivered to the consumer in bursts interspersed with idle intervals. The reasons for this are the limited speed of network devices, insufficient volume of buffers, etc. In addition, self-similar traffic has a special structure that is preserved during multiple scaling. In real processes, there is some outliers with a relatively small average traffic level. Due to such bursts of load, network characteristics also deteriorate: losses, delays, jitter of packets when passing through network nodes increase [12]. Methods for calculating the requirements for networks of new generations (channel bandwidth, buffer capacity, etc.) based on Markov models and Erlang or Little formulas, which were successfully used in the design of telephone networks, can give unreasonably optimistic solutions and lead [7, 13]. With the self-similar nature of the traffic, the dependence of the average duration of the queue (respectively, the required size of the buffer) q from the average utilization ratio has the following form: 𝜌1/2(1−𝐻) 𝑞= ⁄ (1 − 𝜌)𝐻/(1−𝐻) At H=0,5 this formula is simplified: 𝜌 𝑞 = ⁄(1 − 𝜌) which is a classical result of MSS with the simplest input flow and exponentially distributed service time (М/М/1). For a system with deterministic maintenance time (М/D/1) a classic result looks like this: 𝜌 𝜌2 𝑞 = ⁄1 − 𝜌 − ⁄2(1 − 𝜌). In figure 4 shows the results of calculations of the dependence of the required buffer memory 𝑞𝑏𝑢𝑓𝑓 from the utilization factor 𝜌 = 𝜆⁄𝜇 for different inbound traffic patterns. Calculations are made as for Poisson flows of requests M/M/1 і M/D/1, as well as for self-similar flows. (1 – H=0,6; 2 – H=0,8; 3 – H=0,7; 4 – H=0,4; 5 – M/M/1; 6 – M/D/1) Figure 4: Dependencies of the required buffer memory on the utilization ratio 𝝆. 252 The graphs clearly show that for self-similar traffic already at   0,4 a larger memory resource of buffer devices is required than for the classic model M/M/1, which is considered the least favorable compared to others (for example, with a constant or Gaussian service time distribution). The rate of growth of the required amount of memory increases with the increase of the Hurst parameter, which is mainly due to the degree of grouping of homogeneous packets and bursts of network load. It can also be concluded that simply increasing the buffer memory (hardware or software) is ineffective. With the expected increase in the share of data traffic in the total volume, the degree of self- similarity will increase, and the dependence 𝜌(𝑞𝑏𝑢𝑓𝑓 ) will grow more and more sharply. To eliminate or at least reduce the harmful effect of traffic similarity, methods of regulation or shaping of the incoming flow (policing - shaping) are usually used. Ideally, this results in a deterministic or close to deterministic application order. With deterministic traffic (deterministic order of incoming applications and deterministic processing time), the queue growth graph is a linear-broken line (Figure 5). 12 10 8 6 4 2 0 0 0.25 0.5 0.75 1 1.25 1.5 M/D/1 D/D/1 Figure 5: Graph of queue growth with deterministic traffic In practice, both the traffic at the output of the shaper and the packet processing time are quasi- deterministic (we denote them by QD). In figure. 6 shows graphs for the relevant cases. 12 10 8 6 4 2 0 0 0.25 0.5 0.75 1 1.25 1.5 M/D/1 D/D/1 QD/D/1 QD/M/1 Figure 6: Graph of queue growth with quasi-deterministic traffic 5. Conclusions Models of heterogeneous computer network traffic, which has self-similar properties, are analyzed in the work. The considered models of single-channel and multi-channel service system with shared and separate buffer memory for the input queue of requests. Their advantages and disadvantages are shown. Analytical expressions for evaluating the key parameters of mass service systems of self-similar traffic under conditions of stationarity and ergodicity of the application arrival process are presented. 253 For self-similar traffic, the analytical dependence of the average queue duration on the average network utilization rate is determined. To eliminate traffic bursting caused by the similarity of the incoming stream, it is necessary to control its parameters, first of all, the period of arrival of packets. Thanks to this, the rate of growth of queues in the buffer memory of switching nodes slows down. As a result, the risk of overloading individual routes and autonomous network segments is reduced.. 6. References [1] Giambene G. Queuing Theory and Telecommunications: Networks and Applications; 2nd edition. ‒ Springer NY, 2014. [2] Floudas C.A., Pardalos P.M. Encyclopedia of optimization: 2-d ed. – Springer science+buisiness media, LLC, 2009. – 4646 p. [3] Bonaventure O. Computer Networking: Principles, Protocols and Practices. Release. – cnp3book, 2018. [4] Stallings W. Foundations of Modern Networking: SDN, NFV, QoE, IoT, and Cloud. New Jersey; Pearson Education, Inc., Old Tappan, 2016. [5] Popovsʹkyy V.V. Telekomunikatsiyni systemy ta merezhi. Struktura ta osnovni funktsiyi. Kharkiv.: SMIT, 2018. http://www.znanius.com/3534.html [6] Speidel J. Introduction to Digital Communications / Springer Nature Switzerland AG, 2019. [7] Kurose J.F., Ross K.W. Computer Networking: A Top-Down Approach. ‒ 7th ed. ‒ Pearson Education, Inc., 2017. [8] Frenzel L.E. Principles of electronic communication systems, 4th Ed. McGraw Hill Education, 2016. [9] Lesnaya N.N. Development of control algorithm intelligent multiservice networks. Problems efficiency infrastructure. Collected Works, issue 11. Kyiv, 2015. 150-155. [10] Tanenbaum Andrew S., Maarten Van Steen. Distributed systems: principles and paradigms. Pearson Education. Inc. Pearson Prentice Hall, Upper Saddle River, NJ 07458, 2007. [11] Vinogradov N.A., Savchenko A.S. Comparative analysis of the functionals of optimal control corporate computer network. Journal of Qafqaz University (Mathematics and Computer Science). Vol. 1, Nr. 2., 2013. 156-167. [12] Di Giorgio A., Pietrabissa A., Priscoli F.D., Isidori A. Robust Output Regulation for a Class of Linear Differential-Algebraic Systems. ‒ IEEE Control Systems Letters. ‒ 2018. ‒ Vol. 2, No. 3. ‒ P. 477-482. [13] Forbs C., Evans M., Hastings N., Peacock B. Statistical Distributions: 4-th Edition. ‒ John Wiley & Sons, Inc., Hoboken, New Jersey, 2011. ‒ 212 pp. 254