It's a Match!: Near-Optimal and Incremental Middlebox Deployment
It's a Match!: Near-Optimal and Incremental Middlebox Deployment
复制标题
DOI：
10.1145/2875951.2875956
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Tamás Lukovszki;Matthias Rost;S. Schmid
中科院分区：
文献类型：
--
作者：
Tamás Lukovszki;Matthias Rost;S. Schmid
现代计算机网络的虚拟化和软质量为简化的管理和敏感放置提供了新的机会，例如重新墙和代理。本文启动了对虚拟化和软件定义网络中存在的算法利用算法的研究。特别是，我们对中间箱的初始和增量部署感兴趣。我们提供了一个确定性的O（log（min {n，k}））n节点计算机网络的近似算法，其中k是中间箱的容量。该算法基于对子模块函数的优化，该函数可以使用快速增强路径方法有效地计算。派生的近似结合是最佳的：除非p = np持有，否则基本问题在sublogarithmic因子中很难近似。我们还提出了基于整数编程的精确算法，并通过模拟来补充我们的正式分析。特别是，我们考虑使用的中间箱的数量，并在增量部署中突出显示了近似算法的好处。我们的方法还找到了有趣的应用程序，例如，在软件定义网络的增量部署的背景下。
The virtualization and softwarization of modern computer networks offers new opportunities for the simplified management and exible placement of middleboxes as e.g. rewalls and proxies. This paper initiates the study of algorithmically exploiting the exibilities 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,k})) approximation algorithm for n-node computer networks, where k 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.