近日，深圳研究生院信息工程学院李挥教授课题组在计算机网络方向顶级期刊IEEE Journal on Selected Areas in Communications（JSAC）“网络虚拟化关键技术”系列专刊第五期上发表了题为“Tuple Space Assisted Packet Classification with High Performance on Both Search and Update”的学术论文。

网络包分类技术在软件定义网络（SDN）中扮演着极其重要的角色，是构建OpenFlow流表查找及协议无关转发平面的核心技术之一。当前网络包分类技术无法兼顾流表的高速查找和更新。

针对这一问题，该论文提出了一种融合决策树技术与元组技术的异构网络流分类算法CutTSS，在确保高性能规则更新能力的同时极大提升了流表的查找性能。CutTSS算法构建了快速查找的决策树主框架，通过对流表进行基于小域的子集划分及切割，不仅有助于构建深度较浅的决策树数据结构，而且可以有效避免传统决策树技术所存在的规则复制问题；通过对非叶子节点使用元组技术进行决策树的辅助构建，使整体算法可以在不同空间尺度上自适应地利用规则子集特征进行流表的快速查找和更新。

CutTSS算法框架图

IP链规则集中的大规则比例

CutTSS算法的规则更新性能与Open vSwitch中所采用的PSTSS元组算法相当，但在流表查找性能上却比PSTSS算法提升了接近一个数量级。

分类性能测评

更新性能测评

JSAC是中科院JCR期刊分区一区期刊，2019年的影响因子为9.302，也是CCF计算机网络领域三个A类期刊之首。该论文是北京大学深圳研究生院历史上第一篇在JSAC上所发表的论文。

论文的前期工作“CutSplit：A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification”，于2018年发表于CCF计算机网络领域A类会议IEEE International Conference on Computer Communications（INFOCOM），并获得路由与交换会场最佳演讲论文奖。

2018年INFOCOM会议路由与交换会场最佳演讲论文奖

课题组内李文军博士生为该论文的第一作者，李挥为通讯作者。该研究得到了国家重点研发计划、国家自然科学基金、华为“未来网络IDC全域流量测量”前沿课题等项目的支持。