{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:09:08Z","timestamp":1776038948651,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T00:00:00Z","timestamp":1452470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2016,1,11]]},"abstract":"<jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (log(min{\n            <jats:italic>n,k<\/jats:italic>\n            })) approximation algorithm for\n            <jats:italic>n<\/jats:italic>\n            -node computer networks, where\n            <jats:italic>k<\/jats:italic>\n            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\n            <jats:italic>P<\/jats:italic>\n            =\n            <jats:italic>NP<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/2875951.2875956","type":"journal-article","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T13:18:52Z","timestamp":1452604732000},"page":"30-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["It's a Match!"],"prefix":"10.1145","volume":"46","author":[{"given":"Tam\u00e1s","family":"Lukovszki","sequence":"first","affiliation":[{"name":"E\u00f6tv\u00f6s Lorand University, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Rost","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"Aalborg University, Aalborg, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,1,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626313"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCNC.2014.6952725"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703422479"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_5_1","volume-title":"Proc. USENIX ATC","author":"Levin D.","year":"2014","unstructured":"D. Levin : Reaping the benefits of incremental sdn deployment in enterprise network . In Proc. USENIX ATC , 2014 . D. Levin et al. Panopticon: Reaping the benefits of incremental sdn deployment in enterprise network. In Proc. USENIX ATC, 2014."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559899.2560327"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342359"},{"key":"e_1_2_1_9_1","volume-title":"Complexity of Computer Computations.","author":"Karp R.","year":"1972","unstructured":"R. Karp . Reducibility among combinatorial problems . In Complexity of Computer Computations. 1972 . R. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations. 1972."},{"issue":"9","key":"e_1_2_1_10_1","first-page":"1765","article-title":"The internet topology zoo. Selected Areas in Communications","volume":"29","author":"Knight S.","year":"2011","unstructured":"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 . 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.","journal-title":"IEEE Journal on"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2015.47"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INM.2015.7140280"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2159991"},{"key":"e_1_2_1_17_1","first-page":"N0496","article-title":"Network-based firewall services: Extending the firewall into the cloud","author":"Ritter T.","year":"2009","unstructured":"T. Ritter . Network-based firewall services: Extending the firewall into the cloud . In Nemertes White Paper N0496 , 2009 . T. Ritter. Network-based firewall services: Extending the firewall into the cloud. In Nemertes White Paper N0496, 2009.","journal-title":"Nemertes White Paper"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491185.2491203"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_20_1","volume-title":"Springer-Verlag","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . Combinatorial Optimization -- Polyhedra and Efficiency . Springer-Verlag , 2003 . A. Schrijver. Combinatorial Optimization -- Polyhedra and Efficiency. Springer-Verlag, 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602204.2602216"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486022"}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2875951.2875956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2875951.2875956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:18Z","timestamp":1750221558000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2875951.2875956"}},"subtitle":["Near-Optimal and Incremental Middlebox Deployment"],"short-title":[],"issued":{"date-parts":[[2016,1,11]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1,11]]}},"alternative-id":["10.1145\/2875951.2875956"],"URL":"https:\/\/doi.org\/10.1145\/2875951.2875956","relation":{},"ISSN":["0146-4833"],"issn-type":[{"value":"0146-4833","type":"print"}],"subject":[],"published":{"date-parts":[[2016,1,11]]},"assertion":[{"value":"2016-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}