METHOD FOR SELECTING HASH FUNCTION, METHOD FOR STORING AND SEARCHING ROUTING TABLE AND DEVICES THEREOF

• US 20100058027A1
• Filed: 07/29/2009
• Published: 03/04/2010
• Est. Priority Date: 09/01/2008
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Wang, Xiaozhong, Hu, Rui, Su, Hao, Gong, Jun, Sun, Tuanhui, Zhan, Chong, Chao, Hunghsiang Jonathan, Zhang, Jian, Chen, Hongfei
• Granted Patent: US 8,325,721 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 16/325 Hash tables
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A method for selecting a hash function, a method for storing and searching a routing table and devices thereof are provided. The method for selecting a hash function includes: hashing data to be hashed by using a current alternative hash function; decoding a hash result; accumulating decoded results until no carry occurs during the accumulation; and selecting a current alternative hash function with no carry generated as a formal hash function. The method for storing a routing table includes: dividing the routing table into a next-level node pointer portion and a prefix portion for being stored; and selecting a hash function by using the above method for selecting a hash function. The method for searching a routing table includes: directly searching an IP address to be searched according to a directly stored length of a next-level node pointer portion for storing the routing table; and reading a prefix node according to a searched result. Thus, hash collision can be avoided, and memory resources occupied by the routing table can be effectively reduced.

Claims

1. A method for selecting a hash function, comprising:

inputting data to be hashed;

hashing the data to be hashed by using a current alternative hash function;

decoding a hash result; and

accumulating the decoded results, if a carry occurs, replacing the current alternative hash function with a next alternative hash function to hash the data to be hashed until no carry occurs during the accumulation; and

selecting a current alternative hash function as a formal hash function if no carry occurs.

2. The method according to claim 1, wherein the inputting the data to be hashed comprises:

inputting the data to be hashed in parallel;

or

inputting the data to be hashed in serial;

or

inputting the data to be hashed in serial-parallel.

3. The method according to claim 2, wherein the hashing the data to be hashed by using the current alternative hash function comprises:

filtering the data to be hashed by using a significant bit of the current alternative hash function.

4. The method according to claim 3, wherein the replacing the current alternative hash function with the next alternative hash function comprises:

randomly selecting a next alternative hash function to replace the current alternative hash function;

or

selecting a next alternative hash function in a descending order to replace the current alternative hash function;

or

selecting a next alternative hash function in an ascending order of the number of significant bits to replace the current alternative hash function.

8. A method for storing a routing table, comprising:

dividing the routing table into a next-level node pointer portion and a matching entry portion for being stored;

storing root node data and first-level node data at the next-level node pointer portion, wherein the root node data comprises a root node matching entry with a next-level node pointer, a root node hash function of the matching entry, a next-level node pointer of a root node, and a matching entry pointer of the root node;

the root node hash function is a formal hash function selected by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the root node points to the matching entry portion; and

hashing an Internet protocol (IP) address in a step length range of a first-level node of the matching entry by using the root node hash function of the matching entry, and storing the first-level node data at a position pointed to by the next-level node pointer of the root node by using a hash result as an offset address, wherein the first-level node data comprises the IP address in the step length range of the first-level node of the matching entry, a hash function of the first-level node of the matching entry, a next-level node pointer of the first-level node and a matching entry pointer of the first-level node; and

the hash function of the first-level node is a formal hash function selected by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the first-level node points to the matching entry portion.

9. The method according to claim 8, further comprising:

storing N^th-level node data at the next-level node pointer portion; and

hashing an IP address in a step length range of an N^th-level node by using a hash function of an (N−

1)^th-level node of the matching entry, and storing the N^th-level node data at a position pointed to by the next-level node pointer of the (N−

1)^th-level node by using a hash result as an offset address, wherein the N^th-level node data comprises the IP address in the step length range of the N^th-level node of the matching entry, a hash function of the N^th-level node of the matching entry, a next-level node pointer of the N^th-level node, and a matching entry pointer of the N^th-level node; and

the hash function of the N^th-level node is a formal hash function selected by using the method for selecting a hash function according to claim 1;

the matching entry pointer of the N^th-level node points to the matching entry portion; and

N is an integer greater than or equal to 2.

10. A method for storing a routing table, comprising:

dividing the routing table into a next-level node pointer portion and a matching entry portion for being stored;

storing root node data and first-level node data at the next-level node pointer portion, wherein the root node data comprises a root node matching entry with a next-level node pointer, a hash function of a root node segment of the matching entry, a next-level node pointer of the root node segment, and a matching entry pointer of a root node;

the root node segment is a segment formed by dividing a next-level node of the root node matching entry into more than two segments;

the hash function of the root node segment is a formal hash function selected for an Internet protocol (IP) address in a step length range of a first-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the root node points to the matching entry portion; and

hashing the IP address in the step length range of the first-level node in the root node segment of the matching entry by using the hash function of the root node segment of the matching entry, and storing the first-level node data in the root node segment at a position pointed to by a next-level node pointer of the root node by using a hash result as an offset address;

wherein the first-level node data comprises the IP address in the step length range of the first-level node of the matching entry, a hash function of a first-level node segment of the matching entry, a next-level node pointer of the first-level node segment, and a matching entry pointer of the first-level node;

the first-level node segment is a segment formed by dividing a next-level node of the first-level node of the matching entry into more than two segments; and

the hash function of the first-level node segment is a formal hash function selected for an IP address in a step length range of a second-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the first-level node points to the matching entry portion.

11. The method according to claim 10, further comprising:

storing N^th-level node data at the next-level node pointer portion; and

