Introduction

Providing a specified level of Quality of Service for user requests has been and remains the primary purpose of the functioning of modern infocommunication networks (ICNs), in which various technological means and protocols of distribution and reservation of network resources, traffic management, etc. are involved. At the same time, the problem of QoS provision is exacerbated in the conditions of considerable territorial distribution and heterogeneity of ICNs, which significantly influence the scalability of traffic management solutions. An effective way to increase scalability is to use multi-domain Software-Defined Networks (SDN) when a significant list of traffic management functions is translated to many network operating system controllers, which in turn are built into a clear functional hierarchy [1][2][3][4][5][6].

Assigning a separate controller for each network domain contributes to a significant reduction in the amount of service traffic circulating on the network, the size of the routing tables, and improving the timeliness of traffic management tasks solutions, among which routing is of an important consideration. On the other hand, full implementation of these advantages requires a radical modernization of models, methods, and protocols of routing with their functional adaptation to the features of the hierarchical architecture of SDN-controllers and the multidomain structure of ICNs.

Overview of existing solutions regarding hierarchical routing

Currently the most well-known protocols that implement the principles of hierarchical multi-domain routing are considered to be OSPF and Integrated IS-IS used in IP networks, as well as the somewhat outdated PNNI in the ATM network [4][5][6].

However, these protocols still use Dikstra's combinatorial algorithm to calculate routes, which does not take into account the hierarchical features of network construction. It should also be added that QoS requirements in the same protocols are organized indirectly only through routing metrics, which are usually related to the bandwidth of ICN links and paths. Implementing such an approach does help improve the overall QoS level on the network, but does not guarantee the numerical values of the end-to-end QoS indicators, such as the average packet delay for a particular flow.

