WO2001086955A1

WO2001086955A1 - System and method for the efficient utilization of bandwidth in the broadcast dissemination of time-ordered data

Info

Publication number: WO2001086955A1
Application number: PCT/US2001/013876
Authority: WO
Inventors: J. Thomas Ngo; Steven E. Saunders
Original assignee: Interval Research Corp
Current assignee: Interval Research Corp
Priority date: 2000-05-08
Filing date: 2001-05-01
Publication date: 2001-11-15
Anticipated expiration: 2002-11-08
Also published as: AU2001257432A1

Abstract

Segments of data which are encoded for transmission within respective substreams are selectively transmitted to users in response to specific requests. The first request can be serviced by means of data that is transmitted in a conventional, sequential format. Subsequent requests are serviced by transmitting encoded data which is filtered so that those portions of the presentation which have not yet been transmitted in response to earlier requests are not duplicated. The filtering of the data to transmit selected portions of the presentation in response to individual requests can be carried out at various locations along the path between the source of the presentation and the end user, such as at the transmission source of the broadcast system, or at a node located at a point along the transmission path between the source and the users. Each presentation can be divided into a leader portion and a remainder portion. In response to requests for individual presentations, the leader portion is transmitted in an unencoded manner over a channel which is shared by all of the leader portions. The remainder of the presentation is transmitted in an encoded manner over a different logical channel, so that it can begin to be viewed as soon as the leader portion has ended.

Description

SYSTEM AND METHOD FOR THE EFFICIENT UTILIZATION

OF BANDWIDTH IN THE BROADCAST DISSEMINATION

OF TIME-ORDERED DATA

Field of the Invention

The present invention is directed to systems for broadcasting time-ordered data with ininimal commencement delays, such as "on-demand" video services, and more particularly to the efficient utilization of broadcast media bandwidth in such systems.

Background of The Invention

One technique for broadcasting time-ordered data, such as streaming media presentations, in a manner which imposes minimal delays between the time that a user requests the data and the time at which the data can begin to be utilized, is described in Application No. 09/414,514, filed October 8, 1999, and entitled "System and Method for the Broadcast Dissemination of Time-Ordered Data with Minimal Commencement Delays " , the disclosure of which is incorporated herein by reference. In general, that application discloses a technique in which a stream of time-ordered data, such as a video or other multi-media presentation, is divided into multiple fragments of equal length. The fragments are transmitted at different respective repetition rates, so that those fragments which occur near the beginning of the original data stream are transmitted more frequently than those which occur later in the data stream. When a user enters a command to utilize the data, for instance pressing a button on a remote control to view a movie, the individual fragments are stored upon receipt at the user's premises, and reassembled into a contiguous stream for viewing. The ordering of the fragments is such that the wait time required to utilize the data is limited to a predetermined maximum, and at least one copy of every fragment becomes available by the time it is needed.

The previously cited application describes this technique in the context of a one-way broadcast environment, in which all transmissions are unidirectional, e.g. from a cable system head end or a satellite feed to the end user, as is typical of conventional television broadcast systems. To accommodate user requests that are generated at any arbitrary point in time, in such systems it is necessary to continuously broadcast the data in a repetitive fashion. In preferred embodiments disclosed in the foregoing application, the data for a given presentation is encoded in a periodic manner, and repetitively transmitted. In one approach, the fragments are grouped into segments of different lengths, and each segment is repetitively transmitted in a corresponding respective substream within the bandwidth allocated to the presentation data. As a result, the total amount of the allocated bandwidth is continually dedicated to that data, i.e. other types of data cannot also be transmitted within the allocated bandwidth.

Except in those cases where requests are being generated by users at a relatively high frequency, much of the transmitted data ends up being discarded. More particularly, to satisfy any given request, it is only necessary to transmit one copy of each fragment of the data stream. Any additional copies of a fragment that are transmitted prior to a subsequent request will not be utilized. However, since it is not possible to predict or otherwise determine the time and/or frequency at which individual requests will be made, it is necessary to continuously broadcast the data so that no request will go unanswered. Conversely, if the requests can be transmitted upstream to the broadcast station, the data can be transmitted on an as-needed basis, rather than continuously. During those times when the presentation data is not being transmitted to satisfy a particular request, the allocated bandwidth can be used to transmit other types of data that may not be time-sensitive.

Accordingly, the present invention is directed to the broadcast dissemination of time- ordered data in a system which permits users to transmit their requests for data upstream to one or more points along the transmission path between the broadcast system source and the ultimate user. Upstream communications from the user might be accommodated within the broadcast system itself, such as in a two-way cable network, or they might take place by a separate communication system, such as a telephone network.

Summary of the Invention

In accordance with the invention, segments of data which are encoded for transmission within respective substreams are selectively transmitted to users in response to specific requests. In one embodiment, the first request is serviced by means of data that is transmitted in a conventional, sequential format. Subsequent requests are serviced by transmitting encoded data which is filtered so that those portions of the presentation which have not yet been transmitted in response to earlier requests are not duplicated. As a result, a portion of the allocated bandwidth is available to be used for the transmission of other data. Pursuant to another feature of the invention, the filtering of the data to transmit selected portions of the presentation in response to individual requests is carried out at various locations along the path between the source of the presentation and the end user. In one embodiment, the filtering takes place at the transmission source of the broadcast system, so that all users receive the same transmissions and the bandwidth requirements are minimized for the system as a whole. In another embodiment, the filtering takes place at a node located at a point along the transmission path between the source and the users, so that different groups of users can receive different sets of data.

