System and method for digital media server load balancing

• US 7,912,954 B1
• Filed: 06/27/2003
• Issued: 03/22/2011
• Est. Priority Date: 06/27/2003
• Status: Active Grant

• Current Assignee: Xylon LLC (Intellectual Ventures LLC)
• Original Assignee: Beach Unlimited LLC (Intellectual Ventures LLC)
• Inventors: Oesterreicher, Richard T., Murphy, Craig
• Primary Examiner(s): Bruckart; Benjamin R
• Application Number:
  US10/609,426
• Time in Patent Office: 2,825 Days
• Field of Search: 709217-219, 709227-229, 709/226, 714 4- 6
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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/1012 based on compliance of requirements or conditions with available server resources

Abstract

A system and method for load balancing a plurality of servers is disclosed. In a preferred embodiment, a plurality of servers in a video-on-demand or other multi-server system are divided into one or more load-balancing groups. Each server preferably maintains state information concerning other servers in its load-balancing group including information concerning content maintained and served by each server in the group. Changes in a server'"'"'s content status or other state information are preferably proactively delivered to other servers in the group. When a content request is received by any server in a load-balancing group, it evaluates the request in accordance with a specified algorithm to determine whether it should deliver the requested content itself or redirect the request to another server in its group. In a preferred embodiment, this determination is a function of information in the server'"'"'s state table.

Claims

1. A method for selecting a server from a plurality of servers to service a third request for an asset, comprising:

generating, at an adaptable cache of a first server, a list of pairs of requests for the asset and determining a pair of requests having the shortest interval between start times, wherein the pair of requests comprise a first request and a second request;

responsive to the first request, streaming the asset from a storage system of the first server and storing the asset on the adaptable cache of the first server as it is being streamed from the storage system of the first server;

responsive to the second request streaming the asset from the adaptable cache of the first server;

updating a first state table on the first server with information about the asset stored on the adaptable cache of the first server;

communicating the information about the asset stored on the adaptable cache of the first server to each server in the plurality of servers;

updating state tables of each of the other servers in the plurality of servers with the information about the asset stored on the adaptable cache of the first server;

designating a director from the plurality of servers to receive the third request, wherein any of the plurality of servers can be designated as the director;

determining that the asset is not stored on an adaptable cache of the director by accessing a director'"'"'s state table stored on the director, wherein the director'"'"'s state table includes parametric information for each server in the plurality of servers, and wherein the parametric information comprises adaptable cache contents information for each server in the plurality of servers; and

under the direction of the director,

determining a set of servers from among said plurality of servers that have the asset stored in their respective adaptable caches by examining the state table on the director;

determining a load factor for each of the set of servers; and

selecting a second server from among the set of servers based on the load factor.

2. The method of claim 1, wherein designating the director comprises designating the director in a round-robin fashion.

3. The method of claim 1, wherein the director is designated based on a load factor analysis for each server among said plurality of servers, the load factor for each server based on parametric information stored in a respective state table thereon, and wherein the designated director has a lowest load factor.

4. The method of claim 1, further comprising designating the director upon determining that the asset is present on the director.

5. The method of claim 1, wherein said parametric information further comprises functional state and current load of each server.

6. The method of claim 1, wherein said parametric information further comprises whether each server comprises extended memory.

7. The method of claim 1, wherein said parametric information further comprises whether each server comprises an inline adaptable cache.

8. The method of claim 1, wherein said parametric information further comprises whether each asset represented in the parametric information is a new release.

9. The method of claim 1, further comprising storing the asset on the adaptable cache of the director responsive to the third request.

10. The method of claim 1, further comprising forwarding the third request to the second server.

11. The method of claim 1, further comprising redirecting the third request to the second server.

12. The method of claim 1, wherein selecting the second server from among the set of servers further comprises:

identifying as available servers any servers whose load factors are below threshold limits;

determining that there are no available servers; and

upon determining that there are no available servers, selecting a server having a lowest load factor from the other servers having the content.

13. The method of claim 1, further comprising updating parametric information in a second state table on the second server, and communicating updated parametric information to the other servers among said plurality of servers.

14. The method of claim 13, wherein the updated parametric information is communicated via multicast.

15. The method of claim 13, wherein the updated parametric information is communicated via a broadcast message.

25. The method of claim 1, further comprising updating parametric information in a second state table associated with the selected on the second server, and communicating updated parametric information to the other servers among said plurality of servers.

16. A computer-readable medium comprising computer-executable instructions for performing a method comprising:

generating, at an adaptable cache of a first server, a list of pairs of requests for an asset and determining a pair of requests having the shortest interval between start times, wherein the pair of requests comprise a first request and a second request;

responsive to the first request, streaming the asset from a storage system of the first server and storing the asset on the adaptable cache of the first server as it is being streamed from the storage system of the first server;

responsive to the second request, streaming the asset from the adaptable cache of the first server;

updating a first state table on the first server with information about the asset stored on the adaptable cache of the first server, wherein the first server communicates the information about the asset stored on the adaptable cache of the first server to each server in the plurality of servers, and wherein each server in the plurality of servers updates each state table of each server in the plurality of servers with the information about the asset stored on the adaptable cache of the first server;

designating a director from the plurality of servers to receive a third request, wherein any of the plurality of servers can be designated as the director;

determining that the asset is not stored on an adaptable cache of the director by accessing a state table stored on the director, wherein the state table includes parametric information for each server in the plurality of servers, and wherein the parametric information comprises adaptable cache contents information for each server in the plurality of servers; and

under the direction of the director,

