A Mask Matching Algorithm with Fast Incremental Update Support

CAO Zuo-wei; CHEN Xiao; NI Hong

Chinese

您当前的位置：

首页 >

文章列表页 >

A Mask Matching Algorithm with Fast Incremental Update Support

更新时间：2026-09-04

- A Mask Matching Algorithm with Fast Incremental Update Support
- Vol. 36, Issue 4, Pages: 84-88(2019)
- 作者机构：
  
  1. 中国科学院机构声学研究所国家网络新媒体工程技术研究中心,北京,100190
  2. 中国科学院大学机构电子电气与通信工程学院,北京,101400
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：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

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

The Bandwidth Allocation Algorithm for Mixed-criticality Traffic in Industrial Wireless Sensor Networks

Research on assembly action recognition based on MSS-YOLO-MPHands fusion architecture

Lightweight countermeasures against Spectre attacks on the branch prediction unit

Steganography model guided by attention mechanism and improved dense convolution

Aerial vehicle detection algorithm based on multi-scale fusion and small-object enhancement

Related Author

WANG Jun

WANG Qiu-shi

WANG Jin-tao

Related Institution

China Petroleum and Chemical Corporation, Tianjin Branch

Industrial Control Networks and Systems Department, Shenyang Institute of Automation, Chinese Academy of Sciences

University of Chinese Academy of Sciences

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