Method and apparatus for efficient transmissions of programs

We claim:

1. A method of transmitting a program to multiple users over a distribution system, the method comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers such that, at least some of the segments are transmitted more than once, at different times, from the head end so as to enable multiple receivers of users requesting playback of the program at different times to simultaneously receive the segments required for continuous playback of the program.

2. The method of claim 1 wherein some of the segments are transmitted in a sequence which is different from a sequence in which such segments are subsequently played back.

3. The method of claim 2 further comprising storing each segment at users' receivers only once even if the same segment has been received more than once during the transmission of the program.

4. The method of claim 1 wherein at any given time the head end of the distribution system is not dedicated to transmitting the program to a predetermined number of receivers.

5. The method of claim 1 further comprising selecting a maximum response time corresponding to a maximum time interval a user need wait to commence playing back the program.

6. The method of claim 5 wherein each of the segments represents a portion of the program which playing time is equal to one maximum response time.

7. The method of claim 6 wherein the transmission of each set of the segments is separated in time by a time interval essentially equal to the maximum response time.

8. The method of claim 7 wherein the first segment of the program is transmitted during every maximum response time interval.

9. The method of claim 8 wherein a bandwidth limit is imposed so that at most a predetermined maximum number of segments is transmitted during any given maximum response time interval and further comprising delaying the transmission of a number of the segments exceeding the maximum number until an interval in which the number of segments scheduled for transmission is less than the predetermined maximum number.

10. The method of claim 8 further comprising imposing a bandwidth limit and transmitting a segment in an interval prior to the interval when it is scheduled for transmission if the number of segments scheduled for that interval exceeds the limit.

11. The method of claim 1 further comprising storing predetermined segments of predetermined programs at receivers of at least some of the users even if such predetermined programs are not presently being requested by the users in whose receivers the segments are stored.

12. A system for transmitting a program to multiple users comprising:

means for providing a program divided into a plurality of segments at a head end; and

means for transmitting the segments from the head end to users' receivers such that at least some of the segments are transmitted more than once, at different times, so as to enable multiple receivers of users requesting the program at different times to simultaneously receive the segments required for continuous playback of the program.

13. A method of transmitting a program to multiple users over a distribution system, comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers, such that at least some of the segments are simultaneously sent to more than one receiver with no requirement at any time to dedicate the head end of the distribution system to any specific receivers.

14. The method of claim 13 wherein the segments represent portions of the program having equal playback time.

15. A system for transmitting a program to users comprising:

means for dividing a program into segments;

means for dividing at least some of the segments into a plurality of fragments;

means for transmitting at successive intervals at least one fragment of the plurality of fragments of each segment that has been divided into the plurality of fragments; and

means for receiving and storing the fragments of the segments, which have been divided into the plurality of segments, necessary for continuous playback of the program.

16. The system of claim 15 wherein each segment is consecutively numbered and the means for receiving accepts fragments relating to the segments that have numbers higher than the segment currently being played back.

17. The system of claim 15 wherein the fragments of each segment are consecutively numbered and the fragments are played back in numerical order.

18. The system of claim 17 wherein the played back fragments are deleted from the means for receiving and storing.

19. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments;

during each predetermined time interval transmitting one fragment of each segment to users' receivers; and

during each predetermined interval accepting at the receivers the fragments of the segments which have not yet been played back and deleting from the receivers the fragments of the segments which have been played back.

20. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments; and

during each predetermined time interval transmitting one fragment of each segment to users' receivers;

wherein each of the segments is divided into a number of fragments corresponding to a sequential position of such a segment in the program.

21. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments;

during each predetermined time interval transmitting one fragment of each segment to users' receivers; and

receiving and permanently storing fragments of initial segments of the program.

22. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments; and

during each predetermined time interval transmitting one fragment of each segment to users' receives;

wherein segments of the plurality of segments at an ending potion of the program are divided into fewer fragments than a sequential number of the segments in the ending portion of the program.

23. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments; and

during each predetermined time interval transmitting one fragment of each segment to users' receivers;

