# A Cross-Domain Service Function Chain Deployment Scheme Based on Bargaining Game

Authors: Guoyan Li; Yajuan Ren; Yi Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Software-defined networking (SDN) and network function virtualization (NFV) technologies provide support for service function chain (SFC) deployment. As the scale of a network expands, SDN domains are maintained and managed by their respective network operators. When deploying an SFC in multiple domains, to protect the privacy of each domain is challenging. We propose a cross-domain SFC deployment scheme based on a bargaining game. We establish an effective cross-domain service chain system model and combine resource consumption cost and load balance to translate SFC deployment to an optimization problem. A bargaining game model is established so as to reasonably optimize these contradictory parameters. We solve the model by an improved imperialist competition algorithm and obtain the optimal node mapping relationship. Experimental results show that our method performs better than the current one in terms of network load balancing and mapping overhead and has better scalability.


---

## Body

## 1. Introduction

The rapid development of diversified network businesses such as e-commerce, data centers, and social networks has posed challenges to traditional network service models [1]. (1) The coupling between network devices is large, and the topology dependence is severe. For example, deep packet inspection (DPI), firewalls (FWs), and intrusion detection systems (IDS) are mostly deployed on switches based on intermediate hardware boxes, resulting in poor network scalability, insufficient flexibility, and management difficulties. (2) Security services are statically deployed on network devices and cannot be combined, so multidomain services cannot be shared, making it a challenge to meet the dynamic changes of business requirements. Software-defined networking (SDN) [2] has characteristics of separation of control and forwarding. Network function virtualization (NFV) [3], such as of IDS and firewalls, eliminates expensive special equipment [4]. The combination of SDN and NFV provides a new direction in the research of the service function chain (SFC) [5]. SFC deployed virtualization network function (VNF) [6] on the server through NFV technology. According to the requirements of network users and operators, traffic can be guided not only by the centralized traffic control function of SDN but also by VNF instances on the server to provide customized network services.Research on the deployment of SFC has focused on single-domain networks and has obtained some results [7–12]. Affected by geographic locations in the virtual environment [13], VNFs in an SFC are usually deployed in different SDN domains, which are often managed and maintained by different network operators, whose network topology and resource information are independent and closed [14]. The current single-domain network SFC mapping algorithm is unsuitable for multiple domains. Network operators of each SDN domain expect to maintain autonomy and can formulate in-domain SFC deployment algorithms or diversified mapping targets according to their computing power or management strategy. Hence, when an SFC is deployed, each SDN domain must ensure the privacy of its information. To gather the resources of multiple SDN domains to deploy SFC, i.e., to deploy a cross-domain SFC, is a problem that urgently requires solution.Solutions to the problem of cross-domain SFC deployment are either centralized [15–17] or distributed [18, 19]. The centralized method has shortcomings in terms of privacy, robustness, and performance optimization of the autonomous domain. The distributed method has difficulty obtaining the overall optimal mapping scheme and lacks support for load balancing between independent domains. Hence, to reasonably and efficiently deploy the SFC without violating the privacy of the multidomain network, we abstract the physical system into the abstract network with a simpler structure through the public information of the physical network and full mesh aggregation (FMA) [20]. This protects the privacy of the multidomain network and can be globally controlled. The deployment cost of an SFC in a multidomain network is paid by the user who sends the service request. More importantly, the minimization of the user deployment SFC cost requires its deployment to consider user requirements. However, network operators should not be ignored. They expect physical networks to deploy as many service chains as possible, and the more balanced, the better the performance. We propose a cross-domain deployment strategy based on a bargaining game (CDSBG). Our main contributions are summarized as follows:(i)
We study the deployment problem of a multidomain SFC and construct a system model. From the perspective of network users and operators, it is equivalent to the optimization of the underlying network resource consumption cost and load balancing degree.(ii)
Considering the contradiction between the two optimization indicators, the bargaining game method is introduced to solve the problem, and a bargaining model is built.(iii)
An improved imperialist competition algorithm (ICA) is proposed to solve the model. Simulation results show that the algorithm can fairly balance resource consumption cost and load balancing degree to quickly determine an SFC deployment scheme. Hence, the proposed strategy is effective.


## 2. Related Work

The deployment of a single-domain SFC has been widely studied. Zhang et al. [7] established a multiobjective optimization model to maximize average resource utilization, minimize average response time, and optimize service chain mapping according to network conditions and mapping requests. A matrix optimization and multisegment graph method based on overhead and delay was proposed to select the approximate optimal solution of a VNF deployment problem [8]. Li et al. [9] abstracted the problem of service path selection as a grey system theory problem and proposed an appropriate service portfolio selection and traffic control method. Han et al. [10] proposed an SFC deployment approach based on network flow theory to meet operators’ network requirements for load balancing, low latency, and efficient resource utilization. It is difficult to achieve dynamic management of virtual resource use when an SFC is deployed offline. For this reason, Sun et al. [11] and Liu et al. [12] studied the deployment and adjustment of SFCs in dynamic scenarios.The above research is limited to the single-domain environment. To protect the privacy of each domain in a network increases the complexity of the deployment of cross-domain SFC. A method was proposed to solve the problem of cross-domain virtual network mapping [21, 22]. Although these methods have certain guiding significance, they cannot be directly applied to the deployment of a multidomain SFC. To ensure the sequential nature of VNF in SFC deployment, Xu et al. [23] proposed a cross-domain SFC deployment scheme divided by service chain and mapped by service sub-chain to avoid additional network delay. Zhou [24] studied the influence of full disclosure, partial hiding, and complete isolation of network information on cross-domain SFC mapping. Sun et al. [15, 16] studied the mapping problem of the SFC and the question of reducing power overhead during mapping in a multidomain network. To ensure the privacy of each domain in a physical network, the order of VNF in the SFC, and the power overhead, they proposed a fast-response cross-domain mapping algorithm for SFC and a cross-domain mapping algorithm aiming at energy saving. Zhang et al. [17] jointly minimized the total number of SDN domains occupied by SFC and the corresponding cost of network resource consumption and proposed a deployment algorithm to solve the optimization problem. Zhong et al. [18] formalized the cost-aware SFC choreography problem across multiple data centers as an ILP optimization problem to coordinate SFC deployment across multiple distributed control centers while considering a distributed control system load. Liu et al. [19] proposed a distributed cross-domain mapping method for multidomain collaboration, dividing the mapping into domain-level partitioning, intradomain mapping, and interdomain load balancing.It can be seen that most solutions to cross-domain SFC deployment problems are just to simply complete SFC deployment, which ensures the sequential nature of VNF, and a few consider the power and resources consumed by SFC deployment. However, the deployment of SFCs in multiple domains while considering the interests of both network users and operators has not been fully explored. We propose a cross-domain deployment strategy of a bargaining game and an improved ICA to solve the cross-domain SFC deployment problem.


## 3. Analysis and Modeling

### 3.1. System Model

As shown in Figure1, the system model of multidomain SFC deployment includes infrastructure, logical control, and central decision layers.Figure 1
Multidomain service function chain deployment system model.The infrastructure layer includes general-purpose hardware devices (such as standardized forwarding and x86 hardware resource devices) that provide a physical environment for deploying VNF. It is composed of multiple SDN autonomous domains, each managed by different network operators and service providers. The deployment scheme and operation strategy of SDN domains vary by a service provider. Each SDN domain has at least one SDN controller to manage and maintain network resources within the region. The SDN (or logical) controller provides logical centralized control of the infrastructure, which is the architectural foundation for the SDN. Each SDN domain is relatively independent and collaboratively receives the deployment strategy issued by the logical control layer to provide timely and effective responses to user requests.The logical control layer is composed of SDN controllers in each domain and is a bridge connecting the central decision and infrastructure layers. The controllers are connected through the SDN east-west interface, which defines the communication between them. It can complete cross-domain traffic processing and realize collaborative work between multiple heterogeneous controllers. SDN controllers are independent and cannot know the topology of the entire network. They can only observe the state information, such as topology and virtual resource usage, in their own domains and a small amount of information from boundary servers in other domains. According to the deployment strategy issued by the central controller, the SDN controller maps VNF and virtual links to the bottom layer to realize the deployment of the logical service chain.The central decision layer sets up the central controller, global network view, and data center. When a user request arrives, the central controller receives an SFC deployment request. The central controller selects the best candidate SDN domain in which to deploy VNF according to the current network resources and status. It determines the optimal VNF deployment scheme and network service function forwarding path. The data center stores user requests and the current state of network resources. The global network view provides information to the central controller based on the topology among the SDN domains so that the optimal SFC deployment scheme can be determined.


### 3.2. Problem Analysis

