About Linearization of Active Traffic Management Module Model

Abstract

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

-

1. Introduction

While modeling technical systems with control it is often required to study characteristics 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 selfoscillating 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 mathematical modeling. The authors offer a methodological article in order to introduce this method to non-specialists.

The RED Congestion Adaptive Control Mechanism average queue length to control drop function (Fig. 1): p(Q^) = 80; > > >>< Q^ > Qmax > > >:1;

Qmin

Qmin

0 < Q^ 6 Qmin; pmax; Qmin < Q^ 6 Qmax;

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.

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]): >>8W_ (t) = > > > > <

Q_ (t) = > > > > >:>Q^_ (t) =

1 T (Q; t) W (t) T (Q; t)

N (t) 2T (t

C; wqCQ^(t) + wqCQ(t):

W (t)W (t

T (Q; t)) T (Q; t)) p(t

T (Q; 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 average; — C — the queue service intensity; network (excluding delays in hardware); QC — the time whitch batch spent in the queue; ( 1 ) ( 2 ) — 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 approach, 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: The graphical notation for this relationship is shown on Fig. 2.

x2(s) = H(s)x1(s): x1

H

x2

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: F (s) = L[f (t)] = e stf (t) dt :

The inverse Laplace transformation of a complex variable function is the function f (t) of a real variable, such that: f (t) = L 1[F (s)] = estF (s) ds ; where 1 is a real number.

The Laplace transformation allows to replace differential equations with algebraic ones. Formally, the differential operator ddntna is replaced by the degree of the variable s:

Also it simplifies the work with functions with lagging argument. The lagging argument is formally transformed into the multiplicative exponent: ( 3 ) ( 4 )

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

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:

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:

H(s) = n

Y Hi(s): H(s) = n X 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) 1+H1(s)H2(s) x1(s). Thus, the transfer function of connection with negative feedback is:

H(s) =

H1(s) 1 + H1(s)H2(s) : 1Here we used the element “summation unit” (presented in the diagram as a circle). 2Here we used the element “summation unit with subtraction” or “comparator”. 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 f (x)

Hl y We can represent a nonlinear element as follows: {0(A) d !

dt f (x) = {(A) + ( 5 ) 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 characteristic) of the open-loop system.

Make the substitutions @t ! i! and s ! @t ! i! in the transfer function. Undamped 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: where Ho — the transfer function of the open-loop system.

Thus:

1 + Ho(i!) = 0; Ho(i!) := Hl(i!)Hnl(A; i!);

Hl(i!)Hnl(A; i!) =

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:

Given by ( 5 ) from ( 6 ) the equality is obtained:

Hl(i!) =

1 {(A) + i{0(A) ( 7 ) ( 8 ) ( 9 ) ( 10 ) ( 11 ) 8 >>0 = > > > > < >0 = > > > > > :0 = 1 Tf Wf Nf Tf

Wf2 pf ; 2Tf

C; wqCQ^f + wqCQf : 8 >>pf = > > > > < 2 Wf2

;

CTf

Wf = >>> Nf > >:>Q^f = Qf :

; 8 >>LW (W; WT ; Q; p) = > > > <

LQ(W; Q) = > > > > >:LQ^ (Q^; Q) =

W T

N wqCQ^ + wqCQ: 1 T C;

W WT p; 2T

From the system of equations ( 9 ) we get the bound equation for the equilibrium values of the variables:

Let us denote the variables: W := W (t), WT := W (t We write out the right part of the system ( 2 ): t), Q := Q(t), p := p(t t).

The variation of the right part ( 11 ) for all variables in a neighborhood of the equilibrium point is:

LW = W2TT p f = 2WTff pf; W f

LWWT f = 2WT p f = 2WTff pf; LQW f = T2 f = C1Tf2 + 2WCTf2f2 pf; LW = WWT = p f 2T f LQ = TW2 N QT f = TW2 N Q f

Wf2 2Tf ;

QC + Tp

Q

LWQ f = T1 N f = TNf ; f

= CWT2 N f = CWTff2 N;

LQ^Q^ f = wqC f = wqC; LQQ^ f = wqC f = wqC: Considering the equation ( 10 ), we can rewrite this system in the following form.

LWW f = 2WTff W2f2 = Wf1Tf = CNTf2 ; LWWT f = 2WTff W2f2 = Wf1Tf = CNTf2 ;

LQW f = C1Tf2 + 2C2Tf2 = 0; LW = CN2T2f2 2T1f = p f

C2Tf 2N2 ; LQ = N ; W f Tf

LQ = CTf N Q f N CTf2 = 1 ;

Tf Thus, we received from the initial system ( 2 ) the linearized one: 8

_ > W (t) = > > > > > > > > > > > > > > > > > > > <

= > > > > > _ > Q(t) = > > > > > > > > > > _ > ^

Q(t) = > > > : + N CT

L

W W L

W Q f f 2 f L

Q W L ^ Q ^ Q f f

W (t) +

Q(t) + W (t) +

W (t W (t) + ^ Q(t) +

L

Q Q ^ Q Q L f f L

W W T L

W p

f T ) f f

W (t

T ) + f p(t

T ) = f > > > > > > > > > : >>s Q(s) =

W (s)

^ w C Q(s) + w C Q(s) : q q ( 12 ) ( 13 ) ( 14 ) ( 15 ) Let us perform on ( 12 ) the transformation ( 3 ) and ( 4 ).

>s W (s) =

W (s) +

W (s) e sT f p(s) e sT f = = 1 + e sT f

W (s) p(s) e sT

f ; ^ p(Q; t) = P

RED ^

Q(t) ; p max max

Q min

^ 0 < Q 6 Q min

; ; Q min

^ < Q 6 Q max

; ^ Q > Q max

: ( 16 ) ( 17 )

Let’s simplify ( 15 ): 8 > W (s) = > > > > > > > > > <

Q(s) = > > > > > > > >> Q^(s) = > :

1

Considering the formula out ( 14 ) in the following form:

Q^(s) from the system of equations ( 16 ), we can write p(s) = PRED 1 PRED 1+ wqsC

e−sTf

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) (see figures 9 and 10). The intersection of the curves gives the point of emergence of self-oscillations.

Hl(ω) −Hn−l1(A) −Hl−1(ω)

Hnl(A)

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 frequency: A = 1:89 [packets], ! = 16:55s 1.

6.

Conclusion

The authors demonstrated the technique of oscillatory modes research for the systems 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 Avoidance , 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: Mathematics. 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.

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, Hungary, 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 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 .

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 Verification 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 Conference 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 .