Спросить
Войти
Запропоновано модель управлтня трафтом, яка заснована на тензорному узагальненш нел^ ыьмннх диференщальних рiвнянь стану мережi. Це дозволило отримати узгоджене розв&язання задач маршрутизаци та розподЫу канального ресурсу мiж потоками рiзних клаЫв. Ршення дозволяв забезпечити ятсть обслуговування за показниками середньог пакетног швидкостi передачi та затрим-ки пакетiв, в тому чи^ в нестащонарному режимi роботи ттерфейЫв маршрутизаторiв мережi
Ключовi слова: ятсть обслуговування, управлтня трафтом, телекомушкацшна мережа, тензор,
динамiчна модель, маршрутизащя, ттерфейс □-□
Предложена модель управления трафиком, основанная на тензорном обобщении нелинейных дифференциальных уравнений состояния сети. Это позволило получить согласованное решение задач маршрутизации и распределения канального ресурса между потоками различных классов. Решение позволяет обеспечить качество обслуживания по показателям средней пакетной скорости передачи и задержке пакетов, в том числе в нестационарном режиме работы интерфейсов маршрутизаторов сети
UDC 621.391
|DOI: 10.15587/1729-4061.2016.85602
DEVELOPMENT OF THE DYNAMIC TENSOR MODEL FOR TRAFFIC MANAGEMENT IN A TELECOMMUNICATION NETWORK WITH THE SUPPORT OF DIFFERENT CLASSES OF SERVICE
O. Yeremenko
PhD, Senior Researcher Department of Telecommunication Systems Kharkiv National University of Radio Electronics Nauky ave., 14, Kharkiv, Ukraine, 61166 E-mail: oleksandra.yeremenko@nure.ua
Provision of the assigned level of Quality of Service (QoS) in contemporary telecommunication networks (TCN) is an important scientific and technological task, the solution of which requires the systems coordination in the operation of many network protocols, referred to all levels of the model of the Open Systems Interconnection (OSI). In this case, it is important to note that from the point of view of users and infocommunication services, the aspects of providing for end-to-end QoS level first simultaneously by the rate parameters (packet transmission rate), time parameters (average delay and packet jitter) and by reliability parameters (probability or the number of packet losses) [1-3]. The numerical values of these QoS parameters completely depend on the effectiveness of traffic management and, first of all, on the characteristics of the selected path (paths) of the packets transmission, namely on its length (number of hops), capacity and utilization of routers interfaces, which form this path. The enumerated characteristics of the paths in the TCN are traditionally defined by the operation results not only of routing protocols, but also of the mechanisms of allocation of the throughput of interfaces (communication links) between the flows of various classes of the Differentiated Service (DiffServ).
As for the relevance of the conducted study, it is necessary to note that the provision of coordination in solving the problems of routing and the allocation of throughput of communication links of TCN is a key, but not the only
task in the field of Quality of Service maintenance. In the course of solving this problem, it is necessary to take into consideration the fact that a change in packet queue utilization on the TCN router interfaces has a dynamic character, due to which the numerical values of the main Quality of Service parameters in a general case are the function of time (observation period) [4-6]. Owing to this fact, relevant is the development of dynamic tensor models, which are represented by the well-reputed approach, based on the use of differential equations of the state of the modeled system with the view to describing the processes of traffic management and providing the Quality of Service in TCN as a whole.
There is a whole range of the known mathematical models, which with a different degree of accuracy and effectiveness describe the dynamics of a change in the state of telecommunication network during the solution of a wide circle of problems of traffic management and provision of Quality of Service. For example, in works [7-10], with the help of the models, represented by nonlinear differential equations of a change in the window of transmission and TCP flow intensity, the problem of selection of optimum parameter values of both TCP (Transmission Control Protocol) and of AQM (Active Queue Management), functioning together, is solved.
Articles [5, 6] develop an approach to the description of dynamics of change in packet queue utilization on the routers interfaces with the help of linear differential (difference) equations of the network state, used in the solution of routing problems and problems of link resource allocation. The linear nature of the model made it possible to reduce the solution of the problems of traffic management to the problem of optimal management with the quadratic optimality criterion.
Papers [11-15] demonstrated the possibilities of description of dynamics of change in the average queue length on the interfaces with the help of nonlinear differential equations, the form of which is in many respects determined by the nature of the selected models of packets flows and their service discipline on the routers interfaces. At present, the following types of mathematical models, based on different approximations of the dynamics of changes in the state of the network router interface, are known [12]:
- Simple Stationary Approximation, SSA;
- Stationary Peakedness Approximation, PK;
- Average Stationary Approximation, ASA;
- Closure Approximation for Nonstationary Queues;
- Pointwise Stationary Approximation, PSA;
- Pointwise Stationary Fluid Flow Approximation, PSFFA;
- Modified Offered Load Approximation, MOL;
- Fixed Point Approximation, FPA.
In this enumeration of models, it is worth distinguishing the PSFFA approximation, unquestionable advantage of which is the possibility of assigning dynamics of change in average queue length in the analytical form, which makes it possible to numerically estimate the over time changes of such important parameters of Quality of Service as average delay, jitter of packets, as well as a probability of the packets loss. Specifically, for the purpose of giving to the dynamic model of TCN the properties regarding the description of processes of Quality of Service provision according to the parameters of efficiency and of the average delay in the course of solving routing problems, papers [16, 17] implemented its tensor generalization, with the help of which it was possible to obtain the desired conditions for providing QoS in the analytical form. In present work, further development of the proposed approach [16, 17], oriented to the coordinated solution of the problems of routing and link resource allocation, is proposed. On the other hand, the obtained solution is oriented to a certain decrease in the computational complexity, owing to the transition from the use of a basis of independent circuits and node pairs [17] to the system of coordinates of interpolar paths and internal node pairs in the course of tensor geometrization of the TCN structure.
The aim of the work is obtaining the solutions of traffic management, directed towards providing Quality of Service by a set of parameters (average rate of packets transmission and delay) under conditions of dynamic change in the TCN state, which is manifested in the non-stationary operating mode of routers interfaces.
To achieve the set aim, the following problems of research are supposed to be solved:
- selection of the flow-based model of traffic management, based on multipath routing of different flow classes;
- substantiation of the model for describing the dynamics of a change in the average packets delay on the TCN routers interfaces;
- geometrization of the TCN: introduction of geometric space and separate coordinate systems, formed both by the separate communication links, and by a set of paths in the network;
- tensor generalization of nonlinear differential equations of the TCN state with the formulation in the analytical form of conditions of providing QoS during the class-based traffic management;
- stating the problem of traffic management in the TCN as that of optimization and selection of optimality criterion of obtained solutions;
- exploration of the proposed dynamic tensor model of traffic management and obtaining numerical results, which prove its fitness for work and adequacy.
Within the considered model of traffic management, the TCN structure is seen as one-dimensional network S=(U, V), where U = {u¡,i = 1,m} is the set of the network nodes (routers), and
V = {vz = (i,j); z = 1,n; i,j = 1,m; i * j}
is the set of network edges, in this case each edge vz = (i,j) e V simulates the corresponding z-th communication link between the i-th and the j-th routers. Let us also assume as known the throughput 9(i,j) of communication link (i, j) (namely, the j-th network interface on the i-th TCN router), measured in packets per second (1/s).
Let us assume that it is necessary to calculate the set of routing variables x^ in the course of solving the problem of traffic management, based on the multipath routing of flows of different classes. In this case, each routing variable characterizes a fraction of intensity of the k-th flow of the p-th
class ( p = 1,P, k e K , K e K, where K is the set of flows
f > > p p> p i
in the network, and Kp is the set of flows of the p-th class) from the i-th node to the j-th through the corresponding j-th interface. Prevention of overloading of the routers and of the network as a whole is achieved within the framework of satisfying the conditions of conservation the flow on the source, the destination and in the transit nodes, which can be written down in the form [19]:
I x^ = 1 kp eKp, i = sv
j:(ij)eV
• I x^) - I x¿) = a kp eKp, i*skp,dkp; (1)
j:(ij)eV j:(j,i)eV
I x(j„ = -1 kp eKf, i = dv
, j(j-¡)eV
where sk is the node (router) source, dk is the node destination for the packets of the k-th flow of the p-th class.
Then the compliance with the following restrictions, imposed on the control (routing) variables x^, provides for the implementation of the strategy of multipath routing:
For providing controllability of the process of fighting with overloading in the course of flows routing, the following conditions are introduced into the model, compliance with which means that the coefficient of overloading of each communication link must be less than one:
№ *y(pij)j(ij)> (i-j)eE(3)
where Xrepq are the requirements for the average packet rate (intensity) of the k-th flow of the p-th class, which enters the network, the values of which, in their turn, are the metrics of QoS; ypjj) is the control variable, which is responsible for link resource allocation and numerically characterizing the part of the throughput j(i j), allocated to the flows of the p-th class (0 < y(p, j) < 1).
With the use of the PSFFA approximation and the simulation of functioning of the network router interface, for example, by the queuing system M/G/1 (single-link queuing system with the Poisson input flow and an arbitrary service time distribution), its special cases may be distinguished [11, 13]. Thus, in the case of using queuing system M/M/1, the system of nonlinear differential equations of dynamics of a change in the average packets delay of the flows of the p-th class xpij) as the time function on the routers interfaces [16, 20] can be obtained, namely:
fij)(t) dt
= 1 -ji,
"(i-j)
where j ^ = ypj) j(j is the volume of the throughput of interface (i, j), allocated to flows of the p-th class;
kp ■ xkp
req A(i,j)
is the summary intensity of the flows of the p-th class at interface (i, j).
With the help of expressions (4) it is possible to analyze the dynamics of a change in the average packets delay on the routers interfaces both in a stationary operating mode, that is, at
and in the non-stationary mode, for example, during the routing table update time and change in the order of link
resource use.
quantity of interpolar paths and internal node pairs, correspondingly, for which the following expressions are valid:
J(S) = p-1 = m-2; k(S) = m + 1 = n-m + 2; n = J(S) + k(S),
where m is the total quantity of nodes in the network S; p=m-1 is the total quantity of node pairs in the network S; |m=n-m+1 is the cyclomatic number of network m(S) [18].
From all possible interpolar paths, let us select k(S) of linearly independent paths {y¡,i = 1,k}. The set of internal
node pairs is represented by the set {e j, j = 1, j}. The indicated sets form the basis of n-dimensional space of the network structure. In this space the TCN can be described by means of the mixed bivalent tensor [21, 22]
Q = T ®A,
where ® is the operator of tensor multiplication. In this case, it is necessary to note that the components of this tensor are the univalent covariant tensor T of the average packets delays and the univalent contravariant tensor A of flow intensities. In turn, (6) in the index form has the form:
qi = tjii, i,j = i,n(7)
where tj is the average packets delay along the j-th coordinate path (s), and X is the packets flow intensity along the i-th coordinate path (1/s). Tensor (6) is examined in the following coordinate system (CS): CS of edges (type v), as well as CS of interpolar paths and internal node pairs (type ye).
In papers [16, 17], within the framework of tensor generalization, it was assumed that the network routers interfaces function in the stationary mode, that is, its parameters (average queue length, average packets delay and level of packets losses) did not depend on the observation time, but were determined exceptionally by the throughput and intensity of the serviced flow. In this study we proposed using the model PSFFA M/G/1, namely its special case M/M/1, for the purpose of analysis of the dynamics of changes in the state of the router interface over time. The solution of differential equation (4) was analytically obtained with the aid of a set of instruments of the MatLab environment [16, 17], taking into account the queue organization for the flows of different classes:
Let us assume that in the solution of the problem of class-based traffic management, the telecommunication network is represented by the tensor model, in which the structure of network determines the anisotropic space, formed by the sets of interpolar paths and internal node pairs. The source node and the destination node of the packets flows are implied by the network poles, and the set of internal node pairs includes all node pairs, except poles. The dimension of this space is determined by a total quantity of edges in the network and is equal to n [21-23]. In turn, each independent path determines the coordinate axis in the space structure.
Let us assume that S is the connected network, then the values of k(S) and J(S) for this network determine the
"(i-j)
[( jPi-j) ■ W(0, - (iPi-j) ■ exp(-(I(Pi
"(i,j)
+(t-(1(Pij) + j(Pij) *
xln(exp(-(I(PiJ) ■(XoiPij) -ji-j) +1))/j(Pi,j)) *
*Wij) -tj + 1)))/(jfij)-Hj))2) * X«j)-1PiJ))2)/jPiJ)))/jPiJ)))/1Pi,j) +1
where p = 1,P; W() is the Lambert W-function; expQ is the exponential function; to is the average packets delay on the router interface at the initial moment of time, that is, at the moment of calculating control variables x^j
In the index form in the course of further tensor generalization the expression (6) in the CS of edges for each k-th flow
of the p-th class takes the form (indices k and p are omitted for the convenience of recording):
-[(j-W(0, -(1-exp(-(1 + (tiv(j-i)
-(1 +j- ln(exp(-(1- (t01-t0j +1)) / j) x X(T01-T0j + 1)))/(j-1)2) x X(j-1)2)/j))/j))/1 + 1]1V,
AT(t) = GT(t)TT(t),
Tge (t) =
Tg (t)" "tg (t)" "te(t)"
— , at Tg (t) = , Te (t) =
Te (t)" _tk (t)" "tj (t)"
where i = 1,n indicates the number of communication link in the network; parameter v corresponds to the type of the used CS; 1V characterizes the intensity of the k-th flow of the p-th class in the i-th communication link; tV characterizes the average packets delay of the p-th class in the i-th communication link, namely tj According to the postulate of the second generalization of Kron [21-23], the system of equations (9) takes the following form in the vector form
where tg(t) and tE(t) are the average delays of packets in the interpolar path gi and in the internal node pair ; respectively. These vectors Tg(t) and Te(t) have the correspondent dimensions k and J.
The covariant nature of the tensor of delays T(t) leads to the following law of coordinate transformation:
Tv(t) = A T (t),
where Ay(t) and Tn(t) are the correspondent projections of tensors A(t) h T(t) in the CS of edges and are n-dimensional vectors of flows intensity and the packets average delay in
the communication links of TCN; Gv(t) = ||gV(t)|| is the diagonal matrix nxn, in this case the diagonal elements of this matrix correspond to edges jv^i = 1,n} and are calculated as follows
gV(t) = 1V(j-1)/[(jW(0, -(1-exp(-(1 + (t --(1 + j-ln(exp(-(1-(t01-t0j+1)) / j) x x(x01-T0j + 1)))/(j-1)2) x
x(j-1)2)/j))/j))/1 + 1]. (11)
where A is the nxn matrix of covariant coordinate transformation during transferring from the CS of interpolar paths and internal node pairs to the CS of edges. Matrix A is connected with matrix C (matrix of contravariant transformation) by the condition of orthogonality CAt=I, where I is the unit matrix of dimensions of nxn, [•] is the operator of transposition.
In the CS of interpolar paths and internal node pairs, expression (10) takes the form:
Age (t) = Gge (t)Tge (t),
where Gge(t) is the projection of tensor G(t) in the CS of interpolar paths and internal node pairs.
Then G(t) is the bivalent contravariant metric tensor, the projections of which in the CS in question are connected with the following expression:
Gge (t) = A&Gv(t) A. (17)
We will write down (16) in the vector-matrix form:
The projections of tensor of flows intensities A(t) in the introduced coordinate systems (5) are connected together with the aid of the nonsingular nxn square matrix C:
A v(t) = C Age (t),
where C is the matrix nxn, which determines the contra-variant law of transition from the CS of interpolar paths and internal node pairs to the CS of edges, and AgE(t) is the n-dimensional vector, which is the projection of tensor A(t) in the CS of interpolar paths and internal node pairs of type ge, the components of which are the following:
Age (t) =
"Ag (t)" "lg (t)" "le (t)"
— , at Ag(t) = , Ae(t) =
Ae (t)_ 1g (t) ij (t)"
where Ag(t) is the k-dimensional vector of the flow intensities in the interpolar paths of network; A;(t) is the J-dimensional vector of the flow intensities in the internal node pairs of network; lg (t) is the flow intensity in the interpolar path of the network gi ; 1Je(t) is the flow intensity in the internal node pair ej.
The projection of the tensor of average delays T(t) in the CS of the interpolar paths and the internal node pairs of type ge is represented by the n-dimensional vector of the following structure:
"Ag (t)"
Ae (t)"
Gge(t) i G«(t)
--- + --where
Gge» (t)
G<? (t)
G<3> (t)
= G ge (t),
and GL& (t) and G\\J (t) are the square sub-matrices of dimensions kxk and JxJ respectively, Gg/ (t) is the sub-matrix of dimension kxJ, G^&(t) is the sub-matrix of dimension Jxk.
From expression (18), we can obtain the equations:
Ag (t) = Gge (t)Tg (t) + Gge (t)Te (t); Ae (t) = G<3> (t)Tg (t) + Gg4 (t)Te (t);
where Ae(t)=0, as packets of this or that flow can leave the network only through the network poles.
From expressions (19) and (20), according to the results, obtained in [18], it is possible to formulate in the analytical form the conditions of providing QoS:
Lg(t) < G«(t) - G<?(t)[gJ>(t)]- G®(t) Tg (t), (21)
Eig(t)=ikeq,
where 1repq are the requirements on the average packet rate (intensity) of the k-th flow of the p-th class (p = 1,P);
M req G? (t) | G? (t)
, G ge (t) = --- + --tkp req G? (t) | G? (t)
where t^q are the requirements for the average end-to-end packets delay of the k-th flow of the p-th class; Gge(t) and
(t) are the square sub-matrices of dimensions kxk and JxJ, respectively; Gg2(t) is the sub-matrix of dimension kxJ, G® (t) is the sub-matrix of dimension Jxk. According to (11) and (17), all coordinates of these sub-matrices are the time functions.
For the purpose of obtaining the effective solution of the set problem of traffic management in the TCN, let us formulate it as the problem of optimization. In this case, it is necessary to calculate the set of control variables of two types. The first type variables are responsible for routing of flows (x^), and the control variables of second type (ypij)) are responsible for determining the order of the link resource allocation in the network in the course of minimization of the following quadratic criterion of optimality:
(i,j)eE peP kp eKp
+ EE hyp« A.)-[yp^
(i,j)eE peP
where h(xipj) is the routing metric of communication link between the i-th and the j-th nodes of the TCN; hyj is the conditional cost of using the link throughput of communication link (i, j) by the flows of the p-th class. The selection of the criterion of quadratic form is determined by the fact that its use contributes to obtaining solutions of the balanced use of the accessible network resources.
The special features of the proposed solution of traffic management with the use of the tensor model (1)-(22), represented in the coordinate system of interpolar paths and internal node pairs, will be illustrated by the following numerical examples. Within the framework of the example, the network structure, indicated in Fig. 1, is assigned. In this case, the analyzed fragment of the network contains five nodes (routers) and six communication links. The corresponding throughputs are indicated in the breaks of these communication links. Let us assume that it is necessary to transmit the packets of two flows of different classes with the intensity of 470 1/s for each of them between the nodes u1 and u5 (Fig. 1). It is also assumed that the required average
end-to-end delay for the packets of the Class 1 flow must not exceed 150 ms, and for the Class 2 flow - 400 ms.
Fig. 1. Structure of the simulated network
Initial data for studying the traffic management processes of flows of both classes, including the requirements for providing the QoS according to the parameters of the average packet rate lkepq and the average end-to-end packet delay lkepq are represented in Table 1.
Initial data for studying the process of traffic management of different classes
No. of communication link Throughput of link (1/s) Throughput, allocated to Class 1 (1/s), 1eq=470 1/s, tr*eq=150 ms Throughput, allocated to Class 2 (1/s), ireq=470 1/s, <eq=400 ms
According to Table 1, the average end-to-end packets delays for all paths, used in the course of the multipath routing of the flows of two classes, must not exceed the desired values of delays i^q and i^q. Moreover, the requirements for the Quality of Service level for the first class flow by the average end-to-end delay are more rigid than for the second class flow. Taking this into account, a further analysis of the dynamics of a change in the average packet end-to-end delay along all calculated paths for the flows of different classes will be carried out.
For the represented case, it was assumed that in the calculation of average packets delays by means of (9), their initial values (to) on each specific network router interface were known and equaled, respectively:
- 50 ms, 50 ms, 50 ms, 50 ms, 50 ms and 70 ms for the transmitted flow of the Class 1 packets;
- 150 ms, 200 ms, 100 ms, 50 ms, 250 ms and 150 ms for the transmitted flow of the Class 2 packets.
The differentiation of the values of packets delays of the flows of different classes on the same interface was determined by the fact that in practice the separate class queue was organized for servicing each of them, for example, with the help of the mechanism of CBQ (Class-Based Queuing) or CBWFQ (Class-Based Weighted Fair Queuing).
Fig. 2 displays dynamics of change in the average end-to-end packets delay along three calculated paths from the
source to the destination with the service of the Class 1 packets flow.
routing table update timer, for example, 30 s, the stationary mode was not achieved.
Fig. 2. Dynamics of change in the average end-to-end delay
within the observation period: in a stationary mode, the average delays for three paths are equal to 150 ms, 150 ms and 137 ms, respectively, at the required value of not more than 150 ms
Fig. 4. Dynamics of change in the average end-to-end delay within the observation period: delays for three paths for 30 s of the observation period are equal to 400 ms, 400 ms and 370.2 ms, respectively, at the required value of not more than 400 ms
In the course of the simulation of this case, the stationary mode for all paths, used during multipath routing, was observed already after 10 s of the observation period (routing table update timer). In this case, characteristics of the calculated paths for the transmitted Class 1 packets flow (Fig. 3) for 10 s of the observation period are the following:
- Path № 1: the packet rate is 200 1/s; the average packet end-to-end delay is 150 ms;
- Path № 2: the packet rate is 169 1/s; the average packet end-to-end delay is 150 ms;
- Path № 3: the packet rate is 101 1/s; the average packet end-to-end delay is 130.7 ms.
In Fig. 3 and Fig. 5, the numerical values, indicated in the breaks of communication links (from top to bottom), indicate the following: the packet transmission rate (1/s), throughput of communication link, allocated to the flow of the given class (1/s), average packets delay of the flow of the given class (ms).
Fig. 3. Order of multipath QoS-routing and link resource allocation for Class 1 packets flow
In its turn, Fig. 4 displays dynamics of changes in the average packets delay along the three calculated paths between the node-source and the node-destination during the service of the Class 2 packets flow. In this case, within the observation period, which corresponds to the value of the
Fig. 5. Order of multipath QoS-routing and link resource allocation for Class 2 packets flow
Whereas characteristics of the calculated paths of transmission of the Class 2 packets flow had the following values (Fig. 5):
- Path № 1: 1-2-5; the packet rate is 196 1/s; the average packet end-to-end delay is 400 ms;
- Path № 2: 1-3-4-5; the packet rate is 166 1/s; the average packet end-to-end delay is 400 ms;
- Path № 3: 1-2-4-5; the packet rate is 108 1/s; the average packet end-to-end delay is 370.2 ms.
Results of examining the proposed dynamic tensor model in a number of numerical network examples proved its fitness for work and adequacy from the position of solving the problems of traffic management in the TCN, namely the problems of multipath routing and link resource allocation between the flows of different classes of service. It was shown that the allocated link resource (Table 1) simultaneously corresponded to the level of requirements for the
Qualityof Service both by the parameter of average packet rate and by the average end-to-end delay.
The proposed model is a further development and improvement of the earlier known approach [21-23], based on the tensor generalization of the TCN model, and oriented to the stationary operating mode of the network routers interfaces. The scientific novelty and the advantage of the proposed solution is the fact that the established QoS requirements were also satisfied under conditions of the non-stationary operating mode of the network interfaces (Fig. 2, 4). This mode is characteristic for the high utilization of routers and of the network as a whole, which determines the probable application area of this solution.
It is important to note that the practical implementation of the proposed dynamic tensor model of the traffic management in TCN with the support of different classes of service will undoubtedly lead to the complication of the algorithmic-program software of the network routers, after setting the increased requirements for their efficiency. However, during the use of the proposed model in the protocols of the MPLS (Multiprotocol Label Switching) networks it will involve only border routers. It is expedient to use the proposed solution most effectively in the Software-defined Networking (SDN), in which complex computational problems of routing calculations are performed on the corresponding servers of the network operating system. In this case, the productivity of similar routing servers is unquestionably higher than the computational capacities of usual IP-routers. The prospects for improvement of the proposed model of traffic management in the TCN are concerned with the need for expanding functionality of the obtained QoS conditions to the reliability parameters, represented, for example, by the probability of packets losses.
of communication links of the network. Special features of functioning of the network routers interfaces under non-stationary conditions were taken into account. Obtaining these results was possible due to mathematical description of the interfaces operation by the PSFFA model, represented by the system of nonlinear differential equations for estimating the values of the average packets delay.
References
