Modeling RED algorithm modifications in the OpenModelica

Abstract

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

Keywords

• and phrases
• active queue management
• simulation
• hybrid modeling
• Modelica

-

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 ⎧ ⎪⎪0, ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩1, =

1. Introduction

There are many algorithm [8, 9]. 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.

modifications of RED that improve certain characteristics of this

As a modeling tool is proposed to use the language Modelica in the software environment 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

thresholds of the queue, = 0, 5( − ).

The algorithm Double Slope Random Early Detection (DSRED) [ 9, 14 ] introduces an additional threshold value between the minimum and maximum The probability function for dropping packets in the DSRED algorithm is: 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 coeficient 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).

der ( q_avg ) = wq * C * ( q - q_avg ) ; when w <= 1.0 then

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 then elseif then else 1.0; elseif q_avg >= thmin * R and q_avg < thmid * R alfa * ( q_avg

- thmin * R) q_avg >= thmid * R and

q_avg < thmax * R – ℎ 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. 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 function () does not reach the maximum possible value(fig. 5), which indicates a more stable behavior of the system parameters.

3. Simulation of the GRED algorithm

In the Gentle RED algorithm (GRED) [ 9, 15 ], the packet drop function (^) is

The variables ℎ, ℎ, are variable initial system parameters. When > 0, 9, diferences in the behavior of systems operating on RED and GRED are practically not observed. The simulation results with the parameters ℎ = 0, 25, ℎ = 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 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.

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 efect 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 Controllers 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 Diferential 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 .

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 Trafic 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 trafic performance with active queue management and drop from tail , ACM SIGCOMM Computer Communication Review 31 ( 3 ) ( 2001 ) 4 . doi: 10 .1145/505659.505661.