Xiaolei Wang, Lijun Xie＊, Zhiqiang Qin, Yunjie Chen

1 National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, he’nan, China

2 Information and Navigation College, Xi’an 710077, shanxi, China

1. INTRODUCTION

The Fifth Generation (5G) wireless communication technology is proposed to push on revolutionizing future ubiquitous wireless networking, applications, and users’ quality of experience. In order to achieve these goals,5G wireless communication technologies need provide considerably higher network capacity,achieve large-scale equipment connections with reduced delay and cost, and save considerable energy compared to existing wireless technologies [1]. However, current mobile core networks is suffering from a huge variety of expensive and proprietary equipment, as well as inflexible hard-state signaling protocols [2]. When a particular function is not available, the cellular operator have to replace existing equipment even if it is still sufficient for most purposes, which shows the difficulty of adjusting the service quickly as needed.

The European Telecommunications Standards Institute Network functions virtualization Industry Specification Group (ETSI NFVISG) has been promoting the implementation of NFV that replaces dedicated traditional hardware-based middleboxes with novel software-based middleboxes running on commodity hardware (e.g., x86 server)，that is called virtual network function (VNF) instances [3].Currently, the traditional network functions in 5G network, which can be virtualized to VNF instances, include such functions as follows[4].

This paper divides VNF instances with high compatibility into clusters used for combining VNF instances in 5G networks.

·Evolved packet core (EPC) functions, such as the mobility management entity (MME),serving gateway (S-GW), home subscriber server (HSS), packet-gateway (PGW), and policy and charging rules function (PCRF).

·Baseband processing units functions, such as medium access control (MAC), radio link control (RLC), and radio resource control(RRC) procedures.

·switching function, traffic load balancing and operation service centers.

NFV breaks the barrier of function development that results from the monopoly of traditional function providers. Thus, it enables both carriers and third-party function providers participate in developing and deploying VNF instances in date centers and clouds for 5G services, however it also leads to the incompatibility issue among different VNF instances. This incompatibility provides necessity for clustering of VNF instances.

Specific VNF instances in given orders consists Service Function Chains (SFCs), which provides the services in 5G network. Many recent attempts have been made to tackle the SFC combination issue by formulating the optimization problems with different objects and constraints. The Internet Engineering Task Force (IETF) launched a Service Function Chain group to decouple the Infrastructure and service function deployments [5]. Clayman S[6] proposed an orchestrator monitoring the behavior of the virtual resources and placing the network services on the virtual nodes dynamically. Cohen R [7] formulated the virtual network function location problem as an integer linear program and attempted to minimize the distance cost and the setup costs of these functions. Luizelli M [8] attempted to minimize the number of VNF instances mapped on the servers. The three papers ignored the performance of functions which will affect the quality of services that is significant to the customers. Cheng G [9] aimed at maximizing the utility of the functions combination by considering the performance, but it may lead to the waste of the performance of the function instances. Basta A [10] proposed a model that combines SFCs by placing VNF instances dynamically and aims at minimizing the transport network load overhead against data-plane delay, number of potential datacenters and control overhead. Baumgartner [11]presented a novel mathematical optimization model for virtual core network embeddings with respect to latency bounds. Martini [12]formulated the problem of composing, computing and connecting virtual functions along the path that minimizes the overall latency in the 5G network. To minimize the cost of occupied link and node resource, Baumgartner [13]proposed a novel integer linear programming formulation that combines the virtual network topology with virtual network embedding optimization. Bagaa [14] argued the need for adopting service type and requirements as metrics for selecting adequate virtual PDNGWs for User Equipment receiving specific service type. Riggio [15] proposed a VNF placement heuristic algorithm for the performance of SFCs.

