网络基础设施中重要网元子图的确定

刘 峥,郭舒婷,周绮凤,李 涛

(1.南京邮电大学计算机学院,江苏 南京 210023;2.江苏省大数据安全与智能处理重点实验室,江苏 南京 210023;3.厦门大学航天航空学院,福建 厦门 361005)

目前,现代大规模复杂网络基础设施的日常运维往往依赖于集中式网络监控平台和人工干预来保证网络服务的可靠性[1-2].重要网元的监视和管理对保障网络服务的可靠性至关重要.网元的重要性往往由网络管理员根据经验来判断,然而在网络基础设施规模日益增大和网络管理人力资源有限的背景下,对于承载重要业务的网元相对较易确定,而对于处于网络基础设施拓扑结构中的重要节点的判断却很难由人工判定,常常出现错误及遗漏.

网络基础设施中面向业务的网元子图是指网络基础设施中承载具体业务的重要网元的拓扑子图,也包括其他非重要网元.通过确定面向业务的网元子图,可以满足大规模网络基础设施中运维需求,仅需投入较少人力对这些拓扑子图中的网元进行重点监控,就可以提高故障分析的效率,节省网络基础设施运维的成本.目前在网络基础设施运维中并没有成熟的网元子图的确定方法,传统的方法是从发生故障的网元出发,将其邻域网元所组成的子图作为网元子图.

在社交网络研究领域,已经有一些学者对节点的影响力进行了研究,并将高影响力的节点作为重要节点.Kempe等[3]研究了影响最大化问题,集中介绍了描述节点激活行为的模型.Leskovec等[4]提出一种高性价比的懒惰前向(cost-effective lazy forward,CELF)贪心算法的优化策略,运用独立级联型的次模特性(sub-modularity),大大降低了选择最具影响力节点的工作次数.此外,Lei等[5]提出了一个能够在市场病毒式营销中学习到传播概率的方法.Farajtabar等[6]通过对社会活动进行建模,构建了一个凸优化框架确定激励用户刺激社交活动所需的活动水平.但这些社交网络中的影响力评估算法着重关注社交网络中信息的传播模型,而不是故障传播模型,并不适用于评估网络技术设施中网元的影响力.在图数据挖掘的研究领域中,已经有一些学者提出了一些节点之间关系的度量方法.Jeh等[7]提出了一种通过节点邻域的相似性来度量节点之间的相似度的方法,称为SimRank,表征从两个节点出发的随机游走的期望相遇距离.Palmer等[8]定义了一个距离函数来衡量两个属性数据集之间的相似度,用图模型来表示属性值,两个属性值之间的距离定义为重启随机游走的逃逸概率.但这些重要性的度量方法都没有考虑到网络基础设施中网元重要性的特点,没有将重要节点的邻域节点进行深入分析.此外,由于拓扑结构和承载业务两者的异构性,也不能直接利用上述方法度量网元的重要性.另一方面重要网元子图的确定与社交网络研究领域中的社区发现有一定相似.目前,对图上的社区发现算法主要包括:基于谱分析的聚类算法[9],基于图划分的聚类算法[10],基于层次的聚类算法[11]以及基于密度的聚类算法[12].Liu等[13]搜索网络中的极大团,并依据其连接情况合并极大团来获得网络的社区结构.Pons等[14]提出利用长度为l的随机游走来度量图上两个节点的相似度用于社区发现.Tong等[15]也提出了利用重启随机游走在图数据上发现中心子图.但社交网络中的社区发现偏重于寻找社交网络中的相似节点的集合,而不是根据节点的影响力来判断节点的影响范围.

为了同时考虑网元连接关系的重要性和承载业务的重要性,本研究将业务转换为图模型上的点,利用邻域影响度来衡量网元之间(图上节点之间)的连接关系,并由此评估节点的重要性.识别重要节点后,根据其重要性衡量标准,将确定网元子图的问题变成一个在图上对节点进行分组的问题.为此,本文中提出了一个3步的框架来识别重要网元子图:

1) 评估网元节点的重要性,寻找重要的网元节点;

2) 从每个重要网元节点出发,根据节点之间的相关性,生成网元重要子图;

3) 融合网元重要子图,形成网元重要子图集合.

1 评估网元节点的重要性

为了同时考虑网元连接关系的重要性和承载业务的重要性,首先需要弄清重要网元的特征.从大规模复杂网络运维实际出发,网元的重要性主要体现在以下两方面:1) 重要网元与其他网元的直接连接或间接连接的关系较密切,体现在重要网元与其他网元之间的连通路径较多,一旦重要网元发生故障,可能会影响其他网元之间的通信或服务交互.2) 重要网元所承载的业务的数量较多,级别也较高.一旦重要网元发生故障,会影响到承载同样业务的其他网元服务的稳定性.

