{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T01:55:41Z","timestamp":1784080541901,"version":"3.55.0"},"reference-count":15,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T00:00:00Z","timestamp":1505952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>Software\u2010Defined Networking and Network Function Virtualization are two paradigms that offer flexible software\u2010based network management. Service providers are instantiating Virtualized Network Functions, for example, firewalls, DPIs, gateways\u2014to highly facilitate the deployment and reconfiguration of network services with reduced time\u2010to\u2010value. They use Service Function Chaining technologies to dynamically reconfigure network paths traversing physical and virtual network functions. Providing a cost\u2010efficient virtual function deployment over the network for a set of service chains is a key technical challenge for service providers, and this problem has recently caught much attention from both Industry and Academia. In this article, we propose a formulation of this problem as an Integer Linear Program that allows one to find the best feasible paths and virtual function placement for a set of services with respect to a total financial cost, while taking into account the (total or partial) order constraints for Service Function Chains of each service and other constraints such as end\u2010to\u2010end latency, anti\u2010affinity rules between network functions on the same physical node and resource limitations in terms of network and processing capacities. Furthermore, we propose a heuristic algorithm based on a linear relaxation of the problem that performs close to optimum for large scale instances. \u00a9 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 97\u2013106 2018<\/jats:p>","DOI":"10.1002\/net.21768","type":"journal-article","created":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T14:16:54Z","timestamp":1506003414000},"page":"97-106","source":"Crossref","is-referenced-by-count":52,"title":["Virtual function placement for service chaining with partial orders and anti\u2010affinity rules"],"prefix":"10.1002","volume":"71","author":[{"given":"Zaid","family":"Allybokus","sequence":"first","affiliation":[{"name":"Huawei Technologies, France Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nancy","family":"Perrot","sequence":"additional","affiliation":[{"name":"Orange Labs Ch\u00e2tillon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e9r\u00e9mie","family":"Leguay","sequence":"additional","affiliation":[{"name":"Huawei Technologies, France Research Center Boulogne Billancourt, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lorenzo","family":"Maggi","sequence":"additional","affiliation":[{"name":"Huawei Technologies, France Research Center Boulogne Billancourt, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Gourdin","sequence":"additional","affiliation":[{"name":"Orange Labs France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"e_1_2_10_2_1","unstructured":"Network Functions Virtualisation (NFV) Service quality metrics ETSI GS NFV\u2010INF 010 V1.1.1 December 2014."},{"key":"e_1_2_10_3_1","doi-asserted-by":"crossref","unstructured":"B.Addis D.Belabed M.Bouet andS.Secci Virtual network functions placement and routing optimization 2015 IEEE 4th Int Conf Cloud Netw (CloudNet) Niagara Falls ON 2015 pp.171\u2013177.","DOI":"10.1109\/CloudNet.2015.7335301"},{"key":"e_1_2_10_4_1","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/INFCOM.2009.5061987","article-title":"Virtual network embedding with coordinated node and link mapping","author":"Chowdhury N.M.M.K.","year":"2009","journal-title":"IEEE INFOCOM 2009, Rio de Janeiro"},{"key":"e_1_2_10_5_1","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1109\/INFOCOM.2015.7218511","article-title":"Near optimal placement of virtual network functions","author":"Cohen R.","year":"2015","journal-title":"2015 IEEE Conf Comput Commun (INFOCOM), Kowloon"},{"key":"e_1_2_10_6_1","first-page":"374","volume-title":"An approximation algorithm for path computation and function placement in SDNs","author":"Even G.","year":"2016"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2013.013013.00155"},{"key":"e_1_2_10_8_1","doi-asserted-by":"crossref","unstructured":"C.Fuerst S.Schmid andA.Feldmann Virtual network embedding with collocation: Benefits and limitations of pre\u2010clustering 2013 IEEE 2nd Int Conf Cloud Netw (CloudNet) San Francisco CA 2013 pp.91\u201398.","DOI":"10.1109\/CloudNet.2013.6710562"},{"key":"e_1_2_10_9_1","unstructured":"M.Ghaznavi N.Shahriar R.Ahmed andR.Boutaba Service function chaining simplified CoRR 2016 abs\/1601.00751."},{"key":"e_1_2_10_10_1","first-page":"2542","article-title":"Software\u2010defined network function virtualization: A survey","author":"Li Y.","year":"2015","journal-title":"IEEE Access"},{"key":"e_1_2_10_11_1","doi-asserted-by":"crossref","unstructured":"M.C.Luizelli L.R.Bays L.S.Buriol M.P.Barcellos andL.P.Gaspary Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions 2015 IFIP\/IEEE Int Symp Integr Netw Manage (IM) Ottawa ON 2015 pp.98\u2013106.","DOI":"10.1109\/INM.2015.7140281"},{"key":"e_1_2_10_12_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2875951.2875956","article-title":"It's a match!: Near\u2010optimal and incremental middlebox deployment","volume":"46","author":"Lukovszki T.","year":"2016","journal-title":"ACM SIGCOMM Comput Commun Rev"},{"key":"e_1_2_10_13_1","unstructured":"T.LukovszkiandS.Schmid \u201cOnline admission control and embedding of service chains \u201d Structural Information and Communication Complexity: 22nd Int Colloq SIROCCO 2015 Montserrat Spain July 14\u201016 2015 Post\u2010Proceedings C. Scheideler (Editor) Springer International Publishing Cham 2015 pp.104\u2013118."},{"key":"e_1_2_10_14_1","doi-asserted-by":"crossref","unstructured":"S.Mehraghdam M.Keller andH.Karl Specifying and placing chains of virtual network functions 2014 IEEE 3rd Int Conf Cloud Netw (CloudNet) Luxembourg 2014 pp.7\u201313.","DOI":"10.1109\/CloudNet.2014.6968961"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2015.2477041"},{"key":"e_1_2_10_16_1","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1109\/CNSM.2014.7014205","article-title":"VNF\u2010P: A model for efficient placement of virtualized network functions","author":"Moens H.","year":"2014","journal-title":"10th International Conference on Network and Service Management (CNSM) and Workshop, Rio de Janeiro"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21768","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T14:45:57Z","timestamp":1694443557000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,21]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1002\/net.21768"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.21768","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,21]]}}}