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. The algorithm is based on optimizing over a submodular function which can be computed efficiently using a fast augmenting path approach. The derived approximation bound is optimal: the underlying problem is computationally hard to approximate within sublogarithmic factors, unless P = NP holds. We additionally present an exact algorithm based on integer programming, and complement our formal analysis with simulations. In particular, we consider the number of used middleboxes and highlight the benefits of the approximation algorithm in incremental deployments. Our approach also finds interesting applications, e.g., in the context of incremental deployment of software-defined networks.

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