hashing an IP address in a step length range of an N^th-level node in an (N−

1)^th-level node segment by using a hash function of the (N−

1)^th-level node segment of the matching entry, and storing the N^th-level node data in the (N−

1)^th-level node segment at a position pointed to by a next-level node pointer of the (N−

1)^th-level node segment by using a hash result as an offset address;

wherein the N^th-level node data comprises the IP address in the step length range of the N^th-level node of the matching entry, a hash function of an N^th-level node segment of the matching entry, a next-level node pointer of the N^th-level node segment, and a matching entry pointer of the N^th-level node; and

the hash function of the N^th-level node segment is a formal hash function selected for an IP address in a step length range of an (N+1)^th-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the N^th-level node points to the matching entry portion; and

N is an integer greater than or equal to 2.

12. A device for storing a routing table, comprising:

a first matching entry unit, configured to store a matching entry portion of the routing table; and

a first next-level node pointer unit, configured to store root node data and first-level node data;

wherein the root node data comprises a root node matching entry with a next-level node pointer, a root node hash function of the matching entry, a next-level node pointer of a root node, and a matching entry pointer of the root node;

the root node hash function is a formal hash function selected by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the root node points to the matching entry portion;

an Internet protocol (IP) address in a step length range of a first-level node of the matching entry is hashed by using the root node hash function of the matching entry, and a hash result is taken as an offset address to store the first-level node data at a position pointed to by the next-level node pointer of the root node;

the first-level node data comprises the IP address in the step length range of the first-level node of the matching entry, a hash function of the first-level node of the matching entry, a next-level node pointer of the first-level node, and a matching entry pointer of the first-level node;

the hash function of the first-level node is a formal hash function selected by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the first-level node points to the matching entry portion.

13. The device according to claim 12, wherein the first next-level node pointer unit is further configured to:

store N^th-level node data; and

hash an IP address in a step length range of an N^th-level node by using a hash function of an (N−

1)^th-level node of the matching entry, and store the N^th-level node data at a position pointed to by the next-level node pointer of the (N−

1)^th-level node by using a hash result as an offset address;

wherein the N^th-level node data comprises the IP address in the step length range of the N^th-level node of the matching entry, a hash function of the N^th-level node of the matching entry, a next-level node pointer of the N^th-level node, and a matching entry pointer of the N^th-level node; and

the hash function of the N^th-level node is a formal hash function selected by using the method for selecting a hash function according to claim 1;

the matching entry pointer of the N^th-level node points to the matching entry portion; and

N is an integer greater than or equal to 2.

14. A device for storing a routing table, comprising:

a second matching entry unit, configured to store a matching entry portion of the routing table; and

a second next-level node pointer unit, configured to store root node data and first-level node data;

wherein the root node data comprises a root node matching entry with a next-level node pointer, a hash function of a root node segment of the matching entry, a next-level node pointer of the root node segment, and a matching entry pointer of a root node;

the root node segment is a segment formed by dividing a next-level node of the root node matching entry into more than two segments;

the hash function of the root node segment is a formal hash function selected for an Internet protocol (IP) address in a step length range of a first-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the root node points to the matching entry portion;

the IP address in the step length range of the first-level node in the root node segment of the matching entry is hashed by using the hash function of the root node segment of the matching entry, and the first-level node data of the root node segment at a position pointed to by a next-level node pointer of the root node is stored by using a hash result as an offset address;

the first-level node data comprises the IP address in the step length range of the first-level node of the matching entry, a hash function of a first-level node segment of the matching entry, a next-level node pointer of the first-level node segment, and a matching entry pointer of the first-level node;

the first-level node segment is a segment formed by dividing a next-level node of the first-level node of the matching entry into more than two segments; and

the hash function of the first-level node segment is a formal hash function selected for an IP address in a step length range of a second-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1; and

the matching entry pointer of the first-level node points to the matching entry portion.

15. The device according to claim 14, wherein the second next-level node pointer unit is further configured to:

store N^th-level node data; and

hash an IP address in a step length range of an N^th-level node in an (N−

1)^th-level node segment by using a hash function of the (N−

1)^th-level node segment of the matching entry, and store the N^th-level node data of the (N−

1)^th-level node segment at a position pointed to by a next-level node pointer of the (N−

1)^th-level node segment by using a hash result as an offset address;

the N^th-level node data comprises the IP address in the step length range of the N^th-level node of the matching entry, a hash function of an N^th-level node segment of the matching entry, a next-level node pointer of the N^th-level node segment, and a matching entry pointer of the N^th-level node; and

the hash function of the N^th-level node segment is a formal hash function selected for an IP address in a step length range of a (N+1)^th-level node in the root node segment of the matching entry by using the method for selecting a hash function according to claim 1;

the matching entry pointer of the N^th-level node points to the matching entry portion; and

N is an integer greater than or equal to 2.

5. A device for selecting a hash function, comprising:

an alternative hash function unit, configured to send a current alternative hash function;

at least one hash unit, configured to receive input data to be hashed and hash the data to be hashed by using the current alternative hash function sent by the alternative hash function unit;

at least one decoder, configured decode a hash result of the hash unit; and

an accumulator, configured to accumulate decoded results of the decoder, and instruct the alternative hash function unit to replace the current alternative hash function with a next alternative hash function if a carry occurs or instruct the alternative hash function unit to select the current alternative hash function with no carry generated as a formal hash function if no carry occurs.

6. The device according to claim 5, wherein the device comprises at least two hash units and at least two decoders, the at least two hash units are one-to-one corresponding to the at least two decoders, and the at least two decoders send decoded results to the accumulator after decoding hash results of the corresponding hash units.

7. The device according to claim 5, wherein the hash unit comprises:

a router, configured to filter the data to be hashed by using a significant bit of the current alternative hash function so as to obtain the hash result.