Content placement

• US 8,856,846 B2
• Filed: 11/29/2010
• Issued: 10/07/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
• Primary Examiner(s): HUYNH, AN SON PHI
• Application Number:
  US12/955,672
• Publication Number:
  US 20120137336A1
• Time in Patent Office: 1,408 Days
• Field of Search: 725 90- 97, 725/46
• 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 receiving data identifying new media content items to be added to a media distribution system that provides media content on demand to a plurality of endpoints. The media distribution system includes a plurality of distribution nodes, and each of the distribution nodes is coupled to a subset of the endpoints. Historical demand is determined during a particular time period for existing media content items that include content available via at least one of the distribution nodes before the data was received. The method includes forecasting demand for media content items, including new media content items and existing media content items, based on the historical demand. Each media content item is assigned to, and stored at, at least one corresponding distribution node based at least partially on a cost function and the forecasted demand.

Claims

1. A computer-implemented method comprising:

receiving data identifying new media content items to be added to a media distribution system that provides media content on demand to a plurality of endpoints, wherein the media distribution system includes a plurality of distribution nodes, wherein a particular distribution node of the plurality of distribution nodes includes 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, wherein the first storage is distinct from the second storage, and wherein each of the plurality of distribution nodes is coupled to a corresponding subset of endpoints of the plurality of endpoints;

determining historical demands during a particular time period for existing media content items, wherein each of the existing media content items includes content available to the plurality of endpoints via the plurality of distribution nodes prior to the data identifying the new media content items being received;

forecasting demands for a subset of third media content items of the media distribution system based on the historical demands to generate forecasted demands, the third media content items including the new media content items and the existing media content items;

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

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 third media content items to each of the plurality of endpoints;

assigning each of the third media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demands, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the third media content items to each of the plurality of endpoints; and

storing a first particular media content item of the third media content items at the first storage of the particular distribution node.

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

determining demand values for the existing media content items based on a number of requests received during the 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 the subset of the third media content items for a future time period; and

assigning projected demand values to at least the subset of the third 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 demands are based on the projected demand values.

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

4. The method of claim 1, wherein each of the third media content items is assigned based on a topology of the media distribution system.

5. The method of claim 1, wherein each of the third media content items is assigned based on an estimate of peak demand associated with the media distribution system.

6. The method of claim 1, wherein the third 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 demands corresponding to the first set of video content items are forecasted independently of second forecasted demands corresponding to the second set of video content items.

7. The method of claim 1, 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 1, 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 third 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 the different distribution node and stores the third particular media content item at the second storage of the particular distribution node when the third particular media content item is received from the different distribution node.

9. The method of claim 8, 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 8, 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, further comprising:

determining a fractional solution to the cost function by solving a set of simultaneous equations to minimize the cost function; and

rounding the fractional solution based on a rounding heuristic.

12. The method of claim 1, wherein the data identifying the new media content items is received at a server configured to assign media content items to the plurality of distribution nodes.

13. The method of claim 1, wherein the forecasted demands are based on polling results associated with the subset of the third media content items.

14. 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;

receiving data identifying new media content items to be added to a media distribution system that provides media content on demand to a plurality of endpoints, wherein the media distribution system includes a plurality of distribution nodes, wherein a particular distribution node of the plurality of distribution nodes includes 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, wherein the first storage is distinct from the second storage, and wherein each of the plurality of distribution nodes is coupled to a corresponding subset of endpoints of the plurality of endpoints;

determining historical demands during a particular time period for existing media content items, wherein each of the existing media content items includes content available to the plurality of endpoints via the plurality of distribution nodes prior to the data identifying the new media content items being received;

forecasting demands for a subset of third media content items of the media distribution system based on the historical demands to generate forecasted demands, the third media content items including the new media content items and the existing media content items;

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

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 third media content items to each of the plurality of endpoints;

assigning each of the third media content items to a corresponding distribution node of the plurality of distribution nodes based on the cost function and the forecasted demands, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the third media content items to each of the plurality of endpoints; and

storing a first particular media content item of the third media content items at the first storage of the particular distribution node.

15. The system of claim 14, wherein the third media content items are assigned in a manner that approaches a minimum of the cost function subject to physical constraints and logical constraints of the media distribution system and the forecasted demands.

16. The system of claim 14, wherein the third media content items are further assigned based on network modification data describing a physical modification or a logical modification to the media distribution system, and wherein the first media content items and the second media content item include video on demand content.

17. A computer-readable storage device comprising instructions that, when executed by a processor, cause the processor to perform operations comprising:

receiving data identifying new media content items to be added to a media distribution system that provides media content on demand to a plurality of endpoints, wherein the media distribution system includes a plurality of distribution nodes, wherein a particular distribution node of the plurality of distribution nodes includes 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, wherein the first storage is distinct from the second storage, and wherein each of the plurality of distribution nodes is coupled to a corresponding subset of endpoints of the plurality of endpoints;

determining historical demands during a particular time period for existing media content items, wherein each of the existing media content items includes content available to the plurality of endpoints via the plurality of distribution nodes prior to the data identifying the new media content items being received;

forecasting demands for a subset of third media content items of the media distribution system based on the historical demands to generate forecasted demands, the third media content items including the new media content items and the existing media content items;

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

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 third media content items to each of the plurality of endpoints;

assigning each of the third media content items to a corresponding distribution node based on the cost function and the forecasted demands, wherein the cost function is associated with an amount of bandwidth for the media distribution system to provide the third media content items to each of the plurality of endpoints; and

storing a particular media content item of the new media content items at the first storage of the particular distribution node.