WO2018120814A1

WO2018120814A1 - Random load balancing method and apparatus, computer storage medium

Info

Publication number: WO2018120814A1
Application number: PCT/CN2017/094397
Authority: WO
Inventors: 常艳蕊
Original assignee: 深圳市中兴微电子技术有限公司
Priority date: 2016-12-26
Filing date: 2017-07-25
Publication date: 2018-07-05
Also published as: CN108243113A; CN108243113B

Abstract

Disclosed in the embodiments of the present invention is a random load balancing method, comprising: during a round of n load balances, using a two-in-one selector and a unique pseudo-random number on all the planes to process M selectable output links of the current load balance in order to obtain an effective output link of the current load balance; n and M are positive integers; masking the link number of the effective output link of the current load balancing in a mask code table of the M selectable link numbers of the current load balance, and determining M-1 selectable output links of the next load balance; continuing until all of the link numbers in the selectable link mask code table are masked; restoring the masked link numbers in the selectable link mask code table, and performing the next round of load balancing. Also disclosed in the embodiments of the present invention are a random load balancing apparatus and a computer storage medium.

Description

Random load balancing method and device, computer storage medium

Cross-reference to related applications

The present application is filed on the basis of the Chinese Patent Application No. PCT Application No.

Technical field

The present invention relates to the field of large-capacity data exchange, and in particular, to a method and apparatus for random load balancing, and a computer storage medium.

Background technique

In a switching system, the switching network implements data exchange between switching access devices. With the development of the application, the networking of the switching chip becomes complicated, the capacity becomes larger, and the number of Serdes links also increases, and large-capacity switching chips such as 128×128, 168×168, 192×192, 256×256 appear. In order to meet the requirements of the chip's main frequency, the switch chip is made in a multi-plane form.

In multi-level switching, each switching device has multiple routing planes. When data exchange is performed, different planes need to perform load balancing at the same time; data is transmitted in units of cells in the switching system, and different inputs of the same switching device. The link receives the cells sent to different access devices; if multiple output links can reach the destination access device, according to the traditional load balancing mode, FIG. 1 is a schematic diagram of a conventional multi-plane load balancing method, as shown in FIG. It is assumed that the number of links of the switch chip is 96×96, and plane 0, plane 1, plane 2, and plane 3 can all reach the access device through links 0 to 23, and the four planes simultaneously perform load balancing. The output link is 0. Then, all the cells sent to the access device are sent to link 0, causing link 0 to be blocked, and the link bandwidth of 1 to 23 is wasted; this will lead to multi-plane resonance and cannot be guaranteed. Cell equalization of multiple routing planes is available at all On the arriving link, the data stream arriving at a certain device is always transmitted in one or several links, thereby causing the cell to be congested in a switching device, causing the switching capability to decrease, and at the same time causing the data stream. Local congestion and waste of bandwidth.

Summary of the invention

In view of this, embodiments of the present invention are directed to a method and apparatus for random load balancing, and a computer storage medium, so that all cells of multiple routing planes can be uniformly allocated on reachable links to ensure the entire network. The purpose of traffic balancing is to improve bandwidth utilization and system performance.

In order to achieve the above object, the technical solution of the present invention is achieved as follows:

An embodiment of the present invention provides a method for random load balancing, where the method includes:

In a round of n-time load balancing, the M-selectable output links of the current sub-load balancing are processed by using a two-choice selector and a unique pseudo-random number in all planes to obtain a current sub-load balancing. Effective output link; the n, M are positive integers;

The link number of the valid output link of the current current load balancing is masked in the M selectable link number mask tables of the current secondary load balancing, and the M-1 of the next load balancing is determined. Selectable output link;

Until all link numbers in the selectable link number mask table are masked;

The masked link number in the selectable link number mask table is restored for the next round of load balancing.

In the above solution, the M selectable output links of the current sub-load balancing are processed by using a second-selector and a unique pseudo-random number in all planes to obtain an effective output of the current sub-load balancing. Links, including:

Performing k-level output link grouping on the M selectable output links in the current time and in a plane by using a second-selector and a unique one of the pseudo-random numbers in all planes Describe a valid output link for current secondary load balancing; the k is a positive integer.

In the above solution, the k-level output chain is performed on the M selectable output links by using a second-selector and a unique pseudo-random number in all planes in the current time and a plane. The grouping of the roads obtains the effective output link of the current current load balancing, including:

Performing, in the current time and in a plane, two pairs of k-level adjacent output links for the M selectable output links by using a two-select selector and a unique one of the pseudo-random numbers in all planes Grouping

If the number m of the output links of the kth stage is an even number, the m output links of the kth stage are grouped into two groups of adjacent output links, and the selectors of the second selection and the unique ones in all planes are utilized. a pseudo-random number obtains m/2 output links of the k+1th level until the m/2=1, obtaining an effective output link corresponding to the m/2=1; the m is smaller than Equal to M;

If the number m of output links of the kth stage is an odd number, the m-1 output links of the kth stage are grouped into two groups of adjacent output links, and the selectors are selected and the planes are used in all planes. The only one pseudo-random number obtains (m-1)/2 output links of the k+1th stage and the remaining 1 output link of the kth stage until the m=3, and (m-1) /2+1=2 output links, which are determined in the (m-1)/2+1=2 output links by using a binary selector and a unique pseudo random number in a random load Corresponding one effective output link; the m is less than or equal to M.

In the above solution, the M-selectable output link of the current sub-load balancing is processed by using a second-selector and a unique pseudo-random number in all planes, including:

Generating a selection signal according to the unique one of the pseudo-random numbers in all planes; the only one of the all planes is a binary number, and the bit width of the only one of the all planes is the selection The number of signals;

Selecting two selectable output links corresponding to the two inputs of the two selectors according to the signal bits corresponding to the selection signal, to obtain a selectable output chain corresponding to one output road.

In the above solution, the signal bit corresponding to the selection signal is selected for the second selection The two selectable output links corresponding to the two inputs of the selector are selected to obtain a selectable output link corresponding to one output, including:

If only one of the two selectable output links corresponding to the two inputs of the two-select selector is valid, then the valid output link is selected as one of the outputs Output link;

If two of the two selectable output links corresponding to the two inputs of the two selectors are valid or both are invalid, then according to the preset of the signal bits corresponding to the selection signal The rule determines a selectable output link corresponding to the output.

In the above solution, the determining, according to a preset rule of the signal bit corresponding to the selection signal, a selectable output link corresponding to the output end, including:

When the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the first input end of the second selection selector is determined as a selectable output chain corresponding to the output end. Or; when the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the second input end of the second selection selector is determined as one corresponding to the output end; Selected output link.

In the above solution, the method further includes:

A unique one of all planes in one round of load balancing is generated according to a preset random function.

An embodiment of the present invention provides a device for random load balancing, where the device includes:

The processing module is configured to process the M selectable output links of the current sub-load balancing by using a second-selector and a unique pseudo-random number in all planes in one round of load balancing. An effective output link of the current secondary load balancing; the n and M are positive integers;

a determining module configured to block the link number of the valid output link of the current current load balancing in the M selectable link number mask tables of the current secondary load balancing, and determine M-1 selectable output links that are load balanced at a time; until all link numbers in the selectable link number mask table are masked;

The restoration module is configured to restore the blocked link number in the selectable link number mask table for the next round of load balancing.

In the above solution, the processing module is specifically configured to use the two selectors and a unique pseudo random number in all planes in the current time and a plane to the M selectable output chains. The path performs a packet of the k-level output link to obtain the effective output link of the current current load balancing; the k is a positive integer.

In the above solution, the processing module is further configured to: in the current time and in a plane, use the two selectors and a unique pseudo random number in all planes to select the M outputs. The link performs two-two packets of k-level adjacent output links;

In the above solution, the processing module is further configured to generate a selection signal according to the unique one of the pseudo-random numbers in all planes; the only one of the all planes is a binary number, in all planes The bit width of the unique pseudo random number is the number of the selection signals;

In the above solution, the processing module is further configured to: if only one of the two selectable output links corresponding to the two inputs of the two-selector is valid, the effective output is The link serves as a selectable output link corresponding to the output;

In the above solution, the processing module is further configured to: when the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the first input end of the second selection selector is determined as a selectable output link corresponding to the output; or, when the signal bit corresponding to the selection signal is 1, the selectable output corresponding to the second input of the second selector The link is determined to be a selectable output link corresponding to the output.

In the above solution, the device further includes:

A generating module is configured to generate a unique one of all planes in one round of load balancing according to a preset random function.

The processing module, the determining module, the restoring module, and the generating module may use a central processing unit (CPU), a digital signal processor (DSP, Digital Singnal Processor), or Field-Programmable Gate Array (FPGA) implementation.

The embodiment of the present invention further provides a computer storage medium storing computer executable instructions configured to perform the method of random load balancing according to any one of the foregoing aspects.

