基于拓扑分割与聚类分析的虚拟软件定义网络映射算法

陈 港，孟相如，康巧燕，阳勇

（空军工程大学信息与导航学院，西安 710077）

0 引言

网络虚拟化技术通过将网络服务和网络基础设施在逻辑上进行解耦，降低了网络服务的局限性，增强了部署灵活性，实现了网络资源的可靠管控，加速了网络架构和技术上的创新［1］。由于基于传统网络的网络虚拟化存在诸多问题和限制，专家学者将软件定义网络（Software Defined Network，SDN）引入网络虚拟化，形成虚拟软件定义网络（virtual SDN，vSDN）［2-4］，其中的一个关键技术问题是虚拟网络映射。作为vSDN 中的映射，相较于一般的虚拟网络映射［5］，它的映射约束、优化目标、网络复杂度都具有更高的要求［6-7］。

Tan 等［8］考虑网络时延和控制器与转发设备之间的不相交路径数，提高vSDN的生存性并降低网络时延；Kuang等［9］考虑了交换机的流量和内存约束，节点映射策略为将节点根据其重要度指标进行树形拓扑的降序排列后使用贪婪算法进行匹配映射，链路映射策略为选择带宽富裕度高、跳数少的链路优先映射；冉金鹏等［10］采用优化的果蝇算法进行映射方案的求解，在负载均衡、请求接受率和控制延迟等指标上取得较好效果；王健等［11］基于蚁群混合遗传算法映射节点，利用K-最短路径算法映射链路，提高了接受率，并较好地改善了节点和链路的平均利用率以及映射的收益开销比。文献［8-11］中将节点和链路映射分开考虑，没有注意到节点与链路之间的关联性。Li等［12］提出了一种拓扑感知的虚拟软件定义网络映射方法：节点映射时，采用贪婪算法优先映射虚拟网络和物理网络中资源度高的节点；链路映射时，分别采用K-最短路径算法和多商品流算法映射控制链路和数据链路，采用节点重映射提高映射成功率。该方案有效提升了映射效率和收益开销比，通过在链路映射失败时采用节点重映射的方式较为粗略地考虑了节点与链路之间的拓扑与资源关联性，但其算法开销较大，同时未考虑vSDN 中交换机以及控制器内存约束。Yan 等［13］提出了一种基于虚拟软件定义网络的启发式要素感知的资源高效利用算法，该方案基于K-Means 聚类进行节点的匹配映射，采用K-最短路径算法完成链路映射。该方案提升了请求接受率，降低了通信延迟，但其仅根据节点的计算能力、内存以及总的连接带宽这三个要素进行聚类匹配，忽略了节点与链路之间的关联性，未考虑网络的拓扑特征。

总结发现，大部分基于vSDN的映射算法没有充分考虑节点与链路之间的相关性。虚拟网络和物理网络中的节点与链路之间存在着一定的拓扑结构以及对应的计算资源和带宽资源，分开考虑节点映射和链路映射时相当于割裂了两者之间在拓扑结构和资源数值之间的关联性。为在vSDN 映射过程中更全面地考虑节点与链路约束，以及节点与链路之间的相关性，本文提出了一种基于网络拓扑分割与聚类分析的虚拟软件定义网络映射算法（Topology Segmentation and Clustering Analysis-vSDN mapping algorithm，TSCA-vSDN）。本文算法的主要思路如下：1）通过将物理网络和虚拟请求网络按照交换机到控制器的最短跳数值展开为树状拓扑图，实现对网络拓扑的感知和分割，并依据节点的拓扑属性区分出关键节点和链路，避免出现关键节点或链路过早高负荷映射，以提高整体的请求接受率；2）通过定义节点资源度和网络资源度以及节点紧密度，使用聚类算法依据节点的多项属性值进行聚类分析，实现对底层物理网络资源的动态感知；3）通过将链路约束分散到节点带宽资源以及节点的度约束考量，对不符合链路要求的节点进行重映射，充分考虑节点与链路之间的资源与拓扑相关性。仿真结果表明，该算法有效地提升了基于SDN架构的虚拟网络映射在较低连通概率物理网络下的请求接受率。

1 网络模型与评价指标

1.1 网络模型