All the existing researches about VNFs combination into SFCs ignore the incompatibility issue among different VNF instances,and make the assumption that the real performance parameters of a SFC equals to the theoretical value calculated by the performance parameters of VNF instances in the SFC. Implemented by NFV, 5G network would confront the challenge of incompatibility issues among different VNF instances with distinct features.The opening of VNF instances introduces distinct features to themselves as follows. First,VNF instances could be developed by any authenticated provider, for example, HUAWEI,ZTE, Alcatel-Lucent and LinkerNetwoks, etc.In addition, different VNF instances may be developed with distinct development tools,programing languages, data formats and running environments [16]. Therefore, when some VNF instances are combined into a SFC for specific subscriber requests, they may not always cooperate ideally as expected for the incompatibility issues, the reliability and quality of service cannot be guaranteed. However,telecom systems require 99.999% reliability,and the high reliability problem in 5G network is divided into three layers: hardware layer,NFV platform layer and software layer. Each layer should work together to provide overall high reliability. The mentioned incompatibility issues would reduce the reliability of software layer of 5G network [17].

In this paper, we solve the incompatibility issues among different VNF instances by dividing them into clusters oriented to high compatibility for SFCs in 5G network. Firstly,we define compatibility among different VNF instances. secondly, we formulate the clustering of VNF instances as a hypergraph cluster problem. Then, we transform the problem to a non-cooperative multiplayer clustering evolutionary game. Thus, the cluster establishing is transformed to the game equilibrium searching. Finally, to find an Evolutionary Stable Strategy (ESS) that represents a set of highly compatible VNF instances, we design the replicator dynamic algorithm and demonstrate its effect by simulations. The main contributions of this paper are as follows:

1. In order to guarantee the reliability of SFC in 5G, the compatibility of different VNF instances is introduced and measured by the similarity between theoretical value and real measurement value of hit rate, processing cost,processing delay and reliability.

2. A hypergraph clustering model that divides VNF instances to different clusters is proposed to maximize the sum of weights of a cluster.

3. The hypergraph clustering problem is transformed into an evolutionary game model and solved by the discrete-time replicator dynamic algorithm.

The remainder of this paper is organized as follows. Section 2 gives the definition of compatibility of function instances. Section 3 presents the hypergraph clustering model. Section 4 presents the Evolutionary game model.Section 5 proposes the replicator dynamics to obtain instances clusters. Section 6 presents the experimental results. Section 8 concludes this paper.

II. COMPATIBILITY OF VNF INSTANCES

The compatibility of VNF instances represents in many aspects, like hit rate, availability,processing delay and cost, so it needs be accurately quantified. In this paper, we evaluate the compatibility of VNF instances by the probability of multidimensional performance parameters of runtime equals to the expected performance. Given a SFC S that contains k VNF instances (f1,f2,…,fk), and the compatibility of (f1,f2,…,fk) is defined as following:

As mentioned above, we focus on the performance parameters such as hit rate, processing speed, processing cost, and reliability.

Next, we will explain how to calculate the da.

The processing delay of the VNF instance is the time interval between the packet input and output, and the processing delay of the SFC is the sum of multiple VNF instances within the SFC.

The processing cost of an instance is the amount of occupied CPU and the processing cost of a SFC is the sum of multiple VNF instances.

III. HYPERGRAPH CLUSTERING MODEL

In this paper, our goal is to place some NVF instances with high compatibility into a cluster that ensures the QoS. Selecting some VNF instances in the whole 5G network into a cluster is formulated as a mathematical problem of extracting a group from a set of objects with some features, so called clustering. In practice, there should be more and more instances in 5G network, so the number of clusters is uncertain in advance and dynamic. Besides,the compatibility of VNF instances relates to multidimensional performance parameters,thus the general clustering methods are not suitable. Fortunately, the hypergraph theory is suitable for solving the problem.

Based on the hypergraph theory, we formulate this problem as a hypergraph clustering model H=(V,E,)ω, where V={1,...,n}is a finite set of vertices referring to n VNF instances in 5G network, E⊆2Vis a set of hyperedges referring to all SFCs that once deployed, and ω:E→R+is a real-valued positive weight of each hyperedge (SFC) and reflects fitness of the cluster to the network policy. Here, we let cardinality k be the number of functions in the SFC, called k-graphs.

The problem of clustering a k-graph H=(V,E,)ω contains a set of n vertices V={1,...,n}, a set of hyperedgesand a real value affinity function ω:. It can be mathematically defined as solving