Method and device for random load balancing provided by embodiment of the present invention, and computer storage The medium, through a round of n load balancing, using a two-selection selector and a unique pseudo-random number in all planes, processing the M selectable output links of the current sub-load balancing to obtain a current An effective output link of the secondary load balancing; the n, M are positive integers; the link number of the effective output link of the current current load balancing is M selectable links of the current secondary load balancing Masked in the mask table and determine the M-1 selectable output links for the next load balancing; until all link numbers in the selectable link number mask table are masked; The masked link number in the selectable link number mask table is restored, and the next round of load balancing is performed; all cells of multiple routing planes can be uniformly allocated on the reachable link, and guaranteed. The purpose of traffic balancing across the entire network improves bandwidth utilization and system performance.

DRAWINGS

1 is a schematic diagram of a conventional multi-plane load balancing method;

2 is a flowchart of Embodiment 1 of a method for random load balancing according to the present invention;

3 is a flowchart of Embodiment 2 of a method for random load balancing according to the present invention;

4 is a schematic structural diagram of a second-selector of a method for random load balancing according to an embodiment of the present invention;

5 is a schematic diagram of a random load balancing structure of a routing plane of a 96×96 switching device according to an embodiment of a method for random load balancing according to the present invention;

6 is a schematic diagram of a load balancing cell flow direction in Embodiment 2 of a method for random load balancing according to the present invention;

FIG. 7 is a schematic structural diagram of an apparatus for random load balancing according to the present invention.

detailed description

The technical solutions in the embodiments of the present invention will be clearly and completely described in the following with reference to the accompanying drawings.

Embodiment 1

2 is a flowchart of Embodiment 1 of a method for random load balancing according to the present invention; as shown in FIG. 2, the method for random load balancing provided by the embodiment of the present invention may include the following steps:

Step 201: In a round of load balancing, using the two selectors and a unique pseudo random number in all planes, the M selectable output links of the current secondary load balancing are processed to obtain a current The effective output link of the secondary load balancing; the n and M are positive integers.

In a round of n load balancing, the M selectable output links of the current secondary load balancing are performed in the current time and in a plane by using a second selector and a unique pseudo random number in all planes. The packets of the level output link get a valid output link of the current secondary load balancing; where k is a positive integer.

Specifically, in a round of load balancing, a unique one of all planes in one round of load balancing is first generated according to a preset random function, and a selection signal is generated according to the pseudo random number; The pseudo random number is a binary number whose bit width is the number of the selection signals.

For example, the number of routing planes in load balancing is a, and the number of selection signals required for load balancing in each routing plane is b. In a cycle in which load balancing is performed on a routing plane, first A unique pseudo-random number Y in the period is generated according to the preset random function f(x), and a*b selection signals are generated according to Y, wherein the bit width of the pseudo-random number Y is a*b.

Then, in the current time and in a plane, the K selectable output links of the current sub-load balancing are subjected to k-level phase by using a two-select selector and a selection signal generated based on a unique pseudo-random number in all planes. The two-two packets of the adjacent output link get a valid output link of the current secondary load balancing.

In the first embodiment of the present invention, in the current secondary load balancing, when load balancing is performed on one routing plane, the k-th output link is grouped according to the parity of the k-th output link number m, specifically :

If m is an even number, the m output links of the kth stage are paired into two groups of adjacent output links, and the k+ is obtained by using a second selector and a unique pseudo random number in all planes. 1 Level m/2 output links until the m/2=1, obtaining an effective output link corresponding to m/2=1; wherein the m is less than or equal to M;

If m is an odd number, the m-1 output links of the kth stage are paired into two groups of adjacent output links, and the second selection selector and the unique pseudo random number in all planes are used to obtain the second (m-1)/2 output links of k+1 level and one output link of the kth stage until m=3, obtaining (m-1)/2+1=2 output links Determining a corresponding one of the effective output links in the (m-1)/2+1=2 output links by using a binary selector and a unique pseudo random number in a random load; wherein m is less than or equal to M.

In an embodiment of the present invention, a k-level phase is performed on the M selectable output links of the current sub-load balancing by using a two-select selector and a selection signal generated according to a unique pseudo-random number in all planes. When two or two packets of the output link are adjacent to each other, two selectable output links corresponding to the two input ends of the two-selection selector are selected according to the signal bits corresponding to the selection signal, and the selection process thereof for:

If only one of the two selectable output links corresponding to the two inputs of the two selectors is active, then the valid output link is used as a selectable output link corresponding to the output. ;

