Prefetched data in a digital broadcast system6725267Abstract A method for sending data to a client to provide data-on-demand services comprises the steps of: receiving a data file, specifying a time interval, parsing the data file into a plurality of data blocks based on the time interval such that each data block is displayable during a time interval, determining a required number of time slots to send the data file, allocating to each time slot at least a first of the plurality of data blocks and optionally one or more additional data blocks, such that starting from any of the time slots, (i) the data file can be displayed by accessing the first of the plurality of data blocks; (ii) at a consecutive time slot, a next data block sequential to a prior displayed data block is available for displaying; and (iii) repeating step (ii) until all of the plurality of data blocks for the data file has been displayed, and sending the plurality of data blocks based on the allocating step. Claims What is claimed is: Description BRIEF DESCRIPTION OF THE INVENTION
Estimated_BLK_Size = (DataFile_Size * TS)/DataFile_Length (1)
BLK SIZE = (Estimated BLK Size + CLUSTER_SIZE - 1 Byte)/ (2)
CLUSTER_SIZE
BLK_SIZE_BYTES = BLK_SIZE * CLUSTER_SIZE (3)
NUM_OF_BLKS = (DataFile_Size + BLK_SIZE_BYTES - (4)
1 Byte)/BLK_SIZE_BYTES
In equations (1) to (4), the Estimated_BLK_Size is an estimated block size (in Bytes); the DataFile_Size is the data file size (in Bytes); TS represents the duration of a time slot (in seconds); DataFile_Length is the duration of the data file (in seconds); BLK SIZE is the number of clusters needed for each data block; CLUSTER_SIZE is the size of a cluster in the local memory 208 for each channel server 104 (e.g., 64 KBytes); BLK_SIZE_BYTES is a block size in Bytes. In this embodiment, the number of blocks (NUM_OF_BLKS) is equal to the data file size (in Bytes) plus a data block size in Bytes minus 1 Byte and divided by a data block size in Bytes. Equations (1) to (4) illustrate one specific embodiment. A person of skill in the art would recognize that other methods are available to calculate a number of data blocks for a data file. For example, dividing a data file into a number of data blocks is primarily a function of an estimated block size and the cluster size of the local memory 208 of a channel server 104. Thus, the invention should not be limited to the specific embodiment presented above. FIG. 4 illustrates an exemplary process for generating a scheduling matrix for sending a data file in accordance with an embodiment of the invention. In an exemplary embodiment, this invention uses time division multiplexing (TDM) and frequency division multiplexing (FDM) technology to compress and schedule data delivery at the server side. In an exemplary embodiment, a scheduling matrix is generated for each data file. In one embodiment, each data file is divided into a number of data blocks and the scheduling matrix is generated based on the number of data blocks. Typically, a scheduling matrix provides a send order for sending data blocks of a data file from a server to clients, such that the data blocks are accessible in sequential order by any client who wishes to access the data file at a random time. At step 402, a number of data blocks (x) for a data file is received. A first variable, j, is set to zero (step 404). A reference array is cleared (step 406). The reference array keeps track of data blocks for internal management purposes. Next, j is compared to x (step 408). If j is less than x, a second variable, i, is set to zero (step 412). Next, i is compared to x (step 414). If i is less than x, data blocks stored in the column [(i+j) modulo (x)] of a scheduling matrix are written into the reference array (step 418). If the reference array already has such data block(s), do not write a duplicate copy. Initially, since the scheduling matrix does not yet have entries, this step can be skipped. Next, the reference array is checked if it contains data block i (step 420). Initially, since all entries in the reference array has been cleared at step 406, there would be nothing in the reference array. If the reference array does not contain data block i, data block i is added into the scheduling matrix at matrix position [(i+j) modulo (x), j] and the reference array (step 422). After the data block i is added to the scheduling matrix and the reference array, i is incremented by 1, such that i=i+1 (step 424), then the process repeats at step 414 until i=x. If the reference array contains data block i, i is incremented by 1, such that i=i+1 (step 424), then the process repeats at step 414 until i=x. When i=x, j is incremented by 1, such that j=j+1 (step 416) and the process repeats at step 406 until j=x. The entire process ends when j=x (step 410). In an exemplary embodiment, if a data file is divided into six data blocks (x=6), the scheduling matrix and the reference arrays are as follows:
Scheduling Matrix (SM)
TS0 TS1 TS2 TS3 TS4 TS5
[0, 0] blk0 [1, 0] blk1 [2, 0] blk2 [3, 0] blk3 [4, 0] blk4 [5, 0] blk5
[0, 1] [1, 1] blk0 [2, 1] [3,1] [4, 1] [5, 0]
[0, 2] [1, 2] [2, 2] blk0 [3, 2] blk1 [4, 2] [5, 1]
[0, 3] [1, 3] [2, 3] [3, 3] blk0 [4, 3] [5, 2] blk2
[0, 4] [1, 4] blk3 [2, 4] [3, 4] [4, 4] blk0 [5, 3] blk1
[0, 5] [1, 5] [2, 5] [3, 5] blk4 [4, 5] [5, 4] blk0
Reference Array (RA)
space0 space 1 space 2 space3 space4 space5
TS0 blk0 blk1 blk2 blk3 blk4 blk5
TS1 blk1 blk0 blk2 blk3 blk4 blk5
TS2 blk2 blk0 blk3 blk1 blk4 blk5
TS3 blk3 blk1 blk0 blk4 blk5 blk2
TS4 blk4 blk0 blk5 blk2 blk1 blk3
TS5 blk5 blk2 blk1 blk0 blk3 blk4
In this exemplary embodiment, based on the scheduling matrix above, the six data blocks of the data file are sent in the following sequence:
TS0 => blk0
TS1 => blk0, blk1, blk3
TS2 => blk0, blk2
TS3 => blk0, blk1, blk3, blk4
TS4 => blk0, blk4
TS5 => blk0, blk1, blk2, blk5
In another exemplary embodiment, a look-ahead process can be used to calculate a look-ahead scheduling matrix to send a predetermined number of data blocks of a data file prior to a predicted access time. For example, if a predetermined look-ahead time is the duration of one time slot, for any time slot greater than or equal to time slot number four, data block 4 (blk4) of a data file should be received by a STB 300 at a subscribing client at or before TS3, but blk4 would not be played until TS4. The process steps for generating a look-ahead scheduling matrix is substantially similar to the process steps described above for FIG. 4 except that the look-ahead scheduling matrix in this embodiment schedules an earlier sending sequence based on a look-ahead time. Assuming a data file is divided into six data blocks, an exemplary sending sequence based on a look-ahead scheduling matrix, having a look-ahead time of the duration of two time slots, can be represented as follows:
TS0 => blk0
TS1 => blk0, blk1, blk3, blk4
TS2 => blk0, blk2
TS3 => blk0, blk1, blk3, blk4, blk5
TS4 => blk0, blk5
TS5 => blk0, blk1, blk2
A three-dimensional delivery matrix for sending a set of data files is generated based on the scheduling matrices for each data file of the set of data files. In the three-dimensional delivery matrix, a third dimension containing IDs for each data file in the set of data files is generated. The three-dimensional delivery matrix is calculated to efficiently utilize available bandwidth in each channel to deliver multiple data streams. In an exemplary embodiment, a convolution method, which is well known in the art, is used to generate a three-dimensional delivery matrix to schedule an efficient delivery of a set of data files. For example, a convolution method may include the following policies: (1) the total number of data blocks sent in the duration of any time slot (TS) should be kept at a smallest possible number; and (2) if multiple partial solutions are available with respect to policy (1), the preferred solution is the one which has a smallest sum of data blocks by adding the data blocks to be sent during the duration of any reference time slot, data blocks to be sent during the duration of a previous time slot (with respect to the reference time slot), and data blocks to be sent during the duration of a next time slot (with respect to the reference time slot). For example, assuming an exemplary system sending two short data files, M and N, where each data file is divided into six data blocks, the sending sequence based on a scheduling matrix is as follows:
TS0 => blk0
TS1 => blk0, blk1, blk3
TS2 => blk0, blk2
TS3 => blk0, blk1, blk3, blk4
TS4 => blk0, blk4
TS5 => blk0, blk1, blk2, blk5
Applying the exemplary convolution method as described above, possible combinations of delivery matrices are as follows:
Total Data Blocks
Option 1: Send video file N at shift 0 TS
TS0 => M0, N0 2
TS1 => M0, M1, M3, N0, N1, N3 6
TS2 => M0, M2, N0, N2 4
TS3 => M0, M1, M3, M4, N0, N1, N3, N4 8
TS4 => M0, M4, N0, N4 4
TS5 => M0, M1, M2, M5, N0, N1, N2, N5 8
Option 2: Send video file N at shift 1 TS
TS0 => M0, N0, N1, N3 4
TS1 => M0, M1, M3, N0, N2 5
TS2 => M0, M2, N0, N1, N3, N4 6
TS3 => M0, M1, M3, M4, N0, N4 6
TS4 => M0, M4, N0, N1, N2, N5 6
TS5 => M0, M1, M2, M5, N0 5
Option 3: Send video file N at shift 2 TS
TS0 => M0, N0, N2 3
TS1 => M0, M1, M3, N0, N1, N3, N4 7
TS2 => M0, M2, N0, N4 4
TS3 => M0, M1, M3, M4, N0, N1, N2, N5 8
TS4 => M0, M4, N0 3
TS5 => M0, M1, M2, MS, N0, N1, N3 7
Option 4: Send video file N at shift 3 TS
TS0 => M0, N0, N1, N3, N4 5
TS1 => M0, M1, M3, N0, N4 5
TS2 => M0, M2, N0, N1, N2, N5 6
TS3 => M0, M1, M3, M4, N0 5
TS4 => M0, M4, N0, N1, N3 5
TS5 => M0, M1, M2, MS, N0, N2 6
Option 5: Send video file N at shift 4 TS
TS0 => M0, N0, N4 3
TS1 => M0, M1, M3, N0, N1, N2, N5 7
TS2 => M0, M2, N0 3
TS3 => M0, M1, M3, M4, N0, N1, N3 7
TS4 => M0, M4, N0, N2 4
TS5 => M0, M1, M2, M5, N0, N1, N3, N4 8
Option 6: Send video file N at shift 5 TS
TS0 => M0, N0, N1, N2, N5 5
TS1 => M0, M1, M3, N0 4
TS2 => M0, M2, N0, N1, N3 5
TS3 => M0, M1, M3, M4, N0, N2 6
TS4 => M0, M4, N0, N1, N3, N4 6
TS5 => M0, M1, M2, M5, N0, N4 6
Applying policy (1), options 2, 4, and 6 have the smallest maximum number of data blocks (i.e., 6 data blocks) sent during any time slot. Applying policy (2), the optimal delivery matrix in this exemplary embodiment is option 4 because option 4 has the smallest sum of data blocks of any reference time slot plus data blocks of neighboring time slots (i.e., 16 data blocks). Thus, optimally for this embodiment, the sending sequence of the data file N should be shifted by three time slots. In an exemplary embodiment, a three-dimensional delivery matrix is generated for each channel server 104. When data blocks for each data file are sent in accordance with a delivery matrix, a large number of subscribing clients can access the data file at a random time and the appropriate data blocks of the data file will be timely available to each subscribing client. In the example provided above, assume the duration of a time slot is equal to 5 seconds, the DOD system 100 sends data blocks for data files M and N in accordance with the optimal delivery matrix (i.e., shift delivery sequence of data file N by three time slots) in the following manner:
Time 00:00:00 => M0 N0 N1 N3 N4
Time 00:00:05 => M0 M1 M3 N0 N4
Time 00:00:10 => M0 M2 N0 N1 N2 N5
Time 00:00:15 => M0 M1 M3 M4 N0
Time 00:00:20 => M0 M4 N0 N1 N3
Time 00:00:25 => M0 M1 M2 M5 N0 N2
Time 00:00:30 => M0 N0 N1 N3 N4
Time 00:00:35 => M0 M1 M3 N0 N4
Time 00:00:40 => M0 M2 N0 N1 N2 N5
Time 00:00:45 => M0 M1 M3 M4 N0
Time 00:00:50 => M0 M4 N0 N1 N3
Time 00:00:55 => M0 M1 M2 M5 N0 N2
If at time 00:00:00 a client A selects movie M, the STB 300 at client A receives, stores, plays, and rejects data blocks as follows:
Time 00:00:00 => Receive M0 => play M0, store M0.
Time 00:00:05 => Receive M1, M3 => play M1, store M0, M1, M3.
Time 00:00:10 => Receive M2 => play M2, store M0, M1, M2 M3.
Time 00:00:15 => Receive M4 => play M3, store M0, M1, M2, M3, M4.
Time 00:00:20 => Receive none => play M4, store M0, M1, M2, M3, M4.
Time 00:00:25 => Receive M5 => play M5, store M0, M1, M2, M3, M4,
M5.
If at time 00:00: 10, a client B selects movie M, the STB 300 at client B receives, stores, plays, and rejects data blocks as follows:
Time 00:00:10 => Rcv M0, M2 => play M0, store M0, M2.
Time 00:00:15 => Rcv M1, M3, M4 => play M1, store M0, M1, M2, M3, M4.
Time 00:00:20 => Rcv none => play M2, store M0, M1, M2, M3, M4.
Time 00:00:25 => Rcv M5 => play M3, store M0, M1, M2, M3, M4,
M5.
Time 00:00:30 => Rcv none => play M4, store M0, M1, M2, M3, M4,
M5.
Time 00:00:35 => Rcv none => play M5, store M0, M1, M2, M3, M4,
M5.
If at time 00:00: 15, a client C selects movie N, the STB 300 of the client C receives, stores, plays, and rejects data blocks as follows:
Time 00:00:15 => Rcv N0 => play N0, store N0.
Time 00:00:20 -> Rcv N1 N3 -> play N1, store N0, N1, N3.
Time 00:00:25 => Rcv N2 => play N2, store N0, N1, N2, N3.
Time 00:00:30 => Rcv N4 => play N3, store N0, N1, N2, N3, N4.
Time 00:00:35 => Rcv none => play N4, store N0, N1, N2, N3, N4.
Time 00:00:40 => Rcv N5 => play N5, store N0, N1, N2, N3, N4,
N5.
If at time 00:00:30, a client D also selects movie N, the STB 300 at the client D receives, stores, plays, and rejects data blocks as follows:
Time 00:00:30 => Rcv N0, N1, N3, N4 => play N0, store N0, N1, N3, N4.
Time 00:00:35 => Rcv none => play N1, store N0, N1, N3, N4.
Time 00:00:40 =22 Rcv N2, N5 => play N2, store N0, N1, N2, N3, N4,
N5.
Time 00:00:45 => Rcv none => play N3, store N0, N1, N2, N3, N4,
N5.
Time 00:00:50 => Rcv none => play N4, store N0, N1, N2, N3, N4,
N5.
Time 00:00:55 => Rcv none -> play N5, store N0, N1, N2, N3, N4,
N5.
As shown in the above examples, any combination of clients can at a random time independently select and begin playing any data file provided by the service provider. General Operation A service provider can schedule to send a number of data files (e.g., video files) to channel servers 104 prior to broadcasting. The central controlling server 102 calculates and sends to the channel servers 104 three-dimensional delivery matrices (ID, time slot, and data block send order). During broadcasting, channel servers 104 consult the three-dimensional delivery matrices to send appropriate data blocks in an appropriate order. Each data file is divided into data blocks so that a large number of subscribing clients can separately begin viewing a data file continuously and sequentially at a random time. The size of a data block of a data file is dependent on the duration of a selected time slot and the bit rate of the data stream of the data file. For example, in a constant bit rate MPEG data stream, each data block has a fixed size of: Block Size (MBytes)=BitRate (Mb/s).times.TS (sec)/8 (1). In an exemplary embodiment, a data block size is adjusted to a next higher multiple of a memory cluster size in the local memory 208 of a channel server 104. For example, if a calculated data block length is 720 Kbytes according to equation (1) above, then the resulting data block length should be 768 KBytes if the cluster size of the local memory 208 is 64 KBytes. In this embodiment, data blocks should be further divided into multiples of sub-blocks each having the same size as the cluster size. In this example, the data block has twelve sub-blocks of 64 KBytes. A sub-block can be further broken down into data packets. Each data packet contains a packet header and packet data. The packet data length depends on the maximum transfer unit (MTU) of a physical layer where each channel server's CPU sends data to. In the preferred embodiment, the total size of the packet header and packet data should be less than the MTU. However, for maximum efficiency, the packet data length should be as long as possible. In an exemplary embodiment, data in a packet header contains information that permits the subscriber client's STB 300 to decode any received data and determine if the data packet belongs to a selected data file (e.g., protocol signature, version, ID, or packet type information). The packet header may also contain other information, such as block/sub-block/packet number, packet length, cyclic redundancy check (CRC) and offset in a sub-block, and/or encoding information. Once received by a channel server 104, data packets are sent to the QAM modulator 206 where another header is added to the data packet to generate a QAM-modulated IF output signal. The maximum bit rate output for the QAM modulator 206 is dependent on available bandwidth. For example, for a QAM modulator 206 with 6 MHz bandwidth, the maximum bit rate is 5.05 (bit/symbol).times.6 (MHz)=30.3 Mbit/sec. The QAM-modulated IF signals are sent to the up-converters 106 to be converted to RF signals suitable for a specific channel (e.g., for CATV channel 80, 559.250 MHz and 6 MHz bandwidth). For example, if a cable network has high bandwidth (or bit rate), each channel can be used to provide more than one data stream, with each data stream occupying a virtual sub-channel. For example, three MPEG1 data streams can fit into a 6 MHz channel using QAM modulation. The output of the up-converters 106 is applied to the combiner/amplifier 108, which sends the combined signal to the transmission medium 110. In an exemplary embodiment, the total system bandwidth (BW) for transmitting "N" data streams is BW=N.times.bw, where bw is the required bandwidth per data stream. For example, three MPEG-1 data streams can be transmitted at the same time by a DOCSIS cable channel having a system bandwidth of 30.3 Mbits/sec because each MPEG-1 data stream occupies 9 Mbits/sec of the system bandwidth. Typically, bandwidth is consumed regardless of the number of subscribing clients actually accessing the DOD service. Thus, even if no subscribing client is using the DOD service, bandwidth is still consumed to ensure the on-demand capability of the system. In an exemplary embodiment, the total system bandwidth (BW) may be reduced by prefetching some data blocks of each data file. Prefetch data blocks are continuously sent in a separate, dedicated channel. In one embodiment, the prefetch data blocks for a data file are sent sequentially in a group. By sending prefetch data blocks, the total system bandwidth (BW) needed for delivering the remaining data blocks is reduced. After determining a desirable number of prefetch data blocks to be sent in a separate channel, the schedule for sending the remaining data blocks should be adjusted so that the prefetch data blocks are not sent again with other data blocks. For example, in the exemplary schedule matrix above, where a data file is divided into six data blocks, if the first data block "b0" and the second data block "b1" are both prefetch data blocks, the schedule matrix should be modified to be as follows for the remaining data blocks (b2-b5):
TS0 => [nothing]
TS1 => blk3
TS2 => blk2
TS3 => blk3, blk4
TS4 => blk4
TS5 => blk2, blk5
In the above example, if b0 is the only prefetch data block, the total bandwidth for sending the remaining data blocks (b1-b5) of the data file is reduced by 37.5% [i.e., six data blocks removed from a total of sixteen data blocks]. Next, if data block "b1" is also a prefetch data block, the bandwidth for sending the remaining data blocks (b2-b5) is reduced by an additional 12.5%. Thus, the incremental bandwidth reduction for prefetching b1 is not as great as prefetching b0. Because the incremental bandwidth reduction diminishes as more data blocks are prefetched, an optimal number of prefetch data blocks for each data file can be determined based on a desired bandwidth reduction. In an exemplary embodiment, the bandwidth saved by prefetching data blocks x to y of a data file can be estimated by the following equation: .SIGMA.(1/n);n=(x+1) to (y+1) In addition, as the number of prefetch data blocks increases, the prefetch delay time increases. The prefetech delay time is determined based on the size of a data block for each data file, the number of prefetch data blocks per data file, the number of data files being sent, and the allocated prefetch bandwidth in the dedicated channel. In an exemplary embodiment, all prefetch data blocks for each file are sent sequentially and continuously in the dedicated channel, one data block per time slot. A person skilled in the art would recognize that as the number of prefetch data blocks increases, the longer the prefetch delay time. Thus, when determining an optimal number of prefetch data blocks for each data file, an acceptable prefetch delay time should be considered. For example, if data blocks b0 and b1 of data files M and N are to be prefetched in the dedicated channel, these prefetch data blocks can be sent in the following manner: M0 M1 N0 N1 M0 M1 N0 N1 . . . Assuming a given allocated prefetch bandwidth of PRF_BW (Mb/s), in an exemplary embodiment, a prefetch delay time can be calculated as follows: Prefetch delay time=[data block size (Mbytes)*number of prefetch data blocks*(number of data files to be sent+1)*8]/PRF_BW (Mb/s) In an exemplary embodiment, a prefetch cycle time (PRF_TIME), which is the time required to send a complete round of prefetched data blocks for all data files being sent, can be calculated as follows: Prefetch cycle time=[data block size (Mbytes)*number of prefetch data blocks*number of data files to be sent*8 ]/PRF_BW (Mb/s). In one embodiment, to reduce the prefetch delay time, prefetch data blocks of a new data file are sent more frequently than prefetch data blocks in an old data file (e.g., a data file that has been sent continuously for a predetermined amount of time). Fox example, if M is an old data file and N is a new data file, the prefetch data blocks are sent in the following manner: N0 N1 N0 N1 M0 M1 N0 N1 N0 N1 M0 M1 . . . The STB 300, once turned on, continuously receives and updates a program guide stored in the local memory 308 of a STB 300. In an exemplary embodiment, the STB 300 displays data file information including the latest program guide on a TV screen. Data file information, such as video file information, may include movieID, movie title, description (in multiple languages), category (e.g., action, children), rating (e.g., R, PG13), cable company policy (e.g., price, length of free preview), subscription period, movie poster, and movie preview. In an exemplary embodiment, data file information is sent via the dedicated channel, such as a channel reserved for firmware update, commercials, and/or emergency information. In another exemplary embodiment, information is sent in a physical channel shared by other data streams. In an exemplary embodiment, while the STB 300 is not playing any data file, the STB 300 is tuned into the dedicated channel and is ready to receive and update prefetch data blocks that have not yet been received. In an exemplary embodiment, previews are comprised of randomly selected data blocks in a data stream of a data file. Thus, a user who selects a preview of a data file multiple times is unlikely to view an identical preview. An advantage of randomly composed previews is that the DOD system 100 does not need extra bandwidth to broadcast a predetermined preview program. Instead, the DOD system 100 randomly selects data blocks in the normal data stream of a data file after a user requests to view a preview of that data file. In a preferred embodiment, some data blocks cannot become a part of any preview. For example, if a data file provides a movie, the data blocks of the second half of the movie should not become a part of a randomly selected preview. A subscribing client can view a list of available data files arranged by categories displayed on a television screen. When the client selects one of the available data files, the STB 300 controls its hardware to tune into a corresponding physical channel and/or a virtual sub-channel to start receiving data packets for that data file. The STB 300 examines every data packet header, decodes data in the data packets, and determines if a received data packet should be retained. If the STB 300 determines that a data packet should not be retained, the data packet is discarded. Otherwise, the packet data is saved in the local memory 308 for later retrieval or is temporarily stored in the buffer memory 309 until it is sent to the decoder 312. To improve performance efficiency by avoiding frequent read/write into the local memory 308, in an exemplary embodiment, the STB 300 uses a "sliding window" anticipation technique to lock anticipated data blocks in the memory buffer 309 whenever possible. Data blocks are transferred to the decoder 312 directly out of the memory buffer 309 if a hit in an anticipation window occurs. If an anticipation miss occurs, data blocks are read from the local memory 308 into the memory buffer 309 before the data blocks are transferred to the decoder 312 from the memory buffer 309. In an exemplary embodiment, the STB 300 responds to subscribing client's commands via infrared (IR) remote control unit buttons, an IR keyboard, or front panel pushbuttons, including buttons to pause, play in slow motion, rewind, zoom and single step. In an exemplary embodiment, if a subscribing client does not input any action for a predetermined period of time (e.g., scrolling program menu, or selecting a category or movie), a scheduled commercial is played automatically. The scheduled commercial is automatically stopped when the subscribing client provides an action (e.g., press a button in a remote control unit). In another exemplary embodiment, the STB 300 can automatically insert commercials while a video is being played. The service provider (e.g., a cable company) can set up a pricing policy that dictates how frequently commercials should interrupt the video being played. In an exemplary embodiment, a cable company using the DOD system 100 can preset a price list based on the number of commercial interruptions. In one embodiment, data blocks for commercials are continuously broadcasted via a dedicated channel which also broadcasts a program guide, an emergency bit, and any firmware update. A user can choose from such a price list an acceptable balance between price and commercials. In an exemplary embodiment, the DOD system 100 implements the user's selection by maintaining an internal clock which allows automatic insertion of commercial data blocks at the predetermined time intervals based on the user's selected pricing scheme. If an emergency information bit is found in a data packet header, the STB 300 pauses any data receiving operation and controls its hardware to tune into the channel reserved for receiving data file information to obtain and decode any emergency information to be displayed on an output screen. In an exemplary embodiment, when the STB 300 is idled, it is tuned to the channel reserved for receiving data file information and is always ready to receive and display any emergency information without delay. In one embodiment, when the STB 300 appears to be idle (e.g., when a user is not using the system), an alarm may go off to alert a user to turn on the output device to view the emergency information. In another embodiment, the STB 300 is capable of distinguishing emergency information for different regions. For example, the emergency information for an unrelated region will not interrupt a data file being played or trigger an alarm. In contrast, in existing systems, cable companies have to manually interrupt a broadcast to send emergency information. The foregoing examples illustrate certain exemplary embodiments of the invention from which other embodiments, variations, and modifications will be apparent to those skilled in the art. The invention should therefore not be limited to the particular embodiments discussed above, but rather is defined by the following claims. Appendix A Systems and Methods for Providing Video-On-Demand Services for Broadcasting Systems The following is a step-by-step description of the exemplary process illustrated in FIG. 4 for generating a scheduling matrix for a data file having six data blocks: START (Step 402) Receive a number of data blocks for a data file (x); assume the number of data blocks is equal to 6 (x=6). (Step 404) Set j=0 (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (0<6), let i=0 (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [0] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk0? (Step 422) RA does not contain anything because it is empty. Write blk0 into position [0, 0] in SM and the RA. (Step 424) Add 1 to i (i=1) to derive value for position [1, 0]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [1] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk1? (Step 422) RA does not contain blk1. Write blk1 into position [1, 0] in SM and the RA. (Step 424) Add 1 to i (i=2) to derive value for position [2, 0]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [2] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk2? (Step 422) RA does not contain blk2. Write blk2 into position [2, 0] in SM and the RA. (Step 424) Add 1 to i (i=3) to derive value for position [3, 0]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [3] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk3? (Step 422) RA does not contain blk3. Write blk3 into position [3, 0] in SM and the RA. (Step 424) Add 1 to i (i=4) to derive value for position [4, 0]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [4] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk4? (Step 422) RA does not contain blk4. Write blk4 into position [4, 0] in SM and the RA. (Step 424) Add 1 to i (i=5) to derive value for position [5, 0]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [5] in the SM and write to RA; initially, the SM is empty so nothing is written into RA. (Step 420) Does RA contain data block i or blk5? (Step 422) RA does not contain blk5. Write blk5 into position [5, 0] in SM and the RA. (Step 424) Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (j=1). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (1<6), let i=0. (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [1] in the SM and write to RA. Position [1, 0] contains blk1; thus, blk1 is written into RA. All other positions are empty. (Step 420) Does RA contain data block i or blk0? (Step 422) RA does not contain blk0. Write blk0 into position [1, 1] in the SM and the RA. RA now has blk1 and blk0. (Step 424) Add 1 to i (i=1) to derive value for position (2, 1]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [2] in the SM and write to RA. Position [2, 0] contains blk2. All other positions are empty. RA now has blk1, blk0, and blk2. (Step 420) Does RA contain data block i or blk1? (Step 424) RA contains blk1. Thus, nothing is written into position [2, 1]. Add 1 to i (i=2) to derive value for position [3, 1]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [3] in the SM and write to RA. Position [3, 0] contains blk3. All other positions are empty. RA now has blk1, blk0, blk2, and blk3. (Step 420) Does RA contain data block i or blk2? (Step 424) RA does contain blk2. Thus, nothing is written into position [3, 1]. Add 1 to i (i=3) to derive value for position [4, 1]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [4] in the SM and write to RA. Position [4, 0] contains blk4. All other positions are empty. RA now has blk1, blk0, blk2, blk3, and blk4. (Step 420) Does RA contain data block i or blk3? (Step 424) RA does contain blk3. Thus, nothing is written into position [4, 1]. Add 1 to i (i=4) to derive value for position [5, 1]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [5] in the SM and write to RA. Position [5, 0] contains blk5. All other positions are empty. RA now has blk1, blk0, blk2, blk3, blk4, and blk5. (Step 420) Does RA contain data block i or blk4? (Step 424) RA does contain blk4. Thus, nothing is written into position [5, 1]. Add 1 to i (i=5) to derive value for position [0, 1]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [0] in the SM and write to RA. Position [0, 0] contains blk0. All other positions are empty. RA already contains blk0; thus, blk0 is discarded. (Step 420) Does RA contain data block i or blk5? (Step 424) RA does contain blk5. Thus, nothing is written into position [0, 1]. Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (=2). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (2<6), let i=0. (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [2] in the SM and write to RA. Position [2, 0] contains blk2. All other positions are empty. RA now has blk2. (Step 420) Does RA contain data block i or blk0? (Step 422) RA does not contain blk0. Write blk0 into position [2, 2] in the SM and the RA. RA now has blk2 and blk0. (Step 424) Add 1 to i (i=1) to derive value for position [3, 2]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [3] in the SM and write to RA. Position [3, 0] contains blk3. All other positions are empty. RA now has blk2, blk0, and blk3. (Step 420) Does RA contain data block i or blk1? (Step 422) RA does not contain blk1. Write blk1 into position [3, 2] in the SM and the RA. RA now has blk2, blk0, blk3, and blk1. (Step 424) Add 1 to i (i=2) to derive value for position [4, 2]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [4] in the SM and write to RA. Position [4, 0] contains blk4. All other positions are empty. RA now has blk2, blk0, blk3, blk1, and blk4. (Step 420) Does RA contain data block i or blk2? (Step 424) RA does contain blk2. Thus, nothing is written into position [4, 2]. Add 1 to i (i=3) to derive value for position [5, 2]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [5] in the SM and write to RA. Position [5, 0] contains blk5. All other positions are empty. RA now has blk2, blk0, blk3, blk1, blk4, and blk5. (Step 420) Does RA contain data block i or blk3? (Step 424) RA does contain blk3. Thus, nothing is written into position [5, 2]. Add 1 to i (i=4) to derive value for position [0, 2]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [0] in the SM and write to RA. Position [0, 0] contains blk0. All other positions are empty. RA already contain blk0; thus blk0 is discarded. (Step 420) Does RA contain data block i or blk4? (Step 424) RA does contain blk4. Thus, nothing is written into position [0, 2]. Add 1 to i (i=5) to derive value for position [1, 2]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [1] in the SM and write to RA. Position [1, 0] contains blk1 and position [1, 1] contains blk0. RA already contains blk1 and blk0; thus blk1 and blk0 are discarded. All other positions are empty. (Step 420) Does RA contain data block i or blk5? (Step 424) RA does contain blk5. Thus, nothing is written into position [1, 2]. Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (j=3). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (3<6), let i=0. (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [3] in the SM and write to RA. Position [3, 0] contains blk3 and position [3, 2] contains blk1. Blk3 and blk1 are written into RA. All other positions are empty. (Step 420) Does RA contain data block i or blk0? (Step 422) RA does not contain blk0. Write blk0 into position [3, 3] in the SM and the RA. RA now has blk3, blk1 and blk0. (Step 424) Add 1 to i (i=1 ) to derive value for position (4, 3]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [4] in the SM and write to RA. Position [4, 0] contains blk4. All other positions are empty. RA now has blk3, blk1, blk0 and blk4. (Step 420) Does RA contain data block i or blk1? (Step 424) RA does contain blk1. Thus, nothing is written into position [4, 3]. Add 1 to i (i=2) to derive value for position (5, 3]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [5] in the SM and write to RA. Position [5, 0] contains blk5. All other positions are empty. RA now has blk3, blk1, blk0, blk4, and blk5. (Step 420) Does RA contain data block i or blk2? (Step 422) RA does not contain blk2. Write blk2 into position [5, 3] in the SM and the RA. RA now has blk3, blk1, blk0, blk4, blk5, and blk2. (Step 424) Add 1 to i (i=3) to derive value for position (0, 3]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [0] in the SM and write to RA. Position [0, 0] contains blk0. All other positions are empty. RA already contains blk0; thus, discard blk0. (Step 420) Does RA contain data block i or blk3? (Step 424) RA does contain blk3. Thus, nothing is written into position [0, 3]. Add 1 to i (i=4) to derive value for position (1, 3]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [1] in the SM and write to RA. Position [1, 0] contains blk1 and position [1, 1] contains blk0. All other positions are empty. RA already contains blk1 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk4? (Step 424) RA does contain blk4. Thus, nothing is written into position [1, 3]. Add 1 to i (i=5) to derive value for position [2, 3]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [2] in the SM and write to RA. Position [2, 0] contains blk2 and position [2, 2] contains blk0. All other positions are empty. RA already contains blk2 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk5? (Step 424) RA does contain blk5. Thus, nothing is written into position [2, 3]. Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (=4). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (4<6), let i=0. (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [4] in the SM and write to RA. Position [4, 0] contains blk4. Blk4 is written into RA. All other positions are empty. (Step 420) Does RA contain data block i or blk0? (Step 422) RA does not contain blk0. Write blk0 into position [4, 4] in the SM and the RA. RA now has blk4 and blk0. (Step 424) Add 1 to i (i=1) to derive value for position [5, 4]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [5] in the SM and write to RA. Position [5, 0] contains blk5 and position [5, 3] contains blk2. All other positions are empty. RA now has blk4, blk0, blk5, and blk2. (Step 420) Does RA contain data block i or blk1? (Step 422) RA does not contain blk1. Write blk1 into position [5, 4] of the SM and the RA. RA now has blk4, blk0, blk5, blk2, and blk1. (Step 424) Add 1 to i (i=2) to derive value for position [0, 4]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [0] in the SM and write to RA. Position [0, 0] contains blk0. All other positions are empty. RA already contains blk0; thus, do not write a duplicate copy. (Step 420) Does RA contain data block i or blk2? (Step 424) RA does contain blk2. Add 1 to i (i=3) to derive value for position [1,4]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [1] in the SM and write to RA. Position [1, 0] contains blk1 and position [1, 1]. All other positions are empty. RA already contains blk1 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk3? (Step 422) RA does not contain blk3. Write blk3 into position [1, 4] of the SM and the RA. RA now has blk4, blk0, blk5, blk2, blk1, and blk3. (Step 424) Add 1 to i (i=4) to derive value for position [2, 4]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [2] in the SM and write to RA. Position [2, 0] contains blk2 and position [2, 2] contains blk0. All other positions are empty. RA already contains blk2 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk4? (Step 424) RA does contain blk4. Thus, nothing is written into position [2, 4]. Add 1 to i (i=5) to derive value for position [3, 4]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [3] in the SM and write to RA. Position [3, 0] contains blk3, position [3, 2] contains blk1, and position [3, 3] contains blk0. All other positions are empty. RA already contains blk3, blk1, and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk5? (Step 424) RA does contain blk5. Thus, nothing is written into position [3, 4]. Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (j=5). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 412) j is less than x (5<6), let i=0. (Step 414) Compare i to x. (Step 418) i is less than x (0<6). Read matrix positions of column [5] in the SM and write to RA. Position [5, 0] contains blk5, position [5, 3] contains blk2, and position [5, 4] contains blk1. Blk5, blk2, and blk1 are written into RA. All other positions are empty. (Step 420) DoesRA contain data block i or blk0? (Step 422) RA does not contain blk0. Write blk0 into position [5, 5] in the SM and the RA. RA now has blk5, blk2, blk1, and blk0. (Step 424) Add 1 to i (i=1) to derive value for position [0, 5]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (1<6). Read matrix positions of column [0] in the SM and write to RA. Position [0,0 ] contains blk0 and all other positions are empty. RA now has blk5, blk2, blk1, and blk0 (Step 420) Does RA contain data block i or blk1? (Step 424) RA does contain blk1. Add 1 to i (i=2) to derive value for position (1, 5]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (2<6). Read matrix positions of column [1] in the SM and write to RA. Position [1, 0] contains blk1, position [1, 1] contains blk0, and position [1, 4] contains blk3. All other positions are empty. RA already contains blk0 and blk1; thus, do not write a duplicate copy. Write blk3 into RA. RA now has blk5, blk2, blk1, blk0, and blk3. (Step 420) Does RA contain data block i or blk2? (Step 424) RA does contain blk2. Add 1 to i (i=3) to derive value for position (2, 5]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (3<6). Read matrix positions of column [2] in the SM and write to RA. Position [2, 0] contains blk2 and position [2, 2] contains blk0. All other positions are empty. RA already contains blk2 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk3? (Step 424) RA does contain blk3. Add 1 to i (i=4) to derive value for position (3, 5]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (4<6). Read matrix positions of column [3] in the SM and write to RA. Position [3, 0] contains blk3, position [3, 2] contains blk1, position [3, 3] contains blk0. All other positions are empty. RA already contains blk3, blk1, and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk4? (Step 422) RA does not contain blk4. Write blk4 into position [3, 5] of the SM and the RA. The RA now has blk5, blk2, blk1, blk0, blk3, and blk4. (Step 424) Add 1 to i (i=5) to derive value for position [4, 5]. Go back to Step 414. (Step 414) Compare i to x. (Step 418) i is less than x (5<6). Read matrix positions of column [4] in the SM and write to RA. Position [4, 0] contains blk4 and position [4, 4] contains blk0. All other positions are empty. RA already contains blk4 and blk0; do not write a duplicate copy. (Step 420) Does RA contain data block i or blk5? (Step 424) RA does contain blk5. Thus, nothing is written into position [3, 4]. (Step 424) Add 1 to i (i=6). Go back to Step 414. (Step 414) Compare i to x. (Step 416) i is equal to x (6=6). Increment j by 1 (0=5). Go to Step 406. (Step 406) Clear a Reference Array (RA) (Step 408) Compare j to x. (Step 410) j is equal to x (6<6); END.
|
Same subclass Same class Consider this |
||||||||||