网络功能虚拟化环境下的内容交付网络服务器优化部署方法

摘要

本发明针对现有CDN副本放置方案的缺陷，提出了一种网络功能虚拟化环境下的内容交付网络服务器优化部署方法。本发明利用谱聚类模型，兼顾了物理网络的数据和拓扑特性。利用底层网络的拓扑关系以及节点的流量需求建立邻接矩阵，利用谱聚类算法将物理网络节点划分成几个集合。然后遍历每个集合中的节点，计算其作为副本中心节点来为集合中其余节点提供内容服务所需成本。选取成本最小的节点，使其作为副本服务器的放置节点，以此来降低成本。

说明书

技术领域

本发明属于网络技术领域，具体涉及网络功能虚拟化环境下的内容交付网络服务器优化部署方法。

背景技术

随着网络技术的发展，尤其是移动互联网技术的快速发展，使得网络内容从文字图片内容的传播逐渐变为视频形式传播。这使得网络流量呈现出爆炸式增长，增大了网络发生拥堵的可能。网络的拥堵导致用户的体验下降，从而使得内容提供商损失了大量的客户，盈利减少。

而CDN(内容交付网络)的发展，使得内容副本服务器可以部署在离用户较近的边缘网络上，使得用户可以在较短的时间内获取网络内容，增加了用户体验。如图一(a)所示为传统网络，主要分为三个部件：服务器、通信链路和终端用户。在传统的网络中，终端用户请求服务器内容或服务器为用户提供服务，要经过的通信链路较长。当终端用户较多的时候，网络上的流量较大，容易造成拥塞，同时只有一个服务器为用户服务，也很有可能造成服务器负载过大导致宕机。如图一(b)所示在CDN网络中，主要的部件有四个：服务器、通信链路、副本服务器和终端用户。其中服务器是提供内容或者内容更新删除的源服务器，所有的网络内容都从此服务器流入网络。而直接与此服务器相连的是副本服务器，且副本服务器的位置在离终端用户较为接近。而用户所需的内容直接由较近的副本服务器来提供服务，无需跨过大量的网络设备到达原始服务器索取内容。因此可以提高服务质量，减小用户的等待延迟。而CDN技术中一个关键问题就是CDN内容副本服务器的放置问题，现有的副本放置算法都是基于专用的CDN物理服务器来进行部署。而专用的服务器需要耗费大量的人力来部署。同时设备的维护以及更新需要大量的人力物力。老旧设备如果处理不好，也会造成环境污染。同时现有的CDN副本服务器放置算法有明显的缺陷，不能兼顾底层网络的拓扑以用户的请求流量数据来部署。因此及无法有效的降低核心网络流量，提高用户体验。

在现有的CDN副本放置算法的研究中，一种是将CDN副本服务器的放置问题抽象成工厂选址问题。然后利用随机算法将其进行放置。具体步骤为：首先确定承建CDN网络的物理拓扑结构，确定各个节点的流量需求以及不同节点间的带宽；然后在所有物理节点中随机选取适当的节点来放置副本服务器，计算各个节点到最优(距离最近或负载均衡等度量)的副本中心的成本总和。重复上述步骤10次，取成本总和最小的那次作为最终的解决方案。理论 依据证明，在重复10次左右，随机算法的结果较为稳定，效果较好。但是依然存在以下不足：(1)随机算法具有较大的波动性，所产生的解决方案具有很大的局限性。(2)随机算法对物理网络的拓扑结构不敏感，不能根据不同的网络拓扑结构进行调整，算法的拓扑敏感性较差。(3)随机算法对物理网络的节点流量需求，以及带宽资源不敏感，不能根据实际的底层网络需求进行调整，算法的数据敏感性较差。

另一种对CDN副本放置的方式是：基于贪心算法的CDN副本放置方案，利用迭代的思想降低了放置算法的复杂度。算法的具体过程如下：遍历所有物理节点，计算每个物理节点作为副本中心节点为其他节点服务所消耗的成本总和。选取成本总和最小的节点作为副本中心节点。迭代上述过程，直到所有的节点均放置完成。该放置方案的缺点体现在：(1)贪心算法很容易陷入局部最优解。由于先放置的副本中心对后放置的副本中心具有影响，所以很难得到全局性的最优。(2)贪心算法对底层网络的数据是敏感的，但对底层网络的拓扑敏感性较低。

发明内容