In another aspect of the invention, each presentation is divided into a leader portion and a remainder portion. In response to requests for individual presentations, the leader portion is transmitted in an unencoded manner over a channel which is shared by all of the leader portions. The remainder of the presentation is transmitted in an encoded manner over a different logical channel, so that it can begin to be viewed as soon as the leader portion has ended.

These and other features and advantages of the invention will become apparent from the following detailed description of exemplary embodiments depicted in the accompanying drawings,.

Brief Description of the Drawings

Figure 1 is a block diagram of a television broadcast system in which the present invention can be implemented;

Figure 2 is an illustration of the segmentation of a presentation for transmission over multiple substreams;

Figure 3 is an illustration of the transmission of the presentation in response to a first set of requests;

Figure 4 is an illustration of the transmission of the presentation in response to a second, more closely spaced, set of requests;

Figure 5 is a graph of the bandwidth that is allocated to an individual user;

Figure 6 is a graph of the mean bandwidth savings provided by the selective transmission of presentations;

Figure 7 is a graph of the bandwidth usage for conventional video-on-demand, continuous encoded transmissions and selective encoded transmissions; Figure 8 is an illustration of conventional and encoded transmissions in response to multiple requests;

Figure 9 is an illustration of the transmission of overlapping conventional data streams together with encoded data streams;

Figure 10 is a block diagram of the basic components for broadcasting presentations in accordance with the present invention;

Figure 11 is an illustration of one configuration for a broadcast system;

Figure 12 is an illustration of a second configuration for a broadcast system; and

Figure 13 illustrates an example of the transmission of leader data in a shared channel.

Detailed Description

To facilitate an understanding of the principles which underlie the present invention, a brief overview of the basic technique described in the above-cited application will first be presented. In general, the invention is implemented within a system of the type illustrated in Figure 1, in which temporally ordered data is encoded at a source 10, and broadcast to multiple end users at respective remote sites. In the context of the present invention, the term "temporally ordered data" refers to any collection of data in which some portion of the data must be received prior to the time that another portion of the data can be utilized. One suitable example of temporally ordered data is a video presentation, wherein the frames of a movie can be received in any order, and stored for subsequent presentation. However, the viewer cannot begin to watch the movie until the first frame has been received. Other examples of temporally ordered data to which the invention is applicable include broadcast media objects such as audio, video or animation in the context of a multi-media presentation. In the following discussion, the invention will be described with particular reference to its application in the context of "on-demand" video services delivered via television networks. It will be appreciated, however, that the invention can be equally applied to other types of temporally ordered data, as well as various communication systems for the broadcast dissemination of such data.

Referring again to Figure 1, a video presentation is divided into a sequence of data fragments and encoded for transmission, in a manner described in detail hereinafter. The encoded fragments are transmitted from a presentation source 10, such as a cable head-end transmission station, to the subscribers' premises in response to requests that are transmitted upstream from the subscribers' premises. These requests might be transmitted via a two-way cable system, or a telephone network, or any other suitable communications system. As discussed in detail hereinafter, the requests may be transmitted to the presentation source 10, or to a node (not shown) which is located between the source 10 and the subscribers' premises.

At each subscriber's premises, the stream of fragments is received in a suitable set-top converter 12 or other equivalent type of equipment for receiving signals from the source. A decoder 14 within the converter reassembles the fragments into a continuous video stream, and stores them in a suitable frame buffer 16, where they are sequentially presented to the television receivers 18 of subscribers who entered requests. The ordering of the fragments in the encoded stream is such that, regardless of the arbitrary point in time at which a subscriber enters a request to view the presentation, the first fragment of the presentation is available within a period of time τ, and at least one copy of any given fragment becomes available by the time it is needed for viewing in the proper order. In a practical implementation of the invention, the value of τ might be on the order of a few seconds.

Figure 2 illustrates the manner in which the fragments are encoded for transmission. In a preferred embodiment of the invention, the original presentation is divided into fragments of equal length. For instance, if the original presentation comprises a digital video signal that is compressed according to the MPEG-2 Transport-Stream standard, each fragment can comprise 188 bytes of compressed data. The sequential data fragments are grouped into successive segments of the presentation. The first segment comprises the number of fragments that can be transmitted within the nominal wait time τ that is established for the presentation. Each succeeding segment is longer than the preceding segment by a factor of (1 +λ), where λ is less than 1/2, and preferably lies in the range 0.04-0.3. Hence, the k^Λ segment has a length substantially equal to τ(l +λ)^k, where the first segment has a value of k=0. Of course, if the presentation does not comprise an integral number of segments, the last segment may have a length shorter than τ(l +λ)^k.