If two of the two selectable output links corresponding to the two inputs of the two selectors are valid or both are invalid, then the predetermined rule is determined according to the signal bit corresponding to the selection signal. A selectable output link corresponding to the output end; specifically: when the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the first input end of the second selection selector is determined as an output a selectable output link corresponding to the end; or, when the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the second input end of the second selector is determined as the output end Corresponding to an optional output link.

Step 202: Shield the link number of the valid output link of the current current load balancing in the M selectable link number mask tables of the current secondary load balancing, and determine the next load. Equalized M-1 selectable output links; until all link numbers in the selectable link number mask table are masked.

After obtaining a valid output link of the current secondary load balancing, the link number of the valid output link is masked in the M selectable link number mask table of the current secondary load balancing, unmasked The link will act as the M-1 actually selectable output links for the next load balancing; until all link numbers in the selectable link number mask table are masked, a round of load balancing is completed.

Step 203: Restore the blocked link number in the selectable link number mask table, and perform the next round of load balancing.

After completing one round of load balancing, the blocked link number in the selectable link number mask table is restored, and steps 201 to 202 are performed again to perform the next round of load balancing.

The random load balancing method provided by the embodiment of the present invention selects M of the current sub-load balancing by using a two-selection selector and a unique pseudo-random number in all planes in one round of load balancing. The output link is processed to obtain a valid output link of the current secondary load balancing; the n and M are positive integers; the link number of the effective output link of the current current load balancing is in the current time Shielding of load-balanced M selectable link number mask tables and determining M-1 selectable output links for next load balancing; until all of the selectable link number mask tables The link number is masked; the shielded link number in the selectable link number mask table is restored, and the next round of load balancing is performed; using a two-choice selector and a load balancing mask All the cells of multiple routing planes can be evenly distributed on the reachable links to ensure the traffic balance of the entire network. The bandwidth utilization and system performance can be improved and can be used in various modes. Net knot .

Embodiment 2

3 is a flowchart of Embodiment 2 of a method for random load balancing according to the present invention; this embodiment is described by taking a processing manner of a routing plane of a 96×96 switching device as an example, and the switching device includes four Routing plane: plane 0, plane 1, plane 2 and plane 3; the selection signal (select signal) of the two selectors used by the four routing planes is generated by the same random function generator, and the selectable output link is 96. As shown in FIG. 3, the method for random load balancing provided by the embodiment of the present invention may include the following steps:

Step 301: The 96 selectable output links are grouped into two groups and divided into 48 groups. After the first level selection, 48 output links are generated.

The 96 selectable output links are grouped into two groups of adjacent links, which can be divided into 48 groups in total; after the 48 sets of selectable output links are selected by the first choice of 48 two-selectors, Get 48 output links.

4 is a schematic structural diagram of a selector of a method for random load balancing according to an embodiment of the present invention; as shown in FIG. 4, the selector of two options includes two input terminals, one selection signal terminal, and one output terminal; The inputs of the selected selector are link a and link b, respectively, and one of link a and link b is selected as the output link according to link a, link b and selection signal; specifically, when the link When a is valid and link b is invalid, link a is selected as the output link; when link a is invalid and link b is valid, link b is selected as the output link; when link a and link b are both When valid, the corresponding bit of the selection signal (select signal) is used to select link a or link b as an output link; for example, it may be preset to select a link when the corresponding bit of the selection signal (select signal) is 1. a is used as an output link; or, it may be preset that the link b is selected as an output link when the corresponding bit of the selection signal (select signal) is 1.

Step 302: The generated 48 output links are grouped into two groups and divided into 24 groups. After the second level is selected, 24 output links are generated.

After the first stage selection is performed on the 96 selectable output links, after 48 output links are generated, the two output links of the adjacent output links are continued for the 48 output links, and the total can be divided into 24 groups, and then The 24 sets of output links use 24 two-select selectors for second-level selection, resulting in 24 output links.

Step 303: The generated 24 output links are grouped into two groups, and are divided into 12 groups. After the third level is selected, 12 output links are generated.

After two stages of selection of 96 selectable output links, after generating 24 output links, the 24 output links continue to be grouped into two groups of adjacent output links, divided into 12 groups, and then 12 groups The output link uses 12 two-select selectors for third-level selection, resulting in 12 output links.

Step 304: The generated 12 output links are grouped into two groups, and are divided into six groups. After the fourth level is selected, six output links are generated.

Performing three levels of selection on 96 selectable output links, after generating 12 output links, continuing to perform two-two grouping of adjacent output links for the 12 output links, which are divided into 6 groups, and then 6 The group output link uses six alternative selectors for the fourth level selection, resulting in six output links.