wherein segments of the plurality of segments belonging to a beginning portion of the program are transmitted more frequently than segments of the plurality of segments belonging to an ending portion of the program.

24. A receiver for receiving a program supplied to multiple users over a distribution system from a head end, said program being divided into a plurality of program segments, the receiver comprising:

a buffer storage means for storing a plurality of program segments transmitted from the head end of the distribution system; and

a processing means including means for determining whether segments already held in said buffer storage means will be presented on the distribution system prior to playback and removing the segments that will be presented a again prior to playback from the buffer storage means whereby, in use, the program segments required for continuous playback of the program will always be available at the receiver.

25. A method of transmitting a program to multiple users over a distribution system, the method comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers such that, at least some of the segments are transmitted more than once at different times from the head end so as to enable multiple receivers of users requesting playback of the program at different times to simultaneously receive the segments required for continuous playback of the program;

wherein at least some of the segments represent a portion of the program having playing time essentially equal to one maximum response time, which is a maximum time interval a user needs to wait to commence playing back the program, and wherein transmission of each set of segments of the plurality of segments is separated in time by a time interval essentially equal to the maximum response time.

26. A method of transmitting a program to multiple users over a distribution system, the method comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers such that, at least some of the segments are transmitted more than once at different times from the head end so as to enable multiple receivers of users requesting playback of the program at different times to simultaneously receive the segments required for continuous playback of the program;

wherein at most a maximum number of segments, of the plurality of segments, is transmitted during a predetermined time interval, the transmission of other segments of the plurality of segments, exceeding the maximum number, is delayed until an interval in which the number of segments scheduled for transmission is less than the predetermined maximum number.

27. A method of transmitting a program to multiple users over a distribution system, the method comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers such that, at least some of the segments are transmitted more than once at different times from the head end so as to enable multiple receivers of users requesting playback of the program at different times to simultaneously receive the segments required for continuous playback of the program; and

transmitting a given segment of the plurality of segments in a time interval occurring prior to a time interval when the given segment is scheduled for transmission, if a number of segments, scheduled for the interval when the given segment is scheduled for transmission exceeds a predetermined limit.

28. A method of transmitting a program to multiple users over a distribution system, comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers, such that at least some of the segments are simultaneously sent to more than one receiver with no requirement at any time to dedicate the head end of the distribution system to any specific receivers;

wherein each of the segments is divided into fragments such that the segments representing an ending portions of the program are divided into a greater number of fragments than the segments representing a beginning portions of the program.

29. The method of claim 28 wherein each of the segments is divided into a number of fragments that corresponds to a sequential position of such a segment in the program, so that the first segment is divided into one fragment, the second segment is divided into two fragments, the third segment is divided into three fragments and so forth.

30. The method of claim 29 wherein during each predetermined time interval at least one fragment of each segment is transmitted.

31. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments; and

during each predetermined time interval transmitting at least one fragment of each segment to users' receivers;

wherein initial segments of the program are divided into a greater number of fragments than that corresponding to the sequential position of such segments in the program and subsequent segments are divided into a number of fragments corresponding to the position of segments in the program.

32. The method of claim 31 further comprising during each predetermined interval accepting at the receivers the fragments of the segments which have not yet been played back and deleting from the receivers the fragments of the segments which have been played back.

33. A method of transmitting a program to multiple users over a distribution system comprising:

providing a program divided into a plurality of segments wherein at least some of the segments are divided into a plurality of fragments;

during each predetermined time interval transmitting at least one fragment of each segment to users' receivers; and

wherein the fragments of the segments that represent an ending portion of the program are not accepted at the receivers when initial segments of the program are being played to a user in order to decrease the storage requirement of the receivers.

34. The method of claim 33 wherein the initial segments of the program are divided into a greater number of fragments than that corresponding to the sequential position of such segments in the program and subsequent segments are divided into a number of fragments corresponding to the position of segments in the program.

35. The method of claim 33 wherein the segments belonging to a beginning portion of the program are transmitted more frequently than the segments belonging to the ending portion of the program.

36. The method of claim 33 wherein the predetermined interval is essentially equal to a playback interval of a segment.

