【作者】 董永吉；

【导师】 郭云飞；

【作者基本信息】 解放军信息工程大学 ， 军事信息学， 2013， 博士

【摘要】 随着互联网规模急剧增长和多样化应用需求的不断涌现，现有互联网架构在可扩展性、安全性、服务质量保证等方面的问题日益突出，国家973计划信息技术领域重大项目“可重构信息通信基础网络体系”面向未来网络架构，致力于构建一个功能可动态重构和扩展的基础物理网络，为不同业务提供满足其根本需求的、可定制的基础网络服务，使之与日益增长的应用需求和丰富的光传输资源相匹配。报文解析技术作为支撑IP转发、未来网络实验平台OpenFlow流转发、内容过滤等网络功能的基础核心技术，在可重构信息通信基础网络体系的研究和实验上具有多方面重要的研究意义。报文解析能力与资源占用息息相关，由于现在缺乏完善的理论基础和数学模型，报文解析技术在资源优化方面的研究目前尚处于起步阶段。本文以高速报文解析技术为研究对象，以高速流水线结构设计为研究内容，以提高报文解析处理的速率、降低存储资源开销，提供可配置的报文解析能力为目标，提出一个基于高速并行流水线可重构的高速报文解析框架，在此基础上针对IP转发、OpenFlow流转发、内容过滤等处理功能的不同层次协议解析需求，深入研究了三个不同层次的高速报文解析方法，主要研究内容如下：提出一种分层式的报文解析框架SwitchBricks，在框架基础上建立了高速报文解析模型（High-Speed Packet Parsing, HSPP），并提出模型存储资源优化的方向。首先，介绍了SwitchBricks控制与数据分离的结构：控制平面负责多种网络应用下解析能力的控制调度，数据平面完成特定网络环境下报文的高速解析，通过两个平面的协作满足高速报文多样化的解析需求；然后，基于M/D/1排队模型对SwitchBricks的处理性能和存储资源消耗进行推导分析，为后续研究和方案设计提供理论指导；最后，通过对存储资源占用的讨论，提出利用优化流水线存储资源占用原则指导报文解析相关算法的设计。提出了一种面向IP转发的高速报文解析方法（Parsing Pipeline Architecture forForwarding，PPAF），并基于PPAF方法提出一种优化并行流水线存储空间占用的节点映射算法。PPAF通过构建协议二叉trie树来支持报文协议解析的灵活度，利用并行多级流水查表提升报文协议解析处理速率，并以优化并行流水线存储资源占用原则为指导，提出了一种并行流水线节点映射算法（Node To Pipeline, NTP），可解决协议二叉trie树节点到并行流水线映射过程中存储资源不均衡的问题，进而减低存储资源开销。基于NetFPGA-10G的仿真实验表明，相对于现有的高速解析方法，该PPAF方法在处理速率和资源占用上取得较好均衡的同时，支持基于接口的独立解析能力。提出了一种OpenFlow流转发的可编程报文解析方法（Programmable Packet ParsingArchitecture, PPPA），利用该方法提出一种优化分段流水线存储空间占用的节点映射算法。PPPA通过构建协议解析多叉trie树，支持报文协议解析的可扩展，利用分段流水线匹配查找提升报文协议解析处理速率，并以优化分段流水线存储资源占用原则为指导，提出了一种分段流水线节点映射算法（Segmented Node Mapping Algorithm, SNMA），用以实现协议多叉trie树节点到分段流水线均衡存储映射，进而减少存储资源的消耗。基于NetFPGA-10G的仿真实验表明，与现有高速解析方法相比，该方法在能够提供基于接口的独立解析能力的同时，在解析带宽和资源占用上取得了较好的平衡。提出了一种面向内容过滤的协议解析方法(Bidirectional Packet Parsing for ContentFiltering, BiPPCF)，并基于该方法提出一种优化双向流水线存储空间占用的节点映射算法。BiPPCF采用内容提取trie树描述协议的耦合关系，提高了数据包解析的灵活性，利用双向流水线上匹配查找提升报文协议解析处理速率。为优化双向流水线存储资源，提出了一种双向流水线节点映射算法（BidirectionalNode MappingAlgorithmm, BiNMA）均衡各级流水线上的协议多叉trie树节点数目，优化存储空间的使用。数据分析和实验仿真显示，与现有高速解析方法相比，BiPPCF在处理速率、空间利用率等方面能取得较好的均衡。更多还原