Thus finding an expected cluster means finding a subset of vertices with high cluster value. Solving this problem would be an expensive combinational problem and NP-Hard.Bulò [19] proposed a novel method based on the game theoretic point of view for the relax version of this problem.

IV. EVOLUTIONARY GAME MODEL

Evolutionary game theory provides an effective way to the hypergraph clustering problem. Generally, an evolutionary game is played iteratively among individuals from a large population and is formulated as Γ =(P,V,π), where P={1,...,k } is a set of players.V={1,...,n} is the set of pure strategies for each player, and indicates the all VNF instances in 5G network. The payoff functionassigns a utility to each strategy profile

Our goal is to find clusters with high compatibility, so the payoff functionis proportional to the compatibility of the strategy profile

为了进一步证实在本实验中MRS培养基更适合初筛所得乳酸菌生长，我们将MRS培养基上分离得到的菌落分别接种于ATB和MRS液体培养基中，以25℃培养24 h，ATB液体培养基中无菌体生长，而MRS液体培养基成浑浊状；同理，将ATB上分离所得10株菌分别接种于ATB、MRS液体培养基中，这10株菌在两种培养基中均生长，因此证明：（1）MRS培养基更适合本实验中乳酸菌的生长；（2）MRS初筛平板上分离得到的112株菌中包含ATB初筛平板上分离得到的10株乳酸菌，因此本实验后续试验全部采用MRS培养基，并只验证MRS上分离得到的112株菌。

Within the evolutionary process of the clustering game, each player will play pre-assigned strategies, and repeatedly select randomly VNF instances from V. Here, a player with preassigned strategy j∈V is called j-strategist. The state of the population at a given time t is represented as an n-dimensional vector x(t), where xj(t ) represents the portion of j-strategists in the population at time t.let the initial distribution of preassigned strategies in the population is x(0). The set of all possible states of population is defined as the following standard simplex

According to Darwinian evolution theory,the fittest strategies will survive and spread via the natural selection mechanism. We denote the support of x∈∆ as:

which is the set of strategies that are alive in a given population x.

The expected payoff of all players is defined as the following function u:

We use the notations x[k]as a shortcut for a sequence (x,…,x)of k identical states x,and ejto indicate the n-vector with xj=1 and zero elsewhere. Thus the expected payoff earned by a j-strategist in a population x∈∆iswhile the expected payoff over the entire population is u(x[k]).

In evolutionary game theory, an ESS is a state that a disturbance cannot change the genetic compositions of the population. It is proved that an ESS-cluster of H is an ESS of the corresponding hypergraph clustering game. If x∈∆ is an ESS-cluster of H, then

V. EVOLUTION TO A CLUSTER

In this section, we address the issue of determining an ESS cluster for a given instance of a hypergraph clustering problem that is a computationally hard problem. Bulò [19] proved that the ESSs of the clustering game are in one-to-one correspondence with (strict) local solutions of a nonlinear optimization problem.To get the ESS-cluster of the hypergraph clustering game, we need to introduce replicator equation that ensures the distribution of strategies whose payoffs are higher than average payoff will increase over time. Based on the above definition in the hypergraph clustering game, we define the replicator dynamics as follows:

Unlike standard partitional techniques,our approach involves extracting one cluster at a time. The complexity of finding an ESS-cluster with our algorithm turns out to bewhereis the number of SFCs that once existed, and ρ is the average number of iteration needed to converge.

VI. SIMULATION RESULTS

6.1 Performance of algorithm

Firstly, to show the effectiveness of the proposed approach, we compare our approach with two of the most classical hypergraph clustering algorithms, the Clique Averaging algorithm (CA) [20] and the Supersym-metric Nonnegative Tensor Factorization (SNTF)[21]. Since CA and SNTF, in contrast to our method, require as a parameter the number of clusters K, so we run them with values of, where K∗denotes the correct number of clusters. The quality of the clustering algorithms was evaluated in terms of classification error, which is the rate between the number of misclassified instances and the total instances.

Fig. 1 Classification error under different number of clutters

Fig. 2 Clustering time under different number of VNF instances

