Using of the contour method to solving the problem of optimal traffic dis-tribution in the network

全文:

Introduction

Currently, when network technologies are developing at a rapid pace, and the number of devices in the network is steadily growing, telecom operators are faced with the task of increasing the transmitted traffic quality and flexible balancing of incoming traffic without loss of network performance. Changing the bandwidth of communication channels, adding new channels and nodes to the topology leads to a complete recalculation of routing tables.

One of the ways to improve the quality of network functioning is to determine the optimal data transmission routes that implement a routing policy in which one or more optimality criteria are achieved. Such criteria can be the minimum delay and/or loss in the transmission of information both for individual routes or channels and the total, thereby achieving a more balanced load of communication channels.

Modern dynamic routing protocols, such as OSPF [1] and IS-IS [2], allow bypassing busy communication channels to improve the quality of network services. However, with frequent route updates, additional computing resources are needed to activate and install the new route. Multipath routing protocols, as a rule, apply the k-shortest paths algorithm (Yen’s algorithm) used for technical solutions [3]. As an example, we can consider the MPLS-TE module [4; 5], which works with routes calculated using the above algorithm. This allows balancing the load by distributing network traffic along backup routes.

In addition, there are many upgrades and customisations of these methods. Thus, in [6-9] multipath routing models with load balancing based on GERT networks and minimizing planimetric delays for each type of traffic are proposed. In [10] an adaptive routing algorithm on neural networks is studied. In [11] a method involving load balancing with multipath routing is considered, based on the algorithm of paired route permutations, in [12; 13] the rapid IP FRR routing technologies are analyzed.

Despite an impressive list of works and various technical implementations in the form of computer programs [14-17], existing mechanisms do not solve the problem of optimal traffic in terms of losses. That is why this paper has developed and described a mathematical model of the network applying the contour method of traffic analysis by the criterion of minimizing losses.

 1. Bringing the network to a contour view

Suppose we are given a network where the packet loss probability function is known for each communication channel. In the most trivial case, this functional dependence will be determined by the size of the buffer of the telecommunication device to which the communication channel is connected, the data transfer rate of the communication channel, and the statistical characteristics of the flow passing through it. If this is possible, then as such a functional dependence we can use already existing formulas describing the probability of losses for various types of queuing systems. In reality, the dependence of flow losses depends on many factors that are determined by the logic of the software and hardware of a telecommunications device.

To obtain a mathematical model of traffic distribution over the network, it is convenient to represent the network in the form of a directed graph. We define the construction rule: each direction of data transmission between a pair of telecommunication devices will be a directed edge of the graph, the models of telecommunication nodes will correspond to the vertices of the graph. One additional edge will also exit from each node; this edge is a channel through which traffic, lost as a result of buffer overflow of telecommunication devices, will be transmitted. Fig. 1 shows a network consisting of two switching nodes SN1 and SN2. Users who simultaneously receive and transmit data are connected to SN1; in the figure they are designated as sourse and receiver SR1. Similarly, SR2 is connected to SN2. Each channel in Figure 1 is duplex, losses occur at each switching node.

 

Рис. 1. Модель сети

Fig. 1. Network model

 

Based on the above, Fig. 2 shows a network graph where nodes 1 and 2 correspond to traffic sources; edges 1 and 2 are channels connecting the corresponding sources to switching nodes. Nodes 3 and 4 correspond to the traffic receiver; edges 3 and 4 are channels connecting the corresponding receivers to the switching nodes. Thus, pairs of nodes 1 and 3 correspond to SR1; edges 1 and 3 correspond to a duplex channel between SR1-SN1; a pair of nodes 2 and 4 corresponds to SR2, edges 2 and 4 correspond to a duplex channel between SR2-SN2. Node 7 terminates losses from incoming channels to node 5, node 8 terminates losses from incoming channels to node 6, and edges numbered 7 and 8 are traffic reset channels connecting switching nodes with reset termination nodes. Nodes 5 and 6 denote the switching nodes SN1 and SN2, respectively. If channels 7 and 8 as well as nodes 7 and 8 are removed from the network in Fig. 2, then the resulting network will be a lossless network (Fig. 3).

 

Рис. 2. Представление сети с потерями в виде графа

Fig. 2. Graph representation of a lossy network

 

A contour network is a network that does not contain open circuits. Any network can be represented as a contour, ensuring the circulation of the flow in the network. To ensure the flow circulation in the network, it is necessary to close all nodes that have only one edge incident, combining them into one node. This guarantees the equality of the sum of flows entering the node and the sum of flows leaving the node. Thus, for the example considered in Fig. 2 and 3 we need to combine nodes 1 through 4, as well as 7 and 8 (for a lossy network) into one common node. Graphically, such a network is shown in Fig. 4 and 5, respectively.

Рис. 3. Представление сети без потерь в виде графа

Fig. 3. Graph representation of a lossless network

 

Рис. 4. Результат приведения сети с потерями к контурному типу

Fig. 4. The result of reducing a lossy network to a contour form

 

Рис. 5. Результат приведения сети без потерь к контурному типу

Fig. 5. The result of reducing a lossless network to a contour form

 

As can be seen in Fig. 4, nodes 1 through 4 plus nodes 7 and 8 were combined into node 0, and nodes 1 through 4 were combined for the network in Fig. 5. For the resulting networks, it is necessary to determine the contour matrix.

Note that a source is not a single source of information, but a set of independent sources, for example, a PC on a local network. Thus, statistically multiplexed flows pass through the channel connected to the sources in Fig. 1.

 2. Contour method of data analysis

