KR100907827B1 - Forwarding Table Search Device and Method - Google Patents

Abstract

The present invention relates to an apparatus and method for searching a forwarding table. The present invention is divided into a plurality of groups, and has a plurality of forwarding entries stored in each group in order of MAC address values, and a hash key corresponding to each of the groups and the forwarding entries. A data storage unit for storing a forwarding table including a plurality of forwarding databases; After converting a MAC address input from the outside into a hash key, one search group is selected using a predetermined number of upper bits of the hash key, and the rest is performed using the remaining lower bits of the hash key except for the upper bits. A hashing unit for selecting one search forwarding entry in the search group; And outputting output port information of the search forwarding entry if the input MAC address is the same as the MAC address extracted from the search forwarding entry. If the inputted MAC address is different, the input MAC address is divided while dividing a search area within the search group. The branch is configured to include a port information output unit for outputting output port information after searching and acquiring a forwarding entry, thereby enabling a faster searching of the forwarding table.

Forwarding Tables, Dual Hashing Techniques, Split Conquest Techniques, Network Switches

Description

Look up apparatus and method of forwarding table

The present invention relates to a forwarding table retrieval apparatus and method, and more particularly, to a forwarding table retrieval apparatus and method for enabling a network switch to efficiently search and manage forwarding information for forwarding frames to a desired port among a number of ports. .

The present invention is derived from the research conducted as part of the IT new growth engine core technology development project of IT. [Task management number: 2005-S-102-02, Title: Development of carrier-class Ethernet technology].

A network switch provided in a communication network needs a forwarding search engine and an address translation mechanism to receive data from another network device and transmit the data to a desired port.

Since the performance of these network switches is greatly affected by the speed of forwarding path determination, the speed and efficiency of forwarding search engines and address translation mechanisms are important factors in determining the performance of network switches.

In general, in order to shorten a search time, a network switch includes a hash means for converting a large number of bits into an index value of a small number of bits, and uses the forwarding entry to search a forwarding table with a smaller amount of information and provide necessary information. Acquire.

FIG. 1 is a diagram illustrating an operation of a forwarding table search apparatus according to an exemplary embodiment. The forwarding table search apparatus of FIG. 1 selects one forwarding entry fwd_ent using a forwarding table fwd_table and its MAC. Compare the address with the entered MAC address. In the same case, output port information of the currently selected forwarding entry fwd_ent is read. In other cases, output port information is obtained by sequentially comparing with the MAC address of the next forwarding entry fwd_ent.

However, the forwarding entries at this time are not sorted according to a certain principle, and are simply arranged in the order in which each forwarding entry is stored.

Therefore, this sequential retrieval method takes too much time to determine the forwarding path because information must be read and compared for all forwarding entries (fwd_ent) in the forwarding table (fwd_table).

In order to make up for this drawback, US Patent No. 6,266,705 proposed a method of classifying a number of forwarding entries into several pages using a dual hashing technique as shown in FIG. 2.

In the method of FIG. 2, a page to be searched is first selected using 3 bits of MSB (Most Significant Bits) of a hash key, and the forwarding entries within the page are sequentially searched.

Accordingly, the search method of FIG. 2 is much shorter than the conventional sequential search method. However, even at this time, there is a disadvantage in that the search speed decreases in proportion to the number of forwarding entries existing in the page.

As described above, the conventional search method takes a relatively long time, but at this time, the search speed decreases in proportion to the number of forwarding entries existing in the corresponding page.

According to an aspect of the present invention, as a means for solving the above problems, divided into a plurality of groups, corresponding to a plurality of forwarding entries stored in the order of MAC address values in each group, corresponding to each of the group and the forwarding entry A data storage unit for storing a forwarding table including a plurality of forwarding databases having hash keys; After converting a MAC address input from the outside into a hash key, one search group is selected using a predetermined number of upper bits of the hash key, and the rest is performed using the remaining lower bits of the hash key except for the upper bits. A hashing unit for selecting one search forwarding entry in the search group; And outputting output port information of the search forwarding entry if the input MAC address is the same as the MAC address extracted from the search forwarding entry. If the inputted MAC address is different, the input MAC address is divided while dividing a search area within the search group. The present invention proposes a forwarding table search apparatus including a port information output unit for outputting output port information after searching and obtaining a forwarding entry.