本文假设处理的物理网络和虚拟请求网络拓扑图中任意两点间直连边的条数最多为1 条，物理网络和虚拟网络请求拓扑都为非平凡的简单连通图。本文假设控制器为带内部署，且控制器不参与交换机之间的数据转发，只负责控制信令的分发。

1.1.1 物理网络

1.1.3 网络特征分析

为了对不同的网络作出区分，以更好地选择适配的映射策略，本文针对物理网络和虚拟网络给出以下一系列定量的评价指标。

定义节点资源度为p(ni)，为减小各节点因三项资源属性值存在的偏差所导致的节点资源度误差，设立系数α、β、γ，有：

参考文献［12］，定义网络Gi中节点ni的紧密度为CL(ni)，该名词表征节点在拓扑图中的中心程度。令紧密度CL(ni)为节点到其余各节点最短跳数倒数的和，计算式如下：

式（7）表明，到其余各节点最短跳数倒数的和越大的节点，其紧密度就越高，反之就越低。

定义节点控制中心度为CC(ni)，表征拓扑网络中接近控制器的节点中心程度，以方便后续虚拟网络根节点的映射。令节点控制中心度CC(ni)为节点紧密度和交换机节点到最近控制器节点最短跳数之间的比值，即：

式（8）表明，紧密度相同的节点中，到最近控制器节点最短跳数越小的节点，其节点控制中心度就越高，反之则越低。

定义节点关键度为节点控制中心度与节点的度之间的比值，记第i个节点的关键度为CR(ni)。为加快算法收敛，将关键度高于节点关键度平均值20%的节点视为关键节点。关键链路的筛选标准为：关键节点直连的链路。节点关键度计算式为：

式（9）表明，节点控制中心度相同的节点中，度越小的节点，其节点关键度就越高，反之则越低。

1.2 虚拟网络映射模型

虚拟网络映射模型可抽象为带权重的无向图Gv到Gs子集的映射Gv(i)→Gs(i)∈Gs。该映射定义为将虚拟请求网络中的虚拟节点和链路对应映射到物理网络中的物理节点和路径，在映射过程中，需要满足节点的CPU 约束，流表空间TCAM 约束，以及链路的带宽（BW）约束。本文采用两阶段映射法，先映射节点后映射链路，如图1所示。

图1 虚拟SDN映射模型Fig.1 Virtual SDN mapping model

1.2.1 节点映射

对于同一个虚拟网络请求，每一个虚拟节点必须映射到不同的物理节点上，但同一个物理节点上可以存在多个不同虚拟网络请求的虚拟节点。由于物理SDN 控制器节点采用带内部署，所以在映射虚拟交换机节点和虚拟SDN 控制器节点时可以将其统一考虑为虚拟节点映射。假设每一个虚拟网络请求有且只有一个虚拟SDN 控制器负责该网络的数据转发和流量控制。如果虚拟节点映射到物理节点则为Xij=1；否则Xij=0。虚拟节点nv映射到物理节点ns的过程表示为MN，即：

约束条件如下：

其中：式（11）表示待映射虚拟节点CPU 资源需求不能大于被映射物理节点的剩余CPU 资源；式（12）表示待映射虚拟节点TCAM 资源需求不能大于被映射物理节点的剩余TCAM 资源；式（13）表示同一虚拟网络中每一个虚拟节点只能映射到一个物理节点，任意物理节点至多承载同一个虚拟网络中一个虚拟节点。

1.2.2 链路映射

对于虚拟网络请求中的某一条链路而言，它可以对应映射到物理网络中的一条具体的链路，也可以映射到物理网络中由多条链路组成的一条具体的路径。为了在避免歧义的同时更准确地描述链路的映射，将虚拟链路的映射过程定义为虚拟链路与该虚拟链路两端节点映射后对应物理节点间链路或路径的映射。定义底层物理网络两点间任一条非闭环的路径为。将虚拟链路ev映射到物理链路es的过程记为ME，即：

约束条件如下：

式（15）表示待映射的虚拟链路带宽需求不能大于被映射物理节点的剩余带宽资源。

1.3 评价指标

定义1虚拟网络请求接受率。

参考文献［10］，定义为长期的时间段T中成功映射的虚拟网络请求数量与收到的虚拟网络请求数量的比值，表示为AR，如式（16）所示：

