Advanced Tensor Solution to the Problem of Inter-Domain Routing with Normalized Quality of Service

Abstract

The advanced tensor solution to the problem of inter-domain routing with normalized Quality of Service under hierarchical coordination in a communication network is proposed in the paper. The novelty of the method based on the tensor model lies in the more flexible load balancing over the network due to the presence of requirements to average end-to-end delay of packets. The framework of the method comprises a decomposed flow-based routing model that includes the inter-domain routing interaction conditions and ensures the normalized Quality of Service derived from the tensor model. Considering the mentioned above, the advanced inter-domain Quality of Service routing task was formulated in the optimization form, using the quadratic optimality criterion. The conducted analysis of the numerical research results confirmed the efficiency and adequacy of the proposed method when the desired solutions were obtained during the finite number of iterations under a provision of the normalized Quality of Service. It should be noted that the reduced number of such iterations during the operation of the method will decrease the amount of service traffic transmitted over the network needed for obtaining the final solution in the process of inter-domain routing with normalized Quality of Service.

1. Introduction

Indeed, the functioning of modern communication networks is due to the provision of a given Quality of Service (QoS) level for user requests. For this purpose, various technological solutions and protocols related to traffic management, resource reservation, and others are involved [1,2,3]. At the same time, the heterogeneity of networks and their territorial distribution affect the provision of both Quality of Service and scalability of traffic management decisions.

An important place among the practical solutions to increase scalability is applying multidomain networks by using software-defined technologies. Such approaches allow for the organization of a precise functional hierarchy, and traffic management functions are performed by appropriate controllers [1,2,3,4,5,6]. In addition, the distribution of network functions between domain controllers allows you to reduce the workload in the interaction of switches and controllers and optimize the routing process in the multidomain data plane [5,6].

However, realizing the benefits of using multidomain Software-Defined Networks (SDNs) requires improving existing routing models and methods, provided that they are adapted to the specifics of the hierarchical SDN architecture and the corresponding network structure.

The primary purpose of implementing SDN-solutions in practice is to increase the efficiency of processes related to ensuring a given level of QoS. The main feature of the softwarized network architectures lies in the fact that the control plane is separated from the data plane (infrastructure), which includes network equipment [7]. Such an approach provides the following advantages:

• Centralized and integrated management of the network and its infrastructure;
• Automation of the network management process;
• Improved information security;
• Reduction of operating and network managing costs;
• Application of cloud technologies for infrastructure purposes.

In practice, for various reasons, including the need for QoS assurance, different types of SDN architectures are used [6,7,8,9,10]. Partial deployment of SDN by placing a limited number of SDN devices along with traditional network equipment forms the so-called hybrid Software-Defined Network (Hybrid SDN, H-SDN), which has a wide range of applications [8,9]. In turn, the promising direction is the use of a concept of Software-Defined Networking in a Wide Area Network (SD-WAN) and multidomain SDN [4,5,10,11,12], the advantages of which are as follows:

• Optimal utilization of network resource (bandwidth);
• Manageability aimed at reducing the cost of the network administration;
• Enhanced capabilities for providing network security;
• Flexibility and scalability when reallocating network bandwidth in differentiated service users flows, which should receive guaranteed network service;
• High performance of SD-WAN, which can be equated to MPLS networks.

In turn, multidomain SDN must provide the interconnection of distinct SDN domains and interoperability between them through domain controllers [5]. Even though SDN offers flexibility in managing the flows inside a network, deploying a multidomain network increases its size and complexity.

The other multidomain SDN challenge is concerned with the controller scalability factor. Usually, a logically centralized control plane consists of a set of distributed controllers, due to reliability issues. Moreover, such an approach allows for load balancing among controllers and reduces the controller’s response time. However, synchronization mechanisms can cause network overload by the overhead. They must be adapted to improve scalability in line with load reduction regarding maintaining sufficient and consistent information about the controller’s states.

Additionally, the controller placement challenge is related to the number of controllers and their location influence on SDN performance [5]. Next, the corresponding communication protocol and coordination method between controllers, essential mechanisms in multidomain SDN, must be selected.

Within the current work, a generalized architecture of hierarchical coordination inter-domain routing with normalized Quality of Service has the following components, as shown in Figure 1. First and foremost, it contains three planes: the data plane; the domain control plane, represented by a set of SDN controllers of the distinct domains; and the control plane with the central SDN controller. Here, the domain control plane optimizes inter-domain routing processes with normalized QoS. In addition, the upper-level control plane is responsible for routing metrics adjustment during multipath calculation. The data plane consists of SDN routers and domain border routers, e.g., SD-WAN routers.

Therefore, the remainder of this article is structured as follows: Section 2 contains a research background in SDN-based inter-domain routing and provides an analysis of existing solutions. Section 3 proposes the decomposition model of inter-domain QoS routing in a communication network. Section 4 focuses on formulating conditions for ensuring end-to-end Quality of Service in a multidomain network. Section 5 is devoted to the method formulation of hierarchical coordination inter-domain routing in communication networks under a provision of normalized QoS. Section 6 contains the numerical research of the proposed hierarchical coordination SDN inter-domain routing method. Finally, Section 7 discusses the obtained research results, and Section 8 presents the conclusions of the work and directions for future investigations.

2. Research Background

Among the conventional hierarchical multidomain routing protocols, well-known OSPF, Integrated IS-IS, and PNNI are traditionally used [1,2,3,11,12]. Nevertheless, these protocols have significant drawbacks, such as using combinatorial algorithms for route calculation and the absence of explicit QoS guaranteeing mechanisms, while routing metrics are mainly based on the bandwidth of the links only. Here the need arises for implementing novel solutions that consider network hierarchy and QoS guarantees in terms of the average end-to-end packet delay for every distinct flow.

Under analysis, some research results concern the multidomain SDN routing and specifics of softwarized architectures [13,14,15,16,17,18,19,20,21]. The most promising solutions are explained in

Table 1. Existing solutions on SDN inter-domain routing.

