Program transmission optimisation

• US 5,421,031 A
• Filed: 12/23/1993
• Issued: 05/30/1995
• Est. Priority Date: 08/23/1989
• Status: Expired due to Term

• Current Assignee: Deta Technology Development LLC (Intellectual Ventures LLC)
• Original Assignee: Delta Beta Pty. Ltd.
• Inventors: De Bey, Henry C.
• Primary Examiner(s): Eisenzopf, Reinhard J.
• Assistant Examiner(s): VO, NGUYEN THANH
• Application Number:
  US08/173,865
• Time in Patent Office: 523 Days
• Field of Search: 348/6, 348/7, 348/8, 348/10, 348/12, 348/17, 348/13, 455/3.1, 455/4.1, 455/4.2, 455/5.1, 455/6.1, 455/6.3, 455/6.2
• US Class Current: 725/92
• CPC Class Codes: G09B 5/065 Combinations of audio and video presentations, e.g. videotapes, videodiscs, television systems
• CPC Class Codes: G09B 5/12 different stations being capable of presenting different information simultaneously G09B5/14 takes precedence
• CPC Class Codes: H04N 2007/1739 the upstream communication being transmitted via a separate link, e.g. telephone line
• CPC Class Codes: H04N 21/2221 being a cable television head-end CATV in broadcast systems H04H20/78
• CPC Class Codes: H04N 21/23109 by placing content in organized collections, e.g. EPG data repository details of retrieval of video data and associated meta data in video databases G06F16/739
• CPC Class Codes: H04N 21/232 Content retrieval operation locally within server, e.g. reading video streams from disk arrays storage management G06F3/0604; details of querying and searching of video data from a database G06F16/739
• CPC Class Codes: H04N 21/236 Assembling of a multiplex stream, e.g. transport stream, by combining a video stream with other content or additional data, e.g. inserting a URL [Uniform Resource Locator] into a video stream, multiplexing software data into a video stream; Remultiplexing of multiplex streams; Insertion of stuffing bits into the multiplex stream, e.g. to obtain a constant bit-rate; Assembling of a packetised elementary stream multiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00
• CPC Class Codes: H04N 21/2408 Monitoring of the upstream path of the transmission network, e.g. client requests monitoring data switching networks utilization H04L43/0876; scheduling or organising the servicing of application requests H04L67/60
• 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/426 Internal components of the client ; Characteristics thereof H04N5/44 takes precedence
• CPC Class Codes: H04N 21/434 Disassembling of a multiplex stream, e.g. demultiplexing audio and video streams, extraction of additional data from a video stream; Remultiplexing of multiplex streams; Extraction or processing of SI; Disassembling of packetised elementary stream demultiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00
• CPC Class Codes: H04N 21/44004 involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6118 involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/6168 involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/6581 Reference data, e.g. a movie identifier for ordering a movie or a product identifier in a home shopping application
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/002 Special television systems not provided for by H04N7/007 - H04N7/18 still pictures via a television channel H04N1/00098
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A system and method of optimizing transmission of a program to multiple users over a distribution system, with particular application to video-on-demand for a CATV network. The system includes, at a head end of the CATV network a scheduling and routing computer for dividing the video program stored in long term fast storage or short term fast storage into a plurality of program segments, and a subscriber distribution node for transmitting the program segments in a redundant sequence in accordance with a scheduling algorithm. At a receiver of the CATV network there is provided a buffer memory for storing the transmitted video program segments for subsequent playback whereby, in use, the scheduling algorithm can ensure that a user'"'"'s receiver will receive all of the program segments in a manner that will enable continuous playback in real time of the program. Under the control of controller the receiver distinguishes received program segments by a segment identifier so that redundant segments captured in capture memory are then stored in buffer memory from which the segments can be retrieved and decompressed in data decompressor for immediate or subsequent viewing.

Claims

1. A method for optimising transmission of a program to multiple receivers over a distribution system, wherein if one or more receivers request a particular program at a same time or different times, the distribution system responds to each request irrespective of whether or not a receiver other than said one or more receivers is already receiving the same particular program, while minimizing transmission resources required to service the requests, the method comprising:

at a head end of the distribution system,

(a) providing the program divided into a plurality of program segments for implementing a scheduling algorithm by which the program segments are organized into a predetermined sequence; and

(b) transmitting the program segments according to the scheduling algorithm such that during a time required for normal playback of the program at the multiple receivers, at least some of the program segments are transmitted more than once simultaneously from the head end to the multiple receivers with no requirement at any time to dedicate the head end of the distribution system to any specific receiver;

and at a receiver of the distribution system,

