Optimized Consistent Request Distribution for Balanced Load Distribution in a Content Delivery Network

• US 20160164964A1
• Filed: 02/03/2016
• Published: 06/09/2016
• Est. Priority Date: 01/09/2013
• Status: Active Grant

• Current Assignee: Edgio Incorporated
• Original Assignee: EdgeCast Networks (Verizon Communications Inc.)
• Inventors: Yeager, Donnevan Scott, Hartrick, Timothy W., Peters, Robert J.
• Granted Patent: US 10,116,737 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 61/2528 Translation at a proxy
• 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/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Some embodiments provide a proprietary 64-bit consistent distribution scheme that preserves the efficiencies of CARP while providing a significantly more balanced distribution of requests that is on par with schemes reliant on computationally expensive cryptographic hashes. The scheme performs hashing of requested URLs and identifiers of available servers over a 64-bit space while optimizing the hashing to remove computationally expensive operations. Some embodiments provide a variant of the scheme to provide a differentiated distribution on the basis of one or more differentiating factors. A first variant utilizes load factor values to adjust the resulting hashes and to produce a first distribution of differentiated content that varies from a second distribution of undifferentiated content. A second variant identifies requests for differentiated content from requests for undifferentiated content and utilizes a first scheme to distribute the differentiated content and a second altered scheme to distribute the undifferentiated content.

Claims

1. A method comprising:

receiving a plurality of requests over the Internet at a load distribution server allocating the plurality of requests across a plurality of distribution servers, the plurality of requests comprising a first set of requests directed to a first content type and a second set of requests directed to at least a different second content type, the load distribution server comprising a processor and memory storing an identifier identifying each server of the plurality of distribution servers, the processor;

producing a hash result for each server of the plurality of distribution servers, wherein said producing comprises hashing the identifier identifying each server of the plurality of distribution servers;

distributing the first set of requests across a first set of the plurality of distribution servers by adjusting the hash result produced for each server of the first set of distribution servers with at least a first load factor value and by selecting a server from the first set of distribution servers to receive each request from the first set of requests based on the hash result of each server of the first set of distribution servers as adjusted by the first load factor value, the first load factor value increasing selection precedence of any server of the first set of distribution servers over a different second set of the plurality of distribution servers; and

distributing the second set of requests across the second set of distribution servers by adjusting the hash result produced for the second set of distribution servers with at least a second load factor value and by selecting a server from the second set of distribution servers to receive each request from the second set of requests based on the hash result of each server of the second set of distribution servers as adjusted by the second load factor value, the second load factor value increasing selection precedence of any server of the second set of distribution servers over the first set of distribution servers.

2. The method of claim 1, the processor further producing a second hash result by hashing a Uniform Resource Locator (URL) of each request of the plurality of requests.

3. The method of claim 2, wherein selecting a server from the first set of distribution servers is further based on combining the second hash result with the hash result produced for each server of the first set of distribution servers as adjusted by the first load factor value.

4. The method of claim 1, wherein the hash result is a 64-bit value produced from a 64-bit hash of the identifier identifying a server of the plurality of distribution servers.

5. The method of claim 1, wherein the first content type comprises cacheable content and the second content type comprises content that is not cacheable.

6. The method of claim 1, wherein the first content type comprises content that is requested more than a specified threshold during a time duration and the second content type comprises content that is not requested more than the specific threshold during the time duration.

7. The method of claim 1, wherein the first content type comprises content with a first set of file extensions and the second content type comprises content with a different second set of file extensions.

8. The method of claim 1, wherein the first content type comprises content with high quality of service and the second content type comprises content with low quality of service.

9. The method of claim 1, wherein the processor further differentiates the first set of requests from the second set of requests based on a URL, domain name, file extension, or Internet Protocol (IP) address associated with each request of the plurality of requests.

10. A computer-implemented method comprising:

receiving a plurality of requests over the Internet at a first tier server controlling distribution of the plurality of requests across a set of second tier servers, the first tier server comprising a processor and memory storing a threshold for differentiating hot content from regular content, the processor leveraging the memory in;

monitoring request rates for different content requested in the plurality of requests;

distributing a first set of the plurality of requests from the first tier server across the set of second tier servers according to a first consistent distribution scheme, the first set of requests comprising requests requesting at least first content, second content, and third content, and wherein said distributing according to the first consistent distribution scheme comprises sending requests for the first content to a first server of the set of second tier servers, requests for the second content to a second server of the set of second tier servers, and requests for the third content to a third server of the set of second tier servers;

classifying the first content as hot content in response to a request rate of the first content exceeding the threshold, and the second content and the third content as regular content in response to request rates of the second content and the third content not exceeding the threshold; and

distributing a second set of the plurality of requests directed to the first content from the first server across the first server and the second server according to a second consistent distribution scheme, and a third set of the plurality of requests directed to the second content or the third content from the first tier server to at least the third server according to a third consistent distribution scheme.

11. The computer-implemented method of claim 10 further comprising allocating additional server resources to serve the first content by producing the second consistent distribution scheme and the third consistent distribution scheme from the first distribution scheme, the second consistent distribution scheme selecting the first server or the second server for delivery of the first content and the third consistent distribution scheme selecting at least the third server for delivery of the second content and the third content.

12. The computer-implemented method of claim 10, wherein distributing the first set of requests according to the first consistent distribution scheme comprises hashing different identifiers identifying the first server, the second server, and the third servers, and selecting one of the first, second, and third servers to receive a request based on results of said hashing.

13. The computer-implemented method of claim 12, wherein distributing the second set of requests according to the second consistent distribution scheme comprises adjusting results of said hashing using a first set of load factor values prioritizing selection of one of the first server and the second server for distribution of the first content and deprioritizing selection of the third server for distribution of the first content.

14. The computer-implemented method of claim 13, wherein distributing the third set of requests according to the third consistent distribution scheme comprises adjusting results of said hashing using a different second set of load factor values prioritizing selection of the third server for distribution of the second content or the third content and deprioritizing selection of the first server and the second server for distribution of the second content or the third content.

15. The computer-implemented method of claim 10 further comprising advertising an IP address from the first tier server identifying the first tier server as a source for any content served by the set of second tier servers.

16. A method comprising:

distributing a first set of requests from a load distribution server across a plurality of servers;

identifying a first content type from a plurality of content types requested in the first set of requests creating an unbalanced load across the plurality of servers;

receiving over the Internet at the load distribution server, a second set of requests directed to the first content type and a third set of requests directed to other content types from the plurality of content types; and

dynamically differentiating a first set of the plurality of servers for distribution of the first content type and a different second set of the plurality of servers for distribution of the other content types, wherein dynamically differentiating comprises distributing the second set of requests across the first set of servers and distributing the third set of requests across the second set of servers.

17. The method of claim 16, wherein dynamically differentiating comprises temporarily allocating the first set of servers for exclusive distribution of content of the first content type.

18. The method of claim 16, wherein content of the first content type imposes greater load on a server than content of the other content types.

19. The method of claim 16 further comprising producing a hash result for each server of the set of servers by hashing an identifier identifying each server of the set of servers.

20. The method of claim 19, wherein dynamically differentiating comprises adjusting, in response to a request for the first content type, the hash result produced for each server of the first set of servers with a first value without adjusting the hash result produced for each server of the first set of servers with the first value.