Research On Key Problems Of Parallel Wire-speed Processing In Network Processors

At present the bandwidth of Internet backbone network assumes exponential growth, the quick growth of network bandwidth requests network equipment have extremely high package handling ability, simultaneously the network protocol multiplicity and unceasing update request the network equipment to have an enormous flexibility. The deep package handling ability of the network equipment will be the main bottleneck to restrict network performance, namely the contradiction between speed and performance. The traditional network equipment project based on GPP and ASIC cannot simultaneously satisfy high performance and high programmable request, therefore the network processor (NP) based on ASIP appears and develops quickly. The network equipment architecture based on NP disposes 2-7 layers using"store-process-forward"packet handling mode, thus realizing a more complex network processing function. The NP technology has changed the network equipment architecture, and becomes a new core technology to research and develop a next generation of high performance network equipment, now NP is recognized as the most possibility to realize the wire-speed packet processing, hence studying the high performance network equipment core technology which is based on NP is of great strategic importance to our national information infrastructure.Key factors which may influence the performance of complicated application based on NP parallel wire-speed processing can come down to the parallel processing model and the parallel processing algorithms. The parallel processing model determines system's stability, effectiveness, flexibility, upgradeability, and expansibility. The parallel processing algorithms determine the package handling speed and in turn to affect the accuracy and validity. The thesis tries to start a systematic and in-depth research on the parallel processing model based NP and wire-speed processing algorithms and proposes the effective parallel wire-speed package processing model and architecture for high-speed network, gives out series parallel package processing algorithms, solved the contradiction between speed and performance in wire-speed network processing. The main contribution is as follows:(1) This dissertation proposed a parallel processing model NPWM based on NP, NPWM is composed by five different abstract layers, thus some core questions which needs to solve in parallel wire-speed processing and the package handling flow are translated into some basic independent questions. NPWM covered software resources, hardware resources and parallel processing mechanism of NP, considered some parallel wire-speed processing foundational questions about task assignment, resource scheduling, load balancing and so on, and provided abstract uniform programming interface for the network equipment development. NPWM can satisfy performance and flexibility requests of the network equipment, adapt to solve many kinds of network application problem based NP, and can satisfy parallel wire-speed processing requirements.(2) This dissertation proposed the overall system design of network security checking machine (NSCM) based on NPWM using Intel IXP2850, and experimental environment. NPWM and IXP2850 organically integrating, many kinds of parallel mechanism of NP full exerting, some wire-speed parallel processing key algorithm implementing, these methods guaranteed NSCM having strong integrative security defense function and wire-speed package handling high performance. The experimental data showed NSCM has basically achieved the design goal of wire-speed package handling.(3) This dissertation defined the concept of network processes the short rule, proposed rule description, rule memory organization, and parallel match algorithm of rule set in NPWM. The rule set parallel processing has designed many kinds of parallel mechanisms. The rule set uses the tree logic organization of three dimensional chain tables, reduces rule's space and time redundancy as far as possible. The fast match algorithm reduces the match numbers as far as possible in view of the rule set logical organization characteristic. The memory optimization algorithm is divided three kinds of situations to use the different optimized strategy separately. The multi-core multi-thread optimization uses indirect hash algorithm based on the table. The experimental data showed these parallel methods and algorithms improve the package parallel processing ability greatly, and cause the system package throughput rate to achieve wire-speed level.(4) This dissertation proposed a Round Robin package scheduling UWRR algorithm based on the urgency degree. UWRR is based on comparing with three aspect performance of delay performance, fairness and complexity in NP package scheduling algorithm, and combines NPWM system performance. UWRR does not increase complexity excessively, improves the delay performance of the traditional algorithm, introduces the thought of dynamic changing circle scheduling order, realizes the fairness under alterative length package environment. The experimental data indicated, comparing with the traditional algorithm, UWRR improves system performance clearly, solves the above fairness problem well, moreover realizes finer service speed assignment between queues.(5) This dissertation proposed a parallel auto-adapted load balancing HALB algorithm. The NP load balancing algorithm can be divided into two kinds of hash and non-hash, hash is applied widely because of its high efficiency and easy to realize. NP load balancing needs to consider two major problems of package disordering and stream assigning, hence defines the interrelated concepts and parameters, and establishes mathematical model of NP load balancing. HALB is proposed in this foundation, it can adjust mapping weight dynamically based on load state of forward plane, and it is mainly composed by the hash index function, the load assignment mapping function and the dynamic alignment strategy. The experimental data showed the algorithm can assign package between the PE evenly, and guarantee package keeping its order basically. Therefore, this algorithm can improve NP parallel processing ability, and reduce the performance influence of package disordering.