modeling the RED active queue management algorithms: Modelica vs. Julia

Abstract

This work is devoted to the study of the capabilities of the Modelica and Julia programming languages for the implementation of a continuously discrete paradigm in modeling hybrid systems that contain both continuous and discrete aspects of behavior. A system consisting of an incoming stream that is processed according to the Transmission Control Protocol (TCP) and a router that processes trafic using the Random Early Detection (RED) algorithm acts as a simulated threshold system.

Keywords

• active queue management
• simulation
• Modelica
• Julia
• Random Early Detection

1. Introduction

The possible methods for investigating complex systems are the construction of a discrete event model, the construction of a continuous model, and hybrid modeling [ 1 ]. Such hybrid systems combine the operation of continuous and discrete elements, for example, systems with a discrete control device and a control object with a continuous nature of operation [ 2 ]. The system for the further research is the hybrid model of the interaction of the data transmission process via the Transmission Control Protocol (TCP) and the Random Early Detection (RED) algorithm as an algorithm of regulating the flow state. When modeling TCP-like trafic, the liquid (continuous) approach can be used, but it is especially important to consider discrete transitions between TCP states and a discrete packet drop function in RED-type algorithms. It is the hybrid approach that reflects these important features of the simulated system. LGOBE (D. S. Kulyabov) (D. S. Kulyabov) Workshop on information technology and scientific computing in the framework of the X International Conference https://yamadharma.github.io/ (D. S. Kulyabov) © 2020 Copyright for this paper by its authors.

CEUR

CEUR Workshop Proceedings (CEUR-WS.org)

1.1. The structure of the article

The structure of the article is as following. The 2 section describes the basic principles and the mathematical model of the operation of the congestion control mechanism in the TCP protocol with the RED queue management algorithm. The 3 section provides general information about the physical modeling language Modelica which implements, among other things, a hybrid paradigm, and this section also presents the implementation of the algorithm in the Modelica language. The 4 section provides information on the Julia programming language and the DiferentialEquations package for solving various diferential equations. Also in this section some features of the Julia language are presented in the context of hybrid modeling by using the example of the RED module implementation for active trafic management.

1.2. Notations and conventions

In the work we will use the following variables and notation. The main parameters of the system are follows: • () is the average TCP window size (in packets); • () is the average queue length (in packets); • (̂) is the exponentially weighted moving average of the queue length; • (, ) is the Round Trip Time (RTT, sec); • () is the number of TCP sessions; • corresponds to the speed of procession of packets in the queue.

2. Random Early Detection as an active queue managment algorithm

The authors have repeatedly described the research problems, the features of the phenomenon under study, the construction of a mathematical model [ 3, 4 ].

In data transmission networks, there is a global synchronization, during which TCP sources send packets synchronously and also stop transmission synchronously. Such a stable selfoscillating mode of the system operation afects the quality of network service, throughput and latency negatively. The use of Active Queue Management algorithms, like RED [ 5 ], to control trafic reduces the probability of global synchronization, but it does not completely eliminate it. For some values of the initial parameters in the router settings, self-oscillations of the main parameters occur in the system.

An active queue management policy with a RED type algorithm is used to control and prevent congestions in the queues of routers. Algorithms for managing the state of trafic can be represented as control modules in network equipment. The advantage of this algorithm is its eficiency and relatively simple implementation on network equipment.

Let us describe a model for transmitting TCP-like trafic in which the dynamic flow rate is regulated by an RED type algorithm. The model consists of two elements - the packet-generating TCP source and the receiver, which is the queue of the router. It processes incoming packets in accordance with the control algorithm and notifies the source that the packets have reached their

destination. The source and receiver interact through an intermediate link in accordance with the control algorithm, i.e. the value of the average queue length afects the source parameters, in particular, the size of the TCP congestion window.

A mathematical model of the interaction of an incoming TCP stream and a router that processes trafic using a RED-type control algorithm is the autonomous system of three diferential equations [ 6, 7, 8, 9 ]: ( )̇ = (̇) =

1 ()

( max − ) − ⎧(1 − ()) ⎪ ⎨ ⎪max [(1 − ()) ⎩ () () ()

− , () ()

() (̂)̇ = − (̂) + (), () ( − ()) 2 ( − ()) ( − ()), () > 0, − , 0 ] , () = 0,

The (1) equation describes the dynamic change of the average TCP window size. The 1/ (, )

