A software-defined networking is a complex system that consists of a set of end nodes and switching nodes, as well as communication channels that connect them to each other. In such networks, along with the information transmission processes in the communication channels, there are also processes of information sharing that take place and take place at the switching nodes. In a software-defined networking, the central controller manages these distribution processes. Therefore, in the construction of software-defined networking should take into account the quality indicators that characterize these processes. First of all, these indicators are related to delay and loss of messages, errors in the delivery of messages to specific recipients, time of delivery of the data stream, topology of the software-defined networking, etc. They can be described by numerical parametric characteristics, which may be restricted. To design and construct SDNs, developers try to find the values of the characteristics that would optimally satisfy the functioning of the network by minimizing or maximizing its quality. And the tasks of researching and finding such characteristics are inherently multi-criteria. For a complex solution of the general issue of construction a software-defined networking, the article discusses the basic requirements that apply to the criteria in multicriteria tasks. The process of normalization of the parameters of the criterion functions in the formation of the Paretooptimal set of solutions is described and recommendations are given with their subsequent use.
Since the creation of the concept of software-defined networking (SDN), their
optimization has been conducted in three main areas:
─ development of theoretical foundations of packet switching and network flows. In
this direction, the following parameters of the SDN were investigated, such as
network response time, its performance, capacity of resources, indicators of their use,
etc.;
─ development of mathematical methods for optimization of data flows in SDN by
choosing the optimal route of their delivery;
─ scientific and applied researches on development of modern SDN hardware and
software, creation of routing, switching protocols, etc. [
This article deals with the theoretical aspects of the application of multicriteria optimization methods to software-defined networking and refers to the second direction. 2
According to the performed tasks, a software-defined networking is considered as a complex object of research, which is characterized by many features. Describing it, take simultaneously into account many indivisible one of the another characteristics. In other words, for SDN research, a modern systematic approach requires the involvement of the full spectrum of its characteristics.
Since being in different conditions, the network exhibits different system properties, it is necessary to consider not one of its theoretical models, but a set of different, sometimes conceptually contradictory models. However, none of them can be neglected, because each characterizes some property of the SDN under study and none can be accepted as a single one because it does not express the complete set of all properties of the network.
Multiple SDN properties under different conditions can be quantified by appropriate partial criteria. However, contributing to the acquisition of different properties, the corresponding conditions are also evaluated by different partial criteria. Thus, it can be said that mutually exclusive theoretical network models are characterized by contradictory partial criteria, each of which is applied in its own, special conditions and in the values of its special characteristics. And only a complete set of partial criteria makes it possible to adequately evaluate the functioning of the software-switched network. Therefore, a multi-criteria approach with contradictory criteria must be applied to the holistic perception of SDNs in different working conditions. In the general case, the results of solutions of this approach will contain not one but several variants of SDN construction and be in the area of Pareto-optimal (effective) design solutions.
Content essence of many practical problems is the choice of operating conditions SDN that give it an opportunity to show their best qualities. If the conditions, on which these properties depend, are quantitatively expressed by some variables x1, x2 , ..., xm , which are defined on X, then they can be called optimization arguments. In turn, if the properties themselves are also quantified by variables f, then their values will characterize the quality of the network with respect to these properties.
In general, indicators f1, f 2 , ..., f s are called quality criteria and determine vector f { f k }ks1 . Its components quantify the properties of the software-defined networkm ing with a given set of optimization arguments x {xi }i1 X , and the quality of the solution is evaluated by the set of contradictory partial criteria that form sdimensional vector f (x) { fk (x)}ks1 Y , x X , which is defined on the set X. Here, a feasible region X E m is defined and consists of vectors x {xi }i1 of mm dimensional Euclidean space, expression f Y means belonging to the vector f to the class Y of valid efficiency, and vector of partial criteria is limited by the codomain f M .
In addition to the specified conditions, the SDN may also be affected by external,
random factors r. Although these factors are independent, they are known to take their
values from a compact set R, and in calculations consider that this set is given and the
vector of external influences is known [
As a software-defined networking is a multifunctional system, and limitations are imposed on many of its characteristics, the task of research is inherently multicriterion.
In the most general case, to solve such tasks means to find the optimal decision
x* X , which optimizes the efficiency vector under given conditions, relations and
constraints f(x) [
reducing them to a single dimension or to a dimensionless form;
─ a set of partial criteria f f x1, x2 , ..., xm , by which the quality of the network is
evaluated, should be a function of the selected parameters;
─ in turn, the criterion should be considered sensitive to analyzed variants of SDN, in
particular to the selected parameters x1, x2 , ..., xm ;
─ to specify the domain of existence of parameters for unambiguous determination of
their constraints;
─ to provide specified level of network quality and efficiency of its operation;
─ criteria should take into account the assessment of the efficiency performance of
the network main tasks;
─ the criterion should be sufficiently simple and visual, have a clear physical
meaning, so that there are no difficulties in the physical interpretation of the research
results;
─ choosing criteria it is necessary also to take into account the existence of close
links and contradictions between them [
Today, the issue of finding optimal decisions in the problems of criterion research has been given considerable attention. This is confirmed by the large number of publications, and is caused by the fact that this topic covers a very wide range of tasks in a variety of fields.
There are many publications that classify and uncover the various ways and
methods used in multicriteria optimization tasks. Also, many publications are devoted to
disclosing the basic conditions for describing mathematical models of finding optimal
decisions [
Development of a method of finding the optimal variant of construction of the
software-defined networking, which would be economically justified and at the same
time would ensure the fulfillment of the tasks assigned to it and is the purpose of this
article. And as can be seen from the goal, this method will be related to the problem
of multicriteria optimization of complex systems [
As described above, the results of multi-criteria decisions will be in the domain of Pareto-optimal decisions. However, before forming the Pareto-optimal set of variants of SDN construction, it is necessary to clearly define the basic requirements for it. In addition, it is necessary to set clearly the requirements for the criteria functions, their arguments, and also to take into account all the relations between the criteria, their physics and nature. All of these requirements should be an integral part of the process of proving the choice of the optimal SDN construction option.
Characterizing a software-defined networking, its parametric characteristics (PC), in fact, are said to be coordinates of a point in a multidimensional space. In other words, any complex system can be formally described by point coordinates in a multidimensional space of parametric network characteristics. The equation of existence distinguishes in this space the area of technically implemented variants of SDN construction, and the use of models of functioning of this network and methods of evaluating its efficiency provides an opportunity for each point of this area to match the numerical values of the specified criteria.
As is known, there is a method that allows to construct a Pareto-optimal set of
decisions using a quadratic approximation of criterion functions, with given constraints
on parameters and two contradictory criteria. [
For this purpose, each objective function is given as a quadratic polynomial or in matrix form
m m m m f1 x aij xi x j , f 2 x aij xi x j , i0 j0 i0 j0 f1 x A0 2 A1x xT A2 x, f 2 x A0 2 A1x xT A2 x. (1) In this case х is a column vector of SDN parametric characteristics, x T is a transposed column vector of х, А0 is a free term of approximating polynomial, А1 is a vector of approximating coefficients at the first degrees of the parametric characteristics of SDN, which do not multiply with each other, А2 is a symmetric square matrix for the second degrees of parametric characteristics, as well as for parameters that multiply with each other. To find matrices А0, А1 and А2 it is necessary to find the coefficients of the polynomial aij.
Methods of finding polynomial coefficients, as well as arguments for choosing a
quadratic approximation of a criterion function, as described in the second degree
polynomial class, are described in [
After finding the coefficients aij, the matrices А0, А1 and А2 are formed for the
criterion functions, and using the rules of differentiation of the matrix expressions by the
f1 x f 2 x
scalar argument, the values and equals to zero. The values of the
coordx dx
dinates of the unconditional minima of the criteria functions are also found. It is a
point Aopt x11, opt x12 for f1 x , and point Bopt x12 , opt x22 for f 2 x (fig. 1).
If these points belong to the feasible region, the solutions, that meet these points, are
said to be optimal by the criteria f1 x and f 2 x respectively. If the points do not
belong to feasible region, then significant constraints and additional researches, based
on the Lagrange multiplier method, should be introduced [
In the first case, when the criterion surfaces f1x and f 2 x = соnst are multidimensional ellipsoids, and points A and B belong to the feasible region, in the future this case will be considered, we can say that the set of points of the spatial curve AB, which is a locus of adherent points of the second-order lines of the family f1 with lines belonging to the family f 2 , corresponds to set of Pareto-optimal decisions.
However, for further analysis and comparison of the components of the criteria f1x and f 2 x , these components should have the same dimension, that is, be normalized. 5
To reduce the initial families of second order lines f1 and f2 to the same dimension, it is necessary with criterion functions f1x and f2 x to do such orthogonal transformations that would allow to move to the new coordinate system using the replacement of variables, i.e. to move to a new basis, but in the same criterion space.
However, this must be done so that the properties of the initial second-order line families f1 and f 2 do not change according to the moving from the initial coordinate system to the new system and vice versa.
In other words, it is necessary to rotate the coordinate axes of both families of the second-order lines and to move the origin of the coordinates of one of the families.
For further clearness, let’s present a quadratic polynomial in the form (1) if m = 2, f1 x1, x2 a111x12 2a112 x1x2 a122 x22 2a11x1 2a12 x2 a100 , f 2 x1, x2 a121x12 2a122 x1x2 a222 x22 2a12 x1 2a22 x2 a020 . (2) where the upper indices of the coefficients aij correspond to the criterion number, and rotate the coordinate system counterclockwise at an angle . Then the basis vectors е1, е2 move to the new basis vectors, respectively: e~1 cose1 sine2 , e~2 sine1 cose2 .
The old coordinates х1, х2 is expressed by the new coordinates ~x1, ~x2 as: x1 cos x2 ~x1e~1 ~x2e~2 sin csoisn ~x~x12 .
In the new coordinates the quadratic part (1) f 2 x1, x2 looks like: ~x2 csoisn The matrix in parentheses is the product of three matrices A~ QT AQ , moreover А is a symmetric matrix. Hence
A~T QT AQT QT AT QT T QT AQ A~ .
~ So, A =[ a~ij ], 1 i, j 2 , is a symmetric matrix.
Let's try to choose the angle so that the matrix A~ becomes diagonal matrix: So, let’s equate to zero element cos sin sin a11 cos a12 a12 cos
a22 sin sin 1 cos 0 0 2 a12 a~21 cos2 sin 2 a12 sin cos a11 a22 ~ cos2 a12 sin2 a11 a22 0 .
2 If a12 0 , so 0 can be taken. If a12 0 , the following equation must be solved: ctg(2 ) a11 a22 .
2a12 Obviously, the solution of this equation exists. Therefore, there is always such that at which A~ becomes diagonal matrix. In addition, with any choice of , we get: 1 cos2 a11 2 cos sina12 sin 2 a22 , 2 sin 2 a11 2 cos sina12 cos2 a22 .
Hence 1 2 a11 a22 . At the same time, using equality cos sin a11 a12 cos sin 1 0 sin cos a12 a22 sin cos 0 2 , and that the determinant of the product of matrices is equal to the product of the determinants, find 12 a11a22 a122 . Thus, 1 and 2 are roots of the quadratic equation 2 a11 a22 a11a22 a122 0 .
Note that the left-hand side of this equation is true det a11 a12 nomial of is a characteristic polynomial of a matrix a11 a12
a12 . This polya22 aa1222 , so, 1 and 2 are the eigenvalues of this matrix.
It is easy to see that using turning the initial coordinate system by some angle equation f x1, x2 0 is transformed into new coordinates to:
1~x12 2 ~x22 2b13~x1 2b23 ~x2 b33 0 , where b13 b23 a13 a23 csions values of this matrix А2 of a quadratic polynomial (1).
csoisn , b33 a33 , 1 and 2 are the eigen6
It is natural to assume that the quadratic part f 2 in the rotated coordinate system is not identical to zero. Thus, 1 and 2 are not equal to zero at the same time.
Then let’s distinguish in the quadratic part the perfect squares
2 2 2 1~x12 2b13 ~x1 1 ~x12 2 b13 ~x1 b123 b123 1 ~x1 b13 b13 , 1 12 1 1 12 2 ~x22 2b23 ~x2 2 ~x22 2 b223 ~x2 b22223 b22223 2 ~x2 b223 2 b22223 . Let's move the Cartesian coordinate system x1 and ~x2 , and move its origin at the ~ point
O b13 , 1 b23 .
2 z1 ~x1 b13 , z2 ~x2 b23 .
1 2 1z12 2 z22 k 0 , Then new coordinates z1 and z2 will be expressed through ~x1 and ~x2 as follows: In the new coordinates, the equation f x1, x2 0 loses its linear part and looks as where
2 2 k b33 b13 b23 .
12 22
So, by rotating and moving the initial coordinate system, the equations f x1, x2 0 is reduced in new coordinates to kind 1z12 2 z22 k 0 . Moreover, if an equation f x1, x2 0 in any Cartesian coordinate system has this form, then it can have another form in no other Cartesian system. 7
Returning to the issue of normalization, note that a new basis can be constructed by
reducing the quadratic form (1) to the canonical form. As is known, any real
symmetric matrix is orthogonally similar to a real diagonal matrix [
T T AT , T T T 1 , f 1z12 2 z22 ... m z m2 . where
А is a matrix of coefficients aij , Λ is a diagonal matrix of eigenvalues of the matrix А, Т is a matrix of transition or transposition from one basis to another.
In the new variables, the quadratic form (1) is an algebraic sum In general case, for Т only condition of invertibility is required. Finding the appropriate replacement of variables for a given quadratic form is called a canonical form. If Т is an orthogonal matrix, then we are talking about bringing (1) to the principal axes, and the transition is made by expressions
z Tx , and accordingly x T 1z .
But in our case we have two quadratic forms at once f1x and f 2 x , which are second order curves on the plane. It will be wise to try to simplify their equations in a common coordinate system for both. In the general case, this coordinate system will be affine. Note that the points in the affine space are equal, they cannot be stacked with each other. In the affine space, there is also no concept of zero point or start of reference.
Suppose one of the curves is an ellipse. Then move to a Cartesian system, in which the equation is obtained for it x12 a2 x22 b2 1 . The equation of the second curve in this system may have the most general form. Changing the scales along the axes, move to the affine space, in which the equation of the ellipse is the equation of the circle ~x12 ~x22 1. The equation of the second curve in the new (affine) system still has the general form. But using rotation, a form 1z12 2 z22 can be obtained for its quadratic part. However, the rotation of the coordinate system can not change the form of the first equation.
So, let’s have two real symmetric matrices A21 and A2 , which are matrices of coef2 ficients aij of quadratic parts of forms f1 x and f 2 x accordingly, and thus A21 positively defined. In the general case, the positivity of the matrices can be verified using the Sylvester’s criterion.
Then there is the real invertible matrix T such that both matrices T T A21T and T T A22T are diagonal. That is, using the transposition of matrix T, forms f1 x and f 2 x can be simultaneously reduced to a canonical form.
Indeed, because of the positive defining, all the eigenvalues of the matrix A21 , i 0 for all i. Then A21 is orthogonally similar or congruent to a diagonal matrix Λ 1 QT A21Q, 2
QT Q 1 , where Q is a matrix of eigenvectors of the matrix A21 .
Further note that A21 is also congruent to the identity matrix I
I 1 2QT A1Q1 2 Q1 2 T A21 Q1 2 .
2 Let congruence transformation in application to A22 gives a matrix
C Q1 2 T A22 Q1 2 .
c D 1
c . 2 It is easy to verify that С remains a real symmetric matrix. Therefore, using the orthogonal matrix V, which is the matrix of eigenvectors of matrix С, a diagonal matrix D V T CV is obtained. In this case, D is a diagonal matrix of eigenvalues of matrix С V T IV I .
Finally
I T T A21T ,
D T T A22T , where At the same
time, T Q1 2V .
So, in order to normalize the criteria f1 x and f 2 x , that is, to reduce them to the canonical form, it is necessary: ─ to select at least one positive definite quadratic part of these criteria, for example, let in our case be a positive definite quadratic part of the first criterion, i.e. A21 ; ─ find eigenvalues and eigenvectors of a positive definite matrix A21 and add matrices Λ and Q; ─ using the quadratic part of the second criterion A22 and matrices Λ and Q calculate matrix С; ─ find eigenvalues and eigenvectors of matrix С and add matrices D and V; ─ using matrices Λ, Q and V calculate the transpose matrix Т, with a help of which transition to a new basis is executed.
After diagonalization, the criterion functions (2) look like f1 z1, z2 z1 z01 2 z2 z02 2 k1, f 2 z1, z2 1z12 2 z2 2 k2 , or in general case f1 z1, z2 ,...,zm z1 z01 2 z2 z02 2 ... zm z0m 2 k1, f 2 z1, z2 ,...,zm 1z12 2 z2 2 ... m zm 2 k2 .
The transition from the old coordinate system to the new one and vice versa is done using expressions z Tx and x T 1z .
Therefore, using scale variation on the axes, rotation, and moving the coordinate system, the old ellipse family (Fig. 1) can be transformed into a family of circles centered at a point z01, z02 and into a family of deformed ellipses (Fig. 2).
In content terms, the idea of solving the issue of finding Pareto-optimal softwaredefined networking decisions is to determine the equation of the curve АВ in the multidimensional space of the investigated parameters. It was noted above that the Pareto line, or curve АВ, passes through the adherent point of isoquants. Moreover, moving to a new coordinate system, this property is not changed, it is still the locus of adherent points of the second order lines of a new family f1 with lines of family f 2 (Fig. 2).
So, at these points the tangent line and normal to the isoquants of the family f1 coincide with the tangent line and normal to the isoquants of the family f 2 , which allow to form a system of equations of the type df1 x1 x1O x2 x2O
df1 x1 x1O xd2x2 Mx2OO dx1 MO that is M O x1O , x2O AB . where МО is an adherent point, x1O , x2O are coordinates of adherent point.
In order for the adherent point to be Pareto-optimal, it must belong to the curve АВ, In the transition to a new coordinate system value MO x1O , x2O is identical both for family f1 and family f 2 , therefore, in the new coordinate system, the initial equation system looks like this: df1 2z1 z01
dz1 df 2 21z1 dz1 df1 2z2 z02
dz2 df2 22 z2 dz2 z2
z02 1 12 1 z01 z1 .
So, knowing one coordinate of point, the value of another point from a new system of equations can be determined by the formula It can be shown that, in the multidimensional case, the coordinates of the points belonging to the Pareto line, can be determined by a similar formula zm 1 m1 1 zz011 , where
z0m is m-th coordinate of center of family f1 in new coordinate system; m is eigenvalue of the quadratic form f1 .
So, knowing the coordinates of the family center f1 , that is z01, z02 ,...z0m , eigenvalues of the quadratic form f1 , that is 1,2 ,...,m , and changing the coordinate value z1 in the range 0, z01 , it is possible to calculate other coordinates of points belonging to the Pareto line. Application of inverse transformations of the coordinate system allows to obtain Pareto-optimal solutions in the initial coordinate system. 9
Thus, the proposed method allows to obtain from the Pareto-optimal range of criteria by the value of one of any given parameter the whole set of optimal network parameters, as well as the value of the criterion functions in the multidimensional criterion space. The values thus found on the set of several criteria will be the Pareto-optimal values of the software-defined networking construction.
In addition, applying the approaches proposed in the method described in [