S. Schmid

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

By: 
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

In-Band Synchronization for Distributed SDN Control Planes

By: 
L. Schiff, S. Schmid, P. Kuznetsov
Appears in: 
CCR January 2016

Control planes of forthcoming Software-Defined Networks (SDNs) will be distributed : to ensure availability and faulttolerance, to improve load-balancing, and to reduce overheads, modules of the control plane should be physically distributed. However, in order to guarantee consistency of network operation, actions performed on the data plane by different controllers may need to be synchronized, which is a nontrivial task. In this paper, we propose a synchronization framework for control planes based on atomic transactions, implemented in-band, on the data-plane switches.

Public Review By: 
Katerina Argyraki

Software Defined Networking (SDN) advocates a logically centralized control plane, however, for scalability and fault-tolerance reasons, this must be implemented on top of multiple, physically separate controllers; how should these controllers synchronize with each other to avoid leaving the network in an undesirable state? The conceptually straightforward approach would be to have the controllers directly exchange synchronization messages; this paper explores a jazzier alternative: the controllers use part of the data-plane configuration space as transactional shared memory (in particular, to implement an atomic compare-and-swap operation). The paper shows that this approach can be implemented on top of OpenFlow (by leveraging the OpenFlow bundling feature). It also outlines how an example control-plane application — one that configures load-balancing — would benefit from the resulting transactional semantics. The reviewers appreciated the originality of the proposal. They did wish for clearer arguments on why this is the right way to do controller synchronization, as well as a quantitative analysis of the amount of required data-plane resources — but these are forgivable flaws in a paper that addresses a hard and relevant problem in a fresh, I-wish-I-had-thought-of-it way.

Beyond the Stars: Revisiting Virtual Cluster Embeddings

By: 
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

Distributed Cloud Computing: Applications, Status Quo, and Challenges

By: 
Y. Coady, O. Hohlfeld, J. Kempf, R. McGeer, S. Schmid
Appears in: 
CCR April 2015

A distributed cloud connecting multiple, geographically distributed and smaller datacenters, can be an attractive alternative to today’s massive, centralized datacenters. A distributed cloud can reduce communication overheads, costs, and latencies by offering nearby computation and storage resources. Better data locality can also improve privacy. In this paper, we revisit the vision of distributed cloud computing, and identify different use cases as well as research challenges.

Syndicate content