Each of the segments of the original presentation is transmitted within a respective substream of the bandwidth that is allocated for the encoded transmission. For illustrative purposes, Figure 2 illustrates a presentation of length T which has been divided into 4 segments, which are respectively transmitted within 4 substreams of the allocated bandwidth. Each of the individual substreams can be transmitted in parallel with all of the other substreams. More preferably, however, the substreams are transmitted in a time-division multiplexed manner, to form a complete data stream of encoded data. The total bandwidth required to transmit all of the substreams is identified as η. This value can be expressed as a factor of the amount of bandwidth required to transmit the presentation in a conventional, i.e., unencoded, manner.

To service any given request for the presentation, it is only necessary to transmit one complete copy of each segment within its assigned substream. Figure 3 illustrates the situation in which two requests for the presentation are spaced by a period of time which is greater than the time required to transmit the longest segment of the presentation. In this case, a first copy of each segment is transmitted upon receipt of the first request, Rl . The maximum allocated bandwidth η is utilized by all of the segment substreams for the duration of the first segment, as indicated by the hatched areas 20. Once the transmission of the first segment has completed, at time τ, the bandwidth requirements decrease. The bandwidth requirements continue to decrease as the transmission of each successive segment finishes. When the second request, R2, is received, the process repeats, wherein all of the segments of the presentation are again transmitted. In view of the fact that the bandwidth requirements decrease over the duration of the transmission, the unused portions of the available bandwidth, indicated by the shaded areas 22, can be employed to transmit other types of data. For instance, information which is not time-critical, such as program-guide data updates for future presentations, can be downloaded during these periods of available bandwidth capacity and stored at the subscriber's sites.

One of the advantageous features of the encoding technique employed within the present invention is the fact that the transmission of segments need not begin with the first fragment of each segment. Rather, as long as one copy of each fragment is transmitted within the period of its associated segment, the transmitted segment can begin with any fragment in that segment. Consequently, if a request is received while segments are being transmitted in response to a previous request, the response to the new request can be initiated immediately at the point where the current transmission is taking place, rather than start at the beginning of the presentation. Hence, the second request can be accommodated within the same allocated bandwidth η. For instance, Figure 4 illustrates an example in which a second request, R2, is received while the transmission of the last few segments of a presentation is taking place in response to a prior request Rl. In response to the second request, the first few segments are transmitted in their entirety. In the case of those segments whose transmission is still taking place in response to the prior request Rl, their transmission continues in the normal fashion, as illustrated by the lightly hatched overlapping areas 24. Thereafter, those portions of the segments which had been transmitted prior to the second request R2 are then retransmitted, as indicated by the more heavily hatched areas 26, so that each subscriber receives at least one complete copy of each segment after making their respective requests.

The limiting case occurs when requests for a presentation have a very high frequency, such that they are separated in time by no more than τ. In this case, the segments are continuously repeated in their respective substreams, and none of the allocated bandwidth η is available for other data. However, when the requests occur less frequently, a portion of the allocated bandwidth becomes available for other types of data.

Hence, the selective transmission of presentation segments, in response to individual requests from users, provides a savings in bandwidth, relative to the continuous transmission of the encoded presentation. To provide a quantitative evaluation of this bandwidth savings, it is useful to consider the mean bandwidth ratio that is saved by the selective transmission of encoded segments, when presented with an infinite train of regularly spaced requests. The time between adjacent requests can be expressed as fT, where T is the length of the presentation and 0 < f < 1. The bandwidth versus time that is required by the selective transmission of the presentation, in response to such an infinite train of requests, repeats periodically. Each repeat is equal to the bandwidth versus time that is required to serve an individual subscriber with one complete copy of each segment for some fraction of the movie. The profile of this requirement is illustrated in Figure 5. As can be seen, the bandwidth requirements decrease exponentially over time. The mean saved bandwidth can then be expressed as a function of the time between requests, as illustrated in Figure 6. In this figure, the abscissa represents the time between requests, expressed as a multiple of the nominal wait time τ.

This result can be translated into bandwidth usage as a function of the number of concurrent viewers, assuming the worst-case situation in which requests are spaced evenly in time. Figure 7 illustrates the bandwidth usage for three different types of broadcast transmission. Dashed line 30 illustrates the bandwidth usage for continuous transmission of an encoded presentation, as described in Application No. 09/414,514. As can be seen, the bandwidth requirement for continuous transmission remains constant. Line 32 represents the bandwidth usage for the selective transmission of the encoded presentation, in response to individual user requests. As can be seen, the selective transmission provides a significant bandwidth savings, even when the number of simultaneous subscribers is more than 100. These two forms of encoded transmissions are contrasted with the bandwidth requirements for conventional video-on-demand transmission, represented by line 34. In this latter situation, each new request requires the allocation of a dedicated channel to service that request, so that the bandwidth utilization is proportional to the number of concurrent viewers.

Referring back to the situation illustrated in Figure 4, it can be seen that, whenever a request occurs while at least a portion of the transmission is still being carried out in response to a previous request, the later requester can take advantage of fragments that have already been allocated to previous requesters but not yet transmitted. In the example of Figure 4, the second request R2 utilizes those fragments in the overlapping areas 24 that are being transmitted in response to the earlier request, Rl. Consequently, in anticipation of future requests, the transmission of each fragment should be delayed to the latest possible moment. Practically speaking, this means that the first request can be serviced by a conventional data stream, in which each of the fragments are transmitted in their original sequence, rather than in an encoded fashion.

