Abstract:
Disclosed is a load balancing method, the method comprising: for an exchange device at every level, before transmitting each cell, querying a unicast forwarding table according to the ID number of a target access device so as to obtain all links accessing the target access device; and in the all links, polling the cell transmitted to the corresponding target access device. Also disclosed are a load balancing device and storage medium.

Description:
TECHNICAL FIELD 
       [0001]    The disclosure relates to data exchange technology in the field of mobile communications, and in particular to a load balancing method, apparatus, and a storage medium. 
       BACKGROUND 
       [0002]    At present, an exchange network implements data exchange between exchange access apparatuses in an exchange system. The exchange network is divided into a single-stage exchange network and a three-stage CLOS exchange network. The single-stage exchange network is simple in networking and small in capacity. The three-stage CLOS exchange network is complicated in networking and large in capacity. The single-stage exchange network is simple in networking with each link corresponding to only one access apparatus, so the situation where a plurality of access apparatuses share a link does not exist. Therefore, data streams to different access apparatuses in the exchange network will not affect each other. 
         [0003]    In the three-stage CLOS exchange network, as shown in  FIG. 1 , it is composed of three stages of exchange units. Cells sent by the access apparatus reaches to a destination access apparatus via a three-stage exchange apparatus respectively. In first-stage exchange and second-stage exchange, a link may reach to a plurality of access apparatuses. Therefore, data streams arriving to different access apparatuses will affect each other. A traditional load balancing method performs load balancing in all links instead of distinguishing data streams. Therefore, it may be caused that a data stream arriving to a certain apparatus is transmitted in one or more links, thereby causing the problems of local congestion and bandwidth waste of the data stream. 
         [0004]    Data is transmitted in the exchange network on the basis of a cell unit. As shown in  FIG. 2 , a first-stage exchange apparatus receives cells sent to an access apparatus N−1 and an apparatus N, and two links may both reach to the destination access apparatus currently. In accordance with a traditional load balancing mode, these two links do not distinguish destinations of the cells. Therefore, the cells sent in these two links in a polling way, for example, the first cell is sent to a second-stage exchange apparatus  0 , the second cell is sent to a second-stage exchange apparatus  1 , the third cell is also sent to the second-stage exchange apparatus  0 , and so on. So, all the cells sent to the access apparatus N−1 are sent to the second-stage exchange apparatus  0 , and then sent to a third-stage exchange apparatus N−1; and all the cells sent to the access apparatus N are sent to the second-stage exchange apparatus  1 , and then sent to a third-stage exchange apparatus N. A final result is that: all the cells sent to the access apparatus N−1 are congested in the third-stage exchange apparatus N−1, and all the cells sent to the access apparatus N are congested in the third-stage exchange apparatus N. Meanwhile, only one of these two links of the destination access apparatuses N and N−1 receives the cells, and the bandwidths of the other link are completely wasted. 
         [0005]    As above, the traditional load balancing method cannot ensure that cells arriving to each destination access apparatus are balanced across all accessible links. The load balancing method may cause congestion of cells in a certain exchange apparatus, so the exchange capability is reduced, and meanwhile, bandwidth waste will be caused. 
       SUMMARY 
       [0006]    To solve the existing technical problems, the embodiments of the disclosure provide a load balancing method, apparatus, and a storage medium. 
         [0007]    The embodiments of the disclosure provide a load balancing method, which may include the following steps: 
         [0008]    querying, for an exchange apparatus at each stage, a unicast forwarding table according to an ID number of a destination access apparatus before each cell is sent so as to obtain all links arriving to the destination access apparatus; sending, in all the links, the cell arriving to the corresponding destination access apparatus in a polling way. 
         [0009]    Sending, in all the links, the cell arriving to the corresponding destination access apparatus in a polling way includes: 
         [0010]    setting, for the exchange apparatus at each stage, a corresponding load balancing mask table and querying the load balancing mask table while or after the unicast forwarding table is queried; 
         [0011]    performing an AND operation on query results about the unicast forwarding table and the load balancing mask table, and selecting a link having a smaller link number from an AND result via which the cell is sent; and 
         [0012]    setting a mask corresponding to the selected link in the load balancing mask table as 0 with masks corresponding to the remaining unselected links unchanged, and writing the modified mask back to the load balancing mask table. 
         [0013]    The load balancing mask table records the link selected for sending the cell and the unselected links, and after all the links corresponding to an ID number of a destination access apparatus are selected, table entries in this row are all links accessible to the access apparatus. 
         [0014]    In an embodiment, the method may further include: setting initial values of table entries of the load balancing mask table corresponding to each destination access apparatus as 0, and writing, after the unicast forwarding table is read and when no link is selected, all the read links into the load balancing mask table. 
         [0015]    In an embodiment, the method further includes: 
         [0016]    recording, before all the links are selected, the selected link for sending the cell and the unselected links in the load balancing mask table; and 
         [0017]    re-modifying, after all the links are selected, the table entries in the load balancing mask table as all links accessible to the access apparatus. 
         [0018]    The embodiments of the disclosure also provide a storage medium. The storage medium may include a set of instructions, when are executed, causing at least one processor to perform the above-mentioned operations. 
         [0019]    The embodiments of the disclosure also provide a load balancing apparatus. The apparatus may be placed in an exchange apparatus at each stage, and may include a link querying module and a cell sending module, wherein 
         [0020]    the link query module is arranged to query a unicast forwarding table according to an ID number of a destination access apparatus before each cell is sent so as to obtain all links arriving to the destination access apparatus; and 
         [0021]    the cell sending module is arranged to send, in all the links obtained by the link querying module, the cell arriving to the corresponding destination access apparatus in a polling way. 
         [0022]    The cell sending module is arranged to: set, for the exchange apparatus at each stage, a corresponding load balancing mask table, and query the load balancing mask table while or after the unicast forwarding table is queried; 
         [0023]    perform an AND operation on query results about the unicast forwarding table and the load balancing mask table, and select a link having a smaller link number from an AND result via which the cell is sent; and 
         [0024]    set a mask corresponding to the selected link in the load balancing mask table as 0 with masks corresponding to the remaining unselected links unchanged, and write the modified mask back to the load balancing mask table. 
         [0025]    The cell sending module includes a setting and querying module, a calculating and selecting module, and a mask processing module, wherein 
         [0026]    the setting and querying module is arranged to set, for the exchange apparatus at each stage, a corresponding load balancing mask table to, and query the load balancing mask table while or after the unicast forwarding table is queried; 
         [0027]    the calculating and selecting module is arranged to perform an AND operation on query results about the unicast forwarding table and the load balancing mask table, and select a link having a smaller link number from an AND result via which the cell is sent; and 
         [0028]    the mask processing module is arranged to set a mask corresponding to the selected link in the load balancing mask table as 0 with masks corresponding to the remaining unselected links unchanged, and write the modified mask back to the load balancing mask table. 
         [0029]    In an embodiment, the mask processing module is further arranged to set initial values of table entries of the load balancing mask table corresponding to each destination access apparatus as 0, and write, after the unicast forwarding table is read and when no link is selected, all the read links into the load balancing mask table. 
         [0030]    In an embodiment, the mask processing module is further arranged to: record, before all the links are selected, the selected link for sending the cell and the unselected links in the load balancing mask table; and 
         [0031]    re-modify, after all the links are selected, the table entries in the load balancing mask table as all links accessible to the access apparatus. 
         [0032]    According to the load balancing method, apparatus and the storage medium provided by the embodiments of the disclosure, for an exchange apparatus at each stage, a unicast forwarding table is queried according to an ID number of a destination access apparatus before each cell is sent so as to obtain all links arriving to the destination access apparatus; and in all the links, the cell arriving to the corresponding destination access apparatus is sent in a polling way. In the embodiments of the disclosure, cells arriving to each destination access apparatus may be balanced across to accessible links at an exchange apparatus at each stage by distinguishing the destination access apparatuses to which the cells arrive, so it may be ensured that the cells arriving to the destination access apparatus allocates data streams on all links in a balanced manner, thereby improving the utilization ratio of bandwidths and improving the exchange capability. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0033]    In the drawings (not necessarily drawn in proportion), similar reference numbers may describe similar parts in different views. The similar reference number having different letter suffixes may represent different examples for the similar parts. The drawings substantially show each of the embodiments discussed herein in an example way instead of a limitation way. 
           [0034]      FIG. 1  is a structural diagram of a three-stage CLOS exchange network; 
           [0035]      FIG. 2  is a flow diagram of a load balancing cell of a traditional three-stage CLOS exchange network; 
           [0036]      FIG. 3  is an implementation flowchart of a load balancing method according to an embodiment of the disclosure; 
           [0037]      FIG. 4  is a flow diagram of a load balancing cell of a three-stage CLOS exchange network according to an embodiment of the disclosure; 
           [0038]      FIG. 5  is a structural diagram of a load balancing apparatus according to an embodiment of the disclosure; 
           [0039]      FIG. 6  is a structural diagram of a cell sending module in a load balancing apparatus according to an embodiment of the disclosure; and 
           [0040]      FIG. 7  is a structural diagram of a load balancing mask table according to an embodiment of the disclosure. 
       
    
    
     DETAILED DESCRIPTION 
       [0041]    In the embodiments of the disclosure, for an exchange apparatus at each stage, a unicast forwarding table is queried according to an ID number of a destination access apparatus before each cell is sent, so as to obtain all links arriving to the destination access apparatus; and in all the links, the cell arriving to the corresponding destination access apparatus is sent in a polling way. 
         [0042]    The disclosure will be further described in detail below in connection with the drawings and specific embodiments. 
         [0043]      FIG. 3  is an implementation flowchart of a load balancing method according to an embodiment of the disclosure. As shown in  FIG. 3 , the method includes the following steps: 
         [0044]    Step  301 : querying, for an exchange apparatus at each stage, a unicast forwarding table according to an ID number of a destination access apparatus before each cell is sent so as to obtain all links arriving to the destination access apparatus; 
         [0045]    Step  302 : sending, in all the links, the cell arriving to the corresponding destination access apparatus in a polling way. 
         [0046]    In the embodiments of the disclosure, Step  302  specifically includes the following steps: 
         [0047]    Step  3021 : setting, for the exchange apparatus at each stage, a corresponding load balancing mask table, and querying the load balancing mask table while or after the unicast forwarding table is queried; 
         [0048]    Step  3022 : performing an AND operation on query results about the unicast forwarding table and the load balancing mask table, and selecting a link having a smaller link number from an AND result via which the cell is sent; 
         [0049]    Step  3023 : setting a mask corresponding to the selected link in the load balancing mask table as 0 with masks corresponding to the remaining unselected links unchanged, and writing the modified mask back to the load balancing mask table. 
         [0050]    In an embodiment of the disclosure, Step  3022  may also be: performing an AND operation on query results about the unicast forwarding table and the load balancing mask table, and selecting a link having a larger link number from an AND result via which the cell is sent. 
         [0051]    In an embodiment of the disclosure, the load balancing mask table records the link selected for sending the cell and the unselected links. For example, the selected link corresponding to an ID number of a destination access apparatus and the unselected links may be correspondingly recorded in each row of the load balancing mask table. 
         [0052]    After all links corresponding to an ID number of a certain destination access apparatus are selected, table entries in this row are re-modified as all links accessible to the access apparatus. 
         [0053]    In an embodiment of the disclosure, the method further includes: setting initial values of table entries of the load balancing mask table corresponding to each destination access apparatus as 0, and after the unicast forwarding table is read and when no link is selected, writing all the read links into the load balancing mask table. 
         [0054]    In an embodiment of the disclosure, the method further includes: 
         [0055]    recording, before all the links are selected, the selected link for sending the cell and the unselected links in the load balancing mask table; and 
         [0056]    re-modifying, after all the links are selected, the table entries in the load balancing mask table as all links accessible to the access apparatus. 
         [0057]    Here, since link masks corresponding to the ID number of each access apparatus are independent, in the exchange apparatus, cells arriving to each access apparatus may be allocated in the accessible links in a balanced manner. 
         [0058]    Obviously, in the embodiments of the disclosure, cells arriving to each destination access apparatus may be allocated to accessible links at an exchange apparatus at each stage in a balanced manner by distinguishing the destination access apparatuses to which the cells arrive, so it may be ensured that the cells arriving to the destination access apparatus allocates data streams on all links in a balanced manner, thereby improving the utilization ratio of bandwidths and improving the exchange capability. 
         [0059]    The embodiments of the disclosure also provide a storage medium. The storage medium includes a set of instructions, when executed, causing at least one processor to perform the above-mentioned operations. 
         [0060]    The method of the disclosure will be described in detail below in connection with a specific application scenario. 
         [0061]    In the present scenario,  FIG. 4  shows a structural diagram of a three-stage CLOS exchange network. A data sending mode is the same as that shown in  FIG. 2 , in order to compare differences between these two load balancing methods. A first-stage exchange apparatus  0  receives cells sent to an access apparatus N−1 and an access apparatus N, and these two kinds of cells may arrive to a destination access apparatus N−1 and a destination access apparatus N via a second-stage exchange apparatus  0  and a second-stage exchange apparatus  1 , a third-stage exchange apparatus N−1 and a third-stage exchange apparatus N. As shown in  FIG. 2 , in accordance with a traditional load balancing mode, cells cannot be equally allocated in all accessible links, thereby causing local congestion of cells and bandwidth waste. 
         [0062]    In the embodiment for the present scenario, since processing modes of the load balancing method in the exchange apparatus at each stage are identical, the processing mode in the first-stage exchange apparatus is taken as an example herein. The specific processing mode of the present embodiment is as follows: 
         [0063]    Step 1: reading a unicast forwarding table and obtaining two links to an access apparatus N−1, namely a link  0  and a link  1 ; 
         [0064]    Step 2: while or after the unicast forwarding table is read, reading a load balancing mask table. All table entries corresponding to the load balancing mask table currently are 0. In order to ensure that an AND result of data read from the unicast forwarding table and the table entries in the load balancing mask table is not 0, when all the table entries in the load balancing mask table are 0, the table entries are automatically modified as the data read from the unicast forwarding table, that is, two links of which the link numbers are 0 and 1; 
         [0065]    Step 3: performing an AND operation on a reading result about the unicast forwarding table and a reading result about the load balancing mask table, to obtain the two links namely the link  0  and the link  1 , and selecting the link having a smaller link number, namely the link  0  at this time. Therefore, a cell sent to the access apparatus N−1 will be sent out via the link  0 ; 
         [0066]    Step 4: modifying the load balancing mask table. That is, masks of the link  0  in the table entries of the load balancing mask table are set as 0, so current load balancing masks are masks of the unselected link  1 , and the masks are written to a corresponding address in the load balancing mask table. 
         [0067]    Here, the address is an address corresponding to a forwarded unicast ID number. Because there is one-to-one correspondence between the load balancing mask table and the unicast forwarding table, each row in the table represents the unicast ID number. For example, the ID number of a cell forwarded currently is 0, so the corresponding address is an address  0 . 
         [0068]    In the embodiment of the disclosure, the load balancing mask table may adopt the structure as shown in  FIG. 7 , where a row mark represents a unicast ID number as shown by 0 to N−1; a column mark represents a link number as shown by 0 to M−1; each position in the unicast forwarding table is 1 or 0, 1 represents that the link is accessible to the destination access apparatus, and 0 represents that the link is not accessible to the destination access apparatus. For each position in the load balancing mask table, 1 represents that the link is selectable, and 0 represents that the link is not selectable. So, if a certain link is selected when the cell is sent previously, the position corresponding to the ID number will be set as 0, representing that the link has been selected; 
         [0069]    Step 5: continuing to read the unicast forwarding table, so as to obtain two links sent to an access apparatus N, namely the link  0  and the link  1 . The above-mentioned steps  2 ,  3  and  4  are repeated to determine that the cell sent to the access apparatus N is sent out from the link  0 ; 
         [0070]    Step 6: continuing to read the unicast forwarding table, so as to obtain two links sent to the access apparatus N−1, namely the link  0  and the link  1 ; 
         [0071]    It is noted that in the embodiments of the disclosure, each time the exchange apparatus at each stage receives a unicast signal, the unicast forwarding table will be read once. Of course, the load balancing mask table will be read once. 
         [0072]    Step 7: reading the load balancing mask table sent to the access apparatus N−1, to obtain only the link  1 ; 
         [0073]    Step 8: selecting the link  1  for sending the cell, since the table entries of the load balancing mask table have masks of only the link  1 ; 
         [0074]    Step 9: re-setting the table entries of the load balancing mask table as 0 and writing them into the load balancing mask table, since all the links arriving to the access apparatus N−1 are selected for one time; 
         [0075]    Step 10: reading the unicast forwarding table, so as to obtain two links sent to the access apparatus N, namely the link  0  and the link  1 . The above-mentioned steps  7 ,  8  and  9  are repeated to determine that the cell is sent out from the link  1 . Since all the links arriving to the access apparatus N are selected for one time, the table entries of the load balancing mask table are re-set as  0 , and written into the load balancing mask table. 
         [0076]    The load balancing processing methods in the second-stage and third-stage exchange apparatuses are identical to the above-mentioned processing method in the first-stage exchange apparatus, and will not be elaborated herein. 
         [0077]    In the above-mentioned process, the cells sent to the access apparatuses N−1 and N are sent in respective accessible links once in a polling way, and the above-mentioned steps are repeated for subsequent cells. As shown in  FIG. 4 , in this way, the cells arriving to the apparatuses N and N−1 may be equally allocated in all of their own accessible links, thereby achieving the aim of load balancing. 
         [0078]    The embodiments of the disclosure also provide a load balancing apparatus. As shown in  FIG. 5 , the apparatus is placed in an exchange apparatus at each stage, and includes: a link querying module  51  and a cell sending module  52 , wherein the link querying module  51  is arranged to query a unicast forwarding table according to an ID number of a destination access apparatus before each cell is sent, so as to obtain all links arriving to the destination access apparatus; and the cell sending module  52  is arranged to send, in all the links obtained by the link querying module, the cell arriving to the corresponding destination access apparatus in a polling way. 
         [0079]    During practical application, the link querying module  51  and the cell sending module  52  may be implemented by a Central Processing Unit (CPU), a Digital Signal Processor (DSP) or a Field-Programmable Gate Array (FPGA) in the load balancing apparatus. 
         [0080]    The cell sending module  52  is specifically arranged to: set, for the exchange apparatus at each stage, a corresponding load balancing mask table, and query the load balancing mask table while or after the unicast forwarding table is queried; 
         [0081]    perform an AND operation on query results about the unicast forwarding table and the load balancing mask table, and select a link having a smaller link number from an AND result via which the cell is sent; and 
         [0082]    set a mask corresponding to the selected link in the load balancing mask table as 0, with masks corresponding to the remaining unselected links unchanged, and write the modified mask back to the load balancing mask table. 
         [0083]    The cell sending module  52  includes a setting and querying module  521 , a calculating and selecting module  522  and a mask processing module  523 , as shown in  FIG. 6 , wherein 
         [0084]    the setting and querying module  521  is arranged to set, for the exchange apparatus at each stage, a corresponding load balancing mask table, and query the load balancing mask table while or after the unicast forwarding table is queried; 
         [0085]    the calculating and selecting module  522  is arranged to perform an AND operation on query results about the unicast forwarding table and the load balancing mask table, and select a link having a smaller link number from an AND result via which the cell is sent; and 
         [0086]    the mask processing module  523  is arranged to set a mask corresponding to the selected link in the load balancing mask table as 0, with masks corresponding to the remaining unselected links unchanged, and write the modified mask back to the load balancing mask table. 
         [0087]    During practical application, the setting and querying module  521 , the calculating and selecting module  522  and the mask processing module  523  may be implemented by a CPU, a DSP or an FPGA in the cell sending module  52 . 
         [0088]    In an embodiment of the disclosure, the load balancing mask table records the link selected for sending the cell and the unselected links. For example, the selected link corresponding to an ID number of a destination access apparatus and the unselected links may be correspondingly recorded in each row of the load balancing mask table. After all links corresponding to an ID number of a certain destination access apparatus are selected, table entries in this row are re-modified as all links accessible to the access apparatus. 
         [0089]    In an embodiment of the disclosure, the mask processing module  523  is further arranged to set initial values of table entries of the load balancing mask table corresponding to each destination access apparatus as 0, and write, after the unicast forwarding table is read and when no link is selected, all the read links into the load balancing mask table. 
         [0090]    In an embodiment of the disclosure, the mask processing module  523  is further arranged to: record, before all the links are selected, the selected link for sending the cell and the unselected links in the load balancing mask table; and 
         [0091]    re-modify, after all the links are selected, the table entries in the load balancing mask table as all links accessible to the access apparatus. 
         [0092]    In the embodiments of the disclosure, cells arriving to each destination access apparatus may be allocated to an accessible link in a balanced manner at an exchange apparatus at each stage by distinguishing the destination access apparatuses to which the cells arrive, so it may be ensured that the cells arriving to the destination access apparatus allocates data streams on all links in a balanced manner, thereby improving the utilization ratio of bandwidths and improving the exchange capability. 
         [0093]    Those skilled in the art shall understand that the embodiments of the disclosure may be provided as a method, a system or a computer program product. Thus, forms of hardware embodiments, software embodiments or embodiments integrating software and hardware may be adopted in the disclosure. Moreover, a form of the computer program product implemented on one or more computer available storage media (including, but are not limited to, a disk memory, an optical memory and the like) containing computer available program codes may be adopted in the disclosure. 
         [0094]    The disclosure is described with reference to flow charts and/or block diagrams of the method, the device (system) and the computer program product according to the embodiments of the disclosure. It will be appreciated that each flow and/or block in the flow charts and/or the block diagrams and a combination of the flows and/or the blocks in the flow charts and/or the block diagrams may be implemented by computer program instructions. These computer program instructions may be provided for a general computer, a dedicated computer, an embedded processor or processors of other programmable data processing devices to generate a machine, such that an apparatus for implementing functions designated in one or more flows of the flow charts and/or one or more blocks of the block diagrams is generated via instructions executed by the computers or the processors of the other programmable data processing devices. 
         [0095]    These computer program instructions may also be stored in a computer readable memory capable of guiding the computers or the other programmable data processing devices to work in a specific mode, such that a manufactured product including an instruction apparatus is generated via the instructions stored in the computer readable memory, and the instruction apparatus implements the functions designated in one or more flows of the flow charts and/or one or more blocks of the block diagrams. 
         [0096]    These computer program instructions may also be loaded to the computers or the other programmable data processing devices, such that processing implemented by the computers is generated by executing a series of operation steps on the computers or the other programmable devices, and therefore the instructions executed on the computers or the other programmable devices provide a step of implementing the functions designated in one or more flows of the flow charts and/or one or more blocks of the block diagrams. 
         [0097]    The above description is only the preferred embodiments of the disclosure and does not intended to limit the protection scope of the disclosure.