本发明的发明目的在于：针对现有CDN副本放置方案的缺陷，提出了一种NFV(网络功能虚拟化，Network Function Virtualization)环境下的CDN网络副本服务器放置方法。本发明利用谱聚类模型，兼顾了物理网络的数据和拓扑特性。利用底层网络的拓扑关系以及节点的流量需求建立邻接矩阵，利用谱聚类算法将物理网络节点划分成几个集合。然后遍历每个集合中的节点，计算其作为副本中心节点来为集合中其余节点提供内容服务所需成本。选取成本最小的节点，使其作为副本服务器的放置节点，以此来降低成本。

本发明的网络功能虚拟化环境下的内容交付网络服务器优化部署方法，包括下列步骤：步骤1：基于承建内容交付网络的物理拓扑结构，将物理节点中的服务器作为虚拟节点，确定待部署的虚拟网络拓扑结构；

步骤2：根据虚拟网络拓扑结构和虚拟节点的节点流量需求计算相似度矩阵W：

计算任意两个虚拟节点之间的相似度w_ij：若两个虚拟节点之间有链路连接(即虚拟节点之间存直连关系)，则相似度w_ij＝(|d_i-d_j|)^2.5,i≠j；否则，相似度w_ij＝0；其中i、j为虚拟节点标识符，d_i、d_j表示不同虚拟节点的节点流量需求；

由相似度w_ij得到相似度矩阵n表示虚拟节点数目；

步骤3：根据公式D＝dia(dr₁,dr₂,...,dr_n)得到度数矩阵D，由L＝D-W得到拉普拉斯矩阵L，其中dia为对角符号，对角元

并对拉普拉斯矩阵L进行归一化处理，得到归一化的拉普拉斯矩阵L_sym：L_ysm＝D^-1/2LD^-1/2；

步骤4：计算L_ysm的n个特征值及特征向量，将前k个最小特征值对应的特征向量u₁,...,u_k按列排列形成矩阵U_n×k＝(u₁,...,u_k)，其中k表示待部署的副本服务器数目；

对矩阵U_n×k按行归一化得到矩阵T＝(t_ij)_n×k,其中矩阵元素

对矩阵T按行取得向量y₁,y₂,…,y_n，其中向量y_i的下标i对应矩阵T的第i行，且i＝1,…,n；

步骤5：对y₁,...,y_n进行k均值聚类处理，得到k个聚类结果为C₁,C₂,...,C_k(其中每个集合中的元素均是代表y向量的下标值)，由每个聚类结果包含的虚拟节点标识符得到k个节点聚类集合A_m,m＝1,…,k，即A_m＝{i:i∈C_i},m＝1,…,k；

如：聚类结果中向量y₁,y₄,y₇∈C₁，则聚类集合A₁由虚拟节点v₁,v₄,v₇组成。

步骤6：对于每个节点聚类集合A_m，遍历A_m中的每个虚拟节点v_r，计算虚拟节点v_r作为中心节点的成本总和其中c_ir表示从节点v_i到节点v_r的链路长度，即节点v_i到节点v_r的跳数，p为单位带宽成本；选取成本总和cost最小的虚拟节点作为每个A_m的副本中心节点。

由于采用了上述技术方案，本发明的有益效果是：

(1)降低部署成本。本发明充分考虑了网络的拓扑和数据信息。可以根据网络的拓扑和数据信息有效的选择合理的节点来作为副本中心节点来兼顾拓扑和流量需求信息从而降低成本。

(2)降低服务延迟。本发明利用谱聚类算法来将网络拓扑进行分割，更能充分的考虑到网络的延迟特性，因此可以将副本中心的选取分散到离用户更近的节点以降低网络延迟。

(3)降低核心网络流量。由于本发明更能有效的分散副本中心选取的位置到离用户更近的节点上，所以CDN网络和用户间的流量需求只在副本中心到用户之间来回传递，减小了核心网络的流量，从而特高了网络的健壮性减低了拥堵发生的可能。

附图说明

图1是传统网络、CDN网络模型图。

图2是本发明的图例网络的虚拟化过程示意图。

图3是本发明的聚类处理流程示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合实施方式和附图，对本发明作进一步地详细描述。

本发明的网络功能虚拟化环境下的内容交付网络服务器优化部署方法的实施包括NFV环境下的CDN网络模型化、谱聚类算法划分子图和副本中心选取，具体为：

