Load balancing method, load balancing system, load balancing device and topology reduction method

• US 10,432,709 B2
• Filed: 03/27/2017
• Issued: 10/01/2019
• Est. Priority Date: 03/28/2016
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chang, Shu-Hsin, Lu, Kun-Hsien, Hsiao, Yu-Hsien, Kao, Ching-Chun, Su, Yi-Yu
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US15/469,589
• Publication Number:
  US 20170279877A1
• Time in Patent Office: 918 Days
• Field of Search: 709223, 709224, 709226, 709232
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions

Abstract

The disclosure provides a load balancing method, a load balancing system, a load balancing device and a topology reduction method. The load balancing method includes configuring a transmission progress value for each of the edge servers; grouping the edge servers into server groups, wherein each of the edge servers is grouped into at least one server group among the server groups; receiving a download request corresponding to a first video stream from a user device, wherein a first server group among the server groups provides the first video stream; and selecting one of the edge servers from the edge servers of the first server group as a first edge server to provide video data of the first video stream to the user device according to the transmission progress values of the edge servers of the first server group.

Claims

1. A load balancing method, comprising:

configuring a transmission progress value for each of a plurality of edge servers, and grouping the plurality of edge servers into a plurality of server groups, wherein the edge servers of each of the plurality of server groups provide one of a plurality of video streams, and each of the plurality of edge servers is grouped into at least one server group among the plurality of server groups;

receiving a download request corresponding to a first video stream among the plurality of video streams from a user device;

selecting a first server group from the plurality of server groups according to the download request, wherein the first server group provides the first video stream;

selecting one edge server having a minimum transmission progress value from the edge servers of the first server group as a first edge server to provide video data of the first video stream to the user device according to the transmission progress values of the edge servers of the first server group;

calculating an increment and accumulating the increment to the transmission progress value of the first edge server; and

redirecting the download request to the first edge server.

2. The load balancing method according to claim 1, wherein the increment is calculated by dividing a size of the video data by a first bandwidth parameter of the first edge server, wherein the first bandwidth parameter is determined according to an outbound bandwidth of the first edge server.

3. The load balancing method according to claim 1, further comprising:

selecting a second edge server from the edge servers of the first server group, wherein a difference value between a transmission progress value of the second edge server and a minimum transmission progress value among the transmission progress values of the edge servers of the first server group is greater than or equal to an ineligible threshold, or wherein the difference value is greater than or equal to the ineligible threshold within a predetermined time;

removing the second edge server from the first server group; and

sending a message to an origin server corresponding to the first video stream or the second edge server to stop the video data of the first video stream from being synchronized to the second edge server.

4. The load balancing method according to claim 1, further comprising:

if an average bandwidth usage rate of the rest of the edge servers is less than a medium load threshold after one of the edge servers is removed, performing steps of;

selecting a fifth edge server from the edge servers and calculating a bandwidth usage amount of the fifth edge server;

selecting at least one sixth edge server from the edge servers other than the fifth edge server, wherein a sum of a bandwidth difference of each of the at least one sixth edge server between a bandwidth usage amount of the at least one sixth edge server and a bandwidth amount reaching the medium load threshold is greater than the bandwidth usage amount of the fifth edge server;

synchronizing video data of each of video streams provided in correspondence to the fifth edge server to the at least one sixth edge server;

resetting the transmission progress values of the edge servers;

adding the at least one sixth edge server into the server groups corresponding to the video streams provided by the fifth edge server; and

removing the fifth edge server from the server groups.

5. The load balancing method according to claim 4, wherein the step of synchronizing the video data of the video stream provided in correspondence to the fifth edge server to the at least one sixth edge server further comprises:

filling the bandwidth usage amount of each video stream provided by the fifth edge server at the fifth edge server to the bandwidth difference of the sixth edge server to determine the at least one sixth edge server corresponding to each video stream of the fifth edge server; and

sending a message to an origin server corresponding to each video stream provided by the fifth edge server or the sixth edge server corresponding to each video stream provided by the fifth edge server to synchronize video data of each video stream provided by the fifth edge server to the at least one sixth edge server corresponding to each video stream.

6. The load balancing method according to claim 5, wherein the step of adding the at least one sixth edge server into the server group corresponding to the video stream provided by the fifth edge server further comprises:

