【作者】 左震；

【导师】 黄芝平；

【作者基本信息】 国防科学技术大学 ， 仪器科学与技术， 2012， 博士

【摘要】 随着网络通信技术的迅猛发展、网络应用的日益丰富，网络已经成为人类社会重要的基础设施，网络的性能及其运行稳定性成为了事关国家和社会发展的重要问题。作为认知网络的重要手段，网络测量技术是网络管理和网络行为研究的基础，也是进行网络优化、确保网络安全的重要前提。按照测量地域分类，网络测量包括局域网测量、接入网测量和光纤骨干网测量等方式。其中，光纤骨干网测量可以实现大范围、多用户的广域测量，是网络测量领域的研究热点。传统的网络测量研究主要集中在报文（数据包）层次，这导致后端管理系统需要处理和分析的信息量巨大，并且其测量相对平等地对待每个报文，不能获得报文间的内在联系及更高层次的信息，很难满足日益复杂的网络行为的观测及相关网络管理和优化的需求。为弥补报文层次网络测量的不足，基于流粒度的网络测量引起了国内外研究机构的广泛关注。如何利用有限的硬件计算、存储资源实现光纤骨干网的实时流测量，是一项极具挑战性和实用性的研究课题。为此，本文在总结和分析国内外已有研究工作的基础上，对光纤骨干网实时流测量中的IP包实时提取、IP包实时流匹配、流超时判定机制、大象流测量等关键技术进行了深入研究。论文的主要研究内容与创新点归纳如下：1．从最优化利用硬件资源的角度出发，对光纤骨干网IP包提取流程中的并行解扰算法进行了深入研究，提出了一种基于资源最优化的并行解扰算法ROPDA。相对于基于逻辑设计的并行解扰算法，ROPDA算法节省了系统的逻辑资源，降低了系统的复杂度，提高了系统的性能；相对于基于查找表结构的并行解扰算法，ROPDA算法可以运行在较少的片内存储资源的场合；此外，ROPDA算法的相关参数能够根据系统实际逻辑资源与片内存储资源的剩余情况进行灵活调整。依据光纤骨干网IP包实时提取的流程，设计并实现了光纤骨干网IP包实时提取平台。测试结果表明：该平台能够满足光纤骨干网IP包实时提取任务需求。2．为确保IP包流匹配的实时性，匹配算法的时间复杂度必须为O（1）。针对TCAM（Ternary Content Addressable Memory）器件虽然可以实现时间复杂度为O（1）的匹配查询，但其能容纳的匹配条目无法满足光纤骨干网百万数量级并发流的问题，设计了一种基于两层异或Hash和TCAM的IP包实时流匹配算法RFMA-HT。利用异或Hash算法对IP包五元组进行转换以降低对存储空间的需求，同时通过开辟三级存储空间解决了匹配冲突问题。从时间复杂度、空间复杂度以及处理速度与实现三个方面分析了RFMA-HT算法的可行性，并利用实际的光纤骨干网数据对RFMA-HT算法进行了验证。测试结果表明：RFMA-HT算法具有较低的运算复杂度和冲突率，能够满足光纤骨干网IP包实时流匹配的需求。3．针对光纤骨干网中存在的单包流占据系统大量资源的现象，研究了光纤骨干网单包流的特性，提出了一种基于单包流优化的流超时判定算法SFOTS。SFOTS算法利用单包流的特性及早发现单包流并通过设置较小的超时值将其尽早从测量系统中剔除，以提高系统资源利用性能。论文对SFOTS算法相关参数的选择进行了详细的理论分析，并利用实际的光纤骨干网数据对SFOTS算法的性能进行了评估。测试结果表明：SFOTS算法在保证判定准确性的同时对系统存储资源要求较低，特别是在网络攻击或蠕虫爆发等异常情况发生时，SFOTS算法具有更佳的性能优势，确保了测量系统的可靠运行。4．针对现有大象流测量算法存在的判断机制单一、测量粒度偏大、测量结果不稳定等缺点，提出了一种基于三级LRU和状态保持的大象流测量算法3LRU+Hold。3LRU+Hold算法以测量时间片为周期，在每个测量时间片内根据流所包含的IP包个数对流进行分类，将长流、中流、短流分开处理，对准大象流进行保护；在每个测量时间片结束时，对准大象流及大象流的相关状态信息进行保持、更新。论文对3LRU+Hold算法相关参数的选择以及算法的可行性进行了详细的理论分析，并利用实际的光纤骨干网数据和Opnet网络仿真软件，从算法的准确性和测量结果的稳定性两个方面将3LRU+Hold算法与其它算法进行了实验对比。测试结果表明：3LRU+Hold算法对大象流的测量准确性优于LRU算法，且与Sample and Hold、Multistage Filters和LRU等算法相比，3LRU+Hold算法增强了大象流测量结果的稳定性。综上所述，针对光纤骨干网实时流测量中的若干关键问题，本文的研究工作提出了有效的解决方案，为下一步构建光纤骨干网实时流测量系统、推进网络综合管理和网络行为分析等应用提供了基本的理论和技术支持。更多还原

【Abstract】 With the rapid development of network communication technologies and theexplosive increase of network applications, the network has become an importantinfrastructure which deeply affects human society. The performance of the network andits running stability become the key issues related to the development of our society. Asan important means to understand the network, network measurement technology is theresearch foundation for network management, network behavior analysis and thepremise condition for optimizing the network, ensuring network security. According tomeasuring zone, network measurement can be classified as measurement on local areanetwork, measurement on access network and measurement on optical fiber backbonenetwork. Among them, measurement on optical fiber backbone network is a popularresearch topic because it can realize large-scale and multi-user’s overall measurement.The traditional studies of network measurement technology usually concentrate onthe packet-level measurement which makes the management system difficult to processand analyze the huge information. Since it treats the received packets equally, thepacket-level measurement can’t get the internal relations among the packets andhigher-level characteristics of the packets, which are necessary for network behaviorobservation, network management and optimization. To overcome the shortages of thetraditional packet-level network measurement, the flow-level network measurement hasbeen widely concerned by the researchers all over the world. How to realize real-timeflow measurement on optical fiber backbone network by using limited hardwarecomputation and storage resources becomes a challenging and practical research topic.Based on the summary and analysis of the existing research achievements, thisdissertation conducts an in-depth study of the key technologies of real-time flowmeasurement on optical fiber backbone network, including real-time IP packetextraction algorithm, real-time IP packet flow match algorithm, flow timeout strategyand elephant flow measurement algorithm.The main contents and contributions of thisdissertation are as follows:1. Aiming at making the most effective use of the hardware resources, the paralleldescrambling algorithm in IP packet extraction process is studied. A novel resource-optimized parallel descrambling algorithm (ROPDA) is proposed. Compared with theparallel descrambling algorithm based on logic design, ROPDA saves the logicresources, reduces system complexity and improves system performance. Comparedwith the parallel descrambling algorithm based on memory structure, ROPDA can runin the situation of less on-chip memory. What is more, the parameters in ROPDA can beadjusted according to the residual logic and on-chip memory resources in the system. According to the real-time IP packet extraction process, a real-time IP packet extractionhardware platform for optical fiber backbone network is designed. The test results showthat this hardware platform can accomplish the real-time IP packet extraction task onoptical fiber backbone network.2. To ensure the real-time property of flow match for IP packets, the timecomplexity of flow match algorithm should be O(1). For this purpose, theTCAM(Ternary Content Addressable Memory) chip can be used because it can realizeflow match with the time complexity of O(1). However, the memory resource of theTCAM chip can’t contain millions of flows existing on optical fiber backbone network.To solve this bottleneck problem, a real-time IP packet flow match algorithm based ontwo-layer XOR Hash and TCAM (RFMA-HT) is proposed. By using XOR Hashalgorithm, the104bits(96bits) of IP packet head are transferred to reduce the requiredmemory, and a three-layer memory space is designed to avoid conflict in matching. Thetime complexity, memory complexity, processing speed and the feasibility of RFMA-HT are theoretically analyzed. Some practical optical fiber backbone network data areused to evaluate the performance of RFMA-HT. The test results demonstrate thatRFMA-HT is of low computational complexity and conflict rate which can satisfy theneed of real-time IP packet flow matching on optical fiber backbone network.3. There is a great abundance of single-packet flows existing on optical fiberbackbone network which consume lots of system resources. Based on analyzing thecharacteristics of the single-packet flows on optical fiber backbone network, asingle-packet flow optimized timeout strategy (SFOTS) is presented. In this strategy,the single-packet flows can be found and deleted from the memory quickly by setting alow timeout threshold. Therefore, SFOTS improves the memory utilization efficiency ofthe system greatly. The preferences of SFOTS are theoretically analyzed. Somepractical optical fiber backbone network data are used to evaluate the performance ofSFOTS. The test results demonstrate that SFOTS can ensure measurement accuracywhile consuming less memory resources. Especially in the situation of network attack orworm eruption, SFOTS can perform better which can ensure the stability of the system.4. Since the existing elephant flow measurement algorithms have some shortages,such as single definition of elephant flow, high granularity and low stability, a novelelephant flow measurement algorithm based on three-layer LRU and state-hold(3LRU+Hold) is proposed. In each periodic time slice, the flows are classified as longflow, middle flow and short flow according to the number of packets involved in theflow and processed respectively. Thus, the possible elephant flows can be protected. Atthe end of each time slice, the information of the possible elephant flows and elephantflows are retained and updated. The preferences and the feasibility of3LRU+Hold aretheoretically analyzed. Performance of3LRU+Hold is investigated with respect to accuracy and stability by using practical optical fiber backbone network data and Opnetnetwork simulation software. The test results demonstrate that compared with LRU,3LRU+Hold has better accuracy. Also,3LRU+Hold has higher stability, compared withSample and Hold, Multistage Filters and LRU.In summary, several efficient algorithms are developed in this dissertation to tacklethe key problems in real-time flow measurement on optical fiber backbone network.This provides fundamental theory and technique support for the establishment ofreal-time flow measurement system on optical fiber backbone network, networkmanagement and network behavior analysis.更多还原