When a cross-domain SFC is deployed, VNF nodes can be mapped to physical nodes in different domains, and virtual links can be mapped to the underlying paths across domains. Figure2 shows the service chain deployment process. When a service request arrives, the central controller deploys the VNF in SFC to different SDN domains according to the deployment strategy, and a domain’s SDN controller deploys each VNF on the corresponding physical nodes according to the requirements of the network operators in the domain. Then, we can build the service chain deployment path with the correct VNF sequence in the SFC.Figure 2
SFC deployment process.As shown in Figure2, in schemes 1 and 2, VNF is deployed in three and five SDN domains, respectively. Scheme 1 occupies fewer SDN domains and has a shorter deployment path, which reduces the consumption of network resources and better meets the cost requirements of users. Therefore, scheme 1 is superior in terms of user cost. However, scheme 1 deploys more VNFs on domain 3 with higher load, which results in an unbalanced network load. Therefore, scheme 2 is superior in terms of network balance. For each user, it is expected to reduce the number of SFC deployment paths through domains, thereby reducing network resource costs and service fees. However, for network operators, a more balanced network can deploy more SFCs and fulfill more user requests. Therefore, the proposed deployment scheme should consider both the cost of network resources and the balance of the load among network domains.


### 3.3. Model Construction

#### 3.3.1. Parameters and Variables

To simplify the physical network topology and guide the deployment of multidomain SFC, we adopt the FMA technology and model the abstract network asGp=Np,Lp, where Npis the node set, including that within the domain Npi and the boundary node set Npo; Ep is the link set, including the abstract link set within the domain Lpi and the interdomain link set Lpo. The physical network consists of M SDN domains. Dz is the physical network of SDN domain z and can be represented by an undirected graph Gz⊂Gp, where Nz and Ez are, respectively, the collections of physical nodes and network links in domain z. The user request SFC=f1,f2,…,fq can be abstracted as a weighted directed graph Gv=Nv,Lv, where q is the number of VNFs, Nv is the set of VNF nodes in SFC, and Lv is the set of VNF virtual links in SFC. For any nv∈Nv, rqnv represents the computing resources required by node nv instantiation, and rqlv represents the bandwidth resources required by virtual link lv∈Lv. The main parameters are described in Table 1.Table 1
Network parameters and description.
Network parametersDescriptionXNode mapping matrixYijLink-type variableCostTotal resource consumption costncostNode resource consumption costolcostInterdomain link resource consumption costLzThe load factor of thez domain DzL¯Average load factor in SDN domainLBDLoad balancing degree between SDN domainsblpThe bandwidth resource capacity of the physical linkμCostBATNA of the resource consumption costμLBDBATNA of the load balancing degreeThe relevant network parameters are defined as follows.Definition 1.
Node mapping matrix. The mapping relationship between VNF instance nodes and boundary nodes is defined as a matrixXim=xim, where xim=1 means that VNF instance node i maps to boundary node m, and xim=0 means that it fails to do so. It is worth noting that the boundary node does not carry specific VNF instance node mapping. The mapping of a VNF instance node to a boundary node means that the VNF instance node is mapped to a certain intradomain node in the SDN domain, where the boundary node is located.Definition 2.
Link-type variable. According to the node mapping matrixX, the type of VNF instance link can be judged, which is defined as a Boolean variable Yij, where i and j are the endpoints of the virtual link lvi,j. If Yij=1, then link lvi,j is an interdomain link, and Yij=0 means that it is an in-domain link.


#### 3.3.2. Objective Function

1. Resource Consumption Cost. A user making a network service request expects to minimize the cost of network resource consumption while ensuring the quality of service. The resource consumption cost of cross-domain SFC deployment includes nodes, in-domain links, and interdomain links. Since the link connection information in each SDN is not fully disclosed to the public, and resource consumption differs greatly between inter- and intradomain links, we focus on the node and interdomain link resource consumption costs. The total resource consumption cost of cross-domain service chain mapping is (1)cost=α⋅ncost+β⋅olcost,where α and β are factors to adjust the weights of resource costs of node mapping and interdomain link mapping, respectively, and α+β=10≤α,β≤1. For a fixed SFC, the resource cost consumed by node mapping of the service chain is certain, while that of interdomain link mapping varies according to the boundary nodes. If ncost is a constant C, then(2)olcost=∑lvi,j∈LvYij×rqlvi,j×BMh,k,where BM is the unit resource consumption cost matrix connecting links between boundary nodes and BMm,n1≤m,n≤M is the unit resource consumption cost connecting all links between boundary nodes m and n. h=∑p=1Mxip⋅p represents the mapping of VNF node i to boundary node h, and k=∑p=1Mxjp⋅p represents the mapping of VNF node j to boundary node k.2. Load Balancing Degree. An overloaded SDN domain will cause network congestion during service requests. Therefore, the underlying network is expected to achieve a load balancing state. The load balancing degree of the underlying network is measured by the load coefficient of each SDN domain, which is the ratio between the resources occupied by the instantiated VNF and the resource capacity of the domain.SDN domain load factor measures the overall load situation of a single SDN domain. The loadDz of SDN domain z is(3)Lz=1rsDz∑m∈Dz∑i=1qxim⋅rqni,where rsDz is the residual resource capacity of domain Dz and rqni is the computational resource demand of VNF node ni. The average load in the SDN domain is(4)L¯=1Z∑z=1ZLz.To more intuitively reflect the load situation of the SDN domain in the whole physical network, we use the coefficient of variation, that is, the ratio of the standard deviation to the mean, to measure the load degree of the SDN domain, whereσ is the standard deviation,(5)σ=1Z∑z=1ZLz−L¯2,and LBD is the load balancing degree,(6)LBD=1−σL¯×100%.The greater the value ofLBD, the more balanced the network load.Two aspects of performance should be optimized in the deployment process of SFC in the multi-SDN domain to meet the needs of users and network operators. The cost of deploying resources should be reduced, and the load balance of the SDN domain should be improved. Since these two goals are contradictory, to optimize one will inevitably work against the other. Based on this, the multiobjective model is established:(7)minCostmaxLBD,(8)∑m=1Mxim=1,∀i∈Nv,(9)rqlvi,j×Yij≤blp,∀i,j∈Nv,(10)∑m∈Dz∑i=1qxim⋅rqni≤rsDz,∀Dz1≤z≤Z,(11)xim∈0,1,(12)Yij∈0,1.Constraint (8) indicates that each VNF can only be deployed to one boundary node. Constraint (9) specifies that the bandwidth resource demand of the virtual link does not exceed the capacity of the physical link. Constraint (10) reflects that each SDN domain must have sufficient resources to meet those required by VNF instantiation deployed to the domain. Constraints (11) and (12) are integrity constraints.


## 3.1. System Model

As shown in Figure1, the system model of multidomain SFC deployment includes infrastructure, logical control, and central decision layers.Figure 1
Multidomain service function chain deployment system model.The infrastructure layer includes general-purpose hardware devices (such as standardized forwarding and x86 hardware resource devices) that provide a physical environment for deploying VNF. It is composed of multiple SDN autonomous domains, each managed by different network operators and service providers. The deployment scheme and operation strategy of SDN domains vary by a service provider. Each SDN domain has at least one SDN controller to manage and maintain network resources within the region. The SDN (or logical) controller provides logical centralized control of the infrastructure, which is the architectural foundation for the SDN. Each SDN domain is relatively independent and collaboratively receives the deployment strategy issued by the logical control layer to provide timely and effective responses to user requests.The logical control layer is composed of SDN controllers in each domain and is a bridge connecting the central decision and infrastructure layers. The controllers are connected through the SDN east-west interface, which defines the communication between them. It can complete cross-domain traffic processing and realize collaborative work between multiple heterogeneous controllers. SDN controllers are independent and cannot know the topology of the entire network. They can only observe the state information, such as topology and virtual resource usage, in their own domains and a small amount of information from boundary servers in other domains. According to the deployment strategy issued by the central controller, the SDN controller maps VNF and virtual links to the bottom layer to realize the deployment of the logical service chain.The central decision layer sets up the central controller, global network view, and data center. When a user request arrives, the central controller receives an SFC deployment request. The central controller selects the best candidate SDN domain in which to deploy VNF according to the current network resources and status. It determines the optimal VNF deployment scheme and network service function forwarding path. The data center stores user requests and the current state of network resources. The global network view provides information to the central controller based on the topology among the SDN domains so that the optimal SFC deployment scheme can be determined.


## 3.2. Problem Analysis

When a cross-domain SFC is deployed, VNF nodes can be mapped to physical nodes in different domains, and virtual links can be mapped to the underlying paths across domains. Figure2 shows the service chain deployment process. When a service request arrives, the central controller deploys the VNF in SFC to different SDN domains according to the deployment strategy, and a domain’s SDN controller deploys each VNF on the corresponding physical nodes according to the requirements of the network operators in the domain. Then, we can build the service chain deployment path with the correct VNF sequence in the SFC.Figure 2
SFC deployment process.As shown in Figure2, in schemes 1 and 2, VNF is deployed in three and five SDN domains, respectively. Scheme 1 occupies fewer SDN domains and has a shorter deployment path, which reduces the consumption of network resources and better meets the cost requirements of users. Therefore, scheme 1 is superior in terms of user cost. However, scheme 1 deploys more VNFs on domain 3 with higher load, which results in an unbalanced network load. Therefore, scheme 2 is superior in terms of network balance. For each user, it is expected to reduce the number of SFC deployment paths through domains, thereby reducing network resource costs and service fees. However, for network operators, a more balanced network can deploy more SFCs and fulfill more user requests. Therefore, the proposed deployment scheme should consider both the cost of network resources and the balance of the load among network domains.


