The purpose of this work is to study the capabilities of the Julia language for numerical modeling of stochastic systems. As a stochastic system we consider the model of interaction between the process of data transmission via the Transmission Control Protocol (TCP) and the process of regulating the flow state using the Random Early Detection (RED) algorithm. The mathematical model of this interaction is a system of stochastic diferential equations, where there are both continuous and discrete elements of the model. When simulating such systems, it is important to consider the properties of continuous parameters, such as queue length of a router and the TCP window size, as well as discrete transitions between TCP states and the probabilistic packet drop function. Such hybrid systems can be quite easily implemented in specialized dynamic systems modeling languages, for example in Modelica. However, this software package does not have built-in universal tools for modeling stochastic systems, where it is important to consider the random nature of the behavior. The aim of this work is to find optimal tools for modeling such stochastic systems using the Julia language which in used for scientific calculations. For modeling the RED algorithm, the DiferentialEquations.jl library is used. This tool of the Julia language allows solving various kinds of diferential equations, including stochastic diferential equations and delay diferential equations. As a result of the simulation graphs were obtained that demonstrate the dynamics of changes of the TCP window size and the queue length, depending on the initial model parameters and queue threshold values, the correct selection of which ensures the stable operation of the system.
LGOBE (D. S. Kulyabov)
Active Queue Management techniques have been proposed to both alleviate some congestion
control problems for IP networks as well as provide the quality of service. RED controlled
systems [
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
analysis of such algorithms are important for understanding systems dynamics which depends
on the initial settings of the routers. The studies of various models of the trafic transmission
process are urgent tasks, since they allow to evaluate the network weaknesses and trafic losses.
The mathematical model for the interaction of an incoming TCP stream and a router that
processes trafic using a RED control algorithm can be represented as a system of stochastic
diferential equations. Such hybrid system [
Consider the process of transmitting TCP-like trafic controlled by the RED algorithm. A continuous state vector is ( , , )̂ , where ∶= () — average TCP window size (in packets), ∶= () — average queue length (in packets), ∶̂= (̂) — exponentially weighted moving average of the queue length.
The stochastic model is a system of three Ito stochastic diferential equations [
1 + √ () 2() ( )̂ 2 ()
d 1 , () () ⎨d() = ( ⎪ ⎪ ⎩d(̂) = () (() − (̂) ).
() − () ) d +
() √ () () − () d 2 , • () is the Round Trip Time (RTT). It is the time taken for a packet to be sent from a source to a destination and for the corresponding acknowledgement to be received by the source, assuming no packet loss; () — speed of processing packets in the queue; • () is a number of TCP sessions; • d 1 is the Wiener process corresponding to a random () process; • d 2 is the Wiener process corresponding to a random () process.
As the the average queue length increases, the packets drop probability also increases. The classical example of an AQM policy is RED for which ( )̂ takes the next form: ( )̂ = ⎧0, ⎪ (̂) − min ⎨ max − min ⎪ ⎩1,
0 ⩽ (̂) < min, max, min ⩽ (̂) ⩽ max, (̂) > max.
Here ( )̂ is the package dropping function, (̂) is the queue length weighted average, min and max are thresholds of queue length weighted average, max is the maximum level of packages reset. (1) (2)
Julia is a high-level language for scientific and engineering calculations [
To install the package we will use the following command in Julia REPL: using Pkg Pkg.add("DifferentialEquations")
We will enable the package using the command: using DifferentialEquations T = 0.5 N = 60.0 q_min = 0.25 q_max = 0.50 R = 300.0 p_max = 0.1 w_max = 32.0 p = (T, N, C, wq, q_min, q_max, R, p_max, w_max)
We set the vector of the initial system parameters p = (T, N, C, wq, q_min, q_max, R, p_max, w_max).
After declaring the variables and the vector of the system parameters, in the RED function we define the deterministic part of the ( 1) system of equations: function RED(du, u, param, t) if w < w_max
du[
du[
p = 0.0 elseif (q_avg > q_max * R) p = 1.0 p = p_max * (q_avg / R - q_min) / (q_max - q_min)
The DiferentialEquations.jl package allows you to use callbacks to inject custom code into the solver algorithms to model complex functions with conditions and discontinuities. To work with callbacks, two functions are defined: the condition function checks if an event has occurred, the afect function is executed if the event has occurred.
Let us define the condition function and the afecting function, thereby limiting the growth
of the TCP window size to the maximum value:
function condition_w_max(u,t,integrator)
global w_max
u[
c.u[
end
We also add callbacks to control the growth of the () variable:
function condition_Rq(u,t,integrator)
global R
u[
c.u[
end
function condition_Rq_avg(u,t,integrator)
global R
u[
end function affect_Rq_avg!(integrator) global R for c in full_cache(integrator)
c.u[
In this case, we used several callback functions of the discrete type DiscreteCallback. The condition function implements event detection at each step of solving dt, and each afecting function will be executed if the condition function returns true: save_positions = (true,true) cb_w_max = DiscreteCallback(condition_w_max, affect_w_max!,
save_positions = save_positions) cb_Rq = DiscreteCallback(condition_Rq, affect_Rq!,
save_positions = save_positions) cb_Rq_avg = DiscreteCallback(condition_Rq_avg, affect_Rq_avg!, save_positions = save_positions)
With the CallbackSet() tool, multiple callbacks can be combined into one group: Clbsset = CallbackSet(PositiveDomain(), cb_w_max, cb_Rq, cb_Rq_avg)
Let’s call the SDEProblem solver of the DiferentialEquations.jl package, the arguments of which are passed the RED function that specifies the deterministic part of the equations and the REDst function that specifies the stochastic part of the system. Also, in the arguments to the solver, the vector of the initial states of the system and the simulation time are indicated:
Let’s call the solve method of the DiferentialEquations.jl library to solve the above system of equations. The Euler - Maruyama method is used as a numerical method, which has a strong order ( , ) = (1.0, 0.5.)The value denotes the deterministic accuracy order, the value denotes the stochastic part approximation order. sol = solve(prob_sde_RED, EM(), dt=dt, callback = Clbsset)
Using the parallel computing capabilities of the Julia language, let us simulate a large number of trajectories: ensembleprob = EnsembleProblem(prob_sde_RED) sim = solve(ensembleprob, EM(), dt=dt, callback = Clbsset, trajectories = ↪ 200)
Use the EnsembleSummary() method to combine the modeled set of trajectories. summ = EnsembleSummary(sim, 0:dt:tf)
As a result of the simulation, graphs of changes in the TCP window size and the average queue size in a router with a queue control module according to the RED algorithm were obtained for various initial values of the model. With some initial parameters, the system quickly finds suitable values of variables and changes within the average values (fig. 1–3). In the case of modeling only the deterministic part of the (1) system of equations, the model enters a stationary mode of operation (fig. 2).
(a) (b)
Using active queue management algorithms such as RED for trafic control reduces the
chances of global synchronization occurring, but does not completely eliminate it [
The universal and efective tools of the DiferentialEquations.jl library of the Julia scientific computing language were demonstrated for the numerical simulation of a nonlinear system with control, the mathematical model of which is a system of stochastic diferential equations. The interaction of the process of data transmission via the TCP protocol and the process of the lfow state regulation by the RED algorithm in the event of overloads was considered. The tools of the Julia language used in this work are applicable to modeling such stochastic systems with control, containing elements of both continuous and discrete nature of functioning. As a result of modeling, graphs were obtained that demonstrate changes in the main parameters of the system depending on the threshold values of the queue.
This paper has been supported by the RUDN University Strategic Academic Leadership Program and by Russian Foundation for Basic Research (RFBR) according to the research project No 1901-00645.