论文摘要
本文结合国家863计划“十一五”重大项目“新一代高可信网络”总体技术相关课题的研究需求,重点研究高速骨干网流量分析的前端处理算法及其工程实现技术。以布鲁姆过滤器为切入点,本文的研究工作包括三个方面:第一,布鲁姆过滤器的研究与改进;第二,基于布鲁姆过滤器的前端处理算法的设计;第三,高速骨干网业务流实时分类前端系统的设计与实现技术。首先,本文对现有的三种低计算复杂度的计数型布鲁姆过滤器（Counting Bloom Filter, CBF）进行了分析比较,并提出了改进。对Na?ve Counting Bloom Filte（rNCBF）、Space-Code Bloom Filter（SCBF）和d-left Counting Bloom Filter（dlCBF）进行了深入分析,给出了其参数最优设置准则。采用计数误差、空间复杂度和负载适应性为性能指标,对上述三种CBF的性能进行了系统比较。发现虽然就计数误差和空间复杂度而言,dlCBF是三种CBF中最优的,但dlCBF在负载适应性方面却存在缺陷。对dlCBF进行了改进,提出了一种具有良好负载适应性的计数型布鲁姆过滤器BSdlCBF（Binary-Shrinking d-left Counting Bloom Filter）。通过仿真实验,将BSdlCBF和dlCBF、NCBF以及SCBF进行了比较,结果表明BSdlCBF的性能明显优于已有的三种计数型布鲁姆过滤器。其次,本文将BSdlCBF应用于前端处理算法的设计。基于BSdlCBF,提出了一种新的骨干网数据流流量测量算法MR-BSdlCBF（Multi-Resolution BSdlCBF）,与已有的同类流量测量算法MRSCBF（Multi-Resolution SCBF）相比,MR-BSdlCBF算法的优势是负载适应性好,空间复杂度低,并可记录流标识。在MR-BSdlCBF算法基础上,本文最终提出了一种空间高效的数据包公平抽样算法SEFS（Space-Efficient Fair Sampling）,SEFS算法不仅空间复杂度低,而且对于短流的抽样性能明显优于已有的公平抽样算法。SEFS算法较低的空间复杂度使之易于以IP核（Intellectual Property Core）的形式集成到网络设备中去。最后,本文实现了骨干网业务流实时分类前端系统。提出了骨干网业务流实时分类系统的前后端分离的系统结构。该系统结构的优点是消除了前后端的紧耦合,从而增强了系统实现的灵活性,提高了业务流分类的精度,降低了骨干网业务流实时分类的实现代价。基于这种系统结构,本文给出了骨干网业务流实时分类前端系统的硬件实现方法,并详细讨论了基于FPGA（Field Programmable Gate Array:现场可编程门阵列）的SEFS算法的实现技术。本文所实现的骨干网业务流实时分类前端系统已经在国家急需的“一种新型互联网内容监管系统”中得到了应用。