{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T12:54:59Z","timestamp":1773752099505,"version":"3.50.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,7,13]],"date-time":"2015-07-13T00:00:00Z","timestamp":1436745600000},"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":[[2015,7,13]]},"abstract":"<jats:p>\n            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\n            <jats:italic>virtual cluster<\/jats:italic>\n            : a star-shaped virtual network topology connecting virtual machines to a logical switch with absolute bandwidth guarantees.\n          <\/jats:p>\n          <jats:p>In this paper, we debunk some of the myths around the virtual cluster embedding problem. First, we show that the virtual cluster embedding problem is not NP-hard, and present the fast and optimal embedding algorithm VC-ACE for arbitrary datacenter topologies. Second, we argue that resources may be wasted by enforcing star-topology embeddings, and alternatively promote a hose embedding approach. We discuss the computational complexity of hose embeddings and derive the HVC-ACE algorithm. Using simulations we substantiate the benefits of hose embeddings in terms of acceptance ratio and resource footprint.<\/jats:p>","DOI":"10.1145\/2805789.2805792","type":"journal-article","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T13:21:25Z","timestamp":1437139285000},"page":"12-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Beyond the Stars"],"prefix":"10.1145","volume":"45","author":[{"given":"Matthias","family":"Rost","sequence":"first","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Fuerst","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"TU Berlin &amp; T-Labs, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402958.1402967"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v49:1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018465"},{"key":"e_1_2_1_4_1","volume-title":"Proc. INFOCOM 2009 and IEEE\/ACM Trans. Netw. (ToN) 2012","author":"Chowdhury K.","year":"2012","unstructured":"K. Chowdhury , M. R. Rahman , and R. Boutaba . Virtual network embedding with coordinated node and link mapping . In Proc. INFOCOM 2009 and IEEE\/ACM Trans. Netw. (ToN) 2012 , 2012 . K. Chowdhury, M. R. Rahman, and R. Boutaba. Virtual network embedding with coordinated node and link mapping. In Proc. INFOCOM 2009 and IEEE\/ACM Trans. Netw. (ToN) 2012, 2012."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018448"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316209"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374440"},{"key":"e_1_2_1_8_1","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel M.","year":"1988","unstructured":"M. Gr\u00f6tschel , L. Lov\u00e1sz , and A. Schrijver . Geometric Algorithms and Combinatorial Optimization , volume 2 of Algorithms and Combinatorics . Springer , 1988 . M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592577"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21711-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2378956.2378964"},{"key":"e_1_2_1_14_1","volume-title":"Proc. USENIX NSDI","author":"Singla A.","year":"2012","unstructured":"A. Singla , C.-Y. Hong , L. Popa , and P. B. Godfrey . Jellyfish: Networking data centers randomly . In Proc. USENIX NSDI , 2012 . A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey. Jellyfish: Networking data centers randomly. In Proc. USENIX NSDI, 2012."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658943"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342397"},{"key":"e_1_2_1_17_1","unstructured":"Measuring EC2 system performance. http:\/\/goo.gl\/V5zhEd.  Measuring EC2 system performance. http:\/\/goo.gl\/V5zhEd."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2805789.2805792","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2805789.2805792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:52Z","timestamp":1750272952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2805789.2805792"}},"subtitle":["Revisiting Virtual Cluster Embeddings"],"short-title":[],"issued":{"date-parts":[[2015,7,13]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,13]]}},"alternative-id":["10.1145\/2805789.2805792"],"URL":"https:\/\/doi.org\/10.1145\/2805789.2805792","relation":{},"ISSN":["0146-4833"],"issn-type":[{"value":"0146-4833","type":"print"}],"subject":[],"published":{"date-parts":[[2015,7,13]]},"assertion":[{"value":"2015-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}