JP2013247389A - Network apparatus and hash function selection method - Google Patents

Abstract

An object of the present invention is to shorten the selection time of an optimal hash function.
A network device of the present invention has a hash table and a hash counter table, and calculates a hash value of the entry using each of a plurality of hash functions for each entry registration / deletion request. Then, the counter value of the hash value is increased / decreased according to the success / failure of registration / deletion of the entry in the hash table, and the statistical value of the counter value in the hash counter table is obtained for each of the plurality of hash functions. A hash function is selected based on each statistic value, and the hash value of all entries registered in the hash table is calculated using the selected hash function, and the calculated hash value and entry are developed in the hash table.
[Selection] Figure 1

Description

  The present invention relates to a technique for selecting an optimum hash function from a plurality of hash functions in a network device.

  FIG. 13 shows a conventional configuration of a network device such as a router / switch. The network device includes a packet receiving unit 11, a packet processing unit 12, a packet transmission unit 13, a table 14, and a table operation unit 15.

  In the network device shown in FIG. 13, when the packet receiving unit 11 receives a packet from the line, the packet processing unit 12 searches the table 14 for the corresponding entry (entry), and the packet specified by the searched entry. Perform the process.

  In addition to the packet processing described above, the table operation unit 15 performs entry registration / deletion operations on the table 14 when an entry registration / deletion request is issued from the external server 20. Therefore, there is a possibility that the table search by the packet processing and the table operation compete with each other, and the packet processing performance and the table operation performance are affected.

  With the increase in traffic in recent years, network contention measures that require high processing performance (packet transfer performance, table operation performance) require processing contention countermeasures.

  By the way, as a table search technique, Non-Patent Document 1 discloses a linear search method and a hash (hash) method.

  As shown in the upper left of FIG. 14, in the linear search method, entries are registered in a table with a list structure. Therefore, in the case of an entry registered at the end for searching for a desired entry, it is necessary to collate with all entries (in the example on the upper left side of FIG. 14, a search is required up to six times).

  On the other hand, as shown in the lower left side of FIG. 14, in the Hash method, the Hash value by the Hash function is calculated, and the entry is registered in the Hash table for each Hash value. At this time, if the source space is small like the Source port, if the equality function (y = x) is used as the Hash function, no matter what the state of the Hash table is, multiple entries have the same Hash It does not become a value (Hash value collision), and the desired entry can be searched at once. In this case, the memory capacity required to create the hash table is about 300 KBytes at most.

  However, as shown on the right side of Fig. 14, when the original space is large, such as 5-tuple (416 bits) (10 126th space), using the equality function as the Hash function creates a Hash table. The required memory capacity is 10 126 bytes. For this reason, the equality function cannot be used as the Hash function, and the compression function is used, so that collision of Hash values occurs. As a result, in the example on the right side of FIG. 14, a maximum of four searches are required to search for a desired entry.

  However, as shown on the left side of FIG. 15, even in the case of 5-tuple, when the state of the entry group is fixed, it follows the entry group that reduces the collision of the Hash value (back calculation from the entry group). If the Hash function is used, the number of searches for the desired entry can be made close to 1 (if the optimal Hush function can be selected, there is a possibility that it can be searched once as shown in the left side of FIG. 15) .

  However, as shown on the right side of FIG. 15, when the state of the entry group changes as in the Hash table for Pinhole control, when a single Hash function is used, depending on the state of the entry group, There is a problem that Hash value collision occurs and the effect of the Hash method is reduced (in the example on the right side of FIG. 15, a maximum of four searches are required to search for a desired entry).

  As a Hash table for Pinhole control, as a collision avoidance measure when the entry group constantly fluctuates, as shown in FIG. 16, a plurality of Hash functions are prepared in advance (16 in the example of FIG. 16), There is a method for selecting an optimal Hash function corresponding to the state change of the entry group (hereinafter, this method is referred to as a multi-Hash method).

  As an algorithm for selecting the optimum Hash function of the multi-Hash method, for example, as shown in FIG. 17, when searching for input packets based on the Hash value, the average value of the number of entries that are arranged (in FIG. 17) In the example, an algorithm based on “average value” that selects the Hash function that minimizes 2) that averages 1 when the Hash value is 2, 4 when it is 30000, and 1 when it is 65535, and for each Hash value There is an algorithm based on “MAX value” that selects the Hash function that minimizes the MAX value of the number of entries (4 in the example of FIG. 17 when the Hash value is 30000).

  In the example of FIG. 16, an algorithm based on the latter “MAX value” is adopted, and when the entry group is G to L, the MAX value of the number of entries for each Hash value is the smallest when the MAX value is 1. Since it is the function 10, the Hash function 10 is selected.