We enter variables that will be used when composing mathematical models:

 $V$– the set of all vertices of the graph;

 $\left|V\right|$– the number of vertices of the graph;

 $E$– the set of all edges of the graph;

 $\left|E\right|$– the number of edges of the graph;

 $E_h$– the subset of the edges of the graph that are chords;

 $\left|E_h\right|$– the number of edges in the set $E_h$;

 $E_b$– the subset of the edges of the graph that are branches;

 $\left|E_b\right|$– the number of edges in the set $E_b$;

 $E_{src}$– the subset of the edges of the graph to which information sources are connected;

 $\left|E_{src}\right|$– the number of edges in the set $E_{src}$;

 $E_{rcv}$– the subset of the edges of the graph to which the recipients of information are connected;

 $\left|E_{rcv}\right|$– the number of edges in the set $E_{rcv}$;

 $E_{tr}$– the subset of the edges of the graph that connect nodes that are switching nodes;

 $\left|E_{tr}\right|$– the number of edges in the set $E_{tr}$;

 $E_{loss}$– te subset of the edges of the graph, which are the channels of information reset;

 $\left|E_{loss}\right|$– the number of edges in the set $E_{loss}$.

 

According to graph theory, any graph can be described by an incidence matrix; the incidence matrix without a linearly dependent row is a matrix of linearly independent sections, which in turn is orthogonal to the contour matrix [18].

 

${\mathbf{I}}_{\mathit{(}\mathit{\left|}V\mathit{\right|}\mathit{-}\mathit{1}\mathit{)}\mathit{\times }\mathit{\left|}E\mathit{\right|}}\mathbf{\cdot }{{\mathbf{C}}_{\mathit{\left|}{E}_b\mathit{\right|}\mathit{\times }\mathit{\left|}E\mathit{\right|}}}^T=0$, (1)

 

where ${\mathbf{I}}_{\mathit{(}\mathit{\left|}\mathit{V}\mathit{\right|}\mathit{-}\mathit{1}\mathit{)}\mathit{\times }\mathit{\left|}E\mathit{\right|}}$ is the incidence matrix of a contour network without a linearly independent row;

${\mathbf{C}}_{\mathit{\left|}{E}_b\mathit{\right|}\mathit{\times }\mathit{\left|}E\mathit{\right|}}$ is the contour matrix.

 

The matrix ${\mathbf{I}}_{\mathit{(}\mathit{\left|}\mathit{V}\mathit{\right|}\mathit{-}\mathit{1}\mathit{)}\mathit{\times }\mathit{\left|}E\mathit{\right|}}$ is formed from the incidence matrix${\mathbf{I}}_{\mathit{\left|}V\mathit{\right|}\mathit{\times }\mathit{\left|}E\mathit{\right|}}$, describing the graph of the original orthogonal network by removing from it all rows in which there is only one non-zero element. Thus, the transformation of an orthogonal network into a contour network reduces so that all nodes with a degree equal 1 and incident edges from subsets$E_{src}$,$E_{rcv}$  and $E_{loss}$ are combined into one node. This is equivalent to adding all the rows in the matrix ${\mathbf{I}}_{\mathit{\left|}V\mathit{\right|}\mathit{\times }\mathit{\left|}E\mathit{\right|}}$, in which there is only one non–zero element in one row. Thus, since the new matrix is the incidence matrix of the contour network, where one of the rows can also be distinguished as linearly dependent, then the row that resulted from the addition of rows with one non-zero element, can be chosen thereof. The resulting incidence matrix, by adding rows and rearranging columns, is reduced to the following form:

 

                                                      ${\mathbf{I}}_{\mathit{(}\mathit{\left|}V\mathit{\right|}\mathit{-}\mathit{1}\mathit{)}\mathit{\times }\mathit{\left|}E\mathit{\right|}}\mathbf{=}\left[\mathbf{E}\mathbf{ }\mathbf{Hg} { }_{\mathit{(}\mathit{\left|}V\mathit{\right|}\mathit{-}\mathit{1}\mathit{)}\mathit{\times }\mathit{\left|}{E}_h\mathit{\right|}}\right]$.

 

where E is the unity matrix of dimension $\left|V\right|-1$,     _{$\mathbf{Hg}\left(\left|V\right|-1\right)\times \left|E_h\right|$} is the matrix  of the chords of the graph.

Note that the column numbers forming the unity matrix are the numbers of the graph branches that represent the network analyzed, while the column numbers of the matrix Hg are the numbers of the chords of this graph.

To fulfill the orthogonality condition according to formula (1), the matrix C${}_{\left|{\mathrm{E}}_{\mathrm{b}}\right|\times \left|\mathrm{E}\right|}$ must have the following form:

                                                   ${\mathbf{C}}_{\mathit{\left|}{E}_b\mathit{\right|}\mathit{\times }\mathit{\left|}E\mathit{\right|}}\mathit{=}\mathit{\left[}\mathrm{E} (-{{\mathrm{Hg}}_{(\left|\mathrm{V}\right|-1)\times \left|{\mathrm{E}}_{\mathrm{h}}\right|}}^{\text{Т}})\mathit{\right]}$.

A feature of the lossy networks topology is that the spanning tree of a graph can be obtained only from edges that form reset channels: these edges will be branches of the graph, while the remaining edges will be chords of this graph.

Thus, it is possible to propose a faster way to obtain a contour matrix, which requires less computational steps and is applicable when necessary to analyze losses in all channels or in most communication channels.

We introduce the following notations:

 ${\mathbf{I}}_{loss}$– incidence matrix of the lossy network, reduced to a contour form;

 ${\mathbf{I}}_{lossless}$– lossless incidence matrix reduced to a contour view;

 $Xh$– column vector, with each element showing flows in chords from each source;

 $N_{users}$– number of sources equal to the number of elements in the set ;

 n– source number.

In the matrix ${\mathbf{I}}_{loss}$ and ${\mathbf{I}}_{lossless}$ there are the same number of nodes, but a different number of columns, therefore, the matrix ${\mathbf{I}}_{loss}$ is obtained from the matrix ${\mathbf{I}}_{lossless}$ by adding $\left|E_{loss}\right|$ columns to the left, while the columns being added are a diagonal unity matrix, which corresponds to the following expression:

 

                                                             ${\mathbf{I}}_{loss}\mathit{=}\mathit{[}\mathbf{E}\mathbf{ }\mathbf{I}{\mathit{ }}_{lossless}\mathit{]}$ .

 

