Method and system for load balancing over a set of communication channels

• US 8,341,266 B2
• Filed: 03/22/2005
• Issued: 12/25/2012
• Est. Priority Date: 10/06/2004
• Status: Active Grant

• Current Assignee: Hughes Network Systems LLC (Echostar Corporation)
• Original Assignee: Hughes Network Systems LLC (Echostar Corporation)
• Inventors: Olariu, Gabriel L., Ragland, Roderick, Kelly, Frank
• Primary Examiner(s): LI, GUANG W
• Application Number:
  US11/085,954
• Publication Number:
  US 20060072452A1
• Time in Patent Office: 2,835 Days
• Field of Search: 709/226, 725/95, 455/266, 455/452.1
• US Class Current: 709/226
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04W 28/082 among bearers or channels
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

An approach for load balancing is disclosed. A user load is determined based upon data queued for transmission at each of the terminals. In addition, an inroute load corresponding to loading of inroutes serving the terminals is determined. A user-to-inroute distribution that minimizes variation of the inroute load is generated. The user-to-inroute distribution maps the user load to the inroutes. The user load is reassigned to the inroutes based on the determined user-to-inroute distribution. This arrangement has particular applicability to a satellite network that provides data communication services.

Claims

1. A method for providing load balancing in a communication system including a plurality of terminals, the method comprising:

determining a user load based upon data queued for transmission at each of the terminals;

generating a user load vector based on the user load;

sorting the user load vector to identify a more loaded terminal;

determining an inroute load corresponding to loading of inroutes serving the terminals;

generating an inroute load vector based on the inroute load;

sorting the inroute load vector to determine a less loaded inroute;

determining variance of the inroute load vector;

determining a load change for a maximum reduction in the variance of the inroute load vector;

determining a first terminal with a load that matches the load change based on the user load vector;

outputting a user-to-inroute distribution that minimizes variation of the inroute load, the user-to-inroute distribution mapping the user load to the inroutes; and

reassigning the user load to the inroutes based on the determined user-to-inroute distribution from a central hub including moving the load of the first terminal to the less loaded inroute, wherein

the reassignment of the user load to the inroutes is independent of decisions at the terminals and allocation and redistribution of bandwidth is obtained at the plurality of terminals without an externally provided command.

2. The method according to claim 1, wherein the terminals are associated with a common Quality of Service (QoS) level.

3. The method according to claim 1, wherein

the more loaded terminal is the most loaded terminal;

and

the less loaded inroute is the least loaded inroute.

4. The method according to claim 3, wherein the communication system is a satellite network.

5. The method according to claim 4, wherein the inroutes are Time Division Multiple Access (TDMA) streams.

6. A non-transitory computer-readable storage medium having instructions providing load balancing in a communication system including a plurality of terminals, the instruction executable to cause one or more processors to perform the following:

determining a user load based upon data queued for transmission at each of the terminals;

generating a user load vector based on the user load;

sorting the user load vector to identify a more loaded terminal;

determining an inroute load corresponding to loading of inroutes serving the terminals;

generating an inroute load vector based on the inroute load;

sorting the inroute load vector to determine a less loaded inroute;

determining variance of the inroute load vector;

determining a load change for a maximum reduction in the variance of the inroute load vector;

determining a first terminal with a load that matches the load change based on the user load vector;

outputting a user-to-inroute distribution that minimizes variation of the inroute load, the user-to-inroute distribution mapping the user load to the inroutes; and

reassigning the user load to the inroutes based on the determined user-to-inroute distribution from a central hub including moving the load of the first terminal to the less loaded inroute, wherein

the reassignment of the user load to the inroutes is independent of decisions at the terminals and allocation and redistribution of bandwidth is obtained at the plurality of terminals without an externally provided command.

7. An apparatus for providing load balancing in a communication system including a plurality of terminals, the apparatus comprising:

a memory configured to store a user load based upon data queued for transmission at each of the terminals, the memory being further configured to store an inroute load corresponding to loading of inroutes serving the terminals; and

a processor configured to;

generate a user load vector based on the user load, sort the user load vector to identify a more loaded terminal,