## 3.3. Model Construction

### 3.3.1. Parameters and Variables

To simplify the physical network topology and guide the deployment of multidomain SFC, we adopt the FMA technology and model the abstract network asGp=Np,Lp, where Npis the node set, including that within the domain Npi and the boundary node set Npo; Ep is the link set, including the abstract link set within the domain Lpi and the interdomain link set Lpo. The physical network consists of M SDN domains. Dz is the physical network of SDN domain z and can be represented by an undirected graph Gz⊂Gp, where Nz and Ez are, respectively, the collections of physical nodes and network links in domain z. The user request SFC=f1,f2,…,fq can be abstracted as a weighted directed graph Gv=Nv,Lv, where q is the number of VNFs, Nv is the set of VNF nodes in SFC, and Lv is the set of VNF virtual links in SFC. For any nv∈Nv, rqnv represents the computing resources required by node nv instantiation, and rqlv represents the bandwidth resources required by virtual link lv∈Lv. The main parameters are described in Table 1.Table 1
Network parameters and description.
Network parametersDescriptionXNode mapping matrixYijLink-type variableCostTotal resource consumption costncostNode resource consumption costolcostInterdomain link resource consumption costLzThe load factor of thez domain DzL¯Average load factor in SDN domainLBDLoad balancing degree between SDN domainsblpThe bandwidth resource capacity of the physical linkμCostBATNA of the resource consumption costμLBDBATNA of the load balancing degreeThe relevant network parameters are defined as follows.Definition 1.
Node mapping matrix. The mapping relationship between VNF instance nodes and boundary nodes is defined as a matrixXim=xim, where xim=1 means that VNF instance node i maps to boundary node m, and xim=0 means that it fails to do so. It is worth noting that the boundary node does not carry specific VNF instance node mapping. The mapping of a VNF instance node to a boundary node means that the VNF instance node is mapped to a certain intradomain node in the SDN domain, where the boundary node is located.Definition 2.
Link-type variable. According to the node mapping matrixX, the type of VNF instance link can be judged, which is defined as a Boolean variable Yij, where i and j are the endpoints of the virtual link lvi,j. If Yij=1, then link lvi,j is an interdomain link, and Yij=0 means that it is an in-domain link.


### 3.3.2. Objective Function

1. Resource Consumption Cost. A user making a network service request expects to minimize the cost of network resource consumption while ensuring the quality of service. The resource consumption cost of cross-domain SFC deployment includes nodes, in-domain links, and interdomain links. Since the link connection information in each SDN is not fully disclosed to the public, and resource consumption differs greatly between inter- and intradomain links, we focus on the node and interdomain link resource consumption costs. The total resource consumption cost of cross-domain service chain mapping is (1)cost=α⋅ncost+β⋅olcost,where α and β are factors to adjust the weights of resource costs of node mapping and interdomain link mapping, respectively, and α+β=10≤α,β≤1. For a fixed SFC, the resource cost consumed by node mapping of the service chain is certain, while that of interdomain link mapping varies according to the boundary nodes. If ncost is a constant C, then(2)olcost=∑lvi,j∈LvYij×rqlvi,j×BMh,k,where BM is the unit resource consumption cost matrix connecting links between boundary nodes and BMm,n1≤m,n≤M is the unit resource consumption cost connecting all links between boundary nodes m and n. h=∑p=1Mxip⋅p represents the mapping of VNF node i to boundary node h, and k=∑p=1Mxjp⋅p represents the mapping of VNF node j to boundary node k.2. Load Balancing Degree. An overloaded SDN domain will cause network congestion during service requests. Therefore, the underlying network is expected to achieve a load balancing state. The load balancing degree of the underlying network is measured by the load coefficient of each SDN domain, which is the ratio between the resources occupied by the instantiated VNF and the resource capacity of the domain.SDN domain load factor measures the overall load situation of a single SDN domain. The loadDz of SDN domain z is(3)Lz=1rsDz∑m∈Dz∑i=1qxim⋅rqni,where rsDz is the residual resource capacity of domain Dz and rqni is the computational resource demand of VNF node ni. The average load in the SDN domain is(4)L¯=1Z∑z=1ZLz.To more intuitively reflect the load situation of the SDN domain in the whole physical network, we use the coefficient of variation, that is, the ratio of the standard deviation to the mean, to measure the load degree of the SDN domain, whereσ is the standard deviation,(5)σ=1Z∑z=1ZLz−L¯2,and LBD is the load balancing degree,(6)LBD=1−σL¯×100%.The greater the value ofLBD, the more balanced the network load.Two aspects of performance should be optimized in the deployment process of SFC in the multi-SDN domain to meet the needs of users and network operators. The cost of deploying resources should be reduced, and the load balance of the SDN domain should be improved. Since these two goals are contradictory, to optimize one will inevitably work against the other. Based on this, the multiobjective model is established:(7)minCostmaxLBD,(8)∑m=1Mxim=1,∀i∈Nv,(9)rqlvi,j×Yij≤blp,∀i,j∈Nv,(10)∑m∈Dz∑i=1qxim⋅rqni≤rsDz,∀Dz1≤z≤Z,(11)xim∈0,1,(12)Yij∈0,1.Constraint (8) indicates that each VNF can only be deployed to one boundary node. Constraint (9) specifies that the bandwidth resource demand of the virtual link does not exceed the capacity of the physical link. Constraint (10) reflects that each SDN domain must have sufficient resources to meet those required by VNF instantiation deployed to the domain. Constraints (11) and (12) are integrity constraints.


## 3.3.1. Parameters and Variables

To simplify the physical network topology and guide the deployment of multidomain SFC, we adopt the FMA technology and model the abstract network asGp=Np,Lp, where Npis the node set, including that within the domain Npi and the boundary node set Npo; Ep is the link set, including the abstract link set within the domain Lpi and the interdomain link set Lpo. The physical network consists of M SDN domains. Dz is the physical network of SDN domain z and can be represented by an undirected graph Gz⊂Gp, where Nz and Ez are, respectively, the collections of physical nodes and network links in domain z. The user request SFC=f1,f2,…,fq can be abstracted as a weighted directed graph Gv=Nv,Lv, where q is the number of VNFs, Nv is the set of VNF nodes in SFC, and Lv is the set of VNF virtual links in SFC. For any nv∈Nv, rqnv represents the computing resources required by node nv instantiation, and rqlv represents the bandwidth resources required by virtual link lv∈Lv. The main parameters are described in Table 1.Table 1
Network parameters and description.
Network parametersDescriptionXNode mapping matrixYijLink-type variableCostTotal resource consumption costncostNode resource consumption costolcostInterdomain link resource consumption costLzThe load factor of thez domain DzL¯Average load factor in SDN domainLBDLoad balancing degree between SDN domainsblpThe bandwidth resource capacity of the physical linkμCostBATNA of the resource consumption costμLBDBATNA of the load balancing degreeThe relevant network parameters are defined as follows.Definition 1.
Node mapping matrix. The mapping relationship between VNF instance nodes and boundary nodes is defined as a matrixXim=xim, where xim=1 means that VNF instance node i maps to boundary node m, and xim=0 means that it fails to do so. It is worth noting that the boundary node does not carry specific VNF instance node mapping. The mapping of a VNF instance node to a boundary node means that the VNF instance node is mapped to a certain intradomain node in the SDN domain, where the boundary node is located.Definition 2.
Link-type variable. According to the node mapping matrixX, the type of VNF instance link can be judged, which is defined as a Boolean variable Yij, where i and j are the endpoints of the virtual link lvi,j. If Yij=1, then link lvi,j is an interdomain link, and Yij=0 means that it is an in-domain link.


## 3.3.2. Objective Function

