JP7750423B2 - Packet transfer control device, packet transfer control method, distribution simulation device, and program - Google Patents

Description

The present invention relates to a packet forwarding control device, a packet forwarding control method, a distribution simulation device, and a program that realizes distributed control of packets.

In datacenters, packet forwarding architectures, for example, employ a leaf-and-spine architecture to build a redundant configuration for ensuring security and load balancing. The leaf switch selects one of multiple spine switches to forward the data packet. The choice of which spine switch to select depends on the load balancing algorithm, and existing technologies are known to distribute loads on a per-flow or per-packet basis.

In flow-based distribution, packets belonging to a specific service with the same source IP address and destination IP address are grouped together as a flow (flow-by-flow) and distributed. By dynamically selecting a path based on bandwidth information at the time of distribution, it is possible to prevent bandwidth imbalances (see non-patent document 1). On the other hand, by distributing on a packet-by-packet basis, it is possible to prevent bandwidth imbalances even more effectively than with flow-by-flow distribution (see non-patent document 2).

Tat Wing Chim, et al., “Traffic Distribution over Equal-Cost-Multi-Paths,” IEEE Communications Society 2004 Jiawei Huang,et al.,“QDAPS: Queueing Delay Aware Packet Spraying for Load Balancing in Data Center,”2018 IEEE DOI 10.1109/ICNP.2018.000017

In ECMP (Equal Cost Multi Path) and link aggregation, which are used in per-flow L3 (Layer 3) routing, load balancing is achieved by calculating hash values of calculation parameters, such as the 5-tuple obtained for each flow. However, with this type of flow-based distribution based on traditional static hashing, bandwidth imbalances can occur when a specific flow has a large bandwidth or when multi-stage hashing is used. Furthermore, when multi-stage hashing is used, using the same load balancing method (hash calculation algorithm) across multiple connections can result in the same value being calculated on subsequent routers, resulting in poor load balancing.

In addition, when distributing on a per-flow basis, there is technology that dynamically selects paths based on bandwidth information at the time of distribution, but in that case, additional processing (state management) is required, such as maintaining information on the path selected for each flow.
On the other hand, load balancing on a packet basis has problems such as packets arriving in the wrong order and the impact of a failure spreading to all flows, while cell-based balancing has the problem of having to introduce a new transfer method that is different from flow-based or packet-based methods.

The present invention was made in consideration of these points, and its objective is to prevent bandwidth imbalances in packet load balancing control.

The packet forwarding control device of the present invention is a packet forwarding control device that controls switching to each link in packet forwarding processing, and includes a flow information acquisition unit that acquires packet collection information including information collected from the packets to identify the flow, and flow information including information on the bandwidth used by the flow; a hash key selection unit that selects one of pre-set hash key candidates, which is information constructed using the packet collection information; a hash calculation algorithm selection unit that selects one of pre-set hash calculation algorithm candidates; and a simulation unit that uses the selected hash key candidate to calculate the link to which the flow is to be assigned, for all combinations of the hash key candidate and the hash calculation algorithm candidate. The system is characterized by comprising: an execution unit; a distribution algorithm determination unit that calculates the bandwidth usage of each link using information on the bandwidth of the flow from information on links to which the flow is to be distributed according to the hash key candidate and the hash calculation algorithm candidate obtained as a result of the simulation, selects the pair of hash key candidate and hash calculation algorithm candidate that has the most variance in the bandwidth usage of each link based on a predetermined algorithm determination logic, and outputs information on the selected pair of hash key candidate and hash calculation algorithm candidate; and a distribution algorithm switching controller that acquires information on the selected pair of hash key candidate and hash calculation algorithm candidate and sends it to a distribution processing function that distributes the packets to each link, thereby switching the setting of the link to which the packets are to be distributed.

The packet forwarding control device of the present invention can suppress the occurrence of bandwidth imbalances in packet load balancing control.

1 is a block diagram showing a configuration of a packet transfer control device according to an embodiment of the present invention; 10 is a flowchart showing the flow of processing executed by the packet transfer control device according to the embodiment. FIG. 4 is a diagram illustrating an example of a data configuration of flow information according to the embodiment. FIG. 10 is a diagram illustrating an example of a data configuration of simulation result information according to the present embodiment. FIG. 10 is a diagram showing another example of the data configuration of the simulation result information according to the embodiment. FIG. 10 is a block diagram showing the configuration of a load balancing simulation device according to a modified example of the present embodiment. FIG. 2 is a hardware configuration diagram illustrating an example of a computer that realizes the functions of the packet transfer control device according to the present embodiment.