generate an inroute load vector based on the inroute load;

sort the inroute load vector to determine a less loaded inroute;

determine variance of the inroute load vector;

determine a load change for a maximum reduction in the variance of the inroute load vector;

determine a first terminal with a load that matches the load change based on the user load vector

output a user-to-inroute distribution that minimizes variation of the inroute load, the user-to-inroute distribution mapping the user load to the inroutes,

wherein the user load is reassigned to the inroutes based on the determined user-to-inroute distribution, including moving the load of the first terminal to the less loaded inroute, and independent of decisions at the terminals, and allocation and redistribution of bandwidth is obtained at the plurality of terminals without an externally provided command.

8. The apparatus according to claim 7, wherein the terminals are associated with a common Quality of Service (QoS) level.

9. The apparatus according to claim 7, wherein

the more loaded terminal is the most loaded terminal;

and

the less loaded inroute is the least loaded inroute.

10. The apparatus according to claim 9, wherein the communication system is a satellite network.

11. The apparatus according to claim 10, wherein the inroutes are Time Division Multiple Access (TDMA) streams.

12. A method for providing load balancing in a communication system including a plurality of terminals, the method comprising:

generating at least one load vector for a plurality of communication channels based on at least one of a user load based upon data queued for transmission and an inroute load corresponding to loading of inroutes serving the terminals;

sorting the at least one load vector to identify at least one of a more loaded terminal and a less loaded inroute;

determining variance of the at least one load vector;

determining a load change for a maximum reduction in the variance of the at least one load vector;

outputting a load value that generates a maximum reduction in the variance;

identifying a first terminal having a user load corresponding to the load value; and

causing a central hub to assign the first terminal to the less loaded inroute to move the load of the first terminal to the less loaded inroute independent of any decision by the terminal, wherein

allocation and redistribution of bandwidth is obtained at the plurality of terminals without an externally provided command.

13. The method according to claim 12, wherein the terminals are associated with a common Quality of Service (QoS) level.

14. The method according to claim 12, wherein the communication system is a satellite network.

15. The method according to claim 14, wherein the inroutes are Time Division Multiple Access (TDMA) streams.

16. A non-transitory computer-readable storage medium having instructions providing load balancing in a communication system including a hub communicating with a plurality of terminals, the instructions executable to cause one or more processors to perform the following:

generating at least one load vector for a plurality of communication channels based on at least one of a user load based upon data queued for transmission and an inroute load corresponding to loading of inroutes serving the terminals;

sorting the at least one load vector to identify at least one of a more loaded terminal and a less loaded inroute;

determining variance of the at least one load vector;

outputting a load value that generates a maximum reduction in the variance;

identifying a first terminal having a user load corresponding to the load value; and

causing the central hub to assign the first terminal to the less loaded inroute to move the load of the first terminal to the less loaded inroute independent of any decision by the terminal, wherein

allocation and redistribution of bandwidth is obtained at the plurality of terminals without a command provided by the hub.

17. A hub device for providing load balancing in a communication system including a plurality of terminals, the system comprising:

means for generating at least one load vector for a plurality of communication channels based on at least one of a user load based upon data queued for transmission and an inroute load corresponding to loading of inroutes serving the terminals;

means for sorting the at least one load vector to identify at least one of a more loaded terminal and a less loaded inroute;

means for determining variance of the at least one load vector;

means for determining a load change for a maximum reduction in the variance of the at least one load vector;

means for outputting a load value that generates a maximum reduction in the variance;

means for identifying a first terminal having a user load corresponding to the load value; and

means for assigning the first terminal to the less loaded inroute to move the load of the first terminal to the less loaded inroute independent of any decision by the terminal, wherein

allocation and redistribution of bandwidth is obtained at the plurality of terminals without a command provided by the hub.

18. The device according to claim 17, wherein the terminals are associated with a common Quality of Service (QoS) level.

19. The device according to claim 17, wherein the communication system is a satellite network.

20. The device according to claim 19, wherein the inroutes are Time Division Multiple Access (TDMA) streams.