1. Resource Consumption Cost. A user making a network service request expects to minimize the cost of network resource consumption while ensuring the quality of service. The resource consumption cost of cross-domain SFC deployment includes nodes, in-domain links, and interdomain links. Since the link connection information in each SDN is not fully disclosed to the public, and resource consumption differs greatly between inter- and intradomain links, we focus on the node and interdomain link resource consumption costs. The total resource consumption cost of cross-domain service chain mapping is (1)cost=α⋅ncost+β⋅olcost,where α and β are factors to adjust the weights of resource costs of node mapping and interdomain link mapping, respectively, and α+β=10≤α,β≤1. For a fixed SFC, the resource cost consumed by node mapping of the service chain is certain, while that of interdomain link mapping varies according to the boundary nodes. If ncost is a constant C, then(2)olcost=∑lvi,j∈LvYij×rqlvi,j×BMh,k,where BM is the unit resource consumption cost matrix connecting links between boundary nodes and BMm,n1≤m,n≤M is the unit resource consumption cost connecting all links between boundary nodes m and n. h=∑p=1Mxip⋅p represents the mapping of VNF node i to boundary node h, and k=∑p=1Mxjp⋅p represents the mapping of VNF node j to boundary node k.2. Load Balancing Degree. An overloaded SDN domain will cause network congestion during service requests. Therefore, the underlying network is expected to achieve a load balancing state. The load balancing degree of the underlying network is measured by the load coefficient of each SDN domain, which is the ratio between the resources occupied by the instantiated VNF and the resource capacity of the domain.SDN domain load factor measures the overall load situation of a single SDN domain. The loadDz of SDN domain z is(3)Lz=1rsDz∑m∈Dz∑i=1qxim⋅rqni,where rsDz is the residual resource capacity of domain Dz and rqni is the computational resource demand of VNF node ni. The average load in the SDN domain is(4)L¯=1Z∑z=1ZLz.To more intuitively reflect the load situation of the SDN domain in the whole physical network, we use the coefficient of variation, that is, the ratio of the standard deviation to the mean, to measure the load degree of the SDN domain, whereσ is the standard deviation,(5)σ=1Z∑z=1ZLz−L¯2,and LBD is the load balancing degree,(6)LBD=1−σL¯×100%.The greater the value ofLBD, the more balanced the network load.Two aspects of performance should be optimized in the deployment process of SFC in the multi-SDN domain to meet the needs of users and network operators. The cost of deploying resources should be reduced, and the load balance of the SDN domain should be improved. Since these two goals are contradictory, to optimize one will inevitably work against the other. Based on this, the multiobjective model is established:(7)minCostmaxLBD,(8)∑m=1Mxim=1,∀i∈Nv,(9)rqlvi,j×Yij≤blp,∀i,j∈Nv,(10)∑m∈Dz∑i=1qxim⋅rqni≤rsDz,∀Dz1≤z≤Z,(11)xim∈0,1,(12)Yij∈0,1.Constraint (8) indicates that each VNF can only be deployed to one boundary node. Constraint (9) specifies that the bandwidth resource demand of the virtual link does not exceed the capacity of the physical link. Constraint (10) reflects that each SDN domain must have sufficient resources to meet those required by VNF instantiation deployed to the domain. Constraints (11) and (12) are integrity constraints.


## 4. Multiobjective Decision Based on Bargaining Game

To meet the needs of network users and operators, in the deployment of a cross-domain SFC, we hope to simultaneously optimize the indices of resource consumption cost and load balancing degree. Both relationships involve competition and cooperation. Hence, the cost of resource consumption and load balancing can be seen as goals of competing negotiation primitives, each wanting to maximize its own benefits. The multiobjective optimization problem is generally solved based on the bargaining model in game theory.


### 4.1. Bargaining Model

The bargaining model is applied to solve the cooperative game problem. We regard goals as participants and assume that both sides are rational and set initial strategies and payoff functions. Each player negotiates continuously in the strategic space, and a Nash equilibrium is eventually obtained. The solution satisfies the Nash axiom [25] and has the properties of Pareto efficiency, symmetry, equivalent income invariance, and independent selectivity. Therefore, the bargaining problem has the following only reasonable solution:(13)x0=argmaxxf1x−d1f2x−d2,where f1 and f2 are the payoff functions of the players in the game and d1 and d2 are their respective worst possible payoffs. Nash proved that the solution that maximizes the Nash volume under the four axioms is the equilibrium solution of this problem [26].Resource consumption cost and load balancing degree are regarded as two players,Cost and LBD are profit functions of resource consumption cost and load balancing degree, and the possible mapping relationship between VNF and boundary nodes is used as the strategic space of both sides of the game. Therefore, a bargaining game model is established as shown in equation (14), with constraints as shown in equations (8)–(12), (15), and (16). μCost and μLBD are the best alternative to a negotiated agreement (BATNA) of resource consumption cost and load balancing degree, namely, the worst possible gain of both sides of the game. The goal of the game is to agree on at least this BATNA.(14)maxCost−μCostLBD−μLBD,(15)μCost<Cost,(16)μLBD<LBD.Both sides can improve their interests by changing their BATNA. If this selfish behavior is not restricted, then each participant will constantly change the BATNA, leading to bargaining failure.


### 4.2. Fair Bargaining Agreement

A fair bargaining mechanism should be established to avoid an unfair solution or bargaining failure. We find the initial BATNA that can reach the Pareto effective solution and calculate the target according to equation (14). The two sides of the game change their BATNA according to the BATNA update rule. After many iterations, we obtain the optimal Pareto front, and then we get the maximum benefit of both sides, that is, the optimal value of resource consumption cost and load balance.


#### 4.2.1. Initial BATNA

The initial BATNA is set for both sides at the beginning of the game, and the quality of the initial value determines whether the bargaining is successful. According to equations (1) and (6), Costb,Costw and LBDb,LBDw are the optimal and worst values of resource consumption cost and load balance, respectively. The minimum performance threshold for resource consumption cost and load balancing is the initial BATNA, that is, the worst target Costw,LBDw, and a bargaining game is conducted on this.


#### 4.2.2. Update Rules of BATNA

The BATNA update rule is set to avoid both players changing their BATNA without limit. When both sides of the game update their BATNA, the change of BATNA is at most half the difference between the current income and the last bargaining breakpoint. The rules are as follows:(17)μCostk+1−μCostk≤12Costk−μCostk,(18)μLBDk+1−μLBDk≤12LBDk−μLBDk,where μCostk and μLBDk, respectively, are the BATNA of resource consumption cost and load balancing degree in the process of iteration z.


## 4.1. Bargaining Model

The bargaining model is applied to solve the cooperative game problem. We regard goals as participants and assume that both sides are rational and set initial strategies and payoff functions. Each player negotiates continuously in the strategic space, and a Nash equilibrium is eventually obtained. The solution satisfies the Nash axiom [25] and has the properties of Pareto efficiency, symmetry, equivalent income invariance, and independent selectivity. Therefore, the bargaining problem has the following only reasonable solution:(13)x0=argmaxxf1x−d1f2x−d2,where f1 and f2 are the payoff functions of the players in the game and d1 and d2 are their respective worst possible payoffs. Nash proved that the solution that maximizes the Nash volume under the four axioms is the equilibrium solution of this problem [26].Resource consumption cost and load balancing degree are regarded as two players,Cost and LBD are profit functions of resource consumption cost and load balancing degree, and the possible mapping relationship between VNF and boundary nodes is used as the strategic space of both sides of the game. Therefore, a bargaining game model is established as shown in equation (14), with constraints as shown in equations (8)–(12), (15), and (16). μCost and μLBD are the best alternative to a negotiated agreement (BATNA) of resource consumption cost and load balancing degree, namely, the worst possible gain of both sides of the game. The goal of the game is to agree on at least this BATNA.(14)maxCost−μCostLBD−μLBD,(15)μCost<Cost,(16)μLBD<LBD.Both sides can improve their interests by changing their BATNA. If this selfish behavior is not restricted, then each participant will constantly change the BATNA, leading to bargaining failure.


## 4.2. Fair Bargaining Agreement

A fair bargaining mechanism should be established to avoid an unfair solution or bargaining failure. We find the initial BATNA that can reach the Pareto effective solution and calculate the target according to equation (14). The two sides of the game change their BATNA according to the BATNA update rule. After many iterations, we obtain the optimal Pareto front, and then we get the maximum benefit of both sides, that is, the optimal value of resource consumption cost and load balance.


### 4.2.1. Initial BATNA

The initial BATNA is set for both sides at the beginning of the game, and the quality of the initial value determines whether the bargaining is successful. According to equations (1) and (6), Costb,Costw and LBDb,LBDw are the optimal and worst values of resource consumption cost and load balance, respectively. The minimum performance threshold for resource consumption cost and load balancing is the initial BATNA, that is, the worst target Costw,LBDw, and a bargaining game is conducted on this.


### 4.2.2. Update Rules of BATNA

The BATNA update rule is set to avoid both players changing their BATNA without limit. When both sides of the game update their BATNA, the change of BATNA is at most half the difference between the current income and the last bargaining breakpoint. The rules are as follows:(17)μCostk+1−μCostk≤12Costk−μCostk,(18)μLBDk+1−μLBDk≤12LBDk−μLBDk,where μCostk and μLBDk, respectively, are the BATNA of resource consumption cost and load balancing degree in the process of iteration z.


## 4.2.1. Initial BATNA

The initial BATNA is set for both sides at the beginning of the game, and the quality of the initial value determines whether the bargaining is successful. According to equations (1) and (6), Costb,Costw and LBDb,LBDw are the optimal and worst values of resource consumption cost and load balance, respectively. The minimum performance threshold for resource consumption cost and load balancing is the initial BATNA, that is, the worst target Costw,LBDw, and a bargaining game is conducted on this.


## 4.2.2. Update Rules of BATNA

