Media organization for distributed sending of media data

• US 20050081243A1
• Filed: 03/12/2004
• Published: 04/14/2005
• 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.
• Granted Patent: US 7,516,232 B2
• Time in Patent Office: Days
• US Class Current: 725/86
• 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 media comprising processor-executable instructions that, when executed, direct at least one device to perform actions comprising:

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

ranking the respective media data portions in accordance with their respective numbers of requesting clients; and

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

2. The one or more processor-accessible media as recited in claim 1, wherein:

the action of tracking comprises an action of;

tracking the respective media data portions based on the respective numbers of requesting clients on a per-media data block basis; and

the action of ranking comprises an action of;

ranking the respective media data portions in accordance with their respective numbers of requesting clients on a per-byte basis.

3. The one or more processor-accessible media as recited in claim 1, wherein:

the action of tracking comprises an action of;

tracking the respective media data portions based on the respective numbers of requesting clients at a first granularity level; and

the action of ranking comprises an action of;

ranking the respective media data portions in accordance with their respective numbers of requesting clients at a second, different granularity level.

4. 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:

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

5. The one or more processor-accessible media as recited in claim 4, wherein the action of replicating comprises an action of:

storing respective media data portions, which are determined to have a popularity that is above the predetermined popularity percentage, in association with respective senders that hold a secondary role for respective bins in a hash table, the respective media data portions hashing to the respective bins.

6. 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:

establishing a hash table having a plurality of bins, a particular bin of the plurality of bins including a primary role and a secondary role;

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

7. One or more processor-accessible 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; and

mapping the media data hash value to a bin of a hash table.

8. The one or more processor-accessible media as recited in claim 7, 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.

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

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

11. The one or more processor-accessible media as recited in claim 7, 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.

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

13. The one or more processor-accessible media as recited in claim 7, 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.

14. The one or more processor-accessible media as recited in claim 7, 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 device; and

wherein the processor-executable instructions, when executed, direct the at least one device to perform further actions comprising;

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;

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.

15. The one or more processor-accessible media as recited in claim 7, 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.

16. An arrangement for media organization to facilitate the distributed sending of media data, the arrangement comprising:

popularity means for determining popularity of media data portions; and

replication means for replicating media data portions having a popularity that is greater than a predetermined popularity percentage.

17. The arrangement as recited in claim 16, wherein the replication means further comprises:

storage means for storing the replicated media data portions in secondary devices.

18. The arrangement as recited in claim 16, wherein the popularity means further comprises:

ranking means for ranking the media data portions in accordance with a number of clients requesting each media data portion.

19. The arrangement as recited in claim 16, further comprising:

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

hash means for locating media data portions using (i) at least one indicator of the media data portions and a hashing function and (ii) the hash table means.

20. The arrangement as recited in claim 19, wherein the hash table means comprises:

role means for establishing at least two roles in each bin of the multiple bins in accordance with the predetermined popularity percentage.

21. The arrangement as recited in claim 20, further comprising:

send request means for formulating subsequent send requests using the hash means and responsive to the role means.

22. The arrangement as recited in claim 19, wherein the hash means locates media data portions at the devices associated with the multiple bins of the hash table means by calculating a media data hash value, which maps to the multiple bins, from the at least one indicator of the media data portions and the hashing function.

23. The arrangement as recited in claim 16, wherein the arrangement comprises at least one of (i) one or more processor-accessible media and (ii) at least one device.

24. A system comprising:

a hash table including a plurality of bins, each given bin of the plurality of bins associating 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.

25. The system as recited in claim 24, 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.

26. The system as recited in claim 24, 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.

27. The system as recited in claim 26, 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.

28. The system as recited in claim 26, wherein popularity ranking of the media data blocks is determined on a per-byte basis but the popularity is tracked at a different granularity.

29. The system as recited in claim 26, 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 that are within the top predetermined popularity percentage are replicated at the second device.

30. The system as recited in claim 24, further comprising:

a popularity determiner that determines which media data blocks of the media data blocks mapping to each given bin are within a predetermined popularity percentage.

31. The system as recited in claim 24, further comprising:

a device; and

the given sender;

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

32. The system as recited in claim 24, further comprising:

the given sender, the given sender capable of sending the media data blocks mapping to the given bin to clients.

33. The system as recited in claim 24, further comprising:

a scheduler capable of scheduling 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.

34. One or more processor-accessible 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.

35. The one or more processor-accessible media as recited in claim 34, 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.

36. The one or more processor-accessible media as recited in claim 34, 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.

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

38. The one or more processor-accessible media as recited in claim 34, 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.