element reflects the slow start TCP state, during which the window size increases per RTT. The ( max − ) component, which is a Heaviside function, limits the growth of the TCP window. The (1 − ()) () ()/ (, ) component in the (2) equation reflects the increase in the queue length when packets arrive which corresponds to the average packet arrival rate.

The (3) equation reflects the change of the (̂) — exponentially weighted moving average of the queue length function operating as a low-pass filter. It is introduced for some smoothing outliers of the queue length. As soon as the (̂) value exceeds some predetermined threshold value, the router finds out that the system has started overloading and reports this to the source.

The RED algorithm is controlled by the ( )̂ — piecewise probabilistic packet drop function which can be written as a system of nonlinear equations.

( )̂ =

This function depends on the threshold values of the queue size min and max, as well as the max parameter that sets the part of packets that will be discarded if ̂ reaches the maximum value.

3. Modeling in the Modelica language

The Modelica language was developed by the non-profit organization Modelica which also develops a freely distributed library based on it. This object-oriented language of physical modeling is used to solve a wide range of problems [ 10, 11 ]. Modelica is well suited for component-oriented modeling of complex systems consisting of various physical components, also having control (1) (2) (3) (4) components and elements oriented to individual processes. Let us demonstrate the application of this language to hybrid modeling of communication network algorithms [ 2 ].

The basis of the language is represented by classes that can be inherited. In Modelica classes contain methods and fields that can have types of variability such as constant, parameter and variable. In addition to methods and fields, the class contains functions and equations which are defined in the e q u a t i o n section. One of the mandatory requirements of the Modelica program is the coincident number of variables and equations.

Let us declare the variables and parameters used as initial ones.

R e a l p ( s t a r t = 0 . 0 ) ” D r o p p r o b a b i l i t y ” ; R e a l w ( m i n = 1 . 0 , m a x = w m a x , s t a r t = 1 . 0 , f i x e d = t r u e ) ” T C P w i n d o w ” ; R e a l q ( m a x = R , s t a r t = 0 . 0 , f i x e d = t r u e ) ” I n s t a n t q u e u e l e n g t h ” ; R e a l q _ a v g ( s t a r t = 0 . 0 ) ” E W M S q u e u e l e n g t h ” ;

The congestion control algorithm in the queues of the RED router in Modelica is implemented as a R e d class [ 12 ]. A discrete drop function is easily set in the main class using the standard i f operator: c l a s s R e d e q u a t i o n p = i f q _ a v g < t h m i n * R

t h e n 0 . 0 e l s e i f q _ a v g > t h m a x * R

t h e n 1 . 0 e l s e ( q _ a v g / R - t h m i n ) * p m a x / ( t h m a x - t h m i n ) ;

In this implementation, the discrete element of the system interacts well with continuous elements, the behaviour of which is also implemented in the main class of the program using three equations: e q u a t i o n d e r ( w ) = w A d d ( w , w m a x , T ) + ( - 0 . 5 ) * w * d e l a y ( w , T , T ) * d e l a y ( p , T , T ) / d e l a y ( T , T , T ) ; d e r ( q ) = q A d d ( p r e ( q ) , w , T , C , N , R ) ; d e r ( q _ a v g ) = w q * C * ( q - q _ a v g ) ;

In Modelica the d e r operator defines a time derivative. The delay is realized very simply with the help of the d e l a y operator, which makes it possible to work with the delay of both continuous and discrete system elements. The w A d d function limits the size of the TCP window:

f u n c t i o n w A d d i n p u t R e a l w I n , w m a x , T ; o u t p u t R e a l w O u t ; a l g o r i t h m w O u t : = i f n o E v e n t ( w I n > = w m a x ) t h e n 0 . 0 e l s e 1 . 0 / T ; e n d w A d d ;

The q A d d function sets the change in the average queue length depending on the discrete packet drop function: f u n c t i o n q A d d i n p u t R e a l q , w , T , C , N , R ; o u t p u t R e a l q O u t ; p r o t e c t e d R e a l q 1 , q 2 ; a l g o r i t h m q 1 : = N * w / T - C ; q 2 : = q + q 1 ; q O u t : = i f q 2 > R t h e n R - q e l s e i f q 2 > 0 . 0 t h e n q 1 e l s e - q ; e n d q A d d ;

Additional restrictions on the size of () and () variables are set using the w h e n operator in the R e d class: w h e n w < = 1 . 0

t h e n r e i n i t ( w , 1 . 0 ) ; e n d w h e n ; w h e n q > = R

t h e n r e i n i t ( q , R ) ; e n d w h e n ;

