CN107124306A - Content delivery network server optimization dispositions method under network function virtualized environment - Google Patents

Abstract

Aiming at the defects of the existing CDN copy placement scheme, the present invention proposes a content delivery network server optimization deployment method under the network function virtualization environment. The invention utilizes the spectral clustering model, taking into account the data and topological characteristics of the physical network. The adjacency matrix is established by using the topological relationship of the underlying network and the traffic demand of the nodes, and the physical network nodes are divided into several sets by using the spectral clustering algorithm. Then traverse the nodes in each set, and calculate the cost required for it to serve as the replica center node to provide content services for the rest of the set. Select the node with the lowest cost and use it as the placement node of the replica server to reduce the cost.

Description

Optimal deployment method of content delivery network server in network function virtualization environment

technical field

The invention belongs to the field of network technology, and in particular relates to a content delivery network server optimization deployment method under a network function virtualization environment.

Background technique

With the development of network technology, especially the rapid development of mobile Internet technology, the dissemination of network content has gradually changed from text and image content to video dissemination. This results in explosive growth of network traffic and increases the possibility of network congestion. Network congestion leads to a decline in user experience, which causes content providers to lose a large number of customers and reduce profits.

With the development of CDN (Content Delivery Network), the content replica server can be deployed on the edge network closer to the user, so that the user can obtain the network content in a relatively short period of time, which increases the user experience. As shown in Figure 1(a), the traditional network is mainly divided into three components: server, communication link and end user. In a traditional network, end users request server content or servers provide services to users, and the communication link to go through is long. When there are many end users, the traffic on the network is large, which is likely to cause congestion. At the same time, there is only one server serving users, which may also cause excessive load on the server and cause downtime. As shown in Figure 1(b), in the CDN network, there are four main components: server, communication link, replica server and end user. The server is a source server that provides content or updates and deletes content, and all network content flows into the network from this server. The replica server is directly connected to this server, and the location of the replica server is relatively close to the end user. The content required by the user is directly served by the closer copy server, without going across a large number of network devices to the original server to obtain the content. Therefore, the service quality can be improved and the user's waiting delay can be reduced. A key issue in CDN technology is the placement of CDN content replica servers. Existing replica placement algorithms are deployed based on dedicated CDN physical servers. Dedicated servers require a lot of manpower to deploy. At the same time, the maintenance and updating of equipment requires a lot of manpower and material resources. If the old equipment is not handled well, it will also cause environmental pollution. At the same time, the existing CDN replica server placement algorithm has obvious defects, and cannot take into account the topology of the underlying network and deploy it based on user request traffic data. Therefore, it is impossible to effectively reduce core network traffic and improve user experience.

