融合多维特征的ISP网络拓扑匹配优化仿真

2021-11-17高雅娟王玉峰

计算机仿真 2021年2期

高雅娟，王玉峰

(中国矿业大学银川学院，宁夏银川 750021)

1 引言

ISP发展之初，将接入服务作为主体，进行ISP网络拓扑匹配优化，可以实现对网络的维护，汇聚邻近节点，避免设备之间的异构性与不兼容性，从而给用户制造稳定安全的网络环境，但是缓解网络压力程度较低。

针对上述问题，相关研究人员给出如下解决方案。文献[1]在粒子群优化基础上实现网络拓扑匹配的优化。该算法结合SDN方法将全局网络拓扑数据进行可视化处理，利用粒子群优化，结合所处网络链路资源状态等数据，将通过最小优化获取链路最大利用率为目标进行全局优先匹配。实验证明该方法能有效加强网络吞吐量。文献[2]利用最优子网的虚拟网络映射算法，对满足约束条件的虚拟节点进行合并，通过广度优先搜索方法构建子网集合，达到粗化网络拓扑目的，并将粗化后的虚拟网络映射到最佳子网络中。这种方法可以减少链路映射跳数，提高网络请求接受率。文献[3]基于网络拓扑结构，在反馈过程中计算AC值，利用邻接矩阵作为反馈路径，提出一种可达中心性算法，更准确、有效地识别出重要节点。

上述优化方法虽然一定程度上缓解拓扑不匹配问题，但是没有构建明确的拓扑性能评价指标，无法精确衡量拓扑一致性。基于此，本文融合多维特征对ISP网络拓扑匹配进行优化。其创新之处在于构建合理性能评价指标，对ISP网络无向图进行多维特性分析，融合多维特征，通过节点加入、退出、失效等过程，使匹配程度达到最大化，实现网络拓扑匹配优化。

2 ISP网络拓扑匹配优化性能指标构建

现阶段，覆盖网络和拓扑匹配程度的指标主要指伸缩比。其中常用的是路径伸缩比(PS)与时延伸缩比(LS)。文本通过时延伸缩比表达网络拓扑匹配程度，其公式如下

(1)

式中，n代表网络中节点数量，i与j为节点排列序号，0≤i，j

LS主要表示网络时延方面的匹配程度，只能大概的进行反映，无法得到拓扑匹配的详细特征[4]，因此精准度较低。但是拓扑结构的匹配度对于网络结构的改变与优化起到关键作用，如果可以获得局部匹配特征，不但能提高LS，还能改善整个ISP网络的QOS。因此，本文对全局拓扑匹配比GTMR与局部邻居节点准确度LNA两个指标进行定义，从而更准确的得到拓扑匹配的详细信息。

2.1 全局拓扑匹配比定义

GTMR用于描述链路匹配程度，其描述不同网络中相互匹配的链路数量和总链路数量的比值，表达式如下

(2)

2.2 邻居节点准确度定义

LNA值邻居节点之间的匹配比例，关系式如下所示

(3)

图1 不同邻居节点集合关系示意图

假设h=1，表示统计节点的1跳邻居节点的准确度。此时整个网络中LNAi为1的节点数量与覆盖网络节点数量的比值情况通过下述表达式获取

(4)

式中，n为节点总数量，n≤i

3 融合多维特性的ISP网络拓扑匹配优化

3.1 多维特性分析

本文利用无向图G对多维特征进行分析，G能够通过对称邻接矩阵A代表[6]。G中的i与j节点之间存在边关联性，则Aij=Aji=1，反之Aij=0，Aji=0。一个图的特征值其实是它的邻接矩阵特征值，因此分析多维特性对优化网路拓扑匹配具有重要价值。

1)谱密度

无向图G的谱其实为该图邻接矩阵A的特征密度值[7]，通常表示为ρ(λ)。很对有限系统来说，ρ(λ)能够描述为有关特征值的δ函数之和

(5)

假设N→∞时，它收敛于一个连续函数，这时λi表示此无向图的邻接矩阵特性值中第i个特征值。谱密度能够描述特征值的分布规律。

现有研究成果说明ER随机图的谱密度呈半圆状，并且底边区域呈指数分布。而无标度图的谱密度呈对称连续函数，此函数的中间部分为三角形，两边为幂律分布。

上述分析表明，ISP拓扑图不是ER随机图，其属于一种无标度图，但又不满足BA模型的分布。

2)无符号拉普拉斯谱

无向图G的无符号拉普拉斯矩阵|L|的定义式为

|L|=D+A

(6)

式中，D为G的节点度对角矩阵，A为邻接矩阵。无符号拉普拉斯谱(SLS)即为|L|特征集合。结合代数图原理说明，在单位矩阵的所有线性组合里，无符号拉普拉斯谱是划分不同类型图效果最显著的谱，同样表明，SLS可以描述拓扑性质。

