KR20050043035A - Method and hardware architecture for searching ip address by using multiple hashing function - Google Patents

Abstract

The present invention relates to an IP address retrieval method and a hardware structure using a plurality of hash functions.

The present invention relates to an IP address retrieval method using a plurality of hashing functions, comprising: (a) hashing an input address at least once for each prefix length; (b) comparing the prefix stored at the point indicated by the result of the hashing of the forwarding table with the prefix of the address; (c) comparing the prefix stored in an overflow table with the prefix of the address; (d) if the prefix stored in the point indicated by the result of the hashing matches the prefix of the address as a result of the comparison between the steps (b) and (c), transmitting information of the matched entry; And (e) searching for an entry having the longest bit number of the prefix among the entries searched for each prefix length of the address by using the information transmitted in the step (d). The present invention relates to an IP address retrieval method and hardware structure using a hashing function.

According to the present invention, the prefixes are classified according to the prefix lengths, and a separate table is configured to enable parallel retrieval by length for all prefixes. Through this, hashing can be applied to the IP address, and the search time can be reduced.

Description

IP address search method and hardware structure using multiple hash functions {Method and Hardware Architecture for Searching IP Address by Using Multiple Hashing Function}

The present invention relates to an IP address retrieval method and a hardware structure using a plurality of hash functions. More specifically, the prefixes of IP addresses are classified by length to form a plurality of tables for each length, and for each table, an address search is performed by applying multiple hashes using a hash function in parallel, and then matching each table. The present invention relates to a method for retrieving an IP address by searching for an entry having the longest number of bits among prefixes, and a hardware structure therefor.

One of the main functions that must be performed in real time on Internet routers, which are widely used throughout the world, is to forward received packets to their final destination. To this end, all routers have a forwarding table, and information about output ports and next hop addresses for accessing a destination address from this forwarding table is provided. Get it. When a packet is received, the router uses the network part of the destination address of the received packet as a key to refer to the forwarding table, which is called address lookup, and the network part used at this time is prefixed. It is called (Prefix).

In the conventional addressing scheme (Classful Addressing Scheme), the prefix of the IP address is fixed to 8 Bit, 16 Bit or 24 Bit. In the addressing method having a class, IP addresses are wasted because the prefix is fixed, and the size of the forwarding table of the router must increase exponentially as the type of network increases.

In order to solve this problem, Classless Interdomain Routing (CIDR) has been devised. In the CIDR method, the prefix length is not fixed. Therefore, waste of IP addresses can be prevented and address aggregation is prevented. This has the advantage that the size of the forwarding table can be prevented from increasing rapidly at the router. However, a disadvantage of the CIDR scheme is that the longest prefix matching must be performed at the router. Since the input packet does not contain information about the prefix length of its final network, it is necessary to find an entry among the prefixes in the forwarding table that matches the address of the input packet the longest. In other words, various address search schemes, which have been used for exact matching, are no longer applicable to the long-gate prefix matching scheme, which is a bottleneck in the router.

The first number of criteria for evaluating the performance of an address lookup structure is the number of memory lookups. It is important to reduce the number of memory lookups, which is the biggest overhead of the address lookup speed, because the demand for fast address lookup also increases as the link speed increases. Second is the size of the memory. In the case of a backbone router, as the number of networks connected to the router increases exponentially, the number of entries that must be stored in the forwarding table also increases rapidly. The size of the memory is an important element of the address search structure. In addition, performance evaluation is based on the ability to add new prefixes to the forwarding table, ease of table updates to remove unused prefixes, and scalability to IPv6 with 128-bit addresses.

In recent years, various address lookup methods have been studied for Internet routers. Various conventional address search methods are classified as follows.

As a method for address retrieval, there is a method using a content addressable memory (CAM). This method is widely used in the implementation of a real exchange or a router, and it enables very fast address retrieval by directly comparing all the prefixes stored in the input address and the content addressing memory at the same time. The problem is that it is not developing as fast as the number of prefixes used in routers. In other words, compared to RAM, which occupies the same amount of space, the number of prefixes that can be stored in the content addressing memory is very small, the content addressing memory is expensive, and the content addressing memory that stores tens of thousands of prefixes It is difficult to implement, and even if implemented, it is difficult to embed it inside a chip designed to perform an address lookup. Therefore, there is a problem that the application of the content addressing memory related technology to the forwarding table of a backbone router having tens of thousands of entries or IPv6 having a 128-bit address is unreasonable.

