JP3910451B2 - Transmission equipment - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a transmission apparatus, and more particularly to a transmission apparatus that performs packet distribution by performing load distribution of packets flowing on a transmission path.
[0002]
[Prior art]
In recent years, due to the rapid spread of the Internet, the network topology has become complicated and the amount of information has increased remarkably, and there has been a demand for high reliability by increasing the bandwidth of the network and the redundant configuration of the transmission path. Therefore, the connection form between nodes in the network is often connected by multilink or mesh.
[0003]
In such a situation, in order to efficiently use the network bandwidth and prevent packet delay and loss, it is necessary to distribute the load on the transmission path, and usually load balancing control using hash (Hash) calculation Is widely practiced. The hash operation is an operation method for generating a fixed-length pseudorandom number from a given original (data), and the generated pseudorandom value is called a hash value.
[0004]
FIG. 7 is a diagram showing an overview of conventional load balancing control. The table 200 shown in the figure divides the number from 0 to 15 into four to form sections k1 to k4, and each of the sections k1 to k4 has the output route numbers # 1 to # 4. Are listed.
[0005]
As conventional load balancing control, first, hash information is obtained by hashing information in the header of the received packet 100. Then, the table 200 in which each output route number is described for each of a plurality of sections is searched for which section the calculated hash value is included in, and a path to which the packet 100 is to be output is determined. decide.
[0006]
For example, if the hash value of the packet 100 is 5, since it corresponds to the section k2 of 4-7, the packet 100 is output from the route of number # 2. By performing such control, the load on each transmission path can be distributed.
[0007]
[Problems to be solved by the invention]
However, in the conventional load distribution control as described above, the table 200 must prepare as many sections as the number of output routes, and compare each section from the section k1 to determine which section includes the calculated hash value. I must. For this reason, when the number of output routes increases, the hardware configuration becomes complicated, and the output route cannot be determined at high speed.
[0008]
The present invention has been made in view of these points, and an object of the present invention is to provide a transmission apparatus that performs load distribution control efficiently and determines an output route at high speed.
[0009]
[Means for Solving the Problems]
In the present invention, in order to solve the above-described problem, a load distribution group that searches for a load distribution group based on a hash parameter of a packet in a transmission apparatus 10 that performs switching based on the destination address of the packet as shown in FIG. A load distribution ratio setting table T1 including a search unit 11, a load distribution group, and a load distribution ratio including a specific bit corresponding to a boundary value between output routes and represented by a bit arrangement; and a load distribution ratio setting table A load distribution ratio search unit 12 that searches for a load distribution ratio corresponding to the searched load distribution group using T1, and a hash that calculates a hash value corresponding to the input packet by performing a hash operation based on the hash parameter The number of specific bits existing between the calculation unit 13 and the hash value counted from the end of the searched load distribution ratio Thus, the route selection number determination unit 14 that determines the route selection number, and the output route information determination unit that determines the output route information of the packet based on the retrieved load distribution group and the route selection number 15, a transmission apparatus 10 is provided.
[0010]
Here, the load distribution group search unit 11 searches for a load distribution group based on the hash parameter of the packet. The load distribution ratio setting table T1 includes a load distribution group and a load distribution ratio represented by a bit array including specific bits corresponding to boundary values between output routes. The load distribution ratio search unit 12 searches for a load distribution ratio corresponding to the searched load distribution group using the load distribution ratio setting table T1. The hash calculator 13 performs a hash calculation based on the hash parameter, and calculates a hash value corresponding to the input packet. The route selection number determination unit 14 determines the route selection number based on the number of specific bits existing from the end of the searched load distribution ratio to the point where the hash value is counted. The output route information determination unit 15 determines the output route information of the packet based on the retrieved load distribution group and the route selection number.
[0011]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a principle diagram of a transmission apparatus according to the present invention. The transmission device 10 is a device that performs packet transmission by performing switching based on the destination address of the packet, and can be applied to, for example, an IP router arranged in a multilink connection or mesh connection network. .
[0012]
The load distribution group search unit 11 searches for a load distribution group based on the hash parameter (DA (destination address) included in the header) of the packet. Specifically, the load distribution group search unit 11 has an internal table in which the DA value and the load distribution group value correspond to each other, and the load distribution group is obtained from the internal table.
[0013]
The load distribution ratio search unit 12 uses a load distribution ratio setting table T1 including a load distribution group and a load distribution ratio represented by a bit array including specific bits corresponding to boundary values between output routes. Then, the load distribution ratio corresponding to the retrieved load distribution group is extracted.
[0014]
The hash calculation unit 13 performs a hash calculation based on the hash parameters (DA and SA (source address) included in the header) to calculate one hash value corresponding to one input packet.
[0015]
The route selection number determination unit 14 counts the hash value from the end of the retrieved load distribution ratio, and determines the route selection number based on the number of specific bits existing up to that point. For example, in the figure, when counting from the least significant bit of the load distribution ratio to the hash value, there is one specific bit (Δ mark), so the route selection number is determined to be 1.
[0016]
The output route information determination unit 15 determines the output route information (such as the number of the physical port to which the packet is output) of the packet based on the retrieved load distribution group and the route selection number.
[0017]
Next, the load distribution ratio setting table T1 will be described. FIG. 2 is a diagram showing the load distribution ratio setting table T1. The load distribution ratio corresponding to the load distribution group is registered in the load distribution ratio setting table T1.
[0018]
For example, for the load distribution group 3, the load distribution ratio is “0101000100000000”. The bit width of the load distribution ratio corresponds to the distribution granularity. In this case, since the distribution granularity is 16, the bit width of the load distribution ratio is 16 bits. The dispersion particle size is the fineness of the dispersion ratio. When the dispersion particle size is N, load distribution can be performed in units of 1 / N.
[0019]
Next, the hash calculation unit 13 will be described. FIG. 3 is a diagram for explaining hash value calculation. When performing the hash calculation, the hash calculation unit 13 obtains a hash value using the DA and SA of the received packet as hash parameters.
[0020]
In addition, the bit width when the distribution granularity is expressed in binary is a bit width necessary as a hash value. For example, if the distribution granularity is 16, the hash value needs to be a value from 0 to 15. If this is converted to a binary number, it becomes “0000” to “1111”, and the hash value requires 4 bits. .
[0021]
Next, setting of the load distribution ratio registered in the load distribution ratio setting table T1 will be described. FIG. 4 is a diagram illustrating an example of setting the load distribution ratio. The load distribution ratio of the route selection numbers 0, 1, 2, and 3 is 4: 2: 1: 1, and the dispersion granularity is 16. Then, the ratio to the route selection number in this case is 8: 4: 2: 2.
[0022]
Therefore, the branching ratio of the route selection numbers 0 to 3 according to the load distribution ratio is 8/16 for the route selection number 0, 4/16 for the route selection number 1, 2/16 for the route selection number 2, The route selection number 3 becomes 2/16, and when this is converted into a boundary value, the boundary value of the route selection numbers 0 and 1 is 8, and the boundary value of the route selection numbers 1 and 2 is 12 ( = 8 + 4), the boundary value between the route selection numbers 2 and 3 is 14 (= 8 + 4 + 2).
[0023]
Therefore, the load distribution ratio can be set by setting the specific bit to “1” and the bit corresponding to the boundary value between the routes. The least significant bit is from the 0th bit and the 8th and 12th bits. By setting “1” in the 14th bit, the load distribution ratio becomes “0101000100000000”.
[0024]
In this example, since the number of output routes is four, there are only four route selection numbers, so route selection numbers 0 to 3 are used, but routes that can be set with one load distribution ratio. The number of selection numbers (the number of dispersion paths) is determined by the dispersion granularity. That is, if the dispersion particle size is 16, it is possible to select a route from 1 to 16.
[0025]
Next, the route selection number determination process will be described. FIG. 5 is a diagram showing a route selection number determination process. When counting from the least significant bit of the load distribution ratio obtained from the load distribution ratio setting table T1 to the hash value obtained by the hash calculator 13, the route selection number is determined by how many "1" are present.
[0026]
Here, since the load distribution ratio of the packet is “0101000100000000” and the hash value is “1100” (= 12), the least significant bit of the load distribution ratio is the 0th bit, and “1” is counted up to the 12th bit. Since there are two, the route selection number is 2.
[0027]
Next, the output route information determination unit 15 will be described. FIG. 6 shows an output route setting table. The output route information determination unit 15 has an output route setting table T2 as an internal table.
[0028]
The output route information determination unit 15 determines the output route setting table T2 based on the load distribution group searched by the load distribution group search unit 11 and the route selection number determined by the route selection number determination unit 14. To determine the output route information of the packet. In the case of the figure, when the route selection number is 2 in the load balancing group 0, output route information # 2 is determined.
[0029]
As described above, in the transmission device 10 of the present invention, the load distribution ratio for each load distribution group is set in a bit arrangement, the boundary value is represented by the bit position, and the specific bit existing in the location counted up to the hash value The route selection number is determined based on the number, and then the output route information is determined. This eliminates the need for a comparison circuit between the hash value and the boundary value, so that the circuit scale can be reduced and the output route can be determined at high speed.
[0030]
In addition, when the application apparatus of the transmission apparatus 10 of the present invention is considered, it can be applied to an apparatus that performs MPLS (Multi-Protocol Label Switching) label switching. MPLS is a technique for realizing packet transfer by directly connecting at layer 2 without using an upper layer.
[0031]
By applying the present invention to such an apparatus so that the traffic volume of a plurality of LSP (Label Switched Path) set between the edges is constant, load balancing of TE (Traffic Engineering) Control can be performed at high speed.
[0032]
(Supplementary note 1) In a transmission device that performs switching based on the destination address of a packet,
A load distribution group search unit for searching for a load distribution group based on the hash parameter of the packet;
A load distribution ratio setting table including the load distribution group, and a load distribution ratio including a specific bit corresponding to a boundary value between output routes and represented by a bit arrangement;
A load distribution ratio search unit that searches for the load distribution ratio corresponding to the searched load distribution group using the load distribution ratio setting table;
A hash calculation unit that calculates a hash value corresponding to the packet by performing a hash calculation based on the hash parameter;
A route selection number determination unit for determining a route selection number according to the number of the specific bits existing from the end of the searched load distribution ratio to the count of the hash value;
An output route information determination unit that determines output route information of a packet based on the retrieved load distribution group and the route selection number;
A transmission apparatus comprising:
[0033]
(Additional remark 2) The said load distribution ratio setting table registers the said load distribution ratio with the bit width corresponding to the value of a dispersion | distribution granularity, The transmission apparatus of Additional remark 1 characterized by the above-mentioned.
(Supplementary note 3) The transmission apparatus according to supplementary note 1, wherein the hash calculation unit sets a bit width when the value of the distribution granularity is expressed in binary to a bit width that requires the hash value.
[0034]
(Supplementary Note 4) In a transmission apparatus that performs MPLS label switching,
A load distribution group search unit for searching for a load distribution group based on a hash parameter of the packet;
A load distribution ratio setting table including the load distribution group, and a load distribution ratio including a specific bit corresponding to a boundary value between output routes and represented by a bit arrangement;
A load distribution ratio search unit that searches for the load distribution ratio corresponding to the searched load distribution group using the load distribution ratio setting table;
A hash calculation unit that calculates a hash value corresponding to the packet by performing a hash calculation based on the hash parameter;
A route selection number determination unit for determining a route selection number according to the number of the specific bits existing from the end of the searched load distribution ratio to the count of the hash value;
An output route information determination unit that determines LSP information to output the packet based on the retrieved load distribution group and the route selection number;
A transmission apparatus comprising:
[0035]
(Additional remark 5) The said load distribution ratio setting table registers the said load distribution ratio with the bit width corresponding to the value of a dispersion | distribution granularity, The transmission apparatus of Additional remark 4 characterized by the above-mentioned.
(Supplementary note 6) The transmission device according to supplementary note 4, wherein the hash calculation unit sets a bit width when a value of a dispersion granularity is expressed in binary to a bit width that requires the hash value.
[0036]
【The invention's effect】
As described above, the transmission apparatus according to the present invention is based on the load distribution ratio and hash value obtained from the hash parameter of the input packet, and the identification existing from the end of the retrieved load distribution ratio to the point where the hash value is counted. The route selection number is determined by the number of bits. And it was set as the structure which determines the output route information of a packet from a load distribution group and a route selection number. As a result, the output route determination process for load distribution can be performed efficiently and at high speed.
[Brief description of the drawings]
FIG. 1 is a principle diagram of a transmission apparatus according to the present invention.
FIG. 2 is a diagram showing a load distribution ratio setting table.
FIG. 3 is a diagram for explaining calculation of a hash value.
FIG. 4 is a diagram illustrating a setting example of a load distribution ratio.
FIG. 5 is a diagram showing a route selection number determination process.
FIG. 6 is a diagram showing an output route setting table.
FIG. 7 is a diagram showing an overview of conventional load balancing control.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 10 Transmission apparatus 11 Load distribution group search part 12 Load distribution ratio search part 13 Hash calculating part 14 Route selection number determination part 15 Output route information determination part T1 Load distribution ratio setting table