This implies that the matrix $\mathbf{I}{\mathit{ }}_{lossless}$ is a chord matrix for a graph describing a lossy network. Thus, in the matrix $\mathbf{I}{\mathit{ }}_{loss}$columns numbered from $\left(\left|E_{loss}\right|+1\right)$ to $\left(\left|E_{loss}\right|+\left|E_h\right|\right)$ will be branches of the graph, and columns from to will be chords of this graph. Therefore, the contour matrix for a lossy network will be defined as follows:

 

                                                         ${\mathbf{C}}_{loss}\mathit{=}\mathit{[}\mathbf{E}\mathit{ }\mathit{ }\mathit{(}\mathit{-}{{\mathbf{I}}_{lossless}}^T\mathit{)}\mathit{]}$ .

 

In the matrix ${\mathbf{C}}_{loss}$ columns numbered from 1 to $\left|E_h\right|$ will be the chords of the graph, columns from $\left(\left|E_h\right|+1\right)$to $\left(\left|E_h\right|+\left|E_{loss}\right|\right)$ are branches of this graph.

We formulate recommendations on the choice of edge numbers. Based on the notation entered, the recommended numbering order of the edges in the original graph is as follows: first, to number all the edges from the set $E_{src}$, then from $E_{rcv}$, followed by $E_{tr}$ and finally from $E_{loss}$. This recommendation is due to the fact that in the future there will be no need to organize additional search and sorting algorithms necessary for the formation of the final system of constraints and the objective function.

Each row in the contour matrix ${\mathbf{C}}_{loss}$ shows which edges are included in the contour, whereas only one chord is included in each contour, and the direction of this chord sets the direction of the entire contour. Therefore, if the values of the flows in each chord of the graph are known and these values are set as a column vector, then the product of the transposed contour matrix by the vector of flows in the chord will give the values of flows in both each chord and the branches of the graph, thereby the flows in the branches of the graph are linearly dependent on the flows in the chords of this graph or, similarly, flows in the edges of a graph are completely described by flows in its chords. Thus, in the compiled mathematical model, the flows in the chords of the graph will act as variables.

Since each source creates its own flow in each edge of the graph, the number of variables will be determined as the number of chords of the graph multiplied by the number of traffic sources.

Consequently, the vector of variables $Xh$ will contain $N_{users}\cdot \left|E_h\right|$ variables. In the vector $Xh$ variables with ordinal numbers from $\left(n-1\right)·\left(\left|E_h\right|+1\right)$ to $\left(n·\left|E_h\right|\right)$ will show the source streams n in chords from the set $E_h$. To determine the total flow in each communication channel, we will create the following matrix:

                                          ${\mathbf{C}}_{sum}=\left[\begin{array}{cc}\begin{array}{cc}{\mathbf{C}}_{loss}{{}_1}^T& {\mathbf{\text{C}}}_{loss}{{}_2}^T\end{array}& \begin{array}{cc}\cdots & {\mathbf{\text{C}}}_{loss}{{}_{N_{users}}}^T\end{array}\end{array}\right]$ .

 

To determine the flow in each channel created by each source, we will make the following matrix:

                                                 ${\mathbf{C}}_{users}\mathit{=}\mathit{\left[}\begin{array}{ccc}{\mathit{\text{C}}}_{loss}{{}_{\mathit{1}}}^T& \mathit{\cdots }& \mathit{0}\\ \mathit{⋮}& \mathit{\ddots }& \mathit{⋮}\\ \mathit{0}& \mathit{\cdots }& {\mathit{\text{C}}}_{loss}{{}_{N_{users}}}^T\end{array}\mathit{\right]}$.            (2)

 

To determine the total flow in each communication channel

 

                                                             .                        $X{e}_{sum}=\mathbf{C}{}_{sum}\cdot Xh$(3)

 

Each row of the matrix  shows the total flow in each communication channel. To determine the flow in each channel from each source, use the formula

 

                                                            $X{e}_{users}=\mathbf{C}{}_{users}\cdot Xh$.

 

Each row m of the matrix $X{e}_{users}$ shows flows from each individual user. Thus, to find out which flow is being created in the edge $E_i$, it is necessary to take an element $X{e_{users}}_{\left(n-1\right)\cdot \left|E\right|+i}$ from the user n. Having obtained the connections of the flows in each channel through the flows in the chords, the further task is reduced to compiling a system of constraints and an objective function.