In the existing research on CDN replica placement algorithm, one is to abstract the placement problem of CDN replica server into the problem of factory location selection. It is then placed using a random algorithm. The specific steps are: first determine the physical topology of the CDN network, determine the traffic requirements of each node and the bandwidth between different nodes; then randomly select appropriate nodes from all physical nodes to place the replica server, and calculate each node to the optimal ( The sum of the costs of the replica centers for metrics such as closest distance or load balancing. Repeat the above steps 10 times, and take the one with the smallest sum of costs as the final solution. Theoretical evidence proves that the results of the random algorithm are more stable and the effect is better when it is repeated about 10 times. But there are still the following deficiencies: (1) The random algorithm has a large volatility, and the resulting solutions have great limitations. (2) The random algorithm is not sensitive to the topological structure of the physical network, and cannot be adjusted according to different network topological structures, and the topology sensitivity of the algorithm is poor. (3) The random algorithm is not sensitive to the node traffic requirements of the physical network and bandwidth resources, and cannot be adjusted according to the actual underlying network requirements, and the data sensitivity of the algorithm is poor.

Another way to place CDN copies is: a greedy algorithm-based CDN copy placement scheme, which reduces the complexity of the placement algorithm by using the idea of iteration. The specific process of the algorithm is as follows: traverse all physical nodes, and calculate the sum of the costs consumed by each physical node as a copy center node serving other nodes. The node with the smallest sum of costs is selected as the replica center node. Iterate the above process until all nodes are placed. The disadvantages of this placement scheme are as follows: (1) The greedy algorithm is easy to fall into the local optimal solution. Since the replica center placed first has an influence on the replica center placed later, it is difficult to obtain a global optimum. (2) The greedy algorithm is sensitive to the data of the underlying network, but is less sensitive to the topology of the underlying network.

Contents of the invention

The object of the present invention is to propose a CDN network replica server placement method under the NFV (Network Function Virtualization) environment for the defects of the existing CDN replica placement scheme. The invention utilizes the spectral clustering model, taking into account the data and topological characteristics of the physical network. The adjacency matrix is established by using the topological relationship of the underlying network and the traffic demand of the nodes, and the physical network nodes are divided into several sets by using the spectral clustering algorithm. Then traverse the nodes in each set, and calculate the cost required for it to serve as the replica center node to provide content services for the rest of the set. Select the node with the lowest cost and use it as the placement node of the replica server to reduce the cost.

The content delivery network server optimization deployment method in the network function virtualization environment of the present invention includes the following steps: Step 1: Based on the physical topology structure of the content delivery network, the servers in the physical nodes are used as virtual nodes, and the virtual nodes to be deployed are determined. Network Topology;

Step 2: Calculate the similarity matrix W according to the virtual network topology and node traffic requirements of virtual nodes:

Calculate the similarity w _ij between any two virtual nodes: if there is a link between the two virtual nodes (that is, there is a direct connection between the virtual nodes), then the similarity w _ij =(|d _i -d _j |) ^2.5 , i≠j; otherwise, the similarity w _ij =0; where i, j are virtual node identifiers, d _i , d _j represent the node flow requirements of different virtual nodes;

Get the similarity matrix from the similarity w _ij n represents the number of virtual nodes;

Step 3: According to the formula D=dia(dr ₁ ,dr ₂ ,...,dr _n ), the degree matrix D is obtained, and the Laplace matrix L is obtained by L=DW, wherein dia is a diagonal symbol, and the diagonal elements

And normalize the Laplacian matrix L to obtain a normalized Laplacian matrix L _sym : _Lysm = D ^{-1/ 2} LD ^-1/2 ;

Step 4: Calculate the n eigenvalues and eigenvectors of L _ysm , arrange the eigenvectors u ₁ ,...,u _k corresponding to the first k smallest eigenvalues in columns to form a matrix U _n×k =(u ₁ ,. ..,u _k ), where k represents the number of replica servers to be deployed;

Normalize the matrix U _n×k by row to get the matrix T=(t _ij ) _n×k , where the matrix elements

Obtain the vectors y ₁ , y ₂ ,...,y _n for the matrix T by row, where the subscript i of the vector y _i corresponds to the i-th row of the matrix T, and i=1,...,n;

Step 5: Carry out k-means clustering processing on y ₁ ,...,y _n , and obtain k clustering results as C ₁ ,C ₂ ,...,C _k (the elements in each set represent The subscript value of the y vector), from the virtual node identifier contained in each clustering result to obtain k node clustering sets A _m , m=1,...,k, that is, A _m ={i:i∈C _i } ,m=1,...,k;

For example: the vectors y ₁ , y ₄ , y ₇ ∈ C ₁ in the clustering result, then the clustering set A ₁ is composed of virtual nodes v ₁ , v ₄ , v ₇ .

Step 6: For each node clustering set A _m , traverse each virtual node v _r in A _m and calculate the sum of the costs of the virtual node v _r as the central node where c _ir represents the link length from node v _i to node v _r , that is, the number of hops from node v _i to node v _r , and p is the unit bandwidth cost; select the virtual node with the smallest total cost as the copy of each A _m central node.

Owing to adopted above-mentioned technical scheme, the beneficial effect of the present invention is:

(1) Reduce deployment costs. The invention fully considers the topology and data information of the network. According to the topology and data information of the network, a reasonable node can be effectively selected as the replica center node to take into account the topology and traffic demand information to reduce costs.

(2) Reduce service delay. The present invention uses a spectrum clustering algorithm to divide the network topology, which can fully consider the delay characteristics of the network, so the selection of the copy center can be distributed to nodes closer to the user to reduce the network delay.

(3) Reduce core network traffic. Since the present invention can more effectively disperse the location selected by the replica center to a node closer to the user, the traffic demand between the CDN network and the user is only transmitted back and forth between the replica center and the user, reducing the traffic of the core network. Thereby, the robustness of the network is extremely high and the possibility of congestion is reduced.

Description of drawings

Figure 1 is a model diagram of a traditional network and a CDN network.

Fig. 2 is a schematic diagram of the virtualization process of the example network of the present invention.

Fig. 3 is a schematic diagram of the clustering processing flow of the present invention.

detailed description

In order to make the purpose, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the implementation methods and accompanying drawings.

The implementation of the content delivery network server optimization deployment method in the network function virtualization environment of the present invention includes CDN network modeling in the NFV environment, spectral clustering algorithm division of sub-graphs and replica center selection, specifically:

(1) CDN network model in NFV environment

Figure 2(a) shows the actual physical network topology, including computing nodes such as general servers, large data centers and cloud data centers, and functional nodes such as routers and switches. In the network virtualization (NV) environment, all nodes and bandwidth of the physical network can be virtualized into computing resources and bandwidth resources, as shown in Figure 2(b). The NFV technology can deploy the same network function software on different computing nodes or deploy different network function software on the same computing node. In this patent, we mainly deploy the same network function on different computing nodes. Therefore, the original problem of deploying a replica server on the underlying physical network is transformed into deploying a replica server on an abstract network. Doing so can shield different underlying network entities and focus on the selection of replica servers.

(2) Spectral clustering algorithm to divide subgraphs

Let G = (V, E) represent the network topology in Figure 1(b). Among them, V represents the clustering set of nodes, and E represents the combination of links. d ₁ ,d ₂ ,...,d _n represent the traffic demand of each node in the node clustering set, and the subscript n represents the total number of nodes. If there is a link connection between nodes, use the similarity calculated by formula (1), otherwise the similarity is set to 0.

w _ij ＝(|d _i -d _j |) ^2.5 ,(i≠j) (1)

The adjacency matrix of similarity calculated by formula (2)

Matrix D=dia(dr ₁ ,dr ₂ ,...,dr _n ) is a degree matrix, where dr _i (i=1,...,n) is obtained by formula (3)

dia is the diagonal symbol, which means a diagonal matrix, and the remaining matrix entries are zero.

Use the formula (4) to obtain the Laplacian matrix L:

L=D-W (4)

Use formula (5) to find the Laplacian matrix L _sym

L _ysm = D ^-1/2 LD ^-1/2 (5)

Use matlab to obtain all eigenvalues λ ₁ , λ ₂ ,...,λ _n of L _ysm where λ ₁ ≤λ ₂ ≤...λ _n and their corresponding eigenvectors u ₁ ,u ₂ ,..., u _n (the feature vector is the column vector u _i =(u _1,i ,u _2,i ,...,u _n,i ) ^T ). Take the eigenvectors u ₁ ,...,u _k corresponding to the eigenvalues λ ₁ ,...,λ _k (k is the number of replica servers to be placed, this value should be less than n). The k eigenvectors are arranged in columns to form a matrix U _n×k =(u ₁ ,...,u _k ). Calculate matrix U and get normalized matrix T=(t _ij ) _n×k by row, where matrix element t _ij is obtained according to formula (6)

Obtain the vectors y ₁ , y ₂ ,...,y _i ,...,y _n of the matrix T row by row, where the vector subscript i corresponds to the i-th row of the matrix T. Use the k-mean algorithm to cluster y ₁ ,...,y _n .

The steps of the k-mean algorithm are as follows. Among the n vectors, first randomly select k vectors as the centers.

②Traverse other non-central vectors, and calculate the distance from non-central vectors to k central vectors according to formula (7)

③ For each non-central vector, classify this non-central vector and the central vector with the smallest distance into one category. The clustering results C ₁ ',...,C' _k are obtained, where the elements in each set are subscript values representing the y vector.

For each clustering result, a center vector is recalculated, and the sum of distances from this vector to other nodes in the clustering result is the smallest. Thus k new center vectors are obtained.

⑤Repeat step ②- until the distance difference between the newly updated k centers and the center before updating is less than .

⑥ Obtain the k-means clustering method for the clustering results of vectors y ₁ ,...,y _n as C ₁ ,C ₂ ,...,C _k (the elements in each set represent the y vector subscript value)

After the k-means algorithm, we get the clustering results C ₁ ,...,C _k , where the elements in each set also correspond to the subscripts of the nodes in the network topology G=(V,E). Use the formula (8) to obtain the clustering set of the network topology, that is, the node clustering set A ₁ , A ₂ ,...,A _k :

A _m ={i:i∈C _i }, m=1,...,k (8)

So far, the graph clustering is over, and we get different cluster sets, and A ₁ ,...,A _k . Next, select a suitable node in each cluster set as the replica center node to serve all other demand nodes.

(3) copy center selection

For each clustering set, traverse each node of the clustering set, and calculate it as the sum cost of serving other nodes in the set, see formula (9) for the specific calculation:

d _i represents the traffic demand of node v _i in clustering set _Am , v _r represents, c _ir represents the link length from node v _i to node v _j (indicated by the number of hops), and p is the unit bandwidth cost.

Select the node with the smallest cost sum cost as the replica center node of each clustering set.

To sum up, the present invention combines the placement problem of virtual CDN network copy servers with the clustering problem to more effectively solve the virtual CDN network placement problem.

Claims (3)

1. the content delivery network server optimization dispositions method under network function virtualized environment, it is characterised in that including under Row step：Step 1：Based on the physical topological structure for undertaking the construction of content delivery network, using the server in physical node as virtual Node, it is determined that virtual network topology to be disposed；

Step 2：Similarity matrix W is calculated according to the node flow demand of virtual network topology and dummy node：

Calculate the similarity w between any two dummy node_ij：If having link connection, similarity between two dummy nodes w_ij=(| d_i-d_j|)^2.5,i≠j；Otherwise, similarity w_ij=0；Wherein i, j are virtual node identifiers, d_i、d_jRepresent different void Intend the node flow demand of node；

By similarity w_ijObtain similarity matrixN represents dummy node number；

Step 3：According to formula D=dia (dr₁,dr₂,...,dr_n) degree matrix D is obtained, Laplce's square is obtained by L=D-W Battle array L, wherein dia are diagonal symbol, diagonal element

And Laplacian Matrix L is normalized, obtain normalized Laplacian Matrix L_sym：L_ysm=D^-1/2LD^-1/2；

Step 4：Calculate L_ysmN characteristic value and characteristic vector, by the corresponding characteristic vector u of preceding k minimal eigenvalue₁,..., u_kBy row arrangement form matrix U_n×k=(u₁,...,u_k), wherein k represents replica server number to be disposed；

To matrix U_n×kMatrix T=(t are obtained by row normalization_ij)_n×k, wherein matrix element

Vector y is obtained by row to matrix T₁,y₂,…,y_n, wherein vector y_iSubscript i homographies T the i-th row, and i=1 ..., n；

Step 5：To y₁,...,y_nK mean cluster processing is carried out, k cluster result is obtained for C₁,C₂,...,C_k, by each cluster As a result the virtual node identifiers included obtain k node clustering set A_m, m=1 ..., k；

Step 6：For each node clustering set A_m, travel through A_mIn each dummy node v_r, calculate dummy node v_rIn The cost summation of heart nodeWherein c_irRepresent from node v_iTo node v_rLinkage length, that is, save Point v_iTo node v_rHop count, p be unit bandwidth cost；

Choose the minimum dummy nodes of cost summation cost and be used as each node clustering set A_mCopy Centroid.

2. the method as described in claim 1, it is characterised in that in step 5, to y₁,...,y_nCarry out k mean clusters processing tool Body is：

1. in n vector y₁,...,y_nIn, k vector is randomly selected as center vector；

2. in vectorial y₁,...,y_nIn, non-central vector is calculated to the distance of k center vector

3. to each non-central vector, divide its center vector minimum with distance into a class, obtain cluster result C₁',..., C'_k, wherein the element in each cluster result represents y_iSubscript value；

4. to each cluster result C'_m, recalculate a center vector, the center vector to cluster result C'_mIn it is non-in Heart vector it is minimum apart from sum, obtain k new center vectors；

5. repeat step 2. -4., until k center vector newly updating with the range difference of center vector before updating is less than threshold epsilon.

3. method as claimed in claim 2, it is characterised in that the value of threshold epsilon is ε≤0.001.