一种面向云计算网络的拓扑探测方法

摘要

本发明提供了一种基于云计算网络的拓扑探测方法，适用于云计算网络环境下对于网络拓扑进行探测，本发明将拓扑探测分为两层进行分别探测，在第一层中由路由器与计算节点构成，通过发送socket“三明治”包的方法探测出时延；第二层由云计算环境环境中计算节点下的虚拟机的分布构成，本发明采用MPI探测虚拟机间的通信时延，并通过相应的计算后采用并查集算法进行归并聚类，从而得到虚拟机的分布。通过本发明可以比较完整的探测出整个云计算网络环境下的完整拓扑结构。

主权项

一种基于云计算网络的拓扑探测方法，其特征在于该方法包含以下的具体步骤：步骤1.按照预先设定拓扑图进行搭建云平台管理项目Openstack的真实环境，步骤2.在进行第一层网络拓扑探测时对每个路由器下任意选择一个虚拟机进行编号并编入相应的套接字程序socket程序，通过路由器下的虚拟机为分别接收大数据包与两个小的数据包，对每对路由器与计算节点间的数据时延测量，得到每对小数据包的时间差，通过全局搜索拓扑探测MLT算法进行推断，1)选择一个随机的开始状态s₀＝(T₀+u₀)，2)进入下一状态s₁，得到最小值：$\min \{1,\frac{p(T_1,u_1|x)q\left(s_0\right|s_1)}{p(T_0,u_0|x)q\left(s_1\right|s_0)}\times J_{f(s_1-s_0)}\},$3)重复步骤1和步骤2的过程，直到建立一个拓扑图；步骤3.在进行第二层网络拓扑探测时，对于每个路由器虚拟机进行安装信息通信接口库MPI，并写入对应的时间测试程序，由公式T_comm＝T_S+mT_W通过测量节点彼此间发送不同字节大小的数据包，得到不同数据包大小时对应的时间大小，其中T_comm表示节点对间实际测量得到的传输时间；T_S表示节点对间建立的时间；T_w表示节点对间的每单位字节的发送时间；m表示节点对间发送的字节大小；对于每一个节点对i,j,用矩阵实验室MATLAB将其10个值根据上述线性公式拟合出该节点对在T_w矩阵下的值Tw_i,j；使用并查集算法Union‑Find进行节点聚类，并查集是通过树形结构来存储的，在合并操作时利用树的节点数或者利用一个排列数组来存储集合的启发式函数，在查找操作时进行路径压缩使后续的查找操作加速；并查集有三种操作：合并操作Union；把子集合Root2即根2和子集合Root1即根1合并，要求：Root1和Root2互不相交，否则不执行操作；搜索操作Find；搜索单元素x所在的集合，并返回该集合的名字‑‑根节点标示；UFSets构造函数，将并查集中s个元素初始化为s个只有一个单元素的子集合，利用并查集的算法，将MPI测试数据进行划分聚类，number表示节点的数量；threshold表示定义的阈值范围；Tw[number][number]表示T_w矩阵；1)得到“朋友关系矩阵”，设置一个阈值，遍历其余节点，其中有90％～98％比例的节点到两观测节点的时间差在阈值范围内，即认定两观测节点为“直接朋友”关系，否则不是，得到“直接朋友关系”矩阵；2)初始化把每一节点当成一颗子树，该树只有自身一个节点，作为根节点；3)合并子树若节点i,j，为直接朋友关系，对i,j为根节点的子树分别进行压缩路径，使其子树中所有非根节点直接指向根节点，并合并以i,j为根节点的子树，并把编号较小的节点作为新树的根节点，再对新树同样进行压缩路径；4)差错检测，在合并子树的过程中，若节点i,j不为直接朋友关系，而遍历节点i,j的根时得到同一根节点，则说明出现差错；5)显示划分结果，用map即示意图存储不同集合树当中的元素，每棵树的根节点编号作为map的下标，对应的内容是一个向量，用来存储该树所有非根节点，归并好的节点即是虚拟机的部署拓扑，从而得出云环境下第二层网络拓扑；步骤4.在聚类好的虚拟机结构中，通过测试相互的时延，由于在同一路由器下的虚拟机间的通信时间肯定最短，随着经过的路由器与交换机的增多通信时延增加，根据这一原理，通过比较不同虚拟机间的时延相似度来验证之前的聚类分布；步骤5.将第一层拓扑探测结构与第二层拓扑探测结构相结合构成完整的云计算环境下的网络拓扑结构。