Another approach for address retrieval is a search scheme based on a Trie structure. A tree is a tree-based data structure, which is the most representative data structure in which relationships between prefixes are easily expressed. In a tri structure, all prefixes are defined as paths located at one node in the tri and starting from the root node. Since tens of thousands of prefixes of routers are mainly represented by a tri, a scheme of efficiently storing a tri structure in memory and various IP address retrieval methods have been studied. The tri-based scheme has a problem of wasting memory that comes from storing internal nodes that do not correspond to a prefix, and having to perform W memory searches when W is the height of the tri. In addition, there is a problem in that it is not easy to add a new prefix or update to be performed to remove an unused prefix.

Among the proposed tri-structures, a search scheme that reduces the number of memory searches by using an prefix extension has been proposed. Some prefixes have D prefix length sets as L prefix length sets (D> L). Extending the length reduces the number of sets of prefix lengths. In addition, a method of performing a first search in a memory having 2 ²⁴ entries by extending all prefixes having a length less than 24 to 24 has been proposed. If the incoming address has a prefix longer than 24, it moves to a content addressing memory (CAM) that stores the remaining prefix longer than 24 and performs a search. This method has the advantage that the maximum number of memory retrieval times is two, but there is a problem that a large memory of 33 Mbytes must be used to store 2 ²⁴ entries.

On the other hand, if the length of the prefix is less than 16, expands it to ¹⁶ and configures a forwarding table with 2 ¹⁶ entries in memory, and if the prefix of the incoming address is longer than 16, search for prefix longer than 16 along the auxiliary tree. A way of doing this is also proposed. This search method has the advantage of using a smaller memory than the above-described method, but there is a problem that the amount of pre-computation and update is difficult.

Another way to look up an address is to use hashing between prefixes of the same length. Hashing has been widely used for Layer 2 address retrieval using a perfect match. However, the binary search combined hashing method has a problem that pure binary search is not applied. In other words, even if the entry retrieved by the hash does not contain a prefix, a marker must be stored to indicate that a longer prefix exists because of the nature of long-term prefix matching of the IP address. There is a problem in that overhead is involved in calculating and storing. In addition, the binary search combined hashing method is not practical because it assumes that a perfect hash function can be found in a short time for a specific prefix distribution.

In order to overcome this problem, a parallel search method using hashing that finds the longest matched prefix among matching prefixes is performed after performing parallel search on all prefix lengths using separate hash functions for each prefix length. It became. In the parallel search method using hashing, it is possible to search using hashing function implemented by Exclusive OR without assuming a perfect hashing function, and collisions occurring in hashing can be solved by using a sub table. It is a very practical structure as a structure. However, when a collision occurs in the primary table, the binary search is performed on the secondary table, which causes a problem that the maximum number of memory accesses is large.

In order to overcome this problem, a method of finding length levels by performing binary search on one table classified by prefix length and applying hashing to each length level search has been proposed. In this system, a maximum of log ₂ W memory searches are required when an address search is performed for W prefix types. This method has a problem in that it can be used as a valid method only when the prefix information does not change frequently because there are many preprocessing calculations, tables are difficult to update, and a considerable time is required to find the complete hash function.

In order to solve the problem that it takes a long time to find the complete hash function, a method of finding a number of hash functions according to the data distribution has been proposed instead of the perfect hash function. This approach enables Semi Perfect Hashing by using multiple hash functions and creating a table for each hash function.

1 is a diagram illustrating a table configuration method for performing an address search using a plurality of hash functions.

As shown in Fig. 1, when creating a routing table, one prefix is passed through several different hash functions, and the result of the hash obtained from the function is used as a pointer to each table. Fill the table with prefixes. Using this method has the advantage of reducing the possibility of collision caused by hashing by using several hashing functions, and the data are distributed evenly in the table.