根据重要网元的特征，本研究将业务转换为图模型上的节点,再利用邻域影响度捕捉节点的连接关系,进而将连接关系的重要性和承载业务的重要性统一起来.本文中的网络基础设施用图模型G=〈V，E〉表示,其中V是所有网元节点vi所组成的集合,E表示网元之间连接关系的集合,即图上两个节点之间的边ei的集合.

对于用图模型G表示的网络基础设施,令A表示有权重图的邻接矩阵.A(i,j)表示边eij=(vi,vj)上的权重.基于随机游走的概念,在图G上的影响力扩散是指从某一节点v0出发,并按一定概率在图上沿节点和边随机移动.假设目前第vs步的随机游走在节点s+1上,则第s+1步将以概率Pst移动到vs的某一相邻节点vt上,即vt∈N(vs),其中N(vs)表示节点vs在图G上的所有相邻节点的集合,其转移概率Pst=A(s,t)/∑vk∈N(vs)A(s,k),所经过的节点路径组成一个马尔科夫链.令D表示一个对角矩阵,其中对角线上某个值d(s)=∑vk∈N(vs)A(s,k),则对应的马尔科夫链的转移概率矩阵P的矩阵表示为P=D-1A.从节点vj到节点vk的长度为l的概率Qjk可以通过转移矩阵P经过l次乘积后相应位置上的对应元素来表示,故Q=(Qjk)=Pl.

当G为非二项图时,由于马尔科夫链的无记忆性,从任何节点出发,经过无限步的影响度最后落在同一个节点vk的概率只和最终节点的度的大小有关.可以通过返回概率c,将影响度倾向于在出发节点的周围的局部的连接关系,同时只考虑长度为l的随机游走,即邻域影响度所能达到的节点与出发的节点的最短路径长度不超过l.值得注意的是,本文中提出的算法可以根据不同需要自由地增大l以扩大邻域的范围.

定义1邻域影响度:若随机游走的长度为l,则节点vj到节点vk的邻域影响度(影响力)为

其中,0

由此可知邻域影响度的矩阵可表示为:

(1)

根据邻域影响度(影响力)矩阵,重要网元节点的重要性可定义为

S(vj)=∑vk∈VΠjk,

(2)

其中,重要性分值S(vj)表示节点vj的影响力.是根据重要节点对其他节点的影响力,即邻域影响度长度的总和来决定.

式(2)定义网络基础设施图模型G上的重要性,为了同时考虑承载业务的重要性,本文中提出将业务也转换为图模型上的点,如图1所示.假设网络基础设施中的业务有{w1,w2,w3,…}.每种业务wj在图上都映射相应的节点wj.如果某网元承载某业务,则在图上增加连接网元对应节点vi到业务对于节点wj的一条边e(vi,wj).这样生成的包括业务信息的图模型用G′表示.在图G′上利用邻域影响度来统一衡量节点的重要性,可同时衡量连接关系的重要性和关于业务的重要性.对于业务的级别,可以通过给边e(vi,wj)赋予相应的权重,为简化描述,本文中假设所有业务级别都一样,即相应的边的权重为1.下文中将不区分G′和G,两者都表示包括业务信息的图模型.

图1 业务转化为图上的节点Fig.1 Service vertices in the graph

网元节点重要性评估算法步骤为:

1) 计算转移概率矩阵P.将业务转化为图上业务节点,利用图上网元节点的邻接关系和网元承载业务情况得到邻接矩阵A,根据P=D-1A计算转移概率矩阵P.

2) 计算影响力距离矩阵Π.设置合适的随机游走长度l和随机游走的重启概率c,根据式(1) 计算Π.

3) 根据式(2) 计算网元节点的重要性分值.

4) 生成重要网元节点列表.重要性分值大于ξ的网元节点称为重要节点,其中ξ表示重要网元节点重要性的阈值.图2所示的是基于本文中实验部分数据集的网络基础设施图G上的网元重要性的分布情况.通过对网元节点影响力的曲线拟合,可见网元节点影响力分布曲线与幂律分布函数y=1.72x-0.06-1的曲线基本吻合,遵循幂律(power law)分布,因此确定重要节点的重要性的阈值ξ并不是绝对的,而是相对的.在下文3.2节对ξ的取值进行了讨论.

图2 网元节点影响力分布曲线Fig.2 The curve of vertex influence distribution

由于评估节点重要性需要对两个矩阵进行乘积,所以整体的时间复杂度是O(ln3),其中n是图中的网元个数.在实际应用中,可以利用快速稀疏矩阵乘法来代替通常的矩阵相乘算法以加快计算速度.