Claims (5)

In a transmission device that performs switching based on the destination address of a packet,
A load distribution group search unit for searching for a load distribution group based on the hash parameter of the packet;
A load distribution ratio setting table including the load distribution group, and a load distribution ratio including a specific bit corresponding to a boundary value between output routes and represented by a bit arrangement;
A load distribution ratio search unit that searches for the load distribution ratio corresponding to the searched load distribution group using the load distribution ratio setting table;
A hash calculation unit that calculates a hash value corresponding to the packet by performing a hash calculation based on the hash parameter;
A route selection number determination unit for determining a route selection number according to the number of the specific bits existing from the end of the searched load distribution ratio to the count of the hash value;
An output route information determination unit that determines output route information of a packet based on the retrieved load distribution group and the route selection number;
A transmission apparatus comprising: The transmission apparatus according to claim 1, wherein the load distribution ratio setting table registers the load distribution ratio having a bit width corresponding to a value of a distribution granularity. The transmission apparatus according to claim 1, wherein the hash calculation unit sets a bit width when the value of the distribution granularity is expressed in a binary number as a bit width that requires the hash value. In a transmission device that performs MPLS label switching,
A load distribution group search unit for searching for a load distribution group based on a hash parameter of the packet;
A load distribution ratio setting table including the load distribution group, and a load distribution ratio including a specific bit corresponding to a boundary value between output routes and represented by a bit arrangement;
A load distribution ratio search unit that searches for the load distribution ratio corresponding to the searched load distribution group using the load distribution ratio setting table;
A hash calculation unit that calculates a hash value corresponding to the packet by performing a hash calculation based on the hash parameter;
A route selection number determination unit for determining a route selection number according to the number of the specific bits existing from the end of the searched load distribution ratio to the count of the hash value;
An output route information determination unit that determines LSP information to output the packet based on the retrieved load distribution group and the route selection number;
A transmission apparatus comprising: 5. The transmission apparatus according to claim 4, wherein the load distribution ratio setting table registers the load distribution ratio having a bit width corresponding to a value of a distribution granularity.

Images