Reference	Contribution
[13]	The inter-domain communication in Time-Sensitive Networks (TSNs) to achieve end-to-end bounded latency has been proposed. Type of solution: heuristic.
[14]	The Inter-Domain Routing Brokering Plane (IDRBP) aimed at optimal scalability and resource management has been proposed in SDN-based architectures. Type of solution: heuristic.
[15]	The multidomain SDN end-to-end routing mechanism for mobility management has been specified. The optimization-based solution considers bandwidth, number of domains, and flow operations for mobility. Type of solution: optimization.
[16]	The software-defined internetworking (SDI) model has been formulated to extend SDN from intra-domain to inter-domain control. The corresponding prototype for the optimization algorithm has been developed and verified. Type of solution: optimization.
[17]	The new SDN-based Traffic Engineering (TE) method has been developed for large networks to solve intra-domain and inter-domain resource allocation jointly. Type of solution: optimization.

.

An analysis of existing works regarding hierarchical routing shows that the most promising approaches are grounded on flow-based models and optimization methods [15,16,17,22,23,24]. Particular attention should be paid to solutions related to principles and postulates of the hierarchical multilevel systems theory [25,26]. The main feature of such an approach lies in the decision-making hierarchy in the routing process. Moreover, the decomposition within the framework of a network mathematical model is used. In some works, it can be implemented by a system of differential equations [27]. However, in hierarchical routing, upper-level coordination is required, and it concerns the routing decisions of the lower levels.

Regarding QoS routing [19,22,28,29,30,31,32,33], the tensor methodology of network research seems to be relevant [31,32,33]. This class of solutions allows us to obtain the analytical conditions for Quality of Service guaranteed under several indicators, such as average end-to-end packet delay, bandwidth, and packet loss probability.

Therefore, in the present paper, we propose the advanced tensor solution to the problem of inter-domain routing with normalized Quality of Service, with its further application in Software-Defined Networks. The central concept of the approach is providing normalized QoS when the requirements for the end-to-end QoS are set for each domain in the form of corresponding norms. The presented solution further develops the [22,23,24] results.

3. Decomposition Model of Inter-Domain QoS Routing in Communication Network

Suppose that the network structure is represented as an oriented graph $\Gamma =\left(R, \mathrm{W}\right)$, where $R$ is the set of vertices that model routers and $W$ is the set of edges that describe the network links (

Table 2. Notation summary.

Symbol	Meaning
$\Gamma =\left(R, \mathrm{W}\right)$	Oriented graph of network structure
$R$	Set of vertices (routers)s
$W$	Set of edges (network links)
$K$	Number of flows in the network
${\lambda }_{req}^k$	Average packet rate of the kth flow $(k\in K$)
$N$	Number of domains
${\Gamma }^p=\left(R^p,{ \mathrm{W}}^p\right)$	Oriented subgraph of the pth domain
$R^p$	Set of links of the pth domain
$W^p$	Set of links of the pth domain
$m_p$	Number of routers in the pth domain
$n_p$	Number of links in the pth domain
$B^p$	Set of border routers of the pth domain $(B^p\subset R^p$)
$B_{in}^{p,k}$	Subset of the border routers through which the packets of the kth flow income into the pth domain
$B_{out}^{p,k}$	Subset of the border routers through which the packets of the kth flow outgo from the pth domain
${\phi }_{i,j}^p$	Bandwidth of the link $W_{i,j}^p\in W^p$ of the pth domain
$x_{i,j}^{p,k}$	Routing variables that characterize the fraction of the kth packet flow in the link $W_{i,j}^p\in W^p$of the pth domain
${\lambda }_{i,j}^{p,k}$	Average intensity of the kth packet flow in the link $W_{i,j}^p\in W^p$
${\overrightarrow{x}}_p^k$	Routing vector with coordinates ${\overrightarrow{x}}_p^k$ for the kth flow in the pth domain
$C_{p,q}^k$	Matrix of the pth and qth domains interaction
${\tau }_{MP}^k$	Average packet end-to-end delay of the kth flow
${\tau }_{req}^k$	Maximum allowable value for the average packet end-to-end delay of the kth flow
${\tau }_{MP}^{p,k}$	Average packet delay of the kth flow in the pth network domain
$R_{in}^p$	Router through which the kth flow incomes to the network
$R_{out}^p$	Router through which the kth flow outgoes from the network
$V^p$	Set of links belonging to the pth domain (network geometrization)
$n_p^{~}$	Number of routers in the pth domain with imaginary network elements
$m_p^{~}$	Number of links in the pth domain with imaginary network elements
${\kappa }_p^{~}$	Number of linearly independent interpolar paths in the pth domain with imaginary network elements
${\vartheta }_p^{~}$	Number of internal node pairs
$Q$	Mixed bivalent tensor
$T$	Univalent covariance tensor of average packet delays
$\Lambda$	Univalent contravariant tensor of the average flows intensities
$E_v$	Projection of the metric tensor, E, in the coordinate system of edges
$E_{\gamma \epsilon }$	Projection of the metric tensor, E, in the coordinate system of interpolar paths and internal node pairs
${\overrightarrow{\mu }}_{p,q}^k$	Lagrange multiplier vector

). 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 value $\left|K\right|=\tilde{K}$ is the set’s power, which quantitatively characterizes the total number of flows in the network. For each kth flow ($k\in K$), its average packet rate (intensity), ${\lambda }_{req}^k$, is known measured in packets per second (pps) and defines the requirements for the network bandwidth allocated to that flow.

When developing a decomposition model of inter-domain routing, suppose that the network consists of $N$ interconnected subnets—domains. Then let each $p$th individual network domain be described by the graph $\Gamma$ subgraph ${\Gamma }^p=\left(R^p,{ \mathrm{W}}^p\right)$, where $R^p=\left\{R_i^p; i=\overline{1,m_p}\right\}$ is the set of routers of the $p$th domain, $W^p=\left\{W_{i,j}^p; i,j=\overline{1,m_p}, i\ne j\right\}$ is the set of links connecting the routers of the $p$th domain, and $m_p$ and $n_p$ are the total numbers of the routers and communication links in the $p$th domain, respectively.