其中：vSDNRe(t)表示在时刻t成功映射的虚拟网络个数；vSDNGe(t)表示在时刻t收到的虚拟网络个数。

2 虚拟SDN请求映射算法

本章首先介绍拓扑分割物理网络，并计算物理网络和虚拟网络的拓扑和资源指标，然后对物理网络节点基于拓扑和资源指标进行聚类分析，将虚拟网络的节点根据物理节点聚类分析结果进行匹配映射，并在节点映射前进行相关的链路约束判断，节点映射成功后再映射链路，最后对算法的时间复杂度进行计算说明。

2.1 物理网络拓扑分割和资源指标计算

物理网络拓扑分割和资源指标计算步骤如下：

图2 物理网络拓扑分割示例Fig.2 Example of physical network topology segmentation

图3 树形拓扑网络示例Fig.3 Example of tree topology network

图4 延展后的树形拓扑图Fig.4 Extended tree topology diagram

4）计算物理网络和虚拟网络的节点度d(ni)、紧密度CL(ni)、控制中心度CC(ni)。将虚拟网络中紧密度最高的节点作为根节点，其余节点按照到该根节点的最短跳数作为层数转化为树形拓扑网络。

5）计算物理树形拓扑网络的关键节点和关键链路，在映射时只有当关键节点的剩余节点资源度与物理子拓扑网络中平均节点资源度的比值大于一定值时才可以被映射，具体比值记为ratio，通过后续实验得出。但关键链路不受影响，即当关键节点不被映射时依旧可以充当其余节点的数据转发节点，与其直连的关键链路可以被虚拟链路映射。为避免出现关键链路过早耗尽带宽的情况，在链路映射时设置链路权重随链路剩余可用带宽降低而提高。

2.2 节点聚类分析和链路映射

为了充分利用物理网络和虚拟网络的拓扑信息以及资源信息，首先针对物理网络节点的拓扑指标进行聚类分析，分割为k个节点拓扑属性相近的集合；接着，计算虚拟节点到各聚类中心的欧氏距离，选取欧氏距离值最小的集合作为虚拟节点待映射的物理节点集合；然后，按照虚拟网络的树形拓扑网络，从根节点开始依据广度搜索顺序映射虚拟节点，并计算虚拟节点和选取集合中所有节点的资源指标的欧氏距离，选取欧氏距离值最小的物理节点作为虚拟节点的映射节点；最后，除映射虚拟网络根节点外，对每一个虚拟网络节点进行链路约束初步判断，当所有节点链路约束符合后开始链路映射，若仍出现矛盾则进行节点重映射，直至映射成功或遍历后映射失败。

映射算法流程如图5 所示，图中否1、否2、否3、否4 代表不同的转折条件，分别为该节点不满足约束但集合ki未遍历、集合ki已遍历但k个聚类集合未遍历、k个集合已遍历但拓扑网络未遍历、都已遍历未找到合适节点。节点映射时，首先选择合适的物理拓扑网络并映射虚拟网络的控制器，然后映射虚拟网络交换机节点。

图5 映射算法流程Fig.5 Flow chart of mapping algorithm

映射控制器时，首先计算物理子拓扑网络与虚拟网络的优先级pr，然后计算优先级变量pr()（简记为prs）和pr()（简记为prv）的欧氏距离d0，优先考量欧氏距离值最小的物理拓扑网络映射虚拟网络。

其中各变量计算式如下：

若该物理拓扑网络控制器节点满足虚拟网络控制器节点的资源约束，则确认虚拟网络控制器映射到该网络的物理控制器，若不满足则顺序考量下一个物理子拓扑网络，直至遍历完全都不满足约束时则映射失败。

首先选取d1值最小的节点集合cluster(j)(j∈k)作为该虚拟节点的待映射物理节点集合，然后根据物理节点和虚拟节点的C(ni)、TC(ni)、Bw(ni)指标，在集合cluster(j)中计算虚拟节点和物理节点三个资源指标的欧氏距离d2，将集合中的节点按照欧氏距离d2升序排列。

其中各变量计算式如下：

