Scheduling scheme for distributed sending of media data

• US 7,545,812 B2
• Filed: 03/12/2004
• Issued: 06/09/2009
• 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): Hoang; Thai D
• Application Number:
  US10/798,993
• Publication Number:
  US 20050078680A1
• Time in Patent Office: 1,915 Days
• Field of Search: 37039521-39541
• US Class Current: 370/395.4
• 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 processor;

a memory coupled to the processor;

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 for scheduling delivery of media data blocks to the at least one client;

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

wherein the sender increments 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 transmits 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 sends 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 3, wherein the scheduler transmits 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 decrements 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 decrements 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 performs 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. A method for a scheduling scheme to facilitate the distributed sending of media data, the method implemented on a computing device by a processor configured to execute instructions that, when executed by the processor, direct the computing device to perform acts comprising:

dividing, by a scheduler of the computing device, a plurality of media data blocks of a media data stream into three regions comprising a current region, an alternative send request region, and a look-ahead region;

reserving, by the scheduler of the computing device, the media data blocks, wherein the reserving comprises looking ahead along the media data stream to reserve the media data blocks for subsequent sending to clients; and

sending, by a sender of the computing device, the media data blocks, wherein the sending comprises locking the media data blocks responsive to the reserving until after the locked media data blocks have been sent to the clients.

14. The method as recited in claim 13, wherein reserving further comprises:

requesting locks on the media data blocks by identifying to the sender media data blocks to be reserved.

15. The method as recited in claim 13, wherein the reserving further comprises:

canceling locks on the media data blocks by identifying to the sender media data blocks to be unreserved.

16. The method as recited in claim 13, further comprising:

requesting sends of the media data blocks from the sender to the clients after the scheduler has caused the sender to reserve the media data blocks.

17. The method as recited in claim 13, further comprising:

counting, by the sender of the computing device, reserved usage of each media data block of the media data blocks responsive to look ahead requests received from the scheduler.

18. The method as recited in claim 13, further comprising:

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

19. The method as recited in claim 13, wherein the instructions are encoded on one or more processor-accessible media.

20. A system comprising:

a processor;

a memory coupled to the processor;

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, wherein the sender is for sending the associated at least one media data block to clients; and

a scheduler that is associated with a client, wherein the scheduler divides 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.

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

and wherein the scheduler transmits 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.

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

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

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

and wherein the scheduler transmits 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.

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

and

further comprising;

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

wherein the scheduler transmits 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.