The implementation of this concept is depicted in Figure 8. Prior to any requests for the presentation, the allocated bandwidth is not being consumed by the presentation, and therefore can be used to transmit other data not associated with the presentation. When the first request Rl is received, a first transmission 36 of the presentation is started, at its beginning. This transmission is carried out in a conventional manner, i.e. the fragments are transmitted in their original sequential order. The integrated bandwidth that is required to service the first request is the same as that for a conventional transmission of a presentation.

When the next request R2 is received, part of the presentation may not have been transmitted yet in response to the first request. In this case, a second transmission 38 of the presentation begins on a newly allocated channel. This second transmission is encoded as depicted in Figure 2, i.e. segments of fragments are transmitted on respective substreams. In this case, however, the second transmission 38 does not include those portions of the presentation which remain to be sent in response to the earlier request, i.e. that portion of the first transmission 36 which is transmitted subsequent to the second request R2. In other words, the transmission 38 that occurs in response to the second request R2 is limited to those segments of the presentation which have already been transmitted in response to the prior request Rl. This limited portion that is transmitted in response to the second request is identified as the "prefix". Thus, the second requester receives the remaining portion of the presentation 36 that is being transmitted in a conventional format, and the prefix 38 that is transmitted in the encoded format. The prefix has exponentially decreasing bandwidth requirements, as in the profile of Figure 5. Depending upon the point at which the second request R2 is received, the last segment in the prefix 38 can be a partial segment.

As further requests are received, additional prefixes are transmitted, as appropriate. The amount of data that is transmitted in each prefix is dependent upon the portion of the presentation that has already been transmitted in the conventional manner. If the second request occurs very soon after the first one, the prefix is quite small, e.g. it may only contain the first few segments of the presentation, and hence require only a few substreams for its transmission. Later requests require a proportionately larger amount of data to be sent in the prefix. In essence, therefore, a portion of the available bandwidth is allocated, or leased, to each copy of the presentation that is requested. A fixed amount of the bandwidth is leased to the first request. The incremental amount of bandwidth that is leased to the second and subsequent requesters depends upon the times at which their requests arrive, relative to the first request. The unleased portion is available for other purposes.

If a request arrives while a prefix is still being transmitted in response to a previous request, as in the case of request R4, the later requester can take advantage of the fragments which are still being transmitted in response to that prior request, as in the situation depicted in Figure 4. Consequently, the maximum bandwidth requirements will remain bounded, in conformance with the graph of Figure 7. The limiting case occurs when the time between requests is no greater than τ. In this case, the total required bandwidth is equal to the amount of bandwidth η that is allocated to the encoded transmissions, plus the bandwidth required to transmit one conventional version of the presentation.

For purposes of the present disclosure, the bandwidth that is employed to transmit the conventional, or sequential, version of the presentation is identified as a first logical channel, and the bandwidth assigned for use by the encoded version of the presentation, i.e. the prefixes, is denoted as a second logical channel. The total bandwidth assigned to both logical channels, therefore, is η + 1. As described in greater detail in the previously cited application, this assigned bandwidth can be readily accommodated within a single analog television channel, e.g. 6MHz, when QAM-64 modulation is employed. If a request occurs after the conventional broadcast 36 of the presentation in the first logical channel has finished, as in the case of request R6, it is serviced by a new conventional, i.e. non-encoded, transmission 40 in that channel. Subsequent requests are then serviced by means of prefixes whose sizes, i.e. number of segments, are determined according to this second conventional transmission, as in the case of request R7.

In some situations, it may not be necessary to wait for the first conventional stream 36 to end before transmitting another conventional stream in response to a request. For instance, in the example of Figure 8, when a request R5 occurs near the end of the conventional transmission 36, a relatively large percentage of the bandwidth in the second logical channel is required for the initial portion of the prefix 42 that is transmitted in response to the request. Rather than transmit an encoded prefix at this time, it may be preferable to initiate the transmission of a new conventional stream. Such a situation is illustrated in the example of Figure 9. As depicted therein, when the request R5' occurs, a conventional stream of data 44 is transmitted within a third logical channel, which comprises a portion of the bandwidth assigned to the encoded transmissions. Thereafter, if additional requests are received, they are serviced by transmitting encoded prefixes whose sizes are determined relative to the second conventional transmission 44, rather than the first transmission 36. Thus, it can be seen that the prefixes that are transmitted in response to requests R6' and R7' are relatively small, in terms of bandwidth requirements, since they occur near the beginning of the second conventional transmission 44. Hence, by utilizing a second conventional transmission, together with the encoded substreams, the average bandwidth usage can be minimized.

The amount of overlap that is permitted between the first and second conventional transmissions is a function of the amount of bandwidth in the second logical channel that is available for the prefixes that derive from the first conventional transmission 36 and those which derive from the second conventional transmission 44. The permissible overlap can be viewed as a function fT, where 0 ≤ f < 1. The total amount of available bandwidth must be greater than or equal to η + logf + ceil(l/f), where log f is a negative number representing the amount of bandwidth that is saved by transmitting prefixes which do not require the full bandwidth η, and ceil(l/f) is the smallest integer no less than 1/f which represents the number of conventional streams that can be transmitted simultaneously. In the case of a fixed bandwidth allocation, e.g. η -I- 1, a second conventional stream can begin to be transmitted at the point at which the bandwidth which is unused by the first conventional stream and all prefixes transmitted up to that point is equal to or greater than the bandwidth that will be required by the second conventional stream and all subsequent prefixes which are based upon the second conventional stream.

