一种支持快速增量更新的掩码匹配算法

曹作伟; 陈晓; 倪宏

Chinese

您当前的位置：

首页 >

文章列表页 >

一种支持快速增量更新的掩码匹配算法

更新时间：2026-09-04

- 一种支持快速增量更新的掩码匹配算法
- A Mask Matching Algorithm with Fast Incremental Update Support
- 微电子学与计算机 2019年36卷第4期页码：84-88
- 作者机构：
  
  1. 中国科学院机构声学研究所国家网络新媒体工程技术研究中心,北京,100190
  2. 中国科学院大学机构电子电气与通信工程学院,北京,101400
- 作者简介：
- 基金信息：
  
  国家科技重大专项项目 2017ZX03001019
- DOI：
  中图分类号：
- 纸质出版：2019
- 稿件说明：
移动端阅览
曹作伟, 陈晓, 倪宏. 一种支持快速增量更新的掩码匹配算法[J]. 微电子学与计算机, 2019, 36(4): 84-88, 92.

CAO Zuo-wei, CHEN Xiao, NI Hong. A Mask Matching Algorithm with Fast Incremental Update Support[J]. 2019, 36(4): 84-88.
曹作伟, 陈晓, 倪宏. 一种支持快速增量更新的掩码匹配算法[J]. 微电子学与计算机, 2019, 36(4): 84-88, 92. DOI：

CAO Zuo-wei, CHEN Xiao, NI Hong. A Mask Matching Algorithm with Fast Incremental Update Support[J]. 2019, 36(4): 84-88. DOI：

摘要

文章提出一种支持快速增量更新的掩码匹配算法TernarySort.该算法使用决策树将掩码匹配规则划分为多个分区

不同叶节点的规则互不重叠

以保障规则更新性能.同时通过选取有效比特位

减小决策树深度

并允许叶节点中规则重叠

减少分区数量

以提高分类性能.实验结果表明

与现有的算法相比

TernarySort可提升80%以上的分类性能

同时保持快速的更新性能.TernarySort能够满足SDN对掩码匹配算法的要求.

Abstract

This paper proposes a mask match algorithm

TernarySort

supporting fast incremental update. The algorithm uses decision trees to partition mask matching rules. To guarantee the update performance

it restricts that rules residing in different leaf nodes do not overlap with each other. At the same time

TernarySort selects effective bits to reduce the depth of decision trees. And it allows rules to overlap in one leaf node

to decrease the number of partitions and improve the classification performance. The experimental results show that

compared to currently used algorithms

TernarySort can improve packet classification performance by more than 80% while maintaining fast rule updating performance. TernarySort meets the requirements of SDN for mask matching algorithms.

关键词

Keywords

references

MCKEOWN N, AANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74. DOI: 69

SRINIVASAN V, SURI S, VARGHESE G. Packet Classification Using Tuple Space Search[A]. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication[C]. New York, NY, USA: ACM, 1999: 135-146.

BOSSHART P, DALY D, GIBB G, et al. P4: Programming Protocol-independent Packet Processors[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87-95. DOI: 87

DALY J, TORNG E. TupleMerge: Building Online Packet Classifiers by Omitting Bits[A]. 2017 26th International Conference on Computer Communication and Networks (ICCCN)[C]. 2017: 1-10.

TAYLOR D E, TURNER J S. Classbench: A packet classification benchmark[J]. IEEE/ACM Transactions on Networking (TON), 2007, 15(3): 499-511. DOI: 499

PFAFF B, PETTIT J, KOPPNEN T, et al. The Design and Implementation of Open vSwitch[A]. 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)[C]. Oakland, CA: USENIX Association, 2015: 117-130.

HE P, XIE G, SALAMATION K, et al. Meta-algorithms for Software-Based Packet Classification[A]. 2014 IEEE 22nd International Conference on Network Protocols[C]. 2014: 308-319.

GUPTA P, MCKEOWN N. Packet classification using hierarchical intelligent cuttings[A]. Hot Interconnects VII[C]. 1999: 34-41.

YINGCHAREONTHAWORNCHAI S, DALY J, LIU A X, et al. A Sorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification[J]. IEEE/ACM Transactions on Networking, 2018: 1-14. DOI: 1

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

工业无线传感网混合关键性业务带宽分配算法

大模型发展综述：从BERT到Deepseek的技术演进

基于区块链的AI生成内容溯源框架设计研究

基于反向体偏置的高增益稳定性高温运放设计

一种基于特征上下文理解与切片分析的肺结核检测算法