The BATNA update rule is set to avoid both players changing their BATNA without limit. When both sides of the game update their BATNA, the change of BATNA is at most half the difference between the current income and the last bargaining breakpoint. The rules are as follows:(17)μCostk+1−μCostk≤12Costk−μCostk,(18)μLBDk+1−μLBDk≤12LBDk−μLBDk,where μCostk and μLBDk, respectively, are the BATNA of resource consumption cost and load balancing degree in the process of iteration z.


## 5. Model Solving

The bargaining model in this paper is that of non-convex nonlinear optimization, which is difficult to solve by traditional methods. The evolutionary algorithm is metaheuristic and is based on the whole, which can provide a relatively optimal solution in a reasonable time, and it has been widely used in the computer field. The ICA [27] is the transition from the simulation of biological evolution to that of social behavior, inspired by the imperialist invasion of colonies and competing behavior. It has advantages over a traditional population optimization algorithm. It needs no gradient function, and its powerful local searchability and parallel evolution mechanism allow all empires to compete. We use the ICA to solve the model in this paper.


### 5.1. Basic Imperialist Competition Algorithm

The ICA is an overall optimization algorithm whose core is an imperial country, which constitutes the largest power through the continuous invasion and competition between colonial countries and colonies. Combined with the cross-domain SFC deployment problem, the policy space policy, that is, the mapping relationship between VNF nodes and boundary nodes, is regarded as a country. Generally, the lower the cost, the better the strategy, and the greater the power of the corresponding country. Through equation (14), the objective function fxi=Cost−μCostLBD−μLBD of the bargaining game is used to calculate the national cost, ci=Cmax−fxi, where Cmax is a sufficiently large positive number. The basic ICA includes the steps of imperial initialization, assimilation, revolution, and imperial competition [28].In the initial stage of the empire, if the normalization cost of a country is zero, it will cause the initial empire to have no colonies and thus cannot proceed with the assimilation process, which will affect the search efficiency of the algorithm. The deviation angle is an important parameter in the process of assimilation. Blind selection may cause the algorithm to fall into a local optimal solution and converge prematurely. Under the action of a competition mechanism, weak empires are destroyed, one by one. The number of empires rapidly decreases, the diversity of the population is consequently reduced, and it is easy to fall into a local problem. In order to overcome the above shortcomings, the new definition of empire cost, adaptive deviation angle, and empire split mechanism are introduced to improve the ICA. We propose an adaptive ICA based on the division mechanism.


### 5.2. Improved Algorithm

#### 5.2.1. New Definition of Empire Cost

In the initial stage of an empire, it is necessary to divide the colonial countriesNim and colonies Ncol according to the power of the state. The colonial countries and all their colonies constitute an empire. The normalized cost Ck and power of colonial countries pk are(19)Ck=maxlcl−ck,pk=Ck∑l=1Nimcl,where maxlcl is the highest cost value of all colonial countries, l=1,2,…,Nim.Then, there must be at least one colonial country whose normalized cost and power are zero, which means it cannot be allocated to a colony, making it difficult to carry out subsequent assimilation revolutions, affecting the search efficiency of ICA. Equation (20) redefines the normalized cost to effectively avoid normalized cost and power of zero, so that all colonial countries can be allocated to a certain number of colonies,(20)Ck=2×maxlcl−ck.


#### 5.2.2. Adaptive Deviation Angle

In the basic ICA, the deviation angleθ is uniformly distributed as θ∼U−φ,φ, where usually φ=π/4. Since the deviation angle is fixed, the algorithm will fall into a local search.Chaos is a stochastic motion state directly obtained by a deterministic equation and is a nonlinear phenomenon in nature. Logistic mapping is a classical chaos model with randomness and ergodicity, which is important in solving optimization problems. By introducing logistic mapping from chaos theory to the ICA and optimizing the deviation angle in the assimilation process, the phenomenon of precocity can be improved, as can the ability of colonies to seek the optimal global solution away from the optimal local solution. The expression of logistic mapping isxk+1=εxk1−xk.The definition of deviation angle is(21)θt+1=εθt1−θt.Set chaotic parametersε=0.4, θ∈0,1. In each iteration, the chaotic mutation mechanism produces a random function to realize the dynamic control of parameters.


#### 5.2.3. Imperial Division Mechanism

There are two ways to create new states: assimilation and revolution. However, both are carried out within an empire. If the colonial countries have little or no change in the larger algebra, then this will lead to the increase of similarity and decrease of population diversity in the empire and eventually the premature convergence of ICA.We propose an imperial division strategy, which is a new way to create a new empire and set the rate of division for the current empire. When the split rate is greater than the set threshold, a colony becomes a new colonial country and sees a certain number of colonies allocated by the empire to form a new empire. The split rate can be expressed as(22)SPk=η⋅NCkN⋅exptT⋅zt,(23)zt=1,Nnow<Nim,0,other,where Nnow is the current number of empires, T is the total number of iterations of the algorithm, and η is the regulator, which is usually 0.36. In this paper, we set both the splitting threshold and splitting ratio to 0.5.


### 5.3. Cross-Domain  SFC  Deployment Algorithms

To complete SFC deployment, the deployment path is found through the mapping relationship between VNF nodes and boundary nodes. To meet the needs of network users and operators, the optimal mapping relationship is needed to optimize resource consumption cost and load balancing degree. Given the incompatibility of these two optimization goals, we combine the bargaining game process and optimization mechanism of the ICA to obtain the Pareto optimal solution and the best node mapping matrix. The process of cross-domain service chain deployment is shown in Algorithm1.Algorithm 1: CDSBG.
Input: abstract networkGp=Np,Lp;SFC=f1,f2,…,fq;Resource capacity of SDN domainrs0;Maximum number of iterationsT;ICA populationN;Number of empiresNim.Output: node mapping matrixX(1)
Initialize the number of empires, maximum number of iterations, and related parametersθ and RPt.(2)
Initial feasible policies are randomly generated in all policy sets. Initialize country locationxi and country cost ci.(3)
Initialize BATNAμCost andμLBD.(4)
Initial empire building. Calculate the country's normalized costs and power, and generate ASD empires.(5)
Carry out assimilation and revolutionary operations on each imperial colony, and judge whether the empire will split according to equation (22). If so, split operations will be carried out; otherwise, the next step will be taken.(6)
Imperial competition stage. Transfer the worst colony of the worst empire to the best empire.(7)
The empire dies. Check if an empire has no colonies. If so, delete the empire.(8)
Determine if there is only one empire; if so, update BATNA according to formulas (17) and (18); otherwise, loop through steps 5–7.(9)
Determine whether the number of iterations has reachedT. If conditions are met, then the loop is closed, and the optimal imperial position is output. Otherwise, proceed to step 5.


## 5.1. Basic Imperialist Competition Algorithm

The ICA is an overall optimization algorithm whose core is an imperial country, which constitutes the largest power through the continuous invasion and competition between colonial countries and colonies. Combined with the cross-domain SFC deployment problem, the policy space policy, that is, the mapping relationship between VNF nodes and boundary nodes, is regarded as a country. Generally, the lower the cost, the better the strategy, and the greater the power of the corresponding country. Through equation (14), the objective function fxi=Cost−μCostLBD−μLBD of the bargaining game is used to calculate the national cost, ci=Cmax−fxi, where Cmax is a sufficiently large positive number. The basic ICA includes the steps of imperial initialization, assimilation, revolution, and imperial competition [28].In the initial stage of the empire, if the normalization cost of a country is zero, it will cause the initial empire to have no colonies and thus cannot proceed with the assimilation process, which will affect the search efficiency of the algorithm. The deviation angle is an important parameter in the process of assimilation. Blind selection may cause the algorithm to fall into a local optimal solution and converge prematurely. Under the action of a competition mechanism, weak empires are destroyed, one by one. The number of empires rapidly decreases, the diversity of the population is consequently reduced, and it is easy to fall into a local problem. In order to overcome the above shortcomings, the new definition of empire cost, adaptive deviation angle, and empire split mechanism are introduced to improve the ICA. We propose an adaptive ICA based on the division mechanism.


## 5.2. Improved Algorithm

### 5.2.1. New Definition of Empire Cost

In the initial stage of an empire, it is necessary to divide the colonial countriesNim and colonies Ncol according to the power of the state. The colonial countries and all their colonies constitute an empire. The normalized cost Ck and power of colonial countries pk are(19)Ck=maxlcl−ck,pk=Ck∑l=1Nimcl,where maxlcl is the highest cost value of all colonial countries, l=1,2,…,Nim.Then, there must be at least one colonial country whose normalized cost and power are zero, which means it cannot be allocated to a colony, making it difficult to carry out subsequent assimilation revolutions, affecting the search efficiency of ICA. Equation (20) redefines the normalized cost to effectively avoid normalized cost and power of zero, so that all colonial countries can be allocated to a certain number of colonies,(20)Ck=2×maxlcl−ck.


### 5.2.2. Adaptive Deviation Angle

In the basic ICA, the deviation angleθ is uniformly distributed as θ∼U−φ,φ, where usually φ=π/4. Since the deviation angle is fixed, the algorithm will fall into a local search.Chaos is a stochastic motion state directly obtained by a deterministic equation and is a nonlinear phenomenon in nature. Logistic mapping is a classical chaos model with randomness and ergodicity, which is important in solving optimization problems. By introducing logistic mapping from chaos theory to the ICA and optimizing the deviation angle in the assimilation process, the phenomenon of precocity can be improved, as can the ability of colonies to seek the optimal global solution away from the optimal local solution. The expression of logistic mapping isxk+1=εxk1−xk.The definition of deviation angle is(21)θt+1=εθt1−θt.Set chaotic parametersε=0.4, θ∈0,1. In each iteration, the chaotic mutation mechanism produces a random function to realize the dynamic control of parameters.


### 5.2.3. Imperial Division Mechanism

There are two ways to create new states: assimilation and revolution. However, both are carried out within an empire. If the colonial countries have little or no change in the larger algebra, then this will lead to the increase of similarity and decrease of population diversity in the empire and eventually the premature convergence of ICA.We propose an imperial division strategy, which is a new way to create a new empire and set the rate of division for the current empire. When the split rate is greater than the set threshold, a colony becomes a new colonial country and sees a certain number of colonies allocated by the empire to form a new empire. The split rate can be expressed as(22)SPk=η⋅NCkN⋅exptT⋅zt,(23)zt=1,Nnow<Nim,0,other,where Nnow is the current number of empires, T is the total number of iterations of the algorithm, and η is the regulator, which is usually 0.36. In this paper, we set both the splitting threshold and splitting ratio to 0.5.


## 5.2.1. New Definition of Empire Cost

In the initial stage of an empire, it is necessary to divide the colonial countriesNim and colonies Ncol according to the power of the state. The colonial countries and all their colonies constitute an empire. The normalized cost Ck and power of colonial countries pk are(19)Ck=maxlcl−ck,pk=Ck∑l=1Nimcl,where maxlcl is the highest cost value of all colonial countries, l=1,2,…,Nim.Then, there must be at least one colonial country whose normalized cost and power are zero, which means it cannot be allocated to a colony, making it difficult to carry out subsequent assimilation revolutions, affecting the search efficiency of ICA. Equation (20) redefines the normalized cost to effectively avoid normalized cost and power of zero, so that all colonial countries can be allocated to a certain number of colonies,(20)Ck=2×maxlcl−ck.


## 5.2.2. Adaptive Deviation Angle

In the basic ICA, the deviation angleθ is uniformly distributed as θ∼U−φ,φ, where usually φ=π/4. Since the deviation angle is fixed, the algorithm will fall into a local search.Chaos is a stochastic motion state directly obtained by a deterministic equation and is a nonlinear phenomenon in nature. Logistic mapping is a classical chaos model with randomness and ergodicity, which is important in solving optimization problems. By introducing logistic mapping from chaos theory to the ICA and optimizing the deviation angle in the assimilation process, the phenomenon of precocity can be improved, as can the ability of colonies to seek the optimal global solution away from the optimal local solution. The expression of logistic mapping isxk+1=εxk1−xk.The definition of deviation angle is(21)θt+1=εθt1−θt.Set chaotic parametersε=0.4, θ∈0,1. In each iteration, the chaotic mutation mechanism produces a random function to realize the dynamic control of parameters.


## 5.2.3. Imperial Division Mechanism

There are two ways to create new states: assimilation and revolution. However, both are carried out within an empire. If the colonial countries have little or no change in the larger algebra, then this will lead to the increase of similarity and decrease of population diversity in the empire and eventually the premature convergence of ICA.We propose an imperial division strategy, which is a new way to create a new empire and set the rate of division for the current empire. When the split rate is greater than the set threshold, a colony becomes a new colonial country and sees a certain number of colonies allocated by the empire to form a new empire. The split rate can be expressed as(22)SPk=η⋅NCkN⋅exptT⋅zt,(23)zt=1,Nnow<Nim,0,other,where Nnow is the current number of empires, T is the total number of iterations of the algorithm, and η is the regulator, which is usually 0.36. In this paper, we set both the splitting threshold and splitting ratio to 0.5.


## 5.3. Cross-Domain  SFC  Deployment Algorithms

To complete SFC deployment, the deployment path is found through the mapping relationship between VNF nodes and boundary nodes. To meet the needs of network users and operators, the optimal mapping relationship is needed to optimize resource consumption cost and load balancing degree. Given the incompatibility of these two optimization goals, we combine the bargaining game process and optimization mechanism of the ICA to obtain the Pareto optimal solution and the best node mapping matrix. The process of cross-domain service chain deployment is shown in Algorithm1.Algorithm 1: CDSBG.
Input: abstract networkGp=Np,Lp;SFC=f1,f2,…,fq;Resource capacity of SDN domainrs0;Maximum number of iterationsT;ICA populationN;Number of empiresNim.Output: node mapping matrixX(1)
Initialize the number of empires, maximum number of iterations, and related parametersθ and RPt.(2)
Initial feasible policies are randomly generated in all policy sets. Initialize country locationxi and country cost ci.(3)
Initialize BATNAμCost andμLBD.(4)
Initial empire building. Calculate the country's normalized costs and power, and generate ASD empires.(5)
Carry out assimilation and revolutionary operations on each imperial colony, and judge whether the empire will split according to equation (22). If so, split operations will be carried out; otherwise, the next step will be taken.(6)
Imperial competition stage. Transfer the worst colony of the worst empire to the best empire.(7)
The empire dies. Check if an empire has no colonies. If so, delete the empire.(8)
Determine if there is only one empire; if so, update BATNA according to formulas (17) and (18); otherwise, loop through steps 5–7.(9)
Determine whether the number of iterations has reachedT. If conditions are met, then the loop is closed, and the optimal imperial position is output. Otherwise, proceed to step 5.


## 6. Simulation Experiment

### 6.1. Experimental Environment

In this paper, the setting of the underlying physical network refers to Sun et al. [16]. A multidomain network is constructed by forming several SDN domains and connecting them. GT-ITM [29] is used to generate the physical network topology in each domain. The number of physical nodes in a domain is a random number in (5, 30), the number of boundary nodes is a random number in (2, 5), and the nodes in a domain are connected with probability 0.5. Two boundary nodes in different domains are connected with a probability of 0.5 to ensure at least one connection path between any two domains. To verify the extensibility of the algorithm, physical network topologies with different scales are set as T1, T2, and T3, which, respectively, own 4, 6, and 8 SDN domains. Within an SDN domain, resource capacity and link bandwidth resources of physical nodes are distributed as U100,200, and resource cost per unit node and resource cost per unit bandwidth are distributed as U0.2,0.8. The bandwidth resource capacity and unit cost of the interdomain link in the entire multidomain network are distributed as U2000,4000 and U1,4, respectively. In the experiment, it is assumed that the arrival of an SFC request follows a Poisson distribution, and these have different mean values depending on the network size. The Poisson distribution parameters are 60, 120, and 180, respectively, for T1, T2, and T3. For accuracy, we generate 1000 SFC requests of different lengths, deploy them to the underlying physical network, and compute the average.The experiment compares the following methods:(1)
CDSBG: it is the cross-domain SFC deployment strategy based on the bargaining game proposed in this paper.(2)
EE-SFCO-MD: it is a centralized cross-domain SFC mapping method based on energy consumption [17]. The physical network is abstracted into smaller topologies by point aggregation, and all domain-level paths of source and destination are constructed. The SFC request is segmented and mapped to the corresponding domain. The mapping scheme with the lowest energy consumption is obtained through bidding between domain-level paths.(3)
H-algorithm: a centralized cross-domain SFC deployment method [18] minimizes the total number of SDN domains occupied by SFC and the cost of network resource consumption, transforms the SFC cross-domain problem to an optimization problem, and proposes a heuristic algorithm to solve it.None of the three strategies involve intradomain mapping methods. To compare the pros and cons of domain-level partitioning algorithms, the same intradomain mapping method is required. Intradomain mapping adopts a mapping goal [30] to minimize the underlying network resource overhead.The experiment includes the following indicators.(1)
Average mapping overhead of all SFC requests under a certain SFC request length: The average mapping cost is(24)COSTA¯=COSTACOSTM,whereCOSTA and COSTM are, respectively, the mapping overhead and maximum mapping overhead of a certain strategy under a certain request length.(2)
Average mapping time: it is the average time it takes for multiple SFCs to arrive from the request to complete the mapping in a period of time.(3)
Mapping success rate: it is the ratio of the number of successfully mapped SFC requests to the total number of SFCs that arrive in a period of time.(4)
Interdomain load balancing degree: the load coefficients of all SDN domains are calculated by equation (6). The closer the value is to 1, the more balanced the load is between SDN domains.


### 6.2. Experimental Results and Analysis

#### 6.2.1. Performance of CDSBG Strategy

