Network server and load balancing routing method for networks thereof

• US 8,862,775 B2
• Filed: 11/26/2010
• Issued: 10/14/2014
• Est. Priority Date: 11/26/2010
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chiueh, Tzi-Cker, Hsu, Ming-Chao, Tu, Cheng-Chun
• Primary Examiner(s): Golabbakhsh, Ebrahim
• Application Number:
  US12/954,677
• Publication Number:
  US 20120137021A1
• Time in Patent Office: 1,418 Days
• Field of Search: 709239-242, 709/232, 709/221, 709/226, 709/229
• US Class Current: 709/241
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A load balancing routing method for networks is disclosed. The routing method includes following steps. A network topology graph and a plurality of expected bandwidth demands corresponding to a plurality of source-destination pairs are received by a network server. A plurality of link criticalities of a plurality of links established according to the source-destination pairs is calculated by the network server according to the network topology graph and the expected bandwidth demands. A plurality of expected loads of the links is calculated by the network server according to the link criticalities. A plurality of cost values is calculated according to a plurality of residual capacities of the links and the corresponding expected loads. A better transmission path corresponding to each of the source-destination pairs is selected by the network server according to the weighted sum of the cost values corresponding to the links in the source-destination pair.

Claims

1. A load balancing routing method for networks, comprising:

receiving a network topology graph and a plurality of expected bandwidth demands corresponding to a plurality of source-destination pairs by using a network server;

calculating a plurality of link criticalities of a plurality of links established based on the source-destination pairs according to the network topology graph and the expected bandwidth demands and calculating a plurality of expected loads of the links according to the link criticalities by using the network server, and the link criticality corresponding to each of the links is y/x, wherein x is a total number of paths between the source-destination pairs, y is a number of paths between the source-destination pairs that pass through the link, and the expected load of each of the links is equal to a sum of products between the link criticalities and the expected bandwidth demands of the link corresponding to all source-destination pairs;

calculating a plurality of cost values according to a plurality of residual capacities and the corresponding expected loads of the links by using the network server, wherein each of the cost values is obtained by dividing the expected load corresponding to each of the links by the residual capacity corresponding to the link; and

selecting a better transmission path corresponding to each of the source-destination pairs according to a weighted sum of the cost values corresponding to the links in the source-destination pair by using the network server.

2. The routing method according to claim 1, wherein the step of “

selecting the better transmission path corresponding to each of the source-destination pairs according to the weighted sum of the cost values corresponding to the links in the source-destination pair by using the network server”

comprises;

selecting a plurality of candidate transmission paths according to the weighted sum of the cost values corresponding to the links in each of the source-destination pairs by using the network server; and

selecting the better transmission path by the weighted sum which obtained according to a plurality of forwarding tables in the transmission paths by using the network server.

3. The routing method according to claim 2, wherein the step of “

selecting the better transmission path according to the forwarding tables in the transmission paths by using the network server”

comprises;

calculating a total quantity of forwarded information recorded in the forwarding tables and selecting the transmission path having the smallest total quantity among the transmission paths as the better transmission path by using the network server.

4. The routing method according to claim 1 further comprising:

arranging a processing sequence of the source-destination pairs according to the expected bandwidth demands by using the network server.

5. The routing method according to claim 1 further comprising:

updating the expected bandwidth demands according to the better transmission path by using the network server.

6. The routing method according to claim 1 further comprising:

detecting a congestion link among the links by using the network server; and

removing the congestion link from the links of the source-destination pairs by using the network server.

7. The routing method according to claim 6 further comprising:

re-arranging the processing sequence of the source-destination pairs after the congestion link is removed according to the expected bandwidth demands by using the network server.

8. The routing method according to claim 1 further comprising:

selecting at least one second-better transmission path corresponding to each of the source-destination pairs as at least one backup transmission path according to a weighted sum of the cost values corresponding to the links in the source-destination pair.

9. The routing method according to claim 8 further comprising:

when the better transmission path comprises a congestion link, replacing the better transmission path with the backup transmission path as a new better transmission path.

10. The routing method according to claim 1, wherein the step of “

selecting the better transmission path corresponding to each of the source-destination pairs according to the weighted sum of the cost values corresponding to the links in the source-destination pair by using the network server”

comprising;

selecting a plurality of candidate transmission paths according to a plurality sums of the cost values; and

selecting the better transmission path among the candidate transmission paths according to the weighted sum of the cost values.

11. The routing method according to claim 10, wherein the weighted sum is operated according to at least one of a plurality of forwarding table entries of each of the candidate transmission paths, hop counts of each of the candidate transmission paths and sum processor'"'"'s speed of switches along each of the candidate transmission paths.

12. A network server, comprising:

a processor, used to receive a network topology graph and a plurality of expected bandwidth demands corresponding to a plurality of source-destination pairs, and calculates a plurality of link criticalities of a plurality of links established based on the source-destination pairs according to the network topology graph and the expected bandwidth demands and calculates a plurality of expected loads of the links according to the link criticalities, wherein the link criticality corresponding to each of the links is y/x, wherein x is a total number of paths between the source-destination pairs, y is a number of paths between the source-destination pairs that pass through the link, and the expected load of each of the links is equal to a sum of products between the link criticalities and the expected bandwidth demands of the link corresponding to all source-destination pairs, the processor further calculates a plurality of cost values according to a plurality of residual capacities and the corresponding expected loads of the links, wherein each of the cost values is obtained by dividing the expected load corresponding to each of the links by the residual capacity corresponding to the link, and the processor selects a better transmission path corresponding to each of the source-destination pairs according to a weighted sum of the cost values corresponding to the links in the source-destination pair.

13. The network server according to claim 12, the processor selects a plurality of candidate transmission paths according to the weighted sum of the cost values corresponding to the links in each of the source-destination pairs by using the network server and selects the better transmission path by the weighted sum which obtained according to a plurality of forwarding tables in the transmission paths.

14. The network server according to claim 13, the processor calculates a total quantity of forwarded information recorded in the forwarding tables and selecting the transmission path having the smallest total quantity among the transmission paths as the better transmission path.

15. The network server according to claim 12, the processor arranges a processing sequence of the source-destination pairs according to the expected bandwidth demands.

16. The network server according to claim 12, the processor updates the expected bandwidth demands according to the better transmission path.

17. The network server according to claim 15, the processor detects a congestion link among the links by using the network server, and removes the congestion link from the links of the source-destination pairs.

18. The network server according to claim 17, the processor further re-arranges the processing sequence of the source-destination pairs after the congestion link is removed according to the expected bandwidth demands.

19. The network server according to claim 12, the processor selects at least one second-better transmission path corresponding to each of the source-destination pairs as at least one backup transmission path according to a weighted sum of the cost values corresponding to the links in the source-destination pair.

20. The network server according to claim 19, when the better transmission path comprises a congestion link, the processor replaces the better transmission path with the backup transmission path as a new better transmission path.

21. The network server according to claim 12, the processor selects a plurality of candidate transmission paths according to a plurality sums of the cost values, and selects the better transmission path among the candidate transmission paths according to the weighted sum of the cost values.

22. The network server according to claim 21, the weighted sum is operated according to at least one of a plurality of forwarding table entries of each of the candidate transmission paths, hop counts of each of the candidate transmission paths and sum processor'"'"'s speed of switches along each of the candidate transmission paths.