Tatsuya Shinmei, 5 others, “IP packet reception processing using routing table”, IEICE Transactions 2002/8 Vol. J85-B No. 8

  However, in the multi-Hash method, as shown in FIG. 18, when selecting an optimum Hash function, if there is a request to register / delete an entry in the Hash table (step S1), the table surface of the Hash table is frozen. (Step S2), an optimal Hash function is selected and the Hash table is reconstructed (Step S3), the table surface is switched (Step S4), and the freezing of the table surface is released.

  For this reason, while the Hash table is frozen, there is a problem that it is impossible to respond to the entry registration / deletion request and a queue is generated.

  An object of the present invention is to provide a technique capable of shortening the time for freezing the Hash table by shortening the selection time of the optimum Hash function on the premise of the multi-Hash method.

The network device of the present invention
A network device that selects a hash function from a plurality of hash functions,
For each hash value, a hash table that registers entries related to the actual data of the hash value,
A hash counter table for registering a counter value set for each hash value calculated using each of the plurality of hash functions;
A table operation unit for operating the hash table and the hash counter table,
The table operating unit is
For each entry registration / deletion request, the hash value of the entry is calculated using each of the plurality of hash functions, and the hash value of the entry is determined according to the success / failure of registration / deletion of the entry in the hash table. Increase or decrease the counter value, and for each of the plurality of hash functions, obtain a statistical value of the counter value in the hash counter table,
A hash function is selected based on the statistical value of each of the plurality of hash functions, the hash value of all entries registered in the hash table is calculated using the selected hash function, and the calculated hash value and entry are calculated. In the hash table.

The hash function selection method of the present invention is:
A hash function selection method for selecting a hash function from a plurality of hash functions in a network device,
The network device is:
For each hash value, a hash table that registers entries related to the actual data of the hash value,
A hash counter table for registering a counter value set for each hash value calculated using each of the plurality of hash functions,
For each entry registration / deletion request, the hash value of the entry is calculated using each of the plurality of hash functions, and the hash value of the entry is determined according to the success / failure of registration / deletion of the entry in the hash table. Increase or decrease the counter value, and for each of the plurality of hash functions, obtain a statistical value of the counter value in the hash counter table,
A hash function is selected based on the statistical value of each of the plurality of hash functions, the hash value of all entries registered in the hash table is calculated using the selected hash function, and the calculated hash value and entry are calculated. In the hash table.

  According to the present invention, when selecting a hash function, it is only necessary to search a statistical value (average value or MAX value) of each counter value of a plurality of hash functions, so that the selection time can be shortened, and a hash table is stored. The effect that the time to freeze can be shortened is acquired.

It is a block diagram which shows the structure of the network device of this embodiment. It is a figure explaining preconditions, such as a Hash function of this embodiment. It is a figure explaining the surface structure and initial value of the Hash table of this embodiment. It is a figure explaining the state where entry is registered into the operation side of Hash table of this embodiment. It is a figure explaining the Hash counter table and initial value of this embodiment. It is a flowchart explaining the Hash counter table change process of this embodiment. It is a figure explaining the Hash counter table of this embodiment, and an initial value (in the case of an average value). It is a figure explaining the Hash counter table of this embodiment, and an initial value (in the case of MAX value). It is a flowchart explaining the Hash counter table change process (in the case of an average value) of this embodiment. It is a flowchart explaining the Hash counter table change process (in the case of MAX value) of this embodiment. It is a figure explaining Hash counter table (in the case of an average value) of this embodiment. It is a figure explaining Hash counter table (in the case of MAX value) of this embodiment. It is a block diagram which shows the structure of the conventional network device. It is a figure explaining Hash method and its subject. It is a figure explaining the subject at the time of using the compression function of Hash method. It is a figure explaining a multi-Hash system. It is a figure explaining the selection algorithm of the optimal Hash function in a multi-Hash system. It is a figure explaining the subject of a multi-Hash system.

  EMBODIMENT OF THE INVENTION Below, the form for implementing this invention is demonstrated with reference to drawings.

  As shown in FIG. 1, the network device according to the present embodiment is provided with a Hash table (hash table) 16 having a Hash function ID indicating the type of Hash function used as the table 14, and a Hash counter table (hash counter table). Table) 17 is different from the network device shown in FIG.

  The Hash table 16 is a table in which entries related to actual data of the Hash value (for example, 5-tuple actual data) are registered for each Hash value.

  The Hash counter table 17 is a table in which counter values set for each Hash value calculated using each of a plurality of Hash functions are registered.

  The table operation unit 15 also operates the Hash counter table 17 in addition to the Hash table 16.

  Details of the Hash table 16 and the Hash counter table 17 will be described later.