2 is a diagram illustrating a method of searching for an address using a plurality of hash functions.

As shown in FIG. 2, in the method using a plurality of hash functions, a binary search is applied for each prefix length to search a table for each prefix and find a matching entry. As such, using two hash functions has the advantage that performance is improved compared to using one hash function.

However, since address search using multiple hash functions uses multiple hash hardware, there is still a problem of finding a suitable hash function according to the distribution of data. In addition, during the insert process for updating a table, if the bucket of the table indicated by the result of the hash is full, there is a problem that the process of finding a hash function suitable for the current data distribution has to be repeated.

In order to solve the above problems, the present invention, in the IP address retrieval method and hardware structure using a plurality of hashing functions, the prefix of the IP address is classified by length to form a plurality of tables for each length and hashed for each table A method for searching an IP address by applying an address in parallel by applying multiple hashes using a function, and then searching for an entry that matches the longest number of bits of a prefix among entries matched in each table, and hardware for the same. The purpose is to provide a structure.

According to a first object of the present invention, there is provided an IP address retrieval method using a plurality of hashing functions, comprising: (a) hashing an input address at least once for each prefix length; (b) comparing the prefix stored at the point indicated by the result of the hashing of the forwarding table with the prefix of the address; (c) comparing the prefix stored in an overflow table with the prefix of the address; (d) if the prefix stored in the point indicated by the result of the hashing matches the prefix of the address as a result of the comparison between the steps (b) and (c), transmitting information of the matched entry; And (e) searching for an entry having the longest bit number of the prefix among the entries searched for each prefix length of the address by using the information transmitted in the step (d). Provides an IP address retrieval method using the hash function of.

According to a second object of the present invention, there is provided a hardware structure for IP address retrieval using a plurality of hashing functions, comprising: hashing hardware for hashing a prefix of an input address; One or more forwarding tables and an overflow table in which entries are stored in the form of hash tables according to the prefix length of the address, the prefix stored at a point indicated by the result of the hash of the forward table. And a main processor for comparing the prefix stored in the overflow table with the prefix of the address and transmitting information of the matched entry. And a Priority Encoder for receiving the information of the matched entry and searching for an entry having the longest number of bits of the prefix among the searched entries for each prefix length of the address. It provides a hardware structure for IP address lookup using.

According to a third object of the present invention, there is provided a method of generating a forwarding table for retrieving an IP address, the method comprising: (a) dissolving an input address at least once for each prefix length; (b) storing the prefix with a bucket having a smaller load among the buckets indicated by the result of one or more hashes; And (c) if there is no storage space in the forwarding table, storing the prefix in a bucket of an overflow table.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. First of all, in adding reference numerals to the components of each drawing, it should be noted that the same reference numerals are used as much as possible even if displayed on different drawings. In addition, in describing the present invention, when it is determined that the detailed description of the related well-known configuration or function may obscure the gist of the present invention, the detailed description thereof will be omitted.

A preferred embodiment of the present invention proposes a method of applying parallel search to a method using a plurality of hash functions based on data analysis.

3 is a diagram illustrating a hardware structure for IP address retrieval according to a preferred embodiment of the present invention.

The hardware structure for IP address retrieval according to the preferred embodiment of the present invention has a structure including hash hardware 300, main processor 302 and Priority Encoder (308).

The hash hardware 300 according to the preferred embodiment of the present invention functions to hash the prefix of the input address. The hashing hardware 100 according to the preferred embodiment of the present invention is a CRC hashing hardware using a fixed CRC hashing function to facilitate the hardware implementation and updating of the forwarding table. How to get the results of the hash from the CRC hash hardware is described in detail later.

The main processor 302 according to the preferred embodiment of the present invention includes one or more forwarding tables 304 and an overflow table 306 in which entries are stored in the form of hash tables according to the prefix length of the address. have. The main processor 302 compares the prefix stored at the point in the forwarding table 304 indicated by the hash value from the hash hardware 300 and the prefix of the input address, and inputs the prefix stored in the overflow table 306. After comparing the prefix of the matched address, information of the matched entry is transmitted to the Priority encoder 308.