adding the at least one sixth edge server corresponding to each video stream provided by the fifth edge server into a server group corresponding to each video stream provided by the fifth edge server respectively.

7. A load balancing system, comprising:

a plurality of edge servers;

a plurality of origin servers coupled to the plurality of edge servers, wherein each of the plurality of origin servers generates at least one of a plurality of video streams, video data of each of the plurality of video streams is synchronized to at least one of the plurality of edge servers; and

a load balancing device coupled to the plurality of origin servers and the plurality of edge servers,

wherein the load balancing device configures a transmission progress value for each of the plurality of edge servers,

wherein the load balancing device groups the plurality of edge servers into a plurality of server groups, wherein the edge servers of each of the plurality of server groups provide one of the plurality of video stream, and each of the plurality of edge servers is grouped into at least one server group among the plurality of server groups,

wherein the load balancing device receives a download request for a video stream among the video streams from a user device, wherein a first server group among the server groups provides the first video stream,

wherein the load balancing device selects one edge server having a minimum transmission progress value from the edge servers of the first server group as a first edge server to provide video data of the first video stream to the user device according to the transmission progress values of the edge servers of the first server group,

wherein the load balancing device calculates an increment and accumulates the increment to the transmission progress value of the first edge server,

wherein the load balancing device redirects the download request to the first edge server.

8. The load balancing system according to claim 7, wherein the increment is calculated by dividing a size of the video data by a first bandwidth parameter of the first edge server, wherein the first bandwidth parameter is determined according to an outbound bandwidth of the first edge server.

9. The load balancing system according to claim 7,

wherein the load balancing device selects a second edge server from the edge servers of the first server group, wherein a difference value between a transmission progress value of the second edge server and a minimum transmission progress value among the transmission progress values of the edge servers of the first server group is greater than or equal to an ineligible threshold, or wherein the difference value is greater than or equal to the ineligible threshold within a predetermined time,

wherein the load balancing device removes the second edge server from the first server group,

wherein the load balancing device sends a message to the origin server corresponding to the first video stream or the second edge server to stop the video data of the first video stream from being synchronized to the second edge server.

10. The load balancing system according to claim 7,

wherein if an average bandwidth usage rate of the rest of the edge servers is less than a medium load threshold after one of the edge servers is removed, the load balancing device performs steps of:

selecting a fifth edge server from the edge servers and calculating a bandwidth usage amount of the fifth edge server;

selecting at least one sixth edge server from the edge servers other than the fifth edge server, wherein a sum of a bandwidth difference of each of the at least one sixth edge server between a bandwidth usage amount of the at least one sixth edge server and a bandwidth amount reaching the medium load threshold is greater than the bandwidth usage amount of the fifth edge server;

synchronizing video data of each of video streams provided in correspondence to the fifth edge server to the at least one sixth edge server;

resetting the transmission progress values of the edge servers;

adding the at least one sixth edge server into the server groups corresponding to the video streams provided by the fifth edge server; and

removing the fifth edge server from the server groups.

11. The load balancing system according to claim 10, wherein the load balancing device fills a bandwidth usage amount of each video stream provided by the fifth edge server at the fifth edge server in the bandwidth difference of the at least one sixth edge server to determine the at least one sixth edge server corresponding to each video stream of the fifth edge server,

wherein the load balancing device sends a message to the origin server corresponding to each video stream provided by the fifth edge server or the at least one sixth edge server corresponding to each video stream provided by the fifth edge server to synchronize video data of each video stream provided by the fifth edge server to the at least one sixth edge server corresponding to each video stream provided by the fifth edge server.

12. The load balancing system according to claim 11, wherein the load balancing device adds the at least one sixth edge server corresponding to each video stream provided by the fifth edge server into a server group corresponding to each video stream provided by the fifth edge server respectively.

13. A load balancing device, comprising a processing unit and a communication unit, wherein the load balancing device is coupled to a plurality of origin servers and a plurality of edge servers through the communication unit, the plurality of origin servers are coupled to the plurality of edge servers, each of the plurality of origin servers generates at least one of a plurality of video streams, and video data of each of the plurality of video streams is synchronized to at least one of the plurality of edge servers,

wherein the processing unit configures a transmission progress value for each of the plurality of edge servers,

