Media stream scheduling for hiccup-free fast-channel-change in the presence of network chokepoints

• US 7,444,419 B2
• Filed: 10/10/2003
• Issued: 10/28/2008
• Est. Priority Date: 10/10/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Green, Dustin L.
• Primary Examiner(s): Blair; Douglas B
• Application Number:
  US10/683,132
• Publication Number:
  US 20050080904A1
• Time in Patent Office: 1,845 Days
• Field of Search: 709/231, 709/233, 709/234
• US Class Current: 709/231
• CPC Class Codes: H04L 65/764 at the destination reformatting of additional data in video clients H04N21/4355
• CPC Class Codes: H04N 21/238 Interfacing the downstream path of the transmission network, e.g. adapting the transmission rate of a video stream to network bandwidth; Processing of multiplex streams hybrid fiber coaxial [HFC] networks for downstream channel allocation for video distribution H04L12/2801; flow control in packet networks H04L47/10; real-time communication protocols in data switching networks H04L65/00; scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/2387 Stream processing in response to a playback request from an end-user, e.g. for trick-play
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/242 Synchronization processes, e.g. processing of PCR [Program Clock References] arrangements for synchronising broadcast or distribution via plural systems in broadcast distribution systems H04H20/18
• CPC Class Codes: H04N 21/26216 involving the channel capacity, e.g. network bandwidth admission control, resource allocation in open networks H04L12/5692; flow control in packet networks H04L47/10; establishing a schedule or organising the servicing of application requests taking into account QoS H04L67/61
• CPC Class Codes: H04N 21/4384 involving operations to reduce the access time, e.g. fast-tuning for reducing channel switching latency

Abstract

An implementation, as described herein, facilitates fast start-up of a new media stream while avoiding temporal interruption (i.e., “hiccups”) of the presentation of that new media stream. At least one implementation, described herein, coordinates the delivery of multiple simultaneous media streams on a media-stream network. Its coordination accounts for traversal of bandwidth-restricted chokepoints; quickly stopping delivery of one or more media streams from the set of streams; quickly initiating delivery and presentation of one or more new media streams not previously in the set (i.e., a “channel change”); and producing clean playback of all of the streams in the set, despite their different timelines. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Claims

1. A computer-readable medium having processor-executable instructions that, when executed by a processor, performs a method comprising:

receiving a request to start a new media stream from a media-stream presentation device on a media-stream network having one or more bandwidth-limiting chokepoints therein;

calculating an available data-rate reservation on a time-dependent basis through the network to the presentation device, wherein the available data-rate is limited by the one or more chokepoints in the network and their already-reserved time-dependent data-rate usage;

inserting delivery deadlines of data of the new media stream into a delivery deadline schedule of outgoing media streams being sent via the network, wherein data scheduled proximate to a start of the new stream is scheduled to be delivered via the network to the presentation device at a data-rate equal to or greater than the calculated available data-rate, wherein the delivery deadline schedule determines a minimum bit-rate and a deadline by which data from the outgoing media streams will be delivered via the network.

2. A medium as recited in claim 1, wherein the inserting further comprises scheduling data which is not proximate the start of the new stream to be delivered before designated decode time(s)of that data.

3. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream.

4. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises:

determining a value representing how much extra data would be required before startup in order to avoid underflow due to playback of a particular frame at a particular time;

determining a start time that would be required to cause the particular frame to play at the particular time;

determining a separate maximum value for each of several possible ranges of start times of the determined value representing how much extra data would be required to avoid underflow due to all known frames and the possible ranges of start times.

5. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises for each range of start time, adding the amount of extra data required to start by the range of start time to the amount of reserved bit-rate data and deadline data that will already be delivered by the beginning of the range of start time to obtain a total amount of data required to start at a time within the range of start time with no danger of underflow at a later time due to the playback of all known frames.

6. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises determining of a minimum start time which guarantees that the last known frame will be delivered before the PCR (program clock reference, or encoder-specified delivery time) of the last data of the last known frame, and wherein the minimum start time is at least as great as the current time.

7. A medium as recited in claim 1, wherein the method further comprises:

receiving initial media-stream delivery and playback schedule information for one or more media streams being delivered over the network from one or more media-stream encoders or providers;

delaying playback of such media streams by presentation devices by at least a defined amount of time relative to the received playback schedule.

8. A medium as recited in claim 1, wherein the method further comprises determining the dynamic bandwidth capacity of the one or more chokepoints over a defined amount of time.

9. A medium as recited in claim 1, wherein the inserting further comprises adjusting the delivery deadline schedule so that the data of the new stream is given as much reserved bit-rate as possible for delivery via the network given the one or more chokepoints in the network and the preexisting delivery deadlines and bit-rates that are already scheduled.

10. A medium as recited in claim 1, wherein the inserting further comprises assigning the delivery deadlines for the data of the new stream as late into the deadline delivery schedule as possible while still avoiding underflow of that new stream at the presentation device.

