基于邻接矩阵的网络流量检测点选取算法研究.docx

基于邻接矩阵的网络流量检测点选取算法研究何泾沙 2鑫 1石恒华 1许(1 北京工业大学计算机学院, 北京 100124 ) (2 北京工业大学软件学院, 北京 100124)摘要: 为对网络流量进行有效检测，考虑网络节点的流守恒，把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题基于图论中邻接矩阵的概念，在满足对任意顶点度数大于 2 的假设条 件下，提出一个求解弱顶点覆盖问题的近似算法通过将求解弱顶点覆盖集中点与边的关系转化 为点与点的关系，降低了矩阵计算复杂度仿真实验表明，与现有算法相比，新算法能够选取出 更小的弱顶点覆盖集，部署更少的网络流量检测点，减轻了由网络流量数据收集造成的额外负担关键词: 网络流量；检测点；弱顶点覆盖；邻接矩阵；流守恒中图分类号: TP393.07文献标识码: A文章编号: 1001-0505(2008)增刊(I)-0127-04Algorithm research for selecting measurement nodes in measuringnetwork traffic based on adjacency matrixShi Henghua1He Jingsha2Xu Xin1(1 College of Computer Science, Beijing University of Technology, Beijing 100124, China) (2 School of Software Engineering, Beijing University of Technology, Beijing 100124, China)Abstract: To efficiently measure the network traffic, considering the flow-conservation equation, theproblem of selecting measurement nodes is regarded as a problem of finding out the weak vertex cover of a graph. Under the assumption that the degree of each node is more than 2, an approximate algorithm is proposed based on the concept of adjacency matrix in graph. This algorithm decreases the computation complexity by turning the link-node relationship of the weak vertex cover to a node-node relationship. The simulation results show that the novel algorithm can find smaller weak vertex cover and allocate less measurement nodes, therefore reduce the additional network load for collecting network traffic data.Key words: network traffic; measurement nodes; weak vertex; adjacency matrix; flow conservation近些年来，基于 Internet 网络的多媒体需求迅速发展，网络研究者越来越关注网络流量和可用带宽网络流量检测点作为进行网络流量检测的基础，成为近期研究的热点问题之一目前网络流量的检测方法是 针对特定的链路1,通过人工方式合理地规划网络检测点2这种方法难以扩展，不适合网络的动态变化， 可能会因为设置过多的检测点而增加网络额外负担3同时在网络流量检测中，大量设备的频繁轮询采集 数据也会增加网络额外负担，并造成路由器性能下降4关键问题是如何解决选取出的网络流量检测点， 即要能够准确地获取网络流量信息，又要尽可能减少由于数据收集对实际网络造成的额外负担研究中一 般将网络流量检测点选取问题抽象为求无向图的弱顶点覆盖问题，这是一个 NP 难的问题5，通常采用近 似算法求解文献4提出了 3 个计算弱顶点覆盖的近似算法，并使用模拟数据加以比较文献5在文献4 的基础上，从图论角度提出了一个弱化的贪心算法，并分析了它的时间复杂度本文基于图论中邻接矩阵 的概念，提出一个求解弱顶点覆盖问题的近似算法，通过将求解弱顶点覆盖集中点与边的关系转化为点与 点的关系，降低了矩阵计算复杂度在弱顶点覆盖集中网络节点上安装特定软件，设置流量检测器(如 SNMPAgent)，并按照一定频率主动收集与这些节点相关联的链路上的网络流量，以此来得到整个网络所有链路的网络流量信息仿真实验表明，与文献4中提出的 3 个算法相比，新算法具有更好的性能，能够选取出 更小的弱顶点覆盖集收稿日期: 2008-08-31.基金项目: 北京市自然科学基金资助项目(KJ200610005003).作者简介: 石恒华(1978), 男, 博士生, ; 何泾沙(联系人), 男, 博士, 教授, 博士生导师, . 128 东南大学学报(自然科学版) 第 38 卷 1相关问题描述需要考虑的问题是：如何在网络中选取弱顶点覆盖集设置流量检测器，在可以得到网络中每条链路流量基础上，所需的检测器数量较少这个问题可以抽象为图论中求顶点覆盖问题 实际网络拓扑可以抽象为无向图 G = (V , E) ，图中顶点集V = (v1 , v2 , ., vn ) 代表实际网络中路由器、交换机和主机等设备，图中边集 E = (e1 , e2 ,., em ) 代表设备之间的链路其中 n 和 m 分别为图 G 中节点和链路的数量用 e = (vi , v j ) 表示节点 vi 和 v j 之间的链路，用Degree( v )表示与节点 v 相连接的链路数量可以得出如下定义：定义1（顶点覆盖问题） 谓的顶点覆盖问题，是指给定无向图 G = (V , E) ，S 是顶点集V 的一个子集， 使得 e = (u, v) E ，u S 或 v S ，即边集 E 中的任意一条链路至少含有子集 S 的一个节点作为顶点也 就是说 S 中的顶点覆盖图 G 的边集 E 定义2（流量检测集） 给定无向图 G = (V , E) ，如果在顶点集V 的子集 S 的每一个节点上设置流量检测点，可以确定边集 E 中任意链路上的流量，则称 S 是图 G 关于流量的检测集定义3（流守恒方程） Iv 表示图 G 中流入顶点 v 的边，Ov 表示图 G 中流出顶点 v 的边对于顶点 v 的流守恒方程为，流入顶点 v 的流量信息与流出该顶点的流量信息应该基本相同对于一个没有叶子节点的 图来说，可以表示为一下方程式： bw(ei ) bw(e j ) 0 实际环境中以下原因会导致流守恒方程的失真，如：交换设备是数据的源或汇,而不仅仅是数据转发 器；多播导致输出端口的数据复制；交换设备本身的数据包延迟或丢弃然而根据Bell实验室对Lucent 网络长周期的研究表明，流守恒方程所具有的相对误差小于0.05%6可见解决网络流量检测点问题就是求解给定的图 G 顶点覆盖集 S 但已证明，顶点覆盖问题是一个NP难的问题如果网络中只有路由器或交换机等交换设备，那么还可以挖掘以下2条约束：(1) 对图 G 的顶点集V 中的任意顶点 v ，其度Degree( v )2；(2) 对图 G 的顶点集V 中的任意顶点 v ，满足流守恒方程，即流进=流出定义4（弱顶点覆盖问题） 假定无向图 G = (V , E) 满足对任意 v V 有Degree( v )2，称 S V 是图 G的弱顶点覆盖集，当且仅当执行以下操作能使边集 E 中所有链路可以被标记：(1) 标记所有与 S 中顶点相连接的链路(2) 若某个顶点 v 的Degree( v )-1条相连接的链路已被标记,则标记剩下的相连接的那条链路(3) 重复第(2)步，直到不能再标记新的链路为止可见在满足无向图 G = (V , E) 中对任意 v V 有度Degree( v )2这个条件下，将弱顶点覆盖集 S 作为流量检测集，就可以得到边集 E 中任意链路的流量文献5对相关理论进行研究，并使用数学方法加以说明本文基于上述基础，利用图论中邻接矩阵的概念进行相关实验，并对提出的近似算法进行验证为了 便于说明，给出如下定义定义5（邻接关系）在无向图 G = (V , E) 中，如果 u V 与 v V 是 e = (u, v) E 的两个顶点，则称 u和 v 之间存在邻接关系ei Ivei Ov1, 节点之间的边没被标记定义6（邻接矩阵）无向图 G 的邻接矩阵 A = (aij ) 是为如下 n n 矩阵：a= ij0, 其他顶点集V 的子集 S 构成图 G 的一个弱顶点覆盖，当且仅当 S 包含的节点所对应的邻接矩阵的行元素大于 1，即至少存在 1 条以上与该节点相连接的链路没有被标记根据邻接矩阵的定义，可以将文献5中 点与边的关系转化为点与点的关系，降低了矩阵计算复杂度检测点选取算法的实现21,viS基于以上分析，将求解网络流量检测点选取问题转化为以下弱顶点覆盖问题，设： y= i0,v Sin则弱顶点覆盖问题变为求： min yi 且满足， aij 1 ， j = 1, 2, n ，其中 aij 为邻接矩阵中对应元素j =1增刊(I)石恒华, 等: 基于邻接矩阵的网络流量检测点选取算法研究1292.1算法思路求解网络流量检测点选取数目最少问题算法思路为：(1) 在网络拓扑邻接矩阵中选取行元素之和最大的节点 v (2) 删除邻接矩阵中节点 v 对应的行和列，然后在剩下的邻接矩阵中再依次删除所有行元素之和不超 过1的节点对应的行和列，直到不能再删除新的行和列为止(3) 重复步骤(1)和(2)的操作，直到邻接矩阵变为空，即所有的链路都被标记到2.2算法描述将本算法称为 SMN (selecting measurement nodes algorithm)，具体描述如下： 输入：网络拓扑图 G = (V , E)输出：部署网络流量检测点的节点集 S定义节点集 S = ；写出去除图 G 的邻接矩阵 A = (aij ) ，其中 i = 1, 2, n ， j = 1, 2, n ；While ( A 非0)nn计算邻接矩阵 A 中每行元素之和 aij ，选择和为最大的那一行，令 max aij = ak 对应的顶点 vk ，ij =1j =1如果 A 中有两个以上节点对应行的元素之和相等且为 ak ，则取行编号最小的行对应的节点为 vk ；将节点 vk 加入到节点集 S 中；删除邻接矩阵 A 中节点 vk 对应的行和列，然后在剩下的邻接矩阵中再依次删除所有行元素之和不超过1的节点对应行和列，直到不能再删除新的行和列为止；2.3算法举例说明以图1所示的网络拓扑图 G 为例，对SMN算法加以说明：图1 网络拓扑图 G 0001010111001101000011011000010110001 v1 1 v 0100110000011110000011000 0 11 v2 2 00001110000110000 v 310v 01 v 00011 v3 0 v3 3 A = 1 4 01 v A = 01 vA = 11 v4 40 v 4 A = 50 v 110v5 0 0 v5 6 10 v6 00 v6 1 0 v6 00 v7 0 v7 1 10 v7 网络拓扑图 G 对应的邻接矩阵为 A .nnnn节点 v1 的 a1 j = 4 ；节点 v2 的 a2 j = 3 ；节点 v3 的 a3 j = 4 ；节点 v4 的 a4 j = 3 ；节点 v5j =1j =1j =1j =1nnn的 a5 j = 2 ；节点 v6 的 a6 j = 3 ；节点 v7 的 a7 j = 3 ；节点 v1 和节点 v3 的行元素和最大，因为节点 v1比节点 v3 的编号小，所以选取节点 v1 节点 v1 的行元素和最大，所以选取 v1 删除邻接矩阵中节点 v1 对应的行和列，得到的邻接矩阵为 A 同理，在邻接矩阵 A 中选取节点 v2 j =1j =1j =1 130 东南大学学报(自然科学版) 第 38 卷 删除邻接矩阵 A 中节点 v2 对应的行和列，得到的邻接矩阵为 A . 在 A 中再依次删除所有行元素之和不超过1的节点如 v5 ，v7 对应的行和列，得到邻接矩阵 A=0 所以 SMN 算法的覆盖节点集则节点集 S = v1 , v2 即只要轮询节点 v1 ，v2 即可得到网络拓扑图 G 的各条链路上的流量3仿真实验本文以 NEM7为网络拓扑生成工具，采用 Waxman8网络模型生成网络拓扑结构，使用 SMN 算法与文献4中生成简单顶点覆盖(Simple VC)的最大匹配启发算法、生成弱顶点覆盖(WVC)的最大匹配算法和生成弱顶点覆盖的 Greedy Rank 算法进行比较上述 4 种设置算法都是基于图论中最小顶点覆盖原则，其性 能的优劣体现在各个算法得到的网络流量检测点数量上，而测量中的流量精度和准确度与具体使用的流量工具有关依次分别用 N VC， N WVC ， N WVC 和 N WVC 表示上述算法得到的网络流量检测点个数；用matchmatchranksmnAvg.Degree 表示网络拓扑图中节点的平均度数实验中各参数的取值为 n = 500 , = 0.4 ， = 0.02, 0.04, 0.08 比较结果如表 1 所示，可以看出 SMN 算法选出的检测点数量比前 3 种算法都小，说明 SMN 算法具有更好的性能表 14 种选点算法的比较VCWVCWVCWVCNmatchNmatchNrankNsemAvg.Degree4.48.612.616.93874414534662553724084311652543073341312222993324结语在研究网络流量检测点的有效选取问题时，通常把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题本文基于图论中邻接矩阵的概念，提出一个求解弱顶点覆盖问题的近似算法仿真实验表明，与现有算法相比，SMN算法具有更好的性能，能够发现更小的弱顶点覆盖集本文提出将求解弱顶点覆盖集 近似算法中点与边的关系转化为的点与点的关系，降低了矩阵计算的复杂度考虑到弱顶点覆盖集近似算法需要满足对任意 v V 有度Degree( v )2的假设条件，并不完全符合实际网络环境情况，这些将是我们下一步工作中要研究的内容参考文献 (References)Downey A B. Using pathchar to estimate internet link characteristics C/ Proc of the ACM SIGCOMM99 Conference onApplications, Technology, Architectures and Protocals for Computer Communications. New York, USA: ACM Press, 1999:241-250.Jamin S, Jin C, Jin Y, et al. On the placement of internet instrumentation C/ Proc of the IEEE INFOCOM00. Tel Aviv, Israel: IEEE Communication Society Press, 2000: 295-304.Lai K, Baker M. Measuring bandwidth C/ Proc of the IEEE INFOCOM99. New York, USA: IEEE Communication SocietyPress, 1999: 235-245.Breitbart Y, Chan C Y, Carofalakis M, et al. Efficiently monitoring bandwidth and latency in IP network C/ Proc of the IEEE INFOCOM01. Anchorage, Alaska, USA: IEEE Communication Society