Networks Resource Allocation Combinatorial Optimization Mathematical Programming Design and Analysis of Algorithms
(Mixed-)Integer and Linear Programming Approximation Algorithms Computational Complexity Structural Graph Theory Verification: Theorem Provers and Modelchecking
The Virtual Network Embedding Problem (2015-2019)
The Virtual Network Embedding Problem (VNEP) captures the essence of resource allocation problems in virtualized networks: users specify their computation and communication demands via virtual networks, which are then embedded on the physical network (ISP or data center networks).
While the VNEP has been extensively studied for more than 15 years and several hundred papers have been published on the challenges associated to it, only few theoretic results were obtained . Together with Stefan Schmid, I derived the first parametrized approximation algorithms for the VNEP together with a comprehensive list of NP-hardness and inapproximability results. Besides the theoretic results, my team of student workers and I implemented all algorithms and evaluated them in a large scale evaluation.
Figure: Exemplary embedding of a virtual network together with the demands of the virtual network and the used/available capacity of the physical network.
Today's networks contain specific (potentially virtualized) hardware appliances called middleboxes to perform network functions, as, e.g., firewalls, network-address translators, etc. Whenever a flow is to be routed through such an appliance, a specific middlebox together with routes to and from it have to be chosen.
Together with Tamás Lukvoszki and Stefan Schmid, I developed approximations to place middleboxes to connect the maximum number of flows. Based on a greedy scheme, the approximation can be used to incrementally place middleboxes, while not losing the theoretic performance guarantee.
Figure: Results of various experiments with respect to the achieved approximation guarantee and the runtime of the greedy approximations compared to the exact Integer Program.
As part of my teaching duties, I had to schedule and assign several dozens of tutors to various different tasks and rooms for a 2-week block course for 600-1000 students. With around 25-40 tutors, around 600 hours of planned activities and even more booked rooms, I decided to develop an optimization framework to conquer the complexity. Among the considered constraints and objectives are the following:
minimal deviation from teaching plan optimized working hours according to preferences fairness of work assignments minimal number of room switches for tutors optimized usage of tutorial room capacities minimized number of assignment changes when re-planning
The tutor-planner was overall very successful and the tutors were especially satisfied, given that their preferences were met to an high degree (see plot on the left below).
Figure: Plan for a single day indicating tutorials and pc pool sessions.
Figure: Optimized relative working hours and happiness of tutors.
Virtualized networks allow to easily exert control of forwarding paths on the data plane. However, updating end-to-end routes in such Software-Defined Networks have to be scheduled correctly to not bypass critical middleboxes and to not introduce transient loops.
Headed by Stefan Schmid and Arne Ludwig, theoretical hardness proofs for this novel network update problem were obtained, while I was mainly responsible for developing exact algorithms for scheduling updates or deciding that updates are not possible without further overheard. Using large-scale evaluations, we showed that updates can often be performed without overhead while respecting both loop-freedom and middlebox traversal.
Figure: Visualization of the construction used to prove the NP-hardness of the Network Update Problem.
The Internet spans the entire world and most of the ISPs connect at Internet Exchange Points (IXPs). To facilitate novel applications as, e.g., tele-surgery, end-to-end paths supporting Quality-of-Service (QoS) guarantees need to be constructed between end points. To this end, a team around Vasileios Kotronis proposed the idea of Control Exchange Points (CXPs) to stitch paths of individual ISPs at IXPs while ensuring that the sub-paths of each ISP agree with the QoS-specification.
Within this project, I developed new heuristics and used linear programming to obtain baseline solutions. Our results indicated that using our efficient heuristics near-optimal solutions can be obtained, rendering the CXP approach practically feasible.
Figure: Overview of CXP approach: end-to-end paths are stitched at IXPs.
I was part of the EU FP7 Integrated Project UNIFY, which aimed at developing ways to innovate the core of ISP networks by virtualizing it:
Today, rigid network control limits the flexibility of service creation. We pursue full network and service virtualization to enable rich and flexible services and operational efficiency. The UNIFY consortium researches, develops and evaluates means to orchestrate, verify and observe end-to-end service delivery from home and enterprise networks through aggregation and core networks to data centres.
Figure: Overview of provisioning process for service chains.
Within the project, I contributed original theoretic research and worked on the architecture and the design of the central orchestration framework , which decides how to embed virtualized service chains inside the ISP networks.
In-network processing allows for the resource efficient deployment of communication tasks as e.g. multicast. Due to the ongoing effort to fully virtualize networks, several new optimization opportunities arose. Together with Stefan Schmid, I have initiated the study of where to place processing functionality and how to route data in a joint fashion, such that bandwidth can be traded off with node resources. We have coined this problem the Constrained Virtual Steiner Arborescence Problem (CVSAP) and devised a novel single-commodity flow integer formulation for CVSAP that can be solved efficiently using branch-and-cut. While even realistically sized instances can be solved near optimally within one hour, the formulation also enables a range of polynomial-time heuristics which find high-quality solutions with high efficacy in minutes.
Figure: isualization of an optimal world-wide aggregation tree.
Temporal Virtual Network Embedding Problem (2012-2014)
The Temporal Virtual Network Embedding Problem (TVNEP) extends the classical Virtual Network Embedding Problem (VNEP) by introducing a temporal dimension: for each virtual network request a duration and a time interval is given in which it must be embedded.
The TVNEP asks for finding suitable resources to embed the requests together with a feasible schedule, i.e. to find start and end times of the requests such that resource allocations are feasible at any point in time.
Figure: Visualization of our continuous-time event point model.
We have developed multiple Mixed Integer Programming formulations to obtain (near-)optimal solutions to this problem. For facilitating such exact methods, we have developed different state-space as well as symmetry reductions.
ACM International Workshop on Edge Systems, Analytics and Networking (EdgeSys@EuroSys), 2020
Fast and Efficient Network Service Embedding Method with Adaptive Offloading to the Edge
Balázs Németh, Márk Szalay, János Dóka, Matthias Rost, Stefan Schmid, Laszlo Toka, Balázs Sonkoly
The 2nd Workshop on Integrating Edge Computing, Caching, and Offloading in Next Generation Networks (IECCO), INFOCOM 2018, Honolulu, HI, USA, April 2018.
Efficient service graph embedding: A practical approach
Balázs Németh, Balázs Sonkoly, Matthias Rost and Stefan Schmid.
Second IEEE Workshop on
Orchestration for Software Defined Infrastructures (O4SDI), NFV-SDN 2016, Palo Alto, CA, USA, November 2016.
Unifying the Programmability of Cloud and Carrier Infrastructure
Pontus Skoldstrom, Balazs Sonkoly, Mario Kind, Fritz-Joachim Westphal, Wolfgang John, Jokin Garay, Eduardo Jacob, Janos Elek, David Jocha, Robert Szabo, Wouter Tavernier, George Agapiou, Antonio Manzalini, Matthias Rost, Nadi Sarrar, and Stefan Schmid.
European Workshop on Software Defined Networking (EWSDN), Budapest, Hungary, September 2014
Technical Reports
Optimal Virtual Network Embeddings for Tree Topologies
Aleksander Figiel, Leon Kellerhals, Rolf Niedermeier, Matthias Rost, Stefan Schmid, Philipp Zschoche
