{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:04Z","timestamp":1750306804169,"version":"3.41.0"},"reference-count":94,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T00:00:00Z","timestamp":1373500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0963974, CCF- 0820138, and CNS-0720604"],"award-info":[{"award-number":["CNS-0963974, CCF- 0820138, and CNS-0720604"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CNS-0963974, CCF- 0820138, and CNS-0720604"],"award-info":[{"award-number":["CNS-0963974, CCF- 0820138, and CNS-0720604"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>Network virtualization provides a novel approach to running multiple concurrent virtual networks over a common physical network infrastructure. From a research perspective, this enables the networking community to concurrently experiment with new Internet architectures and protocols. From a market perspective, on the other hand, this paradigm is appealing as it enables infrastructure service providers to experiment with new business models that range from leasing virtual slices of their infrastructure to hosting multiple concurrent network services.<\/jats:p>\n          <jats:p>In this article, we present the slice embedding problem and recent developments in the area. A slice is a set of virtual instances spanning a set of physical resources. The embedding problem consists of three main tasks: (1) resource discovery, which involves monitoring the state of the physical resources, (2) virtual network mapping, which involves matching users' requests with the available resources, and (3) allocation, which involves assigning the resources that match the users' requests.<\/jats:p>\n          <jats:p>We also outline how these three tasks are tightly coupled, and how there exists a wide spectrum of solutions that either solve a particular task or jointly solve multiple tasks along with the interactions among them. To dissect the space of solutions, we introduce three main classification criteria, namely: (1) the type of constraints imposed by the user, (2) the type of dynamics considered in the embedding process, and (3) the allocation strategy adopted. Finally, we conclude with a few interesting research directions.<\/jats:p>","DOI":"10.1145\/2522968.2522974","type":"journal-article","created":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T14:09:19Z","timestamp":1383746959000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Slice embedding solutions for distributed service architectures"],"prefix":"10.1145","volume":"46","author":[{"given":"Flavio","family":"Esposito","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Ibrahim","family":"Matta","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Vatche","family":"Ishakian","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2013,7,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391949.1391952"},{"volume-title":"Proceedings of the 31st Annual IEEE Conference on Computer Communications (IEEE\/INFOCOM'12)","author":"Alicherry M.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"Andersen D. G. 2002. Theoretical approaches to node assignment. Unpublished manuscript. http:\/\/repository.cmu.edu\/cgi\/viewcontent.cgi&quest;article=1079&context=compsci.  Andersen D. G. 2002. Theoretical approaches to node assignment. Unpublished manuscript. http:\/\/repository.cmu.edu\/cgi\/viewcontent.cgi&quest;article=1079&context=compsci."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2005.136"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"AuYoung A. Buonadonna P. Chun B. N. Ng C. Parkes D. C. Shneidman J. Snoeren A. C. and Vahdat A. 2009. Two auction-based resource allocation environments: Design and experience. In Market Oriented Grid and Utility Computing R. Buyya and K. Bubendorfer Eds. Chapter 23 Wiley.  AuYoung A. Buonadonna P. Chun B. N. Ng C. Parkes D. C. Shneidman J. Snoeren A. C. and Vahdat A. 2009. Two auction-based resource allocation environments: Design and experience. In Market Oriented Grid and Utility Computing R. Buyya and K. Bubendorfer Eds. Chapter 23 Wiley.","DOI":"10.1002\/9780470455432.ch23"},{"volume-title":"Proceedings of the 1st Workshop on Operating System and Architectural Support for the Ondemand IT InfraStructure.","author":"AuYoung A.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 2nd International Workshop on Management of Emerging Networks and Services (IEEE\/MENS'10)","author":"Baldine I.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/885651.781041"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159916"},{"key":"e_1_2_1_10_1","unstructured":"Bertsimas D. and Tsitsiklis J. 1997. Introduction to Linear Optimization. Athena Scientific.   Bertsimas D. and Tsitsiklis J. 1997. Introduction to Linear Optimization. Athena Scientific."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex optimization. http:\/\/www.stanford.edu\/people\/boyd\/cvxbook.html.   Boyd S. and Vandenberghe L. 2004. Convex optimization. http:\/\/www.stanford.edu\/people\/boyd\/cvxbook.html.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.836103"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592648.1592660"},{"volume-title":"Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization. 51--66","author":"Chakrabarti A.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851486"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9128-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1971162.1971168"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.887322"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851399.1851408"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2009.10.017"},{"volume-title":"Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM'09)","author":"Chowdhury N. M. M. K.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","unstructured":"Chun B. N. and Vahdat A. 2003. Workload and failure characterization on a large-scale federated testbed. Tech. rep. IRB-TR-03-040 Intel Research Berkeley CA.  Chun B. N. and Vahdat A. 2003. Workload and failure characterization on a large-scale federated testbed. Tech. rep. IRB-TR-03-040 Intel Research Berkeley CA."},{"key":"e_1_2_1_23_1","unstructured":"Chun B. N. Ng C. Albrecht J. Parkes D. C. and Vahdat A. 2004. Computational resource exchanges for distributed resource allocation. (Unpublished) http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary.  Chun B. N. Ng C. Albrecht J. Parkes D. C. and Vahdat A. 2004. Computational resource exchanges for distributed resource allocation. (Unpublished) http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary."},{"volume-title":"Proceedings of the 2nd IEEE Workshop on Embedded Networked Sensors.","author":"Chun B. N.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/972374.972398"},{"volume-title":"Proceedings of the 3rd IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition. 149--159","author":"Cordella L. P.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592648.1592663"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1544012.1544079"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.284.16077"},{"volume-title":"Proceedings of the 19th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'07)","author":"Duan Q.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803918"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"volume-title":"TR 2012-014","author":"Esposito F.","key":"e_1_2_1_33_1"},{"volume-title":"Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM'09)","author":"Esposito F.","key":"e_1_2_1_34_1"},{"volume-title":"Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM'06)","author":"Fan J.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12963-6_3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198255.1198265"},{"key":"e_1_2_1_38_1","unstructured":"For Network Innovations G. E. 2013. http:\/\/www.geni.net.  For Network Innovations G. E. 2013. http:\/\/www.geni.net."},{"key":"e_1_2_1_39_1","unstructured":"Foster I. and Kesselman C. 2003. The Grid 2. Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers.   Foster I. and Kesselman C. 2003. The Grid 2. Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1165389.945459"},{"key":"e_1_2_1_41_1","unstructured":"Geni. 2009. End-user opt-in working group. http:\/\/groups.geni.net\/geni\/wiki\/GeniOptIn.  Geni. 2009. End-user opt-in working group. http:\/\/groups.geni.net\/geni\/wiki\/GeniOptIn."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592576"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.779203"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1364782.1364786"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1544012.1544027"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference on Annual Technical Conference (ATC'08)","author":"Hibler M.","key":"e_1_2_1_46_1"},{"volume-title":"Computer: An Introduction to the Design of Warehouse-Scale Machines","year":"2009","author":"Hoelzle U.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.12.011"},{"volume-title":"Proceedings of the IEEE International Conference on Communications (ICC'08)","author":"Houidi I.","key":"e_1_2_1_49_1"},{"volume-title":"Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS'03)","author":"Huang A.-C.","key":"e_1_2_1_50_1"},{"volume-title":"Proceedings of the ACM\/IFIP\/USENIX Middleware Conference. 374--393","author":"Ishakian V.","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2010.17"},{"volume-title":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science. 426--435","author":"Kolliopoulos S. G.","key":"e_1_2_1_53_1"},{"volume-title":"Computer Networking: A Top-Down Approach","year":"2009","author":"Kurose J. F.","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1233813.1233816"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555271.1555275"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592648.1592662"},{"volume-title":"Proceedings of the 8th International Conference of Distributed Computing Systems.","author":"Litzkow M.","key":"e_1_2_1_58_1"},{"volume-title":"Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS'08)","author":"Londono J.","key":"e_1_2_1_59_1"},{"volume-title":"Proceedings of the USENIX Workshop on Hot Topics in Cloud Computing (HotCloud'09)","author":"Londono J.","key":"e_1_2_1_60_1"},{"key":"e_1_2_1_61_1","unstructured":"Lu J. and Turner J. 2006. Efficient mapping of virtual networks onto a shared substrate. Tech. rep. Washington University in St. Louis. http:\/\/www.arl.wustl.edu\/Publications\/2005-09\/wucse2006-35.pdf.  Lu J. and Turner J. 2006. Efficient mapping of virtual networks onto a shared substrate. Tech. rep. Washington University in St. Louis. http:\/\/www.arl.wustl.edu\/Publications\/2005-09\/wucse2006-35.pdf."},{"volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09)","author":"Madhyastha H. V.","key":"e_1_2_1_62_1"},{"key":"e_1_2_1_63_1","first-page":"2004","article-title":"The ganglia distributed monitoring system: Design, implementation and experience","volume":"30","author":"Massie M. L.","year":"2003","journal-title":"Parallel Comput."},{"volume":"3","volume-title":"Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'98)","author":"Matta I.","key":"e_1_2_1_64_1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2008.03.006"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2011.5983876"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPDC.2005.1520946"},{"key":"e_1_2_1_68_1","unstructured":"Organization for the Advancement of Structured Information Standards (OASIS). 2006. Universal description discovery and integration. Version 3.0.2. https:\/\/www.oasis-open.org\/standards.  Organization for the Advancement of Structured Information Standards (OASIS). 2006. Universal description discovery and integration. Version 3.0.2. https:\/\/www.oasis-open.org\/standards."},{"key":"e_1_2_1_69_1","unstructured":"Page L. Brin S. Motwani R. and Winograd T. 1999. The pagerank citation ranking: Bringing order to the web. Tech. rep. 1999-66 Stanford InfoLab.  Page L. Brin S. Motwani R. and Winograd T. 1999. The pagerank citation ranking: Bringing order to the web. Tech. rep. 1999-66 Stanford InfoLab."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.879350"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/774763.774772"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12963-6_4"},{"key":"e_1_2_1_73_1","unstructured":"Rfc2547. 2013. http:\/\/tools.ietf.org\/html\/rfc2547.  Rfc2547. 2013. http:\/\/tools.ietf.org\/html\/rfc2547."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/956981.956988"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1113361.1113369"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653687"},{"key":"e_1_2_1_77_1","unstructured":"RSP. 2013. http:\/\/www.protogeni.net\/trac\/protogeni\/wiki\/RSpec.  RSP. 2013. http:\/\/www.protogeni.net\/trac\/protogeni\/wiki\/RSpec."},{"volume":"10","volume-title":"Proceedings of the 10th Conference on Hot Topics in Operating Systems (USENIX'05)","author":"Shneidman J.","key":"e_1_2_1_78_1"},{"key":"e_1_2_1_79_1","unstructured":"Skiena. S. S. 1997. Set Packing. The Algorithm Design Manual. http:\/\/sist.sysu.edu.cn\/&sim;isslxm\/DSA\/textbook\/Skiena.-.TheAlgorithmDesignManual.pdf.  Skiena. S. S. 1997. Set Packing. The Algorithm Design Manual. http:\/\/sist.sysu.edu.cn\/&sim;isslxm\/DSA\/textbook\/Skiena.-.TheAlgorithmDesignManual.pdf."},{"volume-title":"Proceedings of the International Symposium on High-Performance Distributed Computing (HPDC'03)","author":"Spence D.","key":"e_1_2_1_80_1"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"Srinivasan S. Lee J. W. Liu E. Kester M. Schulzrinne H. Hilt V. Seetharaman S. and Khan A. 2009. NetServ: Dynamically deploying in-network services. http:\/\/www.cs.columbia.edu\/&sim;jae\/papers\/netserv-rearch-paper-v1.3-camera.pdf.  Srinivasan S. Lee J. W. Liu E. Kester M. Schulzrinne H. Hilt V. Seetharaman S. and Khan A. 2009. NetServ: Dynamically deploying in-network services. http:\/\/www.cs.columbia.edu\/&sim;jae\/papers\/netserv-rearch-paper-v1.3-camera.pdf.","DOI":"10.1145\/1658978.1658988"},{"key":"e_1_2_1_82_1","unstructured":"Sword. 2005. Source code http:\/\/sword.cs.williams.edu\/.  Sword. 2005. Source code http:\/\/sword.cs.williams.edu\/."},{"volume-title":"IEEE Global Communication Conference (GLOBECOM'05)","author":"Turner J.","key":"e_1_2_1_83_1"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/INM.2007.374784"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844152"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925861.1925867"},{"key":"e_1_2_1_87_1","unstructured":"World Wide Web Consortium (W3C). 2006. Web service description language version 2. http:\/\/www.w3.org\/TR\/2006\/WD-wsdl20-rdf-20060518\/.  World Wide Web Consortium (W3C). 2006. Web service description language version 2. http:\/\/www.w3.org\/TR\/2006\/WD-wsdl20-rdf-20060518\/."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2002396.2002403"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/1355734.1355737"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1109\/EEE.2005.1"},{"volume-title":"Proceedings of the IEEE Network Operations and Management Symposium (NOMS'10)","author":"Zaheer F.","key":"e_1_2_1_91_1"},{"volume-title":"Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM'06)","author":"Zhu Y.","key":"e_1_2_1_92_1"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851516"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/1544012.1544076"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522968.2522974","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2522968.2522974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:53Z","timestamp":1750232093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522968.2522974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,11]]},"references-count":94,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2522968.2522974"],"URL":"https:\/\/doi.org\/10.1145\/2522968.2522974","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2013,7,11]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}