Method for generating nodes in multiway search tree and search method using the same

• US 20030123397A1
• Filed: 12/31/2001
• Published: 07/03/2003
• Est. Priority Date: 12/30/2000
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Lee, Kang-Bok, Lee, Sang-Woo, Lee, Heyung-Sub, Lee, Hyeong-Ho
• Granted Patent: US 7,403,494 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A node structure of a multiway search tree can accelerates a search speed by making a key, a key pointer and a node pointer coincident with the size of a cache line through the use of only one pointer written on a node regardless of the number of keys used in the node and, thereafter, reduce the main memory capacity, a search method using the node structure and a computer readable recording medium in which a program implementing the search method is recorded. The method for generating nodes of a multiway search tree includes the steps of: a) assigning at least one key to each of the nodes; and b) assigning pointer information so that related information written on the node is accommodated in a cache line regardless a number of keys.

Claims

1. A method for generating nodes of a multiway search tree, comprising the steps of:

a) assigning at least one key to each of the nodes; and

b) assigning pointer information so that related information written on the node is accommodated in a cache line regardless a number of keys.

2. The method as recited in claim 1, wherein the related information includes key information, a key pointer and a node pointer.

3. The method as recited in claim 1, wherein the step b) includes the steps of:

b1) setting a key pointer indicating an address of first key information among a plurality of key information assigned to the node; and

b2) assigning continuous addresses to the other key information except of the first key information, wherein the address of the key information is located at a distance corresponding to a value of the key information from the address indicated by the key pointer.

4. The method as recited in claim 3, further the step b) further includes the steps of:

b3) setting a node pointer indicating an address of a first child node pointer among a plurality of child nodes assigned to the node; and

b4) assigning continuous addresses to the other child nodes except a first child node, wherein the address of the child node is located at a distance corresponding to a value of the node information from an address indicated by the node pointer.

5. The method as recited in claim 2, wherein the node pointer includes key number information indicating a number of the key information and child node location information representing an address of the first child node.

6. The method as recited in claim 5, wherein, if the node is a leaf node, the node pointer sets all values of the child node location information as ‘

1’

.

7. The method as recited in claim 3, wherein addresses of the other key information except the first key information are located based on an equation as:

Address of nth Key=Key pointer Kp+(Number of Bits Assigned to a key*n)

where n represents a location of a packet.

8. A method for searching a multiway search tree in which pointer information is assigned to so as to accommodate related information in a cache line regardless of a number of keys used in each node, the method comprising the steps of:

a) comparing an inputted IP address with a key value;

b) if the inputted IP address is consistent with the key value, searching an outgoing interface by using a key pointer included in the node;

c) if the inputted IP address is not consistent with the key value, determining a type of the node by searching a node pointer;

d) if the node is a leaf node, searching the outgoing interface by acquiring the key pointer after monitoring where the consistency occurs; and

e) if the node is not the leaf node, moving to a next node with reference to the node pointer, and then repeating the steps of a) to c).

9. The method as recited in claim 8, wherein the step d) includes the steps of:

d1) finding a key value region having the inputted IP address based on a comparison result of the step a); and

d2) detecting the outgoing interface corresponding to the key value region.

10. The method as recited in claim 8, wherein the key value of the node is compared with the inputted IP address based a longest prefix matching (LPM).

11. A computer readable recording medium storing instructions for executing a method for generating nodes of a multiway search tree, the method comprising the steps of:

a) assigning at least one key to each of the nodes; and

b) assigning pointer information so that related information written on the node is accommodated in a cache line regardless a number of keys.

12. The computer readable recording medium as recited in claim 11, wherein the step b) includes the steps of:

b1) setting a key pointer indicating an address of first key information among a plurality of key information assigned to the node;

b2) assigning continuous addresses to the other key information except of the first key information, wherein the address of the key information is located at a distance corresponding to a value of the key information from the address indicated by the key pointer;

b3) setting a node pointer indicating an address of a first child node among a plurality of child nodes assigned to the node; and

b4) assigning continuous addresses to the other child nodes except a first child node, wherein the address of the child node is located at a distance corresponding to a value of the node information from an address indicated by the node pointer.

13. A computer readable recording medium storing instructions for executing a method for searching a multiway search tree in which pointer information is assigned to so as to accommodate related information in a cache line regardless of a number of keys used in each node, the method comprising the steps of:

a) comparing an inputted IP address with a key value;

b) if the inputted IP address is consistent with the key value, searching an outgoing interface by using a key pointer included in the node;

c) if the inputted IP address is not consistent with the key value, determining a type of the node by searching a node pointer;

d) if the node is a leaf node, searching the outgoing interface by acquiring the key pointer after noticing where the consistency occurs; and

e) if the node is not the leaf node, moving to a next node with reference to the node pointer, and then repeating the steps of a) to c).

14. The computer readable recording medium as recited in claim 13, wherein the step b) includes the steps of:

d1) finding a key value region having the inputted IP address based on a comparison result of the step a); and

d2) detecting the outgoing interface corresponding to the key value region.