具体映射虚拟网络节点时，首先映射虚拟网络的根节点，然后依照对树形拓扑网络的广度搜索顺序依次进行虚拟节点的映射。具体过程为：排除掉物理控制器节点，然后针对关键节点判断关键节点的节点资源度Rp()是否小于该物理子拓扑网络节点资源度平均值的一半，若小于则跳过该关键节点；否则继续考察物理节点的资源是否满足虚拟节点的资源约束。若考察的物理节点满足虚拟节点的资源约束则对节点进行链路约束初步判断，如果符合判断则将该物理节点作为该虚拟节点的映射节点；若不满足则顺序考察下一个物理节点。若遍历该集合cluster(j)都无法找到符合约束的节点则更换物理拓扑网络。若遍历所有物理拓扑网络仍无法找到符合约束的物理节点，则表明无法成功映射该虚拟网络所有节点，即映射失败。其中，链路约束初步判断的资源需求方为待映射虚拟节点与上层虚拟节点间的链路带宽需求，资源供给方为待被映射物理节点与虚拟网络根节点已映射物理节点间的链路带宽资源。

3）链路映射时，采用K-最短路径算法，在计算两节点间最短路径时，将链路权重设置为物理网络链路带宽最大值与链路剩余带宽的差值加一，以规避关键链路被提前过度映射而降低请求接受率。如果没有找到满足需求的链路，在物理拓扑未遍历完时采用下一个物理子拓扑网络进行节点重映射，若已遍历所有物理子拓扑网络，则进行一次节点重映射，并尽量规避之前已被选择的物理节点，若仍失败则丢弃该虚拟网络请求。如果映射成功则反馈成功。

4）本文提出的TSCA-vSDN 算法，输入为物理拓扑网络和虚拟拓扑网络，输出为节点映射表单和链路映射表单。具体内容如算法1（TSCA-vSDN）所示，其中第1）～4）行计算物理网络中交换机到控制器的最短跳数，并进行拓扑分割；第5）～8）行计算各子拓扑网络的优先度；第9）～12）行进行聚类分析；第13）～27）行根据聚类结果和节点资源属性进行节点匹配映射，输出节点映射表单；第28）～34）行采用K-最短路径算法进行链路映射，输出链路映射表单。

算法1 TSCA-vSDN。

2.3 算法时间复杂度计算

3 算法评估

在相同的底层物理网络环境下，面对不同的虚拟网络请求，针对算法TSCA-vSDN 的请求接受率指标进行仿真实验分析，并与算法KCL-vSDN和To-vSDN进行对比。三种算法的简要描述如下。

1）算法TSCA-vSDN。节点映射时，首先基于K-means 聚类方法对与虚拟节点拓扑参数比例相似的候选物理节点进行聚类，然后根据节点的计算资源选取比例最接近的进行映射；链路映射时，选用K-最短路径算法，在链路映射受阻时采用节点重映射提高映射成功率；算法映射单个虚拟网络的时间复杂度为

2）算法KCL-vSDN。节点映射时，首先基于K-means 聚类方法对与虚拟节点资源比例相似的候选物理节点进行聚类，然后根据网络演算得到的控制要素从集群中选择出最优的物理节点进行匹配映射；链路映射时选用K-最短路径算法［13］；算法映射单个虚拟网络的时间复杂度为

3）算法To-vSDN。节点映射时，采用贪婪算法优先映射虚拟网络和物理网络中资源度高的节点；链路映射时，先采用K-最短路径算法映射控制器到交换机的虚拟控制链路，然后采用多商品流算法映射其余虚拟数据链路，在链路映射受阻时采用节点重映射增加映射成功率［12］；算法映射单个虚拟网络的时间复杂度为

3.1 仿真环境设置

通过文献［14-16］及本文仿真实验发现不同的底层物理网络以及不同的虚拟网络请求，对同一算法的性能有着较大的影响。参考数据中心常用拓扑，采用facebook 数据中心网络拓扑（简记为topo-facebook）和fat-tree 网络拓扑（简记为topo-fat-tree）等两类常见底层物理拓扑结构，以及依靠网络节点和节点连通概率（KP）随机生成的拓扑网络（简记为topomesh），分别作为仿真环境的底层物理网络。

