目前Internet主干网络带宽呈指数性增长,网络带宽的急剧增长要求网络设备具有极高的包处理能力,同时网络协议的多样性和不断更新又要求网络设备具有极大的灵活性,网络设备对分组的深度处理能力将成为制约网络性能的主要瓶颈,即性能与速度之间存在着矛盾。基于GPP和ASIC的传统网络设备方案已经不能同时满足高性能和高可编程性两方面的要求,为此基于ASIP技术的网络处理器(NP)应运而生,并得到了迅速发展。以NP为核心的网络设备体系结构对2~7层的数据分组采用“存储-处理-转发”处理模式,从而可以实现更加复杂的网络处理功能。NP的出现改变了网络设备的体系结构,已成为研发新一代高性能网络设备的核心技术之一,NP是目前公认最有可能实现数据分组线速处理的器件和技术,因此研究基于NP的高性能网络设备核心技术对于加强我国信息基础设施建设具有十分重要的战略意义。NP并行线速处理的复杂应用程序关键性能影响因素可归结为并行处理模型与并行处理算法两方面,并行处理模型决定系统的稳定、高效、灵活、升级和扩展等性能,而并行处理算法则决定系统的分组处理速度,进而影响系统的准确性和有效性。本课题围绕NP并行处理模型与线速处理算法进行了系统而深入的研究,提出了高速网络环境下并行线速分组处理的有效模型与体系结构,给出了一系列高效的并行分组处理算法与实现方法,较好地解决了线速网络处理中性能与速度之间的矛盾。本研究工作取得了以下的主要创新性成果:(1)提出了一种基于NP的并行线速处理模型NPWM。NPWM由五个不同抽象级别的层次组成,从而将并行线速处理需要解决的若干核心问题及分组处理流程转化为基本独立的问题。NPWM覆盖了NP的各种软硬件资源及并行处理机制,考虑了并行线速处理相关的任务分配、资源调度和负载均衡等基础性问题,并为网络设备开发提供抽象的统一编程接口,可以满足网络设备在性能和灵活性两方面的要求,适合解决NP的各种网络应用问题,并能够达到并行线速处理要求。(2)给出基于NPWM模型并采用Intel IXP2850的网络安检机的总体系统设计,并给出本文的实验测试环境。NPWM模型与IXP2850的有机结合,NP多种并行机制的充分发挥,以及多个线速并行处理关键算法的实施,保证了网络安检机既具有强大的综合安全防御功能,又具有线速分组处理的高性能。实验数据说明网络安检机基本达到了线速分组处理的设计目标。(3)提出了网络处理短规则的概念,给出规则的描述和存储组织,并进一步给出规则集在NPWM模型上的并行匹配算法。规则集的并行处理设计了多种并行机制,规则集采用三维链表的树形逻辑组织,尽量减少了规则的时空冗余;快速匹配算法针对规则集的逻辑结构特点,尽量减少匹配的次数;存储优化算法分三种情况分别采用不同的优化策略;多核多线程优化采用基于表的间接哈希算法。实验结果说明这些并行方法和算法的采用,大大提高了分组并行处理能力,使得系统的分组吞吐率达到线速水平。(4)提出一种基于紧急度的轮循分组调度UWRR算法。UWRR算法的提出是在分析比较NP分组调度算法在时延性能、公平性、复杂性等三个方面性能指标的基础之上,并结合了NPWM模型的系统特性。UWRR算法在不过度提高复杂性的情况下,改善了传统算法的时延特性,引入动态改变队列循环调度次序的思想,来实现在变长分组环境下的公平性。实验结果表明与传统算法相比,UWRR算法对系统性能有明显提高,很好地解决了上述公平性问题,而且能实现更精细的队列间的服务速率分配。(5)提出一种并行自适应负载均衡HALB算法。NP负载均衡算法大致可分为哈希和非哈希两大类,其中哈希由于其高效和易于实现而被广泛采用。NP负载均衡要考虑解决分组乱序和流量分配两大问题,基于此给出相关概念和参数描述,并建立了NP负载均衡的数学模型。在此基础上提出HALB算法,算法根据转发平面负载状况动态调整映射权重,算法主要由哈希索引函数、负载分配映射函数和动态调整策略等三部分组成。根据实验结果表明,算法能够均衡地在PE间分配报文,而且基本保证了分组不乱序。因此,该算法能够提高NP并行处理能力,并减少分组乱序对NP性能的影响。