Date of Award

3-24-2016

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Electrical and Computer Engineering

First Advisor

Barry E. Mullins, PhD.

Abstract

One of the central tenets of a Software Defined Network (SDN) is the use of controllers, which are responsible for managing how traffic flows through switches, routers, and other data-passing devices on a computer network. Most modern SDNs use multiple controllers to divide responsibility for network switches while keeping communication latency low. A problem that has emerged since approximately 2011 is the decision of where to place these controllers to create the most 'optimum' network. This is known as the Controller Placement Problem (CPP). Such a decision is subject to multiple and sometimes con_icting goals, making the CPP a type of Multi-Objective Problem (MOP). The Controller Placement Problem is NP-Hard. This means finding the 'optimum' solution can become a time-intensive process as network size increases. Multiple algorithms exist to solve MOPs using shortcut (or 'heuristic') methods which can produce a 'near-optimal' solution in times much shorter than those necessary to guarantee an 'optimal' solution. One popular class of algorithms is known as Evolutionary Algorithms (EAs); EAs designed to solve Multi-Objective problems are called Multi-Objective Evolutionary Algorithms (MOEAs). While many MOEAs exist, their application to the Controller Placement Problem is not well explored. The theory of this thesis is that an MOEA can produce solutions to the Controller Placement Problem which are 'nearly optimal' while keeping execution time low compared to an exhaustive 'optimal' search. This research extends a network modeling tool called the Pareto Optimal Controller Placement (POCO) Framework with custom designed MOEA, called POCO-MOEA. A series of full-factorial experiments is designed and executed to gather data on POCO-MOEA performance to a series of model networks. The algorithm's behavior is then evaluated and compared to exhaustive search through five metrics; fraction of solution space size, average distance between pareto fronts (δ1), worst-case distance between pareto fronts (δ2), relative hypervolume (hyprel), and relative execution time (brel). Results show that performance is dependent on the size of the network, the topology of the network, and the parameters chosen for POCO-MOEA. In general, performance for POCO-MOEA improves as the size of the network increases. Given a large network (60+ nodes), POCO-MOEA can achieve within 0.4% of δ1, 3% of δ2, and 6% of hyprel while still being 500 times faster than exhaustive search. This research demonstrates and adds a valuable tool to the methods of determining optimal device placement for an SDN while providing steps to using MOEAs in real SDN applications.

AFIT Designator

AFIT-ENG-MS-16-M-021

DTIC Accession Number

AD1053821

Download

Share

COinS