topo-facebook 和topo-fat-tree 都有其较为固定的结构，在给定节点数量的前提下，其链路数量是固定的，为方便对照，本文设置三类物理网络节点总数都为200。实验中链路带宽、交换机计算资源、存储资源等数据参考文献［17］进行设置，具体见表1。

表1 底层物理网络分类及参数设置Tab.1 Classification and parameter setting of underlying physical network

链路带宽设为40 Gb/s，交换机节点计算资源CPU 为12×103，存储资源TCAM 为250 × 103，控制器节点计算资源为交换机的4 倍。本文将其节点总数设为200，控制器个数为4。topo-mesh 为随机网络，为考察物理网络节点总数以及连通概率对算法映射性能的影响，设定节点总数分别为200，控制器数量为4；KP为0.02 和0.03；数据链路带宽以及计算资源CPU 和存储资源TCAM 服从均匀分布，即，单位103］；控制链路带宽为40 × 103，控制器计算资源为交换机计算资源的4倍。底层物理网络分类见表1。

虚拟网络采用topo-mesh 随机网络，考虑到虚拟网络的大小不确定性以及持续时长不确定性，将其节点总数N设为N～U［2，20］的均匀分布，KP为0.5，将其持续时长T设为T～P(λ)，λ=120，240，360，480 的泊松分布（单位为s）。数据链路带宽、节点计算资源CPU 和存储资源TCAM 服从均匀分布，，单位为Mb/s，～U[5× 103，20 × 103]；控制链路带宽为10 Mb/s，控制器计算资源和存储资源为交换机的2倍。

3.2 结果分析

本文采用控制变量法共进行了三组实验。实验一在固定物理环境和虚拟网络请求生存时长的条件下，改变关键节点的剩余节点资源度与物理子拓扑网络中平均节点资源度的比值ratio，探究使得算法TSCA-vSDN 的请求接受率最高的ratio值；实验二与实验三在固定物理网络节点总数和相同连通概率（KP）的条件下，改变物理网络类型和虚拟网络请求生存时长，探究物理网络类型和虚拟网络请求生存时长对三种算法请求接受率的影响；同时实验三在实验二的基础上，更换了一种物理网络类型以及KP，探究不同网络类型、不同物理网络KP对三种算法请求接受率的影响。

3.2.1 实验一

基于topo-mesh（KP=0.026）网络拓扑，在当关键节点的剩余节点资源度与物理子拓扑网络中平均节点资源度的比值ratio分别取0.1、0.3、0.5、0.7、0.9，且生存时长为480 时，对算法TSCA-vSDN的请求接受率进行分析。

由实验一的图6 可以看出，当关键节点的剩余节点资源度与物理子拓扑网络中平均节点资源度的比值取0.5 时，算法TSCA-vSDN 的请求接受率较高。后续实验中该比值ratio都取0.5。

图6 不同比值时算法TSCA-vSDN的请求接受率对比Fig.6 Comparison of request acceptance rate of TSCA-vSDN algorithm with different ratios

3.2.2 实验二

基 于topo-facebook（KP≈0.018）网络拓扑和topomesh(KP=0.018)网络拓扑，将三种算法在不同的生存时长条件下进行映射性能对比。

实验二分别以topo-facebook 和对应KP的随机拓扑为底层物理网络，分析了算法TSCA、KCL 以及To 在面对虚拟请求时长T～P(λ)，λ=120，240，360，480的映射性能对比情况。

从图7～8 中可以看出，当虚拟请求时长在120、240、360、480附近服从泊松分布波动时，算法TSCA 的请求接受率（AR）绝大多数情况下为最高。当虚拟网络请求个数接近1000时，所有指标都趋于平滑、稳定，表明此时已基本消除虚拟网络节点总数以及生存时长的随机波动影响，其数值具备一定的说服力。

图7 基于topo-facebook（KP ≈0.018）物理网络的算法请求接受率对比Fig.7 Comparison of algorithm request acceptance rate based on topo-facebook（KP ≈0.018）physical network

