Tamás Lukovszki
Stefan Schmid
Abstract
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.
- A. Gember-Jacobson et al. OpenNF: Enabling innovation in network function control. In Proc. ACM SIGCOMM, 2014. Google Scholar
Digital Library
- M. Bagaa, T. Taleb, and A. Ksentini. Service-aware network function placement for efficient traffic handling in carrier cloud. In Proc. IEEE WCNC, 2014.Google ScholarCross Ref
- J. Chuzhoy and J. Naor. Covering problems with hard capacities. SIAM J. Comput., 2006. Google ScholarDigital Library
- V. Chvatal. A greedy heuristic for the set-covering problem. Math. of Operations Research, 4(3), 1979. Google ScholarDigital Library
- D. Levin et al. Panopticon: Reaping the benefits of incremental sdn deployment in enterprise network. In Proc. USENIX ATC, 2014. Google ScholarDigital Library
- N. Feamster, J. Rexford, and E. Zegura. The road to sdn. Queue, 11(12):20:20--20:40, Dec. 2013. Google ScholarDigital Library
- U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998. Google ScholarDigital Library
- J. Sherry et al. Making middleboxes someone else's problem: Network processing as a cloud service. In Proc. ACM SIGCOMM, 2012. Google ScholarDigital Library
- R. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations. 1972.Google Scholar
- S. Knight, H. Nguyen, N. Falkner, R. Bowden, and M. Roughan. The internet topology zoo. Selected Areas in Communications, IEEE Journal on, 29(9):1765--1775, October 2011.Google Scholar
- L. Lovász. Submodular functions and convexity. Mathematical Programming The State of the Art, 1983.Google ScholarCross Ref
- C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960--981, 1994. Google ScholarDigital Library
- T. Lukovszki and S. Schmid Online admission control and embedding of service chains. In Proc. SIROCCO, 2015.Google ScholarDigital Library
- M. Markovitch and S. Schmid. Shear: A highly available and flexible network architecture: Marrying distributed and logically centralized control planes. In Proc. 23rd IEEE ICNP, 2015.Google ScholarCross Ref
- W. Rankothge, J. Ma, F. Le, A. Russo, and J. Lobo. Towards making network function virtualization a cloud computing service. In IFIP/IEEE IM, 2015.Google ScholarCross Ref
- S. Raza, G. Huang, C.-N. Chuah, S. Seetharaman, and J. P. Singh. Measurouting: A framework for routing assisted traffic monitoring. IEEE/ACM Trans. Netw., 20(1):45--56, Feb. 2012. Google ScholarDigital Library
- T. Ritter. Network-based firewall services: Extending the firewall into the cloud. In Nemertes White Paper N0496, 2009.Google Scholar
- S. Fayazbakhsh et al. Flowtags: Enforcing network-wide policies in the presence of dynamic middlebox actions. In Proc. ACM HotSDN, 2013. Google ScholarDigital Library
- R. Raz and S. Safra. A sub-constant error-probability low-degree test, and sub-constant error-probability pcp characterization of np. In Proc. ACM STOC, 1997. Google ScholarDigital Library
- A. Schrijver. Combinatorial Optimization -- Polyhedra and Efficiency. Springer-Verlag, 2003.Google Scholar
- S. Vissicchio, L. Vanbever, and O. Bonaventure. Opportunities and Research Challenges of Hybrid Software Defined Networks. ACM CCR, 2014. Google ScholarDigital Library
- L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385--393, 1982.Google ScholarCross Ref
- Z. Qazi et al. Simple-fying middlebox policy enforcement using sdn. In Proc. ACM SIGCOMM, 2013. Google ScholarDigital Library
Index Terms
- It's a Match!: Near-Optimal and Incremental Middlebox Deployment
Recommendations
Virtual Network Isolation: Are We There Yet?
SecSoN '18: Proceedings of the 2018 Workshop on Security in Softwarized Networks: Prospects and ChallengesWhile multi-tenant cloud computing provides great benefits in terms of resource sharing, it introduces a new security landscape and requires strong network isolation guarantees between the tenants. Such network isolation is typically implemented using ...
A flexible and efficient container-based NFV platform for middlebox networking
SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied ComputingNetwork Function Virtualization (NFV) enables multiple network functions (NFs) to operate simultaneously on a commodity server. Internet Data Centers (IDCs) gain significant flexibility and agility through NFV's ability to dynamically deploy and ...
Integrated NFV/SDN Architectures: A Systematic Literature Review
Network Functions Virtualization (NFV) and Software-Defined Networking (SDN) are new paradigms in the move towards open software and network hardware. While NFV aims to virtualize network functions and deploy them into general purpose hardware, SDN ...
Comments