During network decomposition, the boundary between domains passed through network routers, as implemented, for example, in OSPF [1,11]:

$$R^p{\displaystyle \cap }{R}^q\ne \varnothing \mathrm{and} W^p{\displaystyle \cap }{W}^q=\varnothing , p\ne q.$$

(1)

In other words, some network routers may belong to several adjacent domains at a time. For each pth domain, we also define a set of border routers, $B^p$ ($B^p\in R^p$). In turn, the entire set of the $p$th domain border routers can be divided into two subsets: $B_{in}^{p,k}$ is the subset of the border routers through which the packets of the $k$th flow income into the $p$th domain, and $B_{out}^{p,k}$ is the subset of the border routers through which the packets of the $k$th flow outgo from the $p$th domain. For each communication link, $W_{i,j}^p$, we denote its bandwidth, ${\phi }_{i,j}^p$, which is measured in packets per second (pps).

As a result of solving the hierarchical inter-domain routing problem for each $p$th domain, it is necessary to calculate the routing variables, $x_{i,j}^{p,k}$, that characterize the fraction of the $k$th packet flow transmitted in the link, $W_{i,j}^p\in W^p$. Then, for each $p$th domain router, the $k$th flow conservation conditions must be met to ensure the connectivity of intra-domain sections of the inter-domain routes. If the $p$th domain is transit for the $k$th packet flow, then such conditions take the following form:

