Priority mechanism for distributed sending of media data

• US 20050081246A1
• Filed: 03/12/2004
• Published: 04/14/2005
• Est. Priority Date: 10/10/2003
• Status: Active Grant

• Current Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Original Assignee: Microsoft Corporation
• Inventors: Baldwin, James Armand, Barrett, Peter T., Green, Dustin L.
• Granted Patent: US 7,443,791 B2
• Time in Patent Office: Days
• US Class Current: 725/105
• 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 multiple schedulers and senders are installed across the multiple devices. Schedulers formulate send requests that stipulate particular media data portions and designate destination clients. Each send request is associated with a send priority. The send requests are transmitted from the multiple schedulers to the multiple senders. The senders rank respective received send requests according to their associated send priorities. Based on the ranked respective send requests and responsive to a respective send bandwidth of each sender, the senders ascertain respective threshold priorities. Each respective threshold priority corresponds to the lowest send priority of all send requests that have been accepted for sending by a respective sender. By comparing individual send priorities associated with individual send requests to respective threshold priorities, the schedulers are able to determine which send requests are selected for sending by respective senders.

Claims

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

transmitting a send request having a priority;

receiving a threshold priority;

comparing the priority of the send request to the threshold priority; and

determining if the send request is selected for sending responsive to the comparing.

2. The one or more processor-accessible media as recited in claim 1, wherein the action of transmitting a send request comprises an action of:

transmitting the send request to a sender that is capable of implementing the send request by sending media data stipulated in the send request to a destination client designated in the send request.

3. The one or more processor-accessible media as recited in claim 2, wherein the action of receiving a threshold priority comprises an action of:

receiving the threshold priority from the sender that is capable of implementing the send request, the threshold priority representing a send request cutoff that indicates a least important priority for send requests selected for sending by the sender.

4. The one or more processor-accessible media as recited in claim 1, wherein the action of transmitting a send request comprises an action of:

transmitting the send request which is associated with a unique priority;

wherein the send request stipulates media data, and the unique priority is dependent at least in part on whether the stipulated media data comprises deadline media data versus early media data, with deadline media data having a relatively higher priority.

5. The one or more processor-accessible media as recited in claim 1, wherein the action of transmitting a send request comprises an action of:

transmitting the send request which is associated with a unique priority;

wherein the send request stipulates media data, and the unique priority is dependent at least in part on whether the stipulated media data is associated with fewer capable senders versus many capable senders, with association with fewer capable senders having a relatively higher priority.

6. The one or more processor-accessible media as recited in claim 1, wherein the actions of comparing and determining comprise actions of:

ascertaining if the priority of the send request is more important than the threshold priority; and

if so, determining that the send request is selected for sending of media data as stipulated by the send request.

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

if the priority of the send request is not ascertained to be more important than the threshold priority, determining that the send request is not selected for sending of media data as stipulated by the send request.

8. The one or more processor-accessible media as recited in claim 1, wherein the action of transmitting a send request comprises an action of transmitting the send request to a sender that is capable of implementing the send request;

and

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

if the send request is not determined to be selected for sending responsive to the comparing,

determining if the priority of the send request is more important than at least one other threshold priority received from at least one other sender that is capable of implementing the send request; and

if so, transmitting the send request to the at least one other sender that is capable of implementing the send request.

9. The one or more processor-accessible media as recited in claim 1, 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 a media data stream to clients.

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

receiving a plurality of send requests, each respective send request of the plurality of send requests having a respective priority;

ascertaining a threshold priority based on the respective priorities of the respective send requests and responsive to a send bandwidth; and

broadcasting the threshold priority.

11. The one or more processor-accessible media as recited in claim 10, wherein the action of receiving a plurality of send requests comprises an action of:

receiving the plurality of send requests from a plurality of schedulers that formulated each send request of the plurality of send requests to include a stipulated media data portion, to designate a destination client, and to have a unique priority.

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

ranking the plurality of send requests according to respective priorities of respective send requests of the plurality of send requests.

13. The one or more processor-accessible media as recited in claim 12, wherein the action of ascertaining a threshold priority comprises an action of:

detecting a particular send request of the plurality of send requests that corresponds to a send request cutoff using the ranked plurality of send requests and the send bandwidth.

14. The one or more processor-accessible media as recited in claim 10, wherein the action of ascertaining a threshold priority comprises an action of:

accumulating bandwidth consumption of the plurality of send requests from a send request that is most important to those that are less important in accordance with the respective priorities thereof.

15. The one or more processor-accessible media as recited in claim 14, wherein the action of ascertaining a threshold priority comprises a further action of:

determining a last send request at which the accumulated bandwidth consumption is less than or equal to the send bandwidth.

16. The one or more processor-accessible media as recited in claim 15, wherein the action of ascertaining a threshold priority comprises a further action of:

setting the threshold priority to a priority corresponding to the last send request at which the accumulated bandwidth consumption is less than or equal to the send bandwidth.

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

discarding send requests of the plurality of send requests that do not fit within the send bandwidth; and

partially discarding and partially retaining a send request of the plurality of send requests that is only partially within the send bandwidth.

18. The one or more processor-accessible media as recited in claim 10, wherein the action of broadcasting the threshold priority comprises at least one action of:

unicasting the threshold priority to a plurality of schedulers;

or

multicasting the threshold priority to the plurality of schedulers.

19. The one or more processor-accessible media as recited in claim 10, 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 the plurality of send requests.

20. An arrangement for prioritized distributed sending of media data, the arrangement comprising:

scheduler means for requesting sending of media data via send requests having send priorities;

