面向网络处理器的资源调度研究

论文摘要

传统的网络设备大多采用基于GPP或ASIC的嵌入式处理器。随着网络流量的迅速增长和网络业务的日益多样,它们在性能或灵活性上已难以满足应用需要。在这种背景下,兼具高速处理能力和灵活编程能力的网络处理器（NP,Network Processor）为下一代通信产品的设计提供了一种灵活的解决方案。目前,网络应用系统的设计越来越多地采用高速、灵活的网络处理器。 网络处理器是典型的多RISC内核的并行实时处理结构,担负着数据包的处理和网络带宽管理等实时任务。在系统结构上,NP一般由一个通用处理器和多个并行或流水的数据包处理引擎（PE,Processing Engine）组成,每个处理引擎内部支持多个线程。如何在多个PE上进行有效的资源分配和调度以提高系统吞吐量、降低数据包时延和应用程序开发时间、保证系统服务质量（QoS,Qualityof Service）要求是当前网络处理器研究的一个热点问题。 论文以863计划（国家高科技技术研究发展计划）资助课题《面向网络处理器结构的新型操作系统核心技术》为基础,研究了网络处理器软件开发平台中有关资源调度的问题。主要涉及两个方面: 1.对于流水组织模式的网络处理器,其处理任务到各个PE的分配目前主要由手工完成,开发效率低且对开发人员素质要求较高,形成产品开发的瓶颈。为解决这一问题,本文首先提出一种任务到PE的自动分配方法。给定划分好的应用任务集和处理流水线级数,应用该方法可以迅速得到近似最优的分配方案。 2.网络服务形式的日益多样使得用户对于QoS的要求越来越高。网络设备的功能由传统的存储-转发模式到存储-处理-转发模式的转换,使得QoS的保证不再仅仅限于网络带宽的分配,还要求处理资源按照QoS的要求进行分配。因此,本文研究了链路调度和多PE调度问题,给出有效的调度策略,保证调度公平、时延等特性。 论文的硬件开发环境使用Intel IXP2400网络处理器开发平台,开发板是RADISYS公司开发的ENP-2611,它是一个完整的可设计开发的设备,具有非常灵活的可编程性。软件开发平台包括基于XScale的开发工具链（Linux GNU）和微代码开发工具（Intel为IXP2400提供的Developer W0rkbench）。

论文目录

• 摘要
• ABSTRACT
• 目录
• 前言
• 第一章 网络处理器研究与发展
• 1.1 网络处理器典型体系结构
• 1.1.1 Intel IXP2400体系结构
• 1.1.2 结构特征
• 1.1.3 IXP2400功能模块
• 1.2 IXP2400编程环境
• 1.3 网络处理器应用领域
• 1.4 网络处理器研究现状
• 1.4.1 体系结构研究
• 1.4.2 软件支撑技术研究
• 1.4.3 应用研究
• 1.5 网络处理器发展前景展望
• 第二章 网络处理器任务自动分配问题
• 2.1 研究背景
• 2.2 相关工作
• 2.3 任务分配问题数学描述
• 2.4 面向NP任务自动分配的遗传算法
• 2.4.1 单流分配矩阵的染色体编码
• 2.4.2 个体适应度计算
• 2.4.3 遗传操作
• 2.4.4 遗传迭代收敛判断
• 2.4.5 多个流的贪婪思想
• 2.5 应用示例
• 2.6 性能分析
• 2.7 算法在其他方面的应用
• 2.7.1 确定管道的数目
• 2.7.2 任务共享
• 2.7.3 任务划分
• 2.8 小结
• 第三章 网络处理器分组调度算法
• 3.1 分组调度概述
• 3.1.1 三种排队策略
• 3.1.2 调度性能指标
• 3.2 常用的分组调度算法
• 3.2.1 基于轮循的调度算法
• 3.2.2 基于GPS模型的PFQ调度算法
• 3.2.3 基于时延的调度算法
• 3.2.4 基于服务曲线的算法
• 3.3 基于SFQ+DWCS的分组调度算法：SFQ+
• 3.3.1 开始时间公平排队算法
• 3.3.2 动态窗函数调度算法
• 3.3.3 SFO+分组调度算法
• 3.3.4 SFQ+算法性能分析
• 3.4 SFQ+算法的NP实现
• 3.4.1 微引擎程序设计原则
• 3.4.2 算法实现机制
• 3.4.3 数据结构
• 3.5 仿真结果分析
• 3.6 分组调度算法小结
• 第四章 网络处理器多PE调度技术
• 4.1 问题背景及相关研究工作
• 4.2 算法描述
• 4.2.1 包处理时间预测模型
• 4.2.2 基于预测时间的多PE调度算法
• 4.2.3 算法的几点改进
• 4.3 性能评价
• 第五章 结束语
• 参考文献
• 附录
• 致谢