Hereinafter, specific processing of the network device according to the present embodiment will be described.
(1) Processing 1
In this embodiment, as shown in FIG. 2, 5-tuple (source address (L3), destination address (L3), source port (L4), destination port (L4), protocol (L3))) is 13 bytes in total. When performing pinhole control, high-speed search using the 2-byte (0 to 65535) Hash function shown below shall be performed.

Also, define 16 Hash functions with rotation bits of 0 to 15 bits (the numbers are used as function IDs as they are), and consider selecting the optimal Hash function sequentially from these 16 Hash functions. . (1) to (3) in FIG. 2 show an example of a Hash function for setting the rotation bit to 4 bits and obtaining the Hash value of the data of # 1. That is, (1) the upper 4 bits are rotated and moved to the lower order, and (2) the data of # 1 is added to this. (3) If a carry occurs in the 17th bit at (2), add 1 to it. This is repeated 13 times with the data of # 1 to # 13.
(2) Processing 2
FIG. 3 shows the surface configuration and initial values of the Hash table 16 for performing pinhole control. Hash table 16 consists of two sides, one of which is the operational side as appropriate. Initially, the zero side is the operational side.

  The table operation unit 15 that performs the table change process calculates the Hash value for the 5-tuple actual data requested for entry registration / deletion by using the Hash function embedded in the Hash function ID portion on the operation side, As shown in FIG. 4, the entry is added / deleted in a partial chain structure with the Hash value as an index. The entry is memory location information indicating the location on the memory of the actual data of the Hash value.

The packet processing unit 12 that performs the table search processing calculates the Hash value using the Hash function embedded in the Hash function ID portion of the operation side, searches the entry with the Hash value as an index, and searches for its own information. If there is a match, drop through, otherwise drop.
(3) Processing 3
FIG. 5 shows the configuration and initial values of the Hash counter table 17.

  As shown in FIG. 5, the initial values of the Hash counter table 17 are all 0.

  FIG. 6 shows a specific flow of change processing of the Hash counter table 17.

  The table operation unit 15 calculates a Hash value for each Hash function from 0 to 15 every time an entry registration / deletion request is made (step S101). At the time of entry registration request (step S102), if the entry to be registered does not exist in the Hash table 16 (No in step S105), in order to successfully register the entry (step S106), the counter value of the Hash value is obtained (step S106). S107), the counter value is incremented by 1 (step S109). On the other hand, when an entry deletion request is made (step S102), if the entry to be deleted exists in the Hash table 16 (Yes in step S103), in order to delete the entry successfully (step S104), the counter value of the Hash value is obtained. (Step S107), the counter value is decremented by -1 (Step S108).

In FIG. 6, the portion surrounded by a dotted line is a process added when entry registration / deletion is requested in this embodiment.
(4) Processing 4
As an algorithm for selecting an optimal Hash function of the multi-Hash method, for example, as shown in FIG. 17, there are an algorithm based on “average value” and an algorithm based on “MAX value”.

