Content placement

• US 9,723,343 B2
• Filed: 08/15/2014
• Issued: 08/01/2017
• Est. Priority Date: 11/29/2010
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Archer, Aaron F., Gopalakrishnan, Vijay, Ramakrishnan, Kadangode, Applegate, David L., Lee, Seungjoon
• Primary Examiner(s): HUYNH, AN SON PHI
• Application Number:
  US14/460,510
• Publication Number:
  US 20140359683A1
• Time in Patent Office: 1,082 Days
• Field of Search: 725 90- 97, 725 46
• 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, by a computer, demand for media content items available to a media distribution system based on historical demand information to generate forecasted demand;

generating, by 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, wherein each distribution node of the plurality of distribution nodes is associated with a corresponding set of a plurality of endpoints, wherein the bandwidth constraints include a particular bandwidth constraint for a link between a first distribution node of the plurality of distribution nodes and a second distribution node of the plurality of distribution nodes, the first distribution node associated with a first set of the plurality of endpoints and the second distribution node associated with a second set of the plurality of endpoints, the second set of the plurality of endpoints distinct from the first set of the plurality of endpoints;

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

determining, by the computer, values of a cost function, 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 the plurality of endpoints of the media distribution system, and wherein the values of the cost function are based on a result of the Lagrangian relaxation operation; and

causing, by the computer, each of the media content items to be stored at 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 stored media content items based on a number of requests received during a particular time period to access each of the stored media content items, the stored media content items available through the media distribution system while the demand values are determined;

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 a 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 values of the cost function indicate that in response to the first distribution node receiving a request for a first media content item of the media content items from a first endpoint of the first set of the plurality of endpoints, the first distribution node accesses the first media content item from the second distribution node via the link.

4. The method of claim 3, wherein the values of the cost function indicate that in response to the second distribution node receiving a second request for a second media content item of the media content items from a second endpoint of the second set of the plurality of endpoints, the second distribution node accesses the second media content item from the first distribution node via the link.

5. 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, 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, in response to a particular endpoint sending 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, in response to the third particular media content item not being 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 second particular distribution node to which the third particular media content item is assigned and sends a second 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 cost function is configured to conserve the amount of bandwidth used.

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 link comprises a second link between the first distribution node and a third distribution node of the plurality of distribution nodes and a third link between the third distribution node and the second distribution node, and wherein the particular bandwidth constraint for the link is based on a first bandwidth constraint for the second link and a second bandwidth constraint for the third link.

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, further comprising, prior to forecasting demand, receiving data identifying new media content items, wherein the historical demand information corresponds to stored media content items, and wherein demand is forecast for the new media content items and the stored media content items.

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 available to 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, wherein each distribution node of the plurality of distribution nodes is associated with a corresponding set of a plurality of endpoints, wherein the bandwidth constraints include a particular bandwidth constraint for a link between a first distribution node of the plurality of distribution nodes and a second distribution node of the plurality of distribution nodes, wherein the first distribution node is associated with a first set of endpoints of the plurality of endpoints, and wherein the second distribution node is associated with a second set of endpoints of the plurality of endpoint, the second set of endpoints distinct from the first set of endpoints;

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

determining values of a cost function, 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 the plurality of endpoints of the media distribution system, and wherein the values of the cost function are based on a result of the Lagrangian relaxation operation; and

causing each of the media content items to be stored at 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 particular bandwidth constraint corresponds to bandwidth of data communicated from the first distribution node to the second distribution node, wherein the bandwidth constraints include a second particular bandwidth constraint for a second link between the first distribution node and the second distribution node, wherein the second particular bandwidth constraint corresponds to bandwidth of data communicated from the second distribution node to the first distribution node, and wherein the particular bandwidth constraint is distinct from the second particular bandwidth constraint.

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 available to 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, wherein each distribution node of the plurality of distribution nodes is associated with a corresponding set of a plurality of endpoints, wherein the bandwidth constraints include a particular bandwidth constraint for a link between a first distribution node of the plurality of distribution nodes and a second distribution node of the plurality of distribution nodes, wherein the first distribution node is associated with a first set of endpoints of the plurality of endpoints, and wherein the second distribution node is associated with a second set of endpoints of the plurality of endpoint, the second set of endpoints distinct from the first set of endpoints;

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

determining values of a cost function, 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 the plurality of endpoints of the media distribution system, and wherein the values of the cost function are based on a result of the Lagrangian relaxation operation; and

causing each of the media content items to be stored at 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.