11. A medium as recited in claim 1, wherein the method further comprises determining the amount of otherwise allocated dynamic bandwidth capacity of the one or more chokepoints over a defined amount of time.

12. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises providing a temporally based test of whether the device has received enough data to begin playback during a specified time interval.

13. A medium as recited in claim 1, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises providing a start-up profile that indicates the conditions under which the presentation device should start presenting the new media stream.

14. A medium as recited in claim 1, wherein the network is, at least partially, unicast.

15. A computing device comprising a medium as recited in claim 1.

16. A method facilitating fast start-up of a new media stream, the method comprising:

receiving a request to start a new media stream from a media-stream presentation device on a media-stream network having one or more bandwidth-limiting chokepoints therein;

calculating an available data-rate reservation on a time-dependent basis through the network to the presentation device, wherein the available data-rate is limited by the one or more chokepoints in the network and their already-reserved time-dependent data-rate usage;

inserting delivery deadlines of data of the new media stream into a delivery deadline schedule of outgoing media streams being sent via the network, wherein data scheduled proximate to a start of the new stream is scheduled to be delivered via the network to the presentation device at a data-rate equal to or greater than the calculated available data-rate, wherein the delivery deadline schedule determines a minimum bit-rate and a deadline by which data from the outgoing media streams will be delivered via the network.

17. A method as recited in claim 16, wherein the inserting further comprises scheduling data which is not proximate the start of the new stream to be delivered before designated decode time(s) of that data.

18. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream.

19. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises:

determining a value representing how much extra data would be required before startup in order to avoid underflow due to playback of a particular frame at a particular time;

determining a start time that would be required to cause the particular frame to play at the particular time;

determining a separate maximum value for each of several possible ranges of start times of the determined value representing how much extra data would be required to avoid underflow due to all known frames and the possible ranges of start times.

20. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises for each range of start time, adding the amount of extra data required to start by the range of start time to the amount of reserved bit-rate data and deadline data that will already be delivered by the beginning of the range of start time to obtain a total amount of data required to start at a time within the range of start time with no danger of underflow at a later time due to the playback of all known frames.

21. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises determining of a minimum start time which guarantees that the last known frame will be delivered before the PCR (program clock reference, or encoder-specified delivery time) of the last data of the last known frame, and wherein the minimum start time is at least as great as the current time.

22. A method as recited in claim 16, wherein the method further comprises:

receiving initial media-stream delivery and playback schedule information for one or more media streams being delivered over the network from one or more media-stream encoders or providers;

delaying playback of such media streams by presentation devices by at least a defined amount of time relative to the received playback schedule.

23. A method as recited in claim 16, wherein the method further comprises determining the dynamic bandwidth capacity of the one or more chokepoints over a defined amount of time.

24. A method as recited in claim 16, wherein the inserting further comprises adjusting the delivery deadline schedule so that the data of the new stream is given as much reserved bit-rate as possible for delivery via the network given the one or more chokepoints in the network and the preexisting delivery deadlines and bit-rates that are already scheduled.

25. A method as recited in claim 16, wherein the inserting further comprises assigning the delivery deadlines for the data of the new stream as late into the deadline delivery schedule as possible while still avoiding underflow of that new stream at the presentation device.

26. A method as recited in claim 16, wherein the method further comprises determining the amount of otherwise allocated dynamic bandwidth capacity of the one or more chokepoints over a defined amount of time.

27. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises providing a temporally based test of whether the device has received enough data to begin playback during a specified time interval.

28. A method as recited in claim 16, wherein the method further comprises facilitating determination of when the presentation device should start presenting the new media stream, wherein such facilitating comprises providing a start-up profile that indicates the conditions under which the presentation device should start presenting the new media stream.

29. A method as recited in claim 16, wherein the network is, at least partially, unicast.

30. A scheduler system comprising:

a physical component;

a receiving unit configured to receive a request to start a new media stream from a media-stream presentation device on a media-stream network having one or more bandwidth-limiting chokepoints therein;

a bandwidth-capacity calculator configured to calculate an available data-rate reservation on a time-dependent basis through the network to the presentation device, wherein the available data-rate is limited by the one or more chokepoints in the network and their already-reserved time-dependent data-rate usage;

a scheduling sub-system configured to insert delivery deadlines of data of the new media stream into a delivery deadline schedule of outgoing media streams being sent via the network, wherein data scheduled proximate to a start of the new stream is scheduled to be delivered via the network to the presentation device at a data-rate equal to or greater than the calculated available data-rate, wherein the delivery deadline schedule determines a minimum bit-rate and a deadline by which data from the outgoing media streams will be delivered via the network.

31. A system as recited in claim 30, wherein the receiving unit is further configured to receive initial media-stream delivery schedule information for one or more media streams being delivered over the network from one or more media-stream encoders or providers.

32. A system as recited in claim 30, wherein the bandwidth-capacity calculator is further configured to determine the dynamic bandwidth capacity of the one or more chokepoints over a defined amount of time.

33. A system as recited in claim 30, wherein the network is, at least partially, unicast.