And the port information output unit outputs output port information of the search forwarding entry if the input MAC address is the same as the extracted MAC address; An inequality comparator for dividing a search region in the search group to obtain a new search forwarding entry if the input MAC address is different from the extracted MAC address; And a search position moving unit moving to the new search forwarding entry.

The inequality comparator sets the extracted MAC address as an index initial value (index_init) when the input MAC address is greater than the extracted MAC address, and sets the extracted MAC address as an index final value (index_final) when the input MAC address is larger than the extracted MAC address. After setting, the new search forwarding entry having an index (index_cur) calculated according to the expression "index_init + (index_final-index_init) / 2" is searched.

And each of the plurality of forwarding databases includes a forwarding database ID; And a hash table indexed by a hash key corresponding to one group and one forwarding entry, each of the plurality of forwarding entries including a MAC address, information indicating whether information is valid, output port information, virtual LAN ID, and next. And information about a pointer indicating a location of a forwarding entry.

According to another aspect of the present invention as a means for solving the above problems, divided into a plurality of groups, a plurality of forwarding entries are stored in each group arranged in the order of MAC address values, and in each of the groups and forwarding entries A configuration step of constructing a plurality of forwarding databases having corresponding hash keys; When the MAC address is input from the outside, the input MAC address is converted into a hash key, and then one search group is selected using a predetermined number of upper bits of the hash key, and the hash key except the upper bits is selected. A selection step of selecting one search forwarding entry in the search group using the remaining lower bits; A first output step of extracting a MAC address from the search forwarding entry and extracting and outputting output port information of the search forwarding entry if the extracted MAC address is the same as the input MAC address; And outputting output port information after newly searching for a forwarding entry having the input MAC address while dividing a search area in the search group if the extracted MAC address is different from the input MAC address. We propose a forwarding information retrieval method including a.

And if the input MAC address is larger than the extracted MAC address, setting the extracted MAC address as an index initial value (index_init), and when the outputting MAC address is smaller, the extracted MAC address as an index final value (index_final). Setting step); a reselection step of newly selecting a forwarding entry having an index calculated according to the expression "index_init + (index_final-index_init) / 2"; A comparison step of outputting output port information of the newly selected forwarding entry if the MAC address of the newly selected forwarding entry is the same as the input MAC address, and reentering the setting step if different; And if the newly selected forwarding entry is invalid, adding a forwarding entry having the input MAC address or deleting the newly selected forwarding entry.

And the sorting step may include selecting whether to add a forwarding entry having the input MAC address or to delete the newly selected forwarding entry; When adding a forwarding entry having the input MAC address, the index final value is set as a modification index, and an index value of a forwarding entry having an index value larger than the modification index is increased by one unit, and then the index is added to the final index position. Adding a forwarding entry with the entered MAC address; And setting the newly selected forwarding entry forwarding entry index final value as the modification index, deleting the newly selected forwarding entry, and decreasing the index value of the forwarding entry having an index value larger than the modification index by one unit. It is characterized by including.

As described above, the apparatus and method for searching a forwarding table according to the present invention classifies the forwarding entries into a plurality of groups, sorts them in the order of MAC addresses in the group, and then uses the dual hashing technique and the partitioning conquer technique to view the required forwarding entries. Make it quick to search. This improves the performance of the network switch using the same.

In addition, in the present invention, even if the forwarding entry is added or deleted, the sorting order of the forwarding entries is continuously maintained, thereby effectively managing the forwarding table.

3 is a diagram illustrating a configuration of an apparatus for searching a forwarding table according to an embodiment of the present invention.

Referring to FIG. 3, the apparatus for searching a forwarding table of the present invention includes a data storage unit 410, a hashing unit 420, a port information output unit 430, and a forwarding entry alignment unit 440.

