摘 要: 软件定义网络(Software Defined Networking, SDN)对网包分类提出了增量更新的需求。目前并没有掩码匹配算法满足快速增量更新，同时不牺牲分类性能。针对这个问题，该文提出一种支持快速增量更新的掩码匹配算法TernarySort。该算法使用决策树将掩码匹配规则划分为多个分区，不同叶节点的规则互不重叠，以保障规则更新性能。同时通过选取有效比特位，减小决策树深度，并允许叶节点中规则重叠，减少分区数量，以提高分类性能。实验结果表明，与现有的算法相比，TernarySort可提升80%以上的分类性能，同时保持快速的更新性能。TernarySort能够满足SDN对掩码匹配算法的要求。

0 引言
软件定义网络(Software Defined Networking, SDN)将控制功能与转发功能分离，通过集中式的控制器以标准化接口对各种网络设备进行管理和配置。OpenFlow[1]由斯坦福大学提出，已成为SDN中控制器与网络设备通信的事实标准。然而OpenFlow面临协议扩展问题，难以满足更多的网络协议、带状态的数据转发等复杂需求。新的数据平面编程语言，如P4[2]，提出了对任意协议字段的支持。借助数据平面可编程技术，交换机无需理解特定的报文协议，新的网络应用的开发不再需要修改交换机代码，新技术、新业务的迭代速度将得到极大的提升。
类似于OpenFlow， P4采用了匹配动作表(Match Action Table, MAT)作为数据平面的转发模型。在MAT模型中，报文处理包括字段解析、流表匹配与动作执行等步骤。流表匹配包括最长前缀匹配、范围匹配和掩码匹配等类型，是影响数据平面转发性能的关键环节之一。流表匹配问题实质上是网包分类问题。在SDN环境下，网包分类算法除支持报文的快速分类，还需要支持规则的快速更新，以满足控制器动态修改交换机转发规则的需求。
传统的网包分类算法大多只关注报文分类速度，难以满足快速更新的需求。基于决策树的算法如HiCuts[3]、SmartSplit[4]等，按空间将规则划分为单个决策树，分类性能高，然而由于规则重叠，同一条规则会重复出现于叶子节点，更新一条规则需要同时处理多个节点，影响更新性能。开源OpenFlow交换机Open vSwitch[5]采用改进的TSS (Tuple Space Search)[6]算法，按照字段掩码长度对规则进行划分，分区内使用哈希搜索，同一分区内规则互不重叠，TSS算法可支持快速更新，然而TSS算法的分区数量过多，影响了报文的分类性能。在TSS算法基础上，TupleMerge[7]算法根据协议字段，去除不重要的比特（比如IP地址的末尾比特），以降低分区数量，提高分类速度，然而该算法要求交换机具备协议字段的先验知识，不能直接应用于可编程数据平面。PartitionSort[8]算法采用最大独立集的方式对规则进行划分，要求同一分区内的规则满足可排序、不重叠，对于最长前缀匹配和范围匹配规则，该算法在更新速度与查找速度上取得了良好的平衡。然而，由于掩码匹配规则无法排序，不能直接应用PartitionSort算法。
针对上述问题，本文提出一种支持快速增量更新的掩码匹配算法TernarySort，选取有效比特将规则划分为决策树，在避免分区内生成重复规则的同时，减少分区数量，实现高速的分类性能与快速的更新性能。本文的主要贡献如下：
1.提出适用于掩码匹配的决策树结构，选取比特划分规则。单个决策树可实现的报文分类与规则更新性能，以及的空间性能，其中为规则数量。
2.提出高效的掩码匹配规则分区方案，通过选取有效比特划分规则，可有效减少分区数量，提高分类性能。
3.提出高效的在线分区算法，通过设置重叠规则的准入条件，在支持规则快速更新的同时，实现高速的报文分类性能。
4.实现TernarySort算法，并进行仿真测试。与TSS算法相比，TernarySort算法可提升70%以上的报文分类性能，同时保持快速的规则更新性能。
作者：曹作伟