Controller placement problem in industrial networks

Technische Universität München Lehrstuhl für Kommunikationsnetze Prof. Dr.-Ing. Wolfgang Kellerer Bachelor‘s Thesis Controller Placement Problem in Industrial Networks Author: Macián Ribera, Sergi Address: Clemenstrasse 127 80796 München Germany Matriculation Number: 03679617 Supervisor: Petra Stojsavljevic Begin: 01. April 2016 End: 30. September 2016 With my signature below, I assert that the work in this thesis has been composed by myself independently and no source materials or aids other than those mentioned in the thesis have been used. München, 25.10. 2016 ------------------------------- ------------------------------- Place, Date Signature This work is licensed under the Creative Commons Attribution 3.0 Germany License. To view a copy of the license, visit http://creativecommons.org/licenses/by/3.0/de Or Send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA. München, 25.10. 2016 ------------------------------- ------------------------------- Place, Date Signature Abstract SDN (Software Defined Networking) architecture has become a trending topic nowadays due to it has been seen that this architecture satisfies the necessary requirements to be considered as a high capacity and reliable network by splitting the data and control plane. This control plane is performed by one or more controllers. An SDN controller is a software running on a host server, which is attached to one of the switches in case of in-band signalling. It has been proven that logically centralized architecture, provide really good results, e.g.., it can afford strict latency and reliability requirements, but it is still under study. This thesis focuses on the primary problem that concerns SDN, where and how many controllers are needed to be deployed in a network. Generally, more than one controller is required because of reliability constraints. This problem is named Controller Placement Problem, also CPP, and there is not a unique answer to this question, since different criteria can be considered, such as switch to controller latency, load balance between the controllers, etc. Moreover, the behaviour of industrial networks when using SDN architecture is studied. The motivation to apply SDN to industrial networks is to see how this architecture works with them, i.e., a study using SDN and industrial networks will be done in order to try to find a feasible solution for the CPP problem when using this kind of networks. Another problem this thesis is focused on is how to decrease the elapsed time when evaluating the CPP problem for a network. An exhaustive evaluation of all possible controllers’ placements is not realistic due to the fact that it can last several hours or even days and a fast response is needed in case that there is a failure. That is the reason why a metaheuristic algorithm named PSA is used and also studied. In this thesis, an algorithm that mixes Pareto Simulated Annealing (PSA) algorithm and Integer Linear Programming (ILP) problem is also studied in order to see if it can improve the way of computing the CPP problem making it faster and more precise. Acknowledgments In this section I am going to thank all staff who helped me with the development of this thesis and that has been close to me during this semester that I have lived abroad, in Munich. First of all, I want to thank Petra Stojsavljevic, Carmen Mas and Jose Antonio Lázaro for helping and supporting me before and during the whole semester. Firstly, Jose Antonio helped me to contact TUM University and Carmen Mas and then, they agreed on my thesis project. During the development of the thesis, all my professors have been really attentive to me, i.e., they were always there for any doubts I had and they helped me to do my best. I would also like to thank both Universities, TUM and UPC, and all institutions behind the Erasmus program for giving me the chance to study abroad during a semester. In my modest opinion, everyone should try this experience. It is a perfect way to open your eyes to new cultures, learn and improve languages and understand how other universities work. Obviously, I really want to thank my family. It has always been there in all difficult moments, cheering me up and making this experience come true. Finally, I also want to thank some friends from Barcelona like Jaume Baltasar for helping me with some doubts about SDN and making me laugh even from a large distance and Jordi Mañes for sharing with me some nice experiences during the Erasmus and helping me with the accommodation. From Munich, I have to thank Alba Luján for helping me with bureaucratic stuff and for keeping me motivated while studying together in the library. v Contents Chapter 1 Introduction ................................................................................................ 7 Chapter 2 Background ................................................................................................ 9 2.1. Software-Defined Networking .................................................................... 9 2.2. Industrial networks .................................................................................... 10 Chapter 3 Controller Placement Problem ............................................................... 13 3.1. Introduction ............................................................................................... 13 3.2. State of the Art ........................................................................................... 13 3.3. Performance metrics .................................................................................. 16 3.4. Pareto Frontier ........................................................................................... 19 Chapter 4 Integer Linear Programming ................................................................. 20 4.1. Introduction ............................................................................................... 20 4.2. Problem formulations ................................................................................ 20 Chapter 5 Pareto Simulated Annealing ................................................................... 22 5.1. Introduction ............................................................................................... 22 5.2. State of the Art ........................................................................................... 22 5.3. Algorithm ................................................................................................... 24 5.4. Pareto Frontier Distances ........................................................................... 28 Chapter 6 Implementation/Results .......................................................................... 29 6.1. Exhaustive evaluation ................................................................................ 29 6.2. ILP ............................................................................................................. 35 6.3. PSA ............................................................................................................ 36 vi Chapter 7 Conclusions and Outlook ........................................................................ 49 Chapter 8 Formatting ................................................................................................ 50 8.1. List of figures ............................................................................................. 50 8.2. List of Tables ............................................................................................. 52 8.3. Notation and Abreviations ......................................................................... 53 8.4. References ................................................................................................. 54 Appendix A ................................................................................................................. 55 Chapter 1 Introduction Nowadays, IT technologies such as communication architectures are constantly improving. Operators and users are looking for more reliable and with higher bit rate networks, SDN (Software Defined Networking) architecture is being studied in order to achieve both goals. The main ideas of these networks are:  To split data plane and control plane  Decide which nodes perform the function of controllers.  To connect each switch to one controller at least. This one will decide the optimal routing the packets from one switch to another one. The problem that is tried to be solved in this study is to find the optimal controller placement, i.e., where and how many controllers have to be deployed in a network in order to ensure the fastest and most reliable communication. This problem is called CPP (Controller Placement Problem) and will be studied in this thesis. When the optimal allocation placement for controllers is considered, there are several criteria that must be taken into account and that must be optimized. The controller placement performance metrics used in this thesis are average and worst-case latencies from controllers to other switches, average and worst-case latencies between controllers, controller’s load and reliability. Some of them, such as switch to controller latency and load balancing cannot be always optimized at the same time. Hence, a trade-off between these metrics has to be always studied. Some studies about controller placement have already been done. They have found a specific solution for a single metric or have mixed two of them and have found the Pareto-Frontier between these two metrics. This one determines when both metrics have the best values. Hence, if one metric is improved the other one will get worse and vice versa. One of the purposes of this project is to continue studying SDN architecture, develop the code capable to compute the controller placement problem (CPP) and analyse the obtained results in order to find the optimal solution for different metrics at the same time. In this thesis, industrial topologies will be used. Our study compares their behaviour with the one in other typical networks, like the ones in database of operational wind parks [11]. Chapter 1. Introduction 8 Controller placement problem is NP-hard and it requires a huge amount of time –hours or even daysfor a normal computer, a heuristic method is developed in order to reduce this time. However, some points in the Pareto-Frontier may not be computed. This metaheuristic evaluation is named PSA (Pareto Simulated Annealing) and will be explained later. The second goal of this project is to study how distances between Pareto-Frontier computed with an exhaustive evaluation and Pareto-Frontier computed with PSA method vary in order to fine tune the PSA parameters, such as the number of iterations and the number of placements evaluated in each iteration. A new algorithm that combines PSA and ILP problem is also studied. Then, its results are compared with results from the commonly used PSA algorithm in order to see which algorithm is better. This project has been carried out at the department of Electrical and Computer Engineering at Technische Universität München (TUM). The thesis will be developed as a part of a bigger project already started at TUM. It is called VirtuWind and its main goal is to study some offshore Wind Parks with a central station, named SCADA, where the communication system will be controlled by SDN architecture. Networks presented in VirtuWind [10] are considered industrial topologies and some of them will be used in this thesis. As it is said in the title of the thesis, it focuses on industrial networks. This kind of networks is later explained in Chapter 2.2. This project is structured as follows: Chapter 2 presents the background information of the main topics of the thesis; Software Defined Networking and industrial networks. In Chapter 3, the CPP problem is described jointly with its SoA, the explanation of some metrics used in this thesis and a description of the meaning and computation of the Pareto Frontier. Then, in Chapter 4, Integer Linear Programming (ILP) problem is presented and its computation is explained. Chapter 5 presents PSA algorithm, in a brief introduction and SoA is explained why this metaheuristic algorithm is used. The code structure and evaluation methodology are presented. Then, Chapter 6 contains the obtained results in this thesis and in Chapter 7 the main conclusions and also future work are presented. Motivation This project has been developed with the objective of studying and improving SDN architecture technology, trying to solve its CPP problem obtaining the best relation between elapsed time and accuracy of the obtained values - distance between the Pareto Frontier obtained from metaheuristic algorithm and the Pareto Frontier obtained from an exhaustive evaluation -. PSA algorithm and ILP problem will be studied together and by separate in order to achieve this goal. The main motivation is to find a good algorithm that can be later overextended and implemented in real networks. Chapter 2. Background 9 Chapter 2 Background 2.1. Software-Defined Networking Nowadays, network architectures have a control plane and a data plane working on the same level, i.e., all nodes can control where and how to send packets at the same time that they are forwarding them. This means that each switch has its own control logic. Due to increasing traffic and flexibility demands, new network architectures are required. SDN is an architecture that is still under study, but it seems to be the solution for these problems. In SDN architecture, control and data planes are decoupled. The control plane is performed by one or more controllers. These SDN controllers are a software running on a host server, which is attached to one of the switches in case of in-band signalling. They have an overview of the network and they can decide for other switches the routes they have to forward and communicate it through OpenFlow Protocol. That’s why SDN is considered as a logically centralized architecture. All deployed nodes in the network, which can contain a controller or not, are also called switches. In the following figure 2.1 [12], a legacy switch is shown on the left and a SDN switch is shown on the right. The legacy switch decides the forwarding path and also forwards the data, i.e., it executes control plane and data plane functions. On the other hand, the externally controlled switch - a SDN switch - just forwards data, but does not decide the route. Figure 2.1 Traditional Switch vs SDN Switch [12] A switch cannot send any packet until it receives the flow table provided by the controller. The larger latency is the time that the receiver is waiting for this flow table. Therefore, the propagation delay, proportional to the distance, between a switch and a controller is considered as the latency of the network. Chapter 3. Controller Placement Problem 16 In document [2], Zoo topologies are used and evaluated taking into account resilience and latency metrics. It is concluded that in order to reach the zero value for πcontroller-less metric when considering outages in a node, controller or edge, a high number of controllers must be deployed. Therefore, one controller is not enough when considering possible outages. Figure 3.2 Latencies versus number of controllers. Figure 6 in [1]. The studies done in [3] and [4] take into account the reliability and it is concluded that in the large majority of topologies, the number of controllers that should be deployed is between [0.035n - 0.117n]. If there are not enough controllers used, there are longer paths between nodes and, therefore, more elements can fail in between. On the other hand, if there are a lot of controllers, there are more control paths. And then, there are also more paths that can fail. The term Pareto Frontier is also used in [1]. It is described as a trade-off between two or more metrics. That means that a metric cannot be minimized in return for increasing another metric at the same time, i.e. when a metric is improved by choosing the best controller’ allocation for it, another metric is getting worse. The exact Pareto Frontier is obtained by an exhaustive search, but it can require a high time to compute it. That is why, in this thesis, a metaheuristic algorithm named Pareto Simulated Annealing is used. However, the Pareto Frontier obtained from this algorithm is just an estimation of the one obtained from an exhaustive evaluation. In this thesis is studied how this estimation differs from the real Pareto Frontiers and how it can be improved, i.e., how its accuracy can be optimized. 3.3. Performance metrics As it is said in the State of the Art (SoA), there are a lot of metrics that can be considered in order to evaluate a controllers’ placement. In this study, all those metrics that do not include node, link or controller failures are evaluated. I.e., metrics which take failures into account are not considered in this thesis. However, availability metric of the Network is also taken into account. Then, in this study, the following performance metrics that will be evaluated for each controller’s placement: Chapter 3. Controller Placement Problem 17 - Average distance nodes-controllers - Worst-case distance nodes-controllers - Inter controller Average distance (controllers-controllers) - Inter controller Worst-case distance (controllers-controllers) - Load imbalance - (un)availability The objective is to minimize the obtained values for these metrics, with the exception of availability. For this reason in this thesis unavailability is used instead of availability. It is considered that all nodes are connected to the closest controller and that there are not restrictions of number of nodes per controller, i.e., there is not maximum nor minimum load per controller. Average switch to controller latency First of all, the word latency has to be defined. It refers to the time interval between the source sending a packet and the destination receiving it. For SDN technologies, as it is said in [1], the most restrictive latency in this kind of communications is the propagation delay between nodes and controllers, which is proportional to the distance between nodes and controllers. Then, for this metric the average distance between placed controllers and all nodes assigned to them is computed. Therefore, it has to be seen which nodes are connected to each controller and then obtain their distances. In order to compute the average latency the following formula is used: 𝐿𝑎𝑣𝑔 (𝑆′)=1 𝑛 ∑min (𝑗 ∊𝑆′)𝑑(𝑖,𝑗) (3.2) 𝑖 ∊𝑉 Worst case switch to control latency The worst-case distance between controllers and nodes can also be computed. Then, it has to be seen which nodes are connected to each controller and obtain their distances. From all these distances, this metric focuses on the largest one, the worst-case latency. Its expression is: 𝐿𝑤𝑐 (𝑆′)=max (𝑖∊𝑉) min (𝑗 ∊𝑆′)𝑑(𝑖,𝑗) (3.3) Average latency inter-controllers In SDN architectures the data and control paths are separated, i.e. there is data and a control plane. The control plane consists of a subnetwork created just by controllers. For this reason, the latencies between these controllers are also important. Therefore, the average distance and worst case distance between controllers must be also computed. In order to compute this metric, d matrix must be modified. A new d(ci,cj) is created from d(i,j) that includes de shortest distance from controller ci to controller cj. It can be Chapter 3. Controller Placement Problem 18 created by removing all rows and columns from d(ci,cj) that do not contain a controller. Then, the following formula can be computed: 𝐿𝑎𝑣−𝐼𝐶=1 𝑘∑ 𝑑(𝑐𝑖,𝑐𝑗) 𝑐𝑖,𝑐𝑗∈𝑆′ (3.4) Worst-case latency inter-controllers In this metric the maximum distance that separates controllers is computed. First, the same procedure used for Average inter-controller Latency to obtain d(ci,cj) must be followed. But then, instead of computing the average distance from all controllers to other controllers, just the highest value is chosen. The regular formula to compute it is: 𝐿𝑤𝑐−𝐼𝐶= max 𝑐𝑖,𝑐𝑗∈𝑆′𝑑(𝑐𝑖,𝑐𝑗) (3.5) Load imbalance In this metric, the difference between the maximum and minimum number of nodes connected to different controllers is computed, i.e. a 0 value would be obtained when all controllers have the same number of assigned nodes. As it is said in [16] the optimal situation is given when each controller has assigned between ⌊𝑛 𝑘⌋ and ⌊𝑛 𝑘⌋+1 nodes. Considering nc as the number of nodes assigned to the controller c, the Load Imbalance can be computed using the following formula: 𝜋𝑙𝑏(𝑆′)= max 𝑐∈𝑆′𝑛𝑐− min 𝑐∈𝑆′𝑛𝑐 (3.6) Availability In this metric the probability of failure in the connection between a controller and the nodes assigned to it is calculated. It is considered that every switch and edge that is used to communicate node A with node B has a probability of failure so, the more switches there are and the longer edges are, the higher probability of failure there will be. Firstly, it is computed matrix a(i,j) that contains the availability between node i and node j, using the shortest path to connect them. The node failure probability and link failure probability are represented with fl and fn, respectively. In order to compute the availability between two nodes i and j, the following formula is used: 𝑎(𝑖,𝑗)=𝑎(𝑗,𝑖)=(1−𝑓𝑛)|𝑝𝑎𝑡ℎ(𝑖,𝑗)|= ∏ (1−𝑓𝑙·𝑑(𝑥,𝑥+1)) 𝑥=𝑝𝑎𝑡ℎ(𝑖,𝑗) (3.7) Where path(i,j) is a vector that contains all nodes that perform the shortest route between node i and j. Chapter 3. Controller Placement Problem 19 For a particular controllers’ deployment, the value of the worst availability between a node and a controller is saved since it is the most restrictive. However, it is transformed to unavailability due to this is the metric that has to be minimized. Then: 𝜋𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑆′)= min 𝑖,𝑗 ∈𝑆′𝑎(𝑖,𝑗) (3.8) 𝜋𝑢𝑛𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑆′)=1− 𝜋𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑆′) (3.9) 3.4. Pareto Frontier The Pareto Frontier is made out one or more different points. If two metrics are considered it will be represented as a line and if three metrics are considered it will be represented as a plane. When two or more metrics are evaluated, normally a solution that satisfies all of them at the same time cannot be found. I.e., there is normally a tradeoff between these two or more metrics. When one of them improves its value, the other one gets worse and vice-versa. As the objective is to minimize both metrics, values on the low-left side of the graphic are the important ones. In [7], Pareto-Frontier is defined as: “A placement x is considered Pareto optimal, if only if there is no placement y such that ∀𝑖 𝑓𝑖(𝑦) ≤𝑓𝑖(𝑥) and 𝑓𝑖(𝑦)<𝑓𝑖(𝑥) for at least one i.” I.e., x is considered to be part of the Pareto-Frontier when there is not another placement y which its evaluated metrics 𝑓𝑖(𝑦) are lower or equal to 𝑓𝑖(𝑥), for at least one metric i. Then, the Pareto Frontier set is created by all these Pareto optimal placements. As it is seen in figures 3.2 and 3.3 all subset of controller’s placements which values are in the Pareto Frontier have been colored in red and the blue line represents the Pareto Frontier. Figure 3.2 Example of Pareto Frontier Figure 3.3 Example of Pareto Frontier (zoomed) Chapter 4 Integer Linear Programming 4.1. Introduction In order to obtain the optimal value of a metric, all possible controllers’ placements had to be computed and the best one had to be chosen, i.e., an exhaustive evaluation was computed. This method requires a lot of processing time due to in some networks there are a lot of possibilities to evaluate. For this reason, in this chapter Mixed Integer Linear Programming -MILPproblem is presented and defined. On the one hand, this method can reach an optimal allocation consuming much less time than an exhaustive evaluation. But, on the other hand, it cannot compute a Pareto Frontier between two metrics. It will not be useful due to it can just provide the two limits that perform this trade-off known as Pareto Frontier, not obtaining the rest of points that are also included. Moreover, it can return an optimal placement that it is not even in the Pareto Frontier since there can be more than one optimal placement. As it is explained later in chapter 6.1.2, there are just three metrics that must be taken into account: Average Latency, Inter Controller Average Latency and Load Imbalance. For each metric some variables, some constraints and, in our case, a function to minimize must be declared. 4.2. Problem formulations Average Latency The following expressions are all provided by [10] and with them an optimal controllers’ allocation in our networks can be found. For the Average Latency the following expression 8 is used. 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: ∑∑𝑥𝑖,𝑗𝑑𝑖,𝑗 𝑛 𝑗=1 𝑛 𝑖=1 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜: ∑𝑥𝑖,𝑗 𝑛 𝑗=1 =1,∀𝑖∈{1,..𝑛} (4.1) ∑𝑦𝑗 𝑛 𝑗=1 =𝑘 𝑥𝑖,𝑗 ≤ 𝑦𝑖,𝑗 ,∀𝑖,𝑗∈{1,..𝑛} Where xi,j is 1 when node i is controlled by node j, otherwise its value is 0. Variable yj is 1 when a controller is placed in node j. Finally, as it happens in CPP problem, di,j Chapter 4. Integer Linear Programming 21 contains the shortest distance between node i and node j, n is the total number of nodes and k is the number of controllers. Inter-Controller Average Latency Then, for optimizing the Inter-controller average latency the next expression can be used: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: ∑∑𝑦𝑖𝑦𝑗𝑑𝑖,𝑗 𝑛 𝑗=1 𝑛 𝑖=1 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜: ∑𝑥𝑖,𝑗 𝑛 𝑗=1 =1,∀𝑖∈{1,..𝑛} (4.2) ∑𝑦𝑗 𝑛 𝑗=1 =𝑘 𝑥𝑖,𝑗 ≤ 𝑦𝑖,𝑗 ,∀𝑖,𝑗∈{1,..𝑛} Load Imbalance Finally, in order to compute the load imbalance between controllers it can be used: 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: ∑∑𝑥𝑖,𝑗𝑑𝑖,𝑗 𝑛 𝑗=1 𝑛 𝑖=1 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜: ∑𝑥𝑖,𝑗 𝑛 𝑗=1 =1,∀𝑖∈{1,..𝑛} ∑𝑦𝑗 𝑛 𝑗=1 =𝑘 (4.3) 𝑥𝑖,𝑗 ≤ 𝑦𝑖,𝑗 ,∀𝑖,𝑗∈{1,..𝑛} ∑𝑥𝑖𝑗 𝑛 𝑖=1 ≤⌈𝑛 𝑘⌉,∀𝑗∈{1,..𝑛} In this case, a maximum load value for the controllers is fixed. As it can be seen in the last expression, the maximum load per controller is ⌈𝑛 𝑘⌉. E.g., if there are 32 nodes and 4 controllers, there would be a maximum of 8 controllers per node. Chapter 5 Pareto Simulated Annealing 5.1. Introduction When the CPP problem is solved using an exhaustive evaluation it is consuming a lot of time since there are a lot of possible controllers’ placements to evaluate. As it is shown in the next table, when the number of controllers is increased, the required time increases exponentially. As a lot of controllers’ possible placements have to be evaluated, too much time is elapsed. In a real SDN network this time is not tolerable due to a fast response is required. That is the reason why a metaheuristic algorithm must be used. It will try to find the best controllers’ placement computing just a small number of placements. I.e., the search space is reduced, so it spends less time. 5.2. State of the Art In paper [3] different algorithms are compared; Random Placement, l-w-greedy, Simulated Annealing and Brute Force. Their conclusion is that Simulated Annealing (SA) is the he algorithm that obtains the best relation between elapsed time and distance from the exhaustive evaluation Pareto Frontier and the algorithm Pareto Frontier, named accuracy, i.e. in [3] it is concluded that Simulated Annealing is the best metaheuristic algorithm that can be used. The objective in document [7] is to improve POCO, a program that computes an exhaustive evaluation, using a heuristic approach. PSA is the chosen and studied one. Firstly, the algorithm is introduced and it is explained how it works step by step, also including some formulas written in this thesis in Chapter 5.3. Hence, in our study, the PSA algorithm explained in [7] will be used and also some expressions from [8]. In order to compare and study the PSA algorithm, two variables named Relative Budget brel and Relative Time Consumption trel are defined in [7] as follows: 𝑏𝑟𝑒𝑙=𝑏𝑃𝑆𝐴 𝑏𝑃𝑂𝐶𝑂=𝑚·𝑠·⌈− 𝑙𝑜𝑔𝑇𝑜 log𝑝⌉ (𝑛 𝑘) (5.1) 𝑡𝑟𝑒𝑙=𝑡𝑃𝑆𝐴 𝑡𝑃𝑂𝐶𝑂 (5.2) Chapter 5. Pareto Simulated Annealing 23 Relative Budget and Relative Time Consumption compare number of evaluated placements and time between PSA algorithm and the exhaustive evaluation used in POCO. A conclusion obtained in [7] is that the larger size of the Search space in a network, i.e., the number of evaluated placements(𝑛 𝑘) in an exhaustive evaluation, the more are reduced brel and trel. I.e., the relation between the number of evaluated placements when using PSA and when using exhaustive evaluation is lower when using large scale networks with high number of controllers and it happens the same with the relation of time. In the following figure 5.1, 60 networks from Zoo Topologies have been evaluated with different number of controllers, obtaining different sizes for the Search Space. The PSA algorithm has been computed 40 times and if the accuracy of at least fmin % of repetitions are below the accuracy threshold (0.01 or 0.02), then the parameters of the PSA are accepted and the relative budget can be computed. If not, PSA parameters are increased in order to increase iterations in the PSA and reduce the accuracy. As it is seen in figure 5.1, the larger size of the Search Space, the smaller Relative Budget is needed. This result means that the bigger Search Space, the more profitable PSA is. Figure 5.1 Relative budget for different Size of Search Space in order to achieve an accuracy level. Figure 5 in [7]. In [5], it is said that when large scale SDN networks are used, our networks often have to be adapted changing the controllers’ position, and it has to be done quickly. The problem is that the elapsed time and memory requirements are too high if all metrics for all possible placements are evaluated, i.e. if an exhaustive evaluation is computed. In this paper [5], Pareto-Capacitated K-Metoids (PCKM) and SA are studied and compared. PCKM is a heuristic algorithm that improves two particular metrics; average latency and imbalance. On the other hand, PSA algorithm is not focused on any particular metric. Its conclusions are that algorithms focused on particular metrics, like PCKM, work better than generic ones, like PSA, when simulating the Pareto Frontier for the metrics they are specialized for. However, this algorithm works worse for other metrics. As there are more metrics to compare, this thesis will consider the PSA instead of PCKM due to it computes several metrics. Chapter 5. Pareto Simulated Annealing 24 5.3. Algorithm In order to program a code capable to compute the PSA metaheuristic algorithm this thesis has followed steps used in [7] and [8]. In [7] PSA is presented as follows: Input values There are several parameters that must be given to the PSA algorithm and that determine its way of working and will influence the obtained result. The first parameter that must be given is the network and the metrics that are going to be evaluated. Then, there are several PSA parameters that will be used in the performance of the algorithm: - s: number of initial random placements from where PSA algorithm starts. - m: number of iterations per temperature level. - To: initial temperature level, it also controls the probability of accepting movements to worse values. - p: temperature decrease with the number of iterations. It’s a value ranged from 0 to 1 that reduces the temperature level every m iterations. Depending on these parameters some characteristics can be increased or decreased like the running time, repetitions of the experiment, dispersion and probability of acceptance of worse values. Generate random placements and compute random weights The next step is to generate some random placements from where our code will start working and assign them some random weights. As explained in [8], in order to compute these random weights it just hast to be taken into account that they all have to Algorithm: Pareto Simulated Annealing 1: Input: G = (V,E),k,s,m,To,p 2: n = |V| 3: S = generateRandomPlacements(n,s,k) 4: Λ = generateRandomWeights(S) 5: M = paretoFrontier(evaluatePlacements(S)) 6: T = To 7: while T > 1 do 8: Y = drawNeighbours(S,n,⌈𝑘𝑇 2𝑇𝑜⌉) 9: updateParetoFrontier(M,Y) 10: Λ = updateWeights(S) 11: S:= accept yЄ Y with probability P(S,Y,T, Λ) 12: if m iterations were performed at T 13: T = T ρ 14: end if 15: end while 16: return M and corresponding placements Table 5.1 PSA Algorithm Chapter 5. Pareto Simulated Annealing 25 be positive and sum 1, i.e. ∀𝑗 𝜆𝑗≥0 𝑎𝑛𝑑 ∑𝜆𝑗=1 𝑗. The random placements are saved in a variable named S. Create the Pareto-Frontier The next step is to evaluate the randomly generated placements. Then, the optimal values are added to the Pareto-Frontier. E.g., if s=3, three random placements are generated and then evaluated, those values that contain minimums will be added to the Pareto-Frontier. This Pareto-Frontier will be later updated with new obtained values for other placements. At the end of the PSA algorithm a Pareto-Frontier containing all the best evaluated placements is returned. Inside the loop Right after that, a loop that will be repeated as many times as we want depending on the variables m, To and p starts. The following expressions provided in [7] can be used to know how many times the loop will be computed and the maximum of different placements that will be evaluated: 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑙𝑜𝑜𝑝𝑠=⌈−log𝑇𝑜 log𝑝⌉ (5.3) 𝑚𝑎𝑥𝑖𝑚𝑢𝑚 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑒𝑑 𝑝𝑙𝑎𝑐𝑒𝑚𝑒𝑛𝑡𝑠=𝑠· 𝑚· ⌈−log𝑇𝑜 log𝑝⌉ (5.4) Generate random neighbours In each loop iteration what is firstly done is to generate new random neighbours named Y for S placements. In this study, a new controllers’ placement Y is considered neighbour of S if at least they share kT/2To (rounding up) controllers as it is done in [7]. However, as it is said in [7], k/2 (rounding up) elements of difference could be also considered. Thus would increase the dispersion according to [7]. Update Pareto-Frontier The following step is to evaluate these new placements, i.e., the neighbours Y, for the two metrics that are compared in this experiment and update the Pareto Frontier with the obtained results. In order to update it, old values in the Pareto Frontier and the new ones obtained from the evaluation are compared. If one of the two metrics has a lower value than other points that are actually in the Pareto Frontier, it is included as a new point. If the new value is better in both metrics than other old value in the Pareto Frontier, then this old value is removed from the Pareto Frontier. Accept neighbours as new placements or not If the new placements have better values than the old ones, they will be accepted, i.e. S will become Y. If they are worse, there is still a probability to accept Y placements. It is needed to be like that because if not, our evaluation could get stacked in a local minimum and probably the global minimum would never be reached as it is shown in 32 Chapter 6. Implementation / Results Figure 6.1 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =3 Figure 6.2 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =5 33 Chapter 6. Implementation / Results What it can be seen in figures 6.1, 6.2 and 6.3 is that when the number of controllers k is increased, the shape of the Pareto Frontier remains being the same one. E.g., in worstcase Latency versus IC average Latency for Barrow topology, two big blocks of points appear in all three cases, k=3, 5 and 7. Each network has its own shape and size, but they are either separated by two big blocks or growing in a correlated way, excepting ThorntonBank2 that has just one block of values. As it can be seen in figure 1 in Annex 1, this behavior is repeated also for other metric comparisons, not just for the three comparisons shown above. 6.1.2 Correlation between different performance metrics In this chapter another conclusion about the fifteen computed comparisons is explained; it is about correlation between metrics. All comparisons are plotted in Annex 1, figure 1, figure 2 and figure 3. As it can be seen, there are some metrics that have a correlated behaviour, i.e., they both improve in the same way. Therefore, they can be considered as ‘equals’ henceforth. In our study is considered that if a pair of metrics ends up with the same pair of values or a short Pareto-Frontier, both metrics are correlated. In figure 6.4 represented bellow, both metrics share an optimal solution or they have a thick Pareto-Frontier. Moreover, it can be said that they are correlated due to they both grow in a linear way, i.e., when one metric gets worse, the other one gets worse too. Figure 6.3 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =7 34 Chapter 6. Implementation / Results Figure 6.4 Correlated metrics Conclusions obtained from the previous figure 6.4 are: 1) There are some pairs of metrics that clearly correlate for any number of controllers k and they have a similar behaviour when compared with other metrics. The correlated metrics are worst-case latency with average latency and inter-controller worst-case latency with inter-controller average latency. I.e., latencies between nodes and controllers and also from controllers to controllers are both correlated. Furthermore, imbalance and unavailability metrics are also correlated themselves. 2) Therefore, from now on, instead of considering 6 metrics, there will be considered just the following ones: average latency between nodes and controllers, average latency between controllers and load imbalance. 3) The correlation of these metrics is equal for all number of controllers, i.e. the correlation of these metrics has no dependence with k. 4) The correlation of these metrics is similar for all industrial networks this thesis is working with, i.e. the correlation of these metrics has no dependence with the network. 35 Chapter 6. Implementation / Results 6.2. ILP In this part of the thesis, results when computing ILP are shown. In order to show how the ILP method works, the code firstly evaluates all possible controllers’ placements, i.e., an exhaustive evaluation, using three controllers and for all metrics; Average Latency, Inter Controller Latency and Imbalance. Then, ILP optimal placements are computed using Gurobi as a MILP solver and the explained expressions provided in chapter 4. All the code has been written in Python. In the following figure, 6.5, just one example of two metrics, Average Latency and Inter-controller Average Latency, and for one network, ThorntornBank1, is shown. Blue points represent each pair of the metrics’ values. The red line represents the ParetoFrontier of the exhaustive evaluation and cyan dots represent the edges of this ParetoFrontier. The red dot represents the ILP optimal placement when optimizing Average Latency and the yellow dot represents the ILP optimal placement when optimizing Inter-Controller Average Latency. As it is seen in figure 6.5, there are several optimal placements for each metric; all dots included in the lowest row for Inter-Controller Average Latency and all dots included in the leftmost column for Average Latency. However, there is just one dot included in the Pareto Frontier. It actually corresponds to one of the edges of the Pareto Frontier. As there are several optimal placements for each metric, i.e., several controllers’ placements that can optimize a metric, when ILP returns an optimal placement it does not have to be necessarily included in the Pareto-Frontier. As it is seen in figure 6.5, there is a certain distance between the yellow and cyan dots. It does not mean that the result is not correct; it just means that it will not always return the placement in the Pareto-Frontier edge. Later, when the metaheuristic algorithm PSA is studied jointly with ILP, this result can give unexpected problems. Figure 6.5 ILP method applied for Average Latency and IC Average Latency 36 Chapter 6. Implementation / Results 6.3. PSA As it can be seen in table 6.3 in chapter 6.1, elapsed times by exhaustive evaluations are too large and unfeasible for real networks since they need fast reaction times. In chapter 6.3.1, some PSA parameters will be tuned in order to see which one is better to be increased to reduce accuracy of the PSA Pareto Frontier with the real Pareto Frontier. In chapter 6.3.2 a new algorithm that combines PSA algorithm and ILP problem is studied in order to see if it is better or worse than the common PSA used in [7]. 6.3.1 Tuning PSA parameters In this chapter the accuracy of the PSA algorithm when modifying its parameters is studied. The goal is to see which of its values is worthier to increase. As it is explained in chapter 5.4, m, s, To and p are the parameters that can be modified. When any of them is increased, the number of evaluated placements in the PSA algorithm also increases. In this case, the study begins with the following parameters: m=2, s=2, To=50 and p=0.9. I.e., the study starts computing a total of 152 placements every time the PSA algorithm is executed. The idea is to increase each parameter, compute the PSA algorithm 100 times and compute the accuracy explained in chapter 5.4 for all the 100 experiments. Then, an average accuracy is obtained. In order to compute this accuracy, an exhaustive evaluation per each network and for the three metrics used – Average Latency, InterController Average Latency and Imbalance - must be done. Firstly, the number of evaluated placements has been computed when m is increased from 2 until 8, keeping other parameters with the same starting values, i.e., s=2, To=50 and p=0.9. Using (5.4) expression in chapter 5.3, the following values: [152, 228, 304, 380, 456, 532, 608] have been obtained, this array is named numEvPl and its values represent the maximum number of placements that will be evaluated in a PSA computation. The next step is to adapt other variables to these values. In order to do so, other variables must keep the initial value. I.e., just one parameter is modified in each case to reach the same number of evaluated placements. Parameter s has to increase in the same way that parameter m increases due to it has the same function in expression (5.4), i.e., s and m values are: [2,3,4,5,6,7,8]. In order to compute To and p, they have been isolated from (5.4) obtaining: 𝑇𝑜(𝑖)=10^(−𝑛𝑢𝑚𝐸𝑣𝑃𝑙(𝑖) 𝑚· 𝑠 ·𝑙𝑜𝑔10(𝑝))=10^(−𝑛𝑢𝑚𝐸𝑣𝑃𝑙(𝑖) 2·2 ·𝑙𝑜𝑔10(𝑝0.9)) (6.1) 𝑝(𝑖)=10^(− 𝑙𝑜𝑔10(𝑇𝑜) 𝑛𝑢𝑚𝐸𝑣𝑃𝑙(𝑖) 𝑚·𝑠 )= 10^(− 𝑙𝑜𝑔10(50) 𝑛𝑢𝑚𝐸𝑣𝑃𝑙(𝑖) 2·2 ) (6.2) 37 Chapter 6. Implementation / Results After computing (6.1) and (6.2), it is concluded that values for To and p will be: To Evaluated placements 50 152 406 228 3003 304 22231 380 164571 456 1218278 532 9018588 608 Table 6.4 To values when m=2, s=2 and p=0.9 The expected behavior is that the more evaluated placements are computed, the better accuracy will be obtained. The intention of this study is to see which parameter reduces more the accuracy between the exhaustive PF and the PSA PF when this parameter is increased. Firstly, the accuracy for Barrow Network has been computed comparing these three metrics: Average Latency, Inter-controller Average Latency and Load Imbalance. The following represented figures, 6.6, 6.7 and 6.8 are split in four different graphs. Each graph shows the obtained accuracy when increasing a specific parameter; either m, s, To or p, keeping other parameters with their initial value, i.e., m=2, s=2, To=50 and p=0.9. p Evaluated placements 0.9 152 0.9336 228 0.9498 304 0.9596 380 0.9662 456 0.9710 532 0.9745 608 Table 6.5 p Values when m=2, s=2 and To= 50 Figure 6.6 Accuracy for Barrow Network Av Lat vs IC Av Lat 38 Chapter 6. Implementation / Results As it can be seen in figures 6.6, 6.7 and 6.8, the obtained results are similar to the expected ones. When increasing the number of loops in the PSA algorithm, i.e., the number of maximum evaluated placements, accuracy takes a lower value, in other words, it improves. Each PSA has been repeated 100 times in order to obtain a more precise result. Relationship between the PSA parameters and PSA accuracy The next objective for this study is to see which metric has improved more when increasing the number of iterations in the PSA algorithm. In order to do so, the difference between the first value obtained and the last one has been computed per each parameter, e.g., the difference of accuracy when using m=2 and m= 8. The obtained result is named improvement. Each pair of compared metrics and each parameter has its own improvement. All improvements for each network and for each pair of compared metrics can be seen in figure 6.9. Figure 6.8 Accuracy for Barrow Network IC Av Lat vs Imb Figure 6.7 Accuracy for Barrow Network Av Lat vs Imb 39 Chapter 6. Implementation / Results Figure 6.8. Improvement of each parameter in all cases 40 Chapter 6. Implementation / Results In figure 6.9, blue bars represent the improvement of each metric, i.e., the difference between the first and the last evaluation. Taking into account that the first case for each couple of metrics has similar results due to it uses the same parameters; the study wants to prove which one got a lower value when increasing the number of evaluated placements. I.e., the higher blue bar, the more it has improved. In the following figure 6.10, the average improvement for each PSA parameter and each pair of metrics has been computed. It can be seen that m parameter has the greatest value in all three metric comparisons. Then, an important conclusion has been reached. The parameter that reduces more quickly the accuracy for all metric comparisons when increasing the number of iterations, and jointly the elapsed time, is m parameter. I.e., it reduces the accuracy between the exhaustive Pareto Frontier and the PSA Pareto Frontier faster than other parameters when considering the same number of PSA iterations, and therefore, the same elapsed time. Hence, the conclusion is that if accuracy is wanted to be reduced, the parameter that must be increased is m. Values shown above in figure 6.10 were computed with k = 4, it has also been computed with k=3 and the obtained values are the same ones. Figure 6.9 Average improvement between the first and last accuracy obtained for each parameter for k=4 Figure 6.10 Average improvement for each parameter for k=3 41 Chapter 6. Implementation / Results 6.3.2 PSA Random vs PSA ILP In this study two different ways to compute the PSA algorithm have been studied, the first way to do it is by computing PSA algorithm as it is described in [7], i.e., starting from s random placements. The second way to compute it is starting from ILP best placement solutions. These two algorithms are named as case 1 and case 2, respectively. In order to compare these two procedures, the accuracy between the original Pareto Frontier, i.e., the one obtained from an exhaustive evaluation, and the Pareto Frontier obtained from either case 1 or case 2. The chosen parameters for this evaluation are the following ones: s has to be equal to 2 because case 2 can just start from two different placements, so it has to be the same for case 1. In order to see how the other parameters affect results, they have also been modified and the experiment has been repeated with the new ones. The first set of values used is m=2, To =50, p=0.9 and k =3. In order to see if results had coherence, the whole calculous has been repeated three times. The obtained results in these three times are similar, but not equals. In this document the three of them are shown. In each case, the PSA evaluation has been computed 50 times in order to obtain a more exact accuracy value, computing the average of accuracy from the 50 obtained values. In the following figure 6.12 an example of how the fifty computed Pareto-Frontiers are distributed in Barrow topology when using Average Latency and IC Average Latency metrics is shown. As it can be seen here and in more figures shown below, the accuracy in case 2 is better than in case 1 due to its Pareto Frontiers are closer to the one computed by an exhaustive evaluation, shown in red. Green lines represent the obtained Pareto Frontiers using the PSA algorithm. Figure 6.11 Pareto Frontiers when using method 1 and method 2 In figure 6.13 the average accuracy in case 1 and in case 2 is shown. If the accuracy in case 2 is better, i.e., it has a lower value than accuracy in case 1, a green line that represents an improvement has been printed. On the other hand, if it is worse, a red line 48 Chapter 6. Implementation / Results case 2 case 1 m Evaluated placements accuracy time (sec) accuracy time (sec) 2 152 0,66156 0,05872 3 228 0,53831 1,57372 0,66692 0,10031 4 304 0,65698 0,14125 5 380 0,62049 0,18374 6 456 0,58844 0,22557 7 532 0,52954 0,26804 Table 6.7 Accuracy and time when changing m. IC av Lat vs Imb Then, the obtained conclusion is that our suggested method is not better than the common PSA algorithm. I.e., PSA algorithm starting from a random point is faster than PSA algorithm starting from ILP optimal placements. Furthermore, it is also demonstrated that the higher number of evaluated placements that are computed in PSA algorithm, the better accuracy is obtained, but also, the more time is required. As it is talked about in Chapter 6.2 ILP implementation, this method returns one of the possible optimal solutions for one metric and there can be a lot, i.e., it does not always return the optimal value also contained in the Pareto Frontier. Our method could be much better if the ILP method returned us the optimal placement for a metric that was also located on the Pareto Frontier. Accuracy in case 2 would be much lower and case 1 would have to spend more time to reach it. However, this is not possible due to there is not a way that forces the ILP problem to return this optimal placement contained in the Pareto Frontier. 47 Chapter 7 Conclusions and Outlook This project wanted to study the behaviour of some Industrial Networks when they were used as SDN Networks. It was wanted to see how they reacted to some different metrics when using different number of controllers. Moreover, the thesis wanted to study these networks for the CPP problem, trying to solve where and how many controllers had to be deployed. In order to solve it, a code capable to compute six different metrics and compute and show de 2D Pareto Frontier between them was developed. There were 15 possible combinations of those metrics per each topology. But then, this study realised that some metrics were correlated and, therefore, they could be treated as equals. That is why this project continued studying the Industrial Networks just comparing three different Pareto Frontiers instead of fifteen. This thesis also focused its work on a metaheuristic algorithm called PSA due to exhaustive evaluations are not realistic to solve the CPP problem because their evaluation time is too large and this networks need a fast reaction time. This algorithm was studied varying some of its parameters and using some Industrial Networks. The objective was to know which PSA parameter was better to increase in order to obtain a better accuracy. By repeating more times the PSA loop, accuracy is improved, i.e., it gets a lower value. The number of loops can be increased by increasing m, s, To or p PSA parameters. The conclusion obtained here is that PSA algorithm improves faster when increasing m parameter. Finally, this project wanted to improve the PSA algorithm with a new one, adding ILP problem to it. Instead of starting from a random value, this new algorithm was started from an optimal allocation for a metric, obtained by solving an ILP problem for each evaluated metric with Gurobi. Unfortunately, results were not good. This method computed a better accuracy when using the same number of iterations in the PSA algorithm, but, however, it spent more time to reach this accuracy than the common PSA algorithm. Therefore, even if the PSA algorithm that started from random placement needed to evaluate more placements, it was faster due to ILP computations were too slow. This project could be improved by taking into account more industrial networks and also by comparing the obtained results with Zoo topologies. Also larger k number could be tested, maybe with higher number of controllers results would change. Moreover, more metrics could be also considered, including the ones that take into account failures. Another situation that could be studied is the load imbalance metric. In this thesis a homogeneous load is considered, i.e., each node has the same load but, in real scenarios some switches may have a higher demand than others. As it is said in chapter 6.3, it would be useful to find a similar method to ILP that provided the two edges in the Pareto Frontier. This could decrease the accuracy for the proposed method in 6.3.2. It could be also tried, as it is said in [7], to change the way of how neighbours are assigned to the placements in the PSA algorithm. Finally, it could be also tried to modify α PSA parameter which it is used to assign and modify weights. Chapter 8. Formatting. 50 Chapter 8 Formatting 8.1. List of figures Figure 2.1 Traditional Switch vs SDN Switch [12] ....................................................... 9 Figure 2.2 Example of SDN architecture [13]. ............................................................ 10 Figure 2.3 Barrow and AlphaVentus are considered as Tree Topologies [10] ............ 11 Figure 2.4 Ormonde is a Ring Topology [10] .............................................................. 11 Figure 2.5 ThornonBank2 is considered as a Tree + Ring topology [10].................... 11 Figure 2.6 AlphaVentus2 is the classical grid topology [10] ....................................... 11 Figure 2.7 ThorntonBank1 and Riffgat are Meshed topologies [10] ........................... 12 Figure 2.8 Cost266 topology ........................................................................................ 12 Figure 3.1 Latencies reduction when k is increased. Fig 4 in [1]. ............................... 15 Figure 3.2 Latencies versus number of controllers. Figure 6 in [1]. ............................ 16 Figure 5.1 Relative budget for different Size of Search Space in order to achieve an accuracy level. Figure 5 in [7]. .............................................................................. 23 Figure 5.2 Accepting worse values to reach the global minimum ............................... 26 Figure 5.3 Representation of the PSA algorithm ......................................................... 27 Figure 6.1 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =3 ........................................................................................................................... 32 Figure 6.2 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =5 ........................................................................................................................... 32 Figure 6.3 WC Lat vs Av Lat, WC Lat vs IC WC Lat and WC Lat vs IC Av Lat for k =7 ........................................................................................................................... 33 Chapter 8. Formatting. 51 Figure 6.4 Correlated metrics ...................................................................................... 34 Figure 6.5 ILP method applied for Average Latency and IC Average Latency .......... 35 Figure 6.6 Accuracy for Barrow Network Av Lat vs IC Av Lat ................................. 37 Figure 6.8 Accuracy for Barrow Network Av Lat vs Imb .......................................... 38 Figure 6.9. Improvement of each parameter in all cases ............................................. 39 Figure 6.10 Average improvement between the first and last accuracy obtained for each parameter for k=4 .......................................................................................... 40 Figure 6.11 Average improvement for each parameter for k=3 .................................. 40 Figure 6.12 Pareto Frontiers when using method 1 and method 2 .............................. 41 Figure 6.13 Accuracy in Case 1 vs Accuracy in Case 2. First computation. ............... 42 Figure 6.14 Accuracy in Case 1 vs Accuracy in Case 2. Second computation. .......... 43 Figure 6.15 Accuracy in Case 1 vs Accuracy in Case 2. Third computation. ............. 44 Figure 6.16 Accuracy in Case 1 vs Accuracy in Case 2. With m=5. ........................... 45 Figure 6.17 (Left) Accuracy for Average Latency vs IC Average Latency. (Right) Accuracy for Average Latency vs Imbalance ....................................................... 46 Figure 6.18Accuracy for IC Average Latency vs Imbalance ...................................... 46 Figure 1.1 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=3 (1) .................................................................................................................. 55 Figure 1.2 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=3 (2) .................................................................................................................. 56 Figure 1.3 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=4 (1) .................................................................................................................. 56 Figure 1.4 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=4 (2) .................................................................................................................. 56 Chapter 8. Formatting. 52 8.2. List of Tables Table 2.1 Example of requirements in an industrial network ...................................... 10 Table 5.1 PSA Algorithm ............................................................................................ 24 Table 6.1 Number of evaluated placements per network and per k ............................. 29 Table 6.2 Total amount of evaluated placements per k ............................................... 29 Table 6.3 Elapsed time for different number of controllers ......................................... 31 Table 6.5 To values when m=2, s=2 and p=0.9 ........................................................... 37 Table 6.6 p Values when m=2, s=2 and To= 50 .......................................................... 37 Table 6.7 Accuracy and time when changing m. Av Lat vs IC av Lat. ....................... 47 Table 6.8 Accuracy and time when changing m. IC av Lat vs Imb ............................. 48 Chapter 8. Conclusions and Outlook 47 8.3. Notation and Abreviations This chapter contains tables where all abbreviations and other notations like mathematical placeholders used in the thesis are listed. Av lat Average Latency Avail Availability CPP Controller Placement Problem E Set of links G Network graph Ic av lat Inter-controller average latency Ic wc lat Inter-controller worst-case latency ILP Integer Linear Programming Imb Load imbalance k Number of controllers MILP Mixed-Integer Linear Programming n Number of nodes PF Pareto Frontier POCO Pareto-Optimal Controller Placement PSA Pareto Simulated Annealing SDN Software Defined Networking SoA State of the Art V Set of nodes Wc lat Worst-case latency Chapter 8. Formatting 54 8.4. References  [1] [Hel12] Heller, B., Sherwood, R., & McKeown, N. (2012). The controller placement problem. ACM SIGCOMM Computer Communication Review, 42(4), 473.  [2] [Hock13] Hock, D. (2013). Pareto-optimal resilient controller placement in SDN-based core networks, 1–9.  [3] [Hu13] Hu, Y., Wendong, W., &Gong, X. (2013). Reliability-aware controller placement for Software-Defined Networks. Integrated Network, 672-675.  [4] [HuRel14] Yannan, H.U., Wendong, W., Xiangyang, G., Xirong, Q. U. E., & Shiduan, C. (2014). On Reliability-optimized Controller Placement for Software-Defined Networks, (February), 38-54.  [5] [Lange] Lange, S., Gebert, S., Spoerhase, J., Rygielski, P., Zinner, T., & Kouvnev, S. (n.d.). Specialized Heuristics for the Controller Placement Problem in Large Scale SDN Networks.  [6] Five Nines of Southbound Reliability in Software-Defined Networks.  [7] [Lan15] Heuristic Approaches to the Controller Placement Problem in Large Scale SDN Networks  [8] D. Hock, M. Hartmann, S. Gebert, T. Zinner, and P. Tram-Gia, „POCOPLC: Enabling dynamic pareto-optimal resilient controller placement in SDN networks, “ in Proc. INFOCOM, Toronto, ON, Canada, 2014, pp 115-116.  [9] [Zhang11] Zhang, Y., Beheshti, N., & Tatipamula, M. (2011). On resilience of split-architecture networks. GLOBECOM – IEEE Global Telecommunications Conference.  [10] VirtuWind  [11] ZooTopology  [12] http://bradhedlund.com/2011/04/21/data-center-scale-openflow-sdn/  [13] http://www.cisco.com/c/en/us/about/press/internet-protocol-journal/backissues/table-contents-59/161-sdn.html  [14] IEEE Standard 1646-2004, “Communication Delivery Time Performance Requirements for Electric Power Substation Automotion”.  [15] M. Goraj, Y. Epassa, R. Midence und D. Meadows, “ Designing and deploying Ethernet networks for offshore wind power applications – a case study,” 10th IET International Conference on Developments in Power System Protection, pp. 15, 2010  [16] Hock, D., Gebert, S., Hartmann, M., Zinner, T., & Tran-Gia, P. (2014). POCO-framework for Pareto-optimal resilient controller placement in SDNbased core networks. IEEE/IFIP NOMS 2014 – IEEE/IFIP Network Operations and Management Symposium: Management in a Software Defined World. 55 Appendix A In this appendix some exhaustive evaluations are plotted. In all cases the topology is shown within its 15 possible combinations of metric comparisons. The metrics used in these comparisons are listed and explained in chapter 3.3 Performance metrics. Figure 8.1 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=3 (1) 56 Figure 1.2 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=3 (2) 57 Figure 1.3 Exhaustive evaluation and Pareto Frontiers for all 6 metrics combinations K=4 (1)