从图7 分析得出，算法TSCA 稳定时的AR随着生存时长的增加出现明显的降低，说明AR稳定时，资源利用率基本已到达该算法利用极限，AR的数值受到了因生存时长增加导致的剩余可用资源的约束。着重分析图7（d）可知，当请求个数为50时，算法TSCA的AR值从1开始陡然下降，说明此时已到达该算法资源利用率极限，随后的大部分虚拟请求映射失败；但当请求个数接近120 时，算法TSCA 的AR值开始回升，因为此时刚开始映射的虚拟请求生存周期已结束，剩余可用资源增加，接下来的部分虚拟请求成功映射，随后AR在一定范围内波动。

对比图7 和图8 可知，两者的底层物理网络topo-facebook和随机拓扑的KP接近，节点总数、控制器数量相同，节点参数相近。分析后发现，三种算法都在随机拓扑上的AR稳定数值更高，算法TSCA 的AR仍然高于其余两者算法，说明算法TSCA 相较于算法TSCA、KCL 更适应topo-facebook 物理网络，能很好地发挥出算法的映射性能，极大提高虚拟网络的请求接受率。

图8 基于topo-mesh（KP=0.018）物理网络的算法请求接受率对比Fig.8 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.018）physical network

3.2.3 实验三

基于topo-fat-tree（KP≈0.026）网络拓扑和topo-mesh（KP=0.026）网络拓扑，将三种算法在不同的生存时长条件下进行映射性能对比，结果如图9～10所示。

图9 基于topo-fat-tree（KP ≈0.026）物理网络的算法请求接受率对比Fig.9 Comparison of algorithm request acceptance rate based on topo-fat-tree（KP ≈0.026）physical network

实验三分别以topo-fat-tree 和对应KP的随机拓扑为底层物理网络，分析了算法TSCA、KCL 以及To 在面对虚拟请求时长T～P(λ)，λ=120、240、360、480的映射性能对比情况。

从图9～10中可以看出，当虚拟请求时长在120、240、360、480附近服从泊松分布波动时，算法TSCA 的请求接受率（AR）绝大多数情况下为最高；当虚拟网络请求个数接近1000 时，所有指标都趋于平滑、稳定，说明此时已基本消除虚拟网络节点总数以及生存时长的随机波动影响，其数值具备一定的说服力。

对比图9 和图10 可知，两者的底层物理网络topo-fat-tree和随机拓扑的KP接近，节点总数、控制器数量相同，节点参数相近。分析后发现，三种算法大都在随机拓扑上的AR稳定数值更高，算法TSCA的AR稳定数值仍然高于其余两种算法，说明算法TSCA 相较于算法TSCA、KCL 更适应topo-fat-tree 物理网络，能很好地发挥出算法的映射性能，极大提高虚拟网络的请求接受率。

图10 基于topo-mesh（KP=0.026）物理网络的算法请求接受率对比Fig.10 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.026）physical network

对比实验二与实验三可以看出，当虚拟请求网络的生存时长不高于360时，算法TSCA 在topo-fat-tree中能取得更好的AR；当虚拟请求网络的生存时长高于480 时，算法TSCA 在topo-facebook中能取得更高的稳定AR值。

通过实验二与实验三可以看出，当虚拟请求网络的生存时长在120、240、360、480 附近服从泊松分布波动时，针对连通概率较低的底层物理网络，如topo-facebook 和topo-fat-tree以及随机分布的物理网络，算法TSCA 的请求接受率稳定值都高于算法TSCA、KCL，能更好地发挥出算法的映射性能。

4 结语

本文所提出的算法TSCA-vSDN 首先通过拓扑分割缩小节点和链路映射搜索范围；然后通过聚类分析节点的拓扑树形和资源属性，优化节点映射匹配过程；最后通过将链路约束作为节点约束的一部分，充分利用节点与链路相关性，提高映射请求接受率。

通过两组对比实验，将算法TSCA-vSDN 与算法KCLvSDN 和To-vSDN 在不同底层物理网络拓扑（如facebook 物理网络、fat-tree 物理网络以及随机分布的物理网络）、不同的虚拟网络请求持续时长条件下的映射性能进行对比，实验结果表明算法TSCA-vSDN 在提高请求接受率方面性能较优。本文所提出的算法TSCA 虽然对请求接受率有较为明显的提升，但它的计算开销也更大，如何在尽量保持较高请求接受率的条件下优化计算流程，进一步降低其计算开销，同时增加对收益与成本比值和负载均衡等方面的优化研究，将是下一步拓展加深的研究课题。