A number of solutions have been proposed in scientific papers on hierarchical routing [7][8][9][10][11][12][13][14], which are mainly represented by flow-based models and optimization methods of calculation. In articles [7,8,[12][13][14], such solutions are adapted to the features of SDN architectures. An important feature of the results obtained in [9][10][11] is that they are based on the use of the provisions, principles, and postulates of the theory of hierarchical multilevel systems [15,16]. First, these solutions impose several hierarchical levels of decision-making on routing in ICNs. Second, they imply a decomposition representation of a network mathematical model, which can be described, for example, by a system of differential equations [17]. Third, a mandatory component of hierarchical routing is the coordination process, which is implemented by the top level in relation to the routing decisions of the lower levels.

From the point of view of QoS routing implementation the approach [18][19][20][21][22][23][24] is particularly noteworthy since is based on the use of tensor research methodology, within which it was possible to obtain in an analytical form the conditions for ensuring the Quality of Service on a number of indicators -bandwidth, average delay, probability of packet loss. Therefore, in this paper, we will propose the solution to the problem of hierarchical coordination of inter-domain routing in the Software-Defined infocommunication network with the provision of normalized QoS, that is when the requirements for the level of end-to-end QoS are set for each domain in the form of corresponding norms. The presented solution is a further development and integration of the results obtained in [9-11, 23, 24].

Decomposition model of inter-domain QoS routing in Software-Defined infocommunication network

Suppose that the network structure is represented as an oriented graph ( , ) G R E  , where R is the set of vertices that model the routers and E is the set of graph edges that describes the communication links of the network. In the general case, a packet flow is generated when providing a particular information service on the network. We denote the number of flows circulating in the network by K , then K K   is the power of the set, which quantitatively characterizes the total number of flows in the During network decomposition, the boundary between domains passed through network routers, as implemented, for example, in OSPF [10]:

0 p q R R   and 0 p q E E   , p q  ,(1)

that is, some network routers may belong to several adjacent domains at a time. We . Then, for each p th domain router, the k th flow conservation conditions must be met to ensure the connectivity of intradomain sections of the inter-domain routes.

also

If the p th domain is transit for the k th packet flow, then such conditions take the form:

, , ,, , , , , , , , , , , , , , , , , 1; 0;

1.

p k p k i j j i p k p p p p p B B E E E E in i j j i p k p k i j j i p p p p E E E E i j j i p k p k i j j i p k p p p p p B B E E E E out i j j i x x x x x x                                                          ( 2 )

The system of equations ( 2) must be met separately for each k th packet flow. The first condition of the system (2) covers all the border routers through which the k th flow arrives at the p th domain. The second condition in ( 2) is introduced for internal p th domain routers that are transit for the k th packet flow. The third condition must be satisfied for all border routers through which the k th flow outgoes from the p th domain.

If the k th packet flow arrives at a network through the p th domain, and its source is the router p i R , for example, then for this network the first condition of the system

(2) will be somewhat simplified and will look like: , , , 1

p k i j p p E E i j x   

. The rest of the equations in the system (2) will remain unchanged. When the router p i R from the p th domain is the k th packet flow receiver, only the last equation of system (2) will be simplified and will look as follows:

, , , 1 p k j i p p E E j i x    .

In addition, to prevent links congestion on the p th network domain, it is important to fulfill the following conditions:

, , , p k p k req i j i j k K λ x     , 1, p N  .(3)

Let us denote as

, , , , p k p k k req i j i j k K λ λ x   

as the average intensity of the k th packet flow transmitted in the link ,

p p i j E E 

. Then, when implementing multipath routing, the routing variables are imposed by the constraints: , , 0 1

p k i j x   .(4)

Variables ( 4 In order to ensure inter-domain connectivity, the model ( 1)-( 4) introduces the following inter-domain interaction conditions [10]:

, , k k k k p q p q p q С x С x    , , 1, p q N  , p q  , k K  ,(5)

where

, k p q

С

is the interaction matrix of the p th and q th domains of the size

, , p k p q x m m  ; , p q m

is the number of routers through which the border between the p th and q th domains passes;

, p k x m is the number of coordinates , , p k i j x of the k p x  .

Thus for the network structure shown in Fig. 1 that consists of two domains, the boundary passes through two routers. In the designations of the first domain (Fig. 1) the border routers are 1

1 1 R 1 2 R 2 1 R 1 4 R 2 3 R 2 4 R 1 3 R 2 2 R 1  req 1  req

Terms of providing normalized Quality of Service over domains in the infocommunication network

For each network flow, its transmission rate, average end-to-end delay, and packet loss probability, certain limits are set with respect to their boundary (minimum and/or maximum) values, which determine the level of customer QoS. In case of support of multidomain ICN architecture, the provision of set values of the end-to-end QoS indicators is often realized on the basis of their previous normalization. Let us introduce the following notation:

 k req 

is the requirement for the boundary value of the average end-to-end delay of the k th packet flow in the ICN, which is measured between the incoming router of the source domain and the outgoing receiver router of the k th packet flow;

 , p k req 

is the normalized requirement for the average delay of packets of the k th flow in the ICN p th domain ( ,

p k  ).

Thus, for each flow k K  , the requirements k req  for the average end-to-end delay of packets are distributed (normalized) in some way between separate domains with the following conditions:  . To obtain such conditions it is necessary to use the functionality of tensor analysis of networks. The results presented in [18][19][20][21][22][23][24][25] allowed obtaining analytical expressions for calculating the values of end-to-end QoS indicators, which were evaluated and analyzed between a pair of individual routers. For the case considered in this study, in the structure of an arbitrary network domain, multiple routers may simultaneously belong to each of the sets

. According to the methodology of tensor modeling of ICN [18,19,23,24], the domain structure determines the anisotropic space formed by coordinate paths. Network edges (links), circuits, interpolar paths, and node pairs can act as coordinate paths where the network poles are the routers p in R and p out R . The dimension of this space is determined by the total number of edges in the network and is equal to p n [18,24].

p k p k p p i j j i i in p p p p E E E E i j j i p k p k p p p out i j j i i in p p p p E E E E i j j i p k p k p p out i j j i i p p p p E E E E i j j i x x if R R x x if R R R x x if R R                                    ( 7 ) Domain 2 Domain 1 1 1 R 1 2 R 2 1 R 1 4 R 2 3 R 2 4 R 1 out R 2 2 R 1 3 R 2 in R 1 1 , 2 1 ,

From all possible interpolar (namely, end-to-end from the source to the destination) paths in the p th domain, we choose p  linearly independent  

When routing the k th flow in the selected space, the p th domain can be represented by a mixed bivalent tensor

   T Q

, where  is the tensor multiplication operator and the components of the tensor are a univalent covariance tensor of average packet delays T and a univalent contravariant tensor of the average intensities of flows  in the coordinate paths of the selected domain. Further, the index p in all tensor quantities and their projections will be omitted for greater clarity of information perception, because it is always a question of only physical quantities that are associated with the p th domain. The tensor can be written in the index form:

i i j j q    , ( , 1, p i j n  ),(9)

where j  is the average packet delay along the jth coordinate path (s); i  is the average packet flow intensity along the ith coordinate path (1/s).

In the selected p n -dimensional space, the tensor (9) will be set in one of two coordinate systems. The first is the coordinate system (CS) of the network edges

  , 1, k p v k n 

, the second one is the CS of linearly independent interpolar paths   , 1,

i p i    and internal node pairs   , 1, j p j 

  , the projections of the tensor in which will be denoted by the index  .

In the case of modeling the operation of the network routers interface by the queuing system M/M/1, the coordinates of the projection of the metric tensor G in the basis of edges v G represented by diagonal elements of the matrix will be determined by the expression:

( ) zz z z v v z v g Β     , (10)

where z v  is the intensity of the k th th flow in the z th communication link when using the continuous link numbering; z v Β is the intensity of the aggregated flow in the z th communication link, which is defined as follows:

, , p k z k v req i j x    , , , p k z k v r e q i j k K Β x     under , p p z i j v E  . (11)

Projections of the twice contravariant metric tensor G when changing the CS of its consideration are transformed by the law

t v G AG A   , (12)

where G  is the projection of the metric tensor in the CS of interpolar paths and internal node pairs; A is the ~p p n n  matrix of covariant coordinate transformation in the transition from the CS of interpolar paths and internal node pairs to the basis of edges;   t  is the operation of the matrix transposition.

As shown in [23,24], the matrix G  can be represented as

1 2 3 4 | | G G G G G              ,(13) where )( 1 t G  is the square ~p p    submatrix; ) ( 4 t G  is the square ~p p    sub- matrix; ) ( 2 t G  is the ~p p   submatrix; ) ( 3 t G  is the ~p p    submatrix.

Then, as shown in [22,23], the conditions for ensuring the normalized QoS in the p th domain when routing the k th flow (8) take the form:

1 1 2 4 3 req G G G G T                       ,(14)

where   1   is the matrix inversion operation;   is the p  -dimensional vector of flow intensities in the interpolar paths of the selected domain with coordinates i   that are connected by the following condition

1 i k req i        ; (15)

req T  is the p  -dimensional vector of average packet delays in the interpolar paths of the selected domain, each of which coordinates i   corresponds to the condition

, p k req i     , 1, p i   .(16)

Method of hierarchical coordination inter-domain routing in Software-Defined infocommunication network with provision of normalized QoS

The hierarchical coordination inter-domain routing method will be based on solving an optimization problem for the calculation of vectors of routing variables 7), ( 14)-( 16) by using the following optimality criterion: min ( )

k p x  ( 1, p N  , k K  ) subject to constraints (3)-(k t k k p p p p N k K F , F x H x        ,(17)

where k p H is the diagonal matrix of routing metrics of links of the p th domain.

The goal coordination principle [9-11, 15, 16] will be used to solve the optimization problem (17). Then, moving to the problem at the unconditional extremum, it is necessary to maximize by   the Lagrangian of the form:

, , ,1 11 ( ) ( ) ( )N NN k t k k k t k k k k p p p pq pq p q p q p k K p q k K q p L x H x μ С x С x                    , (18)

where   is the vector of Lagrange multipliers; , p q   are subvectors of the vector   assigned to each of the vector-matrix domain interaction conditions (5).

Given that within the principle of goal coordination, the Lagrange multiplier vectors 

 are calculated at the upper level and for the lower level are values known, the expression ( 18) can be represented in the following decomposition form:

1 N p p L L    , where , , ,, 1 1 ( ) ( ) ( )N N k t k k k t k k k t k k p p p p pq pq p qp pq p k K q q k K k K p p p q p q L x H x μ С x μ С x                        ,(19)

where p K  is the subset of flows incoming to the p th domain from other domains; p K  is the subset of flows outgoing from the p th domain ( ,

p p K K K    ).

Within the framework of the proposed method, the general problem of hierarchical coordination of inter-domain routing is formulated as a two-level optimization problem:

1. At the lower level, SDN controllers of the domains calculate the routing variables represented by vectors k p x  during the minimization of Lagrangians (19) under constraints (3), ( 4), (7), and ( 14)- (16). The results of the calculations are sent to the top level, namely to the SDN controller of the network. 2. At the top level, the SDN controller of the network coordinates the lower-level solutions to ensure that the conditions (5) are met by modifying the Lagrange multiplier vectors:

, , ,( 1) ( )k k k p q p q p q μ a μ a μ       , ,, , ( )k k k p q p q p q p q * μ x С x С x x x        , (20)

where a is the iteration number;

, k p q μ  

is the gradient of the function (19). From the technological point of view, minimizing the number of iterations of the procedure (20), when obtaining the desired optimal solution, aims to reduce the amount of service traffic transmitted between hierarchical levels about the results of calculations at each iteration, and to decrease the total time of solving the problem of inter-domain routing in the ICN as a whole [9][10][11].

6

Investigation of the proposed method of hierarchical coordination inter-domain QoS routing

Let us investigate the proposed method of hierarchical coordination inter-domain routing in the ICN in order to confirm its functionality, adequacy, and efficiency of the obtained calculation results. In the framework of the numerical example, let us analyze the peculiarities of the solutions to the problem of hierarchical coordination inter-domain QoS routing for the variant of the infocommunication network structure shown in Fig. 1. As an example, consider a single-flow case when, in the course of a study, the requirements for the QoS level in a multidomain network were given by the following parameters:

Then Fig. 3 presents a solution to the problem of inter-domain QoS routing prior to the start of the coordination procedure (20). In Fig. 3, the link breaks show the following data (top to bottom): packet flow intensity, bandwidth, and average packet delay in this link.

The characteristic feature of the obtained solution (Fig. 3) is that the conditions for providing the normalized QoS (6), (21) are fulfilled: the maximum end-to-end delay in the first domain was 38.5 ms and in the second domain it was 48.6 ms. However, the conditions for inter-domain interaction (5) were not met. Inter-domain route connectivity was ensured after the third iteration of the coordination procedure (20).

R 1 2 R 2 1 R 1 4 R 2 3 R 2 4 R 1 3 R 2 2

R Fig. 3. The initial solution to the problem of inter-domain QoS routing under requirements (21).

The coordinated solution to the problem of inter-domain QoS routing is presented in Fig. 4, within which the specified normalized values of the average packet delays in each of the domains (21) were provided: in the first domain the maximum end-toend delay was 38.5 ms, and in the second domain it was 58.3 ms.

Conclusion

The paper proposes a method of hierarchical coordination inter-domain routing in SDN, which is a further development of the solutions presented in [9-11, 23, 24]. The novelty of the method is that the routing solutions obtained with it are aimed not only at increasing the scalability of ICN, but also at ensuring the normalized QoS in terms of average transmission rate and end-to-end average packet delay. The proposed method is based on the use of the decomposition flow-based model of inter-domain routing (3)- (7). The model was supplemented by the conditions for the provision of normalized QoS ( 14)-( 16), which were formulated in an analytical form on the basis of tensor modeling of the ICN (8)- (13).

Within the proposed method, the problem of inter-domain QoS routing was presented in the optimization form with a quadratic optimality criterion (17). The goal coordination principle was used to solve the optimization problem. During the study of the method, its functionality and efficiency were confirmed in terms of ensuring the normalized QoS. It was found experimentally that the method converged to the optimal solution for the finite number of iterations (20). For the structure of the network that was selected as the test (Fig. 1), the number of iterations of the coordination procedure (20) with the proper setting of the gradient search did not exceed three iterations. Reducing the number of such iterations helps to decrease the amount of service traffic that is transmitted across the network between routers and SDN controllers at different levels, as well as minimizing the overall time for solving the inter-domain QoS routing task.

The prospect of further research in this area is that the QoS metrics, which each domain should provide, are not set statically, for example, on the SDN controller, but can be redistributed dynamically between domains with the fulfillment of the conditions (6) in accordance with their structure, capacity, and utilization.