determining a set of servers from among said plurality of servers that have the asset stored in their respective adaptable caches by examining the state table on the director;

determining a load factor for each of the set of servers; and

,

selecting a second server from among the set of servers based on the load factor.

17. The computer-readable medium of claim 16, wherein designating the director comprises designating the director in a round-robin fashion.

18. The computer-readable medium of claim 16, wherein designating the director comprises designating the director on the basis of lowest load.

19. The computer-readable medium of claim 16, wherein designating the director further comprises designating the director if the requested content is present on the director.

20. The computer-readable medium of claim 16, wherein said parametric information further comprises functional state and current load of each server.

21. The computer-readable medium of claim 16, wherein said parametric information further comprises whether each server comprises extended memory.

22. The computer-readable medium of claim 16, wherein said parametric information further comprises whether each server comprises an inline adaptable cache.

23. The computer-readable medium of claim 16, wherein said parametric information further comprises whether each asset represented in the parametric information is a new release.

24. The computer-readable medium of claim 16, further comprising computer-executable instructions for storing the asset on the adaptable cache of the director responsive to the third request.

26. The computer-readable medium of claim 16, further comprising computer-executable instructions for redirecting the third request to the second server.

27. The computer-readable medium of claim 16, wherein the step of selecting the second server from among the set of servers further comprises:

identifying as available servers one or more servers whose load factors are below threshold limits;

determining that there are no available servers; and

upon determining that there are no available servers, selecting a server having a lowest load factor from the other servers having the content.

28. A system for servicing a request for an asset, comprising:

an adaptable cache of a first server configured to generate a list of pairs of requests for the asset and determine a pair of requests having the shortest interval between start times, wherein the pair of requests comprise a first request and a second request;

a storage system of the first server configured to stream the asset responsive to the first request;

the adaptable cache of the first server further configured to store the asset as the asset is streamed from the storage system of the first server;

the adaptable cache of the first server configured to stream the asset responsive to the second request;

the first server configured to update a first state table with information about the asset stored on the adaptable cache of the first server;

the first server further configured to communicate the information about the asset stored on the adaptable cache of the first server to each server in the plurality of servers;

each server in the plurality of servers configured to update their respective state tables with the information about the asset stored on the adaptable cache of the first server;

a business management system configured to designate a director from the plurality of servers to receive the third request, wherein any of the plurality of servers can be designated as the director;

the director configured to determine that the asset is not stored on an adaptable cache of the director by accessing a director'"'"'s state table, wherein the director'"'"'s state table includes parametric information for each server in the plurality of servers, and wherein the parametric information comprises adaptable cache contents information for each server in the plurality of servers; and

the director further configured to;

determine a set of servers from among said plurality of servers that have the asset stored in their respective adaptable caches by examining the director'"'"'s state table,

determine a load factor for each of the set of servers; and

select a second server from among the set of servers based on the load factor.

29. The system of claim 28, wherein the business management system configured to designate the director comprises the business management system configured to designate the director in a round-robin fashion.

30. The system of claim 28, wherein the business management system configured to designate the director comprises the business management system configured to designate the director based on a load factor analysis for each server among the plurality of servers, the load factor for each server based on parametric information stored in a respective state table thereon, and wherein the designated director has a lowest load factor.

31. The system of claim 28, wherein the business management system configured to designate the director comprises the business management system configured to designate the director upon determining that the asset is present on the director.

32. The system of claim 28, wherein said parametric information further comprises at least one of a functional state of each server, a current load of each server, whether each server comprises extended memory, whether each server comprises an inline adaptable cache, and whether each asset represented in the parametric information is a new release.

33. The system of claim 28, wherein the director is further configured to perform at least one of storing the asset on the adaptable cache of the director responsive to the third request, forwarding the third request to the second server, and redirecting the third request to the second server.

34. The system of claim 28, wherein the director configured to select the second server from among the set of servers further comprises the director configured to:

identify as available servers any servers whose load factors are below threshold limits;

determine that there are no available servers; and

upon determining that there are no available servers, select a server having a lowest load factor from the other servers having the content.

35. The system of claim 28, further comprising updating parametric information in a second state table on the second server, and communicating updated parametric information to the other servers among said plurality of servers.

36. A system for servicing a request for an asset, comprising:

an adaptable cache means of a first server for generating a list of pairs of requests for the asset and determining a pair of requests having the shortest interval between start times, wherein the pair of requests comprise a first request and a second request;

means for streaming, responsive to the first request, the asset from a storage system of the first server and storing the asset on the adaptable cache means of the first server as it is being streamed from the storage system of the first server;

means for streaming the asset from the adaptable cache means of the first server responsive to the second request;

means for updating a first state table on the first server with information about the asset stored on the adaptable cache means of the first server;

means for communicating the information about the asset stored on the adaptable cache means of the first server to each server in the plurality of servers;

means for updating state tables of each of the other servers in the plurality of servers with the information about the asset stored on the adaptable cache means of the first server;

means for designating a director from the plurality of servers to receive the third request, wherein any of the plurality of servers can be designated as the director;

means for determining that the asset is not stored on an adaptable cache of the director by accessing a director'"'"'s state table stored on the director, wherein the director'"'"'s state table includes parametric information for each server in the plurality of servers, and wherein the parametric information comprises adaptable cache contents information for each server in the plurality of servers; and

means under the direction of the director for;

determining a set of servers from among said plurality of servers that have the asset stored in their respective adaptable caches by examining the state table on the director;

determining a load factor for each of the set of servers; and

selecting a second server from among the set of servers based on the load factor.