We run all the experiments on a computer equipped with 3.4 Ghz Intel Core i7 processor and 4 Gb RAM. In the case of CAVERAGE and SNTF, we used the original codes with Matlab and C++ implementations, respectively; our method is implemented with Matlab.

To simulate real conditions, we choose 10 VNF instances from HUAWEI, ZTE, Alcatel-Lucent respectively and 10 functions instances from other providers. Here, we let the compatibility of VNF instances from the same provider be 1, and that from n providers be 1/n. Thus, the 10 VNF instances from one provider belong to a cluster, and the other 10 VNF instances from other providers are considered as clutters that do not belong to any cluster. Obviously, K∗=3.

Figure 1 shows the results obtained by the competing algorithms in terms of classification error with three clusters. Each plot shows the average value of 30 experiments. It is clear that our algorithm substantially outperformed both CA and SNTF even when they were set the correct number of clusters K∗,and it worked almost perfectly irrespective of the number of clutters. In addition, both competitors achieved better performances when K ＞K∗, and it is intuitional that the only way to get rid of clutters is to divide them into additional (garbage) clusters. Nevertheless, due to the unpredictable nature of clutters, they typically did not get assigned to the garbage class, however, instead were assigned to the original three clusters, thereby making the performance of CA and SNTF poorer and poorer as clutter increases.

Next, we compare our approach with CA and SNTF about the clustering time with 100, 1000 and 10000 VNF instances. Figure 2 shows that the clustering times of our algorithm is an order of magnitude faster than SNTF, while is an order of magnitude slower than CA. This is indeed to be expected as CAVERAGE, unlike our algorithm and SNTF,transforms the original hypergraph into a graph at the outset, thereby greatly reducing the complexity of the problem. On the other hand, like our algorithm, SNTF does not resort to any graph approximation, but, by optimizing a single variable at a time, it has a substantially larger computational complexity.

6.2 Eff ectiveness of VNF instances clustering

Secondly, to show the effectiveness of VNF instances clustering to the combination of SFCs, we combine the SFCs based on the results of clustering, which means that cluster based on our method first and then select VNF instances for each SFC from the proper cluster respectively. We choose the two typical VNF instances combination methods: greedy and exhaustive [9], which combine VNF instances ignoring the compatibility among different VNF instances. Here, we conduct the simulation by combining four, five and six VNF instances into a SFC respectively. The number of VNF instances of a cluster is fixed to be 1000.

Figure 3 shows the average combination time of different combination methods. Obviously, as the number of VNF instances increases, the combination time of original greedy and exhaustive methods grow quickly,while the combination time of the two clustering-based functions combination methods,called H-g and H-e, increase seldom. Because the original greedy and exhaustive methods need to select VNF instances from all candidates, and then spend more time when the number of VNF instances increases. On the contrary, the number of VNF instances of a cluster is fixed to be 1000, so the number of VNF instance candidates for a SFC is fixed and the time is nearly constant.

Figure 4. shows the compatibility of SFCs combined with the four methods respectively.It is clear that the compatibility of SFCs obtained with H-g and H-e is higher than the two methods without clustering, which means the clustering of VNF instances oriented to compatibility can guarantee the quality of SFCs close to the excepted quality.

Fig. 3 Combination time of SFCs

Fig. 4 Compatibility of SFCs

VII. CONCLUSION

To combine VNF instances into SFCs efficiently in 5G network, this paper presented a novel VNF instances clustering method towards dividing VNF instances with diverse characteristics into different clusters oriented to high compatibility within each cluster. We first defined the compatibility among VNF instances based on the fitness of multidimensional performance parameters, and established the hypergraph clustering model based on the compatibility of VNF instances. By introducing the evolutionary game theory, the model was solved by designing the replicator dynamics. Finally, the results of experiments showed that the proposed method is efficient and clustering of instances can improve the quality of SFCs.

This work was supported by The National High Technology Research and Development Program of China (863) (Grant No.2014AA01A701, 2015AA01A706).

[1] Akyildiz I F, Wang P, Lin S C, “SoftAir: A software defined networking architecture for 5G wireless systems,” Computer Networks, vol. 85, no. 4,2015, pp. 1-18.