In view of the foregoing, therefore, it can be seen that the bandwidth that is required to satisfy multiple requests for a simultaneous viewing of a presentation can be efficiently utilized by selectively transmitting conventional and encoded versions of the presentation in response to the various requests. The unused portion of the allocated bandwidth can then be employed for other types of data which are not time critical.

The basic procedures that are carried out to broadcast a variety of presentations in accordance with the foregoing principles are depicted in the block diagram of Figure 10. As a first step, each presentation is processed in an encoder 50, which determines the fragments that are to be contained within each segment, for transmission in respective substreams, as schematically depicted in Figure 2. If the encoded transmission of a presentation is periodic, the encoded version can be stored after it has been processed, and repetitively transmitted as appropriate. If, however, the encoding is not periodic, the encoding operation is performed on a continual basis.

The second step in the process is the allocation of the presentations to various transmission channels, in response to user requests. For example, if the first incoming request is to view Presentation 3, a channel allocator 52 assigns this presentation to the first available transmission channel. In this context, a "transmission channel" can be considered to be the equivalent of an analog television channel. If the next incoming request is for a different presentation, that presentation is assigned to another one of the available transmission channels. Once all of the available channels have been allocated, requests for additional presentations are denied until a channel becomes free, i.e. all transmissions of a previously requested presentation have ended.

The third major step in the process is the selective gating, or filtering, of the data that is transmitted on each channel. As described previously, when the first request for a presentation is received, a conventional stream of data is transmitted on the allocated channel. This can be achieved by decoding the presentation within the filter 54, or by providing the filter with an unencoded version of the presentation from the source. Subsequent requests are serviced by means of encoded transmissions of the segments in their respective substreams. The filter functions to transmit only the necessary portion of each prefix that is required in response to each received request. Hence, it suppresses the transmission of each fragment in a segment after one complete copy of the segment has been sent in response to a request. In addition, it suppresses the transmission of all later-occurring segments which have not yet been transmitted in the conventional data stream. When the available bandwidth in the allocated channel is not being occupied by the conventional data stream and the prefixes required for each request, the filter permits other, non-time-critical data to be transmitted over the channel.

The final component of the procedure is the decoder 14, which functions to store and time-shift the fragments in the encoded substreams, so that they appear in sequential order for presentation to the television receiver.

Depending upon the particular type of communication system in which the broadcast of presentations is carried out, a number of different configurations of these four main components are possible. One such configuration is illustrated in Figure 11. In this configuration, a relatively large amount of bandwidth is available between the presentation source and the subscribers. For instance, this configuration might be implemented in a satellite broadcast system having a significant number of transmission channels dedicated to on-demand movies. In this implementation, the functions of the encoder, the channel allocator and the filter are performed at the presentation source 10. The encoded presentations are relayed to the subscriber via a satellite 54. Individual decoders 14 at the subscribers' premises select the desired presentation from one of the available channels, for display. In this case, the number of different presentations that can be concurrently viewed by the system's subscribers is equal to the number of channels in the satellite system that are dedicated to the presentations.

A second implementation of the invention is depicted in Figure 12. In this implementation, the presentations are provided to the subscribers by means of a cable television distribution system. Typically, in such a system, the presentations are transmitted from a head end 56 to the subscribers by means of one or more intermediate sites 58 located along the transmission path. An intermediate site can be a hub, a node, a relay station, or the like. For purposes of the present disclosure, the term "node" is employed to designate these various types of intermediate sites.

Each node serves multiple subscribers, each of whom receives the same data from the node. However, different nodes can transmit different data to their respective subscribers. The transmission media 60 from the head end to the nodes might be optical fiber, whereas the links 62 from the nodes to the individual subscribers' premises might be coaxial cables. In one implementation of the invention, the subscribers' requests are transmitted directly to the head end 56. In this case, the functions of the channel allocator and the filter are performed at the head end. The encoding can also be done at the head end if the presentation source, e.g. a server, is located at the head end. Preferably, however, the encoding is carried out at a remote presentation source, and the encoded presentations are transmitted to multiple head end stations, for instance by means of a satellite feed. The encoded presentation can be stored at the head end after receiving one copy thereof, or it can be continuously broadcast to the head end, which then selectively passes segments along as they are needed in response to requests.

At the head end, the channel allocator identifies which presentations have been requested by at least one viewer on a node. It assigns each such presentation to a transmission channel on the path 60 to that node. If all of the transmission channels for that node are occupied, further requests for different presentations are temporarily denied, but further requests for the same presentation are fulfilled. The data filter also resides at the head end, and ensures that only one copy of each segment is transmitted to the node for each request.

