In this work, we consider the network slice composition problem for Service Function Chains (SFCs), which addresses the issue of allocating bandwidth and VNF resources in a way that guarantees the availability of the SFC while minimizing cost. For the purpose of satisfying the availability requirement of the SFC, we adapt a traffic-weighted availability model which ensures that the long-term fraction of traffic supported by the slice topology remains above a desired threshold. We propose a method for composing a single or multi-path slice topology and for properly dimensioning VNF replicas and bandwidth on the slice paths. Through simulations, we show that our proposed algorithm can reduce the total cost of establishment compared to a dedicated protection approach in 5G networks.
more »
« less
Availability-guaranteed slice composition for service function chains in 5G transport networks
Availability is a key service metric when deploying service function chains (SFCs) over network slices in 5G networks. We study the problem of determining the composition of a slice for a service function chain and the mapping of the slice to the physical transport network in a way that guarantees availability of the SFC while minimizing cost. To improve the availability, we design a slice that provides multiple paths (possibly with non-disjoint routing over the physical infrastructure) for hosting SFCs, and we determine the appropriate dimensioning of bandwidth on each path. Our simulation results show the effectiveness of our approach in terms of the cost of establishing the SFC and the SFC acceptance ratio.
more » « less- Award ID(s):
- 2008856
- NSF-PAR ID:
- 10209156
- Publisher / Repository:
- Optical Society of America
- Date Published:
- Journal Name:
- Journal of Optical Communications and Networking
- Volume:
- 13
- Issue:
- 3
- ISSN:
- 1943-0620; JOCNBB
- Page Range / eLocation ID:
- Article No. 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Network Function Virtualization (NFV) emerges as a promising paradigm with the potential for cost-efficiency, manage-convenience, and flexibility, where the service function chain (SFC) deployment scheme is a crucial technology. In this paper, we propose an Ant Colony Optimization (ACO) meta-heuristic algorithm for the Online SFC Deployment, called ACO-OSD, with the objectives of jointly minimizing the server operation cost and network latency. As a meta-heuristic algorithm, ACO-OSD performs better than the state-of-art heuristic algorithms, specifically 42.88% lower total cost on average. To reduce the time cost of ACO-OSD, we design two acceleration mechanisms: the Next-Fit (NF) strategy and the many-to-one model between SFC deployment schemes and ant-tours. Besides, for the scenarios requiring real-time decisions, we propose a novel online learning framework based on the ACO-OSD algorithm, called prior-based learning real-time placement (PLRP). It realizes near real-time SFC deployment with the time complexity of O(n), where n is the total number of VNFs of all newly arrived SFCs. It meanwhile maintains a performance advantage with 36.53% lower average total cost than the state-of-art heuristic algorithms. Finally, we perform extensive simulations to demonstrate the outstanding performance of ACO-OSD and PLRP compared with the benchmarks.more » « less
-
With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.more » « less
-
Network Function Virtualization (NFV) migrates network functions from proprietary hardware to commercial servers on the edge or cloud, making network services more cost-efficient, manage-convenient, and flexible. To facilitate these advantages, it is critical to find an optimal deployment of the chained virtual network functions, i.e. service function chains (SFCs), in hybrid edge-and-cloud environment, considering both resource and latency. It is an NP-hard problem. In this paper, we first limit the problem at the edge and design a constant approximation algorithm named chained next fit (CNF), where a sub-algorithm called double spanning tree (DST) is designed to deal with virtual network embedding. Then we take both cloud and edge resources into consideration and create a promotional algorithm called decreasing sorted, chained next fit (DCNF), which also has a provable constant approximation ratio. The simulation results demonstrate that the ratio between DCNF and the optimal solution is much smaller than the theoretical bound, approaching an average of 1.25. Moreover, DCNF always has a better performance than the benchmarks, which implies that it is a good candidate for joint resource and latency optimization in hybrid edge-and-cloud networks.more » « less
-
Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs) (i.e., firewalls and load balancers), is an effective service provision technique in modern data center networks. By requiring cloud user traffic to traverse the VNFs in order, SFC im- proves the security and performance of the cloud user applications. In this paper, we study how to place an SFC inside a data center to mini- mize the network traffic of the virtual machine (VM) communication. We take a cooperative multi-agent reinforcement learning approach, wherein multiple agents collaboratively figure out the traffic-efficient route for the VM communication. Underlying the SFC placement is a fundamental graph-theoretical prob- lem called the k-stroll problem. Given a weighted graph G(V, E), two nodes s, t ∈ V , and an integer k, the k-stroll problem is to find the shortest path from s to t that visits at least k other nodes in the graph. Our work is the first to take a multi-agent learning approach to solve k- stroll problem. We compare our learning algorithm with an optimal and exhaustive algorithm and an existing dynamic programming(DP)-based heuristic algorithm. We show that our learning algorithm, although lack- ing the complete knowledge of the network assumed by existing research, delivers comparable or even better VM communication time while taking two orders of magnitude of less execution time.more » « less
