Scheduling scheme for distributed sending of media data

• US 20050078680A1
• 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,545,812 B2
• Time in Patent Office: Days
• US Class Current: 370/395.400
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• 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/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Media data is distributed across multiple devices, and the media data is sent therefrom by multiple senders under control of multiple schedulers. For media data blocks in a look-ahead region, schedulers transmit look ahead requests to senders in order to reserve upcoming media data blocks. In a described implementation, a look ahead request identifies a media data block. The receiving sender increments a block usage counter corresponding to the identified media data block responsive to the look ahead request. As part of a look ahead operation, if the media data block is not already in RAM, the sender preloads the media data block into RAM. While the block usage counter indicates that the corresponding media data block is locked, the sender maintains the media data block in RAM. A look ahead cancel message transmitted from the scheduler to the sender prompts the sender to decrement the block usage counter.

Claims

1. A system comprising:

a sender associated with at least one media data block, the sender including a block usage counter corresponding to the at least one media data block;

wherein the sender does not swap out the at least one media data block when the corresponding block usage counter indicates that the at least one media data block is locked; and

a scheduler associated with at least one client, the scheduler capable of scheduling delivery of media data blocks to the at least one client;

wherein the scheduler is adapted to transmit to the sender a look ahead request identifying the at least one media data block;

wherein the sender is adapted to increment the block usage counter corresponding to the at least one media data block in response to receiving from the scheduler the look ahead request identifying the at least one media data block.

2. The system as recited in claim 1, wherein the scheduler is further adapted to transmit to the sender a send request, which designates the at least one client and stipulates the at least one media data block, after transmission of the look ahead request identifying the at least one media data block.

3. The system as recited in claim 2, wherein the sender is capable of sending the stipulated at least one media data block to the designated at least one client responsive to receipt of the send request from the scheduler.

4. The system as recited in claim 2, wherein the scheduler is further adapted to transmit to the sender a look ahead cancel message, which identifies the at least one media data block, after expiration of a retry period.

5. The system as recited in claim 1, wherein the scheduler transmits to the sender the look ahead request in order to reserve and/or preload the at least one media data block prior to transmission to the sender of a send request stipulating the at least one media data block.

6. The system as recited in claim 1, wherein the sender is further adapted to decrement the block usage counter corresponding to the at least one media data block in response to receiving from the scheduler a look ahead cancel message identifying the at least one media data block.

7. The system as recited in claim 1, wherein the sender is further adapted to decrement the block usage counter corresponding to the at least one media data block if the scheduler experiences a failure.

8. The system as recited in claim 1, wherein the sender is further adapted to perform a look ahead operation on the at least one media data block in response to receiving from the scheduler the look ahead request identifying the at least one media data block.

9. The system as recited in claim 8, wherein the sender performs the look ahead operation by checking if the at least one media data block is already present in relatively low-latency memory and, if not, by loading the at least one media data block into the relatively low-latency memory from relatively high-latency memory.

10. The system as recited in claim 9, further comprising:

random access memory (RAM) that forms, at least partially, the relatively low-latency memory; and

mass storage that forms, at least partially, the relatively high-latency memory.

11. The system as recited in claim 1, wherein the system comprises (i) a device on which the sender and the scheduler are functioning or (ii) a first device on which the scheduler is functioning and a second device on which the sender is functioning.

12. The system as recited in claim 1, wherein the block usage counter indicates that the corresponding at least one media data block is locked in random access memory (RAM) when the block usage counter comprises a nonzero value.

13. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct at least one device to perform actions comprising:

formulating a look ahead request to identify a media data block that provides media data for a media data stream being sent to a client, the media data provided by the media data block to be used by the client in a future timeslot; and

transmitting the look ahead request to a sender in order to precipitate incrementation of a block usage counter corresponding to the media data block.

14. The one or more processor-accessible media as recited in claim 13, comprising the processor-executable instructions wherein transmission of the look ahead request to the sender is further to precipitate performance of a look ahead operation by the sender, the look ahead operation including preloading of the media data block into random access memory (RAM) associated with the sender if the media data block is not already present in the RAM.

15. The one or more processor-accessible media as recited in claim 13, wherein the action of formulating comprises an action of formulating by a scheduler;

and wherein the action of transmitting comprises an action of transmitting the look ahead request from the scheduler functioning on a first device to the sender functioning on a second device.

16. The one or more processor-accessible media as recited in claim 13, wherein at least a portion of the processor-executable instructions comprise at least part of software implementing a scheduler that is adapted to schedule sending of media data portions of the media data stream to the client.

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

formulating a send request that designates the client as a destination of one or more stipulated media data portions of the media data block; and

transmitting the send request to the sender in order to precipitate sending of the one or more stipulated media data portions to the designated client from the sender.

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

after transmitting a send request stipulating one or more media data portions of the media data block, waiting for expiration of a retry period during which the client can request transmission of the media data; and

after expiration of the retry period;

formulating a look ahead cancel message identifying the media data block; and

transmitting the look ahead cancel message to the sender in order to precipitate decrementation of the block usage counter corresponding to the media data block.

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

scheduling delivery of the media data for the media data stream to the client responsive to network-related choke points.