As a result of system modeling the dynamics of the change in () , () , (̂) parameters was obtained, presented in Figure 1. The graph shows that for some parameter values in the system there is a stable self-oscillating mode of operation.

4. Modeling in the Julia language

Julia is a high-level language designed for scientific and engineering calculations [ 2, 13, 14, 15 ].

Let us describe the implementation of an Active Queue Management algorithm with a RED control algorithm in Julia1.

1We used the Julia-1.4.1.

In this implementation, we used the DiferentialEquations package [ 16], designed for efective solution of diferential equations of various types, such as ordinary diferential equations, stochastic ordinary diferential equations, diferential algebraic and hybrid equations, as well as delay diferential equations.

To install the package we will use the following command in Julia REPL:

u s i n g P k g P k g . a d d ( ” D i f f e r e n t i a l E q u a t i o n s ” )

We will enable the package using the command:

u s i n g D i f f e r e n t i a l E q u a t i o n s

We set the vector of the initial system parameters p = ( T , N , C , w q , q _ m i n , q _ m a x , R , p _ m a x , w _ m a x ) . The p r variable which is a function of the packet drop probability, acts as a global variable. T = 0 . 5 N = 6 0 . 0 C = 1 0 * 1 0 0 0 0 0 0 . 0 / ( 8 . 0 * 5 0 0 ) w q = 0 . 0 0 0 4 q _ m i n = 0 . 2 5 q _ m a x = 0 . 5 0 R = 3 0 0 . 0 p _ m a x = 0 . 1 w _ m a x = 3 2 . 0 p = ( T , N , C , w q , q _ m i n , q _ m a x ,

R , p _ m a x , w _ m a x ) p r = 0 . 0

Since the original system of diferential equations contains delayed arguments, we define the

history function h ( p , t ) which depends on the parameters vector p and time t . Next, we define the delay of the ( − ()) variable in (1) equation: h ( p , t ) = z e r o s ( 1 ) t a u = T l a g s = [ t a u ]

For our task, the R e d dynamic function describing the behaviour of diferential equations and setting constraints for , , (̂) parameters in DiferentialEquations will have the following form:

In the R e d function, we also set constraints for the , , (̂) parameters. e n d f u n c t i o n q A d d ( q , w , T , C , N , R ) q 1 = N * w / T - C q 2 = q + q 1 i f q 2 > R

r e t u r n R - q e l s e i f q 2 > 0 r e t u r n q 1 r e t u r n - q e n d e l s e e n d

Next we define the parameter change function.

One of the powerful tools of the DiferentialEquations package is callbacks, for which two

functions are defined. A condition function is needed to check if an event has occurred. The afect function is executed if an event has occurred.

The discrete packet drop function is implemented as a controller which is updated every 0.01 seconds until the t f simulation time is reached. The t s t o p s array defines the sampling intervals of the condition check, the function checks if t is one of the sample element. t f = 3 0 . 0 t s t o p s = c o l l e c t ( 0 : 0 . 0 1 : t f ) f u n c t i o n c o n d i t i o n _ c o n t r o l _ l o o p ( u , t , i n t e g r a t o r )

( t i n t s t o p s ) e n d

Next, we determine the afect function, which is the controller. The c o n t r o l _ l o o p ! function at each step calculates the new value of the packet drop probability function depending on the current values of the , , (̂) parameters in accordance with the formula (4). f u n c t i o n c o n t r o l _ l o o p ! ( i n t e g r a t o r ) g l o b a l p r w = i n t e g r a t o r . u [ 1 ] q = i n t e g r a t o r . u [ 2 ] q _ a v g = i n t e g r a t o r . u [ 3 ] i f ( q _ a v g < q _ m i n * R )

p r = 0 . 0 e l s e i f ( q _ a v g > q _ m a x * R )

p r = 1 . 0 e l s e p r = p _ m a x * ( q _ a v g / R - q _ m i n ) / ( q _ m a x - q _ m i n ) e n d e n d

Then we define a discrete type callback:

c b = D i s c r e t e C a l l b a c k ( c o n d i t i o n _ c o n t r o l _ l o o p , c o n t r o l _ l o o p ! )

Finally, we define the vector of the system initial state, the simulation time and call the DDEProblem package solver. The R e d function, vector of initial states, simulation time, and variables delay parameters are passed to its arguments:

u 0 = [ 1 . 0 , 0 . 0 , 0 . 0 ] t s p a n = ( 0 . 0 , t f ) p r o b = D D E P r o b l e m ( R e d , u 0 , h , t s p a n , p , c o n s t a n t _ l a g s = l a g s ) a l g = M e t h o d O f S t e p s ( T s i t 5 ( ) ) s o l = s o l v e ( p r o b , a l g , c a l l b a c k = c b , t s t o p s = t s t o p s )