2 生成重要网元子图

重要网元子图应包括重要网元节点和与重要网元节点相似度较大的节点,即被重要节点影响大的节点,有如下几个特点:1) 重要网元子图应该是一个连通图;2) 重要网元子图应该包括重要节点;3) 重要网元子图应该包括被重要节点影响的节点.

本文中提出了一个类似高维空间中密度聚类思想的扩展策略,从重要网元节点扩展出网元子图.生成重要网元子图的算法步骤如下:

1) 从重要网元节点列表中选择当前重要性分值最大的网元vj,初始化子图gs为空,并将该网元插入到空节点图中,从重要网元节点列表中删除vj,标记vj为已访问节点,设置子图扩展的停止条件阈值ε,计算公式为:

ε=max(Π(j,∶))×rlb，

其中rlb的取值为幂律分布曲线的拐点位置.

2) 初始化最大堆H,将所有未被访问过的重要网元vj的相邻节点vm和影响力值Πjm插入到最大堆H中.

3) 从最大堆H的堆顶获取当前影响力最大值节点vk和其影响力值,若该影响力值大于阈值ε,将所有未被访问过的vk的相邻节点vm和影响力值Πkm插入到最大堆H中,同时将vk加入到图gs中,标记vk为已访问,如果节点vk是重要网元,更新阈值ε,更新公式为:

ε=max(Π(k,∶))×rlb.

重复步骤3),若该影响力值小于阈值ε,则将当前生成的子图gs加入到重要网元子图集合Gs中;若重要网元节点列表不为空,返回步骤1);否则进行步骤4).

4) 融合重要网元子图.遍历重要网元子图集合Gs,若两个重要网元子图存在节点在原图上是直接相连的,将两个网元子图合并成一个网元子图.

生成重要网元子图的算法从重要网元节点出发,通过扩展重要网元来生成重要网元子图.步骤2)和3)使用最大堆来维持影响力大的节点,每次从最大堆H中取出第一个节点加入到当前的重要网元子图gs中.检查是否结束当前重要网元子图gs的扩展的判断条件是当前网元子图gs中的所有节点对待扩展节点的影响力是否小于阈值ε.阈值ε为最后加入到网元子图的重要节点对图上其他节点的影响力的最大值的rlb倍.由于影响力距离遵循幂律分布,rlb的取值为幂律分布曲线的拐点位置,在本文中根据实验中的具体幂律分布情况,rlb的值为0.2.在步骤4)中,对于生成的重要网元子图集合,如果两个重要网元子图存在节点在原图上是直接相连的,那么这两个网元子图将被合并成一个网元子图.

3 实验结果与分析

本文中实验所使用的运行环境为OS X 10.10.5,CPU为Intel i5 1.6 GHz,内存为4 GB,算法的实现基于Python语言.在所有实验中,使用的随机游走的返回概率为0.15.

3.1 数据集

本研究在数据集SNAP1N、SNAP1U、SNAP2N、SNAP2U上进行实验.这4个数据集由数据集SNAP1和SNAP2生成，数据集SNAP1和SNAP2均来源于俄勒冈大学路由查看计划,来自Stanford大学的SNAP项目(https:∥snap.stanford.edu/data/).两个数据集的基本特征如表1所示.

表1 数据集特征

数据集中每个节点代表一个自治系统(如路由),自治系统之间的通信遵循边界网关协议,基于边界网关协议的日志消息可以构建自治系统之间的通信网络拓扑图.由于SNAP1和SNAP2中并没有网元所承载的业务信息,本研究中在其上叠加了合成的业务数据.假设有100种不同的业务,对于每个节点,允许其承载10个不同的业务,承载的业务的数量有均匀分布和正态分布两种情况.随机地从100种业务中选择某节点所承载的具体业务.通过对SNAP1和SNAP2叠加两种不同的业务分布,共生成4个不同的数据集供实验中使用,后文用SNAP1U、SNAP1N、SNAP2U、SNAP2N表示.其中,SNAP1U表示在SNAP1上叠加均匀分布的业务数量,SNAP1N表示在SNAP1上叠加正态分布的业务数量.SNAP2的表示与之类似.

3.2 有效性

首先介绍如何衡量重要网元子图的质量.对于确定的某重要网元子图Gs,可以利用式(3)来衡量重要网元子图的质量：

(3)

其中Π是影响力矩阵.∑vj,vk∈V(Gs),score(vj)≥ξΠjk表示重要网元子图内节点之间的影响力,∑vj∈V(Gs),vk∈V(G),score(vj)≥ξΠjk衡量了重要网元子图内的重要节点到子图内其他节点的影响力,Rcoverage值越高,说明重要网元子图内捕捉到大部分重要节点的影响力越大.