20. The one or more processor-accessible media as recited in claim 13, wherein the media data of the media data stream is logically divided into media data of a current region, media data of an alternative send request region, and media data of a look-ahead region;

and wherein the media data block identified by the look ahead request is part of the media data of the look-ahead region.

21. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct at least one device to perform actions comprising:

receiving a look ahead request identifying a media data block;

incrementing a block usage counter corresponding to the media data block in response to receiving the look ahead request;

receiving a look ahead cancel message identifying the media data block; and

decrementing the block usage counter corresponding to the media data block in response to receiving the look ahead cancel message;

wherein the media data block corresponding to the block usage counter is maintained in random access memory (RAM) while the block usage counter indicates that the media data block is locked.

22. The one or more processor-accessible media as recited in claim 21, wherein the actions of receiving comprise actions of receiving from a particular scheduler functioning on a different device from the at least one device;

and wherein the processor-executable instructions are capable of receiving look ahead requests and look ahead cancel messages from a plurality of schedulers.

23. The one or more processor-accessible media as recited in claim 21, wherein at least a portion of the processor-executable instructions comprise at least part of software implementing a sender that is adapted to send to clients media data portions with which the sender is associated responsive to send requests received by the sender.

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

receiving a send request that designates a destination client and stipulates one or more media data portions of the media data block; and

sending the stipulated one or more media data portions of the media data block to the designated destination client responsive to receiving the send request;

wherein the receiving a send request and the sending the stipulated one or more media data portions occur between the actions of receiving a look ahead request and receiving a look ahead cancel message.

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

the action of receiving a send request comprises an action of;

receiving the send request from a scheduler; and

the action of sending the stipulated one or more media data portions comprises an action of;

sending the stipulated one or more media data portions to the designated destination client without routing the stipulated one or more media data portions through the scheduler.

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

performing a look ahead operation on the media data block in response to receiving the look ahead request.

27. The one or more processor-accessible media as recited in claim 26, wherein the action of performing a look ahead operation comprises actions of:

checking whether the media data block is present within the RAM; and

if the media data block is not present within the RAM, loading the media data block into RAM from a mass storage device.

28. An arrangement for a scheduling scheme to facilitate the distributed sending of media data, the arrangement comprising:

reservation means for looking ahead along a media data stream to reserve media data blocks for subsequent sending to clients; and

sender means for locking the media data blocks responsive to the reservation means until after the locked media data blocks have been sent to the clients.

29. The arrangement as recited in claim 28, wherein the reservation means comprises:

look ahead means for requesting locks on the media data blocks by identifying to the sender means media data blocks to be reserved.

30. The arrangement as recited in claim 28, wherein the reservation means comprises:

look ahead means for canceling locks on the media data blocks by identifying to the sender means media data blocks to be unreserved.

31. The arrangement as recited in claim 28, further comprising:

request means for requesting sends of the media data blocks from the sender means to the clients after the reservation means has caused the sender means to reserve the media data blocks.

32. The arrangement as recited in claim 28, wherein the sender means comprises:

counter means for counting reserved usage of each media data block of the media data blocks responsive to look ahead requests received from the reservation means.

33. The arrangement as recited in claim 28, wherein the sender means comprises:

operation means for performing look ahead operations to preload media data blocks into low-latency memory responsive to look ahead requests received from the reservation means.

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

35. A system comprising:

a media data segment including a plurality of media data blocks;

a plurality of senders, each sender of the plurality of senders associated with at least one media data block of the plurality of media data blocks and capable of sending the associated at least one media data block to clients; and

a scheduler that is associated with a client, the scheduler adapted to divide the plurality of media data blocks of the media data segment into three regions comprising a current region, an alternative send request region, and a look-ahead region.

36. The system as recited in claim 35, wherein the current region comprises a current media data block;

and wherein the scheduler is further adapted to transmit a send request, which designates the client as a destination and stipulates the current media data block, to a sender of the plurality of senders that is associated with the current media data block.

37. The system as recited in claim 36, wherein the sender that is associated with the current media data block, in response to receiving the send request, sends at least one media data sub-block of the stipulated current media data block to the designated client.

38. The system as recited in claim 35, wherein the alternative send request region comprises at least an early data media data block and a later early data media data block;

and

wherein the scheduler is further adapted;

(i) to transmit a first alternative send request, which designates the client as a destination and stipulates the early data media data block, to a sender of the plurality of senders that is associated with the early data media data block; and

(ii) to transmit a second alternative send request, which designates the client as a destination and stipulates the later early data media data block, to another sender of the plurality of senders that is associated with the later early data media data block.

39. The system as recited in claim 35, wherein the look-ahead region comprises at least one look-ahead media data block;

and wherein the scheduler is further adapted to transmit a look ahead request, which identifies the at least one look-ahead media data block, to a sender of the plurality of senders that is associated with the at least one look-ahead media data block.

40. The system as recited in claim 35, wherein the look-ahead region comprises at least one look-ahead media block;

and

further comprising;

another sender that is associated with the at least one look-ahead media data block;

wherein the scheduler is further adapted to transmit a look ahead request, which identifies the at least one look-ahead media data block, to the other sender and to a sender of the plurality of senders that is also associated with the at least one look-ahead media data block.