(1)NFV环境下的CDN网络模型

图2(a)所示为实际的物理网络拓扑，包含通用的服务器、大型数据中心和云数据中心等计算节点以及路由器交换机等功能节点。在网络虚拟化(NV)环境中，物理网络的一切节点和带宽都可以虚拟化为计算资源和带宽资源，如图2(b)所示。而NFV技术可以在不同的计算节点部署相同的网络功能软件或者在同一计算节点上部署不同的网络功能软件。在本专利中，我们主要是在不同的计算节点上部署相同的网络功能。因此原问题在底层的物理网络上部署副本服务器转变为在抽象的上部署副本服务器。这样做可以屏蔽掉底层的不同网络实体，而专注于副本服务器的选取。

(2)谱聚类算法划分子图

令G＝(V,E)表示图1(b)中的网络拓扑图。其中V表示节点聚类集合，E表示链路结合。d₁,d₂,...,d_n表示节点聚类集合中各个节点的流量需求，下标n表示总的节点个数。如果节点和节点之间有链路连接，利用公式(1)计算的相似度，否则相似度均设为0。

w_ij＝(|d_i-d_j|)^2.5,(i≠j)(1)

利用公式(2)求的相似度的邻接矩阵

矩阵D＝dia(dr₁,dr₂,...,dr_n)为度数矩阵，其中dr_i(i＝1,…,n)由公式(3)求出

dia为对角符号，表示对角矩阵，其余矩阵项为零。

利用公式(4)求得拉普拉斯矩阵L：

L＝D-W(4)

利用公式(5)求得拉普拉斯矩阵L_sym

L_ysm＝D^-1/2LD^-1/2(5)

利用matlab求得L_ysm的所有特征值λ₁,λ₂,...,λ_n其中λ₁≤λ₂≤...λ_n及其对应的特征向量u₁,u₂,...,u_n(特征向量为列向量u_i＝(u_1,i,u_2,i,...,u_n,i)^T)。取特征值λ₁,...,λ_k(k为要放置的副本服务器个数，此值应小于n)对应的特征向量u₁,...,u_k。将此k个特征向量按列排列形成矩阵U_n×k＝(u₁,...,u_k)。求矩阵U按行所得归一化的矩阵T＝(t_ij)_n×k,其中矩阵元素t_ij按照公式(6)求得

对矩阵T按行取得向量y₁,y₂,...,y_i,...,y_n，其中向量下标i对应矩阵T的第i行。利用k-mean算法对y₁,...,y_n进行聚类。

其中k-mean算法的步骤如下在n个向量中，首先随机选取k个向量作为中心。

②遍历其他非中心向量，按照公式(7)计算非中心向量到k个中心向量的距离

③对每个非中心向量，将此非中心向量与距离最小的中心向量划为一类。得到聚类结果C₁',...,C'_k，其中每个集合中的元素均是代表y向量的下标值。

对每个聚类结果，重新计算出一个中心向量，此向量到聚类结果中其他节点的距离之和最小。因此得到了k个新的中心向量。

⑤重复步骤②-，直到新更新的k个中心与更新前的中心距离差小于。

⑥得到k-means聚类法对向量y₁,...,y_n的聚类结果为C₁,C₂,...,C_k(其中每个集合中的元素>

通过k-means算法后，我们得到了聚类结果C₁,...,C_k，其中每个集合中的元素也与网络拓扑G＝(V,E)中节点的下标相对应。利用公式(8)求得网络拓扑的聚类集合，即节点聚类集合A₁,A₂,...,A_k：

A_m＝{i:i∈C_i},m＝1,…,k(8)

到此为止，图的聚类结束，我们得到了不同的聚类集合，及A₁,...,A_k。接下来要在每个聚类集合中选取一个合适的节点作为副本中心节点来为所有其他需求节点服务。

(3)副本中心选取

对于每个聚类集合，遍历聚类集合的每个节点，计算其为为集合中其他节点服务的成本总和cost，具体计算见公式(9)：

d_i表示聚类集合A_m中节点v_i的流量需求，v_r表示，c_ir表示从节点v_i到节点v_j的链路长度(用跳数表示)，p为单位带宽成本。

选取成本总和cost最小的节点作为每个聚类集合的副本中心节点。

综上，本发明将虚拟CDN网络副本服务器的放置问题与聚类问题相结合更能有效的解决虚拟CDN网络的放置。