【作者】 黄昆；

【导师】 张大方；

【作者基本信息】 湖南大学 ， 计算机应用技术， 2009， 博士

【摘要】 随着网络带宽和业务流量的迅猛增长,数据包内容过滤技术面临高性能挑战,即如何满足深度数据包检测(Deep Packet Inspection, DPI)的线速处理和低存储空间需求。随着网络规模不断扩大、节点呈现出动态性和异构性,P2P内容分发技术面临高性能挑战,即如何在大规模网络中实现高效、健壮和可伸缩的内容分发。本文研究高性能数据包内容过滤技术,探讨如何折衷考虑DPI的时间和空间需求;研究高性能P2P内容分发技术,探讨如何折衷考虑内容分发的效率、公平性和负载均衡等。(1)高性能数据包内容过滤技术包括基于硬件的数据包预处理方法和特征匹配算法:快速哈希表存在更新开销高和片外存储空间需求大等问题。本文提出了一种基于双计数布鲁姆过滤器的哈希表(Double-counter Bloom filtered Hash Table,DBHT)。双计数布鲁姆过滤器采用插入和删除计数器,分别记录每个存储桶中插入和删除的元素个数。实验结果表明,DBHT是一种时空高效的哈希表,即显著减少更新操作的片外存储器访问次数和片外元素个数,仅需要增加少量片上存储空间大小。特里位图内容分析器存在更新开销高和假阳性访问次数多等问题,而共享节点快速哈希表存在更新开销高和存储空间需求大等问题。本文提出了一种索引拆分布鲁姆过滤器(Index-Split Bloom Filter, ISBF)。在ISBF中,元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行计数布鲁姆过滤器表示元素集。为了降低ISBF的更新开销,本文又提出了懒惰删除算法和空缺插入算法。实验结果表明,ISBF支持快速和存储高效的查找,即显著减少片外存储器访问次数、处理时间以及片上和片外存储空间需求。比特拆分字符串匹配算法存在不必要的状态迁移问题。本文提出了一种字节过滤字符串匹配算法(Byte-Filtered String Matching Algorithm),即在比特拆分字符串匹配之前,采用布鲁姆过滤器预处理数据包内容的每个读入字符。实验结果表明,与比特拆分算法相比,字节过滤算法减少了字符串匹配时间和状态迁移次数,从而提高了DPI的吞吐量。扩展有限自动机是在状态上增加辅助变量及操作指令,从状态方面减少正则表达式匹配的存储空间需求。本文提出了一种基于紧凑型有限自动机(CompactFinite Automaton, CFA)的正则表达式匹配算法,从迁移边方面进一步减少存储空间需求。CFA采用基于优先级的迁移边压缩方法,压缩相同目的状态最多的迁移边;采用基于位图的迁移边查找方法,并行查找不同优先级的迁移边子集。实验结果表明,CFA显著减少迁移边条数和存储空间大小,且在匹配时间上与扩展有限自动机基本相同。(2)高性能P2P内容分发技术包括BitTorrent性能优化方法和基于DHT的负载均衡广播算法:BitTorrent的上传节点和请求节点之间存在“供需悖论”问题。本文提出了一种基于动态配额(Dynamic Quota)的节点选择策略,即按照投资收益原则,上传节点动态地分配TFT算法和OU算法的上传配额。实验结果表明,基于动态配额的节点选择策略是一种效率和公平折衷的方法,即以多上传部分文件块为代价来提高BitTorrent的下载效率。分析自私节点的搭便车(Free Riding)对BitTorrent性能、公平性和健壮性的影响。本文提出了一种基于活跃度(Activeness)的种子节点阻塞算法,即定义请求节点的可用下载带宽和可用上传带宽的比值为活跃度,种子节点优先选择活跃度高的请求节点来上传文件块。实验结果表明,基于活跃度的种子节点阻塞算法不仅抑制自私节点的搭便车,而且提高良性节点的性能,从而增强了BitTorrent健壮性。已有的基于DHT的广播算法是利用贪婪的指针路由算法来构建分布式广播树,存在可伸缩性差和负载不均衡等问题。本文提出了两种基于DHT的轻量级广播算法。当节点标识符空间是均匀分布时,提出了基于令牌(Token)的广播算法,即每个节点根据令牌值从指针节点中选择其孩子节点;当节点标识符空间是任意分布时,提出了基于分割(Partition)的广播算法,即每个节点将整个节点标识符空间分层分割为两个子空间,并选择子空间的代理节点为其孩子节点。实验结果表明,基于令牌和基于分割的广播算法可构建一颗可伸缩和负载均衡的分布式广播树,而不需要额外的状态存储和链路维护等开销。更多还原