图3显示了在数据集SNAP1U和SNAP1N上，对于不同的ξ找到的前10个重要网元子图的Rcoverage的算术平均值.对于每个ξ,变化邻域影响度的长度为2～6.当随机游走的长度为2时,Rcoverage的算术平均值在两个数据集上都只有0.3左右,这是因为长度为2的随机游走在图上所能访问范围过小,不足以捕捉重要节点的影响力.当随机游走的长度超过3时,发现两个数据集上的Rcoverage的算术平均值都超过70%,例如对于长度为5,ξ为85%时,重要网元子图内的重要节点的影响力超过85%都在子图内部.

图3 数据集SNAP1U和SNAP1N的RcoverageFig.3 Rcoverage of dataset SNAP1U and SNAP1N

图中数值表示网元的编号,下同.图4 数据集SNAP1U和SNAP1N的重要网元子图示例Fig.4 An element subgraph of dataset SNAP1U and SNAP1N

图4展示了分别在数据集SNAP1U和SNAP1N上找到的重要网元子图,其中随机游走的长度为4,ξ为85%，灰色节点表示重要网元子图中的重要节点.可见,找到的重要网元子图里包括相当部分的重要节点,也包括与重要节点相连的非重要节点.寻找网元子图的传统方法是从同一时间窗口内的每个故障网元出发,以每个故障网元为中心,寻找与其路径距离小于h的网元节点.将故障网元以及这些故障网元的邻接网元节点所构成的子图作为此故障网元的邻域子图，即为重要网元子图.同一时间窗口内的故障网元邻域子图如有重合,即包含相同节点,则把重合的邻域子图合并.图5展示了在数据集SNAP1U和SNAP1N上利用传统的方法找到的与图4对应的网元子图,即包括发生故障网元的邻域子图,其中邻域子图中的节点到发生故障节点的路径长度为2.可见,传统方法找到的网元子图包括的节点远远多于本文中所找到的重要网元子图中的节点,会极大地增加运维人员的负担.

3.3 运行时间

图5 数据集SNAP1U和SNAP1N的传统网元子图示例Fig.5 An element subgraph of dataset SNAP1U and SNAP1N

图6 数据集的运行时间Fig.6 The running time on datasets

本研究在4个数据集上都进行了运行时间的实验,其中随机游走的长度为4和6,ξ为85%.图6显示了在SNAP1U、SNAP1N、SNAP2U、SNAP2N的运行时间,包括长度为4和6的随机游走.运行时间分两部分,分别对应评估网元节点的重要性和生成重要网元子图.其中,SNAP1U和SNAP1N的实验结果对应左边的坐标纵轴,SNAP2U和SNAP2N的实验结果对应右边的坐标纵轴.由于评估网元重要性算法的时间复杂度为O(ln3),所以评估网元节点重要性所需的时间随l的增加而增加.生成重要网元子图算法是一个启发式的算法,其时间复杂度与重要节点的个数以及重要节点的影响范围有关,但l的变化会影响重要节点的个数,所以生成重要网元算法的时间也会随l的变化而变化.由于生成重要网元子图中要频繁更新最大堆中所对应的影响力值,其时间复杂度为O(logm),其中m是最大堆里的元素个数,所以扩展生成重要网元子图的时间相对较长.

为了衡量算法的时间复杂度,本研究中分别选取不同节点数,在数据集SNAP2N上进行实验.图7显示了在不同大小的图上算法的运行时间,其中随机游走的长度为4,ξ为85%.可见,随着节点数量的增加,计算网元重要性算法和生成重要网元子图算法的运行时间符合上面的复杂度分析,整体上呈多项式时间增长.当节点数为2 000时，生成重要网元子图步骤的变化也反映了启发式算法的启发策略对整体运行时间的影响.

4 结 论

快速而准确地确定重要网元子图可以用于提高网络基础设施的运维效率,降低运维成本.本研究的主要贡献:1) 针对在大规模网络基础设施中确定面向业务的重要网元子图的问题,提出利用邻域影响度来统一衡量网元在连接和业务两方面的重要性;2) 给出了确定重要网元子图的算法,利用类似密度聚类的思想,通过扩展重要网元生成重要网元子图;3) 在真实的网络基础设施数据集上,通过叠加合成的业务承载数据进行了广泛的实验,实验结果验证了提出的方法可以高效地找到高质量的重要网元子图,并将其用于网络基础设施的运维.未来可能的研究方向包括利用其他影响力模型来构建重要网元子图,以及在动态网络基础设施中如何维护所发现的重要网元子图等.