Program transmission optimisation - Patent Review 5421031

I claim:

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:

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.

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:

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;

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.

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.

Description Submit all comments and votes

FIELD OF THE INVENTION

The present invention relates to a system and method for program transmission optimisation over a distribution system and relates particularly, though not exclusively, to such a method and system for supplying video-on-demand over a cable television network.

DISCUSSION OF THE PRIOR ART

Throughout the following specification the word "program" should be understood in the broadest sense of the term and includes any information, whether visual or audible, a mixture of both or otherwise, which is normally perceived in a substantially continuous sequence of impressions through one or more of the human senses. The term "video program" refers to a program of visual information or visual and audible information, whether recorded in reproducible format or transmitted "live". In our "information society", with its increasing emphasis on greater accessibility to information, there are many situations where the same program may be required to be accessed by more than one person at the same time.

Thus, for example, in a library of a large educational institution which stores lectures and other information on audio and/or video cassettes, the demand for certain programs may be particularly high at certain times and there is a need to be able to allow several students to listen to or view the program simultaneously from the beginning, without having to force individuals to start listening to or viewing the program at the same time. Ideally, it should be possible to service the needs of all persons requiring that program immediately when it is requested. In practice this is extremely difficult without expensive duplication of equipment and complex electronic processing. Another example of this type of multiple user situation is so called video-on-demand television. A video-on-demand system ideally allows any subscriber to request (demand) any particular video program at any time of the day.

A prior art video-on-demand system is described in U.S. Pat. No. 4,506,387 to Walter in which each video program is pre-programmed in a memory device selectable by a hose computer at a central data station in response to an address signal transmitted from the user. The host computer controls the transmission of the video program at a high non-real-time rate over a fibre optic line network to a data receiving station at the users location. The data receiving station then converts the received optical data to electrical data and stores it for subsequent real-time transmission to the users television set.

There are a number of significant disadvantages with the system of Walter, the foremost being that it is incompatible with existing television transmission networks and in particular CATV coaxial cable networks. In order to achieve a rapid response time Walter transmits all of the digital data corresponding to an entire program to the receiving station over a plurality of fibre optic lines within a very short time. Even with compression of the digital data the bandwidth requirement for this system is relatively large. For example, sixteen (16) optical data channels over four fibre optic lines are required to transmit a two hour movie in about thirty one seconds. Very few homes or buildings currently have ready access to a fibre optic cable, and a fibre optic network is expensive to install.

A further disadvantage with the system of Walter is that it cannot adequately handle a high demand for the same video program. Research in video tape lending libraries indicates that out of a total of say five thousand tapes held in the library, at any one time only a core group of twenty to forty most popular titles are in high demand. Furthermore, this research into the viewing habits of viewers indicates that the core video demand requirement varies throughout the day as the nature of the-viewers changes. Whilst Walter contemplates that the central data station may transmit only a portion of the selected program to the user for his viewing, and then begin transmitting a portion of another selected program to a second user, the system cannot simultaneously handle several users requesting the same program. In that event, a user must wait until transmission of the entire program to each user who placed a request prior to his own has been completed, before the system can attend to his demand. Clearly with core video programs this could result in unacceptable delays.

SUMMARY OF THE INVENTION

The present invention was developed with a view to providing a method and system for program transmission optimisation over a distribution system for multiple users, and was developed specifically, though not exclusively, with a view to providing a system and method for supplying video-on-demand which is compatible with existing video distribution systems such as CATV. Throughout this specification the term "distribution system" is to be construed in the broadest sense of the term and covers ordinary radio and television networks, CATV and internal television/video/audio distribution systems of the kind employed in hotels, educational institutions and more recently in aircraft and ocean liners.

According to one aspect of the present invention there is provided a method for optimising transmission of a program Go multiple users over a distribution system, the method comprising:

at a head end of the distribution system,

dividing the program into a plurality of program segments; and,

transmitting the program segments in a redundant sequence in accordance with a scheduling algorithm;

and at a receiver of the distribution system,

storing the transmitted program segments in a buffer storage means in the receiver for subsequent playback whereby, in use, said 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.

Preferably the method further comprises selecting a Maximum Response Time (MRT) corresponding to a maximum time a user need wait to commence playing a requested program.

Typically the seep of dividing the program involves dividing the program into segments of a length selected such that at lease one segment can be transmitted in the time of one MRT.

In the preferred embodiment said step of transmitting the segments involves transmitting one or more segments during each MRT, including a first segment corresponding to a first segment of playing time of the program, in accordance with the scheduling algorithm whereby, in use, the first segment is always available at a receiver within one MRT for immediate playback.

According to another aspect of the present invention there is provided a system for optimising transmission of a program to multiple users, the system comprising:

at a head end of the system:

means for dividing the program into a plurality of program segments; and,

means for transmitting the program segments in a redundant sequence in accordance with a scheduling algorithm;

and at a receiver of the system,

buffer storage means for storing the transmitted program segments for subsequent playback on the receiver whereby, in use, said scheduling algorithm can ensure that the receiver will receive all of the program segments in a manner that will enable continuous playback in real time of the program at the receiver.

Preferably the system further comprises at the head end of the system:

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.

According to a further aspect of the present invention there is provided a receiver for receiving a program supplied by a program transmission optimisation system, the receiver comprising:

buffer storage means for storing a plurality program segments of the program transmitted from a head end of the system according no a scheduling algorithm; and,

processing means for processing said program segments stored in the buffer storage means and supplying the segments in the correct sequence for playback whereby, in use said scheduling algorithm can ensure that the receiver will receive all of the program segments in a manner that will enable continuous playback in real time of the program at the receiver.

Typically 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 whereby, in use, the receiver can distinguish redundant segments from segments required for subsequent playback.

According to a still further aspect of the present invention there is provided a scheduling apparatus for a program transmission optimisation system, the apparatus comprising:

means for dividing the program into a plurality of program segments;

means for scheduling said plurality of program segments in a redundant sequence in accordance with a scheduling algorithm: and,

means for routing said scheduled program segments for transmission to one or more receivers of users requesting the program whereby, in use, said 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.

Preferably said means for dividing divides the program into segments of a length selected such that at least one segment can be transmitted in a Maximum Response Time (MRT) time interval, wherein MRT corresponds to a maximum time a user need wait to commence playing a requested program from its beginning.

The scheduling algorithm preferably employed in the invention involves iteratively calculating during each MRT the result of COUNT Modulo X=Y, wherein COUNT=a predetermined initial whole number incremented by 1 each MRT, X=1 to n, where n=the number of segments into which the program has been divided, whereby, in use, wherever Y=0 the program segment number X will be transmitted.

BRIEF DESCRIPTION OF DRAWINGS

In order to facilitate a better understanding of the nature of the invention a detailed description of one preferred embodiment of a program transmission optimisation system and method in the form of a video-on-demand system and method will now be given, by way of example only, with reference to the accompanying drawings, in which:

FIG. 1 is a schematic diagram of a preferred embodiment of a video-on-demand system;

FIG. 2 is a more detailed block diagram illustrating the functional blocks of the video-on-demand system in FIG. 1 applied to a CATV network;

FIG. 3 is a flow chart of the method steps employed at a head end of the video-on-demand system;

FIG. 4 is a flow chart of the method steps employed at a receiver of the video-on-demand system;

FIG. 5 is a tabular representation of the transmission sequence of video segments in accordance with a preferred scheduling algorithm; and,

FIG. 6 is a graphical representation of the relationship between Maximum Response Time and the required video-hours/hour of transmission time.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

FIG. 1 illustrates schematically a preferred embodiment of the video-on-demand system according to the present invention. Referring to FIG. 1, external noncompressed material can enter the system in its most basic format such as 35 mm film, video tape, or through a telecommunications link such as broadcast television or satellite transmission. The non-compressed material is passed through a media compression system 10 for compressing the audio visual program material into a compressed format. The audio visual program material may be compressed by an external video compression service provider such as Intel Corporation. Such external compressed material may enter the system directly via a storage distribution node 12. The storage distribution node 12 routes the compressed video material to the appropriate storage medium.

There are three types of storage in the system, long term slow storage 14, long term fast storage 16 and short term fast storage 18. The division of the storage of compressed video material into the different types of storage is based on commercial considerations, in view of the relatively high cost of fast storage media compared to slow storage media. The selection of the type of storage to which different programs would be routed is based upon the expected future demand for the video material concerned. Daily news segments would probably be stored in short term fast storage 16, whereas a movie classic such as "Gone With The Wind" would probably be stored in long term fast storage 16. Infrequently requested materials such as some obscure silent movie would probably be stored in long term slow storage 14. The storage distribution node 12 is typically a micro or mini computer which controls the flow of data between the different storage devices.

The long term slow storage 14 typically takes the form of storage media such as magnetic tapes, or optical discs and may require human intervention for retrieval of infrequently accessed program material. The long term fast storage 16 may typically take the form of a jukebox type of optical disc storage device. Optical disc storage provides high density storage with random access, and the jukebox access mechanism provides automatic program access. A typical unit currently available is the KODAK Optical Disc System 6800 drive/cabinet. The short term fast storage 18 may take the form of a magnetic disc drive such as an IBM Model 3380. This allows rapid random access to the compressed video material stored in digital format, but is a relatively expensive storage medium and would therefore only be used for storing popular core video programs.

