Media organization for distributed sending of media data

• US 8,037,200 B2
• Filed: 12/02/2008
• Issued: 10/11/2011
• Est. Priority Date: 10/10/2003
• Status: Active Grant

• Current Assignee: ROVI Product Corporation (Xperi Inc.)
• Original Assignee: Microsoft Corporation
• Inventors: Baldwin, James Armand, Barrett, Peter T., Green, Dustin L.
• Primary Examiner(s): JEAN, FRANTZ B
• Application Number:
  US12/326,818
• Publication Number:
  US 20090083806A1
• Time in Patent Office: 1,043 Days
• Field of Search: 709/203, 709/231, 709/247, 725/86, 725/87, 725/105
• US Class Current: 709/231
• CPC Class Codes: H04N 21/222 Secondary servers, e.g. proxy server, cable television Head-end provisioning of proxy services in data packet switching networks H04L67/56
• CPC Class Codes: H04N 21/2318 using striping
• CPC Class Codes: H04N 21/26208 the scheduling operation being performed under constraints
• CPC Class Codes: H04N 21/6581 Reference data, e.g. a movie identifier for ordering a movie or a product identifier in a home shopping application
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Media data is distributed across multiple devices and is locatable using a hashing function and a hash table. The media data is partially replicated based on popularity thereof. In a described implementation, a media data block is locatable by hashing a media data indicator to produce a media data hash value that maps to a bin of the hash table. The bin is associated with at least one device that stores and/or with a sender that is capable of sending to clients the media data blocks mapping thereto. Each bin may have primary and secondary roles. Devices holding primary roles store all of the media data blocks mapping to a bin. Devices holding secondary roles replicate the media data blocks mapping to the bin that are also within a top predetermined popularity percentage. Popularity is determined based on numbers of clients currently requesting a particular media data portion.

Claims

1. A method comprising:

dividing a media data segment into constituent media data portions, wherein the constituent media data portions comprise media data blocks, media data sub-blocks, or media data bytes;

tracking the constituent media data portions based on respective numbers of clients requesting the constituent media data portions;

ranking the constituent media data portions in popularity based on the respective numbers of clients requesting the constituent media data portions;

responsive to the ranking, determining which constituent media data portions have a popularity that is above a predetermined popularity percentage;

replicating the constituent media data portions that are determined to have a popularity that is above the predetermined popularity percentage;

establishing a hash table having a plurality of bins; and

mapping the constituent media data portions to a bin of the hash table, wherein the bin of the hash table includes a primary role and a secondary role;

the primary role associated with a primary sender that is associated with the constituent media data portions mapping to the bin, and the secondary role associated with a secondary sender that is associated with those constituent media data portions that are determined to have a popularity that is above the predetermined popularity percentage.

2. A method as recited in claim 1, further comprising:

combining a media data segment number and a media data block number to form a media data identification value, the media data block number corresponding to a media data block of a media data segment that corresponds to the media data segment number;

applying the media data identification value to a hashing function to produce a media data hash value;

mapping the media data hash value to the bin of the hash table, the bin of the hash table associated with a device;

combining another media data segment number and another media data block number to form another media data identification value;

applying the other media data identification value to the hashing function to produce another media data hash value; and

mapping the other media data hash value to another bin of the hash table, the other bin of the hash table associated with the device.

3. A method as recited in claim 1, further comprising:

determining the popularity of media data portions by ranking the media data portions from a media data portion being requested by the most clients to media data portions being requested by fewer and fewer clients, by computing a number of clients that equals a product of the top predetermined popularity percentage and a total number of requesting clients, and by identifying those media data portions that are requested by the computed number of clients starting with the media data portion being requested by the most clients and progressing in ranked order along those media data portions being requested by fewer and fewer clients.

4. A method as recited in claim 1, further comprising:

establishing a hash table having multiple bins that are associated with multiple devices; and

locating a constituent media data portion using (i) at least one indicator associated with the constituent media data portion and a hashing function, and (ii) the hash table.

5. A method as recited in claim 4, further comprising:

establishing at least two roles associated with each bin of the multiple bins, in accordance with the predetermined popularity percentage; and

formulating successive send requests using the hash table and responsive to the established roles.

6. A method as recited in claim 4, further comprising:

locating media data portions at the multiple devices associated with the multiple bins of the hash table by calculating a media data hash value, which maps to the multiple bins, from the at least one indicator associated with the constituent media data portion and the hashing function.

7. A system comprising:

a memory;

a processor;

a ranking section configured to;

divide a media data segment into constituent media data portions, wherein the constituent media data portions comprise media data blocks, media data sub-blocks, or media data bytes;

track the constituent media data portions based on respective numbers of clients requesting the constituent media data portions; and

