英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
基于FPGA的位矢量编码简易CART结构的低延迟流量分类
文章信息：本文从2019年4月11号开始，结尾于2019年10月30号，2019年10月31号被收入，2019年12月20号可在网上查看。
关键词：流量分类，机器学习，简易CART，高吞吐量，低延迟，FPGA，数据结构
摘要
流量分类是在网络交通实时流动过程中确定应用类型的过程。基于机器学习（ML）的分类方法可以利用流量的统计特性对互联网流量进行分类，因为它能够在加密的流量条件下工作。在本篇论文中提出了一种新的基于ML的网络流量分类数据结构，称为位矢量编码简单CART（BC-SC）。BC-SC数据结构在应用程序类数量方面是一个可扩展的解决方案，同时与最先进的方法相比，在搜索延迟、内存需求和吞吐量方面提供了显著的改进。我们在现场可编程门阵列（FPGA）平台上设计了两种可供选择的硬件结构，即基于流水线和离散并行范围比较器（DPRC），以支持BC-SC数据结构。流水线和基于dprcbs的体系结构可以分别达到665和914千兆位/秒（Gbps）或2078和2857亿分类/秒（MCPS），最小数据包大小为40字节。并且所提出的引擎在八个应用等级下均能达到96.8125%的精度。
- 介绍
流量分类是许多重要的网络安全和管理过程的基础，如流量整形、流量优先、动态访问控制和入侵检测。在流量分类中，将传入的网络流量分类为一组应用程序类，然后，根据预定义的协议，可以对每个协议进行不同的处理，以向用户提供差异化服务。一旦这个过程在互联网流量期间被执行，它就被称为实时交通分类。
互联网流量分类方法可分为以下四种：（i）基于端口号，（ii）深度包检查（DPI）基于，（iii）基于启发式和（iv）基于机器学习（ML）。基于端口号的解决方案只检查网络打包的TCP或UDP端口号，应用程序类是通过查看在网络分配号码管理局（IANA）中注册的目标端口号来确定的。特别的是，一些应用程序（Kazaa、Napster）可能没有在IANA中注册自己的端口号。另外，新的应用程序可以使用不可预知的端口号来隐藏自己。因此，由于端口号使用的不稳定，基于端口号的方法的误分类率日益增加。由于基于端口号的技术导致了估计失误，并且2000年代病毒的广泛传播需要对数据包的有效负载进行深入的分析，因此这一领域的研究主要针对入侵检测系统（IDS）。基于DPI的方法实现签名分析，以识别每个应用程序的特定签名。然而，基于DPI的方法不能处理加密流量条件下的签名搜索。此外，政府还实施隐私法规，限制第三方合法审查数据包内容。基于启发式的技术根据网络流量的模式对网络流量进行分类。然而，这些方法需要大量的内存需求。对于存储交通模式来说，为了克服现有方法所遇到的这些问题，研究者们开始探索新的网络流量分类方法。基于机器学习（ML）的技术，能够利用流量的统计特性对互联网流量进行分类，已经成为人们期待已久的流量分类解决方案。
在基于ML的方法中，分类模型是从先前分类或标记的流集创建的。然后根据生成的模型对新的未知流进行分类。基于ML的分类方法由于其高精度、在加密流量条件下的操作能力以及在动态网络流量环境下的坚固性，近年来受到了研究者的广泛关注。本文首先阐述了我们以前设计的基于机器学习的流量分类器，即基于分类树和回归树的扩展简单CART（E-SC）。接下来，我们提出了一种新的基于机器学习的流量分类器，称为位向量编码简单车（BCSC），并设计了两种不同的硬件架构，称为基于流水线和离散并行距离比较器（DPRC）的现场可编程门阵列（FPGA）平台，支持BC-SC数据结构的实时流量分类。
本篇论文的主要贡献内容如下：
在机器学习算法中，最适合流水线硬件实现的是决策树[7,9,11]。[14]中首次引入的简单CART算法也创建了一个二叉决策树。该算法利用熵测度来确定最佳分割准则，并利用交叉验证方法来平衡树的大小来确定最合适的修剪。因此，简易CART算法产生了比C4.5更平衡的树结构，同时产生了更好的搜索性能，特别是在实时分类方面。在本研究中，我们建议使用简单的购物车（SC）为基础的算法进行实时交通分类。离散化预处理通常与基于决策树的解决方案结合使用，以提高分类精度并减小树的大小。另一方面，离散化过程破坏了树节点大小的一致性，使其难以在硬件上实现。为了使离散化的SC树更适合硬件，我们提出了一种基于SC树的数据结构，称为扩展的简单CART（E-SC），该数据结构通过在树节点中存储固定大小的位字符串来同步节点大小（第3.3节）。
bull;互联网应用程序的数量随着互联网用户数量的日益增加而增加。在基于决策树的解决方案中，树的深度与流量应用程序类的数量密切相关。随着类数的增加，需要更多的分支来区分这些类，因此树的深度进一步增加。为了使树的深度与应用类型的数量无关，我们提出了一种新的基于SC的数据结构，称为位矢量编码简单CART（BC-SC）。根据应用程序类型的数量，拟议的结构似乎是未来分类引擎的可扩展解决方案（第4节）。
bull;我们进一步提出了一种BC-SC上的距离间隔优化方法，它结合了相似的间隔，从而减少了距离树节点的数量。最后，节省了硬件资源，提高了分类器的吞吐量性能（第6节）。
bull;我们设计了两种可选的硬件架构来支持BC-SC数据结构；（i）流水线BC-SC和（ii）基于离散并行范围比较器（DPRC）的BC-SC。这两种架构各有优缺点。所提出的基于流水线和DPRC的BC-SC架构在最小数据包大小为40字节的情况下分别达到665和914 Gbps（2078和2857 MCPS）的吞吐量，同时两者都显示准确率为96.8125%（第7节）。
论文的其余部分安排如下：第二部分介绍了交通分类的背景和前人的工作。第三节介绍了基于CART的简单流量分类方法。第4节介绍BC-SC数据结构。BC-SC的体系结构和硬件实现包含在第5节中。第6节介绍了建议的数据结构。第7节给出了拟议设计的性能评估，第8节对论文进行了总结。
- 背景
2.1流量分类概述
在流量分类中，因特网协议（IP）交通被分类为预定义数量的应用程序类，同时使用经典的包级别（协议、源和目标端口号等）或流级别（到达间隔时间、平均包大小、最大包大小等）特征。将具有相同5元组头字段（源IP地址（SA）、目标IP地址（DA）、源端口号（SP）、目标端口号（DP）、协议）的一系列数据包定义为流。流级特征通常从流中的第一个R包获得，其中R被选为表示整个流的最佳值。即使在加密的流量条件下，包级别和流级别（统计）特征（或它们的不同组合）通常一起使用，以实现高精度。
2.2基于流量分类的机器学习
1990年首次提出了一种使用机器学习技术的网络流量控制，目的是为了最大限度地提高电路交换电信网络中的呼叫完成率[15]。ML算法在1994年首次用于流量分类[16]的场景是攻击检测。这项研究是许多交通分类研究的起点[6]。Roughan等人。提出了k近邻（k-NN）、线性判别分析（LDA）和二次判别分析（QDA）的机器学习算法[17]，对Ftp、Telnet和RealMedia的3个应用类、Telnet、Ftp、RealMedia和Dns的4个应用类和Dns、Ftp、Https的7个应用类进行分类，Kazaa、RealMedia、Telnet和www.Moore和Zuev提出了监督朴素贝叶斯（NB）机器学习技术[18]，具有248个基于全流的特征，用于分类应用类型，如批量数据传输、数据库、交互式、邮件、服务、www、P2P、攻击、游戏和多媒体。该分类器的流量精度达到65%。他们得出结论，C4.5算法似乎是他们定义的任何一组特征中最好的。Crotti等人。提出了一种利用分组长度、内部到达时间和分组到达时间特征的业务分类方法[24]。使用应用程序类http、Smtp和POP3，精度达到91%以上。Erman等人将无监督和半监督学习方法相结合，提出了一种半监督模型[25]。
Bonfiglio等人。提出了两种基于框架的实时Skype流量解析技术[26]。首先是用户的ChiSquare测试，通过对消息内容的随机分析来识别Skype指纹；其次是，通过消息大小和到达率特征来感知Skype流量的NB技术。NB技术已经被证明不管源应用是什么，在确定来自IP的话音通信量时是有效的。这个人的卡方检验分析了所有压缩和加密的Skype流量。Angevine和Zincir Heywood使用C4.5和AdaBoost算法对Skype流量进行了分类，该算法具有10个流统计特性[27]。Kim等人。本文提出的支持向量机（SVM）和C4.5算法具有9个流量统计特性，获得了97.8%的准确率[12]。Alshamari和Zincir Heywood研究了用于互联网流量分类的AdaBoost、SVM、NB、RIPPER和C4.5算法[13]。包括打包水平和流水平特征的22组功能被使用，其中C4.5算法的识别率97.8%，Ssh流量为83%。
Lim等人。利用NB、支持向量机、k-NN和C4.5决策树对网络流量进行分类，得到9个流量统计特征集[28]，C4.5算法对所有特征集的分类结果最为准确。Este等人。提出了一种基于支持向量机的Http、Smtp、Pop3、Ftp分类方法[29]。虽然支持向量机算法的训练阶段比较复杂，但其准确率达到了90%以上。Qu和Prasanna提出使用C4.5决策树算法对Msn、Skype、P2Ptv、Http、Qq Im、Skype Im、Thunder和Yahoo Im应用程序包[2]。转换成紧凑哈希表的C4.5树的准确率超过98.15%。对7个Vpn和7个非Vpn应用类进行了分类，准确率达到94.42%以上[30]。
2.2基于FPGA的流量分类
罗等人。提出了一种基于硬件的流量分类引擎，将C4.5决策树算法映射到FPGAs上[31]，姜和Gokhale在FPGAs上实现了k-NN算法，在对多媒体流量（Skype、即时消息（Im）、Iptv）进行分类时，实现了40gb/s的吞吐量[32]。Groleat等人。使用支持向量机算法对互联网流量进行了分类，并表明软件应用落后于硬件实现[33]。Monemi等人。提出了一种基于NetFPGA的67mhz决策树分类器[34]。
Tong等人。在两种不同的业务分类体系结构上实现了C4.5决策树算法[7]。根据现场可编程门阵列（FPGA）的结果，所提出的设计已达到520和6gbps的吞吐量。甘地等人。使用哈希表实现了C4.5决策树算法[11]。通过同时利用包级和流级特征，建立C4.5决策树，并将其转化为多个哈希表，对四个应用类（Skype、Msn、Thunder和http）进行分类。该设计在最先进的FPGA Virtex-7上实现，实现了165400万次/秒分类（MCPS）吞吐量。曲和普拉桑纳用规则集表表示决策树，并在FPGAs上实现。他们还使用包级别和流标签功能对应用程序类进行分类，如Msn、Skype、Http、Qq Im、P2Ptv、Skype Im、Thunder和Yahoo Im。根据地点和路径结果，得到645个MCPS的吞吐量。Tong等人。提出了一种基于决策树的流量分类加速器，可用于FPGA和具有8个internet应用类[35]多核平台。他们为每个平台提出了两种不同的设计方案，分别基于决策树（ODT）和分治（DQ）技术实现了10000 和8000 MCPS的吞吐量。Soylu等人。是第一个使用简单的CART算法，对互联网流量进行分类的一群人[1]。然而，原始的简单CART树是用一种新的数据结构来表示的，以使其适合硬件实现。该架构在并行和流水线架构上使用FPGAs实现，支持557gbps或1741mcps，精度为96.8%。文献[36]提出了一种简单的CART-forest数据结构，它包含多个用于交通分类的并行SC树。这个FPGAs上的流水线并行结构显示了854gbps的吞吐量，即每秒26.69亿个分类（MCPS），准确率为96.6719%。
- 基于流量分类的简易CART
3.1定义
机器学习的功能定义被正式定义为被观察现象的个体可测量特性。在分组分类中，由于我们估计了流量的类别（Skype、MSN等），我们的特征是源端口（SP）、目的端口（DP）、平均分组大小（AVG）、最小分组大小（MIN）等。
定义流量表示共享相同5元组头字段（SA、DA、SP、DP和Protocol）的一系列internet数据包。
3.2动机
基于机器学习的流量分类的主要性能指标是准确性、吞吐量和搜索延迟，决策树算法是最流行的解决方案，因为它们在硬件平台（如FPGAs）上具有很高的准确性和易实现性，但由于树结构的不平衡，它们将会有很大的搜索延迟[12,13]。
基于ML的算法利用了网络流量的统计特性。决策树是一种类似于流程图的数据结构，其中每个内部节点对特定功能执行测试。图1示出了使用因特网分组属性（源端口（SP）、目的端口（DP）、平均分组大小（AVG）、最小分组大小（MIN）和最大分组大小（MAX））将输入业务分类为应用类的示例二叉决策树例如Skype Tcp、Pplive、Sopcast和Msn。树中的叶节点表示应用程序类（类ID），其中非叶节点表示基于相应属性的决策。
最近的研究提出了流水线硬件架构来加速基于决策树的流量分类[7,9,11]。在这些解决方案中，经典的C4.5决策树由于其高精度和易于硬件应用而成为首选。此外，与其他决策树相比，C4.5决策树包含的节点数量相对较少，但它具有相当不平衡的结构，这会导致搜索操作的长延迟和应
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235965]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