【Abstract】 Along with the unceasing expansion of network scale and increase of diversified applicatio nrequirement, the existing network architecture has been confronted with the increasinglyoutstanding problem of scalability, security, quality of service guarantees. Based on aboverecognition, the major project of National973Plan in field of information technology,"FlexibleArchitecture of Reconfigurable Infrastructure"(FARI) dedicates to build a foundation physicalnetwork whose function is dynamically reconfigurable and extended, to supply basic networkservices which can be customized to satisfy different business, in order to match the growingapplication requirements to rich optical transmission resources. The packet parsing technology asa foundation core technology to support IP forwarding, the future experimental platformOpenFlow forwarding traffic, content filtering, etc., has important many-faceted significance intheory and practice for FARI. Because the capability of packet parsing and resource consumptionis closely related to, However, due to the lack of theoretical basis and mathematic model,researches on the packet parsing technology for resource optimization are still at an initial stage.This thesis concentrates on algorithm of packet parsing, and its aim is to improve theperformance and configurability of packet parsing, and reduce the cost of storage resources. Aframework is founded based on high-speed parallel pipelines, which can satisfy the packetparsing needs of IP forwarding, OpenFlow, and content filtering, etc. According to thisframework, three packet parsing methods for different layers were proposed after research on thetheories step by step, the main contents of this thesis presents are organized as following follows:A layered packet parsing framework named SwitchBricks is proposed, and a high-speedpacket parsing(HSPP) model based on SwitchBricks is set-up, and based on it the optimizationdirection of storage resources is deduced. Firstly, the SwitchBricks’s structure of the separationof control plane and data plane is introduced: control plane is responsible for the scheduling of avariety of network applications, and data plane implements the high-speed packet parsing in theparticular network environment. Two planes are worked together to meet a variety of high-speedpacket parsing requirements. Then, the analytical expressions of SwitchBricks’s performance andstorage resources consumption based on M/D/1queuing model is deduced, which could providetheoretical guidance for our further researches. Finally, the factor of storage resourcesconsumption is discussed, and the design of using pipeline storage resource consumptionminimization principle to guide packet parsing correlative algorithm is proposed.An IP forwarding-oriented high-speed packet parsing method named Parsing PipelineArchitecture for Forwarding (PPAF) is proposed, and a node mapping algorithm to optimize storage resource occupied by the parallel pipeline based on PPAF is provided. PPAF flexiblyanalyses packet protocol by constructing forwarding protocol-trie (FP-trie), improves theprocessing rate by employing parallel hardware pipeline look-up table, and takes parallelpipeline storage resources occupied minimization principle as guida nce. An algorithm formapping node to pipeline (NTP) is proposed to solve the unbalance problem of node mappingstorage resource and reduce the resource consumption. The simulation results through theNetFPGA-10G platform show that PPAF is superior to the extant high speed parsing method intwo ways: PPAF achieves ambidexterity in processing speed and resource consumption; and itcan provide independent interface-based flexible protocol parsing capabilities.An OpenFlow forwarding-oriented programmable packet parsing method namedprogrammable packet parsing architecture (PPPA) is proposed, and a node mapping algorithm tooptimize storage resource consumption by the segmented pipeline based on this method isprovided. The protocol parsing multibit-trie (PPM-trie) is used to express protocol parsing,making the parsing expression of the protocol scalable, and the high-speed look-up table of asegmented pipeline is used to achieve high-performance packet parsing on processing packet.And taking segmented pipeline storage resources occupied minimization principle as guidance, asegmented node mapping algorithm (SNMA) is proposed to establish the association betweenthe pipeline and multibit-trie to optimize the use of storage space on segmented pipeline stages,in order to reduce resource consumption. Finally, the feasibility of PPPA is verified onNetFPGA-10G platform, and the simulation results show that PPPA achieves the balancebetween the performance and resource consumption.A content filtering-oriented packet parsing method named bidirectional packet parsingfor content filtering (BiPPCF) is presented, and a node mapping algorithm to optimize storageresource consumption by the bidirectional pipeline based on the method is proposed. Firstly, thecontent extraction trie (CE-trie) is used to describe the coupling of the protocol relationship toimprove flexibility of the packet parsing; Secondly, hardware bi-directional parallel pipeline isused to enhance the processing rate of the packet parsing; Thirdly, in order to optimizebidirectional pipeline storage resources occupied, a bi-directional node mapping algorithm(BiNMA) is used to balance the number of nodes on all pipeline stages to optimize the storagespace. Analysis and simulation results show that compared with the existing high-speed packetparsing method, BiPPCF gets better balance between the performance and resourceconsumption.更多还原