RCP: A temporal clustering algorithm for real-time controller placement in software-defined networks

In this comprehensive study we introduce a family of maximum entropy based clustering algorithms to address the problem of Controller Placement (CP) or equivalently Edge Controller Placement (ECP) 1. The shared key advantage of our algorithms is utilizing a maximum entropy based framework that in terms of performance translates to avoiding poor locally optimum placements that most competitor ECP algorithms are susceptible to. Controller placement is recognized as one of the most important problems and a significant performance bottleneck in Software Defined Networks (SDN) which is a recent paradigm in telecommunication networks that disentangles data and control planes and brings flexibility and efficiency to the mobile network. SDN networks lie at the core of the fifth generation (5G) wireless systems and beyond and are increasingly being adopted into telecommunication networks over the recent years. CP can be simply stated as where to place and which network nodes to assign to each individual controller such that a desired utility or cost is optimized. The complexity of CP problem can drastically change with mobility of SDN network nodes and due to this observation we offer two classes of algorithms for static and dynamic placement cases. For static controller placement problem where network nodes and controllers are assumed to be stationary, the algorithms, referred to as ECP-LL and ECP-LB, address the dominant leader-less and leader-based controller placement topologies and have linear computational complexity in terms of network size. Each algorithm tries to place controllers close to edge node clusters and not far away from other controllers to maintain a reasonable balance between synchronization and delay costs. While the ECP problem can be conveniently expressed as a multi-objective mixed integer non-linear program (MINLP), our algorithms outperform the state of art MINLP solver, BARON both in terms of accuracy and speed. As for the mobile networks, we propose real-time controller placement algorithms RCP, and RCP+ to tackle the Dynamic Controller Placement (DCP) problem. More specifically these are temporal clustering algorithms that provide real-time solutions for DCP and provide adaptability to inherent variability in network components (traffic, locations, etc.) and is based on a control theoretic framework for which we show the solution converges to a near-optimal solution. The key contribution of these algorithms is the real-time aspect of placement of controllers which to our best of knowledge was never addressed prior to this study. Our algorithms achieve linear O(N) iteration computational complexity with respect to the number of nodes in the network, N and can update new positions of network controller in real-time, and in accordance with mobility of SDN network nodes. This property allows utilization of an aerial control plane using UAV swarms. We compare our work with a frame-by-frame approach and demonstrate its superiority, both in terms of speed and incurred cost, via simulations using some of the largest public mobility datasets with millions of records gathered over the span of months, containing GPS trajectories of thousands of pedestrians and vehicles in large metropolitan areas like San Francisco, US and Beijing, China. Based on these simulations, RCP and RCP+ can be up to 25 times faster than a conventional frame-by-frame method. RCP+ can be viewed as the culmination of the contributions of this thesis. Interestingly ECP-LL, and RCP can be formulated as restricted versions of RCP+ algorithm. RCP+ allows for node prioritization, sparse subsampling, node trajectory prediction using an underlying Recurrent Neural Network (RNN), computation parallelization, and codebook expansion, making it a viable choice even for large-scale mobility networks, which we explore in this thesis. We benchmark RCP+ against a number of alternatives, and show that for real sized networks, it outperforms the comparable state of the art methods.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Soleymanifar, Reza

Contributors dc:contributor

• Beck, Carolyn
• Salapaka, Srinivasa
• Rayadurgam, Srikant
• Stipanovic, Dusan M

• Software Defined Networks
• Uav Swarms
• Temporal Clusterin
• Neural Networks
• Controller Placement

Statement dc:rights

• Copyright 2023 Reza Soleymanifar

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121916

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121916