Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Line speed flexible multi-tuple message classifying method

A packet classification and tuple technology, applied in electrical components, advanced technologies, digital transmission systems, etc., can solve the problems of high memory overhead, slow rule update speed, etc., and achieve low cost, fast rule update speed, and fast search speed. Effect

Active Publication Date: 2015-03-25
NAT UNIV OF DEFENSE TECH
View PDF1 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

The method based on cross product (such as RFC) has extremely high memory overhead, the method based on group space (Tuple Space Search) is only suitable for rule sets with small mask types, and the method based on decision tree (such as EGT-PC) is Has a very slow rule update rate

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Line speed flexible multi-tuple message classifying method
  • Line speed flexible multi-tuple message classifying method
  • Line speed flexible multi-tuple message classifying method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0039] The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments. In order to clearly describe the method of the present invention, the following assumes that the regular IP and port fields are all 4 bits wide, the protocol number field is 2 bits wide, and the discontinuous mask prefix is ​​4 bits wide.

[0040] The wire-speed soft-tuple message classification method of the present invention is as follows: convert each rule in the rule set into a corresponding multi-dimensional prefix, and use the public mask of these prefixes to convert the traditional prefix matching problem into a multi-level exact matching problem; The multilevel exact matching problem uses a hash table to achieve a lookup rate close to O(1). Furthermore, on the basis of the above method, a set of fast rule update method in a multi-core environment can be realized by using the atomic operation provided by the CPU.

[0041] like ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a line speed flexible multi-tuple message classifying method. The method includes the steps of firstly, converting a port field in a rule into a corresponding prefix closure to obtain a discontinuous mask prefix set, wherein the port field is converted into the corresponding prefix closure, that is, the shortest section used for covering the section of the port field and capable of being represented in the form of prefix is formed, and all dimensions of a five-dimension prefix set are connected together to obtain the discontinuous mask prefix set; secondly, establishing a CMT data structure through the discontinuous mask prefix set; thirdly, conducting high-speed message classification through a CMT structure search algorithm. The line speed flexible multi-tuple message classifying method has the advantages of being high in search speed, small in hardware expense, low in energy consumption and the like.

Description

technical field [0001] The invention mainly relates to the field of message forwarding in network technology, in particular to a line-speed soft multi-group message classification method. Background technique [0002] Packet classification (Packet Classification) is a key step in realizing message forwarding, and is also a key technology for completing message forwarding. Data packet classification can be described as: aiming at the five-tuple information (source-destination IP, source-destination port, protocol number) in the IP data packet header, find the best rule to match the data packet header. Among them, each rule consists of five ranges (source-destination IP, source-destination port, protocol number). The source-destination IP is expressed in the form of a prefix, the source-destination port is expressed in the form of a range, and the protocol number is generally an exact value. The "best rule" here refers to the rule with the most accurate mask and the shortest ...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): H04L12/70
CPCY02D30/50
Inventor 黄腾陈曙晖赵国鸿王宝生
Owner NAT UNIV OF DEFENSE TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com