CN101039253A - Method for realizing prefix extension of range matching of ternary content addressable memory - Google Patents
Method for realizing prefix extension of range matching of ternary content addressable memory Download PDFInfo
- Publication number
- CN101039253A CN101039253A CNA2006100115176A CN200610011517A CN101039253A CN 101039253 A CN101039253 A CN 101039253A CN A2006100115176 A CNA2006100115176 A CN A2006100115176A CN 200610011517 A CN200610011517 A CN 200610011517A CN 101039253 A CN101039253 A CN 101039253A
- Authority
- CN
- China
- Prior art keywords
- node
- prefix
- ancestor
- child
- ancestor node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention provides a prefix expansion method for range matching of triple content addressable memory, achieving port range matching or IP address range matching in the matching of packet classification rules. The method sets the starting value in the field which needs range matching of the rules as a starting node of completely binary tree, finding out all expanded prefixes by iteration. The specific steps of finding out all expanded prefixes include: Step 1, judging the current node is a left child node or a right child node; Step 2, if the current node is a right child node, the current node occupies a separate prefix, the next node of the current node is set to be a new current node, and return to step 1; Step 3, if the current node is a left child node, then the largest right ancestral node of the current node occupies a prefix, the next node of the most right leaf node of the largest right ancestral node of the current node is set to be a current node, and return to step 1.
Description
Technical field
The present invention relates to technical field of the computer network, relate in particular to and use TCAM (Ternary ContentAddressable Memory, Ternary Content Addressable Memory) realizes ACL/QoS (Access ControlList/Quality of Service, Access Control List (ACL)/service quality) technology of aspect, be mainly used in router, switch, fire compartment wall, the network equipments such as intruding detection system.
Background technology
In the network equipment now, all need to realize ACL/QoS mostly, most critical partly is exactly a rule match in these technology, but because the field in the rule is a lot, matching way is also different, so when rule was a lot, matching speed had just become performance bottleneck.Now give an example with ACL, traditional ACL is made of five-tuple: source IP address, purpose IP address, source port number, destination slogan, agreement.In the general realization, prefix matching is used in the IP address, and agreement is used accurately coupling, and port is scope of application coupling then.Realize that at present ACL mainly contains two kinds of approach, a kind of software that is to use realizes that most typical is exactly RFC (RecursiveFlow Classification, recursive-flow category) algorithm; Another kind just is to use hardware to realize that most typical is exactly TCAM.Certainly the hardware realization is fast more a lot of than software certainly, especially in some express networks, generally all uses hardware to quicken.
TCAM is a kind of special-purpose Ternary Content Addressable Memory, can carry out fast a large amount of parallel searches.In the time of search, clauses and subclauses all in the memory compare with search key simultaneously, and Search Results is exactly the physical address of occurrence.When carrying out entries match, each position of clauses and subclauses can be 0,1, three kinds of states of x, if x, this position does not participate in comparison so, and acquiescence is success, otherwise the corresponding positions of keyword and clauses and subclauses compares, if identical then successfully otherwise fail.In comparison procedure, if certain position does not match, this entries match failure so; If all mate all positions, this entries match success so.
The inherent characteristic of TCAM hardware makes that TCAM is fit to accurately mate and prefix matching very much, at this moment can use these fields of TCAM direct representation.Such as MAC (Media Access Control, medium access control) address table, MPLS (Multi-protocol Label Switching, multiprotocol label switching) transmitting is exactly accurately to mate, and IPv4/v6 (Internet Protocol version 4/6, Internet protocol the four/six edition) routing table then is a prefix matching.But when TCAM is used for commensurate in scope, such as TCP/UDP (Transfer Control Protocol/User Datagram Protocol, transmission control protocol/User Datagram Protoco (UDP)) port range, so at this moment simple these fields of direct representation just.
The commensurate in scope problem of TCAM is to use the difficult point of TCAM always, solves this problem and go back the good method of neither one at present.Chinese patent: based on the parallel I P bag grader and the method for the solution commensurate in scope of TCAM, application number 200510011511, publication number 1674557 used a kind of regional code method to solve the commensurate in scope problem, but this method has following shortcoming: need handle search key, search efficiency is low, rely on rule base, need to use a lot of extension bits, support that the scope number is limited, update efficiency is low, needs the outer TCAM space of occupying volume etc.The present invention has realized a kind of simple Prefix Expansion method, can effectively solve TCAM commensurate in scope problem.
Summary of the invention
Technical problem to be solved by this invention provides a kind of Prefix Expansion method of simple realization TCAM commensurate in scope, to solve the commensurate in scope problem that TCAM is applied to the ACL/QoS aspect.
For achieving the above object, the present invention proposes a kind of Prefix Expansion method that realizes the three-folded content addressable memory range coupling, realize port range coupling or IP address range coupling in the message classification rule match, wherein, the initial value that needs the commensurate in scope field in the rule is made as the start node of complete binary tree, iteration is found out whole expansion prefixes, and this step of finding out the expansion prefix specifically comprises:
Step 2, if present node is right child, then described present node takies a prefix separately, the next node of described present node is made as new present node, and returns described step 1;
Step 3, if present node is left child, then the maximum right ancestor node of described present node takies a prefix, and the next node of the lobus dexter child node of the right ancestor node of described maximum of described present node is made as new present node, and returns described step 1.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling wherein, when having start node in the node, also comprises before the described step 1:
With the step of start node as initial present node.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, when having terminal node in the node, described step 1 is further comprising the steps of:
Step 31, judge described present node whether more than or equal to or less than described terminal node;
Step 32 is if described present node is greater than described terminal node, then finishing iteration;
Step 33, if described present node equals described terminal node, finishing iteration and described present node added in the expansion prefix then;
Step 34 is if described present node less than described terminal node, then carries out iteration.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, described step 3 is further comprising the steps of:
Step 41 is made as current ancestor node with the last layer ancestor node of described present node;
Step 42 judges that described current ancestor node is left child or right child;
Step 43, if described current ancestor node is right child, then described current ancestor node is the maximum right ancestor node of described present node;
Step 44, if described current ancestor node is left child, then the last layer ancestor node with described current ancestor node is made as new current ancestor node, and returns step 42.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, when having terminal node in the node, described step 43 is further comprising the steps of:
Step 51, whether the lobus dexter child node of judging described current ancestor node is greater than described terminal node;
Step 52 is if then be made as following one deck left side child of described current ancestor node the rightest ancestor node of described present node;
Step 53, if not, then described current ancestor node is the rightest ancestor node of described present node.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, when having terminal node in the node, described step 44 is further comprising the steps of:
Step 61, whether the lobus dexter child node of judging described current ancestor node is greater than described terminal node;
Step 62 is if then be made as following one deck left side child of described current ancestor node the rightest ancestor node of described present node;
Step 63, if not, then the last layer ancestor node with described current ancestor node is made as new current ancestor node, and returns described step 42.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, whether the coverage of judging described current ancestor node is greater than described terminal node, and judgment formula is as follows:
L-1+POW2(level)≤N
The initial leaf node that the described current ancestor node of " L " expression covers, " POW2 (level)=2
Level" the leaf node number that covers of the described current ancestor node of expression, the lobus dexter child node that " L-1+POW2 (level) " just represents that described current ancestor node covers, " N " represents described terminal node.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, when the Wbit field was expanded, the Wbit field was in scope [1,2
W-2] the prefix number of being expanded mostly is 2 (W-1) most, and the height of described complete binary tree is W+1, and W represents field bit figure place.
The Prefix Expansion method of above-mentioned realization three-folded content addressable memory range coupling, wherein, when commensurate in scope is carried out in the IP address, the high-order prefix designates of using, low level uses described Prefix Expansion method to expand.
Adopt the method for the invention can realize the commensurate in scope of TCAM simply and effectively.The present invention not only can support the commensurate in scope of port, can also support the commensurate in scope of IP address simultaneously, realizes that for using TCAM ACL/QoS provides an extraordinary solution.Its advantage is as follows: do not change search key, the search efficiency height does not rely on rule base, does not use extension bits, supports any range, update efficiency height, the not outer TCAM space of occupying volume etc.
Description of drawings
Fig. 1 is the conceptual description schematic diagram of Prefix Expansion method of the present invention;
Fig. 2 is the proof schematic diagram of Prefix Expansion method of the present invention;
Fig. 3 is the flow chart of Prefix Expansion method of the present invention;
Fig. 4 is the flow chart that the present invention searches maximum right ancestor node;
Fig. 5 is the schematic diagram of the specific embodiment of the invention.
Embodiment
Be described in further detail below in conjunction with the enforcement of accompanying drawing technical scheme:
The technical program has been used the notion in a lot of complete binary trees, and Fig. 1 is the conceptual description schematic diagram of Prefix Expansion method of the present invention.As shown in Figure 1, comprise following notion:
A. child/father node: if certain node in binary tree has next node layer, this node just is called the father node of its next node layer so; Next node layer is exactly the child nodes of this node, and the child nodes on a left side/the right is a left side/right child.Notice that child/father node is a level relative concept.
B. brother/same node layer: identical two nodes of father node are the brotgher of node; Other node with layer is called same node layer.The brotgher of node also is same node layer.
C. a left side/right ancestor node: make progress along its left side/right side all nodes of process of node are referred to as a left side/right ancestor node of this node.
D. leaf/limb node: the basecoat node is called leaf node; Other node is called the limb node.Leaf node is the 0th layer, and the limb node is since the 1st layer.
E. node coverage: all nodes that node comprises along the left and right sides are referred to as the coverage of this node.
F. a maximum left side/right ancestor node: a node M has an a maximum left side/right ancestor node with respect to a node N with layer left/right, this ancestor node in the range of nodes of this layer covering, the node on the most left/the right 〉=/≤node N.
G. the most left/the lobus dexter child node: the node on the most left/the right is called the most left/lobus dexter child node in all leaf nodes of a limb node covering.
Design philosophy of the present invention is by using one group of prefix to represent a scope.For example: 4bit represents that [3,12] will be extended to: 0011 (3), and 01xx (4-7), 10xx (8-11) and 1100 (12).The W-bit field is extended to the individual prefix of 2 (W-1) at most.
Fig. 2 is the proof schematic diagram of Prefix Expansion method of the present invention.As shown in the figure, prove that this method must will set forth the proposition of following establishment, those self proof procedures of assigning a topic are not here to have illustrated.Comprise with the proposition of setting up:
A. under same case, span is far away more, and needed prefix number is many more.Same case is meant that two start nodes and two terminal nodes of two scopes all are a left side/right children.
B. for two brotghers of node, the node on the left side is left child, is stopping under the borderline phase situation together prefix number 〉=left node that the node on the right needs.
C. for two brotghers of node, the node on the right is right child, under initial borderline phase situation together, and prefix number 〉=right node that the node on the left side needs.
Under the prerequisite of above-mentioned 3 propositions, can release following conclusion:
When start node be the right child of first node of ground floor limb node, when terminal node was the left child of last node of ground floor limb node, needed prefix number was maximum.
2. can cover top said zone with recurrence method proof time underlay nodes envelope, institute's number of underlay nodes in proper order promptly is the maximum-prefix number of needs.
3. can get according to the complete binary tree characteristic: the Wbit field is in scope [1,2
W-2] the prefix number of being expanded mostly is 2 (W-1) most.
Fig. 3 is the flow chart of Prefix Expansion method of the present invention.As shown in the figure, for given range [M, N], this method adopts a progressively process of iteration, and each iterative process is found out a prefix, and up to finding out all prefixes, concrete steps are described below:
Step S301 composes start node M to a variables L, and this variable is used for iteration.
Step S302 is if L＞N then iteration finish to jump to step S307.
Step S303 if L=N then iteration finish, adds the L node in the expansion prefix, jumps to S307 then.
Step S304 if L is left child, jumps to S306, judges whether it is that left child only need be with LMOD2, if be 0 then be left child, otherwise is right child.
Step S305, L are right children, because L is right child, so can not use its ancestor node that it is covered, so L must account for a prefix separately, the L node is added in the expansion prefix, simultaneously L is pointed to its next node, jump to step S302 then and begin the next round iteration.
Step S306, L are left children, so can use its ancestor node that it is covered.Find the maximum right ancestor node of L, the right ancestor node of this maximum is certain to be existed because N＞L, simultaneously should maximum right ancestor node satisfy following conditions: the lobus dexter child node≤N of this node, so just can use this ancestor node to cover a sheet of node, the right ancestor node of this maximum is added in the expansion prefix, simultaneously L is pointed to the next node of the lobus dexter child node of the right ancestor node of this maximum, this just in time is the leaf node zone that this ancestor node covers, and jumps to S302 then and begins the next round iteration.
Step S307, iteration finishes.
Fig. 4 is the flow chart that the present invention searches maximum right ancestor node.As shown in the figure, specifically comprise the steps:
Step S401 is provided with variable level=1, and ancestor=L ÷ 2, level represent current node level, and bottom one deck is 0, and ancestor represents the node ID of ancestor node place layer.Because ancestor node necessarily exists, so earlier these two variablees are arranged to the ground floor ancestors, i.e. its father node.This father node is at ground floor, and the node ID of its place layer is leaf node sequence number L ÷ 2, and this is to be determined by the characteristic of complete binary tree.
Step S402 is if ancestor MOD2=0 then jump to S404 judges promptly whether the ancestor node is the left child of its father node.Because need look for maximum right ancestor node now, so this process also is the process of an iteration, each node layer of process all must be the left child of its father node, so just can guarantee be by to the upper right side to the path travel through.
Step S403, ancestor are right children, and at this moment iteration finishes, and judge then whether the coverage of current ancestor node surpasses N, and judgment formula is as follows:
L-1+POW2(level)≤N
L is the initial leaf node that this ancestor node covers, POW2 (level)=2
LevelRepresent the leaf node number that this ancestor node covers, so L-1+POW2 (level) the lobus dexter child node of just representing that this ancestor node covers.If lobus dexter child node＞N, the zone of explanation covering has surpassed N so, so level is subtracted 1, is about to ancestor node to the decline one-level, so just can guarantee lobus dexter child node≤N, because present ancestor node has satisfied this condition in the previous round iterative process.Jump to S405 after executing operation.
Step S404, ancestor are left children, and first condition has satisfied, and judge then whether the lobus dexter child node of this ancestor node surpasses N, and determination methods is referring to S403.If surpass then iteration finishes, level is subtracted 1, jump to S405; Otherwise the right ancestor node that this layer is described is legal, continues the right ancestor node of iteration last layer then: level is added 1, and ancestor begins the next round iteration divided by jumping to S402 after 2.
Step S405, iteration finishes.
After iteration was finished, the L node was current maximum right ancestor node in the ancestor node of level layer.The method for expressing of this ancestor node is as follows: suppose to use W bits to represent that L can be expressed as b so
W-1B
1b
0, the maximum right ancestor node method for expressing of its level layer is the low level position one-tenth x with L, other invariant position, and the result is as follows:
b
w-1…b
level+1b
levelx
level-1…x
1x
0
Illustrate: b is expressed as 0/1, and x represents arbitrarily.
Prefix matching is generally only supported in present IP address, though also can support commensurate in scope, but be limited in scope, and restriction is too dead, if support commensurate in scope flexibly, so how realize? if directly use the Prefix Expansion method, method will become complicated so, Kuo Zhan clauses and subclauses also can be too many in addition, when especially expanding the IPv6 address, so this method is unworkable.According to the characteristics of IP address, even the support scope mainly also is the restriction to some host addresses, such as 10.1.1.2～10.1.1.100.According to practical situations, host address generally all is to use low level to represent, a high position then is the network address, at this moment can represent in the following way the IP address:
The network address (high position): prefix matching, adopt the prefix direct representation
Host address (low level): commensurate in scope, adopt the Prefix Expansion method to expand
Such as carrying out Prefix Expansion to the least-significant byte of IPv4 address, high 24 are used prefix designates, so just can realize the commensurate in scope of IP address flexibly.
Fig. 5 is the schematic diagram of the specific embodiment of the invention.As shown in Figure 5, the situation during W=4bit can get 2 * (4-1)=6 prefixes of maximum needs according to formula, and scope is [1,14], below method above just using find out all prefixes:
Step S501, starting point 1 is a right child, because 1MOD2=1, so add in the expansion prefix present starting point=1+1=2 with 0001.
Step S502, starting point 2 is left children, because 2MOD2=0, the maximum right ancestor node that finds it is 001x, lobus dexter child node=3≤14 of this ancestor node add 001x in the expansion prefix, now starting point=3+1=4.
Step S503, starting point 4 is left children, because 4MOD2=0, the maximum right ancestor node that finds it is 01xx, lobus dexter child node=7≤14 of this ancestor node add 01xx in the expansion prefix, now starting point=7+1=8.
Step S504, starting point 8 is left children, because 8MOD2=0, the maximum right ancestor node that finds it is 10xx, lobus dexter child node=11≤14 of this ancestor node add 10xx in the expansion prefix, now starting point=11+1=12.
Step S505, starting point 12 is left children, because 12MOD2=0, the maximum right ancestor node that finds it is 110x, lobus dexter child node=13≤14 of this ancestor node add 110x in the expansion prefix, now starting point=13+1=14.
Step S506, because starting point 14=terminal point 14, so add in the expansion prefix iteration end at this moment with 1110.
Be example with step S503 more below, illustrate how to look for maximum right ancestor node:
Step 01, level=1, ancestor=4 ÷ 2=2.
Step 02, because 2MOD2=0 (left child), 4-1+POW2 (1)=5≤14, level=1+1=2, ancestor=2 ÷ 2=1.
Step 03 because 1MOD2=1 (right child) ≠ 0 so iteration finishes, judges 4-1+POW2 (2)=7≤14 then, illustrates that current the 2nd layer ancestor node is legal maximum right ancestor node.Because 4 are expressed as 0100, so this ancestor node is expressed as: 01xx.
Need 6 prefixes as follows respectively altogether through obtaining expression scope [1,14] after top these iterative process:
Expansion prefix coverage node number
0001 1～1 1
001x 2～3 2
01xx 4～7 4
10xx 8～11 4
110x 12～13 2
1110 14～14 1
Now the field value in the hypothesis search key is 6, so 0110 and 0001,001x, 01xx, 10xx, 110x, 1110 carry out the TCAM coupling, can have only 01xx to mate, and the scope that 01xx represents is [4-7], so the result is entirely true.
Certainly; the present invention also can have other various embodiments; under the situation that does not deviate from spirit of the present invention and essence thereof; being familiar with those of ordinary skill in the art ought can make various corresponding changes and distortion according to the present invention, but these corresponding changes and distortion all should belong to the protection range of the appended claim of the present invention.
Claims (9)
1. Prefix Expansion method that realizes three-folded content addressable memory range coupling, realize port range coupling or IP address range coupling in the message classification rule match, it is characterized in that, the initial value that needs the commensurate in scope field in the rule is made as the start node of complete binary tree, iteration is found out whole expansion prefixes, and this step of finding out the expansion prefix specifically comprises:
Step 1 judges that present node is left child, still right child;
Step 2, if present node is right child, then described present node takies a prefix separately, the next node of described present node is made as new present node, and returns described step 1;
Step 3, if present node is left child, then the maximum right ancestor node of described present node takies a prefix, and the next node of the lobus dexter child node of the right ancestor node of described maximum of described present node is made as new present node, and returns described step 1.
2. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 1 is characterized in that, when having start node in the node, also comprises before the described step 1:
With the step of start node as initial present node.
3. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 1 is characterized in that when having terminal node in the node, described step 1 is further comprising the steps of:
Step 31, judge described present node whether more than or equal to or less than described terminal node;
Step 32 is if described present node is greater than described terminal node, then finishing iteration;
Step 33, if described present node equals described terminal node, finishing iteration and described present node added in the expansion prefix then;
Step 34 is if described present node less than described terminal node, then carries out iteration.
4. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 1 is characterized in that described step 3 is further comprising the steps of:
Step 41 is made as current ancestor node with the last layer ancestor node of described present node;
Step 42 judges that described current ancestor node is left child or right child;
Step 43, if described current ancestor node is right child, then described current ancestor node is the maximum right ancestor node of described present node;
Step 44, if described current ancestor node is left child, then the last layer ancestor node with described current ancestor node is made as new current ancestor node, and returns step 42.
5. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 4 is characterized in that when having terminal node in the node, described step 43 is further comprising the steps of:
Step 51, whether the lobus dexter child node of judging described current ancestor node is greater than described terminal node;
Step 52 is if then be made as following one deck left side child of described current ancestor node the rightest ancestor node of described present node;
Step 53, if not, then described current ancestor node is the rightest ancestor node of described present node.
6. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 4 is characterized in that when having terminal node in the node, described step 44 is further comprising the steps of:
Step 61, whether the lobus dexter child node of judging described current ancestor node is greater than described terminal node;
Step 62 is if then be made as following one deck left side child of described current ancestor node the rightest ancestor node of described present node;
Step 63, if not, then the last layer ancestor node with described current ancestor node is made as new current ancestor node, and returns described step 42.
7. according to the Prefix Expansion method of claim 5,6 described realization three-folded content addressable memory range couplings, it is characterized in that whether the coverage of judging described current ancestor node is greater than described terminal node, judgment formula is as follows:
L-1+POW2(level)≤N
The initial leaf node that the described current ancestor node of " L " expression covers, " POW2 (level)=2
Level" the leaf node number that covers of the described current ancestor node of expression, the lobus dexter child node that " L-1+POW2 (level) " just represents that described current ancestor node covers, " N " represents described terminal node.
8. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 1 is characterized in that when the Wbit field was expanded, the Wbit field was in scope [1,2
W-2] the prefix number of being expanded mostly is 2 (W-1) most, and the height of described complete binary tree is W+1, and W represents field bit figure place.
9. the Prefix Expansion method of realization three-folded content addressable memory range coupling according to claim 1 is characterized in that, when commensurate in scope is carried out in the IP address, and the high-order prefix designates of using, low level uses described Prefix Expansion method to expand.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2006100115176A CN101039253B (en) | 2006-03-17 | 2006-03-17 | Method for realizing prefix extension of range matching of ternary content addressable memory |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2006100115176A CN101039253B (en) | 2006-03-17 | 2006-03-17 | Method for realizing prefix extension of range matching of ternary content addressable memory |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101039253A true CN101039253A (en) | 2007-09-19 |
| CN101039253B CN101039253B (en) | 2010-12-29 |
Family
ID=38889900
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2006100115176A Active CN101039253B (en) | 2006-03-17 | 2006-03-17 | Method for realizing prefix extension of range matching of ternary content addressable memory |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101039253B (en) |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2013167080A2 (en) * | 2013-01-24 | 2013-11-14 | 中兴通讯股份有限公司 | Storage information processing method and device |
| CN103516614A (en) * | 2012-06-28 | 2014-01-15 | 美国博通公司 | System and method for storing integer ranges in a memory |
| CN104184732A (en) * | 2014-08-25 | 2014-12-03 | 浪潮集团有限公司 | Hardware implementation method for matching IP address with IP range strategy |
| CN104410573A (en) * | 2014-11-26 | 2015-03-11 | 中国电子科技集团公司第四十一研究所 | Package matching method based on TCAM (ternary content addressable memory) |
| CN104718731A (en) * | 2012-06-27 | 2015-06-17 | 华为技术有限公司 | Ternary content-addressable memory assisted packet classification |
| CN105515997A (en) * | 2015-12-07 | 2016-04-20 | 刘航天 | BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion |
| CN111625694A (en) * | 2020-06-05 | 2020-09-04 | 中国银行股份有限公司 | Multistage label processing method and device and computer equipment |
| CN115033750A (en) * | 2022-03-23 | 2022-09-09 | 成都卓源网络科技有限公司 | TCAM-based classification structure and method |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6633548B2 (en) * | 2001-01-30 | 2003-10-14 | Nokia Intelligent Edge Routers Inc. | Method and apparatus for ternary content addressable memory (TCAM) table management |
| CN1327674C (en) * | 2005-02-25 | 2007-07-18 | 清华大学 | Double stack compatible router searching device supporting access control listing function on core routers |
| CN100387028C (en) * | 2005-04-01 | 2008-05-07 | 清华大学 | Parallel IP packet sorter matched with settling range based on TCAM and method thereof |
-
2006
- 2006-03-17 CN CN2006100115176A patent/CN101039253B/en active Active
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104718731B (en) * | 2012-06-27 | 2017-08-29 | 华为技术有限公司 | Method, device and the network router for the bag classification that ternary content addressable internal memory is assisted |
| CN104718731A (en) * | 2012-06-27 | 2015-06-17 | 华为技术有限公司 | Ternary content-addressable memory assisted packet classification |
| CN103516614A (en) * | 2012-06-28 | 2014-01-15 | 美国博通公司 | System and method for storing integer ranges in a memory |
| WO2013167080A3 (en) * | 2013-01-24 | 2014-01-03 | 中兴通讯股份有限公司 | Storage information processing method and device |
| WO2013167080A2 (en) * | 2013-01-24 | 2013-11-14 | 中兴通讯股份有限公司 | Storage information processing method and device |
| CN104184732A (en) * | 2014-08-25 | 2014-12-03 | 浪潮集团有限公司 | Hardware implementation method for matching IP address with IP range strategy |
| CN104410573A (en) * | 2014-11-26 | 2015-03-11 | 中国电子科技集团公司第四十一研究所 | Package matching method based on TCAM (ternary content addressable memory) |
| CN104410573B (en) * | 2014-11-26 | 2017-07-21 | 中国电子科技集团公司第四十一研究所 | A kind of bag matching process based on TCAM |
| CN105515997A (en) * | 2015-12-07 | 2016-04-20 | 刘航天 | BF_TCAM (Bloom Filter-Ternary Content Addressable Memory)-based high-efficiency range matching method for realizing zero range expansion |
| CN105515997B (en) * | 2015-12-07 | 2018-07-06 | 刘航天 | The higher efficiency range matching process of zero scope expansion is realized based on BF_TCAM |
| CN111625694A (en) * | 2020-06-05 | 2020-09-04 | 中国银行股份有限公司 | Multistage label processing method and device and computer equipment |
| CN111625694B (en) * | 2020-06-05 | 2023-04-07 | 中国银行股份有限公司 | Multistage label processing method and device and computer equipment |
| CN115033750A (en) * | 2022-03-23 | 2022-09-09 | 成都卓源网络科技有限公司 | TCAM-based classification structure and method |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101039253B (en) | 2010-12-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101039253A (en) | Method for realizing prefix extension of range matching of ternary content addressable memory | |
| CN101035062A (en) | Rule update method for three-folded content addressable memory message classification | |
| CN101035061A (en) | Segmented coded expansion method for realizing the match of the three-folded content addressable memory range | |
| CN101035060A (en) | Integrated processing method for three-folded content addressable memory message classification | |
| CN1781098A (en) | Internet protocol security matching values in an associative memory | |
| CN1305281C (en) | Inter connected network protocol packet error processing equipment and its method and computer readable medium | |
| CN1581818A (en) | Method for supporting multi-port virtual LAN by multi-protocol label swtich | |
| US20020143787A1 (en) | Fast classless inter-domain routing (CIDR) lookups | |
| CN1863142A (en) | Method for providing different service quality tactics to data stream | |
| CN1929447A (en) | Method and device for searching address prefixion and message transfer method and system | |
| CN1744563A (en) | Method for realizing strate gic route in Ethernet switch | |
| CN1946061A (en) | Method and device for fast processing message | |
| CN1764193A (en) | Method for renewing address analysis protocol rapidly | |
| CN1558615A (en) | A physical network topological discovering system and method thereof | |
| CN112929281B (en) | Message processing method, device and equipment of network equipment based on FPGA | |
| CN101047649A (en) | Method and equipment for transmitting data flow | |
| CN1477494A (en) | Data packet recursive flow sorting method | |
| CN101075964A (en) | Method and system for realizing port re-direction by router interface address | |
| CN1545285A (en) | Method of access control list or security policy database | |
| CN1411231A (en) | Data packet transmission method in mobile IP | |
| CN1767495A (en) | Method for assuring two-layer Ethernet exchanger data safety in city area transmission equipment | |
| TW200414033A (en) | Address search | |
| CN1913495A (en) | Data conversion method and device | |
| CN1949749A (en) | Route storage method and apparatus | |
| CN1815997A (en) | Group classifying method based on regular collection division for use in internet |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |