Dynamic Service Function Chain Deployment in NFV-enabled Offshore Edge Computing Networks

Authors: yongchun  han
bin  lin
chaoyue  zhang
qiaodan  wang
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-08-16 03:34:41

Abstract: Network function virtualization (NFV) has gained significant attention as an important paradigm in network service provisioning. In an NFV environment, network services are provided flexibly by deploying service function chains (SFCs) dynamically, which consist of multiple virtual network functions (VNFs) arranged in predefined order. In this paper, we formulate the dynamic SFC deployment optimization (DSDO) problem in the NFV-enabled offshore edge computing network, by jointly optimizing VNF deployment and routing to maximize the service acceptance rate. An SFC deployment scheme, named betweenness centrality and resource availability based dynamic SFC deployment (BR-DSD) scheme is proposed to solve the optimization problem. The proposed BR-DSD scheme aims to allocate resources for SFC deployment by considering both network resource availability and betweenness centrality. Simulation results demonstrate that the proposed BR-DSD scheme outperforms baseline schemes in terms of service acceptance rate.

Main paper: 
 i. introduction: 
 The rapid growth of offshore activities, such as fishing, shipping, tourism, has driven a surge in demand for advanced maritime applications. These applications, equipped with capabilities including image processing, visual enhancement, automatic navigation, and other supporting tools, aim to provide diverse and personalized network services for offshore users. However, these applications require substantial computation resources, posing a challenge for offshore users with limited computation capacity. To address this challenge, edge computing has emerged as a promising solution, offering ample computation resources in close proximity to offshore users, which enables efficient execution of computation tasks on edge servers.Conventional edge computing networks are typically customized for specific missions, which limits their adaptability to diverse services. To addresses this, Network function virtualization (NFV) emerges as a crucial paradigm in network service provisioning. NFV decouples network functions from dedicated hardware and virtualizes them into software components, known as virtual network functions (VNFs). This allows a single physical network to support multiple services simultaneously, enhancing service delivery flexibility and network resource utilization. Within the NFV environment, services are provided dynamically via service function chains (SFCs), which consist of multiple VNFs arranged in a predefined order. However, deploying SFCs in edge networks faces a significant challenge: limited network resources.The SFC deployment problem has drawn significant attention from researchers. The authors in [1] separate the flows into different kinds based on resource preferences, and define relative cost to balance the resource consumption and route heterogeneous traffic at flow level differentially in SDN and NFV-enabled network aiming to minimize the resource consumption costs of flows with SFC requests. The authors in [2] propose a VNF resource allocation scheme based on contextaware grouping technology that enables groups (based on the geographic context of users, such as location and velocity) to compute the optimal number of clusters to minimize the end-toend delay of network services. The authors in [3] accurately measure resource consumption on edge devices considering both CPU consumption by computing and by communicating between consecutive network functions in a chain on edge devices. The authors in [4] consider sharing the allocated computing capacity of a host by VNF resizing and priority queuing to minimize the service deployment cost. In [5] , the subchain-aware NFV service placement optimization problem is investigated that accounts for the configuration cost for stitching together reused network functions to an SFC and strives to reuse existing subchains of consecutive network functions (with already deployed SFC traffic steering).While above studies primarily focus on efficiently allocating network resources for deploying SFCs, they overlook the significance of key links and nodes. In reality, these key components play crucial intermediary roles within networks, naturally experiencing higher resource consumption rates. Congestion at these points can severely hinder service acceptance rates. Therefore, considering the impact of key links and nodes is crucial for improving the service acceptance rate. It is worth mentioning that the authors in [6] determine the VNF placement using a metric based on betweenness centrality and server failure rate, but without considering network resources. Furthermore, offshore edge computing networks suffer from even more severe resource scarcity compared to land-based edge computing, especially in terms of bandwidth resources, due to the changeable maritime environment. Therefore, when deploying SFCs in offshore edge networks, it is imperative to consider bandwidth resources, as opposed to some literatures that assume ample bandwidth resources by assuming optical cable connections between edge servers.Network service requests can be classified into offline and online requests. Offline requests are provided beforehand, while online requests are assumed to arrive sequentially without prior knowledge of future requests [7] . In edge networks, requests frequently join and leave due to user mobility. Therefore, the dynamic nature of network services in the edge networks must be taken into consideration.In this paper, we investigate the dynamic SFC deployment optimization (DSDO) problem in an NFV-enabled offshore edge computing network, by jointly optimizing VNF deployment and routing to maximize the service acceptance rate. Given the NP-hard nature of this problem, we propose a betweenness centrality and resource availability based dynamic SFC deployment (BR-DSD) scheme to solve the optimization problem. The proposed BR-DSD scheme aims to allocate resources for SFC deployment by considering both network resource availability and betweenness centrality, mitigating the potential adverse impact of current services on subsequent ones. Our key contributions include:• We propose the DSDO problem in the offshore edge computing network, by jointly optimizing the VNF deployment and routing aiming at maximizing the service acceptance rate.• Due to the NP-hard, we propose the BR-DSD scheme to solve it. To enhance the service acceptance rate, we consider both the network resources and network betweenness centrality to reduce the potential adverse impact of the current service on subsequent ones in BR-DSD scheme. Simulation results show that BR-DSD scheme can efficiently solve the DSDO problem and obtain high performance in terms of the service acceptance rate.In this section, we model the system, the network and network services in detail. Then we elaborate the constraints on SFC deployment and formulate the DSDO problem.In this paper, we consider an offshore edge computing system enabled by NFV, which consists of a High Altitude Platform (HAP) equipped with a Software-Defined Networking controller, Intelligent Buoys (IBs), and intelligent ships (ISs), as illustrated in Fig. 1 . The HAP serves as a control center with computation and communication capabilities, in order to sense network state information, orchestrate VNFs, and make SFC deployment decisions. Each IB possesses computation and communication capabilities providing resources for SFCs.In the offshore edge computing system, the SFC deployment process includes three steps after the HAP receiving a service request (SR). First, the HAP determines the optimal source node and destination node based on locations of ISs, the service types and network conditions. Second, it constructs the SFC tailored to the SR. Finally, the HAP formulates the SFC deployment scheme, that is, VNFs placement scheme and the routing scheme, providing efficient and effective service delivery. The offshore edge computing network is modeled as an undirected graph ( ) We assume that the hardware resources of each IB have been virtualized using lightweight container-based technology [8] , enabling flexible allocation and sharing of resources. This virtualization approach facilitates the creation of VNFs with arbitrary capacity on demand, owing to the fine-grained resource allocation capabilities of containers., G V E = ,To accommodate the dynamic nature of network states and SRs, we discretize a continuous period into time slots of equal length, denoted as12 , , , T T t t t =. Assume that SRs arrive and depart randomly but processed in a first-come-first-serve manner at the start of each time slot, whose set is defined as   Rr = . R represents the total number of SRs in a given period. At the conclusion of each time slot, the HAP checks all alive services to identify those have reached the end of lifetime. For completed services, the corresponding SFCs are terminated and the network resources are released for subsequent services. EQUATIONThe binary variable r p y represents whether pathEQUATIONDrawing from [3] , for an accurate assessment of CPU consumption, it is crucial to consider not only the computation consumed CPU but also the communication between consecutive VNFs consumed CPU in an SFC. The communication consumed CPU by VNFEQUATIONwhere in f p and out f p are the ingress traffic volume and egress traffic volume of VNFr fS  , respectively. The computation consumed CPU is comp in f f f cp  = (4)where f  is the ratio of CPU consumed by computation and by communication.Then we elaborate the constraints when deploying SFCs.1) VNF Deployment Constraints: For SR rR  , each VNF are assumed to be deployed on only one network node, i.e., , , 1, , .EQUATION,r i r i r f f S +  , if VNF , ri f is deployed on node vV  of path pand its subsequent VNF ,1 ri f + is successfully deployed on a node uV  , then node u must be on path p positioned subsequent to node v within the sequence of nodes consisting of path p. The constraint is formally denoted asEQUATIONi r i ri ff v v p u r i r r i r f u up u V v p x x r R f S f S x   + + +   = =       =  (6)where vEQUATION3) Computation Capacity Constraint: The aggregate consumed CPU on node vV  must not exceed the total available CPU resources on the node v , i.e.,EQUATIONwhere Due to the shared nature of resources among multiple services within the offshore edge computing network and given the scarce CPU and bandwidth resources available, it is not feasible to guarantee the successful acceptance of all SRs. We introduce a binary variable r z , i.e., , ,( )   arrive complete alive | rr R tEQUATIONIn this paper, our objective is to maximize the dynamic service acceptance rate. Consequently, the problem can be formulated as follows: 1)-( 10)    , , s.t.(EQUATIONTo address the DSDO problem, we propose the BR-DSD scheme. The primary objective of this scheme is to maximize the service acceptance rate. To achieve this goal, we devise comprehensive assessment criterion that takes into account three key factors: CPU resources, bandwidth resources, and network betweenness centrality. This criterion is employed to score a set of SFC deployment strategy with the aim of mitigating the potential impact of the current service deployment on subsequent services.Input: Offshore edge computing network ( ) The DLDP algorithm is a variant of the traditional Depth-First Search (DFS) algorithm, combining the DFS strategy with a depth constraint. It is designed to find paths from source node to destination node. Similar to DFS, the DLDP algorithm explores the network to find paths from the source node to the destination node. Due to the limit on the depth of the search, the algorithm focuses solely on paths that match the specific length, effectively avoiding returning the repeated paths when the algorithm is invoked multiple times. The DLDP algorithm first create an empty stack to save the search information as a tuple ( ) , , node depth path . Then ( ) , 0, [ ] rr ss is pushed into this stack. The algorithm pops the head element in the stack and proceeds to explore the neighboring nodes, keeping track of the current path and its depth at each step. Whenever the algorithm reaches a node, it checks whether the node is the destination and whether the current depth matches the specified limit. If both conditions are satisfied, the path is added to set r P . The DLDP algorithm terminates when all possible paths from the source node to the destination node within the specified depth limit are explored and recorded. At the end of algorithm, the set of paths r P are returned. The BRVD algorithm is designed to determine the optimal routing path and VNFs deployment locations along this path. Its primary objective is to allocate resources properly and thereby mitigate the potential impact of the current service on subsequent services. The core idea behind this algorithm is to deploy VNFs on less critical but well-resourced intermediate nodes along a less critical but adequate link. This strategy is adopted due to the inherently faster resource consumption rates on key links and nodes, which make them prone to network congestion and can subsequently lead to services acceptance failure. Therefore, it is imperative to deploy SFC on less critical links nodes that possess sufficient resources, while ensuring that the alive SFCs remain undisrupted. This strategy minimizes the potential for network congestion and thereby enhances the service acceptance rate., G V E = ,Betweenness is a centrality graph metric with global significance that can be applied to both nodes and links [9] . Node betweenness is defined as the number of shortest paths that pass through a node, while link betweenness is similarly defined as the number of shortest paths that pass through a link. Betweenness reflects the positional importance of a node or link in the network. Nodes or links with high betweenness typically play more important intermediary roles as bridges in the network, connecting different parts and being crucial for network connectivity and information flow. Consequently, we use betweenness centrality to measure the importance of a node or a link. Furthermore, we design an assessment criterion to score the routing path and VNF deployment scheme by combining computing resources, bandwidth resources, and betweenness centrality. This ensures a comprehensive evaluation that aligns with the objectives of the BRVD algorithm.We refer to [10] to calculate betweenness of link and node. The score of routing path p is calculated by EQUATIONEQUATIONEQUATION is a weight factor that determines the relative importance of the routing path and the VNFs deployment in the overall assessment.Before specifying the BRVD algorithm, it is imperative to clarify two fundamental concepts: Structured SFC (S-SFC) and Reconstructed Routing Path (R-RP). The S-SFC is derived from the linear SFC by segmenting the chain into distinct subchains, while preserving the original order of VNFs within the chain. A sub-chain represents a consecutive sequence of VNFs within the chain, as depicted in Fig. 2 . In the context of a routing path, nodes designated for deploying VNFs are called deployable nodes. An R-RP is a path that shares the same nodes as the original routing path, except that some deployable nodes are solely utilized for data forwarding, as exemplified in Fig. 3 . The BRVD algorithm initiates by comparing the length of the SFC, i.e., r S , with the number of deployable nodes, i.e., 2 p -, in the routing path. If the length of the SFC is greater than or equal to the number of deployable nodes in the routing path, i.e., 2 r Sp -, the following steps are executed. Initially, the original SFC is structured to obtain a set of S-SFCs, each of which has a length equivalent to the number of deployable nodes in the routing path. Subsequently, the subchains within each S-SFC are sequentially deployed onto the deployable nodes of the routing path. Furthermore, VNF deployment schemes that fail to meet the CPU resource constraints are excluded. Ultimately, the optimal SFC deployment scheme is selected based on equation (13).Conversely, if the length of the SFC is less than the number of deployable nodes in the routing path, the algorithm constructs routing paths with a length equal to that of the SFC. VNFs are then sequentially deployed onto these R-RPs. Similar to the previous case, VNF deployment schemes are filtered, and the optimal SFC deployment scheme is selected and returned.To evaluate the performance of the proposed algorithm in the offshore edge computing network, we developed a simulator using Python. The topology of the offshore edge computing network was generated using the Python package NetworkX 3.2.1, consisting of 10 nodes and 17 links, i.e, 10, 17.The nodes are randomly distributed in an offshore environment. An edge ( ), e u v =indicates a wireless communication link between node u and v with a bandwidth capacity of 15 megabits per second (Mbps). We assume that the bandwidth consumption remains constant as the flow traverses VNF instances, and the traffic rate along each link of the routing path does not fluctuate during the service's lifetime. Each node has a CPU capacity of 100 Mbps.In the offshore edge computing network, 10 different types of VNFs are offered, i.e.,   We compare the performance of our proposed scheme with two baseline schemes: Resource Balanced Dynamic SFC Deployment (RB-DSD) scheme and the Resource Greedy Dynamic SFC Deployment (RG-DSD) scheme. In the RB-DSD scheme, each VNF within an SFC is deployed on one node along the shortest routing path with the aim of achieving resource balance by distributing the VNFs on multiple nodes. Conversely, in the RG-DSD scheme, all VNFs within an SFC are deployed onto a single node with the maximum CPU resources along the shortest routing path, in order to minimize bandwidth and CPU resources consumption. Fig. 4 depicts the dynamic service acceptance rate across each time slot. Across all three schemes, the service acceptance rate exhibits minor fluctuations over time while maintaining overall stability. Notably, our proposed scheme demonstrates superiority over the other two, with the most stable dynamic acceptance rate. This indicates that our scheme not only effectively enhances the service acceptance rate but also exhibits better adaptability to dynamic changes in services. Fig. 5 illustrates the relationship between the service acceptance rate and the average number of SRs in each time slot. As the number of service requests increases, the service acceptance rate gradually decreases for all three schemes. This decline can be attributed to the limited bandwidth and computation resources, which constrain the capacity to accommodate a larger number of services. Furthermore, it is evident that the proposed BR-DSD scheme outperforms the other two schemes. The superiority of our proposed scheme can be attributed to its dynamic deployment of SFCs based on the remaining network resources and the network topology. Specifically, our scheme prioritizes deploying VNFs on less critical nodes with ample computation resources, along less critical routing paths with ample bandwidth resources. This strategy effectively reduces the likelihood of congestion on key links and nodes, thereby mitigating the potential impact of the current service on future service requests and enhancing the overall service acceptance rate. In contrast, the RG-DSD scheme deploys SFCs on nodes with the maximum remaining resources along the shortest path, which reduces the immediate consumption of CPU and bandwidth resources but can easily lead to network congestion, subsequently consuming more network resources. On the other hand, the RB-DSD scheme achieves balanced resource consumption but does so at the cost of consuming more bandwidth resources and computation resources for communication.Fig. 6 depicts the relationship between the average acceptance rate and the length of SFC. As the length of SFC increases, the network experiences increased resource consumption, resulting in a decline in the service acceptance rate. Furthermore, as the length of the SFC request grows, the performance differences between the RB-DSD and RG-DSD schemes and the proposed BR-DSD scheme become pronounced. Specifically, the RB-DSD scheme attempts to balance CPU resources consumption across more nodes, requiring extra bandwidth and CPU resources to facilitate communication, which ultimately leads to a decline due to resource scarcity. On the other hand, the RG-DSD scheme concentrates resource demands on a single node in an attempt to conserve overall network resources, which makes it more susceptible to network congestion and ultimately leads to a decline in the service acceptance rate. Consequently, the superiority of the BR-DVD algorithm becomes increasingly evident as the length of the SFC request escalates. As the capacity of either bandwidth or CPU resources increases, the service acceptance rates of all three schemes initially rise and then stabilize at a level less than 1, indicating that both types of resources impact the service acceptance rate. Notably, as bandwidth resources increase, the rise in the service acceptance rate is more significant, suggesting that in our network, the service acceptance rate is more influenced by bandwidth resources than by CPU resources. V. CONCLUSION In this paper, we propose the dynamic SFC deployment optimization problem in an NFV-enabled offshore edge computing network. We jointly optimize the VNF deployment and routing with the objective of maximizing the service acceptance rate. Due to the NP-hard, we proposed the BR-DSD scheme to solve the optimization problem. The BR-DSD scheme considers both network resource availability and betweenness centrality when allocating resources for deploying SFCs. To be specific, for each service request, we employ the DLDP algorithm to find routing paths. Based on these paths, use the BRVD algorithm to determine the VNF placement strategy. Simulation results demonstrate that the proposed BR-DSD scheme outperforms the baseline schemes and achieves high performance in terms of the service acceptance rate. 
 
 Appendix:  



Reviews: review: title: title: This article is very interesting and a good one.
main_review: main_review: 1. The motivations should be further highlighted in the manuscript, e.g., what problems did the previous works exist? How to solve these problems? The authors may consider analyzing the problems of the previous works and how to address these problems with the proposed method. 
2. The literature review in the Introduction surveys some previous work on the solutions and methods to address the SFC deployment problem, while comparation among these methods which is the most important part is neglected.
3. The quality of language needs significant improvement, and professional editing may be necessary.
title: title: Review Comments for Manuscript No. 181
main_review: main_review: 1. There are some noticeable formatting errors in the manuscript. The authors should carefully review and ensure that the paper meets the IEEE conference paper standards.

2. The text size in Figure 1 is inconsistent with that in other figures and should be adjusted. Additionally, the references need further checking to ensure accuracy and consistency.

3. The Dynamic Service Function Chain (SFC) Deployment Optimization (DSDO) problem proposed by the authors—how does it differ from and what are the challenges compared to other studies in NFV-supported offshore edge computing networks? The authors should provide more detailed explanations to highlight these contrasts.

4. In modeling the DSDO problem, has the manuscript fully considered various constraints present in real-world network environments, such as latency and data throughput limitations? Are the model's assumptions reasonable and generalizable? Is the design of the BR-DSD approach, which simultaneously considers network resources and betweenness centrality, appropriate?

5. Has the implementation of the BR-DSD approach taken into account the complexity and scalability of the algorithm? Were potential challenges in practical deployment, such as real-time requirements and dynamic changes in network topology, considered?
title: title: Generally good, but there are still some problems.
main_review: main_review: The manuscript titled "Dynamic Service Function Chain Deployment in NFV-enabled Offshore Edge Computing Networks" addresses the challenge of deploying service function chains (SFCs) in offshore edge computing environments, which are enabled by Network Function Virtualization (NFV).  The authors formulate the dynamic SFC deployment optimization (DSDO) problem, focusing on maximizing the service acceptance rate by jointly optimizing the deployment of virtual network functions (VNFs) and routing.

Comments:

1.The manuscript introduces a novel approach by integrating betweenness centrality with resource availability for optimizing SFC deployment in offshore edge networks. However, the paper would benefit from a clearer comparison with existing methods to better highlight the unique advantages of the BR-DSD scheme.

2.While the manuscript is well-organized, some of the technical sections, particularly those describing the algorithms, could be made clearer. Simplifying these explanations or including additional diagrams could enhance reader comprehension.

3.The experimental results are convincing, but expanding the range of test scenarios, such as varying levels of network congestion or different service request patterns, would provide a more robust evaluation of the BR-DSD scheme's performance.