We adopt the physical networkT1 for experimental simulation and calculate the relevant performance indices to compare the performance of the three strategies [15].1. Average Mapping Overhead. Figure 3 shows the average mapping overhead of each strategy. The average mapping overhead of the three strategies increases with the SFC request length. The strategies of EE-SFCO-MD and the H-algorithm show a higher average mapping overhead when the SFC length is small (the average mapping overhead is about 40%). With the increase of SFC length, the average mapping overhead of the H-algorithm is higher than that of EE-SFCO-MD. This is because the EE-SFCO-MD strategy constructs the path first, and then the SFC is segmented and mapped. The change of the SFC length will not cause the path to change significantly, so the average mapping overhead of EE-SFCO-MD has a small growth trend. Although the H-algorithm strategy considers resource consumption when deploying paths, it does not consider the resource consumption of interdomain links. In a multi-SDN network, the cost of interdomain links is higher, which increases the average mapping overhead. The mapping overhead of CDSBG is the least, at no more than 25%, because this strategy focuses on resource consumption cost so as to minimize the overhead.Figure 3
Average mapping overhead for each strategy.2. Average Mapping Time. Figure 4 shows the average mapping times of each strategy, which all increase with the SFC request length. The average mapping time of the EE-SFCO-MD strategy is significantly higher than those of the other two strategies, and it linearly increases with the problem size. This is because the EE-SFCO-MD strategy must traverse all paths between SFC source points and destination points to find the path with the lowest energy consumption. Multiple bidding and redistribution are required in the SFC segment allocation to the SDN domain stage. Hence, the mapping time of SFC is relatively long. The average mapping time of the CDSBG and H-algorithm strategies is significantly less than that of the EE-SFCO-MD strategy, and the increase rate is low as the SFC request length increases. The main reason is that both carry out one segmentation and redistribution based on the solution path of the optimization problem. The CDSBG strategy uses an improved IC, and it constantly adjusts the search direction toward the optimal strategy to avoid falling into premature solutions, so it has a shorter average mapping time.Figure 4
Average mapping time of each strategy.3. Mapping Success Rate. Figure 5 shows the mapping success rate of each strategy. This is higher for the EE-SFCO-MD strategy than for the other two strategies, at the cost of a longer mapping time. The EE-SFCO-MD strategy requires traversal of all reachable paths between the SFC start and endpoints and determines the SFC request segmentation scheme through each SDN domain bidding segment to ensure that all VNFs are mapped to the SDN domain and increase the success rate of SFC deployment. The mapping success rate of the CDSBG strategy is higher than that of the H-algorithm strategy by about 5%–17.9%. This is because the former considers the load situation of the physical network when SFC is deployed, and the load-balanced network helps to improve the capacity to accommodate SFC. The latter minimizes the total number of SDN domains occupied by SFC as its optimization goal. Although there are few occupied SDN domains, the loads of some are too high, which is not favorable for subsequent SFC requests. Therefore, the CDSBG strategy has a high mapping success rate.Figure 5
The mapping success rate of each strategy.4. Interdomain Load Balancing Degree. Figure 6 shows the interdomain load balancing degree of each strategy. When the length of the SFC request is small, it is difficult to evenly deploy the VNF nodes to each SDN domain. Therefore, the interdomain load balance of each strategy is low. As the length of the SFC request increases, the interdomain load of each strategy tends to be balanced. However, these are reduced for the EE-SFCO-MD and H-algorithm strategies when the SFC is excessively long. The former strategy is to reduce energy consumption and make SFC fragments centrally deployed in the SDN domain. The latter aims to reduce the number of SDN domains occupied by SFC, which is bound to cause load imbalance. The CDSBG strategy considers the load situation of each SDN domain when deploying VNF nodes. When the ICA is used to solve the problem, the deployment plan that balances the load among the domains is preferred. Compared to the H-algorithm strategy, the CDSBG strategy occupies more SDN domains but achieves better network balance.Figure 6
Interdomain load balancing degree of each strategy.


#### 6.2.2. Extensibility of CDSBG Strategy

To evaluate the scalability of the CDSBG strategy, experimental simulations are performed on physical network topologies of different scalesT1,T2,T3, and the average mapping overhead, average mapping time, mapping success rate, and interdomain load balancing degree are measured. The physical network T1 experiment index value is used as the reference value, and the ratio between other network experiment index values and the reference value is calculated. As shown in Figure 7, the expansion of physical network size, average mapping time, mapping success rate, and interdomain load balancing degree all increase. However, the increase of average mapping time is small because larger network resources are more abundant, and it is easier to find the optimal deployment path in SFC deployment. For this reason, the interdomain load of the physical network is more balanced. Due to the expansion of the network scale, VNF nodes can be deployed in fewer SDN domains, and the number of interdomain links connecting them is reduced. Therefore, even if the scale is expanded, the average mapping overhead decreases.Figure 7
Extensibility of CDSBG strategy.


## 6.1. Experimental Environment

In this paper, the setting of the underlying physical network refers to Sun et al. [16]. A multidomain network is constructed by forming several SDN domains and connecting them. GT-ITM [29] is used to generate the physical network topology in each domain. The number of physical nodes in a domain is a random number in (5, 30), the number of boundary nodes is a random number in (2, 5), and the nodes in a domain are connected with probability 0.5. Two boundary nodes in different domains are connected with a probability of 0.5 to ensure at least one connection path between any two domains. To verify the extensibility of the algorithm, physical network topologies with different scales are set as T1, T2, and T3, which, respectively, own 4, 6, and 8 SDN domains. Within an SDN domain, resource capacity and link bandwidth resources of physical nodes are distributed as U100,200, and resource cost per unit node and resource cost per unit bandwidth are distributed as U0.2,0.8. The bandwidth resource capacity and unit cost of the interdomain link in the entire multidomain network are distributed as U2000,4000 and U1,4, respectively. In the experiment, it is assumed that the arrival of an SFC request follows a Poisson distribution, and these have different mean values depending on the network size. The Poisson distribution parameters are 60, 120, and 180, respectively, for T1, T2, and T3. For accuracy, we generate 1000 SFC requests of different lengths, deploy them to the underlying physical network, and compute the average.The experiment compares the following methods:(1)
CDSBG: it is the cross-domain SFC deployment strategy based on the bargaining game proposed in this paper.(2)
EE-SFCO-MD: it is a centralized cross-domain SFC mapping method based on energy consumption [17]. The physical network is abstracted into smaller topologies by point aggregation, and all domain-level paths of source and destination are constructed. The SFC request is segmented and mapped to the corresponding domain. The mapping scheme with the lowest energy consumption is obtained through bidding between domain-level paths.(3)
H-algorithm: a centralized cross-domain SFC deployment method [18] minimizes the total number of SDN domains occupied by SFC and the cost of network resource consumption, transforms the SFC cross-domain problem to an optimization problem, and proposes a heuristic algorithm to solve it.None of the three strategies involve intradomain mapping methods. To compare the pros and cons of domain-level partitioning algorithms, the same intradomain mapping method is required. Intradomain mapping adopts a mapping goal [30] to minimize the underlying network resource overhead.The experiment includes the following indicators.(1)
Average mapping overhead of all SFC requests under a certain SFC request length: The average mapping cost is(24)COSTA¯=COSTACOSTM,whereCOSTA and COSTM are, respectively, the mapping overhead and maximum mapping overhead of a certain strategy under a certain request length.(2)
Average mapping time: it is the average time it takes for multiple SFCs to arrive from the request to complete the mapping in a period of time.(3)
Mapping success rate: it is the ratio of the number of successfully mapped SFC requests to the total number of SFCs that arrive in a period of time.(4)
Interdomain load balancing degree: the load coefficients of all SDN domains are calculated by equation (6). The closer the value is to 1, the more balanced the load is between SDN domains.


## 6.2. Experimental Results and Analysis

### 6.2.1. Performance of CDSBG Strategy