【Abstract】 As link rates and traffic volumes are constantly growing, the packet contentfiltering technology faces high performance challenges. This means that Deep PacketInspection (DPI) is required to satisfy both line-speed packet processing and smallmemory requirements. As network size continues to grow with increasing dynamicand heterogeneous nodes, it is very challenging for the P2P content distributiontechnology to achieve efficient, robust, and scalable content dissemination acrosslarge-scale networks. In this dissertation, we focus on high performance packetcontent filtering and P2P content distribution technologies. The former involvestradeoffs between time and space complexities of DPI, while the latter involvestradeoffs among efficiency, fairness, and load balance of content distribution. Themajor contributions of this work are as follows.(1)Our packet content filtering technology includes hardware-based packetpreprocessing techniques and signature matching algorithms:The Fast Hash Table suffers from both high update overhead and large off-chipmemory requirements. We propose a Double-counter Bloom filtered Hash Table(DBHT). The Double-Counter Bloom Filter uses insertion and deletion counters perbucket for recording the number of inserted and deleted items. Experimental resultsdemonstrate that the DBHT is a time/space-efficient hash table, which significantlyreduces the off-chip memory accesses as well as the off-chip memory requirements, atthe cost of additional acceptable on-chip memory space.The Trie Bitmap Content Analyzer suffers from high update overhead and manyfalse positive memory accesses, while the Shared-node Fast Hash Table suffers fromboth high update overhead and large off-chip memory requirements. We propose anIndex-Split Bloom Filter (ISBF). The core idea of ISBF is that an index of off-chipitem is split apart into a group of bits, and each group uses several parallel CountingBloom Filters in on-chip memory to represent a set of items. Moreover, both lazedeletion algorithm and vacant insertion algorithm are proposed to reduce the updateoverhead of ISBF. Experimental results demonstrate that the ISBF achieves fast andmemory-efficient lookups, which significantly reduces the off-chip memory accessesand processing times as well as the on-chip and off-chip memory requirements.The bit-split string matching algorithm suffers from the unnecessary state transitions problem. We propose a byte-filtered string matching algorithm, whereBloom filters are used to preprocess every incoming character before performingbit-split string matching. Experimental results show that the byte-filtered algorithmenormously reduces the string matching times as well as the number of statetransitions.The Extended Finite Automaton (XFA) augments DFA with auxiliary statevariables and simple instructions for manipulating them, achieving significantmemory reduction in the aspect of states. We propose a Compact Finite Automaton(CFA) based regular expression matching algorithm, in order to further reducememory requirements in the aspect of transitions. The CFA exploits a priority-basedtransition compression scheme to compress multiple transitions with the same mostdestination state on an input label, and a bitmap-based transition lookup scheme tosearch transition subsets with differenet priority in parallel. Experimental resultsshow that the CFA significantly reduces both the number of transitions and thememory requirements, while almost keeping the same matching times with the XFA.(2)Our P2P content distribution technology includes BitTorrent performanceoptimization techniques and DHT-based balanced broadcast algorithms:BitTorrent suffers from a paradox of supply and demand between upload peersand request peers. We propose a dynamic quota-based peer selection strategy, wheredue to the principle of investment return, each upload peer adaptively allocates uploadquotas for the TFT and OU algorithms. Experimental results show that the dynamicquota scheme is efficiency and fairness tradeoffs, which sacrifices a part of uploadfairness to improve download efficiency of BitTorrent.We analyze the impact of selfish peer’s free riding on the performance,fairness,and robustness of BitTorrent. We propose an activeness-based seed choking algorithm,where the activeness refers to the ratio of available download bandwidth to availableupload bandwidth of request peers, and a seed preferentially uploads request peerswith the highest activeness values. Experimental results show that the activenessalgorithm not only restrains the free riding of selfish peers, but also improves theperformance of benign peers, thus enhancing BitTorrent’s robustness.Exiting DHT-based broadcast algorithms exploit a greedy finger routingalgorithm of DHT to construct a Distributed Broadcast Tree (DBT), leading to thelimitations of scalability and load balancing. We propose two DHT-based lightweightbroadcast algorithms. When nodes are uniformly distributed in the identifier space, atoken-based broadcast algorithm is proposed, where each node selects the finger nodes as its children by a token value. When nodes are arbitrarily distributed in theidentifier space, a partition-based broadcast algorithm is proposed, where each nodehierarchically partitions its identifier space into two subspaces and selects the agentnodes in the subspaces as its children. Experimental results demonstrate that both thetoken-based and partition-based algorithms can construct and maintain a scalable andload-balanced DBT, where the branching factor are at most two, and the tree heightis O (log n )in a Chord ofnnodes, without extra state space and explicit maintenanceoverhead.更多还原