In an alternative arrangement, the filtering function can be carried out at the individual nodes, rather than the head end. In this case, the requests are transmitted to the nodes, whereupon they are relayed to the head end. At the head end, the presentations are not transmitted until requests for those presentations are received. When this occurs, the channels are allocated in accordance with the received requests, and the encoded presentations are transmitted to the appropriate nodes. Hence, a first presentation might be transmitted over a given channel from the head end to one node, while a different presentation might be transmitted over the same channel from the head end to another node, in response to different requests. The presentations continue to be transmitted, until requests for those presentations are no longer present, i.e. no request has been received within a length of time equal to the largest segment in the presentation. At the nodes, the encoded presentations are selectively filtered, so that one copy of each segment is provided to each requesting subscriber. At the subscribers' premises, the encoded presentations are decoded for display. Hence, by performing the filtering function at the nodes, rather than the head end, the number of different presentations that can be watched by the subscribers increases, since the subscribers connected to one node are capable of viewing different presentations from those connected to another node. In some cases, subscribers may not possess decoders which are capable of reorganizing the fragments of an encoded presentation. In this case, the function of the decoder is carried out upstream of the subscribers' premises. For instance, it can be implemented at the node, whereupon the presentation is transmitted in the conventional format from the node to the subscribers via the coaxial cable. Alternatively, encoded transmissions can be sent to the head end, via satellite, and multiple decoders at the head end convert the data into a conventional broadcast, for transmission to the end users.

In general, therefore, each of the functions of encoding the stream of data, allocating transmission channels in response to requests, filtering the fragments that are transmitted, and decoding the data stream can be carried out at a variety of different locations, including the presentation source, the cable system head end, intermediate transmission nodes and the subscribers' premises. The various configurations can be used to advantage to accommodate the bandwidth capabilities of the particular broadcast system in which the invention is implemented, as well as the capabilities within the system for receiving upstream transmissions, operator maintenance requirements, etc.

As can be seen from the profile depicted in Figure 5, the selective transmission of encoded presentations in response to user requests provides significant bandwidth savings that can be employed to transmit other data. The bandwidth usage associated with a single viewer has an exponentially decreasing profile, with a sharp spike occurring just after the viewer's request is received. The spikes reside in the substreams that carry the shortest segments, which are also the substreams that are least occupied when requests are sparse. This profile suggests that many different presentations can share a fixed-bandwidth channel, by interleaving spikes.

To use the bandwidth savings to advantage with multiple presentations, each presentation is divided into two portions, an initial leader portion and a remainder portion. The leader portion could comprise, for example, the first few segments of the presentation. Referring to Figure 13, a channel of bandwidth η is used to transmit the remainder portions of each of the encoded presentations, in the manner described previously. An additional channel of bandwidth mΔη is allocated for the transmission of the leaders of m presentations . The leaders are transmitted in this additional channel in a shared manner. Requests are answered in order of arrival, with duplicates being eliminated for requests that have not yet been served. When the leader channel is empty, a user's request is answered immediately, by transmitting the leader on that channel, resulting in zero wait time. This situation is illustrated in Figure 13 for the request of a first movie Ml . Simultaneously, the remainder of the movie is transmitted in an encoded fashion on channel E_l5 and downloaded at the subscriber's premises for viewing once the leader ends. When the request for a second movie, M2, arrives, the leader channel is again empty, and so its leader is transmitted immediately at that time, and the remainder of the movie is transmitted in an encoded manner on channel E₂

If a request for a movie arrives while the leader channel is currently occupied, as in the case of request M3 , the transmission of its leader is delayed until space becomes available on the leader channel. However, the transmission of the remainder of the movie can begin immediately, on channel E₃ for storage at the subscriber's premises. In the worst case situation, in which the requests for all movies are densely spaced, the maximum wait time for the leader is Te^'VΔη. This wait time decreases in proportion to the number of movies that are in high demand. For instance, if k ≤ m movies are popular, the maximum wait time is (k/m) The^η/Δη.

Thus, by using a shared channel to transmit the leader portion of presentations, or at least those presentations which are in highest demand, the spikes associated with the transmissions in the encoded substreams can be reduced. This technique can be combined with other approaches to further reduce the required bandwidth and/or wait time. One such approach is to cache, or store, the initial portion of the leader at the viewer's site. For instance, the initial portion of the leader which corresponds to the maximum wait time can be repetitively broadcast. Preferably, this initial portion is broadcast for a number of movies which are in the highest demand, e.g. ten. Each of these initial portions are stored at the subscriber's premises. When a viewer enters a request for any of these movies, the stored portion can be replayed immediately, while the rest of the leader is queued and transmitted over the leader channel, and the remainder of the movie is transmitted in an encoded manner. Hence, for the most popular movies, the user will experience a wait time that is practically zero.

This approach can also be employed with other implementations of the invention as well, for instance where the leader channel is not utilized. In this case, the leading portions of each of the most popular presentations are broadcast and stored at the subscribers' premises ahead of time. When a viewer transmits a request for one of these presentations, the stored leader is played back immediately, while the remainder of the presentation is transmitted in an encoded form, pursuant to the embodiments of Figures 4, 8 or 9. By storing the initial portions of the presentations at the viewers' sites, the spikes in the encoded transmissions can be reduced.

In an analogous manner, caching of the leader can be employed at the source to reduce the effects of the bandwidth spikes. In one implementation of the invention, the presentations are stored at the presentation source on magnetic or optical disk media, and retrieved by a server in response to requests. To reduce the bandwidth requirements on the disk storage system, the shortest segments of the most popular presentations can be stored in a fast memory, such as random access memory, to be read therefrom while the remaining segments are retrieved from the disks.