In the present embodiment, the above two algorithms are targeted, and in each case, the following processing is performed in addition to the processing 3.
(A) In the case of an algorithm based on “average value” Average = total number of entries / (number of Hash values whose counter value is not 0), and since all entry numbers are the same for each Hash function, “average is minimum "And" the minimum number of Hash values with a counter value of 0 "are equivalent conditions. Therefore, as shown in FIG. 7, a column “number of Hash values of 0 entry” is provided in the Hash counter table 17, and the initial value is 65536. At the time of changing the counter in process 3, pay attention to 0 → 1 and 1 → 0, and try to change the “number of 0 entry hash values”.
(B) In the case of an algorithm based on “MAX value” As shown in FIG. 8, the “MAX value” field in the Hash counter table 17 and the “MAX number” field, which is the number of Hash values in which the counter value takes the MAX value. And the initial value of “MAX number” is 0. At the time of changing the counter in process 3, it tries to change the "MAX value" without searching the counter values of all the Hash values.
(5) Processing 5
FIG. 9 shows a specific flow of the changing process of the Hash counter table 17 in the case of the algorithm based on the “average value”.

  As shown in FIG. 9, first, the table operation unit 15 performs the processing from steps S101 to S106 in FIG. 6, and then obtains the counter value of the Hash value (step S201).

  At the time of entry deletion request, if the counter value obtained in step S201 is 1 (Yes in step S202), the table operation unit 15 increments “the number of Hash values whose counter value is 0” by 1 (step S203). Thereafter, the counter value obtained in step S201 is decremented by -1 (step S204).

  On the other hand, when the entry registration request is made, if the counter value obtained in step S201 is 0 (Yes in step S205), the table operation unit 15 decrements “the number of Hash values whose counter value is 0” by −1 (step S205). After that, the counter value obtained in step S201 is incremented by 1 (step S207).

Thus, “the number of Hash values whose counter value is 0” for each Hash function is obtained. In FIG. 9, the portion surrounded by a dotted line is a process added when entry registration / deletion is requested in this embodiment.
(6) Processing 6
FIG. 10 shows a specific flow of change processing of the Hash counter table 17 in the case of the algorithm based on the “MAX value”.

  As shown in FIG. 10, first, the table operation unit 15 performs the processing from steps S101 to S106 in FIG. 6, and then obtains the counter value of the Hash value (step S301).

  At the time of entry deletion request, the table operation unit 15 compares the counter value obtained in step S301 with the MAX value (step S302), and if they match, decreases the MAX number by 1 (step S303). If the -1 decremented MAX number is 0 (Yes in step S304), the MAX value is decremented by 1, and the number of Hash values having the same counter value as the value obtained by decrementing the MAX value is decremented to be the MAX number. Thereafter, the counter value obtained in step S301 is decremented by 1 (step S306).

  On the other hand, at the time of entry registration request, the table operation unit 15 compares the counter value obtained in step S301 with the MAX value (step S307). If the counter value is equal to the value obtained by decrementing the MAX value by -1, the MAX number is incremented by 1 (step S308). If the counter value is equal to the MAX value, the MAX value is incremented by 1 and the MAX number is set to 1 ( Then, the counter value obtained in step S301 is incremented by 1 (step S310).

Thus, the “MAX value” for each Hash function is obtained. In FIG. 10, the portion surrounded by a dotted line is a process added at the time of entry registration / deletion request in this embodiment.
(7) Processing 7
The table operation unit 15 performs the above processes 2 to 6 at the time of entry registration / deletion request, and once the fixed time (for example, 100 msec) elapses, it temporarily blocks the entry registration / deletion request (the entry occurred during blocking). Buffer the registration / deletion request), and freeze the operational aspect of Hash table 16 in FIG. Meanwhile, the table operation unit 15 selects an optimum Hash function using the following algorithm, and embeds the function ID of the selected Hash function in a Hash function ID unit that is different from the operation side of FIG.
(A) Case of Algorithm Based on “Average Value” In the case of FIG. 11, the function IDs of the Hash functions having the smallest “number of Hash values of 0 entry” are the function ID1 and the function ID2.