We adopt the physical networkT1 for experimental simulation and calculate the relevant performance indices to compare the performance of the three strategies [15].1. Average Mapping Overhead. Figure 3 shows the average mapping overhead of each strategy. The average mapping overhead of the three strategies increases with the SFC request length. The strategies of EE-SFCO-MD and the H-algorithm show a higher average mapping overhead when the SFC length is small (the average mapping overhead is about 40%). With the increase of SFC length, the average mapping overhead of the H-algorithm is higher than that of EE-SFCO-MD. This is because the EE-SFCO-MD strategy constructs the path first, and then the SFC is segmented and mapped. The change of the SFC length will not cause the path to change significantly, so the average mapping overhead of EE-SFCO-MD has a small growth trend. Although the H-algorithm strategy considers resource consumption when deploying paths, it does not consider the resource consumption of interdomain links. In a multi-SDN network, the cost of interdomain links is higher, which increases the average mapping overhead. The mapping overhead of CDSBG is the least, at no more than 25%, because this strategy focuses on resource consumption cost so as to minimize the overhead.Figure 3
Average mapping overhead for each strategy.2. Average Mapping Time. Figure 4 shows the average mapping times of each strategy, which all increase with the SFC request length. The average mapping time of the EE-SFCO-MD strategy is significantly higher than those of the other two strategies, and it linearly increases with the problem size. This is because the EE-SFCO-MD strategy must traverse all paths between SFC source points and destination points to find the path with the lowest energy consumption. Multiple bidding and redistribution are required in the SFC segment allocation to the SDN domain stage. Hence, the mapping time of SFC is relatively long. The average mapping time of the CDSBG and H-algorithm strategies is significantly less than that of the EE-SFCO-MD strategy, and the increase rate is low as the SFC request length increases. The main reason is that both carry out one segmentation and redistribution based on the solution path of the optimization problem. The CDSBG strategy uses an improved IC, and it constantly adjusts the search direction toward the optimal strategy to avoid falling into premature solutions, so it has a shorter average mapping time.Figure 4
Average mapping time of each strategy.3. Mapping Success Rate. Figure 5 shows the mapping success rate of each strategy. This is higher for the EE-SFCO-MD strategy than for the other two strategies, at the cost of a longer mapping time. The EE-SFCO-MD strategy requires traversal of all reachable paths between the SFC start and endpoints and determines the SFC request segmentation scheme through each SDN domain bidding segment to ensure that all VNFs are mapped to the SDN domain and increase the success rate of SFC deployment. The mapping success rate of the CDSBG strategy is higher than that of the H-algorithm strategy by about 5%–17.9%. This is because the former considers the load situation of the physical network when SFC is deployed, and the load-balanced network helps to improve the capacity to accommodate SFC. The latter minimizes the total number of SDN domains occupied by SFC as its optimization goal. Although there are few occupied SDN domains, the loads of some are too high, which is not favorable for subsequent SFC requests. Therefore, the CDSBG strategy has a high mapping success rate.Figure 5
The mapping success rate of each strategy.4. Interdomain Load Balancing Degree. Figure 6 shows the interdomain load balancing degree of each strategy. When the length of the SFC request is small, it is difficult to evenly deploy the VNF nodes to each SDN domain. Therefore, the interdomain load balance of each strategy is low. As the length of the SFC request increases, the interdomain load of each strategy tends to be balanced. However, these are reduced for the EE-SFCO-MD and H-algorithm strategies when the SFC is excessively long. The former strategy is to reduce energy consumption and make SFC fragments centrally deployed in the SDN domain. The latter aims to reduce the number of SDN domains occupied by SFC, which is bound to cause load imbalance. The CDSBG strategy considers the load situation of each SDN domain when deploying VNF nodes. When the ICA is used to solve the problem, the deployment plan that balances the load among the domains is preferred. Compared to the H-algorithm strategy, the CDSBG strategy occupies more SDN domains but achieves better network balance.Figure 6
Interdomain load balancing degree of each strategy.


### 6.2.2. Extensibility of CDSBG Strategy

To evaluate the scalability of the CDSBG strategy, experimental simulations are performed on physical network topologies of different scalesT1,T2,T3, and the average mapping overhead, average mapping time, mapping success rate, and interdomain load balancing degree are measured. The physical network T1 experiment index value is used as the reference value, and the ratio between other network experiment index values and the reference value is calculated. As shown in Figure 7, the expansion of physical network size, average mapping time, mapping success rate, and interdomain load balancing degree all increase. However, the increase of average mapping time is small because larger network resources are more abundant, and it is easier to find the optimal deployment path in SFC deployment. For this reason, the interdomain load of the physical network is more balanced. Due to the expansion of the network scale, VNF nodes can be deployed in fewer SDN domains, and the number of interdomain links connecting them is reduced. Therefore, even if the scale is expanded, the average mapping overhead decreases.Figure 7
Extensibility of CDSBG strategy.


## 6.2.1. Performance of CDSBG Strategy

We adopt the physical networkT1 for experimental simulation and calculate the relevant performance indices to compare the performance of the three strategies [15].1. Average Mapping Overhead. Figure 3 shows the average mapping overhead of each strategy. The average mapping overhead of the three strategies increases with the SFC request length. The strategies of EE-SFCO-MD and the H-algorithm show a higher average mapping overhead when the SFC length is small (the average mapping overhead is about 40%). With the increase of SFC length, the average mapping overhead of the H-algorithm is higher than that of EE-SFCO-MD. This is because the EE-SFCO-MD strategy constructs the path first, and then the SFC is segmented and mapped. The change of the SFC length will not cause the path to change significantly, so the average mapping overhead of EE-SFCO-MD has a small growth trend. Although the H-algorithm strategy considers resource consumption when deploying paths, it does not consider the resource consumption of interdomain links. In a multi-SDN network, the cost of interdomain links is higher, which increases the average mapping overhead. The mapping overhead of CDSBG is the least, at no more than 25%, because this strategy focuses on resource consumption cost so as to minimize the overhead.Figure 3
Average mapping overhead for each strategy.2. Average Mapping Time. Figure 4 shows the average mapping times of each strategy, which all increase with the SFC request length. The average mapping time of the EE-SFCO-MD strategy is significantly higher than those of the other two strategies, and it linearly increases with the problem size. This is because the EE-SFCO-MD strategy must traverse all paths between SFC source points and destination points to find the path with the lowest energy consumption. Multiple bidding and redistribution are required in the SFC segment allocation to the SDN domain stage. Hence, the mapping time of SFC is relatively long. The average mapping time of the CDSBG and H-algorithm strategies is significantly less than that of the EE-SFCO-MD strategy, and the increase rate is low as the SFC request length increases. The main reason is that both carry out one segmentation and redistribution based on the solution path of the optimization problem. The CDSBG strategy uses an improved IC, and it constantly adjusts the search direction toward the optimal strategy to avoid falling into premature solutions, so it has a shorter average mapping time.Figure 4
Average mapping time of each strategy.3. Mapping Success Rate. Figure 5 shows the mapping success rate of each strategy. This is higher for the EE-SFCO-MD strategy than for the other two strategies, at the cost of a longer mapping time. The EE-SFCO-MD strategy requires traversal of all reachable paths between the SFC start and endpoints and determines the SFC request segmentation scheme through each SDN domain bidding segment to ensure that all VNFs are mapped to the SDN domain and increase the success rate of SFC deployment. The mapping success rate of the CDSBG strategy is higher than that of the H-algorithm strategy by about 5%–17.9%. This is because the former considers the load situation of the physical network when SFC is deployed, and the load-balanced network helps to improve the capacity to accommodate SFC. The latter minimizes the total number of SDN domains occupied by SFC as its optimization goal. Although there are few occupied SDN domains, the loads of some are too high, which is not favorable for subsequent SFC requests. Therefore, the CDSBG strategy has a high mapping success rate.Figure 5
The mapping success rate of each strategy.4. Interdomain Load Balancing Degree. Figure 6 shows the interdomain load balancing degree of each strategy. When the length of the SFC request is small, it is difficult to evenly deploy the VNF nodes to each SDN domain. Therefore, the interdomain load balance of each strategy is low. As the length of the SFC request increases, the interdomain load of each strategy tends to be balanced. However, these are reduced for the EE-SFCO-MD and H-algorithm strategies when the SFC is excessively long. The former strategy is to reduce energy consumption and make SFC fragments centrally deployed in the SDN domain. The latter aims to reduce the number of SDN domains occupied by SFC, which is bound to cause load imbalance. The CDSBG strategy considers the load situation of each SDN domain when deploying VNF nodes. When the ICA is used to solve the problem, the deployment plan that balances the load among the domains is preferred. Compared to the H-algorithm strategy, the CDSBG strategy occupies more SDN domains but achieves better network balance.Figure 6
Interdomain load balancing degree of each strategy.


## 6.2.2. Extensibility of CDSBG Strategy

To evaluate the scalability of the CDSBG strategy, experimental simulations are performed on physical network topologies of different scalesT1,T2,T3, and the average mapping overhead, average mapping time, mapping success rate, and interdomain load balancing degree are measured. The physical network T1 experiment index value is used as the reference value, and the ratio between other network experiment index values and the reference value is calculated. As shown in Figure 7, the expansion of physical network size, average mapping time, mapping success rate, and interdomain load balancing degree all increase. However, the increase of average mapping time is small because larger network resources are more abundant, and it is easier to find the optimal deployment path in SFC deployment. For this reason, the interdomain load of the physical network is more balanced. Due to the expansion of the network scale, VNF nodes can be deployed in fewer SDN domains, and the number of interdomain links connecting them is reduced. Therefore, even if the scale is expanded, the average mapping overhead decreases.Figure 7
Extensibility of CDSBG strategy.


## 7. Conclusions

We studied the deployment of the SFC in a cross-domain environment and proposed a multiobjective optimization model considering resource consumption cost and load balancing degree. Given their cooperation-competition relationship, a bargaining game model was introduced to realize the equity between the two contradictory goals of resource consumption cost and load balancing degree. Simulation results showed that the proposed strategy has better optimization effects in terms of average mapping cost, average mapping time, mapping success rate, and interdomain load balancing. The proposed scheme was to carry out experiments in a complete network environment. The next step is to study how to reestablish the connection path for SFC in the case of interdomain link failure.



---

*Source: 6669917-2021-01-22.xml*