Routing system and method for managing rule entries of ternary content addressable memory in the same

• US 20080192754A1
• Filed: 02/05/2008
• Published: 08/14/2008
• Est. Priority Date: 02/12/2007
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Bong-Cheol, Ku, Yoon-Jin
• Application Number:
  US12/068,365
• Publication Number:
  US 20080192754A1
• Time in Patent Office: Days
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing

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.

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.

2. The method according to claim 1, wherein the hash key comprises a rule ID for identifying each packet classifying/filtering rule, an interface index to which the rule is applied, and an interface direction.

3. The method according to claim 1, wherein each node constituting the linked list further comprises information on an interface index to which the rule is applied.

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.

5. The method according to claim 4, further comprising:

assigning a sequence ID to the new node while reading the double linked list in an order of increasing sequence IDs, in response to the new node being added.

6. The method according to claim 4, further comprising storing the rule at a location of the TCAM indicated by the sequence ID.

7. The method according to claim 4, further comprising performing a search to determine whether a node corresponding to the rule ID and an interface index exists in the single linked list, and deleting the rule from a location of the TCAM indicated by a sequence ID included in the node corresponding to the rule ID and the interface index, in response to the received rule being a rule to be deleted from the TCAM.

8. The method according to claim 7, further comprising deleting the node from the double linked list and the single linked list, in response to the rule being deleted from the location of the TCAM.

9. The method according to claim 4, further comprising reassigning the sequence ID while sequentially reading the double linked list, in response to an entry in which a rule is not stored and no non-used entry from a sequence ID to be assigned to a subsequently received rule to a last sequence ID.

10. The method according to claim 7, further comprising reassigning the sequence ID while sequentially reading the double linked list, in response to an entry in which a rule is not stored and no non-used entry from a sequence ID to be assigned to a subsequently received rule to a last sequence ID.

11. The method according to claim 9, wherein reassigning the sequence ID is performed following a time corresponding to an absolute value of a value obtained by subtracting the number of available entries of the TCAM before the last sequence ID from the number of non-used entries of the TCAM from the sequence ID to be assigned to the subsequently received rule to the last sequence ID.

12. The method according to claim 10, wherein reassigning the sequence ID is performed following a time corresponding to an absolute value of a value obtained by subtracting the number of available entries of the TCAM before the last sequence ID from the number of non-used entries of the TCAM from the sequence ID to be assigned to the subsequently received rule to the last sequence ID.

13. The method according to claim 9, wherein reassigning the sequence ID comprises sequentially reassigning the sequence IDs to the respective nodes constituting the double linked list while reading the double linked list in an order of the increasing sequence ID, the reassigned sequence IDs beginning with 1.

14. The method according to claim 10, wherein reassigning the sequence ID comprises sequentially reassigning the sequence IDs to the respective nodes constituting the double linked list while reading the double linked list in an order of the increasing sequence ID, the reassigned sequence IDs beginning with 1.

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.

16. The system according to claim 15, wherein each entry of the hash table comprises hash key including a rule ID for identifying each packet classifying/filtering rule, an interface index to which the rule is applied, and an interface direction.

17. The system according to claim 16, wherein the single linked list uses the entry of the hash table as the head node, and sequentially links nodes including information on the rule ID or the interface index corresponding to the sequence ID and the hash key.

18. The system according to claim 16, wherein the double linked list links respective nodes constituting the single linked list about the independent head node according to an order of an increasing or decreasing sequence ID.

19. The system according to claim 15, wherein the network processor comprises:

an interface to provide entry management information to an entry manager, the entry management information including information on a packet classifying/filtering rule and information for addition or deletion of any rule to or from the TCAM; and

the entry manager creating the hash table, the single linked list, and the double linked list, and storing or deleting any rule to or from the TCAM according to the entry management information by referring to the hash table, the single linked list, and the double linked list.

20. The system according to claim 15, wherein the network processor further comprises a lookup processor to filter a packet or to apply a packet classification-dependent policy according to packet forwarding information obtained by looking up the TCAM.

21. The system according to claim 15, further comprising a subsidiary memory to store forwarding information for a packet corresponding to each rule stored in the TCAM.