G比特流率下多粒度的网络自动聚类方法

摘要

G比特流率下多粒度的网络自动聚类方法属于计算机网络测量技术领域。其特征在于基于网络测量的周期性采样机制，采用了基于流量预测的启发式算法，同时通过将IP包头的不同字段看成是网络特征空间中的不同维度，提出了针对多维空间的数据进行自动分类的自适应算法。其主要步骤在于：1.设置相关参数；2.启动测量程序；3在一个测量周期内，对于每一个到达的报文依次执行一维源地址和目的地址的聚类，源/目的地址队聚类和端口聚类；4.数据的压缩与输出；5.流量预测。实验表明，本方法能够实时运行在G比特速率的互联网之上，达到了预期发明目标。

主权项

1.G比特流率下的多粒度网络自动聚类方法，其特征在于所述方法是在一个通过路由器或者高端交换机的端口镜像功能接受报文的流量检测服务器中实现的，其步骤依次如下：步骤(1).设置如下参数：在时间间隔T内对网络报文进行测量的测量周期，T＝1分钟；测量目标值，为报文大小；聚类程度Phi＝1％，Phi反映聚类结果的网络测量目标值占当前总网络的测量目标值的比值，用以反映单个网络聚类的测量值占总测量目标值1％以上的各个网络聚类；测量误差允许值ε，ε＝1％·Phi；当前测量周期T内的总测量目标值Vcur，前次测量周期测量值Vlast和下轮测量周期预测值V为0；启发式算法预测深度阈值Tg，默认为0.8phi＝0.008，(ε＜＜Tg≤phi)，Tg为启发式算法的性能参数；滑动因子α，α＝0.5；分裂阈值Tsplit，初始值为0；节点最大深度Wmax，即IP前缀的最大深度，Wmax＝4，IP地址树模型中根节点的深度为W＝0；步骤(2)启动测量程序，设定当前测量总目标值Vcur＝0；步骤(3)在一个测量周期T内，对于每一个到达的报文E依次执行以下步骤：步骤(3.1)设定一维树状存贮结构内，每一个树节点的数据结构为：孩子指针，是指向树节点的孩子节点指针，指向孩子节点所在内存空间，用一个指针数组表示多个孩子指针，初始值为空；预测深度，是在下一个测量周期内所述节点所处的深度，初始值为0；实际深度，是当前节点深度；叶子属性，为真表示所述节点为是叶子节点，为假则否，初始值为否；当前容量，树节点在当前测量周期内所包含的初始报文大小，用字节表示；孩子节点容量，树节点的孩子节点所包含的初始报文大小，初始值为0；前次容量，树节点在上一测量周期内所包含的全部报文的大小，等于上一测量周期内得到的节电当前容量和孩子节点容量之和，初始值为0；步骤(3.2)按以下步骤更新一维树状存贮结构，输入报文的源地址和E的测量目标值，返回源地址深度W1；步骤(3.2.1)设置标识为*.*.*.*的IP地址树根节点为IP地址的当前节点；步骤(3.2.2)满足下列三个条件中的任何一条，则所述步骤(3.2)的当前节点退出：出现叶子节点，且其当前容量加上测量目标值小于分裂阈值Tsplit，则更新当前节点容量值为当前测量值加上当前节点容量，返回当前节点的预测深度；出现叶子节点，且其当前容量加上测量目标值不小于分裂域值Tsplit，但其当前深度已达到最大深度Wmax，则更新当前节点为孩子节点，容量为测量目标值，返回当前节点的预测深度；否则，设置叶子节点属性为假；出现非叶子节点，其当前容量加上测量目标值不小于分裂域值Tsplit，但其当前深度等于最大深度Wmax，则返回当前节点的预测深度；如果不满足以上三条退出条件，则无论节点是否为叶子节点均更新所述当前节点的孩子节点容量为当前节点的孩子节点容量再加上测量目标值；在以上条件中，若节点容量的增长超过分裂域值Tsplit，但当前深度小于最大深度时，该节点根据输入IP地址和当前的深度分裂新的孩子节点并同时取代原有的节点成为当前节点继续执行步骤(3.2.2)，直到节点处于最大深度Wmax；步骤(3.3)按照步骤(3.2)所述方法更新一维树状存贮结构，输入的参数为报文的目的地址和E的测量目标值，返回目的地址的深度W2；步骤(3.4)根据步骤(3.2)和步骤(3.3)返回的源地址和目的地址的深度，分别执行以下步骤步骤(3.4.1)若返回的源地址深度或者目的地址深度有一个大于0，则根据源地址和目的地址得到在相应深度下的IP前缀标识，设为prefix1和prefix2，如果不存在二维叉乘表格H[W1][W2]中的哈希索引表格中，则开辟空间，初始化测量值为0；否则，更新测量值为原有测量值再加上报文E的测量目标值，所述二维叉乘表格的两个维度分别为源地址的深度[W1]和目的地址的深度[W2]，而每一个节点的位置存贮在该深度下的源地址与目的地址的索引表格中，该索引表格使用二维矩阵存贮，矩阵中每一个元素为一个哈希表格，哈西表格中的索引为源地址和目的地址在当前深度下的节点标识；其存贮内容为该地址深度的当前测量目标值和上一个测量周期的测量目标值；步骤(3.4.2)如果返回的源地址或目的地址的深度为最大值Wmax，则更新端口哈希表P：当该地址索引在P中不存在时，则开辟相关的空间，初始化测量值为0；否则，更新源地址或目的地址索对应的端口测量值为原有测量值加上E的测量目标值；步骤(3.5)把报文的测量目标值增加到当前测量总目标值Vcur，对下一个报文重复步骤(3.2)-(3.4)；步骤(4)按照以下步骤分别设置所述当前节点为源地址树和目的地址树的根节点，其节点标识均为*.*.*.*，分别对这两个节点树按照步骤(4.1)进行压缩；步骤(4.1).如果当前节点的当前容量加上当前节点的孩子节点容量小于V·Phi，那么设置当前节点的叶子属性为真，其中预测容量V根据步骤7计算得到；步骤(4.1.1)如果当前节点当前容量和孩子节点容量之和大于预测深度容量Tg·V，则更新当前节点的预测深度为当前节点的当前深度；步骤(4.1.2)如果当前节点当前容量和孩子节点容量之和小于Tg·V，则更新当前深度为节点深度减1，清空其所有孩子节点空间，释放相关资源；步骤(4.2)如果当前节点的当前容量和孩子节点容量之和超过V·Phi，则设置当前节点的预测深度为当前节点的当前深度，对于当前节点的每一个孩子节点，将其设置为当前节点按照步骤(4.1)，依次进行压缩；步骤(5)对源地址和目的地址分别执行如下子步骤，输出一维源地址和目的地址的聚类结果，其示意图如图8所示；步骤(5.1)设置当前节点V为地址树的根节点*.*.*.*，初始化节点队列Q空，对于节点V的孩子指针指向的每一个不为空的孩子节点，将其进入队列Q；步骤(5.2)取出队列Q的第一个节点V1，将V1从队列Q中移除，将其设置为当前节点，将其补偿数值T设定为0；步骤(5.3)对于当前节点V1的每一个孩子来说，分别执行以下步骤，以下以V11举例说明；步骤(5.3.1)如果孩子节点V11的当前容量和孩子节点V11的孩子节点容量大于V·Phi，则增加补偿值T为T的原有容量再加上V11的当前容量和V11的孩子节点容量，并将该孩子节点V11放入队列Q中；步骤(5.4)如果当前节点V1的容量加上当前节点V1的孩子节点容量减去补偿值T大于阈值V*Phi，输出当前节点V1为静态聚类节点；步骤(5.5)如果当前节点V1的当前容量加V11的孩子节点容量减去其前次容量大于阈值V*Phi的话，输出当前节点V1为动态节点；步骤(5.6)设定当前节点V1的前次容量为V11的当前容量加孩子节点容量，设定其当前容量为0；设定V1的孩子节点容量为0；步骤(5.7)若队列Q不为空，返回步骤(5.2)继续，否则退出步骤(5)；步骤(6)压缩并且输出叉乘表格中的源目的地址对，即对于叉乘表中的每一个维度以及维度里面的每一个哈希索引所对应的数据项e，依次执行以下步骤步骤(6.1)如果e的当前容量减去上次容量的绝对值大于阈值Vcur·Phi时，输出e为动态聚类节点；步骤(6.2)如果e的当前容量大于Vcur·Phi，则输出节点e为静态聚类节点；步骤(6.3)如果e的当前容量为0则删除该节点，继续执行步骤(6)；步骤(6.4)设定节点的前次容量为当前容量，设定节点的当前容量为0，继续执行步骤(6)；步骤(7)流量预测，采用简单的加权指数平均模型，按照如下公式进行预测下一次的流量V；V＝αVcur+(1-α)Vlast，------------------------(1)步骤(8).计算步骤3中所用的分裂阈值Tsplit；Tsplit＝ε·(phi)·V/W，--------------------(2)步骤(9).返回步骤(3)，进入下一个测量周期。