Routing system and method for managing rule entries of ternary content addressable memory in the same
First Claim
1. A method of managing rule entries of a Ternary Content Addressable Memory (TCAM) in a routing system, the method comprising:
- creating a hash table having a hash key corresponding to each entry;
creating a single linked list for linking nodes, the single linked list using an entry of the hash table as a head node and the nodes including rule IDs and sequence IDs assigned according to a rule input order; and
creating a double linked list having an independent head node, the double linked list bidirectionally linking the nodes constituting the single linked list according to an order of the sequence IDs.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of managing rule entries of a Ternary Content Addressable Memory (TCAM) in a routing system includes: creating a hash table having a hash key corresponding to each entry; creating a single linked list for linking nodes, the single linked list using the entry of the hash table as a head node and including rule IDs and sequence IDs assigned according to a rule input order; and a double linked list having an independent head node, the double linked list bidirectionally linking the nodes constituting the single linked list according to an order of the sequence IDs. Thus, the packet classifying/filtering rule can be easily added to the TCAM or deleted from the TCAM only with minimal information. Also, the sequence ID reassignment process, required for storing as many rules in the TCAM as possible according to the priority of the rules, is performed when a certain time elapses following rule addition or deletion, thereby reducing a latency that may be caused upon setting the packet classifying/filtering rule.
-
Citations
21 Claims
-
1. A method of managing rule entries of a Ternary Content Addressable Memory (TCAM) in a routing system, the method comprising:
-
creating a hash table having a hash key corresponding to each entry; creating a single linked list for linking nodes, the single linked list using an entry of the hash table as a head node and the nodes including rule IDs and sequence IDs assigned according to a rule input order; and creating a double linked list having an independent head node, the double linked list bidirectionally linking the nodes constituting the single linked list according to an order of the sequence IDs. - View Dependent Claims (2, 3)
-
-
4. A method of managing rule entries of a Ternary Content Addressable Memory (TCAM) in a routing system, the method comprising:
-
creating a hash key corresponding to a received rule and searching a hash table entry matching the hash key in response to receipt of a rule to be added to the TCAM; determining whether a node matching information on the rule exists in a single linked list associated with the searched hash table entry; and adding a new node including information on the received rule before a first node on the single linked list, and adding the new node before a first node on a backward list in a double linked list in response to the absence of a node matching the information on the rule. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A routing system comprising:
-
a network processor to create a hash table including a hash key, a single linked list for linking nodes, the single linked list using an entry of the hash table as a head node and linking the node including rule IDs and sequence IDs assigned according to a rule input order, and a double linked list having an independent head node, the double linked list bidirectionally linking the nodes constituting the single linked list according to an order of the sequence IDs; and a Ternary Content Addressable Memory (TCAM) to store a rule included in the node in a TCAM entry indicated by a sequence ID assigned to the rule. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification