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

• US 7,403,494 B2
• Filed: 12/31/2001
• Issued: 07/22/2008
• Est. Priority Date: 12/30/2000
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Jagannathan; Melanie
• Application Number:
  US10/038,923
• Publication Number:
  US 20030123397A1
• Time in Patent Office: 2,395 Days
• Field of Search: 370/392, 370/231, 709/241, 707/3
• 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 searching a multiway search tree in which pointer information is assigned so as to accommodate related information in a cache line independent of a number of keys used in each node, the method comprising the steps of:

a) comparing an inputted Internet Protocol (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 if the inputted IP address is consistent with the key value; 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).

2. The method as recited in claim 1, 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.

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

4. A computer readable recording medium storing instructions for executing a method for searching a multiway search tree in which pointer information is assigned so as to accommodate related information in a cache line independent 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 if the inputted IP address is consistent with the key value; 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).

5. The computer readable recording medium as recited in claim 4, 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.