Media Stream Scheduling for Hiccup-Free Fast-Channel-Change in the Presence of Network Chokepoints

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.

1 . A system for media stream scheduling comprising:
 a processor;   a media stream scheduler operating on the processor, the media stream scheduler operative to:   provide a media-stream delivery deadline schedule comprising a visibility window in which time is divided into a succession of timeslots;   allocate data of one or more media streams being transmitted over a media-stream network to one of the succession of timeslots, wherein a timeslot specifies a deadline by which data allocated to it must be sent to a media-stream presentation device;   select which data to send at a present time according to the delivery deadline schedule, wherein such selecting comprises:
 choosing first data, from the one or more media streams, allocated to a timeslot having a deadline at or before the present time, 
 choosing enough of second data from other of the one or more media streams having a non-satisfied minimum bit-rate at or before the present time to place into the media-stream delivery deadline schedule so that the minimum bit-rate specified is achieved, and 
 choosing other third data from any stream of the one or more media streams to sum with the first data and the second data to an amount that is operative to fit through one or more bandwidth-limiting chokepoints of the media-stream network; 
   calculate an available data-rate reservation on a time-dependent basis through the media-stream network to the presentation device; and   insert delivery deadlines of data of a new media stream into the delivery deadline schedule of outgoing media streams being sent via the media-stream network, wherein data scheduled proximate to a start of the new media stream is scheduled to be delivered via the media-stream 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 by which data from the outgoing media streams will be delivered via the network.   
     
     
         2 . A system as recited in  claim 1 , wherein the media-stream delivery deadline schedule also specifies a minimum bit-rate at which data of the one or more media streams being transmitted over the media-stream network must be sent to the media-stream presentation device, in such a way that the specified minimum bit-rate at which data of the one or more media streams must be sent is specified in a time-dependent fashion. 
     
     
         3 . A system as recited in  claim 1 , wherein the other third data from any stream is the earliest data from any stream in the deadline schedule that fits through the chokepoints. 
     
     
         4 . A system as recited in  claim 1 , wherein the media stream scheduler is further operative to receive a request to start the new media stream from the media-stream presentation device on the media-stream network, wherein the available data-rate is limited by the one or more chokepoints in the media-stream network and their already-reserved time-dependent data-rate usage. 
     
     
         5 . A system as recited in  claim 1 , wherein the media stream scheduler is further operative to schedule data which is not proximate to the start of the new media stream to be delivered before a designated time code. 
     
     
         6 . A system as recited in  claim 1 , wherein the media stream scheduler is further operative to determine when the media-stream presentation device is safe to present the new media stream. 
     
     
         7 . A system as recited in  claim 6 , wherein the determination of when the media-stream presentation device is safe to present the new media stream is based on determining an amount of extra data required to avoid underflow. 
     
     
         8 . A computer-implemented method comprising:
 providing a media-stream delivery deadline schedule comprising a visibility window in which time is divided into a succession of timeslots;   
       allocating data of one or more media streams being transmitted over a media-stream network to one of the timeslots, wherein a timeslot specifies the deadline by which data allocated to it must be sent to a media-stream presentation device; 
       selecting which data to send at a present time according to the delivery deadline schedule, wherein such selecting comprises:
 choosing first data, from the one or more media streams, allocated to a timeslot having a deadline at or before the present time, 
 choosing enough of second data from other of the one or more media streams having a non-satisfied minimum bit-rate at or before the present time to place into the media-stream delivery deadline schedule so that the minimum bit-rate specified is achieved, and 
 choosing other third data from any stream of the one or more media streams to sum with the first data and the second data to an amount that is operative to fit through one or more bandwidth-limiting chokepoints of the media-stream network; 
 
       calculating an available data-rate reservation on a time-dependent basis through the media-stream network to the presentation device; and 
       inserting delivery deadlines of data of a new media stream into the delivery deadline schedule of outgoing media streams being sent via the media-stream network, wherein data scheduled proximate to a start of the new media stream is scheduled to be delivered via the media-stream 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 by which data from the outgoing media streams will be delivered via the network. 
     
     
         9 . A computer-implemented method as recited in  claim 8 , wherein the media-stream delivery deadline schedule also specifies a minimum bit-rate at which data of the one or more media streams being transmitted over the media-stream network must be sent to the media-stream presentation device, in such a way that the specified minimum bit-rate at which data of the one or more media streams must be sent is specified in a time-dependent fashion. 
     
     
         10 . A computer-implemented method as recited in  claim 8 , wherein the other third data from any stream is the earliest data from any stream in the deadline schedule that fits through the chokepoints. 
     
     
         11 . A computer-implemented method as recited in  claim 8 , wherein the method further comprises receiving a request to start the new media stream from the media-stream presentation device on the media-stream network, wherein the available data-rate is limited by the one or more chokepoints in the media-stream network and their already-reserved time-dependent data-rate usage. 
     
     
         12 . A computer-implemented method as recited in  claim 8 , wherein the method further comprises scheduling data which is not proximate to the start of the new media stream to be delivered before a designated time code. 
     
     
         13 . A computer-implemented method as recited in  claim 8 , wherein the method further comprises determining when the media-stream presentation device is safe to present the new media stream. 
     
     
         14 . A computer-implemented method as recited in  claim 13 , wherein the determination of when the media-stream presentation device is safe to present the new media stream is based on determining an amount of extra data required to avoid underflow. 
     
     
         15 . A system for media stream scheduling comprising:
 a logic device; and   
       a media stream scheduler operating on the logic device to:
 provide a media-stream delivery deadline schedule corresponding to a succession of timeslots; 
 allocate data of one or more media streams being transmitted over a network to one of the succession of timeslots, wherein each of the timeslots specifies a delivery deadline by which data allocated to it is sent to a presentation device; 
 select which data to send at a present time according to the media-stream delivery deadline schedule, wherein such selecting comprises:
 choosing first data from the one or more media streams; 
 allocating the first data to one of the timeslots having a deadline at or before the present time; 
 choosing enough of second data from other of the one or more media streams having a non-satisfied minimum bit-rate at or before the present time to place into the media-stream delivery deadline schedule so that the minimum bit-rate specified is achieved, and 
 choosing other third data from any stream of the one or more media streams to sum with the first data and the second data to an amount that is operative to fit through one or more bandwidth-limiting chokepoints of the network; 
 
 calculate an available data-rate reservation on a time-dependent basis through the network to the presentation device; and 
 insert delivery deadlines of data of a new media stream into the media-stream delivery deadline schedule of outgoing media streams being sent via the network, wherein data scheduled proximate to a start of the new media 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 by which data from the outgoing media streams will be delivered via the network. 
 
     
     
         16 . A system as recited in  claim 15 , wherein the media-stream delivery deadline schedule also specifies a minimum bit-rate at which data of the one or more media streams being transmitted over the network must be sent to the presentation device, in such a way that the specified minimum bit-rate at which data of the one or more media streams must be sent is specified in a time-dependent fashion. 
     
     
         17 . A system as recited in  claim 15 , wherein the other third data from any stream is the earliest data from any stream in the deadline schedule that fits through the chokepoints. 
     
     
         18 . A system as recited in  claim 15 , wherein the media stream scheduler receives a request to start the new media stream from the presentation device via the network, wherein the available data-rate is limited by the one or more chokepoints in the network and the associated already-reserved time-dependent data-rate usage. 
     
     
         19 . A system as recited in  claim 15 , wherein the media stream scheduler schedules data, which is not proximate to the start of the new media stream, to be delivered before a designated time. 
     
     
         20 . A system as recited in  claim 1 , wherein the media stream scheduler determines when the presentation device is safe to present the new media stream based on determining an amount of extra data required to avoid underflow.