It will be appreciated by those of ordinary skill in the art that the present invention can be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The presently disclosed embodiments are therefore considered in all respects to be illustrative, and not restrictive. The scope of the invention is indicated by the appended claims, rather than the foregoing description, and all changes that come within the meaning and range of equivalence thereof are intended to be embraced therein.

Claims

IN THE CLAIMS:

1. A method for transmitting a stream of temporally ordered data in a manner which ensures a bounded wait period before utilization of the data can commence at a receiving site, comprising the steps of: encoding the stream of data by dividing the stream of data into a sequence of fragments and grouping said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments; receiving requests to utilize the stream of data; designating one copy of each fragment to be transmitted in response to each received request; and selectively transmitting the designated copies of the fragments, in a manner such that each encoded segment of fragments is transmitted via a respective substream of data, and copies of fragments that are transmitted in response to later requests are limited to the fragments that have already been transmitted in response to earlier requests.

2. The method of claim 1 further including the step of selectively transmitting a copy of each fragment in an unencoded, sequential order in response to some of said requests.

3. The method of claim 2 wherein said fragments are transmitted in the unencoded, sequential order when a request is received while no other transmissions of the stream of data are taking place.

4. The method of claim 1 wherein all of said segments of fragments are continuously transmitted from a broadcast site to a node located between said broadcast site and the receiving site, and said selective transmission is carried out at said node.

5. The method of claim 1 wherein said encoding, receiving and designating steps are carried out a single site.

6. The method of claim 1 wherein said encoding step is carried out at a first site and the encoded data is transmitted to a second site where said receiving, designating and transmitting steps are carried out.

7. The method of claim 6 wherein the encoded data is continuously transmitted from said first site to said second site.

8. A method for transmitting a stream of temporally ordered data in a manner which ensures a bounded wait period before utilization of the data can commence at a receiving site, comprising the steps of: receiving requests to utilize the stream of data; and in response to each received request, transmitting one complete copy of the stream of data, which is encoded by dividing the stream of data into a sequence of fragments and grouping said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments, such that each encoded segment of fragments is transmitted via a respective substream of data.

9. The method of claim 8 wherein said requests are received at a broadcast site, and the encoded data is stored at said broadcast site.

10. The method of claim 8 wherein the encoded data is transmitted from a first site to a second site at which said requests are received, and said encoded data is selectively retransmitted from said second site to a receiving site in response to received requests.

11. The method of claim 10 wherein said second site carries out the further step of filtering the copies of the fragments that are transmitted such that copies of fragments that are retransmitted in response to later requests are limited to the fragments that have already been retransmitted in response to earlier requests.

12. A method for transmitting a stream of temporally ordered data in a manner which ensures a bounded wait period before utilization of the data can commence at a receiving site, comprising the steps of: receiving an encoded stream of data which comprises a sequence of fragments which are grouped into successive segments each having a length which is a function of the segment's location within the sequence of fragments, and transmitted in a manner such that each encoded segment of fragments is received via a respective substream of data; receiving requests to utilize the stream of data; and retransmitting one copy of each fragment in response to each received request such that copies of fragments that are transmitted in response to later requests are limited to the fragments that have already been transmitted in response to earlier requests.

13. A method for transmitting a stream of temporally ordered data in a manner which ensures a wait period having a length no greater than τ before utilization of the data can commence at a receiving site, comprising the steps of: encoding the stream of data by dividing the stream of data into a sequence of fragments and grouping said fragments into multiple segments, such that the £th segment from the beginning of the data stream has a maximum length substantially equal to τ(l +λ) , where 0<λ<0.5; receiving a first request to utilize the stream of data, and transmitting said fragments in sequential order via a first logical channel, in response to said first request; receiving a second request to utilize the stream of data while said stream of data is being transmitted via said first logical channel; and transmitting each segment of fragments that has already been transmitted in said first logical channel upon the receipt of said second request via a respective encoded substream of data in a second logical channel.

14. The method of claim 13 further including the step of receiving a third request to utilize the stream of data, and transmitting said fragments in sequential order via a third logical channel in response to said third request, when said third request is received within a predetermined time prior to the termination of the transmission of the data stream in said first logical channel.

15. The method of claim 14 further including the step of receiving a fourth request to utilize the stream of data subsequent to receipt of said third request, and transmitting each segment of fragments that has already been transmitted in said third logical channel upon the receipt of said fourth request via a respective encoded substream of data in said second logical channel.

16. The method of claim 13 wherein each of said fragments contains the same amount of data from said stream.

17. The method of claim 13 wherein said first logical channel contains multiple substreams of data that are transmitted in a time-division multiplexed manner.

18. The method of claim 13 wherein the substreams of said second logical channel are transmitted in a time-division multiplexed manner.

19. The method of claim 13 wherein 1/λ is in a range from about 3 to about 25.

