Content Placement

• US 20120137336A1
• Filed: 11/29/2010
• Published: 05/31/2012
• 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., Gopalakrishnan, Vijay, Lee, Seungjoon, Ramakrishnan, Kadangode, Archer, Aaron F.
• Granted Patent: US 8,856,846 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 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, each of the distribution nodes coupled to a subset of the endpoints;

determining historical demand during a particular time period for existing media content items, wherein each of the existing media content items includes content available via at least one of the distribution nodes before the data identifying the new media content items was received;

forecasting demand for media content items of the media distribution system based on the historical demand, the media content items including the new media content items and the existing media content items;

assigning each of the media content items to at least one corresponding distribution node based at least partially on a cost function and the forecasted demand; and

storing each of the new media content items at the at least one corresponding distribution node.

2. The method of claim 1, wherein assigning each of the media content items to at least one corresponding distribution node comprises determining values of the cost function using a mixed integer program model subject to storage constraints of the distribution nodes, bandwidth constraints of the media distribution system, and the forecasted demand.

3. The method of claim 1, wherein forecasting demand 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 at least a subset of the media content items for a future time period; and

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

4. The method of claim 1, wherein the demand is forecasted based at least partially based on a type of content associated with the at least one media content item.

5. The method of claim 1, wherein each of the media content items is assigned to at least one corresponding distribution node based at least partially on storage capacity constraints associated with the distribution nodes.

6. The method of claim 1, wherein each of the media content items is assigned to at least one corresponding distribution node based at least partially on bandwidth constraints associated with the media distribution system.

7. The method of claim 1, wherein each of the media content items is assigned to at least one corresponding distribution node based at least partially on a topology of the media distribution system.

8. The method of claim 1, wherein each of the media content items is assigned to at least one corresponding distribution node based at least partially on an estimate of peak demand of the media distribution system.

9. The method of claim 1, wherein the media content items include a first set of video content items having a first viewing length that is less than about ten minutes, a second set of video content items having a second viewing length that is between about ten minutes and about thirty minutes, a third set of video content items having a third viewing length that is between about thirty minutes and about one hour, and a fourth set of video content items having a fourth viewing length that is greater than about one hour, wherein the demand is forecasted independently for the first set of video content items, the second set of video content items, the third set of video content items, and the fourth set of video content items.

10. The method of claim 1, further comprising:

determining whether each of the existing media content items is stored at the at least one corresponding distribution node, and

when a particular existing media content item is not stored at a particular corresponding distribution node, storing the particular existing media content item at the particular corresponding distribution node.

11. The method of claim 1, further comprising:

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

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

12. The method of claim 1, wherein, when a particular endpoint sends a request for a particular media content item to a first distribution node, the first distribution node determines whether the particular media content item is stored at a main storage of the first distribution node or at a local cache of the first distribution node, when the particular media content item is not stored at main storage or the local cache of the first distribution node, the first distribution node sends a request for the particular media content item to a second particular distribution node and stores the particular media content item at the local cache of the first distribution node when the media content item is received.

13. The method of claim 12, wherein media content items are occasionally removed from the local cache on a least recently used basis.

14. The method of claim 12, wherein media content items are occasionally removed from the local cache on a least frequently used basis.

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;

receive 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, each of the distribution nodes coupled to a subset of the endpoints;

determine historical demand during a particular time period for existing media content items, wherein each of the existing media content items includes content available via at least one of the distribution nodes before the data identifying the new media content items was received;

forecast demand for media content items of the media distribution system based on the historical demand, the media content items including the new media content items and the existing media content items;

assign each of the media content items to at least one corresponding distribution node based at least partially on a cost function and the forecasted demand; and

store each of the new media content items at the at least one corresponding distribution node.

16. The system of claim 15, wherein the mixed integer program model is used to assign the media content items to the corresponding distribution nodes in a manner that approaches a minimum of the cost function subject to physical and logical constraints of the media distribution system and the forecasted demand.

17. The system of claim 16, wherein the mixed integer program model takes into consideration at least storage constraints of the distribution nodes, bandwidth constraints of the media distribution system, and the forecasted demand.

18. The system of claim 15, wherein the media content items include video on demand content.

19. The system of claim 15, further comprising receiving network modification data describing one or more physical or logical modifications to the media distribution system, wherein each of the media content items is assigned to at least one corresponding distribution node based at least partially on the network modification data.

20. The system of claim 15, wherein each of the media content items is assigned to at least one corresponding distribution node using a mixed integer program (MIP) model.

21. The system of claim 20, wherein Lagrangian relaxation is applied to the mixed integer program model to facilitate assigning the media content items to the corresponding distribution nodes.

22. A non-transitory computer-readable medium comprising instructions that, when executed by the processor, cause the processor to:

receive 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, each of the distribution nodes coupled to a subset of the endpoints;

determine historical demand during a particular time period for existing media content items, wherein each of the existing media content items includes content available via at least one of the distribution nodes before the data identifying the new media content items was received;

forecast demand for media content items of the media distribution system based on the historical demand, the media content items including the new media content items and the existing media content items;

assign each of the media content items to at least one corresponding distribution node based at least partially on a cost function and the forecasted demand; and

store each of the new media content items at the at least one corresponding distribution node.