The data storage unit 410 stores a forwarding table fwd_table, and the forwarding table fwd_table has two data structures, a forwarding database fwd_db and a forwarding entry fwd_ent. The plurality of forwarding entries (fwd_ent) are divided into a plurality of groups based on some bits of the hash key, and are sequentially stored in the order of MAC address values for each group.

At this time, the forwarding table (fwd_table) is indexed by a forwarding database ID (FID), and stores a pointer (pfwd_db) indicating the location of the forwarding database (fwd_db) corresponding to each FID.

Each forwarding database (fwd_db) has a data structure as shown in FIG. 4, and contains information such as a FID and a hash table indexed with a corresponding hash key mapped to point to a corresponding group and forwarding entry. Each forwarding entry (fwd_ent) has a data structure as shown in FIG. 5, and the MAC address (MCA address) of the corresponding forwarding entry, valid information indicating whether it is valid, and output port information (pointer to set output L2). information such as a port ID, a VLAN ID, and a pointer to the next entry indicating a location of a next forwarding entry.

The hashing unit 420 converts the MAC address in the frame input from the outside into a hash key having a small number of bits, and then selects one search group from among a plurality of groups by using a dual hashing method. Select one search forwarding entry within the group.

That is, the hashing unit 420 selects a search group using some bits of the hash key, and selects a search forwarding entry using the remaining bits.

For example, if a plurality of forwarding entries (fwd_ent) are classified into eight groups, and each forwarding table (fwd_ent) is configured to store 64 forwarding entries (fwd_ent) in each group, the hashing unit 420 of the present invention As shown in FIG. 6, one group is selected using MSB 3 bits of a hash key, and one forwarding entry is selected within the selected group using the remaining 6 bits.

The port information output unit 430 outputs the output port information if the MAC address of the forwarding entry selected by the hashing unit 420 is the same as the input MAC address. Otherwise, the divide-and-conquer technique is used. After searching and acquiring the new forwarding entry having the input MAC address by dividing the search area in the search group by 1/2 by using, the output port information thereof is output.

To this end, the port information output unit 430 outputs an output port by comparing the input MAC address with the MAC address of the search forwarding entry, and which one is larger, or divides the search area by 1/2 to search for a new search forwarding entry. Equations and inequality comparators 431 and 432 for searching for and a search position shifter 433 for moving the search position to a new search forwarding entry according to the operation results of the equations and inequality comparators 431 and 432.

The forwarding entry sorter 440 adds or deletes the forwarding entries in the order of MAC addresses. For example, when adding a forwarding entry, set the index final value (index_final) as the modified index (index_modified), and then increase the index value of the forwarding entry having an index value larger than the modified index (index_modified) by one unit. Let's do it. On the other hand, when deleting a forwarding entry, set the index of the forwarding entry to be deleted as the modified index (index_modified), delete the corresponding forwarding entry, and set the index value of the forwarding entry having an index value larger than the modified index (index_modified). Decrease by one unit.

That is, when a forwarding entry is added, the storage position of the forwarding entry having an index larger than the added forwarding entry is moved backward by one position, and when the forwarding entry is deleted, the forwarding has an index larger than the index of the deleted forwarding entry. Moves the storage location of the entry forward one position.

7 is a flowchart illustrating a method of retrieving forwarding information according to an embodiment of the present invention.

After converting the MAC address in the frame input from the outside into a hash key (S101), using the hash key according to the dual hashing technique, the search group and the search forwarding entry located in the search group are selected. (S102).

After extracting the MAC address stored in the search forwarding entry (S103), the MAC addresses of the input frames are compared and compared (S104).

As a result of the comparison in S104, if identical, the output port information stored in the search forwarding entry is extracted and notified, and the operation ends (S105, S016).

On the other hand, if it is different, check whether the entered MAC address is smaller than the MAC address of the first forwarding entry in the search group (S107), and if it is small, move to the previous group having the group ID value smaller by one unit and re-enter S103. (S108).

On the other hand, if it is large, it is checked whether the input MAC address is larger than the MAC address of the last forwarding entry in the search group (S109), and if it is large, it moves to the next group having a group ID value one unit larger and re-enters S103 (S110). ).