Step 305: The generated 6 output links are grouped into two groups, and are divided into three groups. After the fifth level is selected, three output links are generated.

After four selections of 96 selectable output links are generated, after six output links are generated, the two output links continue to be grouped into two groups of adjacent output links, and are divided into three groups, and then 3 The group output link uses three alternative selectors for the fifth level selection, resulting in three output links.

Step 306: Divide the generated three output links into two groups and one group, and perform a sixth level selection on the output chains of the two groups to generate one output link and one output remaining. link.

After performing five levels of selection on 96 selectable output links, and generating three output links, the first and second output links or the second and third output links of the three output links are divided. For the first group, the remaining one output link is the second group; then, the two output links of the first group are selected by the second selection selector for the sixth level, and one output link is generated. At the same time, there is one output link remaining.

Step 307: Performing a seventh-level selection of one output link generated by the sixth stage and one remaining output link of the fifth stage to obtain an effective output link.

Taking one output link generated by the sixth level selection and the remaining one output link of the fifth level as one group, using one of the two selectors for the seventh level selection, generating one effective output link, The output link is the final payload balanced link.

Step 308: Shield the obtained link number of a valid output link in the link number mask table of the 96 selectable output links to generate a selectable output link for the next load balancing.

After selecting the last payload equalization link from the 96 selectable output links, the link number of the load balancing link is masked in the link number mask table of the 96 selectable output links. , produces a selectable output link for the next load balancing.

For example, after obtaining a payload equalization link, the location corresponding to the payload equalization link may be 1 and fed back to the load balancing input end, and the link number is in 96 selectable link number masks. Shielded in the table to obtain the next output loadable selectable output link, so that the next blocked load will not be selected.

5 is a schematic diagram of a random load balancing structure of a routing plane of a 96×96 switching device according to an embodiment of a method for random load balancing according to the present invention; as shown in FIG. 5, 96 selectable output links are performed by using a selective selector. Two-two packets and selection of seven adjacent output links, and finally an output link is generated as a payload equalization link; and a corresponding mask is fed back to the input of the load balancing, and the payload is balanced. The link number is masked in the link number mask table of the 96 selectable output links, resulting in a selectable output link for the next load balancing.

The process of load balancing in each routing plane in the switching device is identical; that is, steps 301 to 308 are performed on plane 0, plane 1, plane 2, and plane 3, and each of the active load balancing links is synchronously generated. , the output link to the switching device.

In the above process, each routing plane needs 48+24+12+6+3+1+1=95 selection signals (select signals), and a total of 4 planes require a total of 4×95 selection signals; Choose The signal (select signal) is generated by a pseudo-random number Y, and the pseudo-random number Y is generated by a preset random function, for example, generated by a preset random function f(x)=x^31+x^28+1; 4 planes Each time load balancing is completed, a Y is generated, and the bit width is the number of selection signals (select signals), that is, 4×95.

It should be noted that the preset random function can be set according to actual needs, which is not limited herein.

6 is a schematic diagram of a load balancing cell flow direction in Embodiment 2 of a method for random load balancing according to the present invention; as shown in FIG. 6, after a load balancing is performed on a total of 96 selectable output links from 0 to 95, a plane is used. The output link generated by 0 is the link 0, the output link generated by plane 1 is the link 1, the output link generated by plane 2 is the link 2, and the output link generated by plane 3 is the link 3. That is, four planes can be load balanced to different links respectively, avoiding multi-plane resonance.

Step 309: Determine whether all link numbers in the selectable link number mask table are blocked.

After completing a load balancing, it is determined whether all link numbers in the selectable link number mask table are masked. If all the link numbers in the selectable link number mask table are not completely blocked, then Step 310 is performed. If all the link numbers in the selectable link number mask table are blocked, step 311 is performed.

Step 310: Perform the next load balancing.

When it is determined that all the link numbers in the selectable link number mask table are not completely masked, the load balancing of the current round is not completed, and then the next load balancing is performed on plane 0, plane 1, plane 2, and plane 3, That is, steps 301 to 308 are performed.

Step 311: Restore the blocked link number in the selectable link number mask table, and perform the next round of load balancing.

When it is judged that all link numbers in the selectable link number mask table have been masked, the current load balancing is ended, and at this time, the blocked link number in the selectable link number mask table is restored. Then proceed to the next round of load balancing.