Since the dimension of such a problem is large enough, it is necessary to use mathematical modeling systems to solve it. To form a system of constraints, it is necessary to make a number of matrices A, B, Aeq, Beg, Ceg(x) and C(x), and also set the point of the initial iteration $x0$. A system of nonlinear inequalities is created from the obtained matrices

                             $\left\{\begin{array}{c}\begin{array}{c}\mathbf{A}\cdot X\le 0;\\ \mathbf{Aeq}\cdot X=0;\end{array}\\ \begin{array}{c}\mathbf{C}\left(x\right)\le 0;\\ \mathbf{Ceq}\left(x\right)=0.\end{array}\end{array}\right.$                                   

 

As can be seen, the system consists of four blocks, where $\mathbf{Ceq}\mathit{\left(}x\mathit{\right)}$ is a column vector, each element of which represents a sort of nonlinear dependence on the desired variables, while this value should be zero. Vector $\mathbf{C}\mathit{\left(}x\mathit{\right)}$ is similar to block $\mathbf{Ceq}\left(\mathrm{x}\right)$, however, by contrast each element of this column vector is less than or equal to zero.

To determine the value of the flow in the lossy channels, we will leave in the matrix ${\mathbf{C}}_{loss}$ only those columns that are responsible for the edges from the set $E_{loss}$ (i.e. columns with numbers corresponding to the edges through which the lossy flows pass). We denote such a matrix as $\mathbf{C}{\left(E_{loss}\right)}_{users}$ and form as follows

 

 

                                  $\mathbf{C}{\left(E_{loss}\right)}_{users}=\left[\begin{array}{ccc}\mathbf{\text{C}}{\left(E_{loss}\right)}_{loss}{{}_1}^T& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \mathbf{\text{C}}{\left(E_{loss}\right)}_{loss}{{}_{N_{users}}}^T\end{array}\right]$.

To determine the lossy flow in each lossy channel from each source, we write the following equation:

 

                                                   $Xe{\left(E_{loss}\right)}_{users}=\mathbf{C}{\left(E_{loss}\right)}_{users}\cdot Xh$.             (4)

 

By formula (4) we obtain the values of lossy flows expressed in terms of flows in the chords of the graph. On the other hand, the loss in the source loss channel can be defined as the traffic intensity in the channel that enters the switching node multiplied by the probability of reset for this channel.

Further we need to understand for which channels it is necessary to determine the losses: in case of all channels, the space of channels from subsets belongs to channels $E_{src}$, $E_{rcv}$ and $E_{tr}$; in case we are interested in channels connecting switching nodes only, then this is the space of channels from the subset $E_{tr}$. The latter option is of the greatest practical interest since the edges from the subset$E_{tr}$, as a rule, are the edges of the backbone part of the network, while the edges from the subsets $E_{src}$ and $E_{rcv}$ belong to the access channels and are poorly loaded.

To determine the probability of losses in each channel from the subset $E_{tr}$ it is necessary to determine the total flow in this set. To do this, we will leave only those columns in the matrix ${\mathbf{C}}_{loss}$ that correspond to the numbers of edges from the subset $E_{tr}$ and denote such a matrix as $\mathbf{C}{\left(E_{tr}\right)}_{loss}$. To determine the total flow in the edges of the subset $E_{tr}$ we make a matrix $\mathbf{C}{\left(E_{tr}\right)}_{sum}$ 

 

                      $C{\left(E_{tr}\right)}_{sum}=\left[\begin{array}{cc}\begin{array}{cc}{\left(E_{tr}\right)}_{loss}{{}_1}^T& {\left(E_{tr}\right)}_{loss}{{}_2}^T\end{array}& \begin{array}{cc}\cdots & {\left(E_{tr}\right)}_{loss}{{}_{N_{users}}}^T\end{array}\end{array}\right]$.

 

By analogy with (2), the flow in each channel from the subset $E_{tr}$ created by each source is expressed as follows:

 

                                    $\mathbf{C}{\left(E_{tr}\right)}_{users}=\left[\begin{array}{ccc}\mathbf{\text{C}}{\left(E_{tr}\right)}_{loss}{{}_1}^T& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \mathbf{\text{C}}{\left(E_{tr}\right)}_{loss}{{}_{N_{users}}}^T\end{array}\right]$ .

 

Next, we find the value of the flow vectors for a subset of edges $E_{tr}$:

 

                                                     $Xe{\left(E_{tr}\right)}_{sum}={\left(E_{tr}\right)}_{sum}\cdot Xh$ ,                 (5)

 

                                                    $Xe{\left(E_{tr}\right)}_{users}={\left(E_{tr}\right)}_{users}\cdot Xh$ ,               (6)

 

where $Xe{\left(E_{tr}\right)}_{sum}$ shows the total flow passing through the edges of the subset $E_{tr}$, the element of this vector shows the value of the total flow in the ith edge; $Xe{\left(E_{tr}\right)}_{users}$ shows the flows from each source passing through the edges of the subset $E_{tr}$.

Each row $\left|E_{tr}\right|$ of the matrix $Xe{\left(E_{tr}\right)}_{users}$ shows the flows from each source in the edges of the subset $E_{tr}$. Thus, to find out which flow is being created in the th edge from the user n, it is necessary to take an element $Xe{{\left(E_{tr}\right)}_{users}}_{\left(n-1\right)\cdot \left|E_{tr}\right|+i}$. If the probability function of losses for a channel from a subset $E_{tr}$ is known, the intensity of losses in the channel for the source  will be as follows

                                               $Xe{{\left(E_{tr}\right)}_{users}}_{\left(n-1\right)\cdot \left|E_{tr}\right|+i}\cdot p\left(Xe{{\left(E_{tr}\right)}_{sum}}_i\right)$.

The flow in the reset channel from the source n, which is connected to the node $v_i$, is equal to the sum of the flows along the edges that enter it, corresponding to such edges for which -1 is in the incident matrix in the row indexing the node. If for each node to which the reset channels are connected the flows from the incoming edges are summed, then such a flow will correspond to the reset flow from a specific source in the reset channel originating from this node:

                                      $X{e}_{nv}=\underset{i\in v\left(in\right)}{}Xe{{\left(E_{tr}\right)}_{users}}_{\left(n-1\right)\cdot \left|E_{tr}\right|+i}\cdot p\left(Xe{{\left(E_{tr}\right)}_{sum}}_i\right)$, (7)

 

where $X{e}_{nv}$ is the discharge flow at the node $v_i$ from the source n.

If all the elements $X{e}_{nv}$ are put in the order of increasing the index, the value of the elements of the resulting vector $X{e}_{nv}$ will be equal to the elements of the vector $Xe{\left(E_{loss}\right)}_{users}$, thus $X{e}_{nv}= Xe{\left(E_{tr}\right)}_{users}$, with the implication that

 

                                                    Ceq$\left(x\right)=Xe{\left(E_{tr}\right)}_{users}-X{e}_{nv}$ .

 

Matrix C$\left(x\right)$ can be used to add third-party restrictions, for example, add restrictions on losses in communication channels, set delays for channels or end-to-end delays, and also leave the matrix empty for cases when additional conditions are not required.

For loss restrictions, it is necessary to create a column vector $P_{losses}$, in which we specify the threshold value of loss probabilities for individual channels or all channels in the network. Knowing the functional dependence of the probability of losses for these channels, as well as using the total intensity of losses in these channels from formula (3), we obtain the following expression:

 

                                                             $p\left(X{e}_{sum}\right)\le P_{losses}$ .                        (8)

 

By the same principle, we will create a column vector $T_{wt}$, in which we will specify the delay thresholds for channels or through delays for certain routes. Knowing the functional dependence of the average number of applications in the queue $L_0$, as well as using the total intensity of losses in these channels from formula (3), we obtain an expression for channel and end-to-end delays:

 

                                                              $L_0\left(X{e}_{sum}\right)/X{e}_{sum}$.

 

By analogy with the expression (8), we make up inequalities for a system of constraints:

 

                                                          $L_0\left(X{e}_{sum}\right)/X{e}_{sum}\le T_{wt}$.                    (9)

 

When forming C $\left(x\right)$, it should be taken into account that each element of this set must be less than or equal to zero. To achieve this condition, in formulas (8) and (9), the right part of the inequality is transferred to the left. Then the final form of the column vector C$\left(x\right)$ is the following:

 

                                                  $C\left(x\right)= \left[\begin{array}{c}p\left(X{e}_{sum}\right)-P_{losses}\\ L_0\left(X{e}_{sum}\right)/X{e}_{sum}-T_{wt}\end{array}\right]$.

 

Further we consider the algorithm for obtaining a matrix Aeq the product of a matrix Aeq by a vector of variables X describes such a linear combination of values that are known in advance, which according to the mathematical model are flows in the branches of a subset $E_{rcv}$. It should also be taken into account that the flows from the source n will be zero in all edges of the space $E_{src}$ except for the edge directly connected to the source n.

Therefore, if only the rows corresponding to the edge numbers from the subset $E_{rcv}$ are left from the matrix C${}_{\mathrm{loss}}$, as well as the rows corresponding to the edge numbers of the subset $E_{src}$, in which the flows from the sources are zero, and also denoting such a space as $E_{S0}$, and denoting the resulting matrix  C${\left(E_{rcv}\cup E_{S0}\right)}_{loss}$, we obtain the following matrix:

 

        $\mathbf{C}{\left(E_{rcv}\cup E_{S0}\right)}_{users}=\left[\begin{array}{ccc}\mathbf{\text{C}}{\left(E_{rcv}\cup E_{S0}\right)}_{loss}{{}_1}^T& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \mathbf{\text{C}}{\left(E_{rcv}\cup E_{S0}\right)}_{loss}{{}_{N_{users}}}^T\end{array}\right]$.

 

If we multiply the resulting matrix with the vector $Xh$, we obtain the vector $Xe{\left(E_{rcv}\cup E_{S0}\right)}_{users}$, describing the flows in channels that are quantities known in advance, and their values are entered in the vector Beq. Thus,

 

$\mathbf{Aeq}= {\left(E_{rcv}\cup E_{S0}\right)}_{users}$,

 

                                         $Xe{\left(E_{rcv}\cup E_{S0}\right)}_{users}=\mathbf{C}{\left(E_{rcv}\cup E_{S0}\right)}_{users}\cdot Xh$.

 

We consider the algorithm of A matrix formation. The matrix A is formed due to the necessary to set limits for the flows that pass through the communication channels. The minimum desired restriction is that the streams in each channel created by each source should not be negative, since the value of the streams in the edges of the subset $E_{rcv}$are known in advance, and the value of the flows in the edges of the subset$E_{loss}$ depends on the values of the flows in the edges of the subset $E_{src}$and $E_{tr}$. In the matrix, it is necessary to leave only those columns with the numbers corresponding to the numbers of edges from the space $\left(E_{src}-E_{S0}\right)$and $E_{tr}$. The result is a matrix C${\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{loss}$ from which the matrix is C${\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{users}$formed:

 

$\mathbf{C}{\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{users}=\left[\begin{array}{ccc}\text{C}{\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{loss}{{}_1}^T& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \mathbf{\text{C}}{\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{loss}{{}_{N_{users}}}^T\end{array}\right]$.

 

This patrics matrix is the matrix A, the value of the elements of the vector B equals 0. Thus, a system of constraints is obtained. Since the number of equalities in this system is less than the number of variables, this system has an infinite set of solutions, and each solution gives one of the possible traffic distributions along the chords of the graph, after which, by multiplying the resulting vector by the С_loss matrix, we obtain the final values of flows in all edges of the graph.

To find the best solution, an optimality criterion should be set, which can be expressed using various functions. If we use network losses as a criterion, i.e. minimize the sum of the reset streams, the objective function will be the sum of the array elements $Xe{\left(E_{loss}\right)}_{users}$or $X{e}_{nv}$ and will be as follows:

 

                                                           $f\left(x\right)= \underset{i=1}{\overset{\left|E_{loss}\right|}{}}Xe{\left(E_{loss}\right)}_i$.

 

 3. An example of bringing a network to a system of restrictions

As an example, we consider the network shown in Fig. 6. Denote the value of the variables for this topology, which we will use:

$V=\left\{\mathrm{1,2,3,4}\right\}$, $\left|V\right|=4$, $E=\left\{\mathrm{1,2,3,4,5,6,7,8,9,10,11,12,13}\right\}$, $\left|E\right|=13$, $E_h=\left\{\mathrm{1,2,3,4,5,6,7,8,9,10}\right\}$, $\left|E_h\right|=10$, $E_b=\left\{\mathrm{11,12,13}\right\}$, $\left|E_b\right|=3$, $E_{src}=\left\{\mathrm{3,4}\right\}$, $\left|E_{src}\right|=2$, $E_{rcv}=\left\{\mathrm{1,2}\right\}$, $\left|E_{rcv}\right|=2$, $E_{tr}=\left\{\mathrm{5,6,7,8,9,10}\right\}$, $\left|E_{tr}\right|=6$, $E_{loss}=\left\{\mathrm{11,12,13}\right\}$, $\left|E_{loss}\right|=3$.

 

 

Рис. 6. Исследуемая сеть

Fig. 6. Researched network

 

At the next stage, we will define the contour matrix С_loss  (Table 1).

According to the given topology, the number of sources is 2, hence the variable $N_{users}=2$, and the vector of variables $Xh$ will contain $\left|E_h\right|·N_{users}=10·2=20$ values. The elements of the vector $Xh$ contain unknown variables, for example, variables x₁ and x₁₁ show the speed value of information flows in edge No. 1 created by two different sources. Next, according to the algorithm, we determine the values $X{e}_{sum}$ by formula (5) and$X{e}_{users}$  by formula (6). Vector $X{e}_{sum}$ shows which components make up the flow in the corresponding edges. The vector elements $X{e}_{users}$ show the value of the flow created by a single source in the corresponding edge.

 

Table 1. Contour matrix for the network under study

$E_{rcv}$		$E_{src}$		$E_{tr}$						$E_{loss}$
1	2	3	4	5	6	7	8	9	10	11	12	13
1	0	0	0	0	0	0	0	0	0	–1	0	0
0	1	0	0	0	0	0	0	0	0	0	–1	0
0	0	1	0	0	0	0	0	0	0	1	0	0
0	0	0	1	0	0	0	0	0	0	0	1	0
0	0	0	0	1	0	0	0	0	0	–1	1	0
0	0	0	0	0	1	0	0	0	0	1	–1	0
0	0	0	0	0	0	1	0	0	0	–1	0	1
0	0	0	0	0	0	0	1	0	0	1	0	–1
0	0	0	0	0	0	0	0	1	0	0	1	–1
0	0	0	0	0	0	0	0	0	1	0	–1	1

 

Further it is necessary to determine the nonlinear part of the equations of the mathematical model: we define a matrix C${{\left(E_{loss}\right)}_{loss}}^T$ this matrix consists of rows defined by rows of a subset Е_loss from the matrix C${{}_{\mathrm{loss}}}^{\mathrm{T}}$. Then we determine the value of the lossy flows in the loss channels from each source by the formula (4). On the other hand, the value of lossy flows depends on which flow passes through the edges of the set $E_{tr}$. Thus, it is possible to determine the proportion of the information flow lost for each edge as the product of the flow in the edge from a specific source by the probability of losses for this edge. To do this, we determine the value of the flow vectors for the edge space. In order to use formula (5), we find С(Е_tr)_sum and С(Е_tr)_users to use in formula (6). Employing matrics С(Е_tr)_sum and formula (5), we find the value of the total flows in the edges of the set Е_tr, while using the matrix С(Е_tr)_users and formula (6), we find the value of the flows in the edges from the set Е_tr for each individual source.

Further, using the formula (7), we determine the value of lossy flows for each node in the transport network, which includes flows going through a subset of the Е_tr. We believe that the functional dependence of the probability of losses is known, and the final probability for the total flow is equal to the sum of the probabilities of losses for any component of such a flow. As a result, the value of the vector or the first system of equations of the mathematical model of traffic distribution will look as follows:

 

$\left\{\begin{array}{c}\begin{array}{c}\left(-x_1+x_3-x_5+x_6-x_7+x_8\right)-\left(x_6·\text{P}\left(x_6+x_{16}\right)+x_8·\text{P}\left(x_8+x_{18}\right)\right)=0\\ \left(-x_2+x_4+x_5-x_6+x_9-x_{10}\right)-\left(x_5·\text{P}\left(x_5+x_{15}\right)+x_9·\text{P}\left(x_9+x_{19}\right)\right)=0\\ \left(+x_7-x_8-x_9+x_{10}\right)-\left(x_7·\text{P}\left(x_7+x_{17}\right)+x_{10}·\text{P}\left(x_{10}+x_{20}\right)\right)=0\end{array}\\ \begin{array}{c}\left(-x_{11}+x_{13}-x_{15}+x_{16}-x_{17}+x_{18}\right)-\left(x_{16}·\text{P}\left(x_6+x_{16}\right)+x_{18}·\text{P}\left(x_8+x_{18}\right)\right)=0\\ \left(-x_{12}+x_{14}+x_{15}-x_{16}+x_{19}-x_{20}\right)-\left(x_{15}·\text{P}\left(x_5+x_{15}\right)+x_{19}·\text{P}\left(x_9+x_{19}\right)\right)=0\\ \left(+x_{17}-x_{18}-x_{19}+x_{20}\right)-\left(x_{17}·\text{P}\left(x_7+x_{17}\right)+x_{20}·\text{P}\left(x_{10}+x_{20}\right)\right)=0\end{array}\end{array}\right.$.

 

The next step is to find a mathematical model of linear equalities. To do this, we define the matrix Aeq, for which we define the matrices C${{\left(E_{rcv}\cup E_{S0}\right)}_{loss}}_1$and C${{\left(E_{rcv}\cup E_{S0}\right)}_{loss}}_2$, respectively:

 

                               C${{\left(E_{rcv}\cup E_{S0}\right)}_{loss}}_1=\left[\begin{array}{cc}\begin{array}{cc}\begin{array}{ccc}1& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\\ \begin{array}{cc}\begin{array}{ccc}0& 1& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\\ \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}1& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\right] \begin{array}{c}1\\ 2\\ 4\end{array}$

;

 

                               C${{\left(E_{rcv}\cup E_{S0}\right)}_{loss}}_2=\left[\begin{array}{cc}\begin{array}{cc}\begin{array}{ccc}1& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\\ \begin{array}{cc}\begin{array}{ccc}0& 1& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\\ \begin{array}{cc}\begin{array}{ccc}0& 0& 1\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}& \begin{array}{cc}\begin{array}{ccc}0& 0& 0\end{array}& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\right] \begin{array}{c}1\\ 2\\ 3\end{array}$.

 

Since it is known that $\mathbf{Aeq}=\mathbf{C} {\left(E_{rcv}\cup E_{S0}\right)}_{users}$, then by formula (8) it is possible to make a matrix Aeq. To obtain the system of equations itself, we determine the value of the product Aeq by a vector $Xh,$ denote the resulting vector by $Xeq,$ and also introduce a column vector Beq that shows the value of each element of the vector $Xeq$. As a result , we obtain the following equality:

$\mathbf{Aeq}\mathbf{ }\cdot Xeq=\mathbf{Beq}$.

We establish that the flow created by the source connected to edge No. 3 should deliver 10 pieces of information to the recipient connected to edge No. 2. Obviously, the source does not send anything to itself, so the value of the flow from this source in edge No.1 will equal 0, and also this source cannot create a stream in edgeNo. 4, so the flow in this edge is also equal to 0, whereas the value of the flow itself in the source is unknown, since the loss flows in No. 11, 12 and 13 edges are unknown. From the same considerations, the distribution of the flow from the second source is constructed: the value of the flow in the edge No. 1 is equal to 13 units, in the edges No. 2 and 3 are 0, and the value in the edge No. 4 is unknown.

The final basic constraint is that the intensity of data flows must be non-negative, hence for this we need to find a matrix $\mathbf{A}=\mathbf{C}{\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{loss}$ and multiply it by a vector $Xh$, resulting in a vector $Xh{\left(E_{src}-E_{S0}\cup E_{tr}\right)}_{loss}.$ However, in this example, we can use a unit matrix E of dimension $\left|E_h\right|·N_{users}=20$instead of a matrix A.

To obtain the system of equations itself, we determine the value of the product A of the vector $Xh$, denote the resulting vector for $Xe,$ and also introduce a column vector B that shows the value of each element of the vector $Xe$. As a result, we obtain the following equality: $\mathbf{A}\cdot Xe\ge \mathbf{B}$. The matrix B in this example is given by a column vector entirely consisting of zeros. The number of elements in the matrix B is equal to the number of chords multiplied by the number of sources $N_{users}$, i.e $10\cdot 2=20$.

Applying this method, we fulfill the condition of non-negativity of information flows in the network, although we add additional linear inequalities to the system. It is important to note that this method should not be used for large-dimensional topologies, where unnecessary inequalities can affect the performance of the solution.

The last stage in the formation of a mathematical model is to obtain an objective function, which is defined as the sum of the lossy flows, i.e. it is the sum of the rows of the matrix $Xe{\left(E_{loss}\right)}_{users}$. As a result, the objective function is the difference between the flows that entered the network through the channels of space $E_{src}$ and the flows that left the network along the edges of space$E_{rcv}$:

                                           $F=x_3+x_{13}+x_4+x_{14}-\left(x_1+x_{11}+ x_2+x_{12}\right)$.

We bring the obtained constraints and the target function into a single system:

 

$\left\{\begin{array}{l}\begin{array}{c}\left(-x_1+x_3-x_5+x_6-x_7+x_8\right)-\left(x_6·\text{P}\left(x_6+x_{16}\right)+x_8·\text{P}\left(x_8+x_{18}\right)\right)=0;\\ \left(-x_2+x_4+x_5-x_6+x_9-x_{10}\right)-\left(x_5·\text{P}\left(x_5+x_{15}\right)+x_9·\text{P}\left(x_9+x_{19}\right)\right)=0;\\ \left(+x_7-x_8-x_9+x_{10}\right)-\left(x_7·\text{P}\left(x_7+x_{17}\right)+x_{10}·\text{P}\left(x_{10}+x_{20}\right)\right)=0;\end{array}\begin{array}{c}\\ \\ \end{array}\\ \begin{array}{c}\left(-x_{11}+x_{13}-x_{15}+x_{16}-x_{17}+x_{18}\right)-\left(x_{16}·\text{P}\left(x_6+x_{16}\right)+x_{18}·\text{P}\left(x_8+x_{18}\right)\right)=0;\\ \left(-x_{12}+x_{14}+x_{15}-x_{16}+x_{19}-x_{20}\right)-\left(x_{15}·\text{P}\left(x_5+x_{15}\right)+x_{19}·\text{P}\left(x_9+x_{19}\right)\right)=0;\\ \begin{array}{c}\left(+x_{17}-x_{18}-x_{19}+x_{20}\right)-\left(x_{17}·\text{P}\left(x_7+x_{17}\right)+x_{20}·\text{P}\left(x_{10}+x_{20}\right)\right)=0;\\ X{h}_i\ge 0 \left(i=\mathrm{1,2,}\dots \mathrm{,20}\right);\\ \begin{array}{c}\begin{array}{c}{x}_1=0;\\ x_2=10;\\ x_4=0;\end{array}\\ \begin{array}{c}{x}_{11}=15;\\ x_{12}=0;\\ x_{13}=0;\end{array}\\ F=x_3+x_{13}+x_4+x_{14}-\left(x_1+x_{11}+ x_2+x_{12}\right)\to min.\end{array}\end{array}\end{array}\end{array}\right.$

 

To find a numerical solution, it is necessary to set the value of the loss probability function: in the classical version, it can be assumed that the streams created by the sources have an exponential distribution of intervals between calls; the service time is also distributed exponentially and it is known that there will also be an exponential flow at the output during maintenance [19]. It is also possible to make an assumption about independence of package maintenance by each queuing system. Thus, to describe the probability we can use the formula for a queuing system M/M/1/N at a low loss level. The discharge intensity formula for the M/M/1/N system has the following form:

                                                 $p\left({\lambda }_{sum}\right)= \frac{1-\frac{{\lambda }_{sum}}{\mu }}{1-{\left(\frac{{\lambda }_{sum}}{\mu }\right)}^{N+1}}\cdot {\left(\frac{{\lambda }_{sum}}{\mu }\right)}^N$,

 

where ${\lambda }_{sum}$ is the total intensity of traffic flow through the single-server queueing system;; $\mu$ is the intensity of traffic service; $\left(N-1\right)$is the number of places in the buffer.

The values of service intensities in the edges of the space E_tr for the analyzed network equal${\mu }_5=\mathrm{15,} {\mu }_6=\mathrm{15,}{\mu }_7=\mathrm{20,}{\mu }_8=\mathrm{20,}{\mu }_9=\mathrm{25,} {\mu }_{10}=25$, the values of waiting places for the space are E_tr – $N_5=\mathrm{5,} N_6=\mathrm{4,} N_7=\mathrm{4,} N_8=\mathrm{1,} N_9=\mathrm{3,} N_{10}=8$.

To solve this optimization problem numerically, it is necessary to involve third-party tools that allow solving systems of nonlinear equations using one or more optimality criteria. For example, you can use the MatLab environment with the Optimization Toolbox add-on package connected. It is also possible to use free analogues: GNU Octave with the Optim package connected, or the Python programming language with the numpy and scipy libraries. For this example, use the MatLab environment and the linprog and fmincon functions. The full programming code is written in [20].

When solving optimization problems, it is necessary to find the point of the initial iteration by solving a single system of constraints without an optimality criterion using the linprog function.

Solving this optimization problem with the fmincon function, we obtain the following distribution, shown in Table. 2. The total traffic distribution is shown in Fig. 7.

 

 Table 2. Distribution of flows across communication channels

$Номер ребра$	$Значение потоков от источника № 1 (ед. инф/с)$	$Значение потоков от источника № 2 (ед. инф/с)$	${\lambda }_{sum} (ед. инф / с)$	${\mu }_{\text{обслуж }} (ед. инф / с)$	$Число мест ожидания$	$Пространство ребер$
1	0	13	13	_	_	Потоки в каналах-приемниках, $E_{rcv}$
2	10	0	10	_	_
3	10,055	0	10,055	_	_	Потоки в каналах-источниках, $E_{src}$
4	0	14,609	14,609	_	_
5	5,6507	0	5,6507	15	5	Потоки в транзитных каналах, $E_{tr}$
6	0	10,448	10,448	15	4
7	4,4038	0	4,4038	20	4
8	0	4,1618	4,1618	20	1
9	4,3958	0	4,3958	25	3
10	0	4,1618	4,1618	25	8
11	0	1,6094	1,6094	_	_	Потоки в каналах сброса, $E_{loss}$
12	4,6511×10-2	0	4,6511×10-2	_	_
13	8,077×10-3	2,046×10-6	8,0791×10-3	_	_

 

 

Рис. 7. Суммарное распределение потоков в исследуемой сет

Fig. 7. The total distribution of flows in the studied network

 

In Fig. 7, in a rectangle with a background fill, the first digit shows the number of requests coming to the interface, the second digit shows the bandwidth of the interface (service intensity), and the third digit shows the size of the interface queue. Thus, for channel 7 we have 4.4038/20/4. This means that the traffic intensity on the channel makes 4.4038 packets/s, the service intensity equals 20 packets/s, and the buffer size is 4.

A numerical example shows that for given throughput capacities and buffer sizes, the network serves a given intensity of requirements entering the network with small overloads, as evidenced by insignificant losses in the reset channels.

It should be noted that the solution of the constraint system in general cannot be used independently to solve the problem of traffic distribution without an objective function, since such a system has an infinite number of solutions that contain loop routes. Therefore, in order to solve the problem by the contour method, in addition to the system of constraints it is necessary to use the objective function, as only in this case it is possible to obtain non–linear routes, which is the main difference from the method proposed in [21]. In [21] the problem of optimal traffic distribution in lossless networks was solved by the minimum delay criterion. As part of the task to be solved, it was necessary to determine all the non-parallel routes between each source-recipient pair, and the values of the flows along these routes are the desired variables. In [19], analysis of the growth in the number of pointless routes depending on the network structure was carried out where it was shown that the use of pointless routes is justified only in small topologies or those with a small number of alternative paths between sources and recipients.

 

Conclusion

For the contour method with losses, the number of variables is determined by the product of the sources number and the number of chords in the graph, i.e. adding another edge for the contour method will either increase the number of linearly independent variables in the mathematical model by the number of load sources, or do not increase at all, depending on whether this edge is a chord or a branch, respectively. For optimization problems in which the compilation of a mathematical model is based on the search for pointless routes, adding another edge related to the chord will mean that the number of new variables will increase many times depending on where such an edge is added compared to the contour approach. A feature of the proposed algorithm is the search for a contour matrix, for which it is proposed to use lossy edges as elements of the spanning tree of the graph, which allows immediately determine the contour matrix applying the concept of fundamental cycle of the graph. Thus, this approach for optimal traffic distribution allows to reduce the number of variables used in comparison with the known methods based on loopless routes, and also does not require their preliminary search since they are determined from the dimension of the incidence matrix of the simulated network graph.

 

Благодарности. Исследование выполнено при финансовой поддержке программы стратегического академического лидерства «Приоритет-2030» СибГУ им. М. Ф. Решетнева.

 

Acknowledgments. The reported study was funded by strategic academic leadership program «Priority-2030» of Reshetnev University.

作者简介

Konstantin Gaipov

Reshetnev Siberian State University of Science and Technology

Email: gaipovke@yandex.ru

Cand. Sc., Associate Professor of the Department of Electronic Engineering and Telecommunications

俄罗斯联邦, Krasnoyarsk

Alexander Kuznetsov

Reshetnev Siberian State University of Science and Technology

Email: alex_kuznetsov80@mail.ru

Dr. Sc., Professor, Head of Institute of Space Research and High Technologies

俄罗斯联邦, Krasnoyarsk

Ilya Krikunov

Reshetnev Siberian State University of Science and Technology

编辑信件的主要联系方式.
Email: zaybernev@mail.ru

Junior researcher of the Scientific Library Satellite Telecommunication System

俄罗斯联邦, Krasnoyarsk

参考

补充文件