Next, an embodiment of the present invention (hereinafter referred to as "the present embodiment") will be described.
The packet transfer control device 1 according to this embodiment acquires current flow information, simulates the load balancing situation while changing the hash key and hash calculation algorithm, selects the hash key and hash calculation algorithm that produce the optimal simulation result (allocation result), and switches the transfer process. Furthermore, the packet transfer control device 1 acquires current flow information at predetermined time intervals and repeatedly simulates the load balancing situation, thereby dynamically switching the transfer process in response to fluctuations in the bandwidth of each flow. This allows the packet transfer control device 1 to suppress the occurrence of bandwidth imbalances in the distributed control on a per-flow basis.

FIG. 1 is a block diagram showing the configuration of a packet transfer control device 1 according to this embodiment.
The packet transfer control device 1 is realized by a computer including a control unit, an input/output unit, and a storage unit (not shown). The packet transfer control device 1 also has a distribution processing function configured by an ASIC 100 (Application Specific Integrated Circuit) or the like, and distributes packets to each flow.

The input/output unit inputs and outputs information between a communication device that is an input source of a packet and multiple communication devices that are output destinations of the packets. The packet forwarding control device 1 can distribute packets to multiple links (link #0, link #1, ...) provided between the packet forwarding control device 1 and the multiple communication devices that are output destinations of the packets, and based on the simulation results described below, selects a link (link #0, link #1, ...) through which each flow will flow so as to better distribute the load, that is, to suppress the occurrence of bandwidth imbalance, and outputs the packets.
This input/output unit is composed of a communication interface that transmits and receives information via a communication line, and an input/output interface that inputs and outputs information between an input device such as a keyboard and an output device such as a monitor (not shown).

The storage unit is configured with a hard disk, flash memory, RAM (Random Access Memory), and the like.
This storage unit temporarily stores programs for executing the functions of the control unit and information necessary for the processing of the control unit. This storage unit also stores information on the links that accommodate each flow, which is the result of simulating a combination of hash keys and hash calculation algorithms (flow allocation result information in the simulation result information 300 in Figures 4 and 5, which will be described later).

The control unit is responsible for all processing performed by the packet forwarding control device 1, and as shown in Figure 1, it comprises a traffic information acquisition unit 11, an allocation simulation unit 12, and an allocation algorithm switching controller 13.

The traffic information acquisition unit 11 acquires traffic information from packets received from other communication devices at predetermined time intervals.
The traffic information includes 5-tuple information (source IP address, source port number, destination IP address, destination port number, protocol number) and traffic volume information.

The distribution simulation unit 12 acquires current flow information, simulates the load distribution status while changing the hash key and hash calculation algorithm, and calculates the link to which each flow is to be distributed.The distribution simulation unit 12 then selects the optimal simulation result from the simulation results, that is, the hash key and hash calculation algorithm that will result in distribution of flows with minimal imbalance in the bandwidth of each link.
The distribution simulation unit 12 includes a flow information acquisition unit 121 , a hash key selection unit 122 , a hash calculation algorithm selection unit 123 , a simulation execution unit 124 , and a distribution algorithm determination unit 125 .

The flow information acquisition unit 121 acquires flow information for each flow based on the traffic information acquired by the traffic information acquisition unit 11. The flow information acquired by the flow information acquisition unit 121 includes, for example, five-tuple information, such as source IP address (Src IP), source port number (Src port), destination IP address (Dst IP), destination port number (Dst port), and protocol number, which are preset information, as well as information on the bandwidth (width) used for each flow. In this embodiment, the preset information among the five-tuple information, such as information identifying a flow collected from packets, is referred to as "packet collection information." The bandwidth (width) used for each flow may be acquired by the flow information acquisition unit 121, for example, by calculation based on traffic volume information acquired by the traffic information acquisition unit 11, or the traffic information acquisition unit 11 may calculate the bandwidth (width) used for each flow.

The hash key selection unit 122 selects one of preset hash key candidates. For example, the hash key selection unit 122 selects two-tuple information of a source IP address and a destination IP address, or selects three-tuple information of a source IP address, a destination IP address, and a source port number.
Which set of information from the collected packet information, such as five tuples, is to be adopted as a hash key candidate is set in advance in the hash key selection unit 122 .

The hash calculation algorithm selection unit 123 selects one hash calculation algorithm candidate from among preset hash calculation algorithm candidates.
Any hash calculation algorithm (e.g., MD5, SHA-1, SHA-2, SHA-3) can be set as a candidate hash calculation algorithm in advance. Also, a more detailed algorithm may be set as a candidate hash calculation algorithm. For example, "calculate the remainder of the 15th bit after the XOR (exclusive OR) operation" or "calculate the remainder of the 16th bit after the XOR operation" that are performed in hash calculations can be set.

The simulation execution unit 124 calculates (simulates) the link to which the flow is to be allocated by performing a hash calculation using the hash key candidate selected by the hash key selection unit 122 and the hash calculation algorithm candidate selected by the hash calculation algorithm selection unit 123. The simulation execution unit 124 executes simulations for all combinations of the set hash key candidate and the set hash calculation algorithm candidate.
The simulation execution unit 124 then stores the flow allocation result information 300, which is the result of the simulation, in the storage unit (see FIGS. 4 and 5, which will be described later).

The allocation algorithm determination unit 125 uses the flow allocation result information 300, which is the simulation result of the simulation execution unit 124, to select the combination of "hash key" and "hash calculation algorithm" that best distributes the bandwidth usage of each link based on a predetermined algorithm determination logic.

This predetermined algorithm decision logic is, for example, the following logic.
<Algorithm determination logic "1"> Among the links calculated for each pair of hash key candidate and hash calculation algorithm candidate, the pair of hash key candidate and hash calculation algorithm candidate that has calculated the link with the smallest bandwidth utilization is selected. In other words, the pair of "hash key" and "hash calculation algorithm" that has the smallest bandwidth utilization of the link with the most concentrated traffic is selected.
<Algorithm Determination Logic "2"> The variance of the bandwidth used for each link is calculated, and the pair of "hash key" and "hash calculation algorithm" with the lowest variance value is selected.

Then, the distribution algorithm determination unit 125 determines whether or not to perform a change process (distribution algorithm change process) regarding link distribution for the selected pair of "hash key" and "hash calculation algorithm" based on a predetermined change process determination logic.
The predetermined change process determination logic is, for example, a logic that executes the change process when the condition "the bandwidth usage of each link is equal to or less than a predetermined threshold" is satisfied, and does not execute the change process when this condition is not satisfied. Alternatively, the predetermined change process determination logic may be a logic that executes the change process when the condition "the variance of the bandwidth usage of each link is equal to or less than a predetermined threshold" is satisfied, and does not execute the change process when this condition is not satisfied.

If the allocation algorithm determination unit 125 determines that the conditions based on the specified change processing determination logic are met, it outputs information on the selected pair of "hash key" and "hash calculation algorithm" to the allocation algorithm switching controller 13 as a new allocation algorithm.

The distribution algorithm switching controller 13 sends switching information for the hash key and hash calculation algorithm to the distribution processing function (here, ASIC 100) based on the acquired combination of "hash key" and "hash calculation algorithm" information (distribution algorithm).

The hash switching function unit 101 of the ASIC 100 switches the sorting algorithm based on the acquired "hash key" and "hash calculation algorithm" information. As a result, the ASIC 100 sorts and transfers the received packets to the newly set sorting destination links (links #0, #1, ...).
It should be noted that this allocation processing function is not limited to the ASIC 100, and may be, for example, an FPGA (Field Programmable Gate Array) or the like.
Also, in Figure 1, the distribution processing function (switch) such as ASIC 100 is provided inside the packet forwarding control device 1, but the packet forwarding control device 1 may also be provided externally as a device in a separate housing from the distribution processing function (switch) such as ASIC 100.

<Processing of the packet transfer control device>
Next, the flow of processing executed by the packet transfer control device 1 will be described.
FIG. 2 is a flowchart showing the flow of processing executed by the packet transfer control device 1 according to this embodiment.

First, the traffic information acquisition unit 11 of the packet forwarding control device 1 determines whether a predetermined time interval has elapsed (step S1). If the predetermined time has not elapsed (step S1 → No), the process returns to step S1. On the other hand, if the predetermined time has elapsed (step S1 → Yes), the process proceeds to step S2.

In step S2, the traffic information acquisition unit 11 acquires traffic information from packets received from other communication devices. This traffic information includes information such as a preset 5-tuple, as well as information on traffic volume.

Next, the distribution simulation unit 12 acquires the current flow information, simulates the load distribution status while changing the hash key and hash calculation algorithm, and calculates the link to which each flow will be distributed.The distribution simulation unit 12 then determines the combination of "hash key" and "hash calculation algorithm" that distributes traffic the most. Specifically, it performs the following process.

First, in step S2, the flow information acquisition unit 121 of the distribution simulation unit 12 acquires flow information 200 for each flow based on the traffic information acquired by the traffic information acquisition unit 11 (step S3).

FIG. 3 is a diagram showing an example of the data structure of the flow information 200 acquired by the flow information acquisition unit 121. As shown in FIG.
As shown in Fig. 3, the flow information 200 stores traffic information (packet collection information) and bandwidth information, which are set in advance from information such as a 5-tuple, in association with the flow ID (#1, #2) of each flow. Fig. 3 shows an example in which the source IP address (Src IP), destination IP address (Dst IP), and source port number (Src port) of the 5-tuple information are set as packet collection information. Note that this 5-tuple packet collection information, such as the 5-tuple, that identifies this flow is used as a "hash key."

Next, the hash key selection unit 112 of the distribution simulation unit 12 selects one hash key candidate from among preset candidates (step S4).
Here, for example, it is assumed that the following two hash key candidates are set in advance.
Hash key candidate #1: <Src IP/Dst IP> (source IP address and destination IP address)
Hash key candidate #2: <Src IP/Dst IP/Src port> (source IP address, destination IP address, and source port number)
Here, the following description will be given assuming that the hash key selection unit 112 selects hash key candidate #1.

Next, the hash calculation algorithm selection unit 123 of the distribution simulation unit 12 selects one from among the hash calculation algorithm candidates set in advance (step S5).
Here, for example, it is assumed that one hash calculation algorithm candidate shown below is set.
Hash calculation algorithm candidate #1: "XOR operation followed by modulo calculation of the 15th bit"
Here, the hash calculation algorithm selection unit 123 selects hash calculation algorithm candidate #1.

Next, the simulation execution unit 124 of the distribution simulation unit 12 performs a simulation (hash calculation simulation) to calculate the link to which the flow will be distributed by performing a hash calculation using the hash key candidate selected by the hash key selection unit 122 in step S4 and the hash calculation algorithm candidate selected by the hash calculation algorithm selection unit 123 in step S5 (step S6).
The simulation execution unit 124 then stores the simulation results as simulation result information 300 in a storage unit (not shown).

FIG. 4 is a diagram showing an example of the data structure of the simulation result information 300 generated by the simulation execution unit 124. As shown in FIG.
As shown in FIG. 4, the simulation result information 300 stores flow allocation result information in association with hash key candidates and hash calculation algorithm candidates.
The first line (reference numeral 301) of the simulation result information 300 in FIG. 4 indicates that the following flow allocation result information was obtained as a simulation result when the hash key candidate was "#1: <Src IP/Dst IP>" and the hash calculation algorithm candidate was "#1": "XOR operation followed by modulo calculation of the 15th bit."
Flow #1: Link #0
Flow #2: Link #0
This flow allocation result information indicates that the simulation results show that flow #1 is allocated to link #0 and flow #2 is allocated to link #0.

Next, the simulation execution unit 124 determines whether any hash calculation algorithm candidates remain (step S7). If there are any unselected hash calculation algorithm candidates remaining (step S7 → Yes), the simulation execution unit 124 returns to step S5 and continues processing. On the other hand, if there are no unselected hash calculation algorithm candidates remaining (step S7 → No), the simulation execution unit 124 proceeds to the next step S8.
At this point, since there are no hash calculation algorithm candidates remaining, the process proceeds to step S8.

Next, the simulation execution unit 124 determines whether any hash key candidates remain (step S8). If there are any unselected hash key candidates remaining (step S8 → Yes), the simulation execution unit 124 returns to step S4 and continues processing. On the other hand, if there are no unselected hash key candidates remaining (step S8 → No), the simulation execution unit 124 proceeds to the next step S9.

In this case, hash key candidate #2 remains, so the process returns to step S4, and steps S4 to S8 are executed. As a result, as shown in the second line (reference numeral 302) of the simulation result information 300 in Fig. 4, the following flow allocation result information is obtained as the simulation result when the hash key candidate is "#2: <Src IP/Dst IP/Src port>" and the hash calculation algorithm candidate is "#1": "XOR operation followed by modulo calculation of the 15th bit."
Flow #1: Link #0
Flow #2: Link #1
This flow allocation result information indicates that the simulation results show that flow #1 is allocated to link #0 and flow #2 is allocated to link #1.

Next, in step S8, if there are no hash key candidates remaining (step S8 → No), the distribution algorithm determination unit 125 of the distribution simulation unit 12 refers to the flow distribution result information in the simulation result information 400 (Figure 4) and, based on a predetermined algorithm determination logic, selects the combination of "hash key" and "hash calculation algorithm" that best distributes the bandwidth usage of each link (step S9).

Here, it is assumed that the allocation algorithm determination unit 125 has set the predetermined algorithm determination logic to the above-mentioned <algorithm determination logic "1">, which selects the pair of "hash key" and "hash calculation algorithm" with the smallest bandwidth usage on the link with the most concentrated traffic.

In this case, in the flow allocation result information of the simulation indicated by reference numeral 301 in Figure 4, since flow #1 and flow #2 are accommodated on the same link #0, the total bandwidth usage of link #0 is 100 + 100 = 200 (Mbps) based on the bandwidth (width) shown in Figure 3. Furthermore, the bandwidth (width) of link #1 is 0 (Mbps). Therefore, the bandwidth usage of the link with the most concentrated traffic in the simulation indicated by reference numeral 301 is link #0, 200 (Mbps).

In contrast, in the flow allocation result information of the simulation indicated by reference numeral 302 in Figure 4, flow #1 is accommodated in link #0 and flow #2 is accommodated in link #1, so based on the bandwidth shown in Figure 3, the bandwidth used for flow #1 is 100 (Mbps) and the bandwidth used for flow #2 is also 100 (Mbps). Therefore, the bandwidth used for the link with the most concentrated traffic in the simulation indicated by reference numeral 302 is "100 (Mbps)" for links #0 and #1.

That is, in the simulation indicated by the symbol 301, the distribution simulation unit 12 assigns flow #1 and flow #2 to the same link (symbol a in FIG. 5), while in the simulation indicated by the symbol 302, flow #1 and flow #2 are distributed to multiple links (symbol b in FIG. 5).
As a result, the allocation algorithm determination unit 125 selects the combination of the simulation "hash key" and "hash calculation algorithm" indicated by the symbol 302, which results in the smallest bandwidth usage (here, "100 (Mbps)") for the link with the most concentrated traffic, i.e., the link with the most dispersed traffic.

FIG. 5 is a diagram showing another example of the data structure of the simulation result information 300 generated by the simulation execution unit 124. In FIG.
Here, one hash key candidate and two hash calculation algorithm candidates are set in advance, and the simulation execution unit 124 executes the hash calculation simulation in step S6, and the results are shown.

The first line (reference numeral 303) of the simulation result information 300 in FIG. 5 indicates that the following flow allocation result information was obtained as a simulation result when the hash key candidate was "#1: <Src IP/Dst IP/Src port>" and the hash calculation algorithm candidate was "#1": "XOR operation followed by modulo calculation of the 16th bit."
Flow #1: Link #0
Flow #2: Link #0
This flow allocation result information indicates that flow #1 is allocated to link #0 and flow #2 is allocated to link #0, that is, the simulation result shows that flow #1 and flow #2 are allocated to the same link (symbol c in FIG. 5).

Furthermore, the second line (reference numeral 304) of the simulation result information 300 in FIG. 5 indicates that the following flow allocation result information was obtained as a simulation result when the hash key candidate was "#1: <Src IP/Dst IP/Src port>" and the hash calculation algorithm candidate was "#2": "XOR operation followed by modulo calculation of the 15th bit."
Flow #1: Link #0
Flow #2: Link #1
This flow allocation result information indicates that flow #1 is allocated to link #0 and flow #2 is allocated to link #1, that is, the simulation result shows that flow is distributed to a plurality of links (symbol d in FIG. 5).

In this way, the distribution simulation unit 12 performs hash calculation simulation for all combinations of pre-set hash key candidates and distribution algorithm candidates, and selects the combination of "hash key" and "hash calculation algorithm" that best distributes the bandwidth usage of each link.

Next, the allocation algorithm determination unit 125 determines whether or not to change the allocation algorithm based on a predetermined change process determination logic (step S10).
Here, an example will be described in which the predetermined change process determination logic is, for example, "execute change process if the condition that the bandwidth usage of each link is equal to or less than a predetermined threshold is satisfied." In this case, the allocation algorithm determination unit 125 determines whether the bandwidth usage of flow #1 (100 Mbps) and flow #2 (100 Mbps) is equal to or less than a predetermined threshold, based on the flow allocation result information of the combination of the "hash key" and "hash calculation algorithm" of the simulation selected in step S9, for example, denoted by reference numeral 302 in FIG.

If the predetermined threshold is set to 200 Mbps, for example, the allocation algorithm determination unit 125 determines that the condition based on the predetermined change process determination logic is met (step S10 → Yes), and proceeds to the next step S11. At this time, the allocation algorithm determination unit 125 outputs information about the selected pair of "hash key" and "hash calculation algorithm" to the allocation algorithm switching controller 13.
On the other hand, if the specified threshold is set to 80 Mbps, for example, the distribution algorithm determination unit 125 determines that the conditions based on the specified change processing judgment logic are not met (step S10 → No), and returns to step S1 without performing the distribution algorithm change processing.

In step S11, the sorting algorithm switching controller 13 transmits hash key and hash calculation algorithm switching information to the sorting processing function (here, ASIC 100) based on the acquired information (sorting algorithm) of the pair of "hash key" and "hash calculation algorithm." As a result, the sorting algorithm is changed by the hash switching function unit 101 of ASIC 100.

The packet forwarding control device 1 repeats this load balancing simulation at predetermined time intervals, dynamically switching forwarding processes in response to fluctuations in bandwidth for each flow. Therefore, the packet forwarding control device 1 can suppress the occurrence of bandwidth imbalances in distributed control on a per-flow basis.

<Modification of this embodiment>
As a modification of this embodiment, a device (traffic allocation simulation device 2) having only the functions of the traffic allocation simulation unit 12 shown in FIG. 1 will be described.
The distribution simulation device 2 shown in Fig. 6 has the functions of the flow information acquisition unit 121, hash key selection unit 112, hash calculation algorithm selection unit 123, simulation execution unit 124, and distribution algorithm determination unit 125 shown in Fig. 1. As a result, by inputting any flow information, the distribution simulation device 2 simulates and outputs information on links to which each flow is to be distributed.

Normally, when ECMP is used, it is difficult to determine which link each flow passes through. In contrast, by using the distribution simulation device 2, if a failure occurs, for example, it is possible to quickly determine which link the path in question passes through based on flow information, etc. This makes it possible to respond more quickly after a failure occurs.

<Hardware configuration>
The packet transfer control device 1 according to this embodiment is realized by a computer 900 having a configuration as shown in FIG. 7, for example.
7 is a hardware configuration diagram showing an example of a computer 900 that realizes the functions of the packet transfer control device 1 according to this embodiment. The computer 900 has a CPU (Central Processing Unit) 901, a ROM (Read Only Memory) 902, a RAM 903, an HDD (Hard Disk Drive) 904, an input/output I/F (Interface) 905, a communication I/F 906, and a media I/F 907.

The CPU 901 operates based on programs stored in the ROM 902 or HDD 904, and controls each functional unit shown in Figure 1. The ROM 902 stores a boot program executed by the CPU 901 when the computer 900 is started, as well as programs related to the computer 900's hardware.

The CPU 901 controls input devices 910 such as a mouse and keyboard, and output devices 911 such as a display and printer, via the input/output I/F 905. The CPU 901 acquires data from the input device 910 via the input/output I/F 905, and outputs generated data to the output device 911. If the packet transfer control device 1 has a distribution processing function such as an ASIC 100 (see Figure 1), it sends and receives information via the input/output I/F 905.

HDD 904 stores programs executed by CPU 901 and data used by the programs. Communication I/F 906 receives data from other devices via a communication network (e.g., NW (Network) 920) and outputs the data to CPU 901, and also transmits data generated by CPU 901 to other devices via the communication network.

The media I/F 907 reads the program or data stored on the recording medium 912 and outputs it to the CPU 901 via the RAM 903. The CPU 901 loads the program related to the target processing from the recording medium 912 onto the RAM 903 via the media I/F 907, and executes the loaded program. The recording medium 912 is an optical recording medium such as a DVD (Digital Versatile Disc) or a PD (Phase Change Rewritable Disk), a magneto-optical recording medium such as an MO (Magneto Optical Disk), a magnetic recording medium, a semiconductor memory, etc.

For example, when the computer 900 functions as the packet transfer control device 1 according to this embodiment, the CPU 901 of the computer 900 executes a program loaded onto the RAM 903 to realize the functions of the packet transfer control device 1. In addition, the HDD 904 stores data in the RAM 903. The CPU 901 reads and executes a program related to the target processing from the recording medium 912. Additionally, the CPU 901 may read a program related to the target processing from another device via the communication network (NW 920).

<Effects>
The effects of the packet transfer control device 1 and the like according to the present invention will be described below.
The packet transfer control device according to the present invention is a packet transfer control device 1 that controls switching to each link in packet transfer processing, and includes a flow information acquisition unit 121 that acquires packet collection information including information collected from packets to identify a flow and flow information including information on a bandwidth used by the flow, a hash key selection unit 122 that selects one of preset hash key candidates, which is information configured using the packet collection information, a hash calculation algorithm selection unit 123 that selects one of preset hash calculation algorithm candidates, and a simulation that uses the selected hash key candidate to calculate a link to which a flow is to be allocated, for all combinations of hash key candidates and hash calculation algorithm candidates. The system is characterized by comprising: a simulation execution unit 124; an allocation algorithm determination unit 125 that calculates the bandwidth usage of each link using flow bandwidth information from information on links to which flows are to be allocated according to the hash key candidates and hash calculation algorithm candidates obtained as a result of the simulation, selects a pair of hash key candidates and hash calculation algorithm candidates that has the most variance in the bandwidth usage of each link based on a predetermined algorithm determination logic, and outputs information on the selected pair of hash key candidates and hash calculation algorithm candidates; and an allocation algorithm switching controller 13 that acquires information on the selected pair of hash key candidates and hash calculation algorithm candidates and sends it to an allocation processing function that allocates packets to each link, thereby switching the setting of the link to which the packets are to be allocated.

In this way, the packet transfer control device 1 executes a simulation to calculate the links to which flows will be allocated for all combinations of hash key candidates and hash calculation algorithm candidates, and can select the combination of hash key and hash calculation algorithm that best distributes the bandwidth usage of each link. This enables the packet transfer control device 1 to prevent imbalances in the bandwidth of each link.
Furthermore, by repeating this simulation at predetermined time intervals, the packet transfer control device 1 can achieve optimal load distribution of flows in response to fluctuations in the bandwidth of each flow.

Furthermore, in the packet forwarding control device 1, the specified algorithm determination logic is characterized by selecting a pair of hash key candidate and hash calculation algorithm candidate that has calculated the link with the smallest bandwidth utilization from among the links calculated for each pair of hash key candidate and hash calculation algorithm candidate.

By using such algorithm determination logic, the packet forwarding control device 1 can distribute the bandwidth usage of each link and reliably prevent bandwidth imbalances.

Furthermore, in the packet forwarding control device 1, the specified algorithm determination logic is characterized by calculating the variance of the bandwidth usage of each link for each pair of hash key candidate and hash calculation algorithm candidate, and selecting the pair of hash key candidate and hash calculation algorithm candidate with the lowest variance value.

By using such algorithm determination logic, the packet forwarding control device 1 can distribute the bandwidth usage of each link and reliably prevent bandwidth imbalances.

The distribution simulation device 2 according to the present invention is characterized by comprising: a flow information acquisition unit 121 that acquires packet collection information including information collected from packets that identifies the flow, and flow information including information on the bandwidth used by the flow; a hash key selection unit 122 that selects one of a set of pre-defined hash key candidates, which is information constructed using the packet collection information; a hash calculation algorithm selection unit 123 that selects one of a set of pre-defined hash calculation algorithm candidates; a simulation execution unit 124 that uses the selected hash key candidate to perform a simulation for all combinations of hash key candidate and hash calculation algorithm candidate to calculate the link to which the flow is to be distributed using the selected hash calculation algorithm candidate; and a distribution algorithm determination unit 125 that uses flow bandwidth information to calculate the bandwidth usage of each link from the information on the links to which the flow is to be distributed according to the hash key candidate and hash calculation algorithm candidate obtained as a result of the simulation, selects a combination of hash key candidate and hash calculation algorithm candidate that has the most diversified bandwidth usage for each link based on a predetermined algorithm determination logic, and outputs information on the selected combination of hash key candidate and hash calculation algorithm candidate.

In this way, the distribution simulation device 2 can quickly determine which link the path in question passes through based on flow information, etc., when a failure occurs, for example.

The present invention is not limited to the embodiments described above, and many modifications are possible within the technical spirit of the present invention by those skilled in the art.

REFERENCE SIGNS LIST 1 Packet transfer control device 2 Distribution simulation device 11 Traffic information acquisition unit 12 Distribution simulation unit 13 Distribution algorithm switching controller 100 ASIC (distribution processing function)
REFERENCE SIGNS LIST 101 Hash switching function unit 121 Flow information acquisition unit 122 Hash key selection unit 123 Hash calculation algorithm selection unit 124 Simulation execution unit 125 Allocation algorithm determination unit 200 Flow information 300 Simulation result information

Claims (6)

A packet transfer control device that controls switching to each link in packet transfer processing,
a flow information acquisition unit that acquires packet collection information including information collected from the packets and identifying a flow, and flow information including information on a bandwidth used by the flow;
a hash key selection unit that selects one hash key from among preset hash key candidates, the hash key candidates being information configured using the packet collection information;
a hash calculation algorithm selection unit that selects one from preset hash calculation algorithm candidates;
a simulation execution unit that uses the selected hash key candidate to execute a simulation for calculating a link to which the flow is to be allocated using the selected hash calculation algorithm candidate, for all combinations of the hash key candidate and the hash calculation algorithm candidate;
an allocation algorithm determination unit that calculates the bandwidth usage of each link from information on links to which the flows are allocated according to the hash key candidates and the hash calculation algorithm candidates, obtained as a result of the simulation, using information on the bandwidth of the flows, selects a pair of the hash key candidate and the hash calculation algorithm candidate that has the most variance in the bandwidth usage of each link based on a predetermined algorithm determination logic, and outputs information on the selected pair of the hash key candidate and the hash calculation algorithm candidate;
an allocation algorithm switching controller that acquires information on the selected pair of hash key candidate and hash calculation algorithm candidate, and transmits the information to an allocation processing function that allocates the packets to each link, thereby switching the setting of the link to which the packets are allocated;
A packet transfer control device comprising: 2. The packet forwarding control device according to claim 1, wherein the predetermined algorithm determination logic is logic for selecting the pair of the hash key candidate and the hash calculation algorithm candidate that has calculated the link with the smallest bandwidth utilization among the links with the largest bandwidth utilization calculated for each pair of the hash key candidate and the hash calculation algorithm candidate. 2. The packet forwarding control device according to claim 1, wherein the predetermined algorithm determination logic is logic that calculates a variance of the bandwidth usage of each link for each pair of the hash key candidate and the hash calculation algorithm candidate, and selects the pair of the hash key candidate and the hash calculation algorithm candidate with the lowest variance value. A packet transfer control method for a packet transfer control device that controls switching to each link in packet transfer processing, comprising:
The packet transfer control device
acquiring packet collection information including information collected from the packets and identifying a flow, and flow information including information on a bandwidth used by the flow;
selecting one of preset hash key candidates, the hash key candidates being information configured using the packet collection information;
selecting one of preset hash calculation algorithm candidates;
a step of performing a simulation for calculating a link to which the flow is to be allocated using the selected hash key candidate and the selected hash calculation algorithm candidate, for all combinations of the hash key candidate and the hash calculation algorithm candidate;
a step of calculating the bandwidth usage of each link from information on links to which the flow is allocated according to the hash key candidate and the hash calculation algorithm candidate obtained as a result of the simulation, using information on the bandwidth of the flow, selecting the pair of the hash key candidate and the hash calculation algorithm candidate that has the most variance in the bandwidth usage of each link based on a predetermined algorithm determination logic, and outputting information on the selected pair of the hash key candidate and the hash calculation algorithm candidate;
acquiring information on the selected pair of the hash key candidate and the hash calculation algorithm candidate, and transmitting the information to a distribution processing function that distributes the packet to each link, thereby switching the setting of the link to which the packet is to be distributed;
A packet transfer control method comprising: a flow information acquisition unit that acquires packet collection information including information collected from packets and identifying a flow, and flow information including information on a bandwidth used by the flow;
a hash key selection unit that selects one hash key from among preset hash key candidates, the hash key candidates being information configured using the packet collection information;
a hash calculation algorithm selection unit that selects one from preset hash calculation algorithm candidates;
a simulation execution unit that uses the selected hash key candidate to execute a simulation for calculating a link to which the flow is to be allocated using the selected hash calculation algorithm candidate, for all combinations of the hash key candidate and the hash calculation algorithm candidate;
an allocation algorithm determination unit that calculates the bandwidth usage of each link from information on links to which the flows are allocated according to the hash key candidates and the hash calculation algorithm candidates, obtained as a result of the simulation, using information on the bandwidth of the flows, selects a pair of the hash key candidate and the hash calculation algorithm candidate that has the most variance in the bandwidth usage of each link based on a predetermined algorithm determination logic, and outputs information on the selected pair of the hash key candidate and the hash calculation algorithm candidate;
A distribution simulation device comprising: A program for causing a computer to function as a packet forwarding control device described in any one of claims 1 to 3.