If the input MAC address is smaller than the MAC address of the last forwarding entry in the search group, the input MAC address is compared with the extracted MAC address through step S103 (S111).

As a result of the comparison, when the input MAC address is larger than the extracted MAC address, the extracted MAC address is set as an index initial value (index_init) (S112), and when the MAC address is small, the extracted MAC address is set as an index final value (index_final) ( S113).

At the time of initialization, the index initial value index_init is set to the MAC address having the smallest index value in the search group, and the index final value index_final is set to the MAC address having the largest index value in the search group. However, it is reset to the extracted MAC address through S113.

The current index index_cur is calculated according to the expression "index_init + (index_final-index_init) / 2", and a forwarding entry having the calculated current index index_cur is selected (S114).

That is, the present invention selects a new forwarding entry while dividing the search area in the search group by 1/2 while passing through S114.

For example, if a 10th forwarding entry has a MAC address input as shown in FIG. 8 but a fourth forwarding entry is arbitrarily selected, the present invention divides the search area to select a 12th forwarding entry and an 8th forwarding entry. Then (S1, S2), the 10th forwarding entry is selected next (S3). This allows you to select the desired forwarding entry with a smaller number of searches.

Subsequently, check whether the valid bit of the forwarding entry selected by S114 is "1" (S115). If the valid bit is "1", confirm that the currently selected forwarding entry is valid and re-enter S103. do.

On the other hand, if the valid bit is "0", it confirms that the currently selected forwarding entry is invalid. The operation is terminated after adding a forwarding entry having the input MAC address or performing a forwarding entry alignment process to delete the currently selected forwarding entry (S116).

9 is a flowchart illustrating a forwarding entry sorting method according to an embodiment of the present invention, which is provided so that forwarding entries are stored in the forwarding table fwd_table while being sorted in the order of MAC address values.

First, when a forwarding entry alignment operation is requested and activated, it is checked whether the requested operation is a forwarding entry addition operation or a deletion operation (S201).

In the case of adding a forwarding entry, a modified index (index_modified) is set as an index final value (index_final) (S202), and a forwarding entry having an index value larger than the modified index (index_modified) is moved back by one digit (S203), A new forwarding entry is added at the index final value index_final (S204).

On the contrary, when the forwarding entry existing in the forwarding table (fwd_table) is deleted, the index of the forwarding entry to be deleted is stored in the modified index (index_modified) (S205), the corresponding forwarding entry is deleted (S206), and the modified index (index_modified) A forwarding entry having a larger index value moves forward by one digit (S207).

Thus, even if a forwarding entry stored in the forwarding table fwd_table is added or deleted, the sort order in the forwarding table fwd_table according to the MAC address is maintained.

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and it is common in the art that various substitutions, modifications, and changes can be made without departing from the technical spirit of the present invention. It will be apparent to those skilled in the art.

1 is a view illustrating an operation of a forwarding table search apparatus according to a conventional example;

2 is a diagram illustrating an operation of a forwarding table search apparatus according to another conventional example;

3 is a block diagram of an apparatus for searching a forwarding table according to an embodiment of the present invention;

4 shows a data structure of the forwarding database of FIG.

FIG. 5 shows a data structure of the forwarding entry of FIG. 3; FIG.

6 is a conceptual view illustrating an operation of a hashing unit of FIG. 3;

7 is a flowchart for explaining a method of retrieving forwarding information according to an embodiment of the present invention;

8 is a diagram illustrating an example of a forwarding entry retrieval method using the partitioning conquest method of the present invention; and

9 is a flowchart illustrating a forwarding entry alignment method according to an embodiment of the present invention.

Claims (11)

