基于数组链表的大流量网络地址前缀检测方法

摘要

本发明公开一种基于数组链表的大流量网络地址前缀识别方法，其特征是建立一个用于记录IP地址前缀流量信息的8层结构，每层结构记录IP地址的4个比特前缀流量信息且每层结构至少包括一个结点，其中，第0层记录IP地址的第0个至第3个比特流量信息，第1层记录IP地址的第4个至第7个比特流量信息，第2层记录IP地址的第8个至第11个比特流量信息，第3层记录IP地址的第12个至第15个比特流量信息，第4层记录IP地址的第16个至第19个比特流量信息，第5层记录IP地址的第20个至第23个比特流量信息，第6层记录IP地址的第24个至第27个比特流量信息，第7层记录IP地址的第28个至第31个比特流量信息，每个被测量的IP地址及其前缀的流量信息被记录在8层结构中，测量结束后，对于流量超过阀值的大流量网络地址前缀，其相应的网络地址前缀、网络地址前缀长度和网络地址前缀的流量大小输出，本发明相对于传统处理方法减轻了系统处理的负担，加快了处理每个IP地址的效率，同时大大减少生成新结点的数量，节省生成新结点所需要的时间，并降低中间结点所需要的内存空间的使用。

主权项

一种基于数组链表的大流量网络地址前缀检测方法，其特征是：建立一个用于记录IP地址前缀流量信息的8层结构，每层结构记录IP地址的4个比特前缀流量信息且每层结构至少包括一个结点，其中，第0层记录IP地址的第0个至第3个比特流量信息，第1层记录IP地址的第4个至第7个比特流量信息，第2层记录IP地址的第8个至第11个比特流量信息，第3层记录IP地址的第12个至第15个比特流量信息，第4层记录IP地址的第16个至第19个比特流量信息，第5层记录IP地址的第20个至第23个比特流量信息，第6层记录IP地址的第24个至第27个比特流量信息，第7层记录IP地址的第28个至第31个比特流量信息，每个被测量的IP地址及其前缀的流量信息被记录在8层结构中，测量结束后，对于流量超过阀值的大流量网络地址前缀，其相应的网络地址前缀、网络地址前缀长度和网络地址前缀的流量大小输出，具体步骤如下：第一步：设置参数设置大流量网络地址前缀流量阀值T，设置结点数据结构S，结点数据结构由一个结点头和一个包括16个子结点的数组构成，结点头包括一个用于记录该结点的网络地址前缀的存储器、记录该结点的网络地址前缀长度的存储器和记录该结点流量的结点计数器构成，每个子结点由一个记录流量的子结点计数器和一个指向下一个结点的指针构成，设置一个当前指针指向当前处理结点，设置一个指针数组P[p]，指针数值P的大小为p，p的大小设置为要处理IP地址数量的8倍，设置指针数组P的当前指针数q为0，进入第二步；第二步：测量初始化按照结点数据结构S生成一个新结点作为第0层结点，设置一个指针变量Ipointer指向该新结点，设置该新结点的结点头的网络地址前缀为0，网络地址前缀长度为0，流量大小为0，设置16个子结点中的每个元素的流量大小为0，指向下一个结点的指针为空，将该新结点的指针赋值到指针数组P的第q个元素中，并设置当前指针数q为q+1，输入第一个IP地址及其流量大小，进入第三步；第三步：预处理假设IP地址流量大小为B字节，将IP地址32个比特分成8块，每4个比特为一块，其中第0至第3比特为第0块，第4至第7比特为第1块，第8至第11比特为第2块，第12至第15比特为第3块，第16至第19比特为第4块，第20至第23比特为第5块，第24至第27比特为第6块，第28至第31比特为第7块，设当前层数为i，i＝0，将第0层结点指针Ipointer赋值给当前指针，进入第四步；第四步：结点更新将IP地址流量大小B累加更新到当前指针指向的结点的结点计数器中，该结点所对应的4个比特为IP地址的第i块，对应IP地址的第4*i比特、4*i+1比特、4*i+2比特、4*i+3比特，每个比特所对应的比特值分别为b4*i、b4*i+1、b4*i+2、b4*i+3，计算这4个比特所对应的10进制整数x为8*b4*i+4*b4*i+1+2*b4*i+2+b4*i+3，查找该结点中的第x个子结点，将该IP地址流量大小累加更新到第x个子结点的子结点计数器中，进入第五步；第五步：指向下一层结点如果当前层i等于7，则表示已经进入到最后一层，该IP地址处理结束，进入第八步，否则检查第x子结点的指向下一层的指针，如果指向下一层指针不为空，进入第七步，如果指向下一层指针为空，则按照结点结构S生成一个新结点，将指向下一层指针赋值为新生成结点的地址，进入到第六步；第六步：初始化新结点将该新结点结点头的网络地址前缀存储器的值设置为当前指针指向的结点头中网络地址前缀存储器的值乘以16加上x，新结点结点头的网络地址前缀长度存储器的值为当前指针指向的结点头中网络地址前缀长度存储器的值加上4，新结点结点头中结点计数器的值设置为0，设置新结点的16个子结点中的每个子结点的子结点计数器的值为0，每个指向下一个结点的指针为空，将该新结点的指针赋值到指针数组P的第q个元素中，并设置当前指针数q为q+1，进入第七步；第七步：设置当前处理将第x子结点指针指向的下一层结点的指针赋值给当前指针，设置当前层为i＝i+1，回到第四步；第八步：判断IP地址处理结束如果IP地址及其流量记录没有处理结束，处理下一个IP地址及其流量大小，回到第三步，如果所有的IP地址都处理结束，进入第九步；第九步：读取指针数组中的结点指针设当前指针j为0，从指针数组P中读取第j个指针，进入第十步；第十步：结点输出判断如果第j个指针指向的结点头的流量计数器值大于大流量网络地址前缀阀值T，进入第十一步，否则进入第十六步；第十一步：设置次结点将第j个指针指向的结点划分为4个大小为1比特的子层，其中第0子层至第3子层分别有2、4、8、16个次结点，其中第3子层对应的16个次结点就是第j个指针指向的结点的16个子结点，假设当前子层m为0，当前次结点n为0，进入第十二步；第十二步：计算次结点流量当前次结点的网络地址前缀长度为第j个指针指向的结点的网络地址前缀长度加上m+1，当前次结点的网络地址前缀为第j个指针指向的结点的网络地址前缀乘以2(m+1)加上n，如果当前子层m等于3，则当前次结点流量大小为第j个指针指向的结点的第n个子结点的流量大小，进入第十三步；如果当前子层m小于3，当前次结点对应的流量大小为第j个指针指向的结点的第n*2(3-m)个子结点到第(n+1)*2(3-m)-1个子结点的流量累加和，进入第十三步；第十三步：大流量网络地址前缀输出如果当前次结点的流量大于大流量网络地址前缀阀值T，则输出当前次结点的网络地址前缀、网络地址前缀长度和流量大小，进入第十四步，否则直接进入第十五步；第十四步：设置大流量网络地址前缀次结点的下一个次结点序号如果m小于3，设置m＝m+1，n等于2*n，回到第十二步，如果m等于3，n为偶数，则设置n＝n+1，回到第十二步，如果m等于3，n为奇数，且n小于15，则设置m＝m-1，n＝(n+1)/2，回到第十二步，如果m等于3，n等于15，则进入第十六步；第十五步：设置非大流量网络地址前缀次结点的下一个次结点序号如果n为偶数，则设置n＝n+1，回到第十二步，如果n为奇数，n小于2(m+1)-1，且m大于0，则设置m＝m-1，n＝(n+1)/2，回到第十二步，如果n为奇数，且n等于2(m+1)-1，则进入第十六步；第十六步：下一个被处理的结点如果指针数组P的当前结点指针j小于当前指针数q-1，设置当前结点指针j为j+1，回到第十步，否则结束退出。