网包分类

课题介绍：

在网络过滤和监控中，多域网包分类是高层路由、安全网关等多项应用中的核心技术，其本质是在数学上尚无最优解的多维空间中一点在多体间定位问题。由于网络应用中分类规则有序和重叠等特性，多域网包分类始终是困扰高速网络设备的瓶颈。目前千兆级以上的高端路由器设备均采用专用芯片解决方案，从而成为降低成本和提高性能的障碍。因此，结合当前最新的软硬件平台进展，研究和开发新型高性能网包分类算法，成为推广高性能分类设备的必由之路。

研究方法和研究目标：
1) 算法分析:

• 算法理论复杂度分析: 各种网包分类算法在时域和空域的tradeoff分析
• 网包分类规则集合分析: 分类规则特征提取, 及其内在本质复杂度的分析

2) 算法设计:

• 层次化空间映射: 利用多级空间映射表进行层次化空间映射. 代表算法: HSM
• 高性能数据结构: 利用bit-string压缩决策树指针数组, 分层压缩空间映射结构. 代表算法: ExCuts
• 网络流量信息: 利用网包五元组统计信息动态更新决策树结构, 提高平均分类性能. 代表算法:DCuts

3) 算法实现:

• Linux平台下网包分类模块: 将HSM算法和决策树算法引入netfilter内核模块, 解决linux系统下网包分类模块的瓶颈
• 网络处理器平台下的网包分类模块实现: 在Intel IXP2xxx系列网络处理器上实现了10Gbps的网包分类处理building block

项目合作：

• 2007.6~2009.12 863（目标导向类）计划资助
• 2007.01 - 2007.12 清华大学信息科学技术学院基础研究基金资助
• 2006.10 - 2008.09 清华大学信息技术研究院种子基金资助
• 2004.11 - 2006.09 Intel公司IXA University Program资助 http://www.ixaedu.com/home
• 2004.12 - 2005.12 Juniper公司资助 http://www.juniper.net