wherein the processing unit groups the plurality of edge servers into a plurality of server groups, wherein the edge servers of each of the plurality of server groups provide one of the plurality of video stream, and each of the plurality of edge servers is grouped into at least one server group among the plurality of server groups,

wherein the processing unit receives a download request corresponding to a first video stream among the video streams from a user device, wherein a first server group among the plurality of server groups provides the first video stream;

and

wherein the processing unit selects one edge server having a minimum transmission progress value from the edge servers of the first server group as a first edge server to provide video data of the first video stream to the user device according to the transmission progress values of the edge servers of the first server group,

wherein the processing unit calculates an increment and accumulates the increment to the transmission progress value of the first edge server,

wherein the processing unit redirects the download request to the first edge server.

14. The load balancing device according to claim 13, wherein the increment is calculated by dividing a size of the video data by a first bandwidth parameter of the first edge server, wherein the first bandwidth parameter is determined according to an outbound bandwidth of the first edge server.

15. The load balancing device according to claim 13,

wherein the processing unit selects a second edge server from the edge servers of the first server group, wherein a difference value between a transmission progress value of the second edge server and a minimum transmission progress value among the transmission progress values of the edge servers of the first server group is greater than or equal to an ineligible threshold, or wherein the difference value is greater than or equal to the ineligible threshold within a predetermined time,

wherein the processing unit removes the second edge server from the first server group,

wherein the communication unit sends a message to the origin server corresponding to the first video stream or the second edge server to stop the video data of the first video stream from being synchronized to the second edge server.

16. The load balancing device according to claim 13,

wherein if an average bandwidth usage rate of the rest of the edge servers is less than a medium load threshold after one of the edge servers is removed, the processing unit performs steps of:

selecting a fifth edge server from the edge servers and calculating a bandwidth usage amount of the fifth edge server;

selecting at least one sixth edge server from the edge servers other than the fifth edge server, wherein a sum of a bandwidth difference of each of the at least one sixth edge server between a bandwidth usage amount of the at least one sixth edge server and a bandwidth amount reaching the medium load threshold is greater than the bandwidth usage amount of the fifth edge server;

synchronizing video data of each of video streams provided in correspondence to the fifth edge server to the at least one sixth edge server;

resetting the transmission progress values of the edge servers;

adding the at least one sixth edge server into the server groups corresponding to the video streams provided by the fifth edge server; and

removing the fifth edge server from the first server group.

17. The load balancing device according to claim 16,

wherein the processing unit fills a bandwidth usage amount of each video stream provided by the fifth edge server at the fifth edge server in the bandwidth difference of the at least one sixth edge server to determine the at least one sixth edge server corresponding to each video stream of the fifth edge server,

wherein the communication unit sends a message to the origin server corresponding to each video stream provided by the fifth edge server or the sixth edge server corresponding to each video stream provided by the fifth edge server to synchronize video data of each video stream provided by the fifth edge server to the at least one sixth edge server corresponding to each video stream provided by the fifth edge server.

18. The load balancing device according to claim 17, wherein the processing unit adds the at least one sixth edge server corresponding to each video stream provided by the fifth edge server into a server group corresponding to each video stream provided by the fifth edge server respectively.

19. A topology reduction method, comprising:

configuring a transmission progress value for each of a plurality of edge servers, and grouping the plurality of edge servers into a plurality of server groups, the edge servers of each of the plurality of server groups provide one of a plurality of video streams, and each of the edge servers is grouped into at least one server group among the plurality of server groups;

receiving a download request corresponding to a first video stream among the video streams from a user device;

selecting a first server group from the plurality of server groups according to the download request, wherein the first server group provides the first video stream;

selecting one edge server from the edge servers of the first server group as a first edge server to provide video data of the first video stream to the user device according to the transmission progress values of the edge servers of the first server group;

selecting a second edge server from the edge servers of the first server group, a difference value between a transmission progress value of the second edge server and a minimum transmission progress value among the transmission progress values of the edge servers of the first server group is greater than or equal to an ineligible threshold, or wherein the difference value is greater than or equal to the ineligible threshold within a predetermined time;

removing the second edge server from the first server group; and

stopping the video data of the first video stream from being synchronized to the second edge server.