=Paper=
{{Paper
|id=Vol-1995/paper-16-980
|storemode=property
|title=
About Linearization of Active Traffic Management Module Model
|pdfUrl=https://ceur-ws.org/Vol-1995/paper-16-980.pdf
|volume=Vol-1995
|authors=Tatiana R. Velieva,Anna V. Korolkova,Dmitry S. Kulyabov
}}
==
About Linearization of Active Traffic Management Module Model
==
https://ceur-ws.org/Vol-1995/paper-16-980.pdf
114
About Linearization of Active Traffic Management Module
Model
Tatiana R. Velieva∗ , 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, Russian Federation
Email: velieva_tr@rudn.university, korolkova_av@rudn.university, kulyabov_ds@rudn.university
The emergence of self-oscillating modes in data-transmission networks negatively affects
characteristics of these networks. As a result the task of identifying zones of self-oscillations’
origin and studying the self-oscillation parameters becomes relevant. The study of the self-
oscillating modes is complicated by the significant nonlinearity of the original system. The
study of self-oscillating modes could simplify the transition to the linearized model; however,
the self-oscillating mode disappears during the linearization. As an alternative, it is proposed
to use an harmonic linearization approach which takes into consideration both the linearized
part of the equations and the nonlinearity that influences them. This paper describes the
preparation for the application of the harmonic linearization method, namely the linearization
of the original nonlinear model.
The work is partially supported by RFBR grants No’s 15-07-08795 and 16-07-00556. Also
the publication was financially supported by the Ministry of Education and Science of the
Russian Federation (the Agreement No 02.A03.21.0008).
1. Introduction
While modeling technical systems with control it is often required to study character-
istics of these systems. Also it is necessary to study the influence of system parameters
on characteristics. In systems with control there is a parasitic phenomenon as self-
oscillating mode. We carried out studies to determine the region of the self-oscillations
emergence. However, the parameters of these oscillations were not investigated. In this
paper, we propose to use the harmonic linearization method for this task. This method
is used in control theory, but this branch of mathematics rarely used in classical mathe-
matical modeling. The authors offer a methodological article in order to introduce this
method to non-specialists.
2. The RED Congestion Adaptive Control Mechanism
To improve the performance of the channel it is necessary to optimize the queue
management at the routers. One of possible approaches is the application of the random
early detection (RED) algorithm (see [1–5]).
The RED algorithm uses a weighted queue length as the factor determining the
probability of packet drop. As the average queue length grows, the probability of
packet drop also increases (see (1)). The algorithm uses two threshold values of the
Copyright © 2017 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. Samouilov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the VII Conference
“Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”,
Moscow, Russia, 24-Apr-2017, published at http://ceur-ws.org
Velieva Tatiana R., Korolkova Anna V., Kulyabov Dmitry S. 115
average queue length to control drop function (Fig. 1):
0, 0 < Q̂ 6 Qmin ,
Q̂ − Qmin
p(Q̂) = p , Qmin < Q̂ 6 Qmax , (1)
Qmax − Qmin max
1, Q̂ > Qmax .
Here p(Q̂) — packet drop function (drop probability), Q̂ — exponentially-weighted
moving average of the queue size average, Qmin and Qmax — thresholds for the weighted
average of the queue length, pmax — the maximum level of packet drop.
Figure 1. RED packet drop function
The RED algorithm is quite effective due to simplicity of implementation in the
network hardware, but it has a number of drawbacks. In particular, for some parameters
values there is a steady oscillatory mode in the system, which negatively affects quality
of service indicators (QoS) [6–8]. Unfortunately there are no clear criteria for RED
parameters values selection, in which the system does not enter self-oscillating mode.
We describe the control system driven by RED algorithm as the continuous model
(see [9–16]):
1 W (t)W (t − T (Q, t))
Ẇ (t) = − p(t − T (Q, t));
T (Q, t) 2T (t − T (Q, t))
W (t) (2)
Q̇(t) = N (t) − C;
T (Q, t)
˙
Q̂(t) = −wq C Q̂(t) + wq CQ(t).
Here the following notation is used:
— W — the average TCP window size;
— Q — the average queue size;
— Q̂ — the exponentially weighted moving average (EWMA) of the queue size aver-
age;
— C — the queue service intensity;
— T — full round-trip time; T = Tp + Q C
, where Tp — round-trip time for free
network (excluding delays in hardware); Q
C
— the time whitch batch spent in the
queue;
116 ITTMM—2017
— N — number of TCP sessions;
— p — packet drop function.
For this model we use some simplifying assumptions:
— the model is written in the moments;
— the model describes only the phase of congestion avoidance for TCP Reno protocol;
— in the model the drop is considered only after reception of 3 consistent ACK
confirmations.
3. The Elements of Control Theory
We will use the control theory block-linear approach [17]. According to this ap-
proach, the original nonlinear system is linearized and divided into blocks. These blocks
are characterized by the transfer function linking the input and output values. The
transfer function H(s) ties the input x1 and output x2 functions in following way:
x2 (s) = H(s)x1 (s).
The graphical notation for this relationship is shown on Fig. 2.
x1 x2
H
Figure 2. Transfer function
In control theory Laplace transformations are used. The Laplace transformation of
real variable function f (t) is the function of complex variable s = σ + iω, that:
Z∞
F (s) = L[f (t)] = e−st f (t) dt .
0
The inverse Laplace transformation of a complex variable function is the function
f (t) of a real variable, such that:
σ1Z+i∞
−1 1
f (t) = L [F (s)] = est F (s) ds ,
2πi
σ1 −i∞
where σ1 is a real number.
The Laplace transformation allows to replace differential equations with algebraic
n
ones. Formally, the differential operator ddtna is replaced by the degree of the variable
s:
dn
→ sn . (3)
dtn
Also it simplifies the work with functions with lagging argument. The lagging argu-
ment is formally transformed into the multiplicative exponent:
f (t − τ ) → F (s)e−sτ . (4)
Velieva Tatiana R., Korolkova Anna V., Kulyabov Dmitry S. 117
On the block diagram one can select several connection types: series (Fig. 3), parallel
(Fig. 4) and the connection with the opposite link (Fig. 5). Each of these connection
types can be converted into the structure shown in Fig. 2.
x1 x2 x3
H1 H2
Figure 3. Series connection of blocks
x1 x2 x3
x1 x2 x4 H1
H1 −
x4
x3 H2
H2
Figure 4. Parallel connection of blocks Figure 5. Feedback
For series connection (Fig. 3): x2 (s) = H1 (s)x1 (s), x3 (s) = H2 (s)x2 (s). Excluding
x2 (s), we will get x3 (s) = H2 (s)H1 (s)x1 (s). So, for the series connection the transfer
function of the junction will be the product of the transfer functions of links: H(s) =
H2 (s)H1 (s), or for n links:
n
Y
H(s) = Hi (s).
i=1
For parallel connection1 (Fig. 4) we have x2 (s) = H1 (s)x1 (s), x3 (s) =
H2 (s)x1 (s), x4 (s) = x2 (s) + x3 (s). Excluding x2 (s) and x3 (s), we will get x4 (s) =
(H1 (s) + H2 (s))x1 (s). Thus, the transfer function of the parallel connection is equal to
the sum of transfer functions of the links, or for n links:
n
X
H(s) = Hi (s).
i=1
For negative feedback2 (Fig. 5) we have x3 (s) = H1 (s)x2 (s), x4 (s) =
H2 (s)x3 (s), x2 (s) = x1 (s)x4 (s). By excluding x2 (s) and x4 (s), we will get x3 (s) =
H1 (s)
x (s). Thus, the transfer function of connection with negative feedback
1+H1 (s)H2 (s) 1
is:
H1 (s)
H(s) = .
1 + H1 (s)H2 (s)
1
Here we used the element “summation unit” (presented in the diagram as a circle).
2
Here we used the element “summation unit with subtraction” or “comparator”.
118 ITTMM—2017
4. Harmonic Linearization Method
The method of harmonic linearization is an approximate method. It is used for study
of start-oscillation conditions and determination of the parameters of self-oscillations,
for the analysis and evaluation of their sustainability, as well as for the study of forced
oscillations. Harmonically-linearized system depends on the amplitudes and frequencies
of periodic processes. The harmonic linearization differs from the common method
of linearization (leading to purely linear expressions) and allows to explore the basic
properties of nonlinear systems.
The method of harmonic linearization is used for systems of a certain structure (see
figure 6). The system consists of the linear part Hl and the nonlinear part, which is set
by function f (x). It is generally considered a static nonlinear element.
g x y
f (x) Hl
−
Figure 6. Block structure of the system for the harmonic linearization method
We can represent a nonlinear element as follows:
κ 0 (A) d
f (x) = κ(A) + x = Hnl (A, ∂t )x, (5)
ω dt
where Hnl (A, ∂t ) is the approximate transfer function of the nonlinear unit, κ(a) and
κ 0 (a) are the harmonic linearization coefficients.
After finding the coefficients of harmonic linearization for given nonlinear unit, it is
possible to study the parameters of the oscillation mode. The existence of oscillation
mode in a nonlinear system corresponds to the determination of oscillating boundary of
stability for the linearized system. Then A and ω can be found by using linear systems
stability criteria (Mikhailov, Nyquist–Mikhailov, Routh–Hurwitz). Thus, the study of
self-oscillation parameters can be done by one of the methods of determining the limits
of stability of linear systems.
The Nyquist-Mikhailov criterion [18, 19] allows to judge about the stability of the
open-loop automatic control system by using Nyquist plot (amplitude-phase character-
istic) of the open-loop system.
Make the substitutions ∂t → iω and s → ∂t → iω in the transfer function. Un-
damped sinusoidal oscillations with constant amplitude are determined by passing the
amplitude-phase characteristics of the open-loop system through the point (−1, i0).
The characteristic function of the system is:
1 + Ho (iω) = 0,
Ho (iω) := Hl (iω)Hnl (A, iω),
where Ho — the transfer function of the open-loop system.
Thus:
Hl (iω)Hnl (A, iω) = −1. (6)
Velieva Tatiana R., Korolkova Anna V., Kulyabov Dmitry S. 119
Given by (5) from (6) the equality is obtained:
1
Hl (iω) = − . (7)
κ(A) + iκ 0 (A)
The left part of the equation (7) is the amplitude-phase characteristic of the linear
unit, and the right part is the inverse of the amplitude-phase characteristic of the first
harmonic non-linear level (with opposite sign). And the equation (7) is the equation of
balance between the frequency and the amplitude.
This type of criterion is also called as a Goldfarb method.
Sometimes it is more convenient to write the equation (7) in the following form:
1
κ(A) + iκ 0 (A) = − . (8)
Hl (iω)
This type of criterion is also called as a Kochenburger method.
5. Linearization of the Model
We will carry out the linearization near the equilibrium point (the balance point is
denoted by f index). At the equilibrium point time derivatives turn to zero, so the
system of equations (2) will be as follows:
Wf2
1
0= − pf ;
Tf 2Tf
Wf (9)
0= Nf − C;
Tf
0 = −wq C Q̂f + wq CQf .
From the system of equations (9) we get the bound equation for the equilibrium
values of the variables:
2
pf =
2
;
W f
CTf (10)
Wf = ;
Nf
Q̂f = Qf .
Let us denote the variables: W := W (t), WT := W (t − t), Q := Q(t), p := p(t − t).
We write out the right part of the system (2):
1 W WT
LW (W, WT , Q, p) =
− p;
T 2T
W (11)
LQ (W, Q) = N − C;
T
L (Q̂, Q) = −w C Q̂ + w CQ.
Q̂ q q
120 ITTMM—2017
The variation of the right part (11) for all variables in a neighborhood of the equi-
librium point is:
δLW WT Wf δLW W Wf
= − p =− pf ; = − p =− pf ;
δW f 2T f 2Tf δWT f 2T f 2Tf
Q Q
δLW 1 δ C
+ Tp W WT δ C
+ Tp 1 Wf2
= − 2 + p =− 2
+ pf ;
δQ f T δQ 2T 2 δQ CTf 2CTf2
f
δLW W WT δLQ 1 Wf2 N
= − =− ; = N = ;
δp f 2T f 2Tf δW f T f Tf
Q
δLQ W δT W δ C + Tp W Wf
= − 2N = − 2N = − N =− N;
δQ f T δQ f T δQ CT 2 f CTf2
f
δLQ̂ δLQ̂
= −wq C = −wq C; = wq C = wq C.
δ Q̂ f δQ f
f f
Considering the equation (10), we can rewrite this system in the following form.
δLW Wf 2 1 N
=− =− =− ;
δW f 2Tf Wf2 Wf Tf CTf2
δLW Wf 2 1 N
=− =− =− ;
δWT f 2Tf Wf2 Wf Tf CTf2
δLW 1 2
=− + = 0;
δQ f CTf2 2CTf2
2 2
δLW C Tf 1 C 2 Tf
=− 2
=− ;
δp f N 2Tf 2N 2
δLQ N δLQ CTf N 1
= ; =− =− ;
δW f Tf δQ f N CTf2 Tf
δLQ̂ δLQ̂
= −wq C; = wq C.
δ Q̂ δQ
f f
Velieva Tatiana R., Korolkova Anna V., Kulyabov Dmitry S. 121
Thus, we received from the initial system (2) the linearized one:
δLW δLW
δ Ẇ (t) =
δW (t) + δW (t − Tf ) +
δW f δW T f
δLW δLW
+ δQ(t) + δp(t − Tf ) =
δQ f δp f
N C 2 Tf
=− δW (t) + δW (t − Tf ) − δp(t − Tf ) ;
CT 2 2N 2 (12)
f
δLQ δLQ N 1
δ Q̇(t) = δW (t) + δQ(t) = δW (t) − δQ(t) .
δW f δQ f Tf T f
˙ δLQ̂ δLQ̂
δ Q̂(t) = δ Q̂
δ Q̂(t) + δQ(t) = −wq C δ Q̂(t) + wq C δQ(t) .
δQ
f f
In addition, let us to linearize the drop function (1):
0, 0 < Q̂ 6 Qmin ,
pmax
δp(Q̂, t) = δ Q̂(t) , Qmin < Q̂ 6 Qmax , (13)
Qmax − Qmin
0, Q̂ > Qmax .
The (13) may be denoted as
δp(Q̂, t) = PRED δ Q̂(t) ;
0, 0 < Q̂ 6 Qmin ,
pmax (14)
PRED := , Qmin < Q̂ 6 Qmax ,
Qmax − Qmin
0, Q̂ > Qmax .
Let us perform on (12) the transformation (3) and (4).
N C2T
f
s δW (s) = −
2
δW (s) + δW (s) e−sTf − δp(s) e−sTf =
CT 2N 2
f
C 2 Tf
N
1 + e−sTf δW (s) − δp(s) e−sTf ;
=−
CTf 2 2N 2 (15)
N 1
s δQ(s) =
δW (s) − δQ(s) .
Tf T f
s δ Q̂(s) = −wq C δ Q̂(s) + wq C δQ(s) .
122 ITTMM—2017
Let’s simplify (15):
1 C 2 Tf −sTf
δW (s) = − e δp(s) ;
N −sTf 2N 2
s + CT 2 1+e
f
1 N
δQ(s) = 1 T
δW (s) ; (16)
s + Tf f
1
δ Q̂(s) = δQ(s) .
1 + w sC
q
Considering the formula δ Q̂(s) from the system of equations (16), we can write
out (14) in the following form:
1
δp(s) = PRED δQ(s) . (17)
1 + w sC
q
The function PRED has the form shown in Fig. 7
f (x)
pmax
Qmax − Qmin
x
Qmin Qmax
Figure 7. The function PRED
Based on (16) and (17) the block representation of the linearized RED model (Fig. 8)
is constructed.
C 2 Tf
2N 2
δw 1 N δq
s+ T1 Tf
− s+ N
CT 2
(1+e−sTf ) f
f
δp
PRED 1+ 1 s e−sTf
wq C
Figure 8. Block representation of the linearized RED model
For clarity, it is possible to plot parametric graphs on the complex plane separately
for left Hl (i, ω) and right −1/Hnl (A) parts of the equation (7) (of ω and A respectively)
Velieva Tatiana R., Korolkova Anna V., Kulyabov Dmitry S. 123
(see figures 9 and 10). The intersection of the curves gives the point of emergence of
self-oscillations.
10 4 0.16
−1
10 3 Hl (ω) −Hnl (A) 0.14 −Hl−1 (ω) Hnl (A)
Imaginary part of Hl and −Hnl−1
Imaginary part of Hl and −Hnl−1
10 2 0.12
10 1 0.10
0.08
10 0
0.06
10 -1 0.04
10 -2 0.02
10 -3 0.00
10 -4150 100 50 0 50 100 150 200 250 0.020.10 0.05 0.00 0.05 0.10
Real part of Hl and −Hnl−1 Real part of Hl and −Hnl−1
Figure 9. Nyquist plot for system (7) Figure 10. Nyquist plot for system (8)
For the example of the calculation we have chosen the following parameters: Qmin =
100 [packets], Qmax = 150 [packets], pmax = 0.1, Tp = 0.0075 s, wq = 0.002, C = 2000
[packets]/s, N = 60 (the number of TCP sessions).
As a result we obtained the following values for the amplitude and the cyclic fre-
quency: A = 1.89 [packets], ω = 16.55s−1 .
6. Conclusion
The authors demonstrated the technique of oscillatory modes research for the sys-
tems with control. We tried to explain this technique for mathematicians unfamiliar
with the control theory formalism. We plan to apply this technique to the study of a
wide range of traffic active control algorithms. Also it is interesting to compare these
results with the previous results obtained for self-oscillation systems with control.
References
1. S. Floyd, V. Jacobson, Random Early Detection Gateways for Congestion Avoid-
ance, IEEE/ACM Transactions on Networking 1 (4) (1993) 397–413. doi:10.1109/
90.251892.
2. 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.
3. V. Kushwaha, R. Gupta, Congestion Control for High-Speed Wired Network: A
Systematic Literature Review, Journal of Network and Computer Applications 45
(2014) 62–78. doi:10.1016/j.jnca.2014.07.005.
4. R. Adams, Active Queue Management: A Survey, IEEE Communications Surveys
& Tutorials 15 (3) (2013) 1425–1476. doi:10.1109/SURV.2012.082212.00018.
5. A. V. Korolkova, D. S. Kulyabov, A. I. Chernoivanov, On the Classification of RED
Algorithms, Bulletin of Peoples’ Friendship University of Russia. Series: Mathemat-
ics. Information Sciences. Physics (3) (2009) 34–46.
6. A. Jenkins, Self-Oscillation, Physics Reports 525 (2) (2013) 167–222. arXiv:1109.
6640, doi:10.1016/j.physrep.2012.10.007.
124 ITTMM—2017
7. F. Ren, C. Lin, B. Wei, A Nonlinear Control Theoretic Analysis to TCP-RED
System, Computer Networks 49 (4) (2005) 580–592. doi:10.1016/j.comnet.2005.
01.016.
8. W. Lautenschlaeger, A. Francini, Global Synchronization Protection for Bandwidth
Sharing TCP Flows in High-Speed Links, in: Proc. 16-th International Conference
on High Performance Switching and Routing, IEEE HPSR 2015, Budapest, Hun-
gary, 2015. arXiv:1602.05333.
9. V. Misra, W.-B. Gong, D. Towsley, Stochastic Differential Equation Modeling and
Analysis of TCP-Windowsize Behavior, Proceedings of PERFORMANCE 99.
10. 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.
11. 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 Confer-
ence of the IEEE Computer and Communications Society (Cat. No.01CH37213),
Vol. 3, IEEE, 2001, pp. 1726–1734. doi:10.1109/INFCOM.2001.916670.
12. C. V. V. Hollot, V. Misra, D. Towsley, A Control Theoretic Analysis of RED, 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. 1510–1519. doi:10.1109/
INFCOM.2001.916647.
13. A. V. Korolkova, D. S. Kulyabov, L. A. Sevastianov, Combinatorial and Operator
Approaches to RED Modeling, Mathematical Modelling and Geometry 3 (3) (2015)
1–18.
14. T. R. Velieva, A. V. Korolkova, D. S. Kulyabov, Designing Installations for Veri-
fication of the Model of Active Queue Management Discipline RED in the GNS3,
in: 6th International Congress on Ultra Modern Telecommunications and Control
Systems and Workshops (ICUMT), IEEE Computer Society, 2015, pp. 570–577.
arXiv:1504.02324, doi:10.1109/ICUMT.2014.7002164.
15. A. V. Korolkova, T. R. Velieva, P. A. Abaev, L. A. Sevastianov, D. S. Kulyabov,
Hybrid Simulation Of Active Traffic Management, Proceedings 30th European Con-
ference on Modelling and Simulation (2016) 685–691doi:10.7148/2016-0685.
16. R. Brockett, Stochastic Analysis for Fluid Queueing Systems, in: Proceedings of
the 38th IEEE Conference on Decision and Control (Cat. No.99CH36304), Vol. 3,
IEEE, 1999, pp. 3077–3082. doi:10.1109/CDC.1999.831407.
17. K. J. Aström, R. M. Murray, Feedback Systems: An Introduction for Scientists and
Engineers, America (208) 408.
18. H. Nyquist, Regeneration Theory, Bell System Technical Journal 11 (1) (1932)
126–147. doi:10.1002/j.1538-7305.1932.tb02344.x.
19. J. Hsu, A. Meyer, Modern Control Principles and Applications, McGraw-Hill, 1968.