[2] K. Pentikousis, Y. Wang, and W. Hu, “MobileFlow:Toward Software-Defined Mobile Networks,”IEEE Communications Magazine, vol. 51, no. 7,2013, pp. 44–53.

[3] Abdelwahab S, Hamdaoui B, Guizani M, et al,“Network function virtualization in 5G,” IEEE Communications Magazine, vol. 54, no. 4, 2016,pp. 84-91.

[4] Liang C, Yu F R, Zhang X, “Information-centric network function virtualization over 5g mobile wireless networks,” IEEE Network, vol. 29, no. 3,2015, pp. 68-74.

[5] T. Nadeau E, “Problem Statement for Service Function Chaining,” 2015. https://www.rfc-editor.org/info/rfc7498.

[6] Clayman S, Maini E, Galis A, et al., “The dynamic placement of virtual network functions,” Proc.network operations and management symposium IEEE, 2014, pp. 1-9.

[7] Cohen R, et al., “Near optimal placement of virtual network functions” Proc. IEEE Conference on Computer Communications, 2015, pp. 1346-1354.

[8] Luizelli M C., et al., “Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions” Proc.IFIP/IEEE International Symposium on Integrated Network Management, 2015,pp. 98-106.

[9] Cheng G, Chen H, Hu H, et al, “Enabling network function combination via service chain instantiation,” Computer Networks, vol. 92, no.4, 2015, pp. 396-407.

[10] Basta A, et al., “Applying NFV and SDN to LTE mobile core gateways, the functions placement problem,” The Workshop on All Things Cellular:Operations, Applications, & Challenges. ACM,2014, pp. 33-38.

[11] Baumgartner A, Reddy V S, Bauschert T, “Combined Virtual Mobile Core Network Function Placement and Topology Optimization with Latency Bounds,” Proc. Fourth European Workshop on Software Defined Networks, 2015, pp. 97-102.

[12] Martini B, et al., “Latency-aware composition of Virtual Functions in 5G” Proc. Network Softwarization. IEEE, 2015,pp. 1-6.

[13] Baumgartner A, Reddy V S, Bauschert T, “Mobile core network virtualization: A model for combined virtual core network function placement and topology optimization,” Proc. Network Softwarization. IEEE, 2015, pp. 1-9.

[14] Bagaa M, Taleb T, Ksentini A, “Service-aware network function placement for efficient traffic handling in carrier cloud,” Proc. Wireless Communications and NETWORKING Conference IEEE, 2014, pp. 2402-2407.

[15] Riggio R, Bradai A, Rasheed T, et al., “Virtual network functions orchestration in wireless networks,” Proc. International Conference on network and service management IEEE Computer Society, 2015, pp. 108-116.

[16] Yousaf F Z, Taleb T, “Fine-grained resource-aware virtual network function management for 5G carrier cloud,” IEEE Network, 2016,vol. 30, no. 2, 2016, pp. 110-115.

[17] Mijumbi R, Serrat J, Gorricho J L, et al., “Network Function Virtualization: State-of-the-Art and Research Challenges,” IEEE Communications Surveys & Tutorials, vol. 18, no. 1, 2016, pp.236-262.

[18] Akyildiz I F, Lin S C, Wang P, “Wireless software-defined networks (W-SDNs) and network function virtualization (NFV) for 5G cellular systems: An overview and qualitative evaluation,”Computer Networks, vol. 93, no. 2, 2015, pp. 66-79.

[19] Bulò S R, Pelillo M, “A Game-Theoretic Approach to Hypergraph Clustering,” IEEE Transactions on Pattern Analysis & Machine Intelligence,vol. 35, no. 6, 2013, pp. 1312-1327.

[20] Agarwal S, Lim J, Zelnik-Manor L, et al., “Beyond pairwise clustering,” Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 2005, pp.838-845.

[21] Shashua A, Zass R, Hazan T, “Multi-way Clustering Using Super-Symmetric Non-negative Tensor Factorization,” European Conference on Computer Vision. Springer-Verlag, 2006, pp.595-608.