In the above process, when the same round of load balancing is performed, after a load balancing is completed to generate a valid load balancing link, the next load balancing is generated according to the mask table of the load balancing link and the selectable output link. The output link can be selected, that is, the link number of the generated payload equalization link is shielded in the currently selectable link number mask table, which can avoid the same round of load balancing twice randomly to the same link; Each time the random selection signal (select signal) is different, it can effectively avoid resonance of multiple routing planes, reduce the probability of multi-route plane load balancing to the same link, and finally achieve the purpose of load balancing.

The random load balancing method provided by the embodiment of the present invention performs two-two grouping on 96 selectable output links, and after the first-stage selection, generates 48 output links; 48 output links to be generated are performed. Two or two groups, after the second level selection, generate 24 output links; the generated 24 output links are grouped into two groups, and after the third level is selected, 12 output links are generated; 12 will be generated The output link performs two-two grouping, and after the fourth-stage selection, six output links are generated; the six output links that are generated are grouped into two groups, and after the fifth-level selection, three output links are generated; The generated three output links are divided into two groups and one group, and the second level of the output links of the two groups is selected to generate one output link and one output link remaining; The first output link generated by the sixth stage and the remaining one output link of the fifth stage are subjected to the seventh level selection to obtain an effective output link; the link number of the obtained effective output link is 96. Select the mask in the link number mask table of the output link to generate the next time. a balanced output selectable output link; determine whether all link numbers in the selectable link number mask table are masked, and if not all masked, perform next load balancing; if both are masked, then The masked link number in the selectable link number mask table is restored, and the next round of load balancing is performed; the same round of load balancing is avoided to randomly go to the same link twice, which effectively avoids resonance of multiple routing planes. The probability of multi-route plane load balancing to the same link is reduced, and all the cells of multiple routing planes can be uniformly allocated on the reachable link to ensure the traffic balance of the entire network, and the purpose is improved. Bandwidth utilization and system performance.

Embodiment 3

FIG. 7 is a schematic structural diagram of an apparatus for random load balancing according to the present invention; as shown in FIG. 7, the random load balancing apparatus 07 provided by the embodiment of the present invention includes: a processing module 71, a determining module 72, and a restoring module 73;

The processing module 71 is configured to perform the current sub-load balanced M selectable output links by using a second-selector and a unique pseudo-random number in all planes in one round of load balancing. Processing, obtaining a valid output link of the current secondary load balancing; the n and M are positive integers;

The determining module 72 is configured to block the link number of the valid output link of the current current load balancing in the M selectable link number mask tables of the current secondary load balancing, and determine M-1 selectable output links that are load balanced at a time; until all link numbers in the selectable link number mask table are masked;

The restoration module 73 is configured to restore the blocked link number in the selectable link number mask table for the next round of load balancing.

In an embodiment of the present invention, the processing module 71 is configured to: in the current time and in a plane, use a second selector and a unique pseudo random number in all planes, and the M is used. The selectable output links are grouped into k-level output links to obtain the effective output link of the current current load balancing; the k is a positive integer.

In an embodiment of the present invention, the processing module 71 is further configured to: in the current time and in a plane, use a second selector and a unique pseudo random number in all planes, M selectable output links for two-two packets of k-level adjacent output links;

In an embodiment of the present invention, the processing module 71 is further configured to generate a selection signal according to the unique one of the pseudo-random numbers in all planes; the only one of the all planes is a binary number The bit width of the only one of the pseudo-random numbers in all the planes is the number of the selection signals;

In an embodiment of the present invention, the processing module 71 is further configured to: if only one of the two selectable output links corresponding to the two input ends of the two-selection selector is valid, Using the valid output link as a selectable output link corresponding to the output;

In an embodiment of the present invention, the processing module 71 is further configured to: when the signal bit corresponding to the selection signal is 1, select a corresponding one of the first input ends of the second selection selector The output link is determined as a selectable output link corresponding to the output end; or, when the signal bit corresponding to the selection signal is 1, the second input end of the second selector is selected Corresponding selectable output links are determined to be an alternative to the output Output link.

In an embodiment of the present invention, the device 07 further includes: a generating module 74;

The generating module 74 is configured to generate a unique one of all planes in one round of load balancing according to a preset random function.

The device of the random load balancing in this embodiment may be used to perform the technical solution of the foregoing method embodiment, and the implementation principle and the technical effect are similar, and details are not described herein again.

In a practical application, the processing module 71, the determining module 72, the restoring module 73, and the generating module 74 of the stochastic load balancing device 07 may each be a central processing unit (CPU) located in the random load balancing device 07. ), a microprocessor (Micro Processor Unit, MPU), a digital signal processor (DSP), or a Field Programmable Gate Array (FPGA).