Priority encoder 308 according to the preferred embodiment of the present invention waits for the end of the search in all tables for any one address, and then searches for the entry with the longest number of bits of the prefix among the entries searched by the prefix length of the address. do.

The IP address retrieval scheme according to the preferred embodiment of the present invention is a new retrieval scheme in which two forwarding tables 304 and two hash functions are performed for each prefix length, and address searches are performed in parallel for all prefixes. The reason why the long-establish prefix matching method is difficult is because a plurality of matching entries may be stored in the forwarding table because the length of the prefix is not fixed. In the hardware structure according to the preferred embodiment of the present invention, in order to solve the problem of an increase in the number of memory searches due to an unfixed prefix length, a separate table is formed for each prefix length and stored in different memories in parallel to all lengths. Search was enabled. That is, the transfer table 304 is set separately for each prefix (prefix type * 2 according to length), and the problem according to the long-establishment prefix matching method is converted into an exact matching problem. Therefore, each main processor 302 configured for each prefix length needs only to find one matching entry for the corresponding length during the search. Thus, the longest entry among the parallel entries found in each main processor 302 is determined as a matching entry. Will be.

In addition, in the preferred embodiment of the present invention, only one hashing hardware 300 can be used to obtain hash values for all prefixes in a time sharing manner. In the previous method, a software-based method for finding a suitable hashing function through the CPU according to the distribution of data is proposed. However, in the preferred embodiment of the present invention, hardware implementation and updating is provided by providing a method using a fixed hashing function. This makes it easy to speed up the search of addresses.

4 is a schematic diagram of CRC hashing hardware for calculating the result of hashing according to a preferred embodiment of the present invention.

Hashing is a way of mapping input values to shorter values by passing them through a hashing function. The hash maps the input value to a shorter value, so that different inputs are mapped to the same output value. This phenomenon is called collision, and in the case of structure using hashing, it is important to minimize collision. So a good hashing function is to be able to have a uniform output for any set of inputs. Applying a hash to IP address retrieval results in better performance because the prefixes can be stored more efficiently in the forwarding memory, and a search can find matching entries in a single search, but this must be considered. How to deal with it. In the preferred embodiment of the present invention, in order to minimize the collision, the CRC evaluated to have a performance close to perfect hashing among the hashing functions is used.

In addition, the result values of all hashes for each forwarding table 304 are obtained from one hashing hardware 300, so that a separate hashing hardware 300 is not used for each prefix, thereby burdening the parallel processing structure. Reduced.

The method of obtaining the hash values from the CRC hash hardware 300 according to the preferred embodiment of the present invention is as follows. First, the destination IP address is entered into the CRC hashing hardware 300 by one bit from the high order bit in every cycle. After D cycles after the destination address starts entering the CRC hash hardware 300, two hash values of a particular length are extracted from the CRC register and used as the result of the hash of the prefix D. The result is obtained from one hash hardware 300 with time difference. For example, if the first 8 bits of the IP address enter the CRC hash hardware 300, then the result of two hashes for prefix 8 is extracted from the CRC register. It takes 32 cycles to get the result of the hash for prefix 32 by extracting the two hash values for prefix 9. In this case, the hash value is an index, so the hash length of the table where the prefix is stored is determined by considering the number of entries to be stored.

5 shows the entry structure of the transfer table 304 according to the preferred embodiment of the present invention.

In a preferred embodiment of the present invention, as a result of data analysis for specifying the number of buckets and entries per bucket of each forwarding table 304, two hash functions are used and N items are stored in a table having N / 2 buckets. We found that the probability of 3 or more collisions in each table was very low, 1.5e ^-50 . Based on this analysis, an entry structure according to a preferred embodiment of the present invention will be described using an example of having two hash functions and six loads per bucket for each prefix length.

As shown in FIG. 5, each entry of the delivery table 304 has three loads, so an entry of the delivery table 304 has an item number field indicating three numbers of loads storing prefixes, and three prefixes. Field, and three forwarding RAM pointer fields.

Algorithm 1 is an algorithm for generating the forwarding table 304 according to the preferred embodiment of the present invention.

Algorithm 1