As a result of the simulation, we obtain a graph demonstrating the behaviour of the TCP Reno window size and the average queue length, i.e. reflecting the dynamics of a queue in a router (or gateway) with a queue management module using the RED algorithm (Figure 2).

5. Results

As a result of the study, two software complexes created in the programming languages Modelica and Julia were obtained. Both of these complexes implement the same mathematical model of a data transmission network with an active trafic control module operating according to the RED algorithm. A numerical experiment conducted within the framework of both software systems gives comparable results (see Figure 1 and Figure 2).

6. Discussion

Modelica and Julia languages are both domain-specific languages. However, Julia is considered as the common language of scientific calculations, Modelica is considered as a specialized language for modeling of dynamic, continuous and hybrid systems.

The mathematical model of the RED algorithm is formulated using a hybrid approach. Therefore, in the framework of the Modelica language, its implementation turned out to be quite simple. In this language ordinary diferential equations are written with a delayed argument with the help of high-level tools quite easily. In addition, the use of discrete elements is implemented very clearly.

Julia language is aimed at solving a wider range of tasks. Therefore, it does not have as many syntax tools as the more specialized Modelica. In particular, the implementation of the hybrid paradigm in Julia requires a higher qualification of the programmer than when working with the Modelica language.

For specialized applications, Julia requires a greater level of knowledge than specialized languages such as Modelica. Julia is also a metalanguage and it can serve as the basis for the construction of other languages. For example, the Modia extension [ 17, 18 ] was made to migrate programs from Modelica to Julia (and possibly in the opposite direction).

7. Conclusion

The authors demonstrated the application of the continuous-discrete approach to the modeling of non-linear systems with control. The simulated system is the system consisting of an incoming stream processed according to the TCP protocol, as well as a router that processes trafic using a RED algorithm.

By comparing software implementations in the Modelica and Julia programming languages,

the simplicity of hybrid systems modeling in Modelica is demonstrated, where continuous system elements, implemented by using a system of diferential equations, interact with a discrete packet drop function quite well. Restrictions for some system parameters are set using the w h e n operator. Implementation of the delay is also possible for system elements of any nature of functioning.

Julia also provides the ability to model systems according to a hybrid paradigm. The DifferentialEquations package allows to solve systems of diferential equations of various kinds, including delay diferential equations. The continuous probabilistic function has been successfully implemented using the callback option. A delayed argument to a continuous function is implemented using the h ( p , t ) history function.

Thus, the authors studied the capabilities of the Modelica and Julia programming languages in modeling of hybrid systems containing both continuous and discrete aspects of behaviour. The numerical simulation of the process of transmitting data via TCP and the process of regulating the flow state using the RED algorithm in the event of congestion has been performed, graphs demonstrating changes in the main parameters of the system have been obtained.

Acknowledgments

The reported study was funded by Russian Foundation for Basic Research (RFBR) according to the research project No 19-01-00645 (Dmitry S. Kulyabov and Anna V. Korolkova, mathematical model development). The publication has been prepared with the support of the “RUDN

University Program 5-100” (Anna Maria Yu. Apreutesey, program development).

References

[1] A. V. Korolkova , T. R. Velieva , P. A. Abaev , L. A. Sevastianov , D. S. Kulyabov , Hybrid Simulation Of Active Trafic Management, Proceedings 30th European Conference on Modelling and Simulation ( 2016 ) 685 - 691 . doi:1 0 . 7 1 4 8 / 2 0 1 6 - 0 6 8 5 .

[2] D. Färnqvist , K. Strandemar , K. H. Johansson , J. P. Hespanha , Hybrid Modeling of Communication Networks Using Modelica , in: The 2nd International Modelica Conference , 2002 , pp. 209 - 213 .

[3] A. V. Korolkova , D. S. Kulyabov , T. R. Velieva , I. S. Zaryadov , Essay on the study of the selfoscillating regime in the control system , in: M. Iacono , F. Palmieri , M. Gribaudo , M. Ficco (Eds.), 33 European Conference on Modelling and Simulation, ECMS 2019 , volume 33 of Communications of the ECMS, European Council for Modelling and Simulation , Caserta, 2019 , pp. 473 - 480 . doi:1 0 . 7 1 4 8 / 2 0 1 9 - 0 4 7 3 .

