A software-defined network is a complex system, the basis of which, first of all, is formed by a central controller, switching nodes and data transmission channels ensuring the interaction of these nodes. In the process of designing such systems, special attention must be paid to its topological structure. This is due to several factors. Firstly, the issues of improving the efficiency and reliability of the entire network directly depend on the topological structure. Secondly, topology affects the number of factors when making all the decisions of its design. And finally, the topology completely defines the process of traffic management in a software-defined network, which occurs using a central controller that stores all the information about the network structure. For a comprehensive solution of the general problem of designing software-defined network structure and solving particular problems of optimizing design decisions during its synthesis, the article proposes optimization of system topology using the random search method and the tree structure method. The results of the proposed methods are compared and recommendations are given for combining these methods.
Like all modern technologies, software-defined networks (SDN) are constantly being improved, undergoing processes of modification and modernization. Taking into account the complexity of these technologies, improvement processes for objective reasons are quite lengthy. And although all of them are aimed at the possibility of exchanging various kinds of information, increasing its reliability, transmission speed and reliability of the network elements functioning, their common component is the topological structure of the system. Therefore, the question of the software-defined network structure optimal synthesis is relevant and quite popular.
According to the range of services provided, software-defined networks belong to
data transmission systems [
When solving the problem of a software-defined network structure synthesing, the following are used as performance indicators: ─ reduced costs for the creation and operation of the network; ─ characteristics of software-defined network structure reliability; ─ the reliability of consumer information; ─ average response time of network nodes to a request; ─ average message transmission time; ─ network congestion.
Consider those of the indicators that are most often used to assess the effectiveness of software-defined network.
The cost of software-defined network Ws is estimated by the quoted annual costs,
which take into account both capital and operating costs. Topology of any information
transmission system, and SDN is no exception, can be represented formally as a
symmetric G – graph. Network elements form the vertices of the graph, and data
transmission channels form the edges of the graph [
Evaluation of network topology effectiveness can be based on indicators that characterize the structure of the graph. Such indicators may be: ─ redundancy of the structure Rs. This indicator determines excess of the total number of connections m over their minimum necessary number n-1 (where n is the number of nodes), which ensures network connectivity. ─ uneven structure of Ns. The exponent Ns determines quadratic deviation of connections distribution of given network from a uniform distribution. ─ diameter of the structure Ds. This indicator determines maximum distance of network nodes. ─ compact structure Bs. The indicator Bs characterizes general proximity of the nodes to each other. ─ the degree of Cs structure centralization. This indicator displays relative number of connections that are established through the central controller.
Redundancy of Rs structure in a certain extent characterizes reliability, that is, one of the stability components and affects the efficiency of the SDN. At Rs = 0 (star, tree topology) failure of any element (link or node) produces a partial or complete decay of the network. An increase in the Rs value reflects an increase in the reliability of SDN structure, however, a large redundancy (for example, complete interconnection) makes the network economically disadvantageous and difficult to implement.
Non-uniformity of Ns structure also characterizes reliability of SDN structure, but
only from the point of view of the effect of individual elements failures. Structures
with large values of Ns (star, ring tree, distributed star) are less reliable than with
lower values of unevenness. At Ns = 0 (ring, regular, complete interconnection)
disconnection or failure of a structure node does not disable the network, but only
reduces its performance [
Diameter of Ds structure and Bs structure compactness determine the average residence time of information in the network when it is sent between nodes. An increase in Ds and Bs values generally reflects an increase in the transmission time of messages in the network. Length of data transmission path in structures with large values of Ds and Bs (ring, tree, irregular) is longer than in structures with small values of Ds and Bs (complete relationship). Thus, indicators Ds and Bs characterize both the inertia of information processes and, to a certain extent, the survivability and noise immunity of SDN. The lower values of Ds and Bs are the more efficient network structure is, since its topology with such indicators has a shorter data transmission path and, consequently, a short residence time of the message in the transmission system. In addition, in the network structure of this type there are no communication channels, failure of which leads to the breakdown of the SDN into individual elements.
In general case, degree of Cs structure centralization indicates the presence or absence of a central node in networks, and this determines the control method (centralized, decentralized, and centralized-decentralized). Since the software-defined network is completely controlled from the central controller, the degree of centralization in the SDN affects its reliability, operating efficiency in terms of performance of its individual elements, as well as the software and technical complexity of the processes for managing all network resources. Cs values are close to one and equal to it (star, ring tree, tree) show that the systems structures are centralized, and failure of central node leads to complete destruction of network. Large degree of centralization in SDN is also associated with uneven distribution of the load among the system elements, which determines the necessity to create a central controller with high output. In the case of a network structure with Cs values close to zero or equal to zero (ring, regular, complete interconnection), network should spend a considerable part of time on organizing and managing the exchange of information between nodes, in other words, a software-defined network works like a regular peer-to-peer network.
Analysis of typical structures shows that Rs, Ns, Ds, Bs and Cs characterize their survivability, reliability, performance, and cost. Therefore, using these indicators, it is possible to evaluate the network efficiency in a topological sense.
Considered indicators have different dimensions and are subject to various methods of extremization (some of them require minimization, and the rest require maximization). Therefore, it is necessary to bring them to a dimensionless form and to a single method of extremization, for example, to make them minimized. After these operations, we obtain normalized particular criteria of R0, N0, D0, B0, C0 effectiveness and W0 cost.
It is believed that these indicators equally characterize the components of efficiency, therefore, their weight differentiation is impractical. In this case, aggregated criterion of SDN topology effectiveness can be determined by the following formula: F0 R0 N0 D0 B0 C0 , F0 0;1.
5
In the case of nonlinear compromise scheme [
Consider two algorithms to solve the problem. This is optimization by random search
and using the tree structure method [
In the random search method, optimization occurs by generating a certain number of connected communication networks and choosing the best option from them. As additional settings for the optimization process are: ─ minimum number of edges to be removed when generating a network Rmin; ─ maximum number of edges to be removed when generating a network Rmax, ─ number of iterations Imax.
Number of iterations means number of networks that will be generated, and from which the best option will be selected. The larger value of this parameter, the higher results reliability, as the number of considered cases increases.
Minimum number of edges to be removed – allows you to initially exclude very strongly connected networks from consideration, if it is a priori known that there is no optimal solution among them. As this value increases, the maximum number of edges in the generated networks decreases, thus, connectivity of the networks decreases.
Maximum number of edges to be removed – at the initial stage allows to exclude
from the consideration very weakly connected networks, if it is known that there is no
optimal solution among them. When this value decreases, connectivity of the created
networks increases [
Network generation is as follows. A fully connected network is created. After that, number R is randomly generated that sets number of edges removed from the network:
Rmin R Rmax .
After that it is randomly removed from the fully connected network of, R edges. It is
controlled so that the network remains connected. For the network thus obtained, the
calculation of the values of particular criteria is performed. After that, the generalized
criterion is calculated using the nonlinear compromise scheme [
Consider the description of the algorithm more detailed.
Step 0. Create a random network S0. Set is as initial and optimal. SOPT = S0. ФOPT = Ф0.
Step 1. While I < IMAX repeat. Create a random network SI. If ФI < ФОРТ, then put SOPT = SI. ФOPT = ФI.
Step n. Output optimization result SOPT, ФOPT..
Step 0. Create a fully connected network.
Step 1. Randomly determine the integer R: Rmin < R < Rmax
Step 2. Repeat the procedure for removing a random edge R times. To remove an edge, it is randomly selected. If while deleting, the graph remains connected, then it is deleted and if not, then this edge is excluded from further consideration and another edge is selected for deletion.
In this case, optimization occurs by selecting the optimal edge for removal at each step of the iterative process.
As additional settings for the optimization process are: ─ amount of iteration Imax; ─ a sign of a stop in the absence of leafs of optimization tree with better performance than non-leaf nodes.
For optimization, a fully connected network is built, and then the edges are removed in accordance with the value of the generalized criterion. For optimization, a tree of optimal solutions is built. Its nodes are network options, and edges are the fact of removing one corresponding edge from the top-level network. Thus, the lower we move along the tree, the more edges are removed and the less remains. At each next step, the leaf vertex of the tree with the best value of the generalized optimization criterion is selected, and all possible options for removing one edge from the selected network are considered. All the obtained options and values of the generalized criterion are entered in the optimization tree, and the selected vertex ceases to be leafy. Now the best leaf vertex is again selected and the process is repeated until all leaf vertices are exhausted, the iteration counter is exhausted, or (with the stop sign turned on) a situation does not occur when the optimal solution does not belong to the leaf node.
Algorithm can be interrupted at any iteration. In this case, we get the best result for a given number of iterations.
Step 0. Create a fully connected network and set it as the root of the optimization tree S0.
Step 1. Find in the optimization tree leaf with the best value of the generalized criterion (in the first step it will be the root of the tree – since it is the only node of the tree) S = SI. Calculate all possible options for removing one edge from the network and enter the result into the optimization tree. Repeat this step until the counter reaches the limit of the number of iterations or there are no valid leaf nodes left. 5
Briefly consider the results obtained on a test example. First, we will set the initial data for optimization and the coordinates of the nodes Tables 1-2.
Conversion factor of distances from some conventional units to kilometers. Thus, coordinates of the nodes can be set in any unit of measurement (dimensionless) Cost of capital charges for the construction and operation of one kilometer of communication network (in c.u.) Return on investment (dimensionless)
After optimization by random search and tree structure methods, respectively, the following intermediate and final results of the experiment were obtained Table 3. In addition, the related nodes obtained by these methods are shown Tables 4-5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 + + + + + + + + + + + + 2 + + + + + + + 3 + + + + + 4 + + + + + + 5 + + + + + + 6 + + + + + + + + 7 + + + + + + 8 + + + + + + + + 9 + + + + + + + + 10 + + + + + + + + + + + + + 11 + + + + + + + + 12 + + + + + + + + 13 + + + + + + + 14 + + + + + + 15 + + + + + + + + 16 + + + + + + 17 + + + + 18 + + + + + + + 19 + + + + + 20 + + + + +
Thus, we see that the tree structure method provides the best indicator of efficiency, but requires large computational resources. In this regard, it seems interesting to combine both methods. A fully connected network a priori has a poor value of the optimality criterion and is far from the optimal solution. In this regard, it is inefficient to use it as a base. Thus, the random search method is effectively to be used to generate initial basic networks, and the tree structure method is to be used to improve their characteristics.
In this case, optimization is carried out in two stages. At the first stage, a random optimal network is built using the random search method, and then at the second stage it is used as the base (root) network for the structure tree method – with the help of which it is improved. Using this approach in software-defined networks will allow the central controller to significantly reduce its computing load, both in the case of the initial design of software-defined networks, and in the case of its further improvement.