Multi-Criteria Synthesis of the Software-Defined Network Structure Albert Voronin 1 [0000-0001-7201-2877], Maksym Kuklinskyi 1 [0000-0002-2028-9206], Tetyana Holyavkina 1 [0000-0003-2595-9405], Iryna Gyza 1 [0000-0002-8612-5538], Liudmila Kharlai 2 [0000-0002-7633-933X] 1 National Aviation University, Kyiv, Ukraine, 2 Kyiv College of Communication, Kyiv, Ukraine alnv@ukr.net, maximum_inc@ua.fm, holyavkina.t@gmail.com, irynagyza@gmail.com Abstract. 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 transmis- sion channels ensuring the interaction of these nodes. In the process of design- ing 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 con- troller that stores all the information about the network structure. For a compre- hensive 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 pro- posed methods are compared and recommendations are given for combining these methods. Keywords: Software-Defined Network, Data Transfer System, Topology, Op- timization, Design. 1 Introduction Like all modern technologies, software-defined networks (SDN) are constantly being improved, undergoing processes of modification and modernization. Taking into ac- count 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. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attrib- ution 4.0 International (CC BY 4.0) CMiGIN-2019: International Workshop on Conflict Management in Global Information Networks. 2 Analysis of publications and goal setting According to the range of services provided, software-defined networks belong to data transmission systems [1]. An analysis of the work showed that today, close atten- tion is paid to the research of data transmission systems. This is confirmed by a large number of publications, and caused by the fact that this topic covers a very wide range of tasks in various fields. There are many publications that classify and disclose various ways and methods of data transfer [2-5]. But in most cases they are consid- ered either in the context of generally accepted topologies of transmission systems, or without any description of the latter. There are also publications that are dedicated to the design of data transmission systems, but they mainly relate to certain industries, which narrows their scope, since they are focused on the characteristics of this indus- try only. Even fewer articles address the issue of optimizing data transmission sys- tems [6], especially in the context of software-defined networks [7]. Therefore, the purpose of this article is to develop a method for optimizing the software-defined network structure formation, and assess its effectiveness. 3 Determining performance indicators of a software-defined network 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 [6]. Evaluation of network topology effectiveness can be based on indicators that char- acterize the structure of the graph. Such indicators may be: ─ redundancy of the structure Rs. This indicator determines excess of the total num- ber 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 connec- tions distribution of given network from a uniform distribution. ─ diameter of the structure Ds. This indicator determines maximum distance of net- work 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) dis- connection or failure of a structure node does not disable the network, but only reduc- es its performance [12-14]. Diameter of Ds structure and Bs structure compactness determine the average resi- dence 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, consequent- ly, 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 ab- sence of a central node in networks, and this determines the control method (central- ized, decentralized, and centralized-decentralized). Since the software-defined net- work 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 or- ganizing 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 meth- ods of extremization (some of them require minimization, and the rest require maxi- mization). 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 efficien- cy, therefore, their weight differentiation is impractical. In this case, aggregated crite- rion of SDN topology effectiveness can be determined by the following formula: R0  N 0  D0  B0  C0 F0  , F0  0;1 . 5 In the case of nonlinear compromise scheme [8], the following expression is used as the objective function:   a1 (1  F0 ) 1  a2 (1    W0 ) 1 , a1  a2  1 , where: a1 and а2 – weighting coefficients; ε – some sufficiently small value, which serves to avoid dividing by zero at W0=1. 4 Solving the problem of software-defined network structure synthesis Consider two algorithms to solve the problem. This is optimization by random search and using the tree structure method [8, 9]. 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 [15-17]. 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 [8] taking into account the significance coefficients of the criteria. The result obtained is compared with the optimal solution received at the moment, and if it is better, it is taken as the optimal solution at this step. This procedure is repeated Imax times. 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.. Random network generation algorithm 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. Now consider the structure tree method. 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 criteri- on 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. Consider an optimization algorithm. 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 cri- terion (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 reach- es the limit of the number of iterations or there are no valid leaf nodes left. 5 Practical application of the proposed algorithms 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. Table 1. Initial data Klength=50 Conversion factor of distances from some conventional units to kilometers. Thus, coordinates of the nodes can be set in any unit of measurement (dimensionless) Wcap = 1000 Cost of capital charges for the construction and operation of one kilometer of communication network (in c.u.) En = 1 Return on investment (dimensionless) N = 20 Number of network nodes (dimensionless) Table 2. Nodes coordinates Nodes coordinates Node number Х У 1 9,5 9,7 2 10,1 14,1 3 10,6 16,7 4 10,2 15,2 5 10 12,9 6 9,9 10,9 7 8,7 11,3 8 7,7 8,8 9 7,7 6,6 10 9,1 7,7 11 6,9 4,7 12 6,8 4,2 13 8,6 3,4 14 6,2 5,3 15 7,9 5,6 16 13,4 4,4 17 17,4 4,8 18 11,5 2,2 19 14,8 5 20 13,4 4,1 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. Table 3. Comparison of optimization results Description Random search method Tree method structure Number of iterations 1000 200 Advanced options of Rmin = 50 methods settings Rmax = 171 Rs: 2,10526315789474 Rs: 2,78947368421053 Ns: Ns: 0,00143203681593325 0,00205331184815511 Ds: 2 Ds: 3 Bs: 0,621052631578947 Bs: 0,768421052631579 Cs: 0,376623376623377 Cs: 0,214285714285714 Ws: 12557937,8514079 Ws: 16944651,7100879 Kr: 0,690058479532164 Kr: 0,766081871345029 Kn: 0,0014320368159333 Kn: 0,0020533118481551 Kd: 0,2 Criteria values Kd: 0,3 Kb: 0,145679012345679 Kb: 0,180246913580247 Kc: 0,376623376623377 Kc: 0,214285714285714 Kw: 0,203164838561053 Kw: 0,274133975648503 Fs1: 0,282758581063431 Fs1: 0,292533562211829 Fs: 1,32459769651696 Fs: 1,39557965832538 Best Fs: Best Fs: 1,32417186843977 1,39557965832538 Table 4. Connected nodes during random optimization 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 + + + + + + Table 5. Connected nodes during optimization using the structure tree method 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 + + + + + 6 Conclusion 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 com- bine both methods. A fully connected network a priori has a poor value of the opti- mality 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 improve- ment. References 1. A.E. Kolomeets, L.V. Surkov, Software-defined SDN Networks – A Fundamentally New Approach to Networking, Modern computer systems and technologies: department collected works “Computer systems and networks” MSTU. named after N.E. Bauman, 2014, pp. 33-42. 2. Telecommunication systems and networks: Textbook: T.1 – Modern technologies / B.I. Kruk, V.N. Popantonolulo, V.P. Shuvalov; under the editorship of professor V.P. Shuvalova. – Ed. 3rd, fixed and added, Moscow: Hot line – Telecom, 2003, 647 p. 3. Marder N.S. Modern telecommunications, M.: IRIAS, 2006, 384 p. 4. Abilov A.V. Communication networks and switching systems: Textbook for universities, Moscow, Radio and communications, 2004, 288 p. 5. V.G. Olifer, N.A. Olifer, Computer networks. Principles, technologies, protocols, St. Pe- tersburg. : Publishing house “Peter”, 2000, 672 p. 6. Gostev V.M. System for optimizing the design of data transmission networks, Memoirs of KNU: Physics and mathematics, 2007, Vol. 149. Book 2, pp. 35-48. 7. Mazin Al Hadidi, J. Samih Al-Azzeh, O. Tkalich, R. Odarchenko, S. Gnatyuk, Yu. Khokhlachova. ZigBee, Bluetooth and Wi-Fi Complex Wireless Networks Performance Increasing, International Journal on Communications Antenna and Propagation, Vol. 7, № 1, рр. 48-56, 2017. 8. Vetelina E. Study of development trends of modern network technologies using software- defined networks as an example, New information technologies in automated systems, № 18, 2015, pp. 502-508. 9. A.N. Voronin, Y.K. Ziatdinov, M.V. Kuklinskyi, Multicriteria solutions: models and methods: monograph, Kyiv, NAU, 2011, 348 p. 10. V.S. Mikhalevich, A.I. Kuksa, Methods of sequential optimization, Moscow: Nauka, 1983, 208 p. 11. Roman Odarchenko, Serhii Dakov, Olexandr Oksiuk and Larisa Dakova, Software- Controlled Network SDN Reliability Calculation 5th International Scientific-Practical Conference Problems of Infocommunications Science and Technology, PICS&T 2018, Conference Proceedings, pp. 99-103. 12. S. Gnatyuk, A. Okhrimenko, M. Kovtun, T. Gancarczyk, V. Karpinskyi, Method of Algo- rithm Building for Modular Reducing by Irreducible Polynomial, Proceedings of the 16th International Conference on Control, Automation and Systems, Oct. 16-19, Gyeongju, Ko- rea, 2016, рр. 1476-1479. 13. Al-Azzeh J.S., Al Hadidi M., Odarchenko R., Gnatyuk S., Shevchuk Z., Hu Z. Analysis of self-similar traffic models in computer networks, International Review on Modelling and Simulations, № 10(5), pp. 328-336, 2017. 14. R. Odarchenko, V. Gnatyuk, S. Gnatyuk, A. Abakumova, Security Key Indicators As- sessment for Modern Cellular Networks, Proceedings of the 2018 IEEE First International Conference on System Analysis & Intelligent Computing (SAIC), Kyiv, Ukraine, October 8-12, 2018, pp. 1-7. 15. Z. Hassan, R. Odarchenko, S. Gnatyuk, A. Zaman, M. Shah, Detection of Distributed De- nial of Service Attacks Using Snort Rules in Cloud Computing & Remote Control Sys- tems, Proceedings of the 2018 IEEE 5th International Conference on Methods and Systems of Navigation and Motion Control, October 16-18, 2018. Kyiv, Ukraine, pp. 283-288. 16. M. Zaliskyi, R. Odarchenko, S. Gnatyuk, Yu. Petrova. A.Chaplits, Method of traffic moni- toring for DDoS attacks detection in e-health systems and networks. CEUR Workshop Proceedings, Vol. 2255, pp. 193-204, 2018. 17. I. Parkhomey, S. Gnatyuk, R. Odarchenko, T. Zhmurko et al, Method For UAV Trajectory Parameters Estimation Using Additional Radar Data, Proceedings of the 2016 4th Interna- tional Conference on Methods and Systems of Navigation and Motion Control, Kyiv, Ukraine, October 18-20, 2016, рр. 39-42.