Therefore, the table operation unit 15 selects either function ID1 or function ID2 (function ID1 in the example of FIG. 11).
(B) Case of Algorithm Based on “MAX Value” In the case of FIG. 12, the function ID of the Hash function having the smallest “MAX value” is the function ID2.

  Therefore, the table operation unit 15 selects the function ID2.

  The table operation unit 15 reads all the operational entries of the Hash table 16 using the Hash function filled above and obtains a Hash value for each entry using the Hash function filled above. Then, connect to the Hash value part on the other side with a chain structure as shown in Fig. 4 (write to the other side is overwritten, or once all entries are deleted, the above processing is performed).

  When the above processing is completed, the operation side of Hash table 16 is switched to another side, and freezing is released (processing for entry registration / deletion requests that were being blocked is restarted on the switching side).

  As described above, in this embodiment, for each entry registration / deletion request, a Hash value is calculated using each of the plurality of Hash functions, and the counter value of the Hash value is set according to the success or failure of the entry registration / deletion. Increase / decrease, and for each of the plurality of Hash functions, obtain an average value or MAX value (statistical value) of the counter values in the plurality of Hash functions.

  Then, select a Hash function based on the average value or MAX value of counter values in multiple Hash functions, use the selected Hash function to calculate the Hash value of all entries registered in Hash table 16, and calculate the calculated Hash value And expand entry to Hash table16.

  Therefore, when selecting the optimal Hash function, it is only necessary to search the average value and MAX value of each counter value of multiple Hash functions, so the selection time can be shortened and the time for freezing the Hash table 16 can be shortened. The effect that it can be obtained.

  In the present embodiment, while the selection time of the optimum Hash function is shortened by the above operation, processing is added at the time of entry registration / deletion request (in FIG. 6, FIG. 9, FIG. 10, a dotted line). Enclosed part).

  However, for example, the additional processing of FIG. 9 does not require measurement of all entries, calculation of an average, search of all counter values, and the like. Further, in the addition process of FIG. 10, it is not necessary to search all counter values. For this reason, it is possible to avoid a large increase in the processing load at the time of entry registration / deletion request.

11 Packet receiver
12 Packet processor
13 Packet transmitter
15 Table operation section
16 Hash table
17 Hash counter table

Claims (5)

A network device that selects a hash function from a plurality of hash functions,
For each hash value, a hash table that registers entries related to the actual data of the hash value,
A hash counter table for registering a counter value set for each hash value calculated using each of the plurality of hash functions;
A table operation unit for operating the hash table and the hash counter table,
The table operating unit is
For each entry registration / deletion request, the hash value of the entry is calculated using each of the plurality of hash functions, and the hash value of the entry is determined according to the success / failure of registration / deletion of the entry in the hash table. Increase or decrease the counter value, and for each of the plurality of hash functions, obtain a statistical value of the counter value in the hash counter table,
A hash function is selected based on the statistical value of each of the plurality of hash functions, the hash value of all entries registered in the hash table is calculated using the selected hash function, and the calculated hash value and entry are calculated. To the hash table,
Network equipment. The table operating unit is
When each entry registration request is made, the hash value of the entry is calculated using each of the plurality of hash functions, and when the entry is successfully registered in the hash table, the counter value of the hash value is calculated. Increase,
For each entry deletion request, the hash value of the entry is calculated using each of the plurality of hash functions, and when the entry is successfully deleted from the hash table, the counter value of the hash value is calculated. Decrease,
The network device according to claim 1. The statistical value for each of the plurality of hash functions is the number of hash values whose counter value is 0 among hash values calculated using the hash function,
The table operating unit is
In accordance with the counter value of the hash value calculated using the hash function, the number of hash values whose counter value is 0 is increased or decreased.
The network device according to claim 1 or 2. The statistical value for each of the plurality of hash functions is the number of hash values for which the counter value takes the maximum value among hash values calculated using the hash function,
The table operating unit is
The counter value of the hash value calculated using the hash function is compared with the maximum value of the counter value at that time, and the number of hash values at which the counter value takes the maximum value is increased or decreased according to the comparison result. ,
The network device according to claim 1 or 2. A hash function selection method for selecting a hash function from a plurality of hash functions in a network device,
The network device is:
For each hash value, a hash table that registers entries related to the actual data of the hash value,
A hash counter table for registering a counter value set for each hash value calculated using each of the plurality of hash functions,
For each entry registration / deletion request, the hash value of the entry is calculated using each of the plurality of hash functions, and the hash value of the entry is determined according to the success / failure of registration / deletion of the entry in the hash table. Increase or decrease the counter value, and for each of the plurality of hash functions, obtain a statistical value of the counter value in the hash counter table,
A hash function is selected based on the statistical value of each of the plurality of hash functions, the hash value of all entries registered in the hash table is calculated using the selected hash function, and the calculated hash value and entry are calculated. To the hash table,
Hash function selection method.

Images