A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains
Network Service Providers (NSPs) envisage to support the divergent and stringent requirements of future services by instantiating these services as service chains, commonly referred to as Service Function Chains (SFCs), that are customized and configured to meet specific service requirements. Howeve...
| Authors: | ; ; ; ; |
|---|---|
| Format: | Article |
| Publication date: | 2021 |
| Country: | España |
| Institution: | Universitat Politècnica de Catalunya (UPC) |
| Repository: | UPCommons. Portal del coneixement obert de la UPC |
| Language: | English |
| OAI Identifier: | oai:upcommons.upc.edu:2117/359414 |
| Online Access: | https://hdl.handle.net/2117/359414 https://dx.doi.org/10.1109/ACCESS.2021.3104841 |
| Access Level: | Open access |
| Keyword: | Computer network architectures Service function chaining Distributed algorithm Multi-domain embedding Network function virtualization. Ordinadors, Xarxes d' Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors |
| _version_ | 1878740360999469056 |
|---|---|
| author | Kibalya, Godfrey Mirondo|||0000-0002-7053-3756 |
| author2 | Serrat Fernández, Juan|||0000-0002-4551-9880 Gorricho Moreno, Juan Luis|||0000-0002-6280-1546 Gift Bujjingo, Doreen Serugunda, Jonathan |
| author2_role | author author author author |
| author_browse | Gift Bujjingo, Doreen Gorricho Moreno, Juan Luis|||0000-0002-6280-1546 Kibalya, Godfrey Mirondo|||0000-0002-7053-3756 Serrat Fernández, Juan|||0000-0002-4551-9880 Serugunda, Jonathan |
| author_facet | Kibalya, Godfrey Mirondo|||0000-0002-7053-3756 Serrat Fernández, Juan|||0000-0002-4551-9880 Gorricho Moreno, Juan Luis|||0000-0002-6280-1546 Gift Bujjingo, Doreen Serugunda, Jonathan |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | Network Service Providers (NSPs) envisage to support the divergent and stringent requirements of future services by instantiating these services as service chains, commonly referred to as Service Function Chains (SFCs), that are customized and configured to meet specific service requirements. However, due to the limited footprint of the Infrastructure Providers (InPs), these SFCs may have to transcend multiple InPs/domains. In this regard, determining the optimal set of InPs in which to embed the SFC request emerges as a complex problem for several reasons. First, the large number of possible combinations for selecting the InPs to embed the different sub-chains of the request makes this problem computationally complex, rendering optimal solutions only after long computations, especially in large scale networks, which is unfeasible for delay sensitive applications. Second, the unwillingness of InPs to disclose their internal information, which may be vital for making embedding decisions, usually implies the provisioning of single-domain solutions, which are unsuitable in this working scenario. In this regard, this paper first formulates the multi-domain service deployment problem under multiple request constraints, such as bandwidth or delay, among others. Then, due to the NP-hardness nature of the above problem, this paper proposes an algorithm that is aided by a multi-stage graph for computing a request embedding solution in a distributed manner, solving the problem in acceptable run-times. Results from different simulations reveal that the proposed algorithm is optimized in terms of acceptance ratio and embedding cost, with up to 60.0% and 88.7% improvements in terms of embedding cost and execution time, respectively, for some scenarios, in comparison with a benchmark state-of-the-art algorithm. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_d1a69064f0b3d7500a67d02111a7aec3 |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/359414 |
| publishDate | 2021 |
| publishDateSort | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| publisherStr | Institute of Electrical and Electronics Engineers (IEEE) |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains Kibalya, Godfrey Mirondo|||0000-0002-7053-3756 Serrat Fernández, Juan|||0000-0002-4551-9880 Gorricho Moreno, Juan Luis|||0000-0002-6280-1546 Gift Bujjingo, Doreen Serugunda, Jonathan Computer network architectures Service function chaining Distributed algorithm Multi-domain embedding Network function virtualization. Ordinadors, Xarxes d' Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors Network Service Providers (NSPs) envisage to support the divergent and stringent requirements of future services by instantiating these services as service chains, commonly referred to as Service Function Chains (SFCs), that are customized and configured to meet specific service requirements. However, due to the limited footprint of the Infrastructure Providers (InPs), these SFCs may have to transcend multiple InPs/domains. In this regard, determining the optimal set of InPs in which to embed the SFC request emerges as a complex problem for several reasons. First, the large number of possible combinations for selecting the InPs to embed the different sub-chains of the request makes this problem computationally complex, rendering optimal solutions only after long computations, especially in large scale networks, which is unfeasible for delay sensitive applications. Second, the unwillingness of InPs to disclose their internal information, which may be vital for making embedding decisions, usually implies the provisioning of single-domain solutions, which are unsuitable in this working scenario. In this regard, this paper first formulates the multi-domain service deployment problem under multiple request constraints, such as bandwidth or delay, among others. Then, due to the NP-hardness nature of the above problem, this paper proposes an algorithm that is aided by a multi-stage graph for computing a request embedding solution in a distributed manner, solving the problem in acceptable run-times. Results from different simulations reveal that the proposed algorithm is optimized in terms of acceptance ratio and embedding cost, with up to 60.0% and 88.7% improvements in terms of embedding cost and execution time, respectively, for some scenarios, in comparison with a benchmark state-of-the-art algorithm. Institute of Electrical and Electronics Engineers (IEEE) https://hdl.handle.net/2117/359414 https://dx.doi.org/10.1109/ACCESS.2021.3104841 |
| spellingShingle | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains Kibalya, Godfrey Mirondo|||0000-0002-7053-3756 Computer network architectures Service function chaining Distributed algorithm Multi-domain embedding Network function virtualization. Ordinadors, Xarxes d' Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors |
| title | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| title_full | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| title_fullStr | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| title_full_unstemmed | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| title_short | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| title_sort | A multi-stage graph aided algorithm for distributed Service Function Chain provisioning across multiple domains |
| topic | Computer network architectures Service function chaining Distributed algorithm Multi-domain embedding Network function virtualization. Ordinadors, Xarxes d' Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors |
| topic_facet | Computer network architectures Service function chaining Distributed algorithm Multi-domain embedding Network function virtualization. Ordinadors, Xarxes d' Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors |
| url | https://hdl.handle.net/2117/359414 https://dx.doi.org/10.1109/ACCESS.2021.3104841 |