Data storage for storing a forwarding table, which is divided into a plurality of groups, and includes a plurality of forwarding entries, each of which is sorted and stored in the order of MAC address values, and a forwarding database having hash keys corresponding to the groups and the forwarding entries. part; After converting a MAC address input from the outside into a hash key, one search group is selected using a predetermined number of upper bits of the hash key, and the rest is performed using the remaining lower bits of the hash key except for the upper bits. A hashing unit for selecting one search forwarding entry in the search group; And If the input MAC address is the same as the MAC address extracted from the search forwarding entry, the output port information of the search forwarding entry is output. If the input MAC address is different, the search MAC address is divided in the search group and has the input MAC address. And a port information output unit for outputting output port information after retrieving and acquiring a forwarding entry. The method of claim 1, wherein the port information output unit An equation comparator for outputting output port information of the search forwarding entry if the input MAC address is the same as the extracted MAC address; An inequality comparator for dividing a search region in the search group to obtain a new search forwarding entry if the input MAC address is different from the extracted MAC address; And And a search position moving unit for moving to the new search forwarding entry. The method of claim 2, wherein the inequality comparator If the input MAC address is larger than the extracted MAC address, the extracted MAC address is set as an index initial value (index_init). If the input MAC address is smaller, the extracted MAC address is set as an index final value (index_final). and searching for the new search forwarding entry having an index (index_cur) calculated according to the expression index_init + (index_final-index_init) / 2 ". The method of claim 1, When a new forwarding entry having the input MAC address is newly added, the index value of the forwarding entry having a larger index value than the newly added forwarding entry is increased by one unit, and any one of the plurality of forwarding entries is specified. And a forwarding entry sorting unit which decreases the index value of the forwarding entry having a larger index value than the deleted forwarding entry by one unit. The method of claim 1, wherein each of the plurality of forwarding databases is Forwarding database ID; And And a hash table indexed by hash keys corresponding to one group and one forwarding entry. The method of claim 1, wherein each of the plurality of forwarding entries And information about a MAC address, information indicating whether information is valid, output port information, virtual LAN ID, and a pointer indicating a location of a next forwarding entry. Configuring a plurality of forwarding databases, each of which is divided into a plurality of groups and has a plurality of forwarding entries arranged and stored in the order of MAC address values, and a hash key corresponding to each of the groups and the forwarding entries; When the MAC address is input from the outside, the input MAC address is converted into a hash key, and then one search group is selected using a predetermined number of upper bits of the hash key, and the hash key except the upper bits is selected. A selection step of selecting one search forwarding entry in the search group using the remaining lower bits; A first output step of extracting a MAC address from the search forwarding entry and extracting and outputting output port information of the search forwarding entry if the extracted MAC address is the same as the input MAC address; And If the extracted MAC address is different from the input MAC address, a second output step of dividing a search area in the search group, newly searching for a forwarding entry having the input MAC address, and then outputting output port information; Including forwarding information retrieval method. 8. The method of claim 7, wherein the second output step is Setting the extracted MAC address as an index initial value (index_init) when the input MAC address is larger than the extracted MAC address, and setting the extracted MAC address as an index final value (index_final) when the input MAC address is smaller than the extracted MAC address; a reselection step of newly selecting a forwarding entry having an index calculated according to the expression "index_init + (index_final-index_init) / 2"; And And if the MAC address of the newly selected forwarding entry is the same as the input MAC address, outputting output port information of the newly selected forwarding entry, and if different, forwarding information retrieval to the setting step. Way. The method of claim 8, wherein the second output step And if the newly selected forwarding entry is invalid, adding a forwarding entry having the input MAC address or deleting the newly selected forwarding entry. The method of claim 9, wherein the sorting step Selecting whether to add a forwarding entry having the input MAC address or to delete the newly selected forwarding entry; When adding a forwarding entry having the input MAC address, the index final value is set as a modification index, and an index value of a forwarding entry having an index value larger than the modification index is increased by one unit, and then the index is added to the final index position. Adding a forwarding entry with the entered MAC address; And In the case of deleting the newly selected forwarding entry, after setting the final index value as the modification index, the newly selected forwarding entry is deleted, and the index value of the forwarding entry having an index value larger than the modification index is decreased by one unit. And forwarding information retrieval method. The method of claim 8, wherein the second output step If the extracted MAC address is smaller than the MAC address of the first forwarding entry in the search group, it moves to a group having a unit ID value smaller by one unit. If the extracted MAC address is larger than the MAC address of the last forwarding entry in the search group, the group ID is one unit larger. And moving to each group having a value and then reentering the first output step.

Images