Skip to main content

网包分类

(Packet Classification)#

课题介绍#

在网络转发和监控中，多域网包分类是高层路由、安全网关等多项应用中的核心技术。网包分类的本质是计算几何中的多维空间点定位问题。由于其规则的多维度(multi-dimension)、优先级(priority)和交叠性(overlapping)等特点，网包分类算法复杂低效，始终是困扰高速网络设备的瓶颈。随着软件定义网络(SDN, Software Defined Networking)和边缘计算等的兴起，多域网包分类在可编程网络平台上面临着更高维度和更快更新速率等新的问题。因此，结合当前最新的软硬件平台进展，研究和开发新型高性能网包分类算法，成为推广高性能网络监控设备和可编程网络平台的必由之路。

研究方法与研究目标#

1) 算法分析#

  • 算法理论分析: 研究网包分类算法在时域和空域的理论复杂度；通过引入平滑分析(smoothed analysis)研究算法的真实性能。
  • 网包分类规则分析: 研究真实网包分类规则的各类统计特征，设计优化算法提高网包分类性能。
  • 网包分类流量分析: 研究真实网包分类流量的各类统计特征，设计优化算法提高网包分类性能。

2) 算法设计#

  • 启发式二分查找: 利用启发式的k-d树结构实现高效的二分查找。代表算法: HyperSplit。
  • 高性能空间映射: 利用多级空间映射表进行层次化空间映射。代表算法: HSM。
  • 决策树结构优化: 综合bitmap算法和搜索空间相似性压缩决策树节点存储。代表算法: AggreCuts。
  • 比特层优化设计: 利用混合数据结构和智能分割策略实现时空性能优化。代表算法: DBS，D2BS。
  • 规则集分组优化: 结合规则集交叠分析与智能优化算法优化时空性能。代表算法：RFG, ParaSplit, LiveCuts。
  • 规则集缓存替换: 利用规则集的层级化结构特性优化缓存性能。代表算法：HBD。

3) 算法实现#

  • Linux平台：Linux平台：将HSM和HyperSplit算法引入netfilter内核模块, 解决Linux系统下网包分类模块的瓶颈。在DPDK环境下，实现HyperSplit与TSS算法的测评。
  • NP平台：在Intel IXP2850 网络处理器上实现了AggreCuts算法，在Cavium OCTEON5860 网络处理器上实现了HyperSplit和DBS算法，均达到10 Gbps的64字节小包分类速率。
  • 众核平台：在Tilera TILEPRO64众核处理器上实现并改进了AggreCuts算法，达到了10 Gbps的64字节小包分类速率。
  • FPGA平台：在Xilinx Virtex-5 FPGA平台上实现了HyperSplit和D2BS算法，达到了100 Gbps或以上的64字节小包分类速率。借助高性能HBM，在Xilinx Alevo U50平台上实现了1M规则集的100Gbps分类速率。

项目合作#

  • 2020.10 - 2021.06 腾讯公司委托开发合作
  • 2019.01 - 2022.12 国家自然科学基金面上项目资助
  • 2018.06 - 2019.09 华为公司委托开发合作
  • 2017.06 - 2018.06 华为公司委托开发合作
  • 2015.09 - 2016.09 华为公司委托开发合作
  • 2012.01 - 2013.01 绿盟公司技术转让合作
  • 2011.07 - 2012.06 清华信息科学与技术国家实验室（筹）学科交叉基金（合作者USC Prof. Viktor Prasanna）
  • 2011.01 - 2011.12 北京市支持中央在京高校共建项目资助
  • 2010.07 - 2011.06 清华信息科学与技术国家实验室（筹）学科交叉基金 （合作者USC Prof. Shanghua Teng）
  • 2007.06 - 2009.12 国家高新技术研究发展计划（863计划）信息技术领域重点项目资助
  • 2007.01 - 2007.12 清华大学信息科学技术学院基础研究基金资助
  • 2006.10 - 2008.09 清华大学信息技术研究院种子基金资助
  • 2004.11 - 2006.09 Intel公司IXA University Program资助
  • 2004.12 - 2005.12 Juniper公司资助