The process of generating the transfer table 304 according to the preferred embodiment of the present invention based on Algorithm 1 will be described with reference to FIG.

6 is a diagram illustrating a process of generating a delivery table 304 according to a preferred embodiment of the present invention.

First, the destination IP address is hashed by entering the CRC hash hardware 300 bit by bit. Then, after the L (prefix length) cycle, the result of the hash is extracted from the CRC register. The prefixes stored in the forwarding table are stored in the bucket with the smaller load among the buckets indicated by the two hash values. If the two buckets have the same load, it is prestored in Table 1 (601). If the overflow occurs because the two tables (601, 602) are full, they are stored in the overflow table (306) configured separately. In the structure according to the preferred embodiment of the present invention, a total of 50 main tables 601 and 602 and an overflow table 306 are required, two for each prefix.

Algorithm 2 is an algorithm for retrieving an IP address according to a preferred embodiment of the present invention.

Algorithm 2

A process of retrieving an IP address according to the preferred embodiment of the present invention based on Algorithm 2 will be described with reference to FIG.

7 is a diagram illustrating a process of searching for an IP address according to a preferred embodiment of the present invention.

The IP address retrieval process is performed in parallel using the hash value obtained from the CRC hash hardware 300. The result of the hash required for the retrieval process is obtained in a similar way to constructing the forwarding table 304. The only difference is that the result of the hash for all prefixes is not the result of the hash for one prefix. It must be chosen.

As described in Algorithm 2, the input address is hashed by the prefix length, and the parallel search is performed by the prefix length on the forwarding tables 701 and 702 of each prefix using the result of the hashing as the index of the table. At this time, the overflow table 306 is also searched at the same time. As a result of the search, if the prefix stored at the point indicated by the hash value and the prefix of the input address match, the information of the matched entry is transmitted to the Priority encoder 308. At this time, the information of the matched entry includes a pointer to the forwarding RAM. The priority encoder 308 finds an entry having the longest number of prefix bits among the searched entries using the received information, and forwards the packet to the output port using its forwarding RAM pointer information.

As mentioned in the process of creating the forwarding tables 701 and 702, when the forwarding tables 701 and 702 are full and there is no space for storing the newly added prefix, the forwarding tables 701 and 702 are stored in the overflow table 306 configured separately. This overflow table 306 is implemented using content addressable memory (CAM) and allows matching entries to be found directly in a single search.

On the other hand, updating the delivery table structure created according to the preferred embodiment of the present invention is very simple. The update process is performed in the same way as the transfer table configuration process. In other words, you can store the prefix to be stored in the bucket with the least load among the buckets indicated by the hash key, and in the overflow table if the table overflows. This method has the advantage that a fast update is possible because the preprocessing time is not required long. It is also possible to expand to IPv6 by simply increasing the number of bits in the result of hashing and the number of entries in the forwarding table.

Hereinafter, the performance of the IP address retrieval method and hardware structure for the same according to a preferred embodiment of the present invention.

8 is a graph showing a route distribution according to a prefix length in a hardware structure for IP address retrieval according to a preferred embodiment of the present invention.

The simulation was performed using the actual data passed through the MAE-WEST router for the hardware according to the preferred embodiment of the present invention. FIG. 8 shows the distribution of the prefixes passed through the MAE-WEST router. In this simulation, test cases were determined for items, buckets, and hash functions based on the router's prefix distribution to test entry efficiency and overflow rate. Here, entry efficiency refers to the ratio of entries storing prefixes to all table entries.

Table 1 is a table showing the entry efficiency and the overflow occurrence rate obtained as a result of the simulation performed by varying the number of items, the number of buckets and the number of hash functions.

case Number of items Number of Bucket Number of hash functions Entry number / bucket Memory size Entry efficiency Overflow Rate One N N / 2 One 4 203 KB 49.85% 3.4% 2 N N / 2 2 4 203 KB 49.85% 0.52% 3 N N / 2 2 6 303 KB 33.41% 0% 4 N N / 4 3 6 152 KB 66.3% 0.46%