$$\{\begin{array}{c}{\displaystyle {\displaystyle \sum }_{B_{in}^{p,k}\in B^p}}\left({\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}\right)=1\\ {\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}=0;\\ {\displaystyle {\displaystyle \sum }_{B_{out}^{p,k}\in B^p}}\left({\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}\right)=-1.\end{array}$$

(2)

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

If the kth packet flow arrives at a network through the $p$th domain, and its source is the router $R_i^p$, for example, then, for this network, the first condition of the system (2) will be somewhat simplified, as shown below:

$${{\displaystyle \sum }}_{W_{i,j}^p\in W^p}{x}_{i,j}^{p,k}=1.$$

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

$${{\displaystyle \sum }}_{W_{j,i}^p\in W^p}{x}_{j,i}^{p,k}=1.$$

In addition, to prevent links overload on the $p$th network domain, it is necessary to fulfill the following conditions:

$${{\displaystyle \sum }}_{k\in K}{\lambda }_{req}^k{x}_{i,j}^{p,k}\le {\phi }_{i,j}^p, p=\overline{1,N}.$$

(3)

Let us denote as ${\lambda }_{i,j}^{p,k}={{\displaystyle \sum }}_{k\in K}{\lambda }_{req}^k{x}_{i,j}^{p,k}$ the average intensity of the kth packet flow transmitted in the link $W_{i,j}^p\in W^p$. Then, when implementing multipath routing, the routing variables are imposed by the following constraint:

$$0\le x_{i,j}^{p,k}\le 1.$$

(4)

Variables (4) are the coordinates of the routing vectors, ${\overrightarrow{x}}_p^k$, that set the result of the solution for the $k$th flow routing problem in the $p$th domain. During the distributed calculation of vectors ${\overrightarrow{x}}_p^k$ across each $p$th domain, it is essential to ensure the structural and functional connectivity of inter-domain routes that are traverse multiple routers of different domains. In order to provide inter-domain connectivity, models (1)–(4) introduce the following inter-domain interaction conditions [22,23,24]:

$${\mathrm{C}}_{p,q}^k{\overrightarrow{x}}_p^k={\mathrm{C}}_{q,p}^k{\overrightarrow{x}}_q^k, p,q=\overline{1,N}, p\ne q, k\in K,$$

(5)

where $C_{p,q}^k$ is the interaction matrix of the $p$th and $q$th domains of the $m_{p,q}\times m_x^{p,k}$ size, $m_{p,q}$ is the number of routers through which the boundary between the $p$th and $q$th domains passes, and $m_x^{p,k}$ is the number of coordinates $x_{i,j}^{p,k}$ of the ${\overrightarrow{x}}_p^k$.

Therefore, for the network structure shown in Figure 2 that consists of two domains, the boundary passes through two routers. In the designations of the first domain (Figure 2), the border routers are $R_3^1$ and $R_4^1$, while in the designations of the second one, the border routers are $R_1^2$ and $R_2^2$. In the gaps of links, their bandwidth is shown.

4. Conditions for Ensuring End-to-End Quality of Service in Multidomain Network

Quality-of-Service requirements are usually set in terms of bandwidth and average packet delay for each flow circulating in the network. Then the refined conditions for providing QoS on the average end-to-end packet delay for each specific kth flow in a multidomain network take the following form:

$${\tau }_{MP}^k\le {\tau }_{req}^k.$$

(6)

The value ${\tau }_{MP}^k$ is measured between the input router of the source domain and the output router receiving the packets of the kth flow. For the network structure example shown in Figure 1, the value ${\tau }_{req}^k$ determines the maximum allowable value for the average end-to-end delay of packets ${\tau }_{MP}^k$ transmitted in the multidomain network between routers $R_1^1$ and $R_4^2$.

Conditions (6), taking into account the multidomain network structure and the additive nature of time metrics ${\tau }_{MP}^k={{\displaystyle \sum }}_{p=1}^N{\tau }_{MP}^{p,k}$, can be represented in the following form:

$${{\displaystyle \sum }}_{p=1}^N{\tau }_{MP}^{p,k}\le {\tau }_{req}^k,$$

(7)

where ${\tau }_{MP}^{p,k}$ is the value of the average packet delay of the kth flow in the pth network domain, which is measured depending on the type of the pth domain, as follows:

• If the pth domain is the source of the kth packet flow, then ${\tau }_{MP}^{p,k}$ determines the value of the average delay of packets transmitted by one or more paths from the source router of this flow to an arbitrary border router from the subset $B_{out}^{p,k}$;
• If the pth domain is the receiver of the kth packet flow, then ${\tau }_{MP}^{p,k}$ characterizes the average delay of packets transmitted by one or more paths from any border router from the subset $B_{in}^{p,k}$ to the receiver router of the same domain;
• If the pth domain is transit for the kth packet flow, then ${\tau }_{MP}^{p,k}$ determines the average delay of packets transmitted by one or more paths between any pair of routers, the first of which belongs to the subset $B_{in}^{p,k}$ and the second one is from the $B_{out}^{p,k}$.

In supporting the multidomain network structure, the provision of required values of end-to-end QoS indicators is often implemented based on their preliminary normalizing [22]. Let ${\tau }_{req}^{p,k}$ be the normalized requirements for the average packet delay of the kth flow in the pth network domain. That is, for each of the flows’ $k\in K$, the requirements for the average end-to-end packet delay, ${\tau }_{req}^k$, are distributed (normalized) in some way between individual domains with the following condition:

$${{\displaystyle \sum }}_{p=1}^N{\tau }_{req}^{p,k}\le {\tau }_{req}^k,$$

(8)

when

$${\tau }_{MP}^{p,k}\le {\tau }_{req}^{p,k}.$$

(9)

Therefore, in the case of ensuring the normalized QoS in a multidomain network, in addition to the value ${\tau }_{req}^k$, the values ${\tau }_{req}^{p,k}$ that must be taken into account when calculating both intra-domain and inter-domain routes are also set in advance. For an example of the network structure, as shown in Figure 1, the value ${\tau }_{req}^{1,1}$ determines the requirements for the average packet delay of the first flow transmitted in the first domain between the routers $R_1^1$ and $R_3^1$ or $R_1^1$ and $R_4^1$. The value ${\tau }_{req}^{2,1}$characterizes the average delay requirements of the first packet flow transmitted in the second domain between the routers $R_1^2$ and $R_4^2$ or $R_2^2$ and $R_4^2$.

Within the framework of this study, it is considered that ${\tau }_{req}^k$ and ${\tau }_{req}^{p,k}$ are predetermined. This raises the problem of formulating the conditions of normalized QoS on the network in terms of calculating expressions for ${\tau }^{p,k}$. It is necessary to use the functionality of tensor analysis of networks to obtain such conditions. The results presented in References [22,23,24] allowed analytical expressions to calculate 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 work, in the structure of an arbitrary network domain, multiple routers may simultaneously belong to each set $B_{in}^{p,k}$ and $B_{out}^{p,k}$. This aspect is a unique characteristic of transit domains. The following methodology is proposed to account for the features of the multidomain network architecture.

• During the kth flow routing for each pth domain, the pair of routers $R_{in}^p$ and $R_{out}^p$ is determined, between which ${\tau }^{p,k}$ is calculated. In the domain that served as the source of the kth packet flow, the $R_{in}^p$ was the router through which the kth flow income to the network. For the domain that served as the kth packet flow receiver, the $R_{out}^p$ was the router through which the kth flow outgo from the network.
• Additional imaginary routers $R_{in}^p$ and $R_{out}^p$, which become adjacent for routers from $B_{in}^{p,k}$ and $B_{out}^{p,k}$ subsets, respectively, through imaginary communication links, are introduced to the network structure at the boundaries of the $p$th domain that interacts with other ones through two or more routers. If the boundary between the $p$th and $q$th domains passes through several routers, as shown, for example, in Figure 2, then the imaginary routers $R_{in}^p$ and $R_{out}^p$ coincide (Figure 3). The introduction of imaginary routers is conditioned by the fact that value ${\tau }^{p,k}$ can now be evaluated and analyzed between a pair of routers $R_{in}^p$ and $R_{out}^p$ based on the approach proposed in Reference [22]. To prevent the impact of packet delays, ${\tau }^{p,k}$, in imaginary communication links connecting real border routers to imaginary ones, their bandwidths must go to $+\infty$ during the calculations.
• The continuous numbering of the communication links in the pth domain is adopted to geometrize the network structure further. For this purpose, the set of network links belonging to the $p$th domain is denoted as $V^p=\left\{v_z^p, z=\overline{1,n_p^{~}}\right\}$, where $n_p^{~}$ and $m_p^{~}$ are the number of communication links and routers in the $p$th domain, respectively, taking into account the introduced imaginary network elements. Thus, for the network structure example, as shown in Figure 3, $n_1^{~}=n_2^{~}=6$ and $m_1^{~}=m_2^{~}=5$. Such an increase in the number of communication links and routers leads to an increase in the number of variables, $x_{i,j}^{p,k}$, with the condition (2) being replaced by the following flow conservation conditions on the $p$th domain routers:

  $$\{\begin{array}{l}{\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}=1, \mathrm{if} R_i^p=R_{in}^p;\\ {\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}=0, \mathrm{if} R_i^p\ne R_{in}^p,R_{out}^p;\\ {\displaystyle {\displaystyle \sum }_{W_{i,j}^p\in W^p}}{x}_{i,j}^{p,k}-{\displaystyle {\displaystyle \sum }_{W_{j,i}^p\in W^p}}{x}_{j,i}^{p,k}=-1, \mathrm{if} R_i^p=R_{out}^p.\end{array}$$

  (10)

According to the methodology of network tensor modeling [22,23,24,32,33], the domain structure determines the anisotropic space formed by coordinate paths. Network edges (links), circuits, interpolar paths, and node pairs can serve as coordinate paths where the network poles are the routers $R_{in}^p$ and $R_{out}^p$. Here, the space dimension is determined by the total number of edges in the network and is equal to $n_p^{~}$ [22].

We choose ${\kappa }_p$ linearly independent $\left\{{\gamma }_i,i=\overline{1,{\kappa }_p}\right\}$ from all possible interpolar paths (namely end-to-end paths from the source to the destination) in the pth domain, whereas the set $\left\{{\epsilon }_j,j=\overline{1,{\vartheta }_p}\right\}$ represents the set of internal node pairs. These sets form the basis of the $n_p^{~}$-dimensional space of the network structure:

$${\kappa }_p^{~}=n_p^{~}-m_p^{~}+2; {\vartheta }_p^{~}=m_p^{~}-2; n_p^{~}={\kappa }_p^{~}+{\vartheta }_p^{~}.$$

(11)

When routing the kth flow in the selected space, the $p$th domain can be represented by a mixed bivalent tensor $Q=T\otimes \Lambda$, where $\otimes$ is the tensor multiplication operator. Here, the components of the tensor are the univalent covariance tensor of average packet delays, $T$, and univalent contravariant tensor of the average flows intensities, $\Lambda$, 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 associated with the pth domain. The tensor can be written in the index form [32,33]:

$$q_j^i={\tau }_j{\lambda }^i, (i,j=\overline{1,n_p^{~}}),$$

(12)

where ${\tau }_j$ is the average packet delay along the jth coordinate path (measured in seconds, s), and ${\lambda }^i$ is the average packet flow intensity along the ith coordinate path (pps).

The tensor (12) is set in one of two coordinate systems in the selected $n_p^{~}$-dimensional space. The first is the coordinate system (CS) of the network edges $\left\{v_k,k=\overline{1,n_p^{~}}\right\}$. The second one is the CS of linearly independent interpolar paths $\left\{{\gamma }_i,i=\overline{1,{\kappa }_p}\right\}$ and internal node pairs $\left\{{\epsilon }_j,j=\overline{1,{\vartheta }_p}\right\}$, where the index $\gamma \epsilon$ denotes the tensor projections.

In the case of modeling the operation of the network router interface by the queuing system M/M/1 [32], the coordinates of the metric tensor ($E$) projection in the basis of edges ($E_v$) represented by diagonal elements of the matrix are determined by the following expression:

$$e_v^{zz}={\left[{\lambda }_v^z\left({\phi }_z-{{\rm B}}_v^z\right)\right]}^{-1},$$

(13)

where ${\lambda }_v^z$ is the intensity of the $k$th flow in the $z$th communication link when using the continuous link numbering; ${{\rm B}}_v^z$ is the intensity of the aggregated flow in the $z$th communication link, which is defined as follows:

$${\lambda }_v^z={\lambda }_{req}^k{x}_{i,j}^{p,k}, {{\rm B}}_v^z={{\displaystyle \sum }}_{k\in K}{\lambda }_{req}^k{x}_{i,j}^{p,k} \mathrm{under} v_z^p=E_{i,j}^p.$$

(14)

Projections of the twice-covariant metric tensor, $E$, when changing the coordinate system of its consideration are transformed by the following law:

$$E_{\gamma \epsilon }={(C_{\gamma \epsilon }^v)}^t{E}_v{C}_{\gamma \epsilon }^v,$$

(15)

where $E_{\gamma \epsilon }$ is the projection of the metric tensor in the CS of interpolar paths and internal node pairs, $C_{\gamma \epsilon }^v$ is the $n_p^{~}\times n_p^{~}$ matrix of contravariant coordinate transformation in transition from the CS of interpolar paths and internal node pairs to the basis of edges, and ${[\cdot ]}^t$ is the operation of the matrix transposition.

As shown in References [32,33], the matrix $E_{\gamma \epsilon }$ can be represented as follows:

$$E_{\gamma \epsilon }=\left|\right|\begin{array}{ccc}{E}_{\gamma \epsilon }^{\langle 1\rangle }& |& E_{\gamma \epsilon }^{\langle 2\rangle }\\ ---& +& ---\\ E_{\gamma \epsilon }^{\langle 3\rangle }& |& E_{\gamma \epsilon }^{\langle 4\rangle }\end{array}\left|\right|,$$

(16)

where $E_{\gamma \epsilon }^{\langle 1\rangle }$ is the square ${\kappa }_p^{~}\times {\kappa }_p^{~}$ submatrix, $E_{\gamma \epsilon }^{\langle 4\rangle }$ is the square ${\vartheta }_p^{~}\times {\vartheta }_p^{~}$ submatrix, $E_{\gamma \epsilon }^{\langle 2\rangle }$ is the ${\kappa }_p^{~}\times {\vartheta }_p^{~}$ submatrix and $E_{\gamma \epsilon }^{\langle 3\rangle }$ is the ${\vartheta }_p^{~}\times {\kappa }_p^{~}$ submatrix.

Ensuring compliance with QoS conditions (7) or (8), (9) is associated with the need for analytical calculation of delay values ${\tau }_{MP}^{p,k}$ in each network domain. The solution of this problem under conditions (2) is based on the use of the results obtained by the following [22]:

$${\tau }_{MP}^{p,k}=\frac{{\Lambda }_{\gamma }^t{E}_{\gamma \epsilon }^{\langle 1\rangle }{\Lambda }_{\gamma }}{{\lambda }_{req}^k},$$

(17)

where the components of the numerator in terms of geometrization and metrization of the network tensor model are tied, firstly, to the structure of the pth network domain and its links parameters, and secondly, to the characteristics of the kth packet flow. Then the conditions for Quality of Service for the average end-to-end delay of the kth packet flow and bandwidth in the pth network domain (9) can be written in more detail:

$$\frac{{\Lambda }_{\gamma }^t{E}_{\gamma \epsilon }^{\langle 1\rangle }{\Lambda }_{\gamma }}{{\lambda }_{req}^k}\le {\tau }_{req}^{p,k}.$$

(18)

However, Equation (17) is valid for the case of a bipolar pth network domain structure, i.e., where the packets of the kth flow are transmitted from one border router from the set $B_{in}^{p,k}$ (source router) to another border router from the set $B_{out}^{p,k}$ (receiver router). Therefore, depending on the specifics of the structural construction and relation of individual network domains, the application of (18) in solving problems of inter-domain QoS routing has specific features.

5. Method of Hierarchical Coordination Inter-Domain Routing in Communication Network under Provision of Normalized QoS

The hierarchical coordination inter-domain routing method is based on solving an optimization problem for the calculation of vectors of routing variables ${\overrightarrow{x}}_p^k$ ($p=\overline{1,N}$, $k\in K$) subject to constraints (3)–(5), (8)–(10), and (18) by using the following optimality criterion:

$$min F, F={{\displaystyle \sum }}_{p\in N}{{\displaystyle \sum }}_{k\in K}{({\overrightarrow{x}}_p^k)}^t{H}_p^k{\overrightarrow{x}}_p^k,$$

(19)

where $H_p^k$ is the diagonal matrix of routing metrics of the $p$th domain links.

The goal coordination principle [9,10,11,15,16] solves the optimization problem (19). Then, moving to the problem at the unconditional extremum, it is necessary to maximize by $\overrightarrow{\mu }$ the Lagrangian of the form:

$$L={{\displaystyle \sum }}_{p=1}^N{{\displaystyle \sum }}_{k\in K}{({\overrightarrow{x}}_p^k)}^t{H}_p^k{\overrightarrow{x}}_p^k+{{\displaystyle \sum }}_{p=1}^N{{\displaystyle \sum }}_{\begin{array}{c}q=1\\ q\ne p\end{array}}^N{{\displaystyle \sum }}_{k\in K}{({\overrightarrow{\mu }}_{p,q}^k)}^t\left({\mathrm{C}}_{p,q}^k{\overrightarrow{x}}_p^k-{\mathrm{C}}_{q,p}^k{\overrightarrow{x}}_q^k\right),$$

(20)

where $\overrightarrow{\mu }$ is the vector of Lagrange multipliers, and ${\overrightarrow{\mu }}_{p,q}$ are subvectors of the vector $\overrightarrow{\mu }$ assigned to each vector–matrix domain interaction condition (5).

Given that within the principle of goal coordination, the Lagrange multiplier vectors $\overrightarrow{\mu }$ are calculated at the upper level, and for the lower level are values are known, the expression (20) can be represented in the following decomposition form: $L={{\displaystyle \sum }}_{p=1}^N{L}_p$, where

$$L_p={{\displaystyle \sum }}_{k\in K}{({\overrightarrow{x}}_p^k)}^t{H}_p^k{\overrightarrow{x}}_p^k+{{\displaystyle \sum }}_{\begin{array}{c}q=1\\ p\ne q\end{array}}^N{{\displaystyle \sum }}_{k\in K_p^{+}}{({\overrightarrow{\mu }}_{p,q}^k)}^t{\mathrm{C}}_{p,q}^k{\overrightarrow{x}}_p^k-{{\displaystyle \sum }}_{\begin{array}{c}q=1\\ p\ne q\end{array}}^N{{\displaystyle \sum }}_{k\in K_p^{-}}{({\overrightarrow{\mu }}_{q,p}^k)}^t{\mathrm{C}}_{p,q}^k{\overrightarrow{x}}_p^k,$$

(21)

where $K_p^{+}$ is the subset of flows incoming to the $p$th domain from other domains, and $K_p^{-}$ is the subset of flows outgoing from the $p$th domain ($K_p^{+},K_p^{-}\subset K$).

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

• At the lower level, SDN controllers of the domains calculate the routing variables represented by vectors ${\overrightarrow{x}}_p^k$ during the Lagrangians (21) minimization under constraints (3), (4), (10), and (18). The results of the calculations are sent to the upper level, namely to the SDN controller.
• At the upper level, the SDN controller coordinates the lower level solutions to ensure that the conditions (5) are met by modifying the Lagrange multiplier vectors:

  $${\overrightarrow{\mu }}_{p,q}^k\left(a+1\right)={\overrightarrow{\mu }}_{p,q}^k\left(a\right)+\nabla {\overrightarrow{\mu }}_{p,q}^k, \nabla {\overrightarrow{\mu }}_{p,q}^k\left(x\right)|\begin{array}{c}\\ x=x^{*}\end{array}={\mathrm{C}}_{p,q}{\overrightarrow{x}}_p^k-{\mathrm{C}}_{q,p}{\overrightarrow{x}}_q^k,$$

  (22)

  where $a$ is the iteration number, and $\nabla {\overrightarrow{\mu }}_{p,q}^k$ is the function (21) gradient.
• The modified values of the Lagrange multiplier vectors ${\overrightarrow{\mu }}_{p,q}^k$ are transmitted to the lower level to calculate new routing vectors, ${\overrightarrow{x}}_p^k$. The calculation process becomes iterative. Inter-domain route connectivity will be ensured when the gradient values (20) approach zero.

From the technological point of view, minimizing the number of iterations of the procedure (22) 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 network as a whole [22,23,24].

6. Numerical Research of the Proposed Method of Hierarchical-Coordination Inter-Domain Routing in Communication Network under Provision of Normalized QoS

We studied the proposed hierarchical coordination inter-domain routing method in the communication network to confirm the efficiency and adequacy of the obtained numerical results. Within the calculation example, we analyzed the nature of the solutions to the hierarchical coordination inter-domain QoS routing for the variant of the network structure, which is shown in Figure 2. The network consists of two domains (Figure 2). The first and second domains contain four routers:

$$R^1=\left\{R_1^1,R_2^1,R_3^1,R_4^1\right\}, R^2=\left\{R_1^2,R_2^2,R_3^2,R_4^2\right\}.$$

The interaction between domains is carried out via routers $R_3^1$ ($R_1^2$) and $R_4^1$ ($R_2^2$). Let the packet source node be the router $R_1^1$ in the first domain and the receiver node $R_4^2$ in the second domain, respectively. The gaps in communication links (Figure 1) show their bandwidth (pps). The matrix’s main diagonal $H_p^k$ (19) is the values $\frac{{10}^8}{{\phi }_{i,j}^p}$ by analogy with the values of routing metrics used in the OSPF protocol [1,2]. The operation of each router interface was simulated by using the queueing system M/M/1.

For example, consider a single flow case when the following parameters set the requirements for the QoS level in a multidomain network: ${\lambda }_{req}^1=350$ pps and ${\tau }_{req}^1=80$ ms. In the first case, the normalizing of the QoS level between the network domains by the average delay was carried out as follows:

$${\tau }_{req}^{1,1}=30 \mathrm{ms}, {\tau }_{req}^{2,1}=50 \mathrm{ms}.$$

(23)

Then Figure 5 shows the initial problem solution of inter-domain QoS routing, i.e., before starting the coordination procedure (22). This figure shows the following data in the link gaps (from top to bottom): packet flow intensity, bandwidth, and the average packet delay in this communication link (ms). A characteristic feature of the obtained solution (Figure 5) is that the conditions for providing normalized QoS (8) are met. The average end-to-end delay in the first domain from the source router, $R_1^1$, to the domain boundary was 25.6 ms, while in the second domain, from the domain boundary to the receiving router, $R_4^2$, it was equal to 34.88 ms (

Table 3. Characteristics of the calculated routes in Figure 5.

Domain	${\mathit{\lambda }}_{\mathit{r}\mathit{e}\mathit{q}}^1, \mathbf{pps}$	$\left|\mathit{P}\right|$	Characteristics of the Calculated Paths			${\mathit{\tau }}_{\mathit{M}\mathit{P}}^{\mathit{p},1}, \mathbf{ms}$
			Route	${\mathit{\lambda }}_{\mathit{p}}, \mathbf{pps}$	${\mathit{\tau }}_{\mathit{p}}, \mathbf{ms}$
1	350	3	$R_1^1\to R_2^1\to R_3^1$	45.5	13	25.6
			$R_1^1\to R_2^1\to R_4^1$	130.5	12.7
			$R_1^1\to R_4^1$	174	38.5
2		3	$R_1^2\to R_4^2$	129.43	48.6	34.88
			$R_1^2\to R_3^2\to R_4^2$	76.69	17.1
			$R_2^2\to R_3^2\to R_4^2$	143.88	32

).

However, there was no interconnection of inter-domain routes, because the conditions of inter-domain interaction (5) in the case of Lagrangians (21) minimization were not met, since the route for each domain is calculated independently on the appropriate SDN domain controllers.

To ensure the connectivity of inter-domain routes within the presented method, a coordination procedure (22) was used that is proposed for implementation on the SDN controller. Thus, Figure 6 shows the routing order in a multidomain network after the first iteration of the coordination procedure (22), when conditions (5) were not met again. However, the average end-to-end packet delays in the domains met the norms (23) and amounted to 26.16 and 32.64 ms, respectively.

Inter-domain route connectivity was ensured only after the third iteration of the coordination procedure (22). The coordinated solution of the inter-domain QoS routing problem is presented in Figure 7. The specified normalized values of average packet delays (23) were provided in each domain. In the first domain, the maximum end-to-end delay was 26.84 ms, and in the second, it was 44.24 ms (

Table 4. Characteristics of the calculated routes in Figure 7.

Domain	${\mathit{\lambda }}_{\mathit{r}\mathit{e}\mathit{q}}^1, \mathbf{pps}$	$\left|\mathit{P}\right|$	Characteristics of the Calculated Paths			${\mathit{\tau }}_{\mathit{M}\mathit{P}}^{\mathit{p},1}, \mathbf{ms}$
			Route	${\mathit{\lambda }}_{\mathit{p}}, \mathbf{pps}$	${\mathit{\tau }}_{\mathit{p}}, \mathbf{ms}$
1	350	3	$R_1^1\to R_2^1\to R_3^1$	131.53	16.5	26.84
			$R_1^1\to R_2^1\to R_4^1$	44.47	11.4
			$R_1^1\to R_4^1$	174	38.5
2		3	$R_1^2\to R_4^2$	87.66	16	44.24
			$R_1^2\to R_3^2\to R_4^2$	43.87	30.5
			$R_2^2\to R_3^2\to R_4^2$	218.47	58.3

).

In the second case (Figure 8, Figure 9 and Figure 10), the normalizing of the QoS level between the network domains by the average end-to-end packet delay was carried out in the reverse way:

$${\tau }_{req}^{1,1}=50 \mathrm{ms}, {\tau }_{req}^{2,1}=30 \mathrm{ms}.$$

(24)

Meanwhile, other QoS requirements remained unchanged:

$${\lambda }_{req}^1=350 \mathrm{pps} \mathrm{and} {\tau }_{req}^1=80 \mathrm{ms}.$$

The initial solution of the inter-domain QoS-routing problem under the requirements (24) is shown in Figure 8. As before, the following data are indicated in the link gaps (from top to bottom): packet flow intensity, bandwidth, and average packet delay in this communication link (ms). Fulfillment of QoS requirements (24) was confirmed by the fact that the maximum end-to-end delay in the first domain was 35.83 ms, and in the second domain, it was 26.71 ms, but the connectivity of inter-domain routes was not ensured.

For the coordination of routing solutions, as in the previous variant of the calculations, three iterations of the coordination procedure were enough (22). The result obtained after the first iteration is presented in Figure 9, and the coordinated solution of the inter-domain QoS routing problem under the normalized requirements (24) is shown in Figure 10.

Within this solution, it was possible to ensure not only the connectivity of inter-domain routes but also the normalized Quality of Service for the average end-to-end packet delays at 37.81 ms for the first network domain and 21.92 ms for the second one, which met the established requirements (24) (

Table 5. Characteristics of the calculated routes in Figure 10.

Domain	${\mathit{\lambda }}_{\mathit{r}\mathit{e}\mathit{q}}^1, \mathbf{pps}$	$\left|\mathit{P}\right|$	Characteristics of the Calculated Paths			${\mathit{\tau }}_{\mathit{M}\mathit{P}}^{\mathit{p},1}, \mathbf{ms}$
			Route	${\mathit{\lambda }}_{\mathit{p}}, \mathbf{pps}$	${\mathit{\tau }}_{\mathit{p}}, \mathbf{ms}$
1	350	3	$R_1^1\to R_2^1\to R_3^1$	146	17.1	37.81
			$R_1^1\to R_2^1\to R_4^1$	21.4	10.5
			$R_1^1\to R_4^1$	182.6	57.5
2		3	$R_1^2\to R_4^2$	105.2	22.3	21.92
			$R_1^2\to R_3^2\to R_4^2$	40.8	22
			$R_2^2\to R_3^2\to R_4^2$	204	21.7

).

Accordingly, the proposed method can be utilized as the basis of the algorithmic software of the central controller and domain controllers. Furthermore, the results of calculating routes (Table 5) on the controllers were used to form a forwarding table on SDN data plane network elements (routers) about the multipath routing across the SDN domains. Therefore, in

Table 6. Forwarding order for inter-domain QoS routing shown in Figure 10.

Calculation Results on the First Domain Controller
Destination|domain	Next Hop|domain	Fraction of flow (balancing order)
For $R_1 | 1$
$R_4 | 2$	$R_2 | 1$	0.48
	$R_4 | 1$	0.52
For $R_2 | 1$
$R_4 | 2$	$R_3 | 1$	0.87
	$R_4 | 1$	0.13
Calculation Results on the Second Domain Controller
Destination	Next Hop|domain	Fraction of flow (balancing order)
For $R_1 | 2$
$R_4 | 2$	$R_3 | 2$	0.28
	$R_4 | 2$	0.72
For $R_2 | 2$
$R_4 | 2$	$R_4 | 2$	1
For $R_3 | 2$
$R_4 | 2$	$R_4 | 2$	1

, the results of calculations on domain controllers indicate the directives for data-plane routers on routing packet flows and the order of their balancing in the network.

7. Discussion

The demands that motivated the creation and modification of SDN inter-domain routing solutions can be formulated as follows:

• Accounting for multidomain network structure;
• Ensuring the connectivity of inter-domain routes and the order of balancing across inter-domain routes;
• Guarantying the QoS level, both within domains and end-to-end Quality of Service;
• Support for multipath routing with load balancing to ensure more efficient use of the network resource;
• Implementation of hierarchical routing with coordination of decisions obtained in separate domains;
• Providing a high convergence rate of the coordination procedure to reduce the time required to solve the problem of hierarchical multidomain routing and decrease the amount of overhead traffic associated with coordination.

The decomposition model of inter-domain routing (1)–(18) was further developed to ensure the Quality of Service in the network, consisting of many series-connected domains. The model was based on the conditions for the implementation of multipath routing (4), conditions for the flow conservation (2), preventing overload of links and the network in general (3), and conditions for inter-domain interaction (5) guaranteeing the routes connectivity. The flow-based model of inter-domain routing was supplemented by the conditions of providing end-to-end and normalized Quality of Service (6)–(9).

The novelty of the proposed routing model is the modification of flow-conservation conditions (10), which allowed us to formulate conditions for ensuring the end-to-end Quality of Service in multidomain networks in terms of bandwidth and average end-to-end packet delay ((17) and (18)). It was possible to formulate in analytical form the conditions of QoS assurance ((17) and (18)) based on tensor network modeling in geometric space, which was created by coordinate paths of edges (links), interpolar paths, and internal node pairs.

A method of hierarchical coordination routing in multidomain Software-Defined Networks (18)–(22) with the provision of normalized Quality of Service is a further development of the solutions presented in References [22,23,24]. The routing solutions obtained with its help are aimed at increasing network scalability. The novelty of the method is the provision of domain-normalized average end-to-end packet delay when the normalized Quality of Service requirements are met in each domain separately (18) and routing solutions are coordinated under inter-domain interaction (5).

Numerical studies have shown that the convergence rate of the coordination procedure, namely the number of coordination iterations, was influenced by the following main factors:

• Number of domains in the network;
• Structure and size of domains;
• Number of border routers;
• Network congestion;
• Implementation of multipath routing strategy.

As the number of border routers increased, the number of iterations in the general case also increased, expanding the time to solve the inter-domain routing problem. Figure 11 shows the dependence of the number of iterations of the coordination procedure on the number of network domains, with the number of border routers equal to two.

8. Conclusions

In summary, the work proposed and investigated the method of hierarchical-coordination inter-domain routing in a Software-Defined Network, with the provision of normalized Quality of Service. The study of several numerical examples confirmed the efficiency of the proposed method. This method provides an adaptive nature of packet flow routing under changing requirements (norms) for the Quality-of-Service level in terms of the average end-to-end packet delay, bandwidth in the network, and its distinct domains.

Within the framework of the proposed method, the problem of inter-domain QoS routing was presented in an optimization form with a quadratic optimality criterion (19). The principle of goal coordination from the theory of hierarchical multilevel control systems is used to solve the optimization problem. This mathematical apparatus allowed us to correctly formulate and ensure the solution of problems that are assigned to two hierarchical levels. The lower level (level of SDN domain controllers) was responsible for calculating intra-domain routes based on minimizing expression (21) according to constraints (3), (4), (8), (10), and (18). The upper level (network SDN controller level) was responsible for coordinating the lower-level solutions by fulfilling the conditions of inter-domain interaction (5) to ensure the consistency of inter-domain routes within the gradient procedure (22). Coordination of routing solutions was completed in the case of approaching the gradient (22) to zero.

The study of the proposed method of inter-domain QoS-routing on several computational examples confirmed its efficiency in ensuring normalized Quality of Service. It is experimentally established that the method converged to the optimal solution for a finite number of iterations (22). For the network structure selected as a test (Figure 2), the number of iterations of the coordination procedure (22) provided the appropriate setting of the gradient search and did not exceed three. Reducing the number of such iterations helps decrease the amount of service traffic transmitted on the network between routers and SDN controllers at different levels and minimize the overall time to solve the problem of inter-domain QoS routing.

The method provided the high scalability of routing solutions, as routing tasks in individual domains were solved independently based on local information about the status of communication links and routers of these domains that positively affects the efficiency of network management and overhead. In ensuring the normalized Quality of Service in multidomain SDN, the main problem was coordinating the order of routing at the domain border, which passed through more than one router. The studies confirmed the convergence of the method to the desired optimal solutions for a finite number of iterations, on average, for two or three iterations. The number of such iterations could increase critically (to 6–8) only if the Quality-of-Service level norms in the domains met these domains’ limits.

Future research is concerned with improving the presented method by enhancing its flexibility and providing end-to-end Quality of Service without prior normalizing. In addition, modifications will be made to the mathematical model by using other types of coordination, such as predicting and evaluating interactions.