The scheduling and routing computer 20 receives requests for specific audio visual material from user's receivers 22A, 22B or 22C via a bi-directional request and distribution network. The scheduling and routing computer 20 controls the retrieval and division of the selected video program in a plurality of video segments, schedules the video segments in accordance with a scheduling algorithm and controls the routing of the scheduled segments for transmission to one or more of the receivers 22A, 22B or 22C, so that each requesting viewer's receiver will receive all of the video segments in a manner that will enable continuous immediate viewing of the program. The video-on-demand system employs a combination of frequency multiplexing and time division multiplexing. The time division multiplexing of the video segments is controlled by the scheduling and routing computer 20 in accordance with the scheduling algorithm. The frequency multiplexing is performed by a subscriber distribution node 24 under the control of the scheduling and routing computer 20. The processing capabilities of the scheduling and routing computer 20 are similar to that required by computers used by banks for automatic teller machines. The scheduling and routing computer 20 may be any suitable computer with a typical processing capability of 1.5 to 200 million instructions per second (MIPS), depending on the size of the subscriber base and other loading factors.

The viewer's receivers 22 are typically frequency agile to be compatible with the frequency multiplexing employed at the head end of the system. The receivers are provided with processing means to capture the appropriate data packets created by the time division multiplexing of the video segments. The receivers 22 are also provided with buffer storage means for storing the received video segments, and would typically also comprise decompression means for decompressing the video data for subsequent display on a dedicated television screen, or fed into a conventional television set.

The video-on-demand system of FIG. 1 can operate on either analog or digital communication circuits, however in the preferred embodiment described below the video distribution system is a conventional cable television system which is analog. In the preferred embodiment of the system described below primarily modulated digital data is transmitted over the CATV network. However, it is envisaged that a future system will employ a mixture of analog and modulated digital signals.

The method of program transmission optimisation according to the invention can provide transmission optimisation for either digital or analog information signals.

Conventional CATV systems are typically simplex communication systems (one way only) so that there is no easy way to retransmit data when errors are detected. Accordingly, some form of error compensation is required. Fortunately, television data is generally used in a very transient manner, unlike computer data that must be assured of accurate transmission. If a few frames of a TV image are disturbed most viewers accept this without even a conscious acknowledgment of their occurrence. Accordingly, a much higher bit error rate can be tolerated, for example 1 erroneous data bit per 100,000. At this rate the human eye/brain system normally cannot even detect the video effects caused by this erroneous bit. Most digital modems work with bit error rates of 1 in 100,000,000 to 1 in 1,000,000,000! Therefore, the video-on-demand system can tolerate error rates typically from 1,000 to 10,000 times higher than most computer data systems are presently designed for. A higher error rate will of course improve performance, although the improvement may be imperceptible to a viewer.

FIG. 2 illustrates in block diagram form a preferred embodiment of the video-on-demand system applied to a CATV network. The video demand system comprises at the head end means for providing a video program in a compressed format in the form of Write Once Read Many (WORM) storage devices and magnetic disc storage devices 28 providing long term fast storage 16 and short term fast storage 18 respectively. In this particular embodiment the compressed video material is stored in digital format in the storage devices and the video programs may already be segmented in the storage media in video packets sized to be compatible with the system specifications. The magnetic disc devices 28 and WORM devices 26 are connected to a scheduling and routing computer 30 by data bus 32.

The scheduling and routing computer 30 responds to a subscriber request for a particular program by retrieving the video program from the appropriate storage media and dividing the video program into a plurality of video segments. As mentioned above, the video program may be stored in the storage media already in segments corresponding to the scheduling requirements of the system thereby reducing the load on the computer 30 during the process of retrieving and dividing the video program into video segments. The computer 30 then schedules the plurality of video segments of the video program in accordance with a scheduling algorithm, as will be described in more detail below, and routes the scheduled video segments for transmission to one or more receivers of viewers requesting the video program. For core video programs (those that are in continuous demand by at least one subscriber for periods of more than one Video Playing Time (VPT)), the scheduling algorithm can be run once and the packets stored in the scheduled sequence on a serial recording device such as a tape drive (not shown), to further reduce loading on the computer.

In this embodiment the subscriber distribution node 24 comprises a plurality of modems 34 under the control of the scheduling and routing computer 30. Each modem 34 modulates a different carrier frequency signal, corresponding to each of the channels on the CATV network 36, for transmitting the video segment data packets routed to the appropriate modem 34 by the scheduling and routing computer 30 over data bus 32.