the scheduler means including determination means for determining if the send requests have been selected for sending using the send priorities and a threshold priority; and

sender means for sending media data portions in response to the send requests in accordance with the send priorities;

the sender means including ascertainment means for ascertaining the threshold priority based on the send priorities of the send requests and responsive to a send bandwidth of the sender means.

21. The arrangement as recited in claim 20, wherein the scheduler means further comprises:

formulation means for originally formulating the send requests to include designated destination clients, stipulated media data portions, and the send priorities.

22. The arrangement as recited in claim 20, wherein the scheduler means further comprises:

transmission means for transmitting each send request of the send requests to a sender means of a plurality of sender means, each sender means of the plurality of sender means having at least one send request being transmitted thereto in dependence on which media data portions are associated therewith.

23. The arrangement as recited in claim 20, wherein the determination means further comprises:

comparison means for comparing the send priorities to the threshold priority.

24. The arrangement as recited in claim 20, wherein the scheduler means further comprises:

checking means for checking whether another threshold priority is lower than the send priorities of send requests that are not selected for sending.

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

a plurality of scheduler means and a plurality of sender means that are exchanging send requests and threshold priorities.

26. The arrangement as recited in claim 20, wherein the sender means further comprises:

ranking means for ranking the send requests from most important to least important according to the send priorities.

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

28. A system that is configured to perform actions comprising:

transmitting a send request associated with a send priority from a scheduler to a sender;

ascertaining a threshold priority at the sender based on a ranking of send requests and responsive to a send bandwidth of the sender, the ranking of send requests including the send request from the scheduler;

transmitting the threshold priority to the scheduler; and

determining at the scheduler if the send request is being honored by the sender using the threshold priority and the send priority associated with the send request.

29. The system as recited in claim 28, wherein the system is configured to perform further actions comprising:

ranking the send requests in order of respective priorities of respective send requests of the send requests to produce the ranking of send requests; and

detecting a send request cutoff corresponding to a send request (i) that fits within the send bandwidth of the sender and (ii) that is associated with a lowest send priority of all send requests that fit within the send bandwidth of the sender.

30. The system as recited in claim 28, wherein the system comprises a plurality of devices;

and wherein (i) the scheduler and the sender are functioning on a single device of the plurality of devices or (ii) the scheduler is functioning on a first device of the plurality of devices, and the sender is functioning on a second device of the plurality of devices.

31. The system as recited in claim 28, wherein the system is configured to perform further actions comprising:

receiving the send request at the sender from the scheduler; and

transmitting, in response to the receiving, an acknowledgment from the sender to the scheduler if the send priority associated with the send request is more important than a current threshold priority of the sender.

32. The system as recited in claim 28, wherein the action of determining comprises:

determining that the send request is being honored by the sender if (i) the send priority associated with the send request is as important or more important than the threshold priority of the sender, (ii) an acknowledgment is received at the scheduler from the sender in response to the transmitting of the send request, and (iii) the threshold priority is marked by the sender as being final.

33. The system as recited in claim 28, wherein the system is configured to perform further actions comprising:

if the send request is not determined to be honored by the sender, then;

checking, at the scheduler, if another sender that is capable of sending media data as stipulated in the send request has transmitted another threshold priority that is less important than the send priority associated with the send request; and

if so, transmitting a subsequent send request associated with the send priority from the scheduler to the other sender.

34. The system as recited in claim 28, wherein the system is configured to perform further actions comprising:

if the send request is not determined to be honored by the sender, then;

checking, at the scheduler, if another sender has transmitted another threshold priority that is less important than another send priority that is assignable to the send request by the scheduler; and

if so, transmitting from the scheduler to the other sender a subsequent send request associated with the other send priority as assigned by the scheduler.

35. One or more processor-accessible media comprising processor-executable instructions that, when executed, cause a system to create schedulers that are capable of formulating send requests having send priorities in order to provide media data streams to clients;

to establish senders that are respectively associated with respective media data portions and adapted to ascertain respective threshold priorities each time slot based on respective prioritized rankings of the respective send requests received at each sender from the schedulers and responsive to respective send bandwidths of each respective sender; and

to enable the schedulers to determine if send requests are being honored by respective senders using the respective ascertained threshold priorities thereof.

36. The one or more processor-accessible media as recited in claim 35, comprising the processor-executable instructions wherein each respective send bandwidth comprises a percentage, which is less than 100 percent, of a respective maximum outgoing bandwidth that is available at each respective sender of the established senders.

37. The one or more processor-accessible media as recited in claim 35, comprising the processor-executable instructions wherein the schedulers are adapted to transmit subsequent send requests to the senders in response to the ascertained threshold priorities.

38. The one or more processor-accessible media as recited in claim 37, comprising the processor-executable instructions wherein respective senders of the senders are further adapted to ascertain respective intermediate threshold priorities within each time slot based on respective prioritized rankings of the subsequent send requests received at each sender from the schedulers and responsive to the respective send bandwidth of each respective sender.

39. The one or more processor-accessible media as recited in claim 37, comprising the processor-executable instructions wherein the subsequent send requests are at least one of (i) transmitted to different senders as compared to original send requests and/or (ii) assigned a more important send priority as compared to the original send requests.

40. The one or more processor-accessible media as recited in claim 35, comprising the processor-executable instructions wherein each respective scheduler uses no more than a particular percentage, with the particular percentage being less than 100 percent, of a respective allotted portion of an aggregate send bandwidth of the senders that has been allotted to each respective scheduler when allocating media data sends to ensure future guaranteed media data delivery deadlines.