【作者】 时向泉；

【导师】 苏金树；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2007， 博士

【摘要】 新型的网络应用和协议以及高速发展的链路带宽在可扩展性和高性能报文转发方面对路由器提出了更高的要求。传统路由器却不能完全满足上述要求,基于网络处理器的高性能路由器由于同时具有高性能、高灵活性和高可扩展性而受到关注,成为研究的热点。基于网络处理器的高性能路由器的性能主要取决于如下三个方面:1)选用的网络处理器的性能;2)路由器转发系统的网络处理器组织和使用方式;3)所采用的相关服务质量控制算法。对上述三个方面展开研究,对于提高基于网络处理器的高性能路由器的综合性能具有重要意义。本文对上述三个方面进行了研究,主要内容包括:与网络处理器本身性能密切相关的多线程并行性能研究、并行网络处理器组成的高速转发子系统之间的负载均衡算法的研究以及适用于网络处理器的拥塞控制机制的研究。研究内容对于指导基于网络处理器的高性能路由器的设计发挥了重要作用。网络处理器的性能对路由器性能具有重要影响,而网络处理器性能主要取决于其采用的并行机制。本文提出了网络处理器并行性能模型NP~3M和多线程并行处理的时间模型;对NP~3M模型中的多线程停顿特性和切换开销因素进行了研究,并通过实验对模型及相关结论进行了验证,研究分析结论直接用于指导“863计划”重点课题的网络处理器微码设计和提高微码软件的处理效率。网络处理器间的并行数据处理是提高路由器性能的有效途径之一。本文针对多网络处理器并行处理产生的负载均衡、报文保序等问题开展研究,提出并设计了面向报文流量特征的多网络处理器动态负载均衡算法D-IHDA,在该算法中引入了极大流的动态判定机制和针对不同流量特征的报文定义了映射表项更新概率算法。提出了适用于汇聚网络处理器模型的流控算法思想,引入了二次分发机制以提高系统的性能,进一步降低报文丢弃率。实验表明,与相关算法相比,D-IHDA算法具有更好的扩展性,更低的报文丢失率和更好负载均衡度。服务质量控制算法对路由器的性能具有重要作用。本文通过对网络处理器处理数据报文的流程分析,归纳提出了多阶段拥塞控制模型,为解决每个阶段的拥塞控制机制之间互相孤立的问题,提出了一个多阶段资源感应拥塞控制机制CC-AMR,该机制可以综合利用多个资源信息来进行网络处理器的缓冲管理和拥塞避免,并直接应用于“863计划”重点课题,提高了路由器的性能。针对缩短队列平均长度和减少抖动问题,本文综合研究了流输入速率和缓冲占有率的关系,提出了一个基于输入速率和缓冲占用率的缓冲管理算法A-SARED。与RED和SARED相比,A-SARED具有较小平均队列长度和更平缓队列抖动特性的同时,具有更高的吞吐率。针对传统机制对区分服务支持的不足,设计了面向区分服务的缓冲管理与报文调度机制CCAAQM及其具体实现算法。模拟实验证明,CCAAQM机制能够在网络节点为需要可靠保证的流应用提供区分服务。更多还原

【Abstract】 In recent years, new network applications and protocols as well as the link bandwidth requirements grow rapidly, higher performance and scalability are required for next generation high performance routers. However, the traditional routers cannot meet the requirements mentioned above. Therefore network processors-based high performance routers have attracted much attention because of their higher performance, flexibility and scalability.The performance of a network processors-based high performance router mainly depends on three factors: 1) .the inherent performance of network processors used in the router; 2). the organization and employment of network processors in router systems; 3). the related control algorithms of QoS. Carrying on research work around the three factors mentioned above is very important to improve the performance of network processors-based high performance routers.This dissertation focuses on the three factors related to the performance of network processors-based routers. It includes: 1).the performance of parallel multithreads; 2).the dynamic load balance algorithm for high speed packet forwarding system composed of the parallel network processors; 3).the congestion control mechanisms fit for parallel network processors. It is important for designing network processors-based high performance routers.The performance of network processors has a significant impact on the performance of routers, while the performance of network processors mainly depends on the parallel processing mechanisms. Network processors parallel performance model (NP~3M) and network processors Multithread Parallel Processing Time Model are constructed in the dissertation, and these models are verified by experiments. Furthermore, the characteristics of multithread halting and the cost of multithread switching are studied, and the results are verified by experiments. The results of the research have been used to guide the design of network processors picocode of the important "863" project and to improve the processing efficiency of picocode software.Parallel data processing between network processors is an efficient way to improve the performance of routers. In this paper, we conduct research on load balance and packets order preserving problems which are induced from parallel processing of network processors, propose and design D-IHDA, a dynamic load balance algorithm orienting packet traffic characteristics, D-IHDA introduces a dynamic judging mechanism for maximum traffic and defines the probabilistic algorithm for updating mapped entries according to different traffic characteristics. We propose the idea for traffic control algorithm which can be used in aggregate network processor models, and introduce the twice-distributing mechanism to improve the system performance and further reduce the packet loss rate. The simulation results show that this algorithm with the well-chosen design parameters has better overall performance on its expansibility, load balancing and packet ordering compared with other algorithms.QoS controls algorithms are very important to the performance of routers. Through analysis of the data packet processing flow of network processors, we induce the multistage congestion control mechanism. Furthermore, to solve the problem of isolation between the congestion control mechanisms in different congestion control stage, we propose CC-AMR, a congestion control mechanism with awareness of multistage resources, which can synthetically utilize some resource congestion information to manage the buffer of network processors and aviod congestion. We improved the performance of routers by applying this mechanism in the important project of National High-Tech Research (863) Program.In order to reduce average queue length and alleviate wobble problem, a buffer management algorithm called A-SARED based on the relationship of packet flow input rate and buffer occupancy percentage is proposed. Compared with RED and SARED, it has shorter average queue length as well as improved throughput. Contraposed to traditional mechanism poorly supporting QoS, we design a DiffServ-oriented buffer management and packet schedule mechanism called CCAAQM and the corresponding implementation algorithms. The simulation results demonstrate that CCAAQM mechanism can provide differentiated service for flows that need assurable service within network node.The work of the dissertation is supported by the important project of National Science Foundation of China (NSFC) and the important project of National High-Tech Research (863) Program. The major results are successfully applied in developing the "New Generation Internet High Performance Router". This project gained the Second prize of National Scientific and Technological Progress Award in 2006.更多还原