Nothing Special   »   [go: up one dir, main page]

CN111581489A - 一种基于共享计数树的存储空间优化采样方法 - Google Patents

一种基于共享计数树的存储空间优化采样方法 Download PDF

Info

Publication number
CN111581489A
CN111581489A CN202010438372.8A CN202010438372A CN111581489A CN 111581489 A CN111581489 A CN 111581489A CN 202010438372 A CN202010438372 A CN 202010438372A CN 111581489 A CN111581489 A CN 111581489A
Authority
CN
China
Prior art keywords
flow
data packet
sampling
node
shared
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202010438372.8A
Other languages
English (en)
Other versions
CN111581489B (zh
Inventor
杨武
玄世昌
王巍
苘大鹏
吕继光
唐德志
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Harbin Engineering University
Original Assignee
Harbin Engineering University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harbin Engineering University filed Critical Harbin Engineering University
Priority to CN202010438372.8A priority Critical patent/CN111581489B/zh
Publication of CN111581489A publication Critical patent/CN111581489A/zh
Application granted granted Critical
Publication of CN111581489B publication Critical patent/CN111581489B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/95—Retrieval from the web
    • G06F16/953—Querying, e.g. by the use of web search engines
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/13—File access structures, e.g. distributed indices
    • G06F16/137—Hash-based
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/17—Details of further file system functions
    • G06F16/172—Caching, prefetching or hoarding of files
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/24—Classification techniques
    • G06F18/241—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches
    • G06F18/2411—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches based on the proximity to a decision surface, e.g. support vector machines
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/24—Classification techniques
    • G06F18/243—Classification techniques relating to the number of classes
    • G06F18/24323—Tree-organised classifiers
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2483—Traffic characterised by specific attributes, e.g. priority or QoS involving identification of individual flows

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Evolutionary Computation (AREA)
  • Evolutionary Biology (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Artificial Intelligence (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明属于流量采样技术领域，具体涉及一种基于共享计数树的存储空间优化采样方法。本发明旨在节约采样设备存储空间，具体包括根据采样判断机制决定是否对到来的数据包进行采样；如果决定对到来的数据包进行采样，在哈希流跟踪表中对该数据包所属流节点进行检索；若未检索到采样数据包所属流节点，则为该数据包在流跟踪表中新建流节点；当对某条流终止采样时，将该流在流节点和共享计数树集合中存储的特征值还原并导入到有序流特征记录缓冲区中；待缓冲区已满，将采样流特征记录写入到文件中。

Description

一种基于共享计数树的存储空间优化采样方法
技术领域
本发明属于流量采样技术领域，具体涉及一种基于共享计数树的存储空间优化采样方法。
背景技术
近些年，互联网中应用的种类和数量有了显著的发展。为应对应用变化对网络带来的影响，网络管理者需要对流量应用特征进行测量，在测量的过程中需要对流量进行应用分类。为支持应用分类，采样流量应保留足够的应用特征。现代应用程序的一个具体会话通常是由多条流组成，会话中每一条流的源IP相同但目的IP可能互异。若在某一应用程序会话中采到更多的流，则会为采样流量保留更多的应用特征，进而有助于机器学习算法准确地对采样流量进行应用识别。RelSamp只会对一定范围内的源IP所对应的流进行采样，而且在有效采样比恒定的情况下，它可以通过提高流采样概率，降低包采样概率来提高在应用程序会话中所采到的流的数量，更多地保留采样流量的应用特征。但是，针对流的任意一个统计特征，例如，流大小，RelSamp需要为每一条流分配一个计数器来记录其大小。为每个计数器分配的空间都要一致且要保证计数器的计数范围能够涵盖最大流的计数值。网络流量分布具有重尾分布的特点，即占小比例的大流占据了网络流量中的大比例。有研究表明，按照流大小对流进行排序，排在前15％的流占据了流量总体的95％。为每条流分配空间大小一致的计数器来记录流大小，必然会造成流量采样设备存储空间的大量浪费。为每一条流分配空间大小一致的计数器来记录其他统计特征(例如，采样过程中，该流FIN，SYN以及ACK包到来的个数)也同样会对流量采样设备的存储空间造成浪费。尤其是当RelSamp部署在网络流并发量巨大的高速网络环境中时，会对流量采样设备造成巨大的存储压力。
发明内容
本发明的目的在于提供节约采样设备存储空间的一种基于共享计数树的存储空间优化采样方法。
本发明的目的通过如下技术方案来实现：包括以下步骤：
步骤1：根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure BDA0002503152910000011
确定输出包采样概率pp和当前流采样概率pf；
步骤2：从数据包缓冲队列提取数据包，并为该数据包分配两个取值范围在[0，1)的随机数rf和rp；
步骤3：获取数据包的源IP并计算该源IP的哈希值；
步骤4：将源IP的哈希值与源IP选择概率ph相乘得到目标值；
步骤5：若目标值落在预先配置好的范围内，则执行步骤6；否则抛弃该数据包；
步骤6：搜索数据包所属流节点；
若没有查找到该数据包对应的流节点且rf≤pf，则对该数据包进行采样并为该数据包创建一个流节点，新建流特征存储单元，并更新该流的流特征存储单元；
若查找到该数据包所属流节点且rp≤pp，则对该数据包进行采样并更新该流的流特征存储单元；
若没有查找到该数据包对应的流节点且rf＞pf，或查找到该数据包所属流节点且rp＞pp时抛弃该数据包；
步骤7：当对某条流的采样结束后，将存储在流节点中的流特征以及存储在共享计数树中的流统计特征还原为完整的流记录，并将流记录加入到流记录缓冲队列中；待缓冲区已满，将采样流特征记录写入到文件中。
本发明还可以包括：
所述的步骤1中根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure BDA0002503152910000021
确定输出包采样概率pp和当前流采样概率pf的具体步骤为：
步骤1.1：输入预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure BDA0002503152910000022
步骤1.2：初始化包采样概率pp和当前流采样概率pf；
pp＝pe/ph
pf＝pe/ph
步骤1.3：令
Figure BDA0002503152910000023
步骤1.4：获取当前采样比px；
步骤1.5：若
Figure BDA0002503152910000024
则输出包采样概率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，
Figure BDA0002503152910000031
在存储流长度的共享计数树中对该流进行c次计数；若数据包不是TCP数据包或者TCP数据包没被置位，则不需在共享计数树中对该数据包所属流的ACK包个数，SYN包个数，FIN包个数和RST包个数特征进行计数。
所述的步骤6中更新流的流特征存储单元的具体步骤为：
步骤6.1：更新流节点中的流最近更新时间；
步骤6.2：对该数据包进行解析，计算出该数据包应用层有效负载长度；
步骤6.3：若该数据包应用层有效负载长度大于原有最大有效载荷长度，则对最大有效载荷长度进行更新；若该数据包应用层有效负载长度小于原有最小有效载荷长度，则对最小有效载荷长度进行更新；
步骤6.4：在共享计数树中更新统计特征值。
所述的步骤6.4中在共享计数树中更新统计特征值的具体步骤为：
步骤6.4.1：提取出数据包的五元组信息，对五元组信息进行哈希，定位该数据包在流表中所对应的流节点，并从流节点中提取出该流的流标签ftuple；
步骤6.4.2：生成随机数i，i∈[0，r)；
步骤6.4.3：从随机数集合S中选择S[i]与流标签ftuple进行异或，并将异或值作为参数传给主哈希函数H，生成哈希函数hi；计算哈希值
Figure BDA0002503152910000032
定位本次计数的加强计数器；其中，p为加强计数器的数量；
步骤6.4.4：更新统计特征值C[u]，C[u]←C[u]+1；
如果C[u]没有溢出，则本步骤结束，完成对统计特征值的更新；
如果C[u]溢出且其父节点的下标大于或等于虚拟根节点的下标，则加强计数器L[u]溢出，不再使用该共享计数树计数；
如果C[u]溢出且其父节点的下标小于虚拟根节点的下标，更新u，
Figure BDA0002503152910000033
重新执行步骤6.4.4。
所述的步骤7中从共享计数树中还原该流数据统计特征值的具体步骤为
步骤7.1：从结束采样流的流节点中提取流标签ftuple；
步骤7.2：将随机数集合S中的元素S[i]依次与流f的流标签进行异或，并将异或值作为参数传给主哈希函数H，分别计算出r个哈希值
Figure BDA0002503152910000041
定位记录该流统计特征值的r个加强计数器及子树计数器；
步骤7.3：计算流的统计特征值s；
Figure BDA0002503152910000042
其中，Xi为子树计数器的值；li为子树计数器的高度；n为目前共享计数树的总计数值；ki为子树计数器中叶子节点的个数，
Figure BDA0002503152910000043
本发明的有益效果在于：
本发明提出的一种基于共享计数树的存储空间优化采样方法并不会影响SVM分类器和C4.5分类器对采样流量应用识别的准确率，而且本发明在采样过程中仅需少量的存储空间。具体来说，用SVM分类器对本发明的采样流量进行应用识别，在所识别的各应用中，应用识别的平均精度为0.867；用C4.5分类器对本发明的采样流量进行应用识别，在所识别的各应用中，应用识别的平均精度为0.891。以9GB流量作为输入，在采样过程中，本发明最多仅需700KB的存储空间，最少仅需200KB的存储空间。
附图说明
图1是本发明的总体框架图。
图2是本发明中确定相关采样概率的流程图。
图3是本发明中采样判断策略的流程图。
图4是本发明中更新流特征存储单元实例图。
图5是三层的共享计数树存储结构图。
图6是三层的共享计数树逻辑结构图。
图7是计数器存储结构图。
图8是加强计数器图。
图9是加强计数器向量图。
图10是五元组信息为tuple3的流特征记录还原过程实例图。
图11是用以说明子树计数器中根节点的选择方法的图例。
具体实施方式
下面结合附图对本发明做进一步描述。
本发明提出了一种基于共享计数树的存储空间优化采样方法-MiniSamp。如图1所示，MiniSamp的技术方案如下：
(1)根据采样判断机制决定是否对到来的数据包进行采样。
(2)如果决定对到来的数据包进行采样，在哈希流跟踪表中对该数据包所属流节点进行检索；若未检索到采样数据包所属流节点，则为该数据包在流跟踪表中新建流节点。
(3)流特征存储结构由流特征存储单元构成，流特征存储单元由采样流节点和在共享计数树集合中记录采样流统计特征值的计数器组成。在流跟踪表中定位到采样数据包所属流节点之后，对采样数据包的相关特征进行提取，并分别在流节点和共享计数树集合中更新采样流特征值。
(4)当对某条流终止采样时，将该流在流节点和共享计数树集合中存储的特征值还原并导入到有序流特征记录缓冲区中；待缓冲区已满，将采样流特征记录写入到文件中。
(5)将采样流特征记录文件输入到预先训练好的分类器中，并以流为单位生成应用分类的结果。
(1)确定相关采样概率
采样过程中，MiniSamp对每个到来的数据包进行三个阶段的判断，并根据判断的结果决定是否对其采样。这三个阶段分别是源IP选择阶段，流选择阶段以及包选择阶段。在这三个阶段中分别对应三个概率，ph，pf以及pp。其中ph可以在源IP选择阶段控制所采样源IP集合的规模，pf在流选择阶段可以对确定采样源IP所采流的个数进行控制，pp可以控制采样流中所采数据包的个数。
在正式开始采样之前，首先要确定采样概率ph，pf以及pp的值。网络运营人员通常会预先配置有效采样比pe以及ph(ph≥pe)，并根据其采样目的指定
Figure BDA0002503152910000051
在确定采样概率的过程中，利用一种迭代式算法，以到来的数据包作为输入，对pf及pp的值不断进行二分查找，目的是在确保有效采样比为pe的前提下，使得pf不断逼近
Figure BDA0002503152910000052
并得出此时pp的值。当ph，pf，pp三个采样概率已经确定后，将在确定采样概率阶段中生成的采样流特征记录全部丢弃，并开始正式采样。确定采样概率的流程图如图2所示。
(2)采样机制
捕包线程在流量采样设备的网卡处循环捕包，并将捕到的TCP或UDP数据包存入到数据包缓冲队列中。存在状态标志tag，在采样阶段将tag设置为1。
对采样判断逻辑进行说明，首先从数据包缓冲队列取包，并为该数据包分配两个取值范围在[0，1)的随机数，分别用rf和rp表示。在源IP选择阶段中，对该数据包的源IP进行哈希，将哈希值与ph相乘得到目标值，如果该目标值落在预先配置好的范围内，则进入到流选择阶段，否则抛弃该数据包。在流选择阶段中，对该数据包的五元组信息(源IP，源端口，目的IP，目的端口，传输层协议)进行哈希，根据哈希值在哈希流表中对该数据包所属流的流节点进行检索，若没有查找到该包对应的流节点，且rf≤pf，则对该数据包进行采样，并为其在流表中创建流节点；若查找到该包所属流节点，则进入包选择阶段，若rp≤pp，则对该数据包进行采样，并对该数据包所属的流存储单元进行更新；否则，抛弃该数据包。其流程图如图3所示。
(3)流特征更新
MiniSamp是一种支持应用分类的采样算法，为支持机器学习算法对采样流量进行应用类型识别，MiniSamp在采样过程中对可用于应用分类的流统计特征进行记录。通过参考现有的支持流量应用分类的特征，并结合自身背景，MiniSamp生成的单向采样流记录由如下流特征组成：传输层协议，源端口，目的端口，最小有效负载长度，最大有效负载长度，数据包数量，总数据长度，平均段大小，ACK包个数，SYN包个数，FIN包个数，RST包个数。其中最小有效负载长度，最大有效负载长度，数据包数量等特征可用于识别UDP应用，ACK包个数，SYN包个数，FIN包个数，RST包个数，平均段大小等特征可用于识别TCP应用；传输层协议，源端口，目的端口，总数据长度等特征既可用于识别TCP应用也可用于识别UDP应用。在UDP流记录中，将有关TCP标志位的统计特征值均置为0。
MiniSamp将单向流的应用特征分别存储在流节点和共享计数树集合中，将源IP，目的IP，源端口，目的端口，传输层协议，最小有效负载长度，最大有效负载长度，流到达时间，流最近更新时间等信息记录在流节点中，将数据包个数，总数据长度，ACK包个数，SYN包个数，FIN包个数，RST包个数等信息记录在各自的共享计数树中。流特征存储单元由流节点和共享计数树记录该流统计特征值的计数器组成。
当为采样数据包新建流特征存储单元时，对数据包进行解析，将五元组信息，流到达时间，流最近更新时间，最小有效负载长度以及最大有效负载长度写入流节点中，其中流最近更新时间与流到达时间均为当前时间，最小有效负载长度和最大有效负载长度均为该数据包的应用层有效负载长度。若该数据包为TCP数据包，对TCP首部进行解析，检测标志位ACK，FIN，SYN，RST是否在其中被置位，若被置位，则在对应的共享计数树中对该流到来的标志位数据包个数进行计数；在存储流大小的共享计数树中对该流进行计数；计算该数据包的长度len，以32B为一个数据块，得出该数据包所占的数据块数c。在存储流长度的共享计数树中对该流进行c次计数。c的计算公式如下：
Figure BDA0002503152910000071
当对数据包的流特征存储单元进行更新时，首先更新流节点中的流最近更新时间，然后对该数据包进行解析，计算出该数据包应用层有效负载长度，将其与流节点中的最大有效载荷长度和最小有效载荷长度分别进行比较，如果该长度大于原有最大有效载荷长度，则对最大有效载荷长度进行更新；如果该长度小于原有最小有效载荷长度，则对最小有效载荷长度进行更新。对共享计数树的更新操作与建立流特征存储单元时相同。MiniSamp更新流特征存储单元实例如图4所示，其中SCT是共享计数树(Shared Counter Tree)的缩写。
对在共享计数树中更新采样流的统计特征值的过程进行介绍。为记录采样流的某个统计特征值，在采样过程中为所有采样流分配若干个共享的计数器。将这些计数器在逻辑上组织成一棵近似二叉树，便构成了MiniSamp中的共享计数树。
对共享计数树做如下说明，为其分配的存储空间为N比特，为每个计数器所分配的空间为a比特，共享计数树中的计数器个数为N/a。共享计数树的高度为h，共有h层，最下层为第0层，最上层为第h-1层。计数树中的叶子节点的个数为p，计数树中的非叶子节点的度为2。如果h-1层节点的个数超过了1个，则在计数树中设置一个虚拟根节点。一个三层的共享计数树存储结构如图5所示，逻辑结构如图6所示。
在计数器中，使用最高位作为状态位，使用余下的a-1位进行计数，计数器存储结构如图7所示。
用C[i]，i∈[0，p)来表示计数树的某个叶子节点，从C[i]到根节点的路径上所包含的节点构成了一个加强计数器，称它为L[i]。例如，L[0]＝{C[0]，C[8]，C[12]}是一个加强计数器。因为计数树中共有p个叶子节点，故其中含有p个加强计数器。用向量L来表示计数树中的加强计数器集合，有L＝{L[1]，L[2]，...，L[p-1]}。加强计数器如图8所示。
为任意一条采样流f，通过流的五元组信息以及相互独立的r个哈希函数hi从p个加强计数器中选取r(r＜＜p)个加强计数器。这r个加强计数器构成了流f的加强计数器向量，用Lf表示该向量，将Lf中的第i个元素，表示为Lf[i]。Lf[i]的具体计算公式如下，其中i∈[0，r)，哈希函数hi的值域是[0，p-1)。
Lf[i]＝L[hi(f)] (2)
为了降低设计哈希函数的难度，可以不真正地设计r个相互独立的哈希函数，而是只设计一个主哈希函数H并利用一个由r个元素组成的集合S来模拟r个相互独立的哈希函数。使用哈希函数hi对流f进行哈希运算的公式如下：
Figure BDA0002503152910000081
因为r<<p，从共享计数树的p个加强计数器中，随机选取r个各不相同的计数器的概率是
Figure BDA0002503152910000082
因此向量Lf中的各加强计数器是互异的。
在图9中，r＝3，流f的加强计数器向量Lf＝{L[1],L[0],L[4]}，流g的加强计数器向量Lg＝{L[3],L[4],L[6]}。其中加强计数器L[4]被流f与流g共享，因不同的流可以共享相同的加强计数器，故共享计数树可以记录的流的数量远远大于其加强计数器的数量。
在共享计数树中更新采样流数据包个数，ACK包个数，SYN包个数，FIN包个数，RST包个数等统计特征值的步骤如下：
步骤1：提取出到来数据包的五元组信息，对五元组信息进行哈希，定位该数据包在流表中所对应的流节点，并从流节点中提取出该流的流标签，其中流标签由源IP，源端口，目的IP，目的端口，传输层协议，该流到达时间等信息组成。假设到来数据包所属流为f，其流标签为ftuple。
步骤2：生成随机数i，其中i∈[0，r)。
步骤3：H为主哈希函数，从随机数集合S中选择S[i]与流标签ftuple进行异或，其中随机数集合S的规模为r，并将异或值作为参数传给主哈希函数H，生成哈希函数hi，计算哈希值
Figure BDA0002503152910000083
定位本次计数的加强计数器。
步骤4：C[u]←C[u]+1。如果C[u]没有溢出，则本步骤结束。如果C[u]溢出且其父节点的下标大于或等于虚拟根节点的下标，则加强计数器L[u]溢出，不再使用该共享计数树计数。如果C[u]溢出且其父节点的下标小于虚拟根节点的下标，将C[u]的状态位设置为1，并按照公式5更新u，并继续执行本步骤。
Figure BDA0002503152910000084
在采样过程中使用共享计数树记录流总数据长度的步骤如下：
步骤1：对到来的数据包进行解析，计算出该数据包的长度为len，以32B为一个数据块，计算出该数据包的数据块数c。
步骤2：c←c–1。
步骤3：在共享计数树中对数据包所属流的数据块个数进行1次计数。
步骤4：若c小于0，则对流总数据长度的计数过程结束，否则转至步骤2。
(4)流特征还原
流特征还原线程每10s启动一次，当对某条流的采样结束后，流记录还原线程将存储在流节点中的流特征以及存储在共享计数树中的流统计特征还原为完整的流记录，并将流记录加入到流记录缓冲队列中。
流特征还原线程首先将状态标志tag设置为0，此时不进行采样，将捕获的数据包暂存在数据包缓冲队列中。为不影响正在进行的采样操作，等待0.25s再获取流表的互斥锁，并获取当前时间；对流表中的流节点依次进行扫描，对每一流节点进行扫描的过程中，计算流最近更新时间距当前时间的时间间隔，如果时间间隔大于16秒，则认为该流在网络环境中已经不处于活跃状态，结束对该流的采样，此时，利用该流五元组信息，流到达时间在共享计数树集合中分别还原出采样流的数据包个数，总长度，ACK包个数，SYN包个数，FIN包个数，RST包个数等统计特征值，将流总长度乘以32，再除以数据包个数得出流的平均段长度；将流节点中的五元组信息，流到达时间，流持续时间，最小有效负载长度，最大有效负载长度以及在共享计数树集合中还原的各统计特征值和平均段长度写入到流记录缓冲区中；将流记录加入到流记录缓冲队列中。如果流记录缓冲队列中流记录的个数超过m(其中m远远小于哈希表的规模)，则获取有序流记录缓冲队列的互斥锁，其中有序流记录缓冲队列对流记录以源IP和流到达时间进行有序排列。将流记录缓冲队列中的所有流记录元素出队并加入到有序流记录缓冲队列中之后，释放对有序流记录缓冲队列的互斥锁。当对流表中所有流节点扫描还原完成后，释放流表的互斥锁，并将状态标志tag设置为1，流特征还原阶段结束，重新开始采样。五元组信息为tuple3的流特征记录还原过程实例如图10所示。
在MiniSamp中使用主机活动周期的概念来近似代替应用程序会话。主机活动周期是一组源IP相同的流的集合，集合中流所属的应用类型可能不同，对其中的流以到达时间排序，集合中的每条流的到达时间与它前一条流的到达时间的时间间隔小于t秒。输出线程将有序流记录缓冲队列中的流记录以主机活动周期为单位输出到采样流记录文件中。
对从共享计数树中还原采样流的统计特征值的过程进行介绍。引入子树计数器的概念，在图6中，以C[13]为根的子树中包含节点C[13]，C[10]，C[11]，C[4]，C[5]，C[6]，C[7]。子树中的所有节点组成了一个子树计数器，子树计数器的值可用如下方法来计算，例如计算以C[13]为根的子树计数器的值，value(13)＝22aC[13]+2a(C[10]+C[11])+(c[4]+C[5]+C[6]+C[7])。共享计数树中的某个节点是否可以作为子树的根节点与该节点计数器的状态位有关，每个加强计数器对应一个子树计数器。在图11中，以加强计数器L[4]为例，说明子树计数器中根节点的选择方法。在(a)中，因为C[4]计数器未溢出，所以未对C[4]设置状态位，那么以C[4]为其子树的根节点，不需再判断是否可以以C[4]的祖先节点为根节点，该子树中只有一个叶子节点C[4]，该子树的高度为L＝1。在(b)中C[4]计数器溢出，C[10]计数器未溢出。所以对C[4]设置状态位，那么以C[10]为其子树的根节点，不需再判断是否可以以C[10]的祖先节点为根节点，该子树中只有两个叶子节点C[4]，C[5]，一个非叶子节点C[10]，该子树的高度为L＝2。在(c)中C[4]计数器溢出，C[10]计数器溢出。所以对C[4]，C[10]设置状态位，那么以C[13]为子树的根节点，该子树中有四个叶子节点C[4]，C[5]，三个非叶子节点C[10]，C[11]，C[13]，该子树的高度为L＝3。
从共享计数树中还原该流数据包个数，ACK包个数，SYN包个数，FIN包个数，RST包个数，总数据块数等统计特征值的步骤如下：
步骤1：从结束采样流f的流节点中提取流标签ftuple。
步骤2：H为主哈希函数，将随机数集合S中的元素S[i]，i∈[0，r)依次与流f的流标签进行异或，并将异或值作为参数传给主哈希函数H，分别计算出r个哈希值
Figure BDA0002503152910000101
Figure BDA0002503152910000102
定位记录该流统计特征值的r个加强计数器及子树计数器。
步骤3：分别计算r个子树计数器的值Xi，i∈[0，r)。
步骤4：分别将r个子树计数器的高度li计算出来，并分别计算r个子树计数器中叶子节点的个数
Figure BDA0002503152910000103
步骤5：计算目前共享计数树的总计数值n。
步骤6：通过公式6计算流f的统计特征值，其中公式6是通过统计学原理推导出的，其结果是需还原的统计特征值的估计量，并可以证明该估计量是该统计特征值的无偏估计量。
Figure BDA0002503152910000104
当对流f结束采样时，MiniSamp从共享计数树中还原该流总数据长度的步骤如下：
步骤1：还原流f的总数据块数c。
步骤2：计算流f的长度len，其中len←32×c。
本发明提出的一种基于共享计数树的存储空间优化采样方法并不会影响SVM分类器和C4.5分类器对采样流量应用识别的准确率，而且本发明在采样过程中仅需少量的存储空间。具体来说，用SVM分类器对本发明的采样流量进行应用识别，在所识别的各应用中，应用识别的平均精度为0.867；用C4.5分类器对本发明的采样流量进行应用识别，在所识别的各应用中，应用识别的平均精度为0.891。以9GB流量作为输入，在采样过程中，本发明最多仅需700KB的存储空间，最少仅需200KB的存储空间。
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (8)

1.一种基于共享计数树的存储空间优化采样方法，其特征在于，包括以下步骤：
步骤1：根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure FDA0002503152900000011
确定输出包采样概率pp和当前流采样概率pf；
步骤2：从数据包缓冲队列提取数据包，并为该数据包分配两个取值范围在[0，1)的随机数rf和rp；
步骤3：获取数据包的源IP并计算该源IP的哈希值；
步骤4：将源IP的哈希值与源IP选择概率ph相乘得到目标值；
步骤5：若目标值落在预先配置好的范围内，则执行步骤6；否则抛弃该数据包；
步骤6：搜索数据包所属流节点；
若没有查找到该数据包对应的流节点且rf≤pf，则对该数据包进行采样并为该数据包创建一个流节点，新建流特征存储单元，并更新该流的流特征存储单元；
若查找到该数据包所属流节点且rp≤pp，则对该数据包进行采样并更新该流的流特征存储单元；
若没有查找到该数据包对应的流节点且rf＞pf，或查找到该数据包所属流节点且rp＞pp时抛弃该数据包；
步骤7：当对某条流的采样结束后，将存储在流节点中的流特征以及存储在共享计数树中的流统计特征还原为完整的流记录，并将流记录加入到流记录缓冲队列中；待缓冲区已满，将采样流特征记录写入到文件中。
2.根据权利要求1所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤1中根据预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure FDA0002503152900000012
确定输出包采样概率pp和当前流采样概率pf的具体步骤为：
步骤1.1：输入预先配置的有限采样比pe、源IP采样概率ph以及目标流采样概率
Figure FDA0002503152900000013
步骤1.2：初始化包采样概率pp和当前流采样概率pf；
pp＝pe/ph
pf＝pe/ph
步骤1.3：令
Figure FDA0002503152900000014
步骤1.4：获取当前采样比px；
步骤1.5：若
Figure FDA0002503152900000021
则输出包采样概率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。
3.根据权利要求1或2所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤6中为数据包新建流特征存储单元的具体方法为：对数据包进行解析，将五元组信息、流到达时间、流最近更新时间、最小有效负载长度以及最大有效负载长度写入流节点中；其中，流最近更新时间与流到达时间均为当前时间；最小有效负载长度和最大有效负载长度均为该数据包的应用层有效负载长度；若该数据包为TCP数据包，对TCP首部进行解析，检测标志位ACK、FIN、SYN、RST是否在其中被置位；若TCP数据包被置位，则在对应的共享计数树中对该流到来的标志位数据包个数进行计数；在存储流大小的共享计数树中对该流进行计数；计算该数据包的长度len，以32B为一个数据块，得出该数据包所占的数据块数c，
Figure FDA0002503152900000022
在存储流长度的共享计数树中对该流进行c次计数；若数据包不是TCP数据包或者TCP数据包没被置位，则不需在共享计数树中对该数据包所属流的ACK包个数，SYN包个数，FIN包个数和RST包个数特征进行计数。
4.根据权利要求1或2所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤6中更新流的流特征存储单元的具体步骤为：
步骤6.1：更新流节点中的流最近更新时间；
步骤6.2：对该数据包进行解析，计算出该数据包应用层有效负载长度；
步骤6.3：若该数据包应用层有效负载长度大于原有最大有效载荷长度，则对最大有效载荷长度进行更新；若该数据包应用层有效负载长度小于原有最小有效载荷长度，则对最小有效载荷长度进行更新；
步骤6.4：在共享计数树中更新统计特征值。
5.根据权利要求3所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤6中更新流的流特征存储单元的具体步骤为：
步骤6.1：更新流节点中的流最近更新时间；
步骤6.2：对该数据包进行解析，计算出该数据包应用层有效负载长度；
步骤6.3：若该数据包应用层有效负载长度大于原有最大有效载荷长度，则对最大有效载荷长度进行更新；若该数据包应用层有效负载长度小于原有最小有效载荷长度，则对最小有效载荷长度进行更新；
步骤6.4：在共享计数树中更新统计特征值。
6.根据权利要求4所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤6.4中在共享计数树中更新统计特征值的具体步骤为：
步骤6.4.1：提取出数据包的五元组信息，对五元组信息进行哈希，定位该数据包在流表中所对应的流节点，并从流节点中提取出该流的流标签ftuple；
步骤6.4.2：生成随机数i，i∈|0，r)；
步骤6.4.3：从随机数集合S中选择S[i]与流标签ftuple进行异或，并将异或值作为参数传给主哈希函数H，生成哈希函数hi；计算哈希值
Figure FDA0002503152900000031
定位本次计数的加强计数器；其中，p为加强计数器的数量；
步骤6.4.4：更新统计特征值C[u]，C[u]←C[u]+1；
如果C[u]没有溢出，则本步骤结束，完成对统计特征值的更新；
如果C[u]溢出且其父节点的下标大于或等于虚拟根节点的下标，则加强计数器L[u]溢出，不再使用该共享计数树计数；
如果C[u]溢出且其父节点的下标小于虚拟根节点的下标，更新u，
Figure FDA0002503152900000032
重新执行步骤6.4.4。
7.根据权利要求5所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤6.4中在共享计数树中更新统计特征值的具体步骤为：
步骤6.4.1：提取出数据包的五元组信息，对五元组信息进行哈希，定位该数据包在流表中所对应的流节点，并从流节点中提取出该流的流标签ftuple；
步骤6.4.2：生成随机数i，i∈|0，r)；
步骤6.4.3：从随机数集合S中选择S[i]与流标签ftuple进行异或，并将异或值作为参数传给主哈希函数H，生成哈希函数hi；计算哈希值
Figure FDA0002503152900000033
定位本次计数的加强计数器；其中，p为加强计数器的数量；
步骤6.4.4：更新统计特征值C[u]，C[u]←C[u]+1；
如果C[u]没有溢出，则本步骤结束，完成对统计特征值的更新；
如果C[u]溢出且其父节点的下标大于或等于虚拟根节点的下标，则加强计数器L[u]溢出，不再使用该共享计数树计数；
如果C[u]溢出且其父节点的下标小于虚拟根节点的下标，更新u，
Figure FDA0002503152900000041
重新执行步骤6.4.4。
8.根据权利要求6或7所述的一种基于共享计数树的存储空间优化采样方法，其特征在于：所述的步骤7中从共享计数树中还原该流数据统计特征值的具体步骤为
步骤7.1：从结束采样流的流节点中提取流标签ftuple；
步骤7.2：将随机数集合S中的元素S[i]依次与流f的流标签进行异或，并将异或值作为参数传给主哈希函数H，分别计算出r个哈希值
Figure FDA0002503152900000044
定位记录该流统计特征值的r个加强计数器及子树计数器；
步骤7.3：计算流的统计特征值s；
Figure FDA0002503152900000042
其中，Xi为子树计数器的值；li为子树计数器的高度；n为目前共享计数树的总计数值；ki为子树计数器中叶子节点的个数，
Figure FDA0002503152900000043
CN202010438372.8A 2020-05-22 2020-05-22 一种基于共享计数树的存储空间优化采样方法 Active CN111581489B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010438372.8A CN111581489B (zh) 2020-05-22 2020-05-22 一种基于共享计数树的存储空间优化采样方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010438372.8A CN111581489B (zh) 2020-05-22 2020-05-22 一种基于共享计数树的存储空间优化采样方法

Publications (2)

Publication Number Publication Date
CN111581489A true CN111581489A (zh) 2020-08-25
CN111581489B CN111581489B (zh) 2023-03-24

Family

ID=72115966

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010438372.8A Active CN111581489B (zh) 2020-05-22 2020-05-22 一种基于共享计数树的存储空间优化采样方法

Country Status (1)

Country Link
CN (1) CN111581489B (zh)

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101227318A (zh) * 2007-12-04 2008-07-23 东南大学 高速网络流量的超点实时检测方法
CN101668006A (zh) * 2009-10-12 2010-03-10 哈尔滨工程大学 一种用于异常检测的自适应网络流量采样方法
US8864583B1 (en) * 2011-05-03 2014-10-21 Open Invention Network, Llc Computing device independent and transferable game level design and other objects
CN104317801A (zh) * 2014-09-19 2015-01-28 东北大学 一种面向大数据的数据清洗系统及方法
CN104463922A (zh) * 2014-12-03 2015-03-25 天津大学 一种基于集成学习的图像特征编码及识别方法
CN104715418A (zh) * 2015-03-16 2015-06-17 北京航空航天大学 一种新型社会网络采样方法
US20180276220A1 (en) * 2014-06-26 2018-09-27 Google Llc Batch-optimized render and fetch architecture

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101227318A (zh) * 2007-12-04 2008-07-23 东南大学 高速网络流量的超点实时检测方法
CN101668006A (zh) * 2009-10-12 2010-03-10 哈尔滨工程大学 一种用于异常检测的自适应网络流量采样方法
US8864583B1 (en) * 2011-05-03 2014-10-21 Open Invention Network, Llc Computing device independent and transferable game level design and other objects
US20180276220A1 (en) * 2014-06-26 2018-09-27 Google Llc Batch-optimized render and fetch architecture
CN104317801A (zh) * 2014-09-19 2015-01-28 东北大学 一种面向大数据的数据清洗系统及方法
CN104463922A (zh) * 2014-12-03 2015-03-25 天津大学 一种基于集成学习的图像特征编码及识别方法
CN104715418A (zh) * 2015-03-16 2015-06-17 北京航空航天大学 一种新型社会网络采样方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
ZHE LIN ET AL.: "Towards Efficient and Scalable Acceleration of Online Decision Tree Learning on FPGA", 《2019 IEEE 27TH ANNUAL INTERNATIONAL SYMPOSIUM ON FIELD-PROGRAMMABLE CUSTOM COMPUTING MACHINES》 *
陈炳宪: "社交网络的数据采集策略研究与应用", 《中国优秀硕士学位论文全文数据库 (信息科技辑)》 *

Also Published As

Publication number Publication date
CN111581489B (zh) 2023-03-24

Similar Documents

Publication Publication Date Title
CN107566206B (zh) 一种流量测量方法、设备及系统
EP2530874B1 (en) Method and apparatus for detecting network attacks using a flow based technique
US8964548B1 (en) System and method for determining network application signatures using flow payloads
CN111131084B (zh) 一种QoS感知的OpenFlow流表查找方法
US8578024B1 (en) Network application signatures for binary protocols
CN101459560B (zh) 长流的识别方法、数据流量的测量方法及其设备
CN110858823B (zh) 一种数据包的分类方法、装置及计算机可读存储介质
CN110535825B (zh) 一种特征网络流的数据识别方法
CN112350956B (zh) 一种网络流量识别方法、装置、设备及机器可读存储介质
US8064359B2 (en) System and method for spatially consistent sampling of flow records at constrained, content-dependent rates
Chen et al. Distinct counting with a self-learning bitmap
CN112119613A (zh) 具有流大小检测器的转发元件数据平面
CN115297059B (zh) 一种基于p4的传输层负载均衡系统
CN113518130A (zh) 一种基于多核处理器的分组突发负载均衡方法及系统
CN113965492A (zh) 一种数据流统计方法及装置
Turkovic et al. Detecting heavy hitters in the data-plane
CN117827851B (zh) 一种用于流基数测量的数据处理结构及其应用
CN111581489B (zh) 一种基于共享计数树的存储空间优化采样方法
CN111200542B (zh) 一种基于确定性替换策略的网络流量管理方法及系统
CN111835599A (zh) 一种基于SketchLearn的混合网络测量方法、装置及介质
CN110022343B (zh) 自适应事件聚合
CN112416820B (zh) 一种数据包分类存储方法及系统
CN116303585A (zh) 一种基于Flag标志位的数据流计数方法、设备和存储介质
CN114745336B (zh) 基于rfc的报文分类方法、装置、计算机设备和存储介质
Wang et al. Robust pipelined memory system with worst case performance guarantee for network processing

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant