Method of Providing and Retrieving a Data Segment

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

1. Field of the Invention

The described invention relates to the field of data storage and transmission. In particular, the invention relates to a method of providing a data segment with minimal access latency. A data segment is defined herein as a sequential data stream of finite length. The data segment includes, but is not limited to, any combination of audio and/or video data.

2. Description of Related Art

On-demand systems are employed in various settings. For example, on-demand movies are shown on cable television and on private television networks, such as those found in a hotel. The cable company and the hotel are able to provide the video to a user upon the request of the user (on-demand). On-demand systems use a back channel to provide a signal to the cable provider's or hotel's video server to begin providing the on-demand movie. The back channel may be accessed using a remote control to transmit information of the user's request to a television set or set-top box, which in turn provides a signal to the video server. Alternatively, the user may call via telephone (the back channel) to order a movie. The movie will then be broadcast for the user to view.

Near-on demand refers to a system which may not begin immediately at the request of the user. Instead, the near-on demand system repeats at intervals that are short enough to be acceptable to the user. The user no longer needs to use a back channel to indicate that he wishes to access the data segment. Instead, he just waits for the data segment to restart in order to view the data segment from the beginning.

One way of providing a data segment using a near-on-demand system is by providing the entire data segment on multiple channels, each channel offset by a fixed time interval. For example, if a data segment is two hours long, four channels (with offsets of 0, 30, 60, and 90 minutes) would adequately allow for a person to access the data segment from the beginning every 30 minutes. The user can tune in to the channel that is next to restart the data segment from the beginning. However, this method takes many channels to reduce to a reasonable amount the access latency, i.e., the maximum waiting period until the data segment is restarted. In the above example, using four channels, a person may need to wait up to 30 minutes for the data segment to restart. This amount of time may be unacceptable to many users.

A method of providing a data segment is disclosed. The data segment is divided into three or more portions and provided via two or more channels. Each of the channels carries a portion of the data segment, the portion of the data segment carried by each channel being less than the entire data segment. Each of the channels repeat over time.

In one embodiment, the two or more channels are physical channels. In another embodiment, the two or more channels are logical channels which are time-multiplexed over a single physical channel.

A method of accessing the data segment provided as discussed above is also disclosed. Additionally, a device that stores a data segment using two or more channels is disclosed.

FIG. 1 is a block diagram illustrating the hardware used for accessing a data segment provided over two or more channels.

FIG. 2 is a block diagram illustrating an alternate embodiment of hardware used for accessing the data segment provided over two or more channels.

FIG. 3A shows an embodiment in which a data segment has been divided into portions of equal length.

FIGS. 3B-3H show pictorially what the hardware does for one embodiment during various time intervals corresponding to t=0 to t=7, as shown in FIG. 3A.

FIGS. 4A-4H show pictorially what the hardware does to access the same data segment of FIGS. 3A-3H one time interval later.

FIG. 5A-5H show pictorially what the hardware does to access the same data segment of FIGS. 3A-3H two time intervals later.

FIG. 6A-6H show pictorially what the hardware does to access the same data segment of FIGS. 3A-3H three time intervals later.

FIG. 7 shows an alternate embodiment, in which the two or more channels are not physical channels, but are logical channels which are time-multiplexed over a single physical channel.

FIG. 8 shows an embodiment employing a time-division multiplexed (TDM) data segment using the techniques of the present invention to improve the access time to retrieve data from a storage medium such as a hard disk, or CD-ROM.

A method of providing a data segment with minimal access latency is described. The invention uses hardware that is able to simultaneously record one or more channels while another channel is being viewed directly or played back from storage. One example of such hardware is in copending patent application entitled "Method of Time Shifting to Simultaneously Record and Play A Data Stream," Serial No. 08/996,535, filed concurrently with this application and assigned to the same corporate assignee. However, other such hardware can be constructed to provide record and playback capability based off of different channels.

The invention provides a way of accessing a data segment with minimal access latency. This is accomplished by providing the first portion of the data segment on a first channel that is repeated at a high rate of frequency. Thus, a user will not have to wait long to begin accessing the first portion of the data stream.

While the user is accessing the first portion of the data stream, the user can also record subsequent portions of the data segment which are being provided on other channels. In this way, the user is able to access either a portion of the data segment directly from one of the channels, or a portion of the data segment that has been buffered to a storage unit.

The channels are arranged to provide data in such a way that it is possible to provide the entire data segment from the beginning to end at the same rate of frequency that the first portion of the data segment is provided.

An example is helpful to describe how the channels can be set up to take advantage of the present invention. FIG. 3A shows an embodiment in which a data segment has been divided into portions of equal length. In this particular case, he data segment is divided into seven portions, sequentially numbered from 1 to 7. The portions are divided among various channels. In this example, the portions are divided among three separate channels.

On channel 1, portion 1 is repeated over and over again. At each time interval, T, which in this case, is one seventh of the length of the data segment, portion 1 repeats.

On channel 2, portions 2 and 3 are repeated. After every two time intervals, T, portion 2 repeats. Portion 3 follows portion 2.

On channel 3, portions 4, 5, 6, and 7 are repeated. After every four time intervals, T, portion 4 repeats. The rest of the portions follow each other sequentially.

In one embodiment, index information precedes each portion indicating which portion of the data segment follows. In the example of FIG. 3A, the index information identifies which of the portions 1 to 7 is being provided on a particular channel). There are numerous ways of providing this type of index information. For example, the index information may be embedded in the data segment itself, such as a time index of the data segment. Alternatively, the receiver may be able to determine which portion of the data segment is being provided by knowing the time schedule according to which the portions are provided on the channels.

FIGS. 3B-3H show pictorially what the hardware does for one embodiment during various time intervals corresponding to t=0 to t=7, as shown in FIG. 3A. FIGS. 3B-3H show an output device and a storage device. In this example, portions of the data segment are provided to the output device. They are provided directly from a receiver (rcvr), or they are provided from a storage device. Portions of the data segment are also stored to the storage device during various time intervals. In this example, the output device is a monitor (mon), and the storage device is a hard disk (hdd).

FIG. 3B shows pictorially what the hardware does during the first time interval t=[0 . . . 1): The portion 1 is sent to the monitor while portion 4 is saved to the storage device. NOTE: The time notation above uses a left bracket to indicate time inclusive of the end point; the right parenthesis indicates time non-inclusive of the end point. However, this is meant to be an example only; the exact cut off times for a portion being included or not included in a particular time interval T, may vary by implementation.

FIG. 3C shows pictorially what the hardware does during the second time interval t=[1 . . . 2): The portion 2 is displayed to the monitor while portion 5 is saved to the storage device.

FIG. 3D shows pictorially what the hardware does during the third time interval t=[2 . . . 3): The portion 3 is displayed to the monitor while portion 6 is saved to the storage device.

FIG. 3E shows pictorially what the hardware does during the fourth time interval t=[3 . . . 4): As was previously mentioned, portion 4 was already stored to the storage device as shown in FIG. 1b. At time t=[3 . . . 4), portion 4 is retrieved from the storage device and displayed to the monitor while portion 7 is saved to the storage device.

FIG. 3F shows pictorially what the hardware does during the fifth time interval t=[4 . . . 5): The portion 5 is retrieved from the storage device and displayed to the monitor.

FIG. 3G shows pictorially what the hardware does during the sixth time interval t=[5 . . . 6): The portion 6 is retrieved from the storage device and displayed to the monitor.

FIG. 3H shows pictorially what the hardware does during the seventh time interval t=[6 . . . 7): The portion 7 is retrieved from the storage device and displayed to the monitor.

Thus, if a user accesses the 3 channels at time t=0 (or up to one time interval before t=0), the user is able to view the entire data segment by recording portions of the data segment while other portions are being displayed. A data flow manager handles the routing of the portions of the data segment from the multiple channels to and from the storage unit, and to the output device.

FIGS. 4A-4H show pictorially what the hardware does to access the same data segment of FIGS. 3A-3H one time interval later, i.e., starting at time t=1. Although the data being provided on the channels at time t=1 is the same as in FIG. 3A, the sequence of buffering the portions of the data segment on the different channels varies from that of FIGS. 3A. This is because the portions of the data segment have a different timing relationship to one another. For example, for time t=[1 . . . 2), in the sequence of FIG. 3C, portion 5 is stored to the hard disk, while portion 2 is displayed. In FIG. 4B, portion 2 is recorded while portion 1 is displayed. The portion being displayed is dictated by the starting time of the data segment being accessed.

In the previous description, only one channel is recorded at a time. Another embodiment allows multiple channels to be recorded at the same time. For example, in FIG. 3B, portion 1 and 4 can be saved to the storage device during t=[0 . . . 1). As shown in FIG. 3C, portion 2 and 5 can be saved to the storage device during t=[1 . . . 2), and as shown in FIG. 3D, portion 3 and 6 can both be saved to the storage device during t=[2 . . . 3). In this manner, combined with the other time periods which need only save a portion from a single channel, the storage device can store the entire data segment. In one embodiment, once all or portions of the data segment are stored on the storage device, the near on demand system 100 is able to access the data segment immediately on future accesses.