Those skilled in the art will appreciate that embodiments of the present invention can be provided as a method, system, or computer program product. Accordingly, the present invention can take the form of a hardware embodiment, a software embodiment, or a combination of software and hardware. Moreover, the invention can take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage and optical storage, etc.) including computer usable program code.

The present invention has been described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (system), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or FIG. These computer program instructions can be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing device to produce a machine for the execution of instructions for execution by a processor of a computer or other programmable data processing device. Means for implementing the functions specified in one or more of the flow or in a block or blocks of the flow chart.

The computer program instructions can also be stored in a computer readable memory that can direct a computer or other programmable data processing device to operate in a particular manner, such that the instructions stored in the computer readable memory produce an article of manufacture comprising the instruction device. The apparatus implements the functions specified in one or more blocks of a flow or a flow and/or block diagram of the flowchart.

These computer program instructions can also be loaded onto a computer or other programmable data processing device such that a series of operational steps are performed on a computer or other programmable device to produce computer-implemented processing for execution on a computer or other programmable device. The instructions provide steps for implementing the functions specified in one or more of the flow or in a block or blocks of a flow diagram.

The above is only the preferred embodiment of the present invention and is not intended to limit the scope of the present invention.

Industrial applicability

According to the embodiment of the present invention, the M selectable output links of the current sub-load balancing are processed by using a two-selection selector and a unique pseudo-random number in all planes in one round of load balancing. Obtaining a valid output link of the current secondary load balancing; the n and M are positive integers; and the link number of the effective output link of the current current load balancing is equal to the M of the current secondary load balancing Masked in the selected link number mask table and determine the M-1 selectable output links for the next load balancing; until all link numbers in the selectable link number mask table are masked Upstream; the masked link number in the selectable link number mask table is restored, and the next round of load balancing is performed; all cells of multiple routing planes can be uniformly allocated in the reachable chain. On the road, to ensure the balance of traffic throughout the network, the utilization of bandwidth and the performance of the system are improved.

Claims

A method of random load balancing, the method comprising:

In a round of n-time load balancing, the M-selectable output links of the current sub-load balancing are processed by using a two-choice selector and a unique pseudo-random number in all planes to obtain a current sub-load balancing. Effective output link; the n, M are positive integers;

The link number of the valid output link of the current current load balancing is masked in the M selectable link number mask tables of the current secondary load balancing, and the M-1 of the next load balancing is determined. Selectable output link;

Until all link numbers in the selectable link number mask table are masked;

The masked link number in the selectable link number mask table is restored for the next round of load balancing.
The method of claim 1 wherein said processing the M selectable output links of the current sub-load balancing using a two-select selector and a unique one of the pseudo-random numbers in all planes results in a The effective output link for current sub-load balancing, including:

Performing k-level output link grouping on the M selectable output links in the current time and in a plane by using a second-selector and a unique one of the pseudo-random numbers in all planes Describe a valid output link for current secondary load balancing; the k is a positive integer.
The method of claim 2 wherein said M selectable outputs are selected in said current time and in a plane using a second selector and a unique pseudo random number in all planes The link performs a packet of the k-level output link to obtain the effective output link of the current current load balancing, including:

Performing, in the current time and in a plane, two pairs of k-level adjacent output links for the M selectable output links by using a two-select selector and a unique one of the pseudo-random numbers in all planes Grouping

If the number of output links m of the kth stage is even, the m output links of the kth stage are performed. Two or two packets of adjacent output links, using a two-select selector and the unique one of the pseudo-random numbers in all planes to obtain m/2 output links of the k+1th stage until the m/2 =1, an effective output link corresponding to the m/2=1 is obtained; the m is less than or equal to M;

If the number m of output links of the kth stage is an odd number, the m-1 output links of the kth stage are grouped into two groups of adjacent output links, and the selectors are selected and the planes are used in all planes. The only one pseudo-random number obtains (m-1)/2 output links of the k+1th stage and the remaining 1 output link of the kth stage until the m=3, and (m-1) /2+1=2 output links, which are determined in the (m-1)/2+1=2 output links by using a binary selector and a unique pseudo random number in a random load Corresponding one effective output link; the m is less than or equal to M.
The method of claim 1 wherein said processing the M selectable output links of the current sub-load balancing using a two-select selector and a unique one of the pseudo-random numbers in all planes comprises:

Generating a selection signal according to the unique one of the pseudo-random numbers in all planes; the only one of the all planes is a binary number, and the bit width of the only one of the all planes is the selection The number of signals;

