技术摘要：
本发明属于流量采样技术领域，具体涉及一种基于共享计数树的存储空间优化采样方法。本发明旨在节约采样设备存储空间，具体包括根据采样判断机制决定是否对到来的数据包进行采样；如果决定对到来的数据包进行采样，在哈希流跟踪表中对该数据包所属流节点进行检索；若未  全部
背景技术：
近些年，互联网中应用的种类和数量有了显著的发展。为应对应用变化对网络带 来的影响，网络管理者需要对流量应用特征进行测量，在测量的过程中需要对流量进行应 用分类。为支持应用分类，采样流量应保留足够的应用特征。现代应用程序的一个具体会话 通常是由多条流组成，会话中每一条流的源IP相同但目的IP可能互异。若在某一应用程序 会话中采到更多的流，则会为采样流量保留更多的应用特征，进而有助于机器学习算法准 确地对采样流量进行应用识别。RelSamp只会对一定范围内的源IP所对应的流进行采样，而 且在有效采样比恒定的情况下，它可以通过提高流采样概率，降低包采样概率来提高在应 用程序会话中所采到的流的数量，更多地保留采样流量的应用特征。但是，针对流的任意一 个统计特征，例如，流大小，RelSamp需要为每一条流分配一个计数器来记录其大小。为每个 计数器分配的空间都要一致且要保证计数器的计数范围能够涵盖最大流的计数值。网络流 量分布具有重尾分布的特点，即占小比例的大流占据了网络流量中的大比例。有研究表明， 按照流大小对流进行排序，排在前15％的流占据了流量总体的95％。为每条流分配空间大 小一致的计数器来记录流大小，必然会造成流量采样设备存储空间的大量浪费。为每一条 流分配空间大小一致的计数器来记录其他统计特征(例如，采样过程中，该流FIN，SYN以及 ACK包到来的个数)也同样会对流量采样设备的存储空间造成浪费。尤其是当RelSamp部署 在网络流并发量巨大的高速网络环境中时，会对流量采样设备造成巨大的存储压力。
技术实现要素：
本发明的目的在于提供节约采样设备存储空间的一种基于共享计数树的存储空 间优化采样方法。 本发明的目的通过如下技术方案来实现：包括以下步骤： 步骤1：根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率 确 定输出包采样概率pp和当前流采样概率pf； 步骤2：从数据包缓冲队列提取数据包，并为该数据包分配两个取值范围在[0，1) 的随机数rf和rp； 步骤3：获取数据包的源IP并计算该源IP的哈希值； 步骤4：将源IP的哈希值与源IP选择概率ph相乘得到目标值； 步骤5：若目标值落在预先配置好的范围内，则执行步骤6；否则抛弃该数据包； 步骤6：搜索数据包所属流节点； 若没有查找到该数据包对应的流节点且rf≤pf，则对该数据包进行采样并为该数 据包创建一个流节点，新建流特征存储单元，并更新该流的流特征存储单元； 5 CN 111581489 A 说　明　书 2/9 页 若查找到该数据包所属流节点且rp≤pp，则对该数据包进行采样并更新该流的流 特征存储单元； 若没有查找到该数据包对应的流节点且rf＞pf，或查找到该数据包所属流节点且 rp＞pp时抛弃该数据包； 步骤7：当对某条流的采样结束后，将存储在流节点中的流特征以及存储在共享计 数树中的流统计特征还原为完整的流记录，并将流记录加入到流记录缓冲队列中；待缓冲 区已满，将采样流特征记录写入到文件中。 本发明还可以包括： 所述的步骤1中根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概 率 确定输出包采样概率pp和当前流采样概率pf的具体步骤为： 步骤1.1：输入预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率 步骤1.2：初始化包采样概率pp和当前流采样概率pf； pp＝pe/ph pf＝pe/ph 步骤1.3：令 步骤1.4：获取当前采样比px； 步骤1.5：若 则输出包采样概率pp和当前流采样概率pf，结束计算； 否则，执行步骤1.6；其中α为设置的精度； 步骤1.6：若|px-pe|≤α，则返回步骤1.3；否则执行步骤1.7； 步骤1.7：若当前采样比px大于预先配置的有限采样比pe，则令pp＝0.5*(pp t)，t ＝0.00001，返回步骤1.6；否则，令pp＝0.5*(pp 1)，返回步骤1.6。 所述的步骤6中为数据包新建流特征存储单元的具体方法为：对数据包进行解析， 将五元组信息、流到达时间、流最近更新时间、最小有效负载长度以及最大有效负载长度写 入流节点中；其中，流最近更新时间与流到达时间均为当前时间；最小有效负载长度和最大 有效负载长度均为该数据包的应用层有效负载长度；若该数据包为TCP数据包，对TCP首部 进行解析，检测标志位ACK、FIN、SYN、RST是否在其中被置位；若TCP数据包被置位，则在对应 的共享计数树中对该流到来的标志位数据包个数进行计数；在存储流大小的共享计数树中 对该流进行计数；计算该数据包的长度len，以32B为一个数据块，得出该数据包所占的数据 块数c， 在存储流长度的共享计数树中对该流进行c次计数；若数据包不是TCP数 据包或者TCP数据包没被置位，则不需在共享计数树中对该数据包所属流的ACK包个数，SYN 包个数，FIN包个数和RST包个数特征进行计数。 所述的步骤6中更新流的流特征存储单元的具体步骤为： 步骤6.1：更新流节点中的流最近更新时间； 步骤6.2：对该数据包进行解析，计算出该数据包应用层有效负载长度； 步骤6.3：若该数据包应用层有效负载长度大于原有最大有效载荷长度，则对最大 有效载荷长度进行更新；若该数据包应用层有效负载长度小于原有最小有效载荷长度，则 对最小有效载荷长度进行更新； 6 CN 111581489 A 说　明　书 3/9 页 步骤6.4：在共享计数树中更新统计特征值。 所述的步骤6.4中在共享计数树中更新统计特征值的具体步骤为： 步骤6.4.1：提取出数据包的五元组信息，对五元组信息进行哈希，定位该数据包 在流表中所对应的流节点，并从流节点中提取出该流的流标签ftuple； 步骤6.4.2：生成随机数i，i∈[0，r)； 步骤6.4.3：从随机数集合S中选择S[i]与流标签ftuple进行异或，并将异或值作为 参数传给主哈希函数H，生成哈希函数hi；计算哈希值 定位本次计 数的加强计数器；其中，p为加强计数器的数量； 步骤6.4.4：更新统计特征值C[u]，C[u]←C[u] 1； 如果C[u]没有溢出，则本步骤结束，完成对统计特征值的更新； 如果C[u]溢出且其父节点的下标大于或等于虚拟根节点的下标，则加强计数器L [u]溢出，不再使用该共享计数树计数； 如果C[u]溢出且其父节点的下标小于虚拟根节点的下标，更新u， 重 新执行步骤6.4.4。 所述的步骤7中从共享计数树中还原该流数据统计特征值的具体步骤为 步骤7.1：从结束采样流的流节点中提取流标签ftuple； 步骤7.2：将随机数集合S中的元素S[i]依次与流f的流标签进行异或，并将异或值 作为参数传给主哈希函数H，分别计算出r个哈希值 定位记录该流 统计特征值的r个加强计数器及子树计数器； 步骤7.3：计算流的统计特征值s； 其中，Xi为子树计数器的值；li为子树计数器的高度；n为目前共享计数树的总计数 值；ki为子树计数器中叶子节点的个数， 本发明的有益效果在于： 本发明提出的一种基于共享计数树的存储空间优化采样方法并不会影响SVM分类 器和C4.5分类器对采样流量应用识别的准确率，而且本发明在采样过程中仅需少量的存储 空间。具体来说，用SVM分类器对本发明的采样流量进行应用识别，在所识别的各应用中，应 用识别的平均精度为0.867；用C4.5分类器对本发明的采样流量进行应用识别，在所识别的 各应用中，应用识别的平均精度为0.891。以9GB流量作为输入，在采样过程中，本发明最多 仅需700KB的存储空间，最少仅需200KB的存储空间。 附图说明 图1是本发明的总体框架图。 图2是本发明中确定相关采样概率的流程图。 图3是本发明中采样判断策略的流程图。 7 CN 111581489 A 说　明　书 4/9 页 图4是本发明中更新流特征存储单元实例图。 图5是三层的共享计数树存储结构图。 图6是三层的共享计数树逻辑结构图。 图7是计数器存储结构图。 图8是加强计数器图。 图9是加强计数器向量图。 图10是五元组信息为tuple3的流特征记录还原过程实例图。 图11是用以说明子树计数器中根节点的选择方法的图例。