FIG. 5A-5H show pictorially what the hardware does to access the same data segment of FIGS. 3A-3H two intervals later, i.e., starting at time t=2. Similarly, FIGS. 6A-6H show how the same data segment is handled by the hardware starting at time t=3. The data segment starting at time t=4 would be similar to FIGS. 3A-3H, and so forth. Thus, a data segment may be accessed from the three channels every interval time T.

Using the above example, for a two hour movie, the time interval T is equal to 2 hours divided by the 7 time intervals taken to view the movie. This amounts to 17 minutes and 8 seconds, which is approximately 2.33 times better in terms of access latency than that which would be provided by the prior art method or using three channels to provide the entire data segment every 40 minutes.

Tables 1, 2 and 3 show the approximate gains in access time latency using the present invention versus using the same number of channels to provide the entire data segment as in the prior art.

Depending on the hardware used, two or more channels can be received or tuned at the same time ("tune" in Tables 1-3), and one or more channels can be recorded at the same time ("rec" in Tables 1-3). While one embodiment may actually tune to different channels, an alternate embodiment may de-multiplex channels from a data stream containing two or more channels. In this alternate embodiment, the "tuned" numbers would refer to the number of channels that could be simultaneously de-multiplexed. Other methods of simultaneously providing multiple channels to the system are also possible. Table 1 shows information for a system which can tune two channels (tune=2) at a time, but can only record one of the channels at a time (rec=1). Table 2 shows information for a system which can tune two channels at a time, and can record both of the channels. Table 3 shows information for a system which can tune and record all of its channels.

Tables 1, 2, and 3 show that there are advantages to being able to record more than one channel at a time. However, with a minimum configuration that receives two channels and that can record one of the channels at a time, there is still a gain over the prior art method of providing the entire data segment over each channel.

Table 1 shows a best channel length set up using 1 to 10 channels for a system which can tune two channels at a time, but can only record one of the channels at a time. For a 1 channel implementation, there is no improvement over the prior art. However, using 2 channels, there is a 1.5 time improvement over the prior art in terms of access latency. Using 2 channels, the first channel provides the first portion (1 portion total) which is repeated. The second channel provides the second and third portions (2 portions total) which are repeated. Thus, there are 3 portions total, and the access latency is 40 minutes.

In Table 1, using 3 channels, there is a 1.67 time improvement in access time latency over the prior art. Channel 1 provides the first portion (1 portion total) which is repeated; channel 2 provides the second and third portions (2 portions total) that are repeated; and channel 3 provides the fourth and fifth portions (2 portions total) that are repeated.

In Table 1, using 4 channels, there is a 2.25 time improvement in access time latency over the prior art. Channel 1 provides the first portion (1 portion total) which is repeated; channel 2 provides the second and third portions (2 portions total) that are repeated; channel 3 provides the fourth and fifth portions (2 portions total) that are repeated; and channel 4 provides the sixth, seventh, eighth, and ninth (4 portions total) that are repeated.

In Table 1, because there is a limit to the number of channels that can be recorded at the same time, the number of portions which can be repeated on a given channel is restricted. Table 3, for example, does not have a restriction on the number of channels that can be recorded at the same time. Table 3 is thus able to double the number of portions per channel for each additional channel added.

Additionally, the order of the portions has to be structured in such a way that no matter at which time interval the data segment is accessed, the entire data segment will be able to be accessed in its entirety. For a system that is constrained by the number of channels that can be recorded, such as that of Table 1, the ordering of the portions is important. The portions of the data segment on a channel may need to be set up with a particular phase. A phase of X indicates that the portions are ordered sequentially, but rotated by X. For example, a 4-portion length of a data segment starting with portion 4 and having a phase of 0 is the sequence of portions (4, 5, 6, 7). A phase of 1 indicates the portions of the channel are ordered sequentially but rotated by one (e.g., 5, 6, 7, 4). A phase of 2 indicates the portions of the channel are ordered sequentially but rotated by two (e.g., 6, 7, 4, 5). A phase of 3 indicates the portions of the channel are ordered sequentially but rotated by three (e.g., 7, 4, 5, 6). A method of determining a proper order for the portions of the data segments and their phase relative to the channels has been determined. If the order is incorrectly set up, the entire data segment may not be accessible from all possible starting points with the desired access latency.

