CONTENT PLACEMENT

• US 20140359683A1
• Filed: 08/15/2014
• Published: 12/04/2014
• Est. Priority Date: 11/29/2010
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Applegate, David L., Archer, Aaron F., Gopalakrishnan, Vijay, Lee, Seungjoon, Ramakrishnan, Kadangode
• Granted Patent: US 9,723,343 B2
• Time in Patent Office: Days
• US Class Current: 725/95
• CPC Class Codes: H04N 21/2225 Local VOD servers
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand

Abstract

A method includes forecasting demand for media content items of a media distribution system based on historical demand information to generate forecasted demand. The method includes generating a mixed integer program model based on storage constraints of a plurality of distribution nodes of the media distribution system, bandwidth constraints of the media distribution system, and the forecasted demand. The method includes performing a Lagrangian relaxation operation using the mixed integer program model. The method includes determining values of a cost function based on a result of the Lagrangian relaxation operation. The method includes assigning each of the media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demand.

Claims

1. A method comprising:

forecasting, at a computer, demand for media content items of a media distribution system based on historical demand information to generate forecasted demand;

generating, at the computer, a mixed integer program model based on storage constraints of a plurality of distribution nodes of the media distribution system, bandwidth constraints of the media distribution system, and the forecasted demand;

performing, at the computer, a Lagrangian relaxation operation using the mixed integer program model;

determining, at the computer, values of a cost function based on a result of the Lagrangian relaxation operation, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the media content items to each of a plurality of endpoints of the media distribution system; and

assigning, at the computer, each of the media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demand.

2. The method of claim 1, wherein forecasting the demand comprises:

determining demand values for existing media content items, which are available through the media distribution system when determining the demand values, based on a number of requests received during a particular time period to access each of the existing media content items;

assigning rank positions to the demand values based on a magnitude of each of the demand values;

estimating a popularity order of a subset of the media content items for a time period for which the demand is being forecast; and

assigning projected demand values to at least the subset of the media content items, wherein a particular projected demand value assigned to the first particular media content item is the demand value of a particular rank position that corresponds to a particular position in the popularity order of the first particular media content item, and wherein the forecasted demand is based on the projected demand values.

3. The method of claim 1, wherein the forecasted demand is based on a type of content associated with a subset of the media content items.

4. The method of claim 1, further comprising sending a command to store a first particular media content item of the media content items at a particular distribution node.

5. The method of claim 4, wherein the particular distribution node of the plurality of distribution nodes includes a first storage to store first media content items that are assigned to the particular distribution node and second storage to store a second media content item requested from a different distribution node of the plurality of distribution nodes to which the second media content item is assigned, and wherein the first particular media content item is stored in the first storage.

6. The method of claim 5, wherein the first storage is distinct from the second storage.

7. The method of claim 5, further comprising:

determining, for the particular distribution node, whether any media content item is stored at the first storage of the particular distribution node that is not assigned to the particular distribution node, and

when a second particular media content item is stored at the first storage of the particular distribution node and is not assigned to the particular distribution node, causing the second particular media content item to be deleted from the first storage of the particular distribution node.

8. The method of claim 5, wherein, when a particular endpoint sends a first request for a third particular media content item to the particular distribution node, the particular distribution node determines whether the particular media content item is stored at the first storage of the particular distribution node or at the second storage of the particular distribution node, and wherein, when the third particular media content item is not stored at the first storage or the second storage of the particular distribution node, the particular distribution node sends a second request for the third particular media content item to a distribution node to which the third particular item is assigned and sends a command to store the third particular media content item at the second storage of the particular distribution node.

9. The method of claim 5, wherein the second storage stores multiple second media content items, and wherein the multiple second media content items are removed from the second storage in accordance with a least recently used removal procedure.

10. The method of claim 5, wherein the second storage stores multiple second media content items, and wherein the multiple second media content items are removed from the second storage in accordance with a least frequently used removal procedure.

11. The method of claim 1, wherein the Lagrangian relaxation operation is performed on the mixed integer program model for the storage constraints of the plurality of distribution nodes and the bandwidth constraints of the media distribution system.

12. The method of claim 1, wherein the values of the cost function are minimum values for the mixed integer program model.

13. The method of claim 1, wherein the media content items include a first set of video content items having a first viewing length and a second set of video content items having a second viewing length, wherein the first viewing length is less than the second viewing length, and wherein first forecasted demand that corresponds to the first set of video content items is forecast independently of second forecasted demand that corresponds to the second set of video content items.

14. The method of claim 1, wherein each of the plurality of distribution nodes is coupled to a corresponding subset of endpoints of the plurality of endpoints.

15. A system comprising:

a processor; and

memory accessible to the processor, the memory comprising instructions that, when executed by the processor, cause the processor to perform operations comprising;

forecasting demand for media content items of a media distribution system based on historical demand information to generate forecasted demand;

generating a mixed integer program model based on storage constraints of a plurality of distribution nodes of the media distribution system, bandwidth constraints of the media distribution system, and the forecasted demand;

performing a Lagrangian relaxation operation using the mixed integer program model;

determining values of a cost function based on a result of the Lagrangian relaxation operation, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the media content items to each of a plurality of endpoints of the media distribution system; and

assigning each of the media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demand.

16. The system of claim 15, wherein the operations further comprise sending a command to store a first particular media content item of the media content items at a particular distribution node.

17. The system of claim 15, wherein the media content items are assigned based on network modification data describing a physical modification or a logical modification to the media distribution system and wherein the media content items include video on demand content.

18. A computer-readable storage device comprising instructions executable by a processor to perform operations comprising:

forecasting demand for media content items of a media distribution system based on historical demand information to generate forecasted demand;

generating a mixed integer program model based on storage constraints of a plurality of distribution nodes of the media distribution system, bandwidth constraints of the media distribution system, and the forecasted demand;

performing a Lagrangian relaxation operation using the mixed integer program model;

determining values of a cost function based on a result of the Lagrangian relaxation operation, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the media content items to each of a plurality of endpoints of the media distribution system; and

assigning each of the media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demand.

19. The computer-readable storage device of claim 18, wherein operations further comprise sending a command to store a first particular media content item of the media content items at a particular distribution node.

20. The computer-readable storage device of claim 18, wherein the forecasted demand is based on a type of content associated with a subset of the media content items.