5 UDC 004.021:519.6 Modeling RED algorithm modifications in the OpenModelica Anna-Maria Y. Apreutesey* , Anna V. Korolkova* , Dmitry S. Kulyabov*† * Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University) 6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation † Laboratory of Information Technologies Joint Institute for Nuclear Research 6 Joliot-Curie, Dubna, Moscow region, 141980, Russia Email: 1032152610@pfur.ru, korolkova-av@rudn.ru, kulyabov-ds@rudn.ru The goal of this work is to simulate the Random Random Detection algorithm (RED) and Double Slope Random Early Detection (DSRED) and Gentle Random Early Detection (GRED) modifications in Modelica. RED and its modifications allow to control the network load by selectively discarding packets before the queue is full and Transmission Control Protocol (TCP) begins to reduce the transmission rate preventing resynchronization. This selective packet loss helps TCP find the right data rate faster and keep the queue size and latency at the appropriate level. The existence of a large number of modifications of the classical RED algorithm is associated with the problem of selecting the parameters of the algorithm (queue thresholds, maximum drop parameter, etc.) under which the system would function stably and efficiently. The Modelica language is used as the implementation language. Based on the results obtained during the simulation it is planned to conduct a comparative analysis of the three algorithms with similar initial parameters to reveal the advantages of one or another algorithm. Key words and phrases: active queue management, simulation, hybrid modeling, Mod- elica. Copyright © 2019 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the IX Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Moscow, Russia, 19-Apr-2019, published at http://ceur-ws.org 6 ITTMM—2019 1. Introduction The active queue management (AQM) [1–3] algorithm with the Random Early Detection (RED) control algorithm is used to monitor and prevent congestion in router queues [4–7]. The RED allows you to adjust the flow rate by selectively dropping packets before the queue is full. If the router queue is almost empty, all packets arriving at the system are accepted. As the queue is filled and as a result of exceeding a certain threshold value, the packet drop function starts to work. This causes TCP-like protocols to slow down the transmission rate and prevents re-synchronization of connection parameters. There are many modifications of RED that improve certain characteristics of this algorithm [8, 9]. As a modeling tool is proposed to use the language Modelica in the software envi- ronment OpenModelica [10–13]. Modelica is a language developed by the non-profit organization Modelica. This association is also developing a free standard library for this language. Modelica supports continuous and hybrid (continuously discrete) paradigms. 2. Simulation of the DSRED algorithm The algorithm Double Slope Random Early Detection (DSRED) [9, 14] introduces an additional threshold value 𝑞𝑚𝑖𝑑 between the minimum 𝑞𝑚𝑖𝑛 and maximum 𝑞𝑚𝑎𝑥 thresholds of the queue,𝑞𝑚𝑖𝑑 = 0, 5(𝑞𝑚𝑎𝑥 − 𝑞𝑚𝑖𝑛 ). The probability function for dropping packets in the DSRED algorithm is: ⎧ ⎪ ⎪ ⎪ 0, 𝑞ˆ < 𝑞𝑚𝑖𝑛 , ⎪ ⎪ 𝑞 − 𝑞𝑚𝑖𝑛 ) , 𝛼 (ˆ 𝑞𝑚𝑖𝑛 ≤ 𝑞ˆ < 𝑞𝑚𝑖𝑑 , ⎨ 𝑝(ˆ 𝑞) = (1) ⎪1 − 𝛾 + 𝛽 (ˆ ⎪ ⎪ 𝑞 − 𝑞𝑚𝑖𝑑 ) , 𝑞 𝑚𝑖𝑑 ≤ 𝑞 ˆ < 𝑞𝑚𝑎𝑥 , ⎪ ⎪ ⎩ 1, 𝑞ˆ > 𝑞𝑚𝑎𝑥 . 2 (1 − 𝛾) 2𝛾 𝛼= , 𝛽= 𝑞𝑚𝑎𝑥 − 𝑞𝑚𝑖𝑛 𝑞𝑚𝑎𝑥 − 𝑞𝑚𝑖𝑛 . Variable 𝛼 reflects the slope of the function in the first segment between threshold values 𝑞𝑚𝑖𝑛 and 𝑞𝑚𝑖𝑑 . Since overload is not critical in this segment, 𝛼 is chosen in such a way as to discard as few packets as possible. The coefficient 𝛽 adjusts the slope of the function for the second segment between 𝑞𝑚𝑖𝑑 and 𝑞𝑚𝑎𝑥 . In this segment, the probability of dropping a packet must be high enough to warn the sender of overload. Therefore, 𝛽 must be greater than 𝛼. The mode selector for setting the packet drop function is the variable 𝛾 (fig. 1). The program, written in Modelica, reflects the behavior of the packet drop function (1) and the three main system parameters [7]: – 𝑤(𝑡) is the average TCP window size (in packets); – 𝑞(𝑡) is the average queue size (in packets); – 𝑞ˆ(𝑡) is the queue size exponentially weighted moving average of the queue size. The following is a code fragment describing the behavior of the main parameters of the system 𝑤(𝑡), 𝑞(𝑡), 𝑞ˆ(𝑡) controlled by the RED algorithm (listing 1). The operator der sets the time derivative, the operator delay sets the delay. Listing 1: Changing the main parameters of the RED system der ( w ) = wAdd ( w, wmax, T ) - w * delay ( w, T ) * delay ( p, T ) / ˓→ (2 * delay ( T, T ) ) ; der ( q ) = qAdd ( pre ( q ) , w, T, C, N, R ) ; der ( q_avg ) = wq * C * ( q - q_avg ) ; when w <= 1.0 then Apreutesey A. Y., Korolkova A. V., Kulyabov D. S. 7 Figure 1. The packet drop function in the DSRED algorithm Figure 2. The packet drop function in the GRED algorithm reinit ( w, 1.0) ; end when ; when q >= R then reinit ( q, R ) ; end when ; The packet drop function 𝑝(ˆ𝑞 ), which distinguishes the DSRED algorithm from the classic RED, is described in Modelica as follows (listing 2). Listing 2: The packet drop function in the DSRED algorithm p = if q_avg < thmin * R then 0.0 8 ITTMM—2019 elseif q_avg >= thmin * R and q_avg < thmid * R then alfa * ( q_avg - thmin * R ) elseif q_avg >= thmid * R and q_avg < thmax * R then 1 - gamma + betta * ( q_avg - thmin * R ) else 1.0; The following is a listing fragment describing the growth of a TCP window (listing 3). Listing 3: The growth of a TCP window function wAdd input Real wIn ; input Real wmax ; input Real T ; output Real wOut ; algorithm wOut := if noEvent ( wIn > wmax ) then 0 else 1 / T ; end wAdd ; To change the instantaneous queue length, set the appropriate function (listing 4). Listing 4: Change of the queue length function qAdd input Real q, w, T, C, N, R ; output Real qOut ; protected Real q1, q2 ; algorithm q1 := N * w / T - C ; q2 := q + q1 ; qOut := if ( q2 > R ) then R - q elseif ( q2 > 0) then q1 ˓→ else - q ; end qAdd ; The following variables act as initial parameters of the system: – 𝑡ℎ𝑚𝑖𝑛 is the normalized lower queue threshold; – 𝑡ℎ𝑚𝑎𝑥 is the normalized high queue threshold; – 𝑝𝑚𝑎𝑥 is the maximum probability of dropping packets. As a result of the simulation, the graphs demonstrating the improvement in the behavior of the function of the average queue size 𝑞(𝑡) in the DSRED algorithm compared to RED with some parameters were obtained. Figure 3 shows that with the initial parameters 𝛾 = 0, 8, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 2, when using the DSRED algorithm, the amplitude and frequency of the oscillations of the average queue size decreased slightly, which has a positive effect on the behavior of the system. With initial parameters 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 01, i.e. as the maximum probability of dropping packets 𝑝𝑚𝑎𝑥 decreases, the amplitude of the oscillations of the queue length function in the DSRED algorithm is also slightly less than when using the classic RED, in which the function 𝑞(𝑡) reaches its maximum value (fig. 4). However, the frequency of oscillation of the average queue size function in DSRED increases, comparing with this function in RED(fig. 4). The simulation results(fig. 5) also show that with 𝛾 = 0, 8, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 9, 𝑝𝑚𝑎𝑥 = 0, 01 parameters using the DSRED algorithm, the amplitude of fluctuations of the average queue size decreases slightly, and the frequency increases. When the lower threshold of the queue rises, i.e. with an increase in the length of the queue on which the packet drop function operates, it can be seen that the queue function 𝑞(𝑡) in the classical RED process in the oscillation process reaches its maximum value and is held at this level for some time. When using DSRED, the Apreutesey A. Y., Korolkova A. V., Kulyabov D. S. 9 Figure 3. The average queue size function 𝑞(𝑡) in DSRED and RED algorithms, 𝛾 = 0, 8, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 2 Figure 4. The average queue size function 𝑞(𝑡) in DSRED and RED algorithms, 𝛾 = 0, 8, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 01 function 𝑞(𝑡) does not reach the maximum possible value(fig. 5), which indicates a more stable behavior of the system parameters. 10 ITTMM—2019 Figure 5. The average queue size function 𝑞(𝑡) in DSRED and RED algorithms, 𝛾 = 0, 8, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 9, 𝑝𝑚𝑎𝑥 = 0, 01 3. Simulation of the GRED algorithm In the Gentle RED algorithm (GRED) [9, 15], the packet drop function 𝑝(ˆ 𝑞 ) is ⎧0, 𝑞ˆ < 𝑞𝑚𝑖𝑛 , ⎪ ⎪ 𝑞ˆ − 𝑞𝑚𝑖𝑛 ⎪ ⎪ 𝑝𝑚𝑎𝑥 , 𝑞𝑚𝑖𝑛 ≤ 𝑞ˆ < 𝑞𝑚𝑎𝑥 , ⎪ ⎪ ⎪ ⎨𝑞 −𝑞 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑝(ˆ 𝑞) = (2) ⎪ 𝑞ˆ − 𝑞𝑚𝑎𝑥 ⎪ ⎪ (1 − 𝑝𝑚𝑎𝑥 ) + 𝑝𝑚𝑎𝑥 , 𝑞𝑚𝑎𝑥 ≤ 𝑞ˆ < 2𝑞𝑚𝑎𝑥 , 𝑞𝑚𝑎𝑥 ⎪ ⎪ ⎪ ⎪ ⎩ 1, 𝑞ˆ > 2𝑞𝑚𝑎𝑥 . In the GRED algorithm the RED standard drop function is in the working range from 𝑞𝑚𝑖𝑛 to 𝑞𝑚𝑎𝑥 . The additional segment is necessary to provide smoother behavior of the reset function outside the operating range (fig. 2). The program fragment presented below (listing 5) is written in Modelica and describes the behavior of the packet drop function 𝑝(ˆ𝑞 ) (2). Listing 5: The packet drop function in the GRED algorithm p = if q_avg < thmin * R then 0.0 elseif q_avg >= thmin * R and q_avg < thmax * R then ( ( q_avg - thmin * R ) * pmax ) / ( thmax * R - thmin * R ) elseif q_avg >= thmax * R and q_avg < 2 * thmax * R then ( ( q_avg - thmax * R ) * ( 1 - pmax ) ) / ( thmax * R ) + pmax else 1.0; The variables 𝑡ℎ𝑚𝑖𝑛 , 𝑡ℎ𝑚𝑎𝑥 , 𝑝𝑚𝑎𝑥 are variable initial system parameters. When 𝑝𝑚𝑎𝑥 > 0, 9, differences in the behavior of systems operating on RED and GRED are practically not observed. The simulation results with the parameters 𝑡ℎ𝑚𝑖𝑛 = 0, 25, Apreutesey A. Y., Korolkova A. V., Kulyabov D. S. 11 Figure 6. The average queue size function 𝑞(𝑡) in GRED and RED algorithms, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 01 Figure 7. The TCP window size function 𝑤(𝑡) in GRED and RED algorithms, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 01 𝑡ℎ𝑚𝑎𝑥 = 0, 6, 𝑝𝑚𝑎𝑥 = 0, 01 (fig. 6) reflect that the amplitude of the average queue 𝑞(𝑡) size with the GRED remained almost unchanged compared to the RED, and the oscillation frequency increased. Figure 7 shows the change in the average size of the TCP window. When using the GRED, the system behaves more stable, since the oscillations of the 𝑤(𝑡) in GRED do not reach zero, unlike the system according to RED. When increasing the length of the queue on which the packet drop function operates, for example with 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 9, 𝑝𝑚𝑎𝑥 = 0, 01 parameters, it can be seen that the 𝑞(𝑡) function does not reach zero when using GRED, i.e. the amplitude of oscillation is slightly smaller compared with the same function in the RED (fig. 8). A more vivid 12 ITTMM—2019 Figure 8. The average queue size function 𝑞(𝑡) in GRED and RED algorithms, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 9, 𝑝𝑚𝑎𝑥 = 0, 01 Figure 9. The TCP window size function 𝑤(𝑡) in GRED and RED algorithms, 𝑡ℎ𝑚𝑖𝑛 = 0, 25, 𝑡ℎ𝑚𝑎𝑥 = 0, 9, 𝑝𝑚𝑎𝑥 = 0, 01 example of reducing the amplitude of oscillations in a system operating on the GRED is shown in the figure 9, which shows the 𝑤(𝑡) function. The average size of a TCP window in the GRED ranges from 8, 7 to 17, 5 packets; in the classic RED, the 𝑤(𝑡) function ranges from 0, 13 to 19, 4, demonstrating the advantages of the GRED algorithm with these initial parameters. Apreutesey A. Y., Korolkova A. V., Kulyabov D. S. 13 4. Conclusions In this paper, the principles of the operation of such RED algorithm modifications , such as DSRED and GRED, were described, mathematical models of these algorithms were given, and the systems controled by these algorithms were simulated using the Modelica language in the OpenModelica. During the simulation, the results were obtained demonstrating that under some initial parameters the amplitude or frequency of oscillations of the average queue size can be reduced. The systems operating on DSRED and GRED, mainly showed a slight decrease in the amplitude of the oscillation parameters 𝑞(𝑡) or 𝑤(𝑡), which indicates a positive effect on the system behavior, however the oscillation frequency in most cases increased. By increasing the length of the queue on which the packet drop function operates, the DSRED algorithm made the behavior of the 𝑞(𝑡) function more stable, reducing its amplitude. In the GRED system, the behavior of the function of the average queue size changed slightly, however, the 𝑤(𝑡) function graphs showed a more stable behavior of the system than at lower maximum threshold values of the queue. Acknowledgments The publication has been prepared with the support of the “RUDN University Program 5-100” (Anna-Maria Y. Apreutesey, Anna V. Korolkova, calculation model development and algorithms on Modelica language). The reported study was funded by Russian Foundation for Basic Research (RFBR), project number 19-01-00645 (Dmitry S. Kulyabov, research algorithm development). References 1. L. Chrost, A. Chydzinski, On the Evaluation of the Active Queue Management Mechanisms, 2009 First International Conference on Evolving Internet (2009) 113– 118doi:10.1109/INTERNET.2009.25. 2. R. Adams, Active Queue Management: A Survey, IEEE Communications Surveys & Tutorials 15 (3) (2013) 1425–1476. doi:10.1109/SURV.2012.082212.00018. 3. C. V. V. Hollot, V. Misra, D. Towsley, Wei-Bo Gong, On Designing Improved Con- trollers for AQM Routers Supporting TCP Flows, in: Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213), Vol. 3, IEEE, 2001, pp. 1726–1734. doi:10.1109/INFCOM.2001.916670. 4. S. Floyd, V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking 1 (4) (1993) 397–413. doi:10.1109/90. 251892. 5. V. Jacobson, Congestion Avoidance and Control, ACM SIGCOMM Computer Communication Review 18 (4) (1988) 314–329. arXiv:arXiv:1011.1669v3, doi: 10.1145/52325.52356. 6. V. Misra, W.-B. Gong, D. Towsley, Stochastic Differential Equation Modeling and Analysis of TCP-Windowsize Behavior, Proceedings of PERFORMANCE 99 (1999). 7. V. Misra, W.-B. Gong, D. Towsley, Fluid-Based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED, ACM SIGCOMM Computer Communication Review 30 (4) (2000) 151–160. doi:10.1145/347057. 347421. 8. A. V. Korolkova, D. S. Kulyabov, A. I. Chernoivanov, On the Classification of RED Algorithms, Bulletin of Peoples’ Friendship University of Russia. Series “Mathematics. Information Sciences. Physics” (3) (2009) 34–46. 9. A. V. Korolkova, D. S. Kulyabov, Mathematical Model of the Dynamic Behavior of RED-Like System Parameters, Bulletin of Peoples’ Friendship University of Russia. Series “Mathematics. Information Sciences. Physics” (1) (2010) 54–64. 14 ITTMM—2019 10. P. Fritzson, Principles of Object-Oriented Modeling and Simulation with Modelica 2.1, Wiley-IEEE Press, 2003. 11. P. Fritzson, Introduction to Modeling and Simulation of Technical and Physical Systems with Modelica, John Wiley & Sons, Inc., Hoboken, NJ, USA, 2011. doi: 10.1002/9781118094259. 12. A. V. Korolkova, T. R. Velieva, P. O. Abaev, L. A. Sevastianov, D. S. Kulyabov, Hybrid Simulation Of Active Traffic Management, Proceedings 30th European Conference on Modelling and Simulation (2016) 685–691doi:10.7148/2016-0685. 13. T. R. Velieva, E. G. Eferina, A. V. Korolkova, D. S. Kulyabov, L. A. Sevastianov, Modelica-based TCP simulation, Journal of Physics: Conference Series 788 (100) (2017) 012036.1–7. doi:10.1088/1742-6596/788/1/012036. 14. B. Zheng, M. Atiquzzaman, DSRED: A New Queue Management Scheme for the Next Generation Internet, IEICE Transactions on Communications E89-B (3) (2006) 764–774. doi:10.1093/ietcom/e89-b.3.764. 15. G. Iannaccone, M. May, C. Diot, Aggregate traffic performance with active queue management and drop from tail, ACM SIGCOMM Computer Communication Review 31 (3) (2001) 4. doi:10.1145/505659.505661.