Utility-based model for caching programs in a content delivery network

• US 8,954,556 B2
• Filed: 12/01/2011
• Issued: 02/10/2015
• Est. Priority Date: 12/01/2011
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Qian, Yuhui, Yao, Xuefeng, Jin, Zhiying, Hao, Jack Jianxiu
• Primary Examiner(s): Wang, Liangche A
• Assistant Examiner(s): ALRIYASHI, ABDULKADER MOHAMED
• Application Number:
  US13/308,872
• Publication Number:
  US 20130145001A1
• Time in Patent Office: 1,167 Days
• Field of Search: 709223-226, 709/220, 709217-219, 711/118, 711133-136, 707/736, 707/E17.119, 707/E17.12, 707/E17.121
• US Class Current: 709/223
• 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/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

Methods, devices, and storage media for receiving one or more utility preferences that indicate one or more criteria for measuring one or more utilities of programs; calculating utility solutions for the programs based on the one or more utility preferences; selecting one or more programs to store for at least one of downloading or streaming based on the utility solutions; and storing the one or more programs for downloading or streaming to users.

Claims

1. A method comprising:

receiving, by a network device, utility preferences that indicate criteria for measuring one or more utilities of programs;

storing hard constraint information, wherein the hard constraint information includes one or more hard resource constraints pertaining to one or more resources of the network device and one or more hard program constraints pertaining to the programs;

receiving weights pertaining to the utility preferences;

identifying a value of at least one of the weights, which pertains to at least one of the utility preferences, as being higher in value relative to another value of the weights, which pertains to another one of the utility preferences;

pre-sorting candidate programs that rank higher relative to other programs with respect to the at least one of the utility preferences based on an identification of the value;

calculating, by the network device, utility solutions for at least a portion of pre-sorted candidate programs based on the utility preferences and the hard constraint information, wherein the calculating comprises;

selecting one or more programs, which are top-ranked, in relation to each of the utility preferences;

combining the selected one or more programs from each of the utility preferences; and

applying the weights of the utility preferences in relation to a combined set of programs;

selecting, by the network device, one or more programs to store for at least one of downloading or streaming based on the utility solutions; and

storing the one or more programs.

2. The method of claim 1, further comprising:

storing soft constraint information; and

calculating the utility solutions based on the soft constraint information.

3. The method of claim 1, further comprising:

collecting statistical information pertaining to the programs, and wherein the calculating comprises;

calculating the utility solutions based on the statistical information.

4. The method of claim 1, wherein the utility preferences include at least one of previous access history pertaining to the programs or bitrates of the programs, and the method further comprising:

storing user preference information pertaining to users that at least one of download or stream programs, wherein the calculating further comprises;

calculating the utility solutions for the programs based on the utility preferences, the hard constraint information, and the user preference information.

5. The method of claim 1, wherein the one or more hard resource constraints pertain to storage space, bandwidth, or a processor limitation, and the one or more hard program constraints are based on a popularity of the programs, wherein the popularity is not based on previous access of the programs.

6. The method of claim 1, further comprising:

transmitting, to another device, an update program request that identifies the programs to be stored, and wherein at least one of the utility preferences include upper bound and lower bound values, the method further comprising;

using the upper bound and the lower bound values to calculate one of the utility solutions, wherein the one of the utility solutions is normalized based on the upper bound and the lower bound values.

7. The method of claim 1, wherein the calculating comprises:

applying one or more heuristics that reduce a time constraint and a search space constraint for selecting the one or more programs.

8. A device comprising:

a communication interface;

one or more memories that store instructions; and

one or more processors to execute the instructions to;

receive utility preferences that indicate criteria for measuring one or more utilities of programs;

store hard constraint information, wherein the hard constraint information includes one or more hard resource constraints pertaining to one or more resources of the device and one or more hard program constraints pertaining to the programs;

receive weights pertaining to the utility preferences;

identify a value of at least one of the weights, which pertains to at least one of the utility preferences, as being higher in value relative to another value of the weights, which pertains to another one of the utility preferences;

pre-sort candidate programs that rank higher relative to other programs with respect to the at least one of the utility preferences based on an identification of the value;

calculate utility solutions for at least a portion of pre-sorted candidate programs based on the utility preferences and the hard constraint information, wherein a calculation comprises;

select one or more programs, which are top-ranked, in relation to each of the utility preferences;

combine the selected one or more programs from each of the utility preferences;

apply the weights of the utility preferences in relation to a combined set of programs; and

select one or more programs to store for at least one of downloading or streaming based on the utility solutions.

9. The device of claim 8, wherein the one or more processors further execute the instructions to:

store soft constraint information; and

calculate the utility solutions based on the soft constraint information.

10. The device of claim 8, wherein the one or more processors further execute the instructions to:

determine whether the programs will cause a violation of a constraint indicated by the hard constraint information; and

remove any of the programs in response to a determination that any of the programs will cause the violation of the constraint indicated by the hard constraint information.

11. The device of claim 8, wherein the one or more processors further execute the instructions to:

receive statistical information pertaining to the programs, and wherein when calculating, the one or more processors further execute the instructions to;

calculate the utility solutions based on the statistical information.

12. The device of claim 8, wherein the one or more processors further execute the instructions to:

transmit a message to another device that stores the one or more programs, wherein the message indicates the selected one or more programs.

13. The device of claim 8, wherein the one or more processors further execute the instructions to:

store the one or more programs;

receive user requests for the at least one of downloading or streaming of programs; and

download or stream programs to users in response to the user requests.

14. The device of claim 8, wherein the one or more processors further execute the instructions to:

store user preference information pertaining to users that at least one of download or stream programs, and wherein when selecting the one or more programs, the one or more processors further execute the instructions to;

select the one or more programs based on the user preference information.

15. The device of claim 8, wherein the device includes an edge server of a content delivery network or an edge server controller of a content delivery network.

16. A non-transitory storage medium storing instructions executable by a computational device to:

receive utility preferences that indicate criteria for measuring one or more utilities of programs;

store hard constraint information, wherein the hard constraint information includes one or more hard resource constraints pertaining to one or more resources of the computational device and one or more hard program constraints pertaining to the programs;

receive weights pertaining to the utility preferences;

identify a value of at least one of the weights, which pertains to at least one of the utility preferences, as being higher in value relative to another value of the weights, which pertains to another one of the utility preferences;

pre-sort candidate programs that rank higher relative to other programs with respect to the at least one of the utility preferences based on an identification of the value;

calculate a utility solution for at least a portion of pre-sorted candidate programs based on the utility preferences and the hard constraint information, wherein a calculation comprises;

select one or more programs, which are top-ranked, in relation to each of the utility preferences;

combine the selected one or more programs from each of the one or more utility preferences; and

apply the weights of the utility preferences in relation to a combined set of programs;

compare calculated utility solutions;

determine a set of programs having a higher utility relative to other programs in response to comparisons; and

select one or more programs to store for at least one of downloading or streaming based on the utility solutions.

17. The non-transitory storage medium of claim 16, further storing instructions executable by the computational device to:

store soft constraint information; and

calculate the utility solutions based on the soft constraint information.

18. The non-transitory storage medium of claim 16, wherein the one or more hard program constraints include a constraint that a particular program must be stored for a particular time period and will not be removed or swapped out regardless of other conditions.

19. The non-transitory storage medium of claim 16, further storing instructions executable by the computational device to:

select the one or more programs based on user preference information pertaining to users that at least one of download or stream programs.

20. The non-transitory storage medium of claim 16, further storing instructions executable by the computational device to:

update programs stored based on the selected one or more programs.