当前位置: 首页 » 论文导航 » 工业技术 » 正文
一种支持快速增量更新的掩码匹配算法
发布日期:2018-08-21  来源:微电子学与计算机   浏览次数:263
核心提示:摘要:软件定义网络(SoftwareDefinedNetworking,SDN)对网包分类提出了增量更新的需求。目前并没有掩码匹配算法满足快速增量更新,同时不牺牲分类性能。
 摘 要: 软件定义网络(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%以上的报文分类性能,同时保持快速的规则更新性能。
作者:曹作伟
 
 
 
评论详情
 
0条 [查看全部]  相关评论
 
 
 

免责声明:本平台并非任何杂志官网,仅限于整理学术信息以及期刊投稿渠道

 
 
展开