(c) storing the transmitted program segments in a buffer storage means in the receiver for subsequent playback, wherein if a same program segment is received by the receiver more than once, said same program segment is stored only once in the buffer storage means, and wherein said scheduling algorithm ensures that any receiver will receive all of the program segments in a manner that will enable continuous playback of the program at a normal playback rate of the program while providing flexibility to structure the buffer storage means to be smaller than is required to hold the entire program if desired.

2. A method as claimed in claim 1, further comprising the step of selecting a Maximum Response Time (MRT) corresponding to a maximum time a user need wait to commence playing a requested program from a beginning of the program.

3. A method as claimed in claim 2, wherein step (a) comprises providing the program divided into program segments of a length selected such that at least one program segment is transmitted in the time of one MRT.

4. A method as claimed in claim 3, wherein step (b) comprises transmitting one or more program segments during each MRT, including a first program segment corresponding to a first segment of playing time of the program, in accordance with the scheduling algorithm, wherein, in use, the first program segment is always available at a receiver within one MRT for immediate playback.

5. A method as claimed in claim 4, further comprising at the head end of the distribution system the step of numbering the program segments 1 to n, where n equals the number of segments into which the program is divided, and wherein the segments are numbered in the order in which they should appear in the program for normal playback.

6. A method as claimed in claim 5, wherein implementing the scheduling algorithm involves iteratively calculating during each MRT the result of:

space="preserve" listing-type="equation">COUNT Modulo X=Y,

wherein COUNT=a predetermined initial whole number incremented by 1 after each MRT;

X=1 to n, where n=the number of segments into which the program has been divided; and

organizing the program segments into said predetermined sequence based on said calculation wherein, in use, whenever Y=O, the program segment number X will be transmitted.

7. A method as claimed in claim 1, further comprising the steps of recording a user identification number, a program title identification number and a time of each request in a subscriber request map;

and tracking each request and its progress towards completion.

21. A method as claimed in claim 1, wherein step (b) comprises transmitting program segments occurring early in the program more frequently than program segments occurring later in the program.

22. A method as claimed in claim 1, wherein step (b) comprises transmitting the plurality of program segments in accordance with a modified scheduling algorithm adapted to smooth a transmission load and to reduce transmission bandwidth requirements.

23. A method as claimed in claim 22, wherein the plurality of program segments comprises a first program segment, and wherein step (b) further comprises transmitting one or more initial program segments at predetermined time intervals for storing indefinitely in the buffer storage means in the receiver and transmitting the plurality of program segments except said one or more initial program segments in accordance with the modified scheduling algorithm, wherein in use, the first program segment is always available at the receiver for immediate viewing.

24. A method as claimed in claim 1, further comprising, prior to step (b), a step of compressing the program, wherein the plurality of program segments are provided in a compressed format.

8. A system for optimizing transmission of a program to multiple receivers, wherein when one or more receivers request a particular program at a same time or different times, the system responds to each request irrespective of whether or not a receiver other than said one or more receivers is already receiving the same particular program, while minimizing transmission resources required to service the requests, the system comprising:

at a head end of the system;

means for providing the program divided into a plurality of program segments for implementing a scheduling algorithm by which the program segments are organized into a predetermined sequence; and

,

means for transmitting the program segments according to the scheduling algorithm such that during a time required for normal playback of the program at the multiple receivers, at least some of the program segments are transmitted more than once simultaneously from the head end to the multiple receivers with no requirement at any time to dedicate the head end of the system to any specific receiver;

and at a receiver of the system,

buffer storage means for storing the transmitted program segments for subsequent playback on the receiver, wherein if a same program segment is received by the receiver more than once, said same program is stored only once in the buffer storage means, and wherein said scheduling algorithm ensures that any receiver will receive all of the program segments in a manner that will enable continuous playback of the program at a normal playback rate of the program while providing flexibility to structure the buffer storage means to be smaller than is required to hold the entire program if desired.

9. A system as claimed in claim 8, further comprising at the head end of the system:

means for numbering the program segments 1 to n, where n equals the number of program segments into which the program is divided, and wherein the program segments are numbered in the order in which they should appear in the program for normal playback, said means for numbering being operatively connected to said means for providing the program and said means for transmitting the program segments to provide for transmission of the program segments in accordance with the scheduling algorithm.

10. A system as claimed in claim 9, further comprising at the head end of the system:

means for appending a segment identifier to each program segment prior to transmitting, wherein said segment identifier at least identifies a program segment by its number, said means for appending a segment identifier being operatively connected to said means for numbering to determine a number assigned to each program segment for inclusion in said segment identifier.

11. A system as claimed in claim 8, wherein said means for transmitting transmits one or more of said program segments during each Maximum Response Time (MRT) time interval, wherein MRT corresponds to a maximum time a user need wait to commence playing a requested program.

