Zaid Allybokus defended his thesis on Tuesday 11th June.
It took place in Amphitheater Morgenstern (building Kahn of Inria’s center in Sophia Antipolis) at 15:00.
The title: Real-Time Scalable Algorithms for Alpha-Fair Resource Allocation in Software Defined Networks
Abstract:
In this dissertation, we deal with the design of algorithms to tackle the α-fair
resource allocation problem in real-time and distributed SoftwareDefined
Networks (SDN). First, we define three major requirements that picture the
challenges of real-time algorithms implementable in modern distributed SDN
controllers. Those challenges are the ability to provide feasible resource
allocations at all times, good transient solutions in terms of optimality gap
that converge in an acceptable number of inter-controller communication rounds,
and their ability of being massively parallelized independently of the network
architecture. We use the Alternating Directions Method of Multipliers to design
an algorithm that simultaneously, and unprecedentedly, tackles the three
challenges. Motivated by a first study of the structural properties of the
α-fair model, where we derive a lower bound on the optimal solution, we tune
the penalty parameter of the augmented Lagrangian of the problem in order to
optimize the algorithm’s performance. We show that the algorithm can function
in real-time when the traffic requirements can vary more or less abruptly. The
variation of the traffic requirements are modeled by real-time varying
coefficients of the optimization model that is solved on-the-fly and may
represent various prioritization policies of the traffic (payment, traffic
type, number of connections within a tunnel, etc). Then, we describe how to
extend the algorithm to real world use cases with limited modifications to cope
with multi-path load balancing and online adjustments. Furthermore, we address
the problem of α-fairness when the environment is uncertain and the available
amount of resources over the network links is known only through general
density functions. The main focus there is, instead of feasibility, the notion
of safety. We design a heuristic that polishes an outer relaxation of the
problem, based on the sensitivity analysis of the static problem. In general,
we are able to provide a safe and acceptably efficient solution by solving
several static problems.
Keywords: Software-Defined Networks, Resource Allocation, AlphaFairness, Real-Time, Distributed Algorithms, ADMM, Convex Optimization.
