基于多核网络处理器的数据包分类算法研究

论文摘要

随着Internet规模的日益扩大,各种网络业务不断涌现,网络应用的数据流迅猛增长,网络设备原本单一的“尽力”服务方式已不能满足要求。这一切对各种网络设备提出了新的要求,需要如资源预留服务、QoS（Quality of Service）服务、虚拟专用网、基于策略的路由等新的“差别”服务机制。数据包分类技术作为提供“差别”服务的基础技术,是网络研究的一个热点,很多经典的数据包分类算法被相继提出。早期的经典算法都是基于那个时代主流的网络设备,也有一些是基于特定的硬件。随着多核网络处理器逐渐成为主流网络设备所采用的架构,基于多核网络处理器的数据包分类算法研究成为具有重要实现意义和理论研究价值的课题。本文首先概述了基于多核网络处理器的应用研究,以及多核并行策略所引入的问题。然后概述了数据包分类,介绍了常用数据包分类算法,并给出对这些算法的总结。在此基础上,提出了基于多核网络处理器的数据包分类研究的问题,以及针对这些问题相应的解决方案和改进方法,包括在多核网络处理器数据包分类性能评价标准中引入了基于多队列系统的Power公式,提出了基于元组空间并行策略和基于跳转位划分并行策略,以及基于规则集统计特征提出了对HyperSplit算法的改进HS-e。实验结果表明,这些解决方案和改进方法能够在一定条件下提高数据包分类的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.2 国内外研究近况
• 1.3 本文的工作
• 第二章 多核网络处理器
• 2.1 多核网络处理器OCTOEN
• 2.1.1 MIPS架构
• 2.1.2 硬件组成
• 2.1.3 数据包流程
• 2.1.4 多核程序运行环境
• 2.2 多核网络处理器应用研究
• 2.2.1 多核网络处理器应用研究
• 2.2.2 多核网络处理器并行策略相关问题
• 2.3 本章小结
• 第三章 数据包分类
• 3.1 数据包分类概述
• 3.1.1 数据包分类
• 3.1.2 规则集统计特征
• 3.1.3 数据包分类理论极限
• 3.1.4 数据包分类性能评价
• 3.2 常用数据包分类算法
• 3.2.1 穷尽查找
• 3.2.2 判定树
• 3.2.3 分解法
• 3.2.4 元组空间
• 3.3 数据包分类算法总结
• 3.4 本章小结
• 第四章 基于多核网络处理器的数据包分类研究
• 4.1 问题描述
• 4.2 多核网络处理器数据包分类性能评价
• 4.3 数据包分类多核并行策略
• 4.3.1 简单并行策略
• 4.3.2 基于元组空间并行策略
• 4.3.3 基于跳转位划分并行策略
• 4.4 HS-e
• 4.4.1 HyperSplit
• 4.4.2 基于规则集统计特征的改进
• 4.5 性能测试
• 4.6 本章小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文