Each subscriber on the CATV network 36 is provided with a receiver 40 for receiving the video segment data packets corresponding to the requested program and storing the video segments for future viewing by the subscriber. Each receiver 40 typically comprises a buffer memory 42 for storing the video segments of the video program transmitted from the head end, and video processing means for processing the video segments stored in the buffer memory and supplying the segments in the correct sequence to a subscriber television set 44 for viewing. Typically the video processing means may include a controller 52 and a capture memory 46 for capturing the video segment data packets received over the CATV network 36 and demodulated by one or more modems 48 of the receiver. Under the control of controller 52 the video processing means distinguishes received program segments by a segment identifier, for example the PKT ID, so that redundant segments can be ignored and overwritten in capture memory 46. Modem 48 is preferably a frequency agile broad band modem such as the Fairchild M505, although as noted above a more low level digital modem with lower bit error rate can also be employed. Compressed video data packets captured in capture memory 46 are stored in buffer memory 42 from which the segments can be retreived and decompressed in data decompressor 50 for immediate or subsequent viewing. The microprocessor based controller 52 controls the flow of data and the video processing within the receiver 40.

Some CATV systems can accommodate bidirectional decoders or receivers, and for this type of system the receiver 40 is provided with a key pad 54 to enable the subscriber to initiate a request via the CATV network 36. However, the majority of CATV systems are unidirectional (simplex) and a subscriber request must therefore be made over the public switched telephone network (PSTN) 56. The subscriber request via the PSTN 56 may be verbal or via touch tone keying similar to that provided by other on-line subscriber network service providers.

Security on the system to prevent unauthorised viewing of transmitted programs may be implemented in several ways. Standard encryption algorithms could be applied at the modems 34 prior to transmission. Each receiver 40 would then require a key to decrypt the received data. Encryption/decryption keys are distributed to subscribers in a similar manner to that employed by financial institutions to distribute PINs for automatic teller machine usage. Alternatively, each data packet transmitted at the head end can be prefixed with a receiver ID unique to each subscriber so that a pirate receiver would need to select the appropriate receiver ID in order to receive a particular video program.

It will be appreciated that the video-on-demand system illustrated in FIG. 2 is exemplary only, and than many other hardware implementations could be employed to effect the method and system for supplying video-on-demand according to the invention. For example, the receivers 40 may comprise several modems for simultaneously receiving data packets over several channels, and the capture memory may be dispensed with if the video segments are stored in the buffer memory in compressed format. The video segments are then decompressed when they are provided to the subscriber's television set in the correct sequence for viewing. Furthermore, certain sections of the head end apparatus or of the receiver may be located at different geographical locations. For example, in view of the typical architecture of CATV systems, it is possible that the modem and buffer sections of the receiver will become part of the cable network in what is referred to as a subscriber tap, and that the other sections would be located at the subscriber's premises.

It should be noted that the video segment data packets for a particular program need not be transmitted over the same channel for all viewing subscribers. By employing a combination of time division multiplexing and multiple channels at the head end of the system, data rates over each of the channels can be kept at a minimum therefore allowing the use of less expensive hardware at the receivers. Each receiver 40 may be configured to scan the channels in a cyclic fashion in order to determine which channel or channels the appropriate video segments are being transmitted. In addition to this a dedicated control channel can be provided over which data from the scheduling and routing computer 30 is transmitted to instruct each receiver as to which packets to receive and on which channel(s). However, preferably the head end transmits the video segments in accordance with the scheduling algorithm in a continuous manner, with each video segment provided with a title ID as well as a segment ID, so that each receiver will receive all of the video segments with the appropriate title ID and can discard or overwrite the video segments already received.

A key feature of the present invention is the scheduling of the video segments for transmission in a redundant sequence in a manner that will ensure that each receiver will receive all of the video segments for the requested program according to a schedule that will enable continuous playback in real time of the video program at the receiver. A preferred form of an efficient scheduling algorithm and its implementation will now be described in detail.

In the following description the term "Maximum Response Time" (MRT) refers to the maximum time a subscriber will need to wait before the video program requested will be available for viewing at his receiver. MRT refers to the maximum time that the system has to respond to the demand. Video Play Time (VPT) refers to the time required to play the particular video program when viewed at normal play back speed. The data that comprises the video program must be divided into video segment data packets of such a length that one packet can be transmitted in the time of 1 MRT. The video segment play back time or slot length of one data packet need not be less than 1 MRT and may be longer than 1 MRT depending on how much band width is available over the transmission medium for transmitting the data packet(s) in the time of 1 MRT. The slot length may be variable in order to adjust the instantaneous loading and data rates on the transmission medium or to adjust the amount of buffer storage space required in the receivers. However, in any one installation, the slot length and MRT would normally be fixed for a specific system configuration. In the following description the slot length has been made equal to the MRT in order to simplify explanation. Thus, for example, if the video program i