Selecting two selectable output links corresponding to the two inputs of the two selectors according to the signal bits corresponding to the selection signal, to obtain a selectable output chain corresponding to one output road.
The method according to claim 4, wherein said selecting two selectable output links corresponding to two inputs of said two selector selectors according to signal bits corresponding to said selection signal, Obtain an optional output link corresponding to an output, including:

If only one of the two selectable output links corresponding to the two inputs of the two-select selector is valid, the valid output link is used as the output end An optional output link;

If two of the two selectable output links corresponding to the two inputs of the two selectors are valid or both are invalid, then according to the preset of the signal bits corresponding to the selection signal The rule determines a selectable output link corresponding to the output.
The method according to claim 5, wherein the determining, according to a preset rule of signal bits corresponding to the selection signal, a selectable output link corresponding to the output end, comprising:

When the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the first input end of the second selection selector is determined as a selectable output chain corresponding to the output end. Or; when the signal bit corresponding to the selection signal is 1, the selectable output link corresponding to the second input end of the second selection selector is determined as one corresponding to the output end; Selected output link.
The method of any of claims 1-6, wherein the method further comprises:

A unique one of all planes in one round of load balancing is generated according to a preset random function.
A device for random load balancing, the device comprising:

The processing module is configured to process the M selectable output links of the current sub-load balancing by using a second-selector and a unique pseudo-random number in all planes in one round of load balancing. An effective output link of the current secondary load balancing; the n and M are positive integers;

a determining module configured to mask the link number of the valid output link of the current current load balancing in the M selectable link number mask tables of the current secondary load balancing, and determine the next load balancing M-1 selectable output links; until all link numbers in the selectable link number mask table are masked;

a restore module configured to block the blocked link number in the selectable link number mask table Restore, the next round of load balancing.
The device according to claim 8, wherein the processing module is specifically configured to: in the current time and in a plane, use a second selector and a unique pseudo random number in all planes, The M selectable output links are grouped into k-level output links to obtain the effective output link of the current current load balancing; the k is a positive integer.
The apparatus according to claim 9, wherein the processing module is further configured to: in the current time and a plane, use a second selector and a unique pseudo random number in all planes, The M selectable output links perform two-two packets of k-level adjacent output links;

If the number m of the output links of the kth stage is an even number, the m output links of the kth stage are grouped into two groups of adjacent output links, and the selectors of the second selection and the unique ones in all planes are utilized. a pseudo-random number obtains m/2 output links of the k+1th level until the m/2=1, obtaining an effective output link corresponding to the m/2=1; the m is smaller than Equal to M;

If the number m of output links of the kth stage is an odd number, the m-1 output links of the kth stage are grouped into two groups of adjacent output links, and the selectors are selected and the planes are used in all planes. The only one pseudo-random number obtains (m-1)/2 output links of the k+1th stage and the remaining 1 output link of the kth stage until the m=3, and (m-1) /2+1=2 output links, which are determined in the (m-1)/2+1=2 output links by using a binary selector and a unique pseudo random number in a random load Corresponding one effective output link; the m is less than or equal to M.
The apparatus according to claim 8, wherein the processing module is further configured to: generate a selection signal according to the only one pseudo random number in all planes; a unique one of the all planes is a pseudo random number a binary number, a bit width of a unique one of the all planes being the number of the selection signals;

Two inputs to the two selectors according to signal bits corresponding to the selection signal The two selectable output links corresponding to the end are selected to obtain a selectable output link corresponding to one output.
The apparatus according to claim 11, wherein the processing module is further configured to: if only one of the two selectable output links corresponding to the two inputs of the two-selector is valid And the effective output link is used as a selectable output link corresponding to the output end;

If two of the two selectable output links corresponding to the two inputs of the two selectors are valid or both are invalid, then according to the preset of the signal bits corresponding to the selection signal The rule determines a selectable output link corresponding to the output.
The device according to claim 12, wherein the processing module is further configured to: when the signal bit corresponding to the selection signal is 1, the first input end of the second selection selector is corresponding to The selectable output link is determined as a selectable output link corresponding to the output terminal; or, when the signal bit corresponding to the selection signal is 1, the second input of the second selector is selected The selectable output link corresponding to the terminal is determined as a selectable output link corresponding to the output.
The device of any of claims 8-13, wherein the device further comprises:

A generating module is configured to generate a unique one of all planes in one round of load balancing according to a preset random function.
A computer storage medium having stored therein computer executable instructions configured to perform the method of random load balancing of any of the preceding claims 1-7.