[4] D. S. Kulyabov , A. V. Korolkova , T. R. Velieva , E. G. Eferina , L. A. Sevastianov , The Methodology of Studying of Active Trafic Management Module Self-oscillation Regime , in: W. Zamojski, J. Mazurkiewicz , J. Sugier , T. Walkowiak , J. Kacprzyk (Eds.), DepCoSRELCOMEX 2017. Advances in Intelligent Systems and Computing , volume 582 of Advances in Intelligent Systems and Computing , Springer International Publishing, Cham, 2018 , pp. 215 - 224 . doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 3 1 9 - 5 9 4 1 5 - 6 _ 2 1 .

[5] S. Floyd , V. Jacobson , Random Early Detection Gateways for Congestion Avoidance , IEEE/ACM Transactions on Networking 1 ( 1993 ) 397 - 413 . doi:1 0 . 1 1 0 9 / 9 0 . 2 5 1 8 9 2 .

[6] 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 ( 2000 ) 151 - 160 . doi:1 0 . 1 1 4 5 / 3 4 7 0 5 7 . 3 4 7 4 2 1 .

[7] V. Misra , W.-B. Gong , D. Towsley , Stochastic Diferential Equation Modeling and Analysis of TCP-Windowsize Behavior , Proceedings of PERFORMANCE 99 ( 1999 ).

[8] A. V. Korolkova , D. S. Kulyabov , L. A. Sevastianov , Combinatorial and Operator Approaches to RED Modeling, Mathematical Modelling and Geometry 3 ( 2015 ) 1 - 18 .

[9] M. Hnatič , E. G. Eferina , A. V. Korolkova , D. S. Kulyabov , L. A. Sevastyanov , Operator Approach to the Master Equation for the One-Step Process , EPJ Web of Conferences 108 ( 2016 ) 02027 . doi:1 0 . 1 0 5 1 / e p j c o n f / 2 0 1 6 1 0 8 0 2 0 2 7 . a r X i v : 1 6 0 3 . 0 2 2 0 5 .

[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:1 0 . 1 0 0 2 / 9 7 8 1 1 1 8 0 9 4 2 5 9 .

[12] A.-M. Y. Apreutesey , A. V. Korolkova , D. S. Kulyabov , Modeling RED algorithm modiifcations in the OpenModelica , in: D. S. Kulyabov, K. E. Samouylov , L. A. Sevastianov (Eds.), Proceedings of the Selected Papers of the 9th International Conference ”Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems” (ITTMM-2019) , Moscow, Russia, April 15-19 , 2019 , volume 2407 of CEUR Workshop Proceedings , Moscow, 2019 , pp. 5 - 14 .

[13] J. Bezanson , S. Karpinski , V. B. Shah , A. Edelman , Julia: A Fast Dynamic Language for Technical Computing ( 2012 ) 1 - 27 . a r X i v : 1 2 0 9 . 5 1 4 5 .

[14] J. Bezanson , A. Edelman , S. Karpinski , V. B. Shah , Julia: A fresh approach to numerical computing , SIAM Review 59 ( 2017 ) 65 - 98 . doi:1 0 . 1 1 3 7 / 1 4 1 0 0 0 6 7 1 . a r X i v : 1 4 1 1 . 1 6 0 7 .

[15] A. Joshi , R. Lakhanpal , Learning Julia, Packt Publishing, 2017 .

[16] C. Rackauckas , Q. Nie , DiferentialEquations.jl - A Performant and Feature-Rich Ecosystem for Solving Diferential Equations in Julia , Journal of Open Research Software 5 ( 2017 ). doi:1 0 . 5 3 3 4 / j o r s . 1 5 1 .

[17] H. Elmqvist , T. Henningsson , M. Otter , Systems Modeling and Programming in a Unified Environment Based on Julia , in: T. Margaria , B. Stefen (Eds.), Leveraging Applications of Formal Methods , Verification and Validation: Discussion, Dissemination, Applications. ISoLA 2016 , volume 9953 of Lecture Notes in Computer Science, Springer, Cham, 2016 , pp. 198 - 217 . doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 3 1 9 - 4 7 1 6 9 - 3 _ 1 5 .

[18] M. Otter , H. Elmqvist , Transformation of Diferential Algebraic Array Equations to Index One Form , in: Proceedings of the 12th International Modelica Conference , Prague, Czech Republic, May 15 -17, 2017 , volume 132 , 2017 , pp. 565 - 579 . doi:1 0 . 3 3 8 4 / e c p 1 7 1 3 2 5 6 5 .