rank the constituent media data portions in popularity based on the respective numbers of clients requesting the constituent media data portions;

a replicating section configured to responsive to the ranking, determine which constituent media data portions have a popularity that is above a predetermined popularity percentage; and

replicate the constituent media data portions that are determined to have a popularity that is above the predetermined popularity percentage; and

a hash table including a plurality of bins, each given bin of the plurality of bins configured to associate a given sender with media data blocks that map to the given bin,

wherein a particular media data block corresponds to a particular media data block number and a media data segment number, the particular media data block number and the media data segment number combined into a particular media data identification value that is hashed to a particular media data hash value, the particular media data hash value mapping the particular media data block to a particular bin of the plurality of bins.

8. The system of claim 7, wherein the particular bin has a primary role and a secondary role;

wherein the primary role is associated with a primary sender, and the secondary role is associated with a secondary sender.

9. The system of claim 7, wherein the particular bin has a primary role and a secondary role;

wherein the primary role corresponds to all media data blocks that map to the particular bin, and the secondary role corresponds to media data blocks that map to the particular bin and are within a top predetermined popularity percentage.

10. The system of claim 9, wherein the particular bin further has a tertiary role;

wherein the tertiary role corresponds to media data blocks that map to the particular bin and are within a different top predetermined popularity percentage, the different top predetermined popularity percentage being greater than the top predetermined popularity percentage.

11. The system of claim 9, wherein popularity ranking of the media data blocks is determined on a per-byte basis but the popularity is tracked at a different granularity.

12. The system of claim 9, further comprising:

a first device on which a primary sender is functioning, the primary sender associated with the primary role;

wherein the media data blocks that map to the particular bin are stored at the first device; and

a second device on which a secondary sender is functioning, the secondary sender associated with the secondary role;

wherein the media data blocks that map to the particular bin and are within the top predetermined popularity percentage are replicated at the second device.

13. The system of claim 7, further comprising:

a device; and

the given sender;

wherein the given sender is functioning on the device and the media data blocks are stored at the device.

14. The system of claim 7, further comprising:

the given sender, the given sender configured to send a first message to clients, wherein the first message comprises the mapping of the media data blocks to the given bin.

15. The system of claim 7, further comprising:

a scheduler configured to schedule delivery of the media data blocks to clients and adapted to formulate send requests stipulating the media data blocks and designating the clients; and

the given sender, the given sender adapted to send the stipulated media data blocks to the designated clients responsive to the send requests.

16. The system of claim 7, wherein the system determines the popularity of constituent media data portions by ranking the constituent media data portions from a constituent media data portion being requested by the most clients to constituent media data portions being requested by fewer and fewer clients, by computing a number of clients that equals a product of a top predetermined popularity percentage and a total number of requesting clients, and by identifying those constituent media data portions that are requested by the computed number of clients starting with the constituent media data portion being requested by the most clients and progressing in ranked order along those constituent media data portions being requested by fewer and fewer clients.

17. A computer implemented method comprising:

determining a popularity of media data portions stored on a server in accordance with a number of clients requesting each media data portion,

wherein determining comprises determining the popularity of the media data portions by ranking the media data portions from a media data portion being requested by the most clients to media data portions being requested by fewer and fewer clients, by computing a number of clients that equals a product of a top predetermined popularity percentage and a total number of requesting clients, and by identifying those media data portions that are requested by the computed number of clients starting with the media data portion being requested by the most clients and progressing in ranked order along those media data portions being requested by fewer and fewer clients,

wherein determining further comprises dividing a media data segment into constituent media data portions, wherein the constituent media data portions comprise media data blocks, media data sub-blocks, or media data bytes;

tracking the constituent media data portions based on respective numbers of clients requesting the constituent media data portions;

ranking the constituent media data portions in popularity based on the respective numbers of clients requesting the constituent media data portions; and

determining which constituent media data portions have a popularity that is above a predetermined popularity percentage responsive to the ranking;

locating the media data portions using a hashing function and a hashing table; and

replicating those media data portions that are within the top predetermined popularity percentage, including replicating the constituent media data portions that are determined to have a popularity that is above the predetermined popularity percentage.

18. The method of claim 17, wherein the hashing table includes a plurality of bins with each bin being associated with a primary sender and a secondary sender, the secondary sender associated with replicated media data portions.

19. The method of claim 17, wherein the hashing function produces a media data hashing value from a media data block number and a media data segment number;

and the media data hashing value maps the media data block to a bin of the hashing table.

20. The method of claim 17, wherein the media data portions are located using the hashing function and the hashing table by mapping the media data portions to bins of the hashing table with each bin of the hashing table being associated with at least one device that stores the media data portions mapping thereto.