20. A method for transmitting a stream of temporally ordered data in a manner which ensures a wait period having a length no greater than τ before utilization of the data can commence at a receiving site, comprising the steps of: dividing the stream of data into a sequence of fragments; grouping said fragments into multiple segments, such that the / th segment from the beginn iinngg < of the data stream has a maximum length substantially equal to τ(l +λ) , where 0<λ<0.5; receiving a first request to utilize the stream of data, and transmitting said fragments in sequential order via a first logical channel, in response to said first request; receiving a second request to utilize the stream of data while said stream of data is being transmitted via said first logical channel; and selectively transmitting each segment of fragments that has already been transmitted in said first logical channel upon the receipt of said second request via a respective encoded substream of data in a second logical channel, or initiating the transmission of said fragments in sequential order via a third logical channel in response to said second request.

21. The method of claim 20 wherein the fragments are selected for transmission in the second logical channel or the third logical channel, in response to said second request, in dependence upon whether the second request is received within a predetermined time prior to the termination of the transmission of the data stream in said first logical channel.

22. A method for delivering a streaming media presentation via a broadcast network, comprising the steps of: dividing the presentation into a sequence of data fragments; grouping said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments; repetitively transmitting each segment of fragments in a respective substream of encoded data from a broadcast source to a node that is located between said broadcast source and viewing locations; receiving a request at said node to view the presentation at one of said viewing locations; storing a copy of each of the fragments received over said substreams at said node upon receiving said request; and transmitting the stored fragments from said node to said viewing location in sequential order.

23. The method of claim 22 wherein the transmission of the stored fragments from said node to the viewing location commences after one copy of every fragment in the first segment has been received at said node subsequent to said request.

24. The method of claim 22 wherein said fragments are transmitted from said node in sequential order via a first logical channel, and further including the steps of receiving a second request at said node to utilize the stream of data while said stream of data is being transmitted via said first logical channel, and transmitting each segment of fragments that has already been transmitted in said first logical channel upon the receipt of said second request via a respective encoded substream of data in a second logical channel.

25. A method for delivering a streaming media presentation via a broadcast network, comprising the steps of: dividing the presentation into a sequence of data fragments; grouping said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments; repetitively transmitting each segment of fragments in a respective substream of encoded data from a broadcast source to a node that is located between said broadcast source and viewing locations; receiving requests at said node to view the presentation at respective viewing locations; and transmitting one complete copy of each segment from said node to said viewing locations in response to each received request.

26. The method of claim 25 wherein, when a second request is received at said node while a copy of at least one segment is being transmitted in response to a first request, only those portions of segments which were transmitted prior to the second request are retransmitted to provide one complete copy in response to the second request.

27. The method of claim 25 further including the step of receiving said requests at said broadcast source, and inhibiting the transmission of said segments from said broadcast source to said node until a request for the presentation is received at the broadcast source.

28. The method of claim 27 further including the step of terminating the transmission of said segments from the broadcast source if no request for the presentation is received within a period equal to the length of the longest segment.

29. A method for transmitting multiple streams of temporally ordered data in a manner which ensures a bounded wait period before utilization of any of the streams of data can commence at a receiving site, comprising the steps of: dividing each stream of data into a leader portion and a remainder portion; encoding the remainder portion of each stream of data by dividing the data into a sequence of fragments and grouping said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments; receiving requests to utilize the streams of data; transmitting the leader portion of a requested stream over a first logical channel which is common to all of said leader portions; and transmitting one copy of each fragment in the remainder portion of a requested stream over a second logical channel, in response to each received request, in a manner such that each encoded segment of fragments is transmitted via a respective substream of data within said second logical channel.

30. The method of claim 29, wherein the leader portions of multiple requested streams are transmitted serially over said first logical channel.

31. The method of claim 30 wherein, when a new request is received while a leader is being transmitted in response to a prior request, the transmission of the leader that is responsive to the new request is delayed until the leaders which are responsive to prior requests have been transmitted over said first logical channel.

32. The method of claim 31 wherein the transmission of the remainder portion which is responsive to the new request is initiated upon receipt of the new request, such that plural remainder portions are transmitted in a temporally overlapping manner.

33. A system for transmitting a stream of temporally ordered data in a manner which ensures a bounded wait period before utilization of the data can commence at a receiving site, comprising: an encoder which divides the stream of data into a sequence of fragments and groups said fragments into successive segments each having a length which is a function of the segment's location within the sequence of fragments; a channel allocator which allocates fragments to be transmitted to a transmission channel, such that each segment is transmitted via a respective substream within the allocated transmission channel; and a filter which is responsive to requests to utilize the stream of data to selectively transmit copies of fragments via their respective substreams within the allocated channel, such that copies of fragments that are transmitted in response to later requests are limited to the fragments that have already been transmitted in response to earlier requests.

34. The system of claim 33 including a broadcast source and multiple nodes located in transmission paths between the broadcast source and receiving sites, and wherein said filter is located at each of said nodes.

35. The system of claim 33 wherein the data stream is divided into a leader portion and a remainder portion, and wherein said encoder encodes said remainder portion into said groups of fragments, and further wherein said channel allocator allocates said leader portion to a first channel for transmission and allocates the encoded remainder portion to a second channel for transmission.

36. The system of claim 35 wherein said channel allocator allocates the leader portions of multiple data streams to said first channel for shared transmission therein, and allocates separate respective channels for the encoded remainder portions of said multiple data streams.