Method and apparatus for transferring content among large clusters of storage devices to achieve a target replication distribution

• US 9,942,311 B2
• Filed: 06/27/2013
• Issued: 04/10/2018
• Est. Priority Date: 06/27/2013
• Status: Expired due to Fees

• Current Assignee: Magnolia Licensing LLC (IP Edge LLC)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Ioannidis, Efstratios, Massoulie, Laurent, Picconi, Fabio, Jiang, Wenjie
• Primary Examiner(s): Coulter, Kenneth R
• Application Number:
  US14/901,658
• Publication Number:
  US 20160142476A1
• Time in Patent Office: 1,748 Days
• Field of Search: 709203, 709224, 709223
• CPC Class Codes: H04L 65/61 for supporting one-way streaming services, e.g. Internet radio
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/80 Responding to QoS
• 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/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A content distribution network, including: a content server that stores a set of content items; a plurality of gateways for storing and serving content requests to a subset of the content items, the plurality of gateways being grouped into a plurality of classes of gateways; and a plurality of class trackers corresponding to the plurality of classes; wherein each class tracker manages a placement of content items and an assignment of content requests for its class of gateways; wherein the plurality of class trackers exchange congestion signals among themselves; wherein, for each content item, each class tracker determines a fraction of gateways in its class of gateways that store the content item and a rate of content requests that are forwarded to the content server or other class trackers, based on requests for the content item entering its class and the congestion signals received from other class trackers.

Claims

1. A content distribution network, comprising:

a content server that stores a set of content items;

a plurality of gateways for storing and serving content requests to a subset of the content items, the plurality of gateways being grouped into a plurality of classes of gateways; and

a plurality of class trackers corresponding to the plurality of classes of gateways;

wherein each class tracker manages a placement of content items and an assignment of content requests for its corresponding class of gateways;

wherein the plurality of class trackers exchange congestion signals among themselves;

wherein, for each content item, each class tracker determines a replication ratio determining a fraction of gateways in its corresponding class of gateways that store a copy of a content item and a forwarding rate determining a rate of content requests that are forwarded to the content server or other class trackers, based on requests for the content item entering its class and the congestion signals received from other class trackers; and

wherein each class tracker adapts the replication ratio and forwarding rate such that an aggregate traffic load of each class does not exceed a total upload capacity of each class and such that a traffic load imposed on each class by requests for a content item does not exceed an upload capacity of gateways storing the content item.

2. The content distribution network according to claim 1, wherein each gateway comprises a plurality of storage slots for storing content items, wherein one of the plurality of storage slots is accessed by other gateways.

3. The content distribution network according to claim 1, wherein each class tracker tracks which gateways are in its class, which gateways are on or off, the content stored on each gateway, and which gateway is busy or idle.

4. The content distribution network according to claim 1, wherein the exchange of congestion signals is carried out periodically;

and, after each exchange, each class tracker updates, for each content item, the fraction of gateways in its corresponding class of gateways that store the content item and the rate of content requests that are forwarded to the content server or other class trackers.

5. The content distribution network according to claim 1, wherein, for each content item, each class tracker determines the fraction of gateways in its corresponding class of gateways that store the content item and the rate of content requests that are forwarded to the content server or other class trackers, is further based on minimizing cross-traffic costs associated with content requests that are forwarded to the content server or other class trackers.

6. A method of operating a content distribution network, the content distribution network comprising a content server that stores a set of content items, a plurality of gateways for storing and serving content requests to a subset of the content items, the plurality of gateways being grouped into a plurality of classes of gateways, and a plurality of class trackers corresponding to the plurality of classes of gateways, the method comprising:

managing, by each class tracker, a placement of content items and an assignment of content requests for its corresponding class of gateways;

exchanging congestion signals among the plurality of class trackers; and

for each content item, determining, by each class tracker, a replication ratio determining a fraction of gateways in its corresponding class of gateways that store a copy of a content item and a forwarding rate determining a rate of content requests that are forwarded to the content server or other class trackers, based on requests for the content item entering its class and the congestion signals received from other class trackers; and

adapting by each class tracker the replication ratio and forwarding rate such that an aggregate traffic load of each class does not exceed a total upload capacity of each class and such that a traffic load imposed on each class by requests for a content item does not exceed an upload capacity of gateways storing the content item.

7. The method according to claim 6, wherein each gateway comprises a plurality of storage slots for storing content items, wherein one of the plurality of storage slots is accessed by other gateways.

8. The method according to claim 6, wherein each class tracker tracks which gateways are in its class, which gateways are on or off, the content stored on each gateway, and which gateway is busy or idle.

9. The method according to claim 6, further comprising:

carrying out the exchange of congestion signals periodically; and

after each exchange, for each content item, updating, by each class tracker, the fraction of gateways in its corresponding class of gateways that store the content item and the rate of content requests that are forwarded to the content server or other class trackers.

10. The method according to claim 6, wherein, for each content item, the determining by each class tracker the fraction of gateways in its corresponding class of gateways that store the content item and the rate of content requests that are forwarded to the content server or other class trackers, is further based on minimizing cross-traffic costs associated with content requests that are forwarded to the content server or other class trackers.

11. Apparatus comprising one or more processors configured to manage a placement of content items and an assignment of content requests for a first subset of a plurality of gateway devices, wherein the one or more processors:

receives a congestion signal;

determines a replication ratio determining a fraction of gateway devices in the first subset of gateway devices that store a copy of a content item and a forwarding rate determining a rate of content requests that are forwarded to a content server or to a second subset of the plurality of gateway devices, based on requests for the content item entering the class and the received congestion signal; and

adapting the replication ratio and forwarding rate such that an aggregate traffic load of the first subset of the plurality of gateway devices does not exceed a total upload capacity of the first subset and such that a traffic load imposed on the first subset by requests for a content item does not exceed an upload capacity of gateway devices in the first subset storing the content item.

12. The apparatus of claim 11, wherein the one or more processors are further configured to track which gateway devices among the plurality of gateway devices are in the first subset, which gateway devices in the first subset are on or off, the content stored on each gateway device in the first subset, and which gateway devices in the first subset are busy or idle.

13. The apparatus of claim 12, wherein the one or more processors are further configured to determine the replication ratio and forwarding rate based on minimizing a cross-traffic cost associated with content requests that are forwarded to the content server or to the second subset of gateway devices.

14. The apparatus of claim 13 wherein:

the one or more processors are included in one of a plurality of class trackers included in a content distribution network comprising the content server, the plurality of gateway devices and the plurality of class trackers;

the plurality of gateway devices are grouped into a plurality of classes of gateway devices;

the plurality of class trackers correspond to the plurality of classes of gateway devices; and

the first and second subsets of gateway devices correspond to first and second ones of the plurality of classes of gateway devices.