Case 1 uses one hash function. In other words, if 25 prefixes are stored for each length. As shown in Table 1, when N items were stored in N / 2 buckets with 4 loads for each bucket, about 200 Kbytes of memory was required, which resulted in a 3.4% overflow. However, the other conditions are the same as in case 1, and in case 2 where the number of hash functions is increased to 2, the overflow rate is significantly reduced to about 0.5%. Compared to using one hash function, using two hash functions reduces the value of overflow because each prefix is evenly distributed in both tables. Case 3 allocated about 33% more memory than the previous two cases to completely eliminate the overflow, which completely eliminated the overflow. Finally, case 4 is the case where N items are stored in N / 4 buckets with 6 loads per bucket and three hash functions are used to make the most efficient use of memory. In this case, it took about 152 Kbytes of memory and 136 overflows.

As a result of the comparison of the four cases described above, it can be seen that the overflow caused by the collision can be drastically reduced when using several than the simulation using one hash function. In addition, it can be seen that the memory efficiency and the overflow rate are in a trade-off relationship.

On the other hand, the results shown in Table 1 shows that the rate of occurrence of overflow is very small. Thus, the overflow table 306 can be implemented using a content addressable memory (CAM) with a small number of entries.

Table 2 compares the performance of the existing search structure with the search structure according to the preferred embodiment of the present invention.

Address Lookup Scheme Number of Memory Accesses (Minimum / Maximum) Forwarding Table Size Huang's scheme 1/3 450KB to 470KB DIR-24-8 1/2 33 MB DIR-21-3-8 1/3 9 MB SFT 2/9 150KB to 160KB Parallel hashing 1/5 189 KB Inventive Architecture One 203 KB + CAM with 154 entries

As shown in Table 2, the search structure according to the preferred embodiment of the present invention is excellent in that the search can be performed with only one memory access at all times, and the required memory size is about 203 Kbytes, which is very high compared to other search structures. It can be seen that the excellent performance.

The above description is merely illustrative of the present invention, and those skilled in the art to which the present invention pertains may various modifications without departing from the essential characteristics of the present invention. Accordingly, the embodiments disclosed herein are not intended to limit the present invention but to describe the present invention, and the spirit and scope of the present invention are not limited by these embodiments. It is intended that the scope of the invention be interpreted by the following claims, and that all descriptions within the scope equivalent thereto shall be construed as being included in the scope of the present invention.

As described above, according to the present invention, the prefixes are classified according to the prefix length and a separate table is configured to enable parallel search by length for all the prefixes. Through this, hashing can be applied to the IP address, and the search time can be reduced. In addition, as a result of using multiple hash functions to show performance similar to a perfect hash, it is possible to search for all prefixes with a single memory search.

In addition, according to a preferred embodiment of the present invention, all prefixes can be stored without overflow by using only 300 Kbytes of memory. However, if 150 Kbytes of memory is used for more efficient use of memory, only 99.5% of the prefix can be stored in memory. Even if it occurs, there is an effect of enabling the search at the same time as the forwarding table search without additional memory search.

In addition, the structure according to the preferred embodiment of the present invention has the advantage that the prefix update and the switch to IPv6 is simple, and the hardware implementation is easy due to the repeatability of the function.

1 is a diagram illustrating a table configuration method for performing an address search using a plurality of hash functions.

2 is a diagram illustrating a method of searching for an address using a plurality of hash functions;

3 illustrates a hardware structure for IP address lookup according to a preferred embodiment of the present invention;

4 is a schematic representation of CRC hashing hardware for calculating the result of a hashing in accordance with a preferred embodiment of the present invention;

5 shows an entry structure of the transfer table 304 according to the preferred embodiment of the present invention;

6 is a view showing a process of creating a delivery table 304 according to a preferred embodiment of the present invention;

7 illustrates a process of searching for an IP address according to a preferred embodiment of the present invention;

8 is a graph showing a route distribution according to a prefix length in a hardware structure for IP address retrieval according to a preferred embodiment of the present invention.

<Explanation of symbols for the main parts of the drawings>

300: hash hardware 302: main processor

304: forwarding table 306: overflow table

308: Priority Encoder

Claims (26)