Tables 1, 2 and 3 show a length (the total number of portions on a channel) and the phase for the channel. FIG. 3A, 4A, 5A and 6A, for example, used a channel set up comprising three channels set up with length/phase of (1.0 2.0 4.1). This is easiest to see in FIG. 4A starting at time t=1.

A program which calculates the best length/phase set up for channels which are constrained by the number of channels that can be either tuned or recorded is attached in the Appendix. [Dennis, do you have a soft copy of the program?, Otherwise, I'll submit the hardcopy I have.]

FIG. 1 is a block diagram illustrating the hardware used for accessing a data segment provided over two or more channels. Receiver hardware receives the portions of the data segment over the two or more channels. In one embodiment, the receiver hardware may be a modem, a tuner, or a network interface.

From the receiver hardware, the two or more channels are separated. They are also optionally compressed at this step. A data flow manager routes the portions of the data segment to a storage unit or buffers the portions of the data segment to an output device such as an audio/video output. Decompression is performed if the data had been compressed in a previous step.

FIG. 2 is a block diagram illustrating an alternate embodiment of hardware used for accessing the data segment provided over two or more channels. In this case, the receiver hardware provides the portions of the data segment to a scheduler and data flow manager. The raw data is buffered to the hard disk as needed. The scheduler/data flow manager then provides the portions of the data segment to a subchannel separator, from which the separate portions of the data segment are buffered and selected to be provided at the audio/video output.

The present invention has many potential uses: For example, it can be used for near-on-demand movies that are provided over cable, or broadcast as Direct Broadcast Satellite (DBS) or Advanced TV (ATV). It can be used for providing music via the Internet, cable, DBS or ATV. It can provide news clips, text, or audio over the Internet.

Encryption can also be employed with the present invention. For example, all channels may be encrypted except for channel 1. Thus, non-subscribers to the broadcast service would be able to watch the first portion of a movie, for example, since it is not encrypted. However, the non-subscribers would not be able to view the encrypted portions. This provides a valuable "free preview" capability.

In one embodiment, a programmable computer is used for performing the various operations such as compression, decompression, scheduling/routing of portions of the data segment to the hard disk or the output device. Application software may be written to employ the techniques of the present invention. In other cases, the operating system of the computer may use the techniques present invention to lower access latency.

FIG. 7 shows an alternate embodiment, in which the two or more channels are not physical channels. Instead, the two or more channels are logical channels that are time-multiplexed over a single physical channel. For example, a time-division multiplexed (TDM) signal that has a high compression could be used to provide a data segment to a user with minimal access latency.

FIG. 8 shows an embodiment employing a TDM data segment using the techniques of the present invention to improve the access time to retrieve data from a storage medium such as a hard disk, or CD-ROM. Because of the circular nature of the medium, a head positioned on a particular track of a hard disk or CD-ROM, is able to access a data segment stored on the storage medium with a minimal access latency. The trade off is the storing of more data to the storage medium to allow for a faster access time, and the decrease in the rate at which the information is retrieved to M/N, where M is the bit rate of the storage device and N is the number of channels used. However, some implementations benefit from the increased access time achievable. Implementing the techniques of the present invention for storing and retrieving a TDM data segment to and from a storage medium, may be done via application software or via an operating system.

To illustrate how the techniques of the present invention can be applied, a normal access to a hard disk has an average access time of a seek time plus half a rotation period. In the worst case, the normal access to a hard disk is the seek time plus a full rotation period. Using four channels that are time-division multiplexed and stored on the hard disk, the average time to access the data is the seek time plus 1/30 of a rotation period. The worst case is the seek time plus 1/15 of the rotation period. (Table 3 shows a four channel case in which a data segment is divided into 15 portions. If the data segment is spread out equally over the entire length of the circular track, the data segment restarts every 1/15 of a rotation. However, the data segment could be repeated multiple times to allow for a lower access latency.) A hard disk access could be improved by several milliseconds, assuming a rotation period of approximately 8.3 ms for a 7200 RPM hard drive. Similarly, for a 8X CD-ROM, a delay from rotation is 50 ms worst case, which can be reduced significantly using the techniques of the present invention.

Thus, a method of providing a data segment with minimal access latency is disclosed. The specific arrangements and methods described herein are merely illustrative of the principles of this invention. For example, the same method may be used to store and retrieve other types of data segments besides video segments. Numerous modifications in form and detail may be made without departing from the scope of the described invention. Although this invention has been shown in relation to a particular embodiment, it should not be considered so limited. Rather, the described invention is limited only by the scope of the appended claims.