37. A receiver for receiving a program supplied to multiple users over a distribution system from a head end, said program being divided into a plurality of program segments, the receiver comprising:

a buffer storage means for storing a plurality of program segments transmitted from the head end of the distribution system; and

means for determining whether segments presented on the distribution system will be presented again prior to playback and rejecting the segments that will be presented again, but accepting the segments that will not be presented again for storing in the buffer storage means.

Description Submit all comments and votes

FIELD OF THE INVENTION

The present invention relates to a system and method for program transmission optimization over a distribution system and relates particularly, though not exclusively, to a method and system for video transmission optimization.

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, tactile, olfactory, audible, or other information, a mixture of these 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 host 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. 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. A fixed multiplexing scheme, such as that of Walter, services each user's request in turn with a high speed transmission burst which may be a portion or all of a program. It is forced to repeat that burst to start a second user at the beginning of the same program since there is an unvarying FIFO (first in first out) sequence to the program data and no redundancy. If a second user of the same program is physically on the same bus and is to be served before the burst is over the first user must be temporarily denied transmission. 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 optimization 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, including satellite and microwave 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 of transmitting a program to multiple users over a distribution system, the method comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers such that, at least some of the segments are transmitted more than once from the head end so as to enable multiple receivers of users requesting playback of the program at different times to simultaneously receive the segments required for continuous playback of the program.

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

means for providing a program divided into a plurality of segments at a head end; and

means for transmitting the segments from the head end to users' receivers such that at least some of the segments are transmitted more than once so as to enable multiple receivers of users requesting the program at different times to simultaneously receive the segments required for continuous playback of the program.

According to a further aspect of the present invention there is provided a method of transmitting a program to multiple users over a distribution system, comprising:

at a head end of the distribution system, providing a program divided into a plurality of segments; and

transmitting the segments from the head end to users' receivers, such that any one segment can simultaneously be sent to more than one receiver with no requirement at any time to dedicate the head end of the distribution system to any specific receivers.

According to a still further aspect of the present invention there is provided a receiver for receiving a program supplied to multiple users over a distribution system from a head end, said program being divided into a plurality of program segments, the receiver comprising:

a buffer storage means for storing a plurality of program segments transmitted from the head end of the distribution system; and

a processing means including means for calculating whether segments already held in said buffer storage means will be presented on the distribution system prior to playback and if so removing such segments from the buffer storage means whereby, in use, the program segments required for continuous playback of the program will always be available at the receiver.

BRIEF DESCRIPTION OF DRAWINGS

In order to facilitate a better understanding of the nature of the invention a detailed description of preferred embodiments of a program transmission optimization system and method providing video transmission optimization 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 first embodiment of a program transmission optimization system in the form 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 scheduling algorithm;

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

FIGS. 7A and 7B are block diagrams of another embodiment of a program transmission optimization system according to the invention;

FIG. 8 is a table illustrating a different technique for dividing a program into segments;

FIG. 9 is a table illustrating a sequence of transmission of the program segments in FIG. 8 according to an alternative scheduling algorithm;

FIG. 10 is a table illustrating the manner in which segments transmitted according to the scheduling algorithm of FIG. 9 are received and processed by a receiver;

FIGS. 11, 12 and 13 are tables similar to that of FIGS. 8, 9 and 10 respectively, illustrating one technique for bandwidth minimization;

FIGS. 14, 15 and 16 are tables similar to that of FIGS. 8, 9 and 10 respectively illustrating one technique for buffer minimization;

FIGS. 17, 18 and 19 are tables similar to the table of FIG. 9 illustrating alternative techniques for smoothing bandwidth requirements; and,

FIG. 20 is a flow chart of the process employed by a receiver for deciding whether or not to accept data for storage in buffer.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

FIG. 1 illustrates schematically an embodiment of the program transmission optimization system according to the present invention. This embodiment is in the form of a video-on-demand (VOD) system. Referring to FIG. 1, external non-compressed 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 external compressed material may enter the system directly via a storage distribution node 12. Standard compression algorithms such as that developed by MPEG may be employed. 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 d