In the IP address retrieval method using a plurality of hash functions, (a) hashing the input address at least once for each prefix length; (b) comparing the prefix stored at the point indicated by the result of the hashing of the forwarding table with the prefix of the address; (c) comparing the prefix stored in an overflow table with the prefix of the address; (d) if the prefix stored in the point indicated by the result of the hashing matches the prefix of the address as a result of the comparison between the steps (b) and (c), transmitting information of the matched entry; And (e) searching for an entry having the longest bit number of the prefix among the entries searched for each prefix length of the address by using the information transmitted in step (d). IP address retrieval method using a plurality of hash function, characterized in that it comprises a. The method of claim 1, The address search in the forwarding table or the overflow table is performed simultaneously in parallel for each prefix length of the address. The method of claim 1, And classifying the prefixes of the addresses by length to generate one or more forwarding tables for each length. The method of claim 1, And the forwarding table is stored in one memory for each prefix length of the address. The method of claim 1, And said hashing is performed using a CRC hashing function. The method of claim 1, The entry of the forwarding table includes a field indicating the number of loads storing the prefix, a prefix field used for the search, and a forwarding RAM pointer field. Way. The method of claim 1, And the information of the matched entry includes a pointer to a forwarding RAM. The method of claim 1, And a result value of one or more hashes is provided from one hash hardware at a time difference. The method of claim 1, The overflow table is an IP address retrieval method using a plurality of hash functions, characterized in that the content addressable memory (CAM). In the hardware structure for IP address retrieval using a plurality of hash functions, Hash hardware for hashing the prefix of the input address; One or more forwarding tables and an overflow table in which entries are stored in the form of hash tables according to the prefix length of the address, the prefix stored at a point indicated by the result of the hash of the forward table. And a main processor for comparing the prefix stored in the overflow table with the prefix of the address and transmitting information of the matched entry. And Priority encoder that receives the information of the matched entry and searches for an entry with the longest number of bits of the prefix among the entries found for each prefix length of the address. Hardware structure for IP address search using a plurality of hash function, characterized in that it comprises a. The method of claim 10, The address search in the forwarding table or the overflow table is performed simultaneously in parallel for each prefix length of the address. Hardware structure for IP address search using a plurality of hash functions. The method of claim 10, At least one forwarding table is generated for each length by dividing the prefixes of the addresses by lengths. The method of claim 10, The forwarding table is stored in one memory for each prefix length of the address. Hardware structure for IP address search using a plurality of hash functions. The method of claim 10, The hash hardware is a hardware architecture for IP address search using a plurality of hash functions, characterized in that CRC hash hardware using a CRC hash function. The method of claim 10, The entry of the forwarding table includes a field indicating the number of loads storing the prefix, a prefix field used for the search, and a forwarding RAM pointer field. Hardware architecture. The method of claim 10, And the information of the matched entry includes a pointer to a forwarding RAM. The method of claim 10, And a result value of one or more hashes is provided from one hash hardware at a time difference. The method of claim 10, The overflow table is a hardware structure for IP address retrieval using a plurality of hash functions, characterized in that implemented by a content addressable memory (CAM). In the method of generating a forwarding table for IP address retrieval, (a) hashing the input address at least once for each prefix length; (b) storing the prefix in a bucket having a small load among buckets indicated by one or more result values of the hash; And (c) if there is no storage space in the forwarding table, storing the prefix in a bucket of an overflow table Method for generating a forwarding table for IP address search, characterized in that it comprises a. The method of claim 19, The input address is input to the hash hardware by one bit, characterized in that the forwarding table generation method for IP address search. The method of claim 19, And generating one or more forwarding tables for each length by classifying the prefixes of the addresses by length. The method of claim 19, And the forwarding table is stored in one memory for each prefix length of the address. The method of claim 19, And said hashing is performed using a CRC hashing function. The method of claim 19, The entry of the forwarding table includes a field indicating the number of loads storing the prefix, a prefix field used for the search, and a forwarding RAM pointer field. The method of claim 19, And a result value of one or more hashes is provided from one hash hardware at a time difference. The method of claim 19, And the overflow table is implemented as a content addressable memory (CAM).