12. A system as claimed in claim 11, further comprising scheduling means for scheduling said plurality of program segments, said scheduling means comprising:

means for iteratively calculating during each MRT the result of the scheduling algorithm;

space="preserve" listing-type="equation">COUNT Modulo X=Y,

wherein COUNT=a predetermined initial whole number incremented by 1 after each MRT;

X=1 to n, where n=the number of segments into which the program has been divided; and

means for organizing the program segments into said predetermined sequence based on said calculation wherein, in use, whenever Y=0, the program segment number X will be transmitted,

and wherein said means for organizing is operatively connected to said means for transmitting the program segments to provide for transmission of the program segments in accordance with said result of said scheduling algorithm.

13. A receiver for receiving a program supplied to multiple receivers by a program transmission optimization system, wherein more than one of the multiple receivers request a particular program at a same time or different times, the system responds to each request irrespective of whether or not a receiver other than said more than one of the multiple receivers is already receiving the same particular program while minimizing transmission resources required to service the requests, the receiver comprising:

buffer storage means for storing a plurality of program segments of the program transmitted from a head end of the program transmission optimization system according to a scheduling algorithm such that during a time required for normal playback of the program at the multiple receivers, at least some of the program segments are transmitted more than once simultaneously from the head end to the multiple receivers with no requirement at any time to dedicate the head end of the system to any specific receiver, and wherein if a same program segment is received by the receiver more than once, said same program segment is stored only once in the buffer storage means; and

processing means for processing said program segments stored in the buffer storage means and for supplying the segments in a correct sequence for playback, wherein said scheduling algorithm ensures that the receiver will receive all of the program segments in a manner that will enable continuous playback of the program at a normal playback rate of the program while providing flexibility to structure the buffer storage means to be smaller than is required to hold the entire program if desired.

14. A receiver as claimed in claim 13, wherein said processing means comprises means for distinguishing received program segments by a segment identifier, wherein said segment identifier at least identifies a segment by its number and wherein, in use, the receiver uses the segment identifier to distinguish redundant segments from segments required for subsequent playback.

15. A receiver as claimed in claim 13, wherein said processing means further comprises decompressing means for decompressing compressed program segments transmitted from the head end of the program transmission optimization system.

16. A scheduling apparatus for a program transmission optimization system for optimizing transmission of a program from a head end to multiple receivers, wherein if one or more of the multiple receivers request a particular program at a same time or different times, the system responds to each request irrespective of whether or not a receiver other than said one or more of the multiple receivers is already receiving the same particular program, while minimizing transmission resources required to service the requests, the scheduling apparatus comprising:

means for providing the program divided into a plurality of program segments for implementing a scheduling algorithm by which the program segments are organized into a predetermined sequence; and

means for scheduling said plurality of program segments according to the scheduling algorithm such that during a time required for normal playback of the program at the multiple receivers at least some of the program segments are transmitted more than once simultaneously from the head end to the multiple receivers with no requirement at any time to dedicate the head end of the system to any specific receiver;

and wherein said scheduled program segments are transmitted to one or more receivers of users requesting the program such that if a same program segment is received by a receiver more than once, said same program segment is stored only once in a buffer storage means provided in the receiver, and wherein said scheduling algorithm ensures that a user'"'"'s receiver will receive all of the program segments in a manner that will enable continuous playback of the program at a normal playback rate of the program while providing the flexibility to structure the buffer storage means to be smaller than is required to hold the entire program if desired.

17. A scheduling apparatus as claimed in claim 16, wherein said means for providing the program provides the program divided into segments of a length selected such that at least one segment is transmitted in a Maximum Response Time (MRT) time interval, wherein the MRT corresponds to a maximum time a user need wait to commence playing a requested program from a beginning of the program.

18. A scheduling apparatus claimed in claim 17, further comprising means for numbering the program segments 1 to n, where n equals the number of segments into which the program is divided, and wherein the segments are numbered in the order in which they should appear in the program for normal playback.

19. A scheduling apparatus as claimed in claim 18, wherein said scheduling means comprises means for iteratively calculating during each MRT the result of the scheduling algorithm;

space="preserve" listing-type="equation">COUNT Modulo X=Y,

wherein COUNT=a predetermined initial whole number incremented by 1 after each MRT;

X=1 to n, wherein n=the number of segments into which the program has been divided; and

means for organizing the program segments into said predetermined sequence based on said calculation wherein, in use, whenever Y=0, the program segment number X will be transmitted.

20. An apparatus as claimed in claim 16, wherein said means for providing the program retrieves the program segments from a compressed program storage means wherein the program is stored in compressed segmented format corresponding to said plurality of segments.