M. Rost

It's a Match! Near-Optimal and Incremental Middlebox Deployment

T. Lukovszki, M. Rost, S. Schmid
Appears in: 
CCR January 2016

The virtualization and softwarization of modern computer networks offers new opportunities for the simplified management and flexible placement of middleboxes as e.g. firewalls and proxies. This paper initiates the study of algorithmically exploiting the flexibilities present in virtualized and software-defined networks. Particularly, we are interested in the initial as well as the incremental deployment of middleboxes. We present a deterministic O(log(min{n, κ})) approximation algorithm for n-node computer networks, where κ is the middlebox capacity.

Public Review By: 
Fabián E. Bustamante

Network functions or middleboxes can be used to manipulate packets and flows in sophisticated ways to improve security, performance and general network management. They are virtually ubiquitous in modern computer networks and increasingly more flexible as they become softwaredefined and virtualized. Through software-defined networking, operators can route traffic through arbitrary paths across chains of middleboxes to enforce policies or manage the middleboxes’ load. Before enabling such interesting functionality, however, one has to decide where to place these middleboxes in the network. The authors study precisely this, presenting a proof of hardness of the problem and an algorithm for approximating a solution. The specific problem tackled is how to place middleboxes in a n-node network so that every pair in a set of source-destination pairs has a path of length at most L with one middlebox in it. There is an additional constraint that a middlebox can be used at most k times (a capacity constraint). The problem boils down to a capacitated set cover problem which, I have been told, explains the log(min{n,k}) factor approximation of the proposed greedy approach. Reviews were generally positive, pointing out the value of good theoretical analysis of a problem so far addressed through heuristics. While from a theoretical perspective the proposed approach is obvious once the problem is framed as a capacitated set cover problem, the authors should be acknowledged for the problem formulation and framing. The authors’ model does ignore a number of practicalities including the fact that middleboxes are often deployed in a chain, that the traffic coming out of a middlebox is transformed, and that network links have capacity constraints. When considered, such practicalities may render their current solution inappropriate. Still, the authors present a valuable first step in addressing a clearly important and challenging problem. ACM SIGCOMM Computer Communication Review

Beyond the Stars: Revisiting Virtual Cluster Embeddings

C. Fuerst, M. Rost, S. Schmid
Appears in: 
CCR July 2015

It is well-known that cloud application performance can critically depend on the network. Over the last years, several systems have been developed which provide the application with the illusion of a virtual cluster : a star-shaped virtual network topology connecting virtual machines to a logical switch with absolute bandwidth guarantees. In this paper, we debunk some of the myths around the virtual cluster embedding problem.

Public Review By: 
Hitesh Ballani

Public Review for Beyond the Stars: Revisiting Virtual Cluster Embeddings Matthias Rost, Carlo Fuerst, and Stefan Schmid Motivated by reports of variable network performance in cloud data centers, a lot of recent research has focused on providing cloud users a dedicated virtual network with bandwidth guarantees. A virtual network abstraction that has gained currency is the "virtual cluster" – the user’s virtual machines can be seen as being connected to a single logical switch through logical links of guaranteed bandwidth. This paper focusses on the virtual cluster embedding problem. While optimal embedding of a virtual cluster is NP-hard, the authors show that when all virtual machines for a user have the same bandwidth guarantee, optimal embedding is possible in polynomial time (even atop arbitrary physical topologies). The authors also propose a new embedding model whereby there is no one-to-one mapping of the virtual cluster’s logical switch onto a physical switch. Such a "hose embedding" can reduce the physical resources needed to support a virtual cluster. While the hose embedding is NP-hard, the authors propose a polynomial time algorithm for a variant of this embedding problem which still reduces a cluster’s resource footprint. The reviewers appreciated that while past algorithms for virtual cluster embedding focus on fast embedding at the expense of optimality, the paper shows that optimal embedding for a common class of virtual clusters is tractable. This is a neat result. Beyond contributing new algorithms, the paper will also serve to remind readers of some existing results from theoretical computer science. The key practical challenge is computational scalability; even for a physical topology with a few hundred nodes, the hose embedding algorithm takes a few minutes to run. Engineering the algorithm to run fast at data center scale is challenging yet imperative, and the authors briefly discuss how this could be achieved. ACM SIGCOMM Computer Communication Review Public review written by

Syndicate content