 |
Claims  |
|
|
We claim:
1. A multimedia server comprising:
an addressable memory media including a first addressable memory device and
a second addressable memory device where the first addressable memory
device has a latency of t.sub.lat1 and a data transfer rate r.sub.t, said
first addressable memory device being adapted for storing program
information in plurality of sequential data segments, where each of said
data segments is partitioned into n portions with each of said portions
having d bits of information such that each of said data segments contains
(n.multidot.d) bits;
the second addressable memory device having a data transfer rate of r.sub.t
and a latency of t.sub.lat2, said second addressable memory device being
adapted for storing program information of duration t.sub.lat1 in
plurality of sequential data segments, where each of said data segments
contains (n.multidot.d) bits and where t.sub.lat2 <<t.sub.lat1 such that
the stored information can be completely retrieved from the second
addressable memory device within a time period that is less than
t.sub.lat1 and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a
communication network, wherein each of said buffer memories receives d
bits of program information from a particular one of said sequential data
segments at a rate r.sub.t from said addressable memory media, stores said
received d bits of information, and then transfers said stored d bits of
information to said communication network at a rate r.sub.d, while
simultaneously receiving, at a rate r.sub.t, from said addressable memory
media, another d bits of program information associated with said
particular one of said sequential data segments.
2. The multimedia server of claim 1 wherein said first addressable memory
device comprises a magnetic disk, and wherein said second addressable
memory device comprises a random access semiconductor memory.
3. The multimedia server of claim 1 wherein said first addressable memory
device comprises an optical disk, and wherein said second addressable
memory device comprises a random access semiconductor memory.
4. The multimedia server of claim 1 wherein said communication network
comprises a public telecommunications network.
5. The multimedia server of claim 1 wherein said program information
comprises data representative of a video signal.
6. A multimedia server system comprising:
an addressable memory media including a first addressable memory device
having a latency of t.sub.lat1 and a data transfer rate of r.sub.t, said
first addressable memory device being adapted for storing program
information in plurality of sequential data segments, where each of said
data segments is partitioned into n portions with each of said portions
having d bits of information such that each of said data segments contains
(n.multidot.d) bits, and a second addressable memory device having a data
transfer rate of r.sub.t and a latency of t.sub.lat2, said second
addressable memory device being adapted for storing program information of
duration t.sub.lat1 in plurality of sequential data segments, where each
of said data segments contains (n.multidot.d) bits and where t.sub.lat2
<<t.sub.lat1 such that the stored information can be completely retrieved
from the second addressable memory device within a time period that is
less than t.sub.lat1 and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a switching
system, wherein each of said buffer memories receives d bits of program
information from a particular one of said sequential data segments at a
rate r.sub.t from said addressable memory media, stores said received d
bits of information, and then transfers said stored d bits of information
to said switching system at a rate r.sub.d, while simultaneously
receiving, at a rate r.sub.t, from said addressable memory media, another
d bits of program information associated with said particular one of said
sequential data segments, said switching system being adapted to
selectively connect one or more of said plurality of buffer memories with
at least one data interface that is adapted to receive and decode the
program information output by said plurality of buffer memories.
7. The multimedia server system of claim 6 wherein said first addressable
memory device comprises a magnetic disk, and wherein said second
addressable memory device comprises a random access semiconductor memory.
8. The multimedia server system of claim 6 wherein said first addressable
memory device comprises an optical disk, and wherein said second
addressable memory device comprises a random access semiconductor memory.
9. The multimedia server system of claim 6 wherein the connection between
said switching system and said data interface is effected via a public
telecommunications network.
10. The multimedia server system of claim 6 wherein said program
information comprises data representative of a video signal.
11. A multimedia server system comprising:
an addressable memory media including a first addressable memory device
having a latency of t.sub.lat1 and a data transfer rate of r.sub.t, said
first addressable memory device being adapted for storing program
information in plurality of sequential data segments, where each of said
data segments is partitioned into n portions with each of said portions
having d bits of information such that each of said data segments contains
(n.multidot.d) bits, and a second addressable memory device having a data
transfer rate of r.sub.t and a latency of t.sub.lat2, said second
addressable memory device being adapted for storing program information of
duration t.sub.lat1 in plurality of sequential data segments, where each
of said data segments contains (n.multidot.d) bits and where t.sub.lat2
<<t.sub.lat1 such that the stored information can be completely retrieved
from the second addressable memory, device within a time period that is
less than t.sub.lat1 and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a
programmable switching system, wherein each of said buffer memories
receives d bits of program information from a particular one of said
sequential data segments at a rate of r.sub.t from said addressable memory
media, stores said received d bits of information, and then transfers said
stored d bits of information to said programmable switching system at a
rate r.sub.d, while simultaneously receiving, at a rate r.sub.t from said
addressable memory media, another d bits of program information associated
with said particular one of said sequential data segments, said
programmable switching system being adapted to selectively connect one or
more of said plurality of buffer memories with at least one data interface
in response to viewer generated commands, said data interface being
adapted to receive and decode the program information output by said
plurality of buffer memories, and said data interface being further
adapted to receive said viewer generated commands and transmit said
commands to said programmable switching system.
12. The multimedia server system of claim 11 wherein said first addressable
memory device comprises a magnetic disk, and wherein said second
addressable memory device comprises a random access semiconductor memory.
13. The multimedia server system of claim 11 wherein said first addressable
memory device comprises an optical disk, and wherein said second
addressable memory device comprises a random access semiconductor memory.
14. The multimedia server system of claim 11 wherein the connection between
said programmable switching system and said data interface is effected via
a public telecommunications network.
15. The multimedia server system of claim 11 wherein said program
information comprises data representative of a video signal, and the
decoding of said program information by said data interface results in the
production of a video signal comprising at least one video frame.
16. The multimedia server system of claim 15 wherein, in response to a
particular viewer generated command, said programmable switching system
facilitates the sequential transmission of the data segments from each of
the buffer memories to said data interface, so that said sequentially
transmitted data segments, when decoded, provide a continuous
representation of the video signal program information stored within said
addressable memory media.
17. The multimedia server system of claim 15 wherein, in response to a
particular viewer generated command, the data interface repetitively
produces a video signal representing a single video frame.
18. The multimedia server system of claim 15 wherein, in response to
particular viewer generated commands, said programmable switching system
facilitates the transmission of data representing non-contiguous sequences
of video frames from at least one of said buffer memories to said data
interface, so that said transmitted data, when decoded, provides an
accelerated representation of the video signal program information stored
within said addressable memory media.
19. The multimedia server system of claim 15 wherein, in response to
particular viewer generated commands, said programmable switching system
facilitates the sequential transmission of data representing video frames
from at least a particular one of said buffer memories to said data
interface, which, when decoded, provides a continuous representation of a
specific portion the video signal program information stored within said
addressable memory media.
20. A multimedia server system comprising:
an addressable memory media including a magnetic disk having a latency of
t.sub.lat1 and a data transfer rate of r.sub.t, said magnetic disk being
adapted for storing information representative of a video signal in
plurality of sequential data segments, where each of said data segments is
partitioned into n portions with each portion having d bits such that each
of said data segments contains (n.multidot.d) bits, and a random access
semiconductor memory having a data transfer rate of r.sub.t and a latency
of t.sub.lat2, said random access semiconductor memory being adapted for
storing information representative of a video signal of duration
t.sub.lat1 in plurality of sequential data segments, where each of said
data segments contains (n.multidot.d) bits and where t.sub.lat2
<<t.sub.lat1 such that the stored information can be completely retrieved
from the second addressable memory device during a time period that is
less than t.sub.lat1 and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a
programmable switching system, wherein each of said buffer memories
receives d bits of information representative of a video signal from a
particular one of said sequential data segments at a rate of r.sub.t from
said addressable memory media, stores said received d bits of information,
and then transfers said stored d bits of information to said programmable
switching system at a rate r.sub.d, while simultaneously receiving, at a
rate r.sub.t from said addressable memory media, another d bits of
information associated with said particular one of said sequential data
segments, said programmable switching system being adapted to selectively
connect one or more of said plurality of buffer memories with at least one
data interface in response to viewer commands, said data interface being
adapted to receive and decode the program information output by said
plurality of buffer memories, and said data interface being further
adapted to receive said viewer commands and transmit said viewer commands
to said programmable switching system.
21. The multimedia server system of claim 20 further comprising a second
random access semiconductor memory containing data representing a
high-speed version of the data stored within said addressable memory
media, said second random access semiconductor memory being linked to said
programmable switching system, and configured to provide said high-speed
version data to said data interface in response to said viewer commands.
22. The multimedia server system of claim 21 wherein said information
stored upon said addressable memory media consists of data representing
intra, bi-directional and predicted video frames, and said information is
encoded so that the data representing any two consecutive intra video
frames is separated by data representing (2k+1) groupings of three video
frames, where k is a positive integer and each grouping of three video
frames consists of a pair of bi-directional video frames followed by a
predicted video frame.
23. The multimedia server system of claim 22 wherein the information stored
upon said second random access semiconductor memory consists of data
representing intra, bi-directional and predicted video frames, and said
information is encoded so that the data representing any two consecutive
intra video frames is separated by data representing a single grouping of
three video frames consisting of a pair of bi-directional video frames
followed by a predicted video frame.
24. The multimedia server system of claim 20 further comprising a
high-speed video data buffer adapted for collecting and storing a
high-speed version of the data stored within said addressable memory
media, said high-speed video data buffer being linked to said programmable
switching system, and configured to provide said high-speed version data
to said data interface in response to said viewer commands.
25. The multimedia server system of claim 23 wherein said information
stored upon said addressable memory media consists of data representing
intra, bi-directional and predicted video frames, and said information is
encoded so that the data representing any two consecutive intra video
frames is separated by data representing (2k+1) groupings of three video
frames, where k is a positive integer and each grouping of three video
frames consists of a pair of bi-directional video frames followed by a
predicted video frame.
26. The multimedia server system of claim 25 wherein the information stored
upon said high-speed video data buffer consists of data representing
intra, bi-directional and predicted video frames, and said information is
encoded so that the data representing any two consecutive intra video
frames is separated by data representing a single grouping of three video
frames consisting of a pair of bi-directional video frames followed by a
predicted video frame.
27. In a multimedia server system comprising:
an addressable memory media including a first addressable memory device
having a latency of t.sub.lat1 and a data transfer rate of r.sub.t, said
first addressable memory device being adapted for storing program
information in plurality of sequential data segments, where each of said
data segments contains (n.multidot.d) bits;
a second addressable memory device having a data transfer rate of r.sub.t
and a latency of t.sub.lat2, said second addressable memory device being
adapted for storing program information of duration t.sub.lat1 in
plurality of sequential data segments, where t.sub.lat2 <<t.sub.lat1 such
that the stored information can be completely retrieved from the second
addressable memory during a time period that is less than t.sub.lat1 and
where each of said data segments is partitioned into n portions with each
portion having d bits of information such that each of said data segments
contains (n.multidot.d) bits; and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a
programmable switching system, wherein each of said buffer memories
receives d bits of program information from a particular one of said
sequential data segments at a rate of r.sub.t from said addressable memory
media, stores said received d bits of information, and then transfers said
stored d bits of information to said programmable switching system at a
rate r.sub.d, while simultaneously receiving, at a rate r.sub.t form said
addressable memory media, another d bits of programming information
associated with said particular one of said sequential data segments, said
programmable switching system being adapted to selectively connect one or
more of said plurality of buffer memories with at least one requesting
viewer in response to viewer generated commands;
a method for retrieving multimedia information, comprising the steps of:
receiving a viewer generated command requesting particular information
stored within said addressable memory means;
establishing a connection between at least one of said buffer memories and
said requesting viewer in response to said received viewer generated
command, and
transmitting to said requesting viewer at least one data segment associated
with said requested information via a particular one of said buffer
memories and said programmable switching system.
28. The method of claim 27 wherein said first addressable memory device
comprises a magnetic disk, and wherein said second addressable memory
device comprises a random access semiconductor memory.
29. The method of claim 27 wherein said first addressable memory device
comprises an optical disk, and wherein said second addressable memory
device comprises a random access semiconductor memory.
30. The method of claim 27 wherein the connection between said programmable
switching system and said requesting viewer is established via a public
telecommunications network.
31. The method of claim 27 wherein said program information comprises data
representative of a video signal, and decoding said program information
results in the production of a video signal comprising at least one video
frame.
32. The method of claim 31 wherein further comprising the step of effecting
sequential connections to a plurality of said buffer memories via said
programmable switching system in response to a received viewer generated
command, and thereby provide said requesting viewer with a continuous
representation of the video signal program information stored within said
addressable memory media.
33. The method of claim 31 further comprising the step of repetitively
providing said requesting viewer with data representing a single frame of
video in response to a received viewer generated command.
34. The method of claim 31 further comprising the step of transmitting, via
said programmable switching system, data representing non-contiguous
sequences of video frames from at least one of said buffer memories to
said requesting viewer in response to a received viewer generated command,
so that said transmitted data, when decoded, provides an accelerated
representation of the video signal program information stored within said
addressable memory media.
35. The method of claim 31 further comprising the step of transmitting, via
said programmable switching system, data representing video frames from at
least a particular one of said buffer memories to said requesting viewer
in response to a received viewer generated command, wherein said
transmitted data provides a continuous representation of a specific
portion the video signal program information stored within said
addressable memory media.
36. In a multimedia server system comprising:
an addressable memory media including a magnetic disk having a latency of
t.sub.lat1 and a data transfer rate of r.sub.t, said magnetic disk being
adapted for storing information representative of a video signal in
plurality of sequential data segments, where each of said data segments is
partitioned into n portions with each portion having d bits of information
such that each of said data segments contains (n.multidot.d) bits, and a
random access semiconductor memory having a data transfer rate of r.sub.t
and a latency t.sub.lat2, said random access semiconductor memory being
adapted for storing information representative of a video signal of
duration t.sub.lat1 in plurality of sequential data segments, where each
of said data segments contains (n.multidot.d) bits and where t.sub.lat2
<<t.sub.lat1, such that the stored information can be completely retrieved
from the second addressable memory during a time period that is less than
t.sub.lat1 and
a plurality of buffer memories, each dedicated to continually relaying the
data contained within one of said sequential data segments to a
programmable switching system, wherein each of said buffer memories
receives d bits of program information from a particular one of said
sequential data segments at a rate of r.sub.t from said addressable memory
media, stores said received d bits of information, and then transfers said
stored d bits of information to said programmable switching system at a
rate r.sub.d, while simultaneously receiving, at a rate r.sub.t form said
addressable memory media, another d bits of programming information
associated with said particular one of said sequential data segments, said
programmable switching system being adapted to selectively connect one or
more of said plurality of buffer memories with at least one requesting
viewer in response to viewer generated commands;
a method for retrieving multimedia information, comprising the steps of:
receiving a viewer generated command requesting information representing a
particular video signal stored within said addressable memory means;
establishing a connection between at least one of said buffer memories and
said requesting viewer in response to said received viewer generated
command, and
transmitting to said requesting viewer at least one data segment associated
with said requested information via a particular one of said buffer
memories and said programmable switching system. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD
The invention relates to providing multiple-user access to a multimedia
database, and in particular, to on-demand access to such a database.
BACKGROUND OF THE INVENTION
The movie on demand ("MOD") concept has become exceedingly popular within
the telecommunications, computer and cable television industries. Viewers
that subscribe to a MOD service have access to a much wider range of
content than subscribers to ordinary broadcast-based television or cable
networks. MOD subscribers can, at any time they wish, view a movie that
they select from among a particular set of available movies. Furthermore,
while watching the selected movie, a MOD subscriber can typically control
the viewing via an interface that provides video tape player functions.
For example, a subscriber may pause and then resume viewing the movie, or
skip forward or backward within the movie (analogous to the fast-forward
and rewind functions of a video tape player). Thus, MOD systems differ
substantially from today's standard broadcast television and cable systems
in which, at any given time, all the viewers see the same portion of the
same movie, and viewers have no control over its transmission.
Until recently, relatively low telecommunication and cable network
bandwidths and limited-capacity video storage technologies made offering
MOD services to a significant number of viewers a difficult task. However,
present optical fiber networks have bandwidths of several gigabits/second.
Furthermore, not only is it now possible to store video data in digital
form, but it is also possible to obtain compression ratios that are as
high as forty to one. For example, a 30 frames/second video signal, can be
compressed to only 1.5 megabits/second by employing the Motion Picture
Experts Group algorithm ("MPEG compression") set forth by D. Gall in
Communications of the ACM, 34(4), pages 46-58, "MPEG: A video compression
standard for multimedia applications," April 1991. Thus, using present
networking technology, it is possible to concurrently transmit independent
video streams to thousands of viewers.
Although the problem of transmitting video data has been considerably
simplified by the availability of high bandwidth networks, the design and
implementation of a practical MOD storage server that enables the
simultaneous retrieval of different portions of different movies by
different subscribers remains a significant technological hurdle. A
storage architecture for a MOD server must facilitate the continuous
retrieval of movies, as well as provide video tape player-like functions,
and the ability to simultaneously service multiple subscribers. In
addition, the server must have a relatively low-cost.
Generally, a MOD server will include a cache for temporarily storing the
movies that are to be made available to subscribers. These movies will be
loaded onto the cache from a library that provides a permanent storage
location for the movies (e.g., an addressable collection of video tapes or
disks). In its basic configuration, the cache can consist of a large
random access memory ("RAM") having a flat architecture. However, this
approach will increase the cost of the MOD server substantially due to the
vast amounts of semiconductor RAM needed to store any given movie, and the
high cost of RAM. For example, an MPEG compressed 100 minute movie, having
an average bandwidth of 1.5 megabits/second, will require approximately
1.1 gigabytes of RAM storage. Assuming the cost of RAM is $50.00 per
megabyte, the cost of the RAM component alone for a single movie MOD
server would approach $55,000. This cost would rise to $5.5 million for a
RAM-based cache capable of storing 100 movies.
It is well known in the art to provide systems that facilitate the
continuous retrieval of video and audio data from a storage medium, such
as a disk, in response to multiple concurrent requests for the retrieval
of multimedia objects residing on a disk (see D. P. Anderson, Y Osawa, R.
Govidan, A file system for continuous media, ACM Transactions on Computer
Systems, 10(4), pages 311-337, November 1992; H. J. Chen, T. D. C. Little,
Physical storage organizations for time-dependent data, Foundations of
Data Organization and Algorithms, pages 19-34, Springer-Verlag, October
1993; P. V. Rangan, H. M. Vin, Efficient storage techniques for digital
continuous multimedia, IEEE Transactions on Knowledge and Data
Engineering, 5(4), pages 564-573, August 1993; P. V. Rangan, H. M. Vin, S.
Ramanathan, Designing an on-demand multimedia service, IEEE Communications
Magazine, 1(1), pages 56-64, July 1992; C. Yu, W. Sun, D. Bitton, Q. Yang,
R. Bruno, J. Tulis, Efficient placement of audio data on optical disks for
real-time applications, Communications of the ACM, 32(7), pages 862-871,
July 1989). However, under these schemes, concurrent requests are serviced
in a round-robin fashion retrieving successive portions of multimedia
objects and performing multiple seeks in each round. Thus, the schemes are
unsuitable for handling large number of requests concurrently.
SUMMARY OF THE INVENTION
The aforementioned problems are solved, in accordance with the principles
of the invention, by providing a multimedia on-demand server including a
randomly-accessible library of multimedia programs (such as movies stored
on magnetic or optical disks), a limited amount of RAM to buffer and store
selected portions of programs retrieved from the library, and an interface
that switchably routes program material from the library and RAM buffers
to an audience of viewers. The server employs a restricted retrieval
strategy and a novel storage allocation scheme that enable different
portions of one or more programs to be continuously retrieved and
selectively routed to a large number of on-demand viewers, while at the
same time minimizing the amount of the RAM required to effect this
service. The on-demand server also responds to viewer-generated commands
to control the viewing of a program. In a particular embodiment, these
commands include video tape player-like operations such as fast-forward,
rewind and pause.
BRIEF DESCRIPTION OF THE DRAWING
In the drawing:
FIG. 1 shows, in simplified block diagram form, the architecture of a
multimedia on-demand server incorporating an embodiment of the invention;
FIG. 2A is a depiction of a (p.multidot.1) partition of data representing a
movie retrieved from within program library 100 of FIG. 1;
FIG. 2B is a depiction of p-by-n matrix arrangement of data representing a
movie retrieved from within program library 100 of FIG. 1;
FIG. 3 is a depiction of the frame sequencing of the MPEG-encoded video
transmitted to viewers within the system of FIG. 1;
FIG. 4 shows, in simplified block diagram form, the architecture of a
multimedia on-demand server incorporating a dedicated RAM that stores a
high-speed version of a movie;
FIG. 5A shows, in simplified block diagram form, the architecture of a
multimedia on-demand server incorporating disks for storing high-speed
versions of a movie;
FIG. 5B is a depiction of p-by-n.sub.ff matrix arrangement of data
representing a movie retrieved from disk 503 of FIG. 5A; and
FIG. 6 shows, in simplified block diagram form, the architecture of a
multimedia on-demand server incorporating a circular buffer that stores a
high-speed version of a movie.
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 shows, in simplified form, the architecture of a multimedia
on-demand server incorporating an embodiment of the invention.
Specifically shown is multimedia program library 100, which includes
randomly-accessible magnetic disk labeled 101 and RAM 102, both of which
serve to store digital program information representing audio and video
signals that comprise a feature-length movie. For reasons that will become
evident, digital information representing a small portion of the beginning
of the movie is stored within RAM 102, and remainder of the movie
information is stored upon magnetic disk 101. This digital program
information is retrieved from RAM 102 and magnetic disk 101, and
transmitted along lines 103-107 to RAM buffers (108-112). The output of
each RAM buffer is linked to switch 113 via one of lines 114-118, and the
output of switch 113 may be selectively linked to individual viewers via
transmission lines 119 and telecommunication network 120. Switch 113 is a
programmable switch adapted to controllably direct the distribution and
transmission of multimedia signals among the various transmission lines in
response to commands from controller 121 (such programmable switches are
well known in the art). Only 20 transmission lines are shown exiting
switch 113; however, as indicated by the dots shown in FIG. 1,
transmission lines can be added to provide for an increased number of
viewers.
Telecommunication network 120 is connected to program decoder/viewer
interface ("decoder/interface") 122 via lines 123 and 124. As shown, line
123 serves to provide the viewer with program information, and line 124
serves to convey viewer generated information into the network. This
viewer generated information is then communicated to controller 121 via
line 125. Decoder/interface 122 is also linked to video display 126.
The rate, r.sub.d, at which program information is transmitted to network
120 (and therefore to viewers) from video switch 113 cannot exceed the
bandwidth of any given one of the transmission lines (collectively labeled
119). However, this transmission rate must be sufficiently high so as to
provide enough data to generate thirty frames of video per second (the
standard television rate). Within the system of FIG. 1, r.sub.d is 1.5
megabits/second (0.1875 megabytes/second)--a rate suitable for supporting
the transmission of thirty frames of MPEG compressed video per second. The
rate of retrieval, r.sub.t, of program information from magnetic disk 101
on the order of 20 megabytes/second, with a latency, t.sub.lat, (i.e., the
maximum time to access and read or write a random location upon the
magnetic disk), of 35 milliseconds. Magnetic disks having 10,000 megabyte
capacities, 20 megabyte/second retrieval rates, and maximum latencies of
35 milliseconds are commercially available (for example, the ST410800W
Elite 9 magnetic disk drive manufactured by Seagate Technology, Inc. of
Scotts Valley, Calif.). A storage capacity of approximately 10,000
megabytes enables program library 100 to store on the order of eight 100
minute movies compressed in the 1.5 megabits/second MPEG format.
Within the system illustrated in FIG. 1, an optimal program retrieval and
storage allocation scheme is employed to maximize the number of potential
on-demand program viewers, while keeping RAM buffer capacity requirements
to a minimum. In this scheme, the retrieval of program information (such
as a movie) initiated at a given time is referred to as a phase. For
example, if a first on-demand viewer initiated retrieval of a particular
movie from program library 100 at 1:00, another on-demand viewer initiated
retrieval of that same movie at 1:10, and yet another on-demand viewer
initiated retrieval of the movie at 1:15, each viewer would be receiving a
separate phase of the movie. Naturally, each viewer would receive the
particular phase via different transmission lines (collectively labeled
119), and via separate connections to network 123. The maximum number of
concurrent phases, p, which can be supported by the system of FIG. 1 is
given by:
##EQU1##
The amount of RAM buffer required to support each phase is kept to a
minimum by employing a restricted retrieval scheme, referred to as
phase-constrained allocation. This allocation scheme eliminates seeks to
random disk locations, and thereby enables the concurrent retrieval of p
phases, while allowing the size of the RAM buffer for each phase to be
kept constant--independent of the number of phases being retrieved and the
latency associated with disk 101.
In order to support p concurrent phases within the system of FIG. 1, the
movie data stored within program library 100 must be separated into p
contiguous partitions. If l is the length, in seconds, of a movie stored
within program library 100, then the movie occupies lr.sub.d bits. The
system of FIG. 1 is configured so that movie data is read from program
library 100 in d size portions, where d is arbitrarily chosen to be 50
kilobits. As will become evident, each buffer within the system of FIG. 1
must have a capacity of 2d, and 100 kilobit RAM buffers can be easily and
inexpensively obtained. Ideally, the length l of the movie is set so that
(l.multidot.r.sub.d) is a multiple of (p.multidot.d) to assure that it may
be retrieved in an integer number of d sized portions after it is
partitioned into p segments. Of course, any movie can be modified to
conform to this constraint by appending advertisements, previews or blank
frames to lengthen the movie, or by editing the movie to shorten it.
Each of these p data partitions can be visualized as a (p.multidot.1)
vector (see FIG. 2A), wherein each row within the vector contains t.sub.c
.multidot.r.sub.d bits of movie data, and where
##EQU2##
Assuming a 100.7 minute movie (an arbitrary length chosen because it is
divisible by (p.multidot.d)), the value of t.sub.c is computed as follows:
##EQU3##
Given such an arrangement, the smallest phase difference that the system
of FIG. 1 will support is equal to t.sub.c, because the first bit in any
two adjacent rows within the (p.multidot.1) vector will be t.sub.c seconds
apart.
Since movie data in each row is retrieved in portions of size d, a row can
be further viewed as consisting of n portions of size d, where:
##EQU4##
Thus, the movie can be represented as a (p.multidot.n) matrix of data as
shown in FIG. 2B. Each portion in the matrix can be uniquely identified by
the row and column to which it belongs.
The movie is sequentially stored within program library 100 in column-major
form. That is, all the data within the first column of FIG. 2B is stored
within program library 100, followed by all the data within the second
column of FIG. 2B, and the next column, until finally, the data within the
nth column has been stored. All of this movie data is stored upon disk
101, with the exception of the initial (t.sub.lat .multidot.r.sub.d) bits
of the column-major movie data. These initial bits must be stored within
RAM 102 to compensate for the inherent delay of repositioning the heads of
disk 101. RAM 102 need only have a capacity of (t.sub.lat
.multidot.r.sub.d) bits, which is only 52,500 bits for the system of FIG.
1. The necessity of this combination RAM/disk storage scheme is explained
below.
By sequentially reading the column-major form data from program library
100, movie data from rows 1 through p are retrieved at a rate r.sub.d. For
each of the p rows of the data matrix illustrated in FIG. 2B, there is a
dedicated line linking program library 100 and video switch 113.
Similarly, for each data matrix row there is a dedicated RAM buffer into
which consecutive portions of a row are stored and retrieved. For purposes
of illustration, only five lines linking program library 100 and video
switch 113, and only five RAM buffers (with their associated input and
output lines) are explicitly shown in FIG. 1. As indicated by the dots,
additional buffers and lines are provided to accommodate the p of columns
in the data matrix. As the data from each row is retrieved from disk it is
routed through the corresponding dedicated line to the corresponding
dedicated buffer.
Each of the RAM buffers (108-112) is implemented as a circular buffer. That
is, if while writing into a buffer, the last memory location within that
buffer is reached, then further bits are written at the beginning of the
RAM buffer. Similarly, while reading data, if the last memory location of
a buffer is read, then subsequent bits are read from the beginning of the
buffer. To support the above circular storage scheme, every t.sub.c /n
seconds, the next consecutive column of movie data is retrieved from disk
and stored in a RAM buffer. The size of each RAM buffer is fixed at a size
2d. For each column of data within the matrix of FIG. 2B, d bits of data
associated with a particular row are transmitted to viewers from a first
group of d memory sites within the RAM buffer dedicated to the data stored
in that particular row, while the d bits of data associated with that same
row, but the next consecutive column is stored in another d memory sites
of that same dedicated buffer. This arrangement of reading column-major
data from program library 100 and transmitting it to switch 113 via the
dedicated lines and RAM buffers makes p individual streams of data
continually and concurrently available to viewers. Each of these streams
represents a different t.sub.c second segment of the movie. For example,
the segment provided to switch 113 via line 103, buffer 108 and line 114
is the movie from time 0 through t.sub.c (0-57 seconds); the segment
provided to switch 113 via line 104, buffer 108 and line 115 is the movie
from time t.sub.c through 2t.sub.c (57-114 seconds); the segment provided
via line 105, buffer 110 and line 116 is the movie from time 2t.sub.c
through 3t.sub.c (114-171 seconds); and so on through line 107, buffer 112
and line 118 that provides the final movie segment (corresponding to time
(p-1)t.sub.c through pt.sub.c).
Once the nth column of data has been retrieved, the disk heads must be
repositioned to the start of disk 101 so that the | | |