SLS的分布特征值为降序排列，λi的排列顺序按照(i-1)(N-1)进行规格化处理[8]。其中，N表示节点数量，虽然子图之间规模与平均度不尽相同，但是SLS分布情况非常相似，特征值为1的概率都很高，且尾重特性及其相似。通过幂律拟合结果得出，所有子图中全部高于1的特征值和排列顺序之间均满足幂律分布规则，特征指数较为相近。

3)规格化拉普拉斯谱

无向图G的规格化拉普拉斯谱(NLS)矩阵L的定义式为

L=D-1/2×L×D-1/2

(7)

式中，L为G的拉普拉斯矩阵，L=D-A，D与A具有相同含义。NLS属于L的特征集合，经过规格化的拉普拉斯特征值区间为[0，2]，按照升序排列结果为：λ1≤λ2≤…≤λN。NLS的分布特征比较相似，均呈三个台阶状分布，并且重数相对大的特征值位置大致相同。

3.2 匹配优化算法实现

对上述三个多维特征进行融合，利用面向测量的方式，优化网络拓扑匹配。优化算法的实现主要包括新节点加入、节点失效与退出三个部分。

图2 优化方法框架图

3.2.1 节点加入

(8)

根据上述条件，判断出新加入节点需要符合如下连接条件：

1)网络成本归一化度量

将节点距离当作网络成本度量。若节点nodem+1和节点nodei发生连接，其中i∈{1，2，…，m}。两个节点构建的连接成本归一化度量表示为mDi。

则mDi度量越大，构建链路所花费的成本越小。

2)网络时延归一化度量

将平均最短路径距离当作时延度量。如果有节点nodem+1与节点nodei存在连接时，且i∈{1，2，…，m}。在连接建立后，网络时延表示为hi，两个节点构建的时延归一化度量为mHi。此时度量值mHi越大，网络时延越小。

3)网络健壮性归一化度量

将网络遭到一定威胁后仍然正常传输的流量当作健壮性度量。在nodem+1和nodei两个节点发生连接后，网络受到随机攻击或恶意攻击后仍可以进行正常通信的节点占比情况表示为ri，节点nodem+1与nodei的网络健壮性归一化度量表示为mRi，归一化度量越高，网络越健壮。

4)网络吞吐量归一化度量

将网络临界数据出现率作为吞吐量度量。假设在节点nodem+1与nodei建立联系后，网络吞吐量用ti表示，则两个节点连接的吞吐量归一化度量为mTi。此时，该度量越大吞吐量越高。

5)连接判断度量measure

如果在优化过程中成本权重、时延权重、健壮性权重与吞吐量权重分别表示为：wD、wH、wR与wT，因此新加入节点nodem+1和存在最大连接度量measure并且没有构建链路的节点i建立新链路。假设此时出现很多节点均满足该条件，需要随机挑选一个备用节点与新加入节点构建连接。其中

measure=wDmDi+wHmHi+wRmRi+wTmTi

stwD+wH+wR+wT=1

(9)

其中，wD∈[0，1]，wH∈[0，1]，wR∈[0，1]，wT∈[0，1]。

图3 节点加入算法

其中DR存在动态变化性质，在算法初始化过程中，DR=R，此时建立上图中(a)所示的示意图；在DR发生改变时，需要对J与新产生的DR以及子节点存在的关系进行判断，结合三角形边长关系，可以得到三种节点跳数发生的处理情况，从而确定最佳父节点添加到网络中。

3.2.2 节点退出

为确保整个ISP网络中节点之间的兼容性、贯通性，维护邻居关系和层次关系，并且降低网络拓扑的维护成本，把需要退出节点的父节点设为动态根节点形式。在网络节点退出过程中，必须对其子节点与父节点做合理调整。假如退出的节点为叶子节点，需要将退出消息发送到父节点，之后直接退出即可；假设不属于叶子节点，此时需要先将退出消息传送给父节点，并且找到更佳的节点代替该父节点。

3.2.3 节点失效

若节点发生失效情况，该节点不能将消息传输给父节点与子节点。此时，需要通过广播方式将消息传送到其它节点。假设失效节点是叶子节点，利用发现节点把失效信息传递给父节点；当失效节点不属于叶子节点时，将失效节点全部子节点退出，使其重新回到网络中。以此完成了ISP网络拓扑匹配优化。

4 仿真研究

为验证所提方法的合理性，本文利用BRITE拓扑生成器形成六个不相同规模的网络拓扑：{100，200，400，800，1600，3200}，节点最小度设为3，且位置符合随机分布条件。仿真中，将本文方法与文献[1]、文献[2]、文献[3]方法进行对比，以邻居节点准确度最大值、节点消耗个数与全局拓扑匹配比作为评价指标。

邻居节点准确度最大值对比测试获得的实验结果如表1所示：