Media organization for distributed sending of media data

• US 7,516,232 B2
• Filed: 03/12/2004
• Issued: 04/07/2009
• Est. Priority Date: 10/10/2003
• Status: Active Grant

• Current Assignee: ROVI Product Corporation (Xperi Inc.)
• Original Assignee: Microsoft Corporation
• Inventors: Barrett, Peter T., Green, Dustin L., Baldwin, James Armand
• Primary Examiner(s): Jean, Frantz B
• Application Number:
  US10/800,309
• Publication Number:
  US 20050081243A1
• Time in Patent Office: 1,852 Days
• Field of Search: 709/231, 709/247, 709/203, 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. One or more processor-accessible storage media comprising processor-executable instructions that, when executed, direct at least one device to perform actions 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 a bin of a hash table, the bin of the hash table associated with a device;

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;

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

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

2. The one or more processor-accessible media as recited in claim 1, comprising the processor-executable instructions wherein the bin of the hash table is associated with a sender that is capable of sending the media data block to a client.

3. The one or more processor-accessible media as recited in claim 1, comprising the processor-executable instructions that, when executed, direct the at least one device to perform a further action comprising:

storing the media data block in a device associated with the bin of the hash table.

4. The one or more processor-accessible media as recited in claim 1, wherein the action of storing the media data block comprises an action of:

storing the media data block in association with a sender that is associated with the bin of the hash table, the sender functioning on the device.

5. The one or more processor-accessible media as recited in claim 1, comprising the processor-executable instructions that, when executed, direct the at least one device to perform a further action comprising:

transmitting a send request that stipulates the media data block to a sender associated with the bin of the hash table, the sender capable of sending the media data block to a client.

6. The one or more processor-accessible media as recited in claim 1, wherein the action of combining comprises an action of:

concatenating the media data segment number and the media data block number to form the media data identification value.

7. The one or more processor-accessible media as recited in claim 1, wherein the action of applying comprises an action of:

applying the media data identification value to the hashing function that uses a linear feedback shift register (LFSR) to produce the media data hash value.

8. The one or more processor-accessible media as recited in claim 1, wherein the action of mapping comprises an action of:

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

wherein the first device has a primary role with respect to the bin and stores all media data blocks mapping thereto, and the second device has a secondary role with respect to the bin and stores media data blocks mapping thereto that also correspond to a predetermined popularity level.

9. One or more processor-accessible storage media comprising processor-executable instructions that, when executed, cause a system to determine popularity of media data portions in accordance with a number of clients requesting each media data portion;

to locate the media data portions using a hashing function and a hashing table; and

to replicate those media data portions that are within a top predetermined popularity percentage,

wherein the system determines 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,

and wherein the system performs actions 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;

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

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

10. The one or more processor-accessible media as recited in claim 9, comprising the processor-executable instructions 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.

11. The one or more processor-accessible media as recited in claim 9, comprising the processor-executable instructions wherein each media data portion comprises a media data block;

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.

12. The one or more processor-accessible media as recited in claim 9, comprising the processor-executable instructions 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.