Note: Descriptions are shown in the official language in which they were submitted.
CA 022~6417 1998-11-23
W097/44942 PCT~S97/08679
CO~ K METHOD AND APPARATUS FOR OBJECT STREAMING
REFERENCE TO CO-PENDING APPLICATION
This application claims the benefit of a United States
Provisional Application Serial No. 60/018,256 filed May 24,
1996.
BACKGROUND
"Distributed computing" makes use of a computer
network formed out of one or more computers loosely coupled
together to allow processes on different computers to
communicate with each other and to provide services for
each other. One of the most common paradigms of
distributed computing is known as the "client-server
model", in which consumers of services are called
"clients", and make requests of service providers, called
"servers".
In object oriented distributed computing, there is a
notion of computer entities called "objects". Each object
comprises a particular state and a set of defined
behaviors. The state is represented by data maintained by
the object. The behavior is specified in terms of
operations that the object can perform with the
operations, typically realized by executable code.
Conceptually, the data and the code are inextricably bound
together in the object. Objects may be "persistent", that
is, they may continue to exist even though they are
inactive or the computer on which they exist has failed or
has been turned off. Further, objects may issue requests
for services to other objects as well as supply services.
.~.............................................................................. .....
CA 022~6417 1998-11-23
PCTrUS97/08679
W 097/44942
--2--
Typically, data is held in linear files on a server.
When a client requests that data or a part thereof, a
connection is formed between the data source (server) and
delivery (client) point.
In the prior art there are in general two different
types of servers. The first, known as a web server,
typically stores data files of a number of different types.
Web servers typically communicate with clients over a
network such as the Internet using the well known TCP/IP
protocol. The second type of server, known as a streaming
media server, stores and transmits media files of various
types.
More particularly, the web servers presently in use
typically store data files in a format known as Hyper Text
Markup Language(HTML). HTML permits the web servers to
handle container files which reference other files of
varying formats. Using HTML, a given web document may
include content information in various formats and may also
refer to other files by including reference information
known as a Uniform Reference Locator (URL). URL's specify
the location of remote servers at which files referenced in
the HTML file may be located.
Upon receipt of an HTML file from the original web
server, a client then must access each document referenced
from its source. Each such request typically requires a
full cycle of communication with a remote server, including
opening a connection socket with the remote server,
requesting that the file be transferred, waiting for the
file to download, closing the connection, and then, finally
parsing the file. To render a given web page may therefore
require many such cycles.
The other type of server, known as a streaming media
server, has been developed to be particularly suited for
multimedia of various types. Such servers may handle
single data types, such as a RealAudioTM file, or may
CA 02256417 1998-11-23
W O 97144942 PCTnUS97/08679
include mixed media typo~, in formats such a~ NetShow~
IRealAudioTM i~ a trademark of r~G~ssiv~ Networks, Inc.,
and NotShow~ io a trademark of Micro~oft Corporation). In
any ~vent, media filee ar~ typ~ cally laid out in a linear
fashion in a single file. ~hus, when the client requests a
~ile from a strsaming server, a socke~ is ~imply opened and
delivery of data ls begun.
The client may perform a caching or buffering
oper~tion prior to ~ctual p~ay back of the media file.
This ensures that the med~a file ~s played back to the user
of t~e client computer in a contin~ls~ls ~tream. In
particular, the client may calculate in advance an amount
of data that it must have on hand prior to actually
beginning to render the media file, ~o that the u~er has an
impression of con~inuous delivery of the media.
In such a linear streaming server, files may ~e
~ormatted in advance with a speclfic communication transfer
bandwidt~ in ~ind. For examp}e, a Real Audio file may have
been compressed ror recelpt at a baud rate such as 14.4
kilo bit~ per ~con~ (kbps). Another file would be made
available for optimum playb~ck at 28.8 k~ps. These
different file formats provide for al~owances in playing
back data suc~ that it is rondQred in a continuous fashion
at the re~pectiYe rates.
~5 In streaming media server, the connection remains open
with the server during the full duration of the play back
of the file. Thus, ~or example, even on a high speed
network connection 6uch a~ a Tl line, if the media file is
a ten minute audio file, then the connection will remain
open for ten minutes, even though the available information
transfer rate on a Tl line is much gr~ater than the audio
bandwidth.
I ~ In addition, one other disadvantage of streaming media
servers is that they typically implement a lossy type of
compression algorithm. Thus, if network traffic increases
-4-
after file download has begun, bits may be dropped and the
quality of the presentation is adversely affected.
Therefore, with streaming media files, the content
must typically be specific to each type of client at the
targeted bit rate. In addition, the streaming media server
is occupied for the real time duration of the media clip,
and the presentation may experience degradation based upon
the amount of latency in the network.
For example, EP 0 690 627 A1 describes a system in
which a user defined a sequence of user-specified items. A
remotely located processor selects expressive works that
conform to the user-specified items and communicates an
entertainment signal, e.g. broadcast television signal, to
the user.
EP 0 674 414 A2 disclosed a streaming distributed
multimedia system in which broadcast quality media data,
such as video clips, are sent in response to a list of
requests by a user.
SUMMARY OF THE INVENTION
Briefly, in the present invention, rather than
interpreting container objects that contain references to
other objects that must be retrieved by the client opening
multiple connections with various servers, and rather than
specifying the streaming of data in a single access
request, the present invention provides for transmission of
data as a stream of objects. In particular, in response to
a user or application request for a file, the client issues
a request for the file in the form of a sequence of desired
objects. The request is presented to the server as a
single request that includes a list of multiple objects to
be returned to the client.
On the server side, the request is pulled together
according to what the client has requested. The requested
objects are then sent together in a single stream to the
CA 022~6417 1998-11-23
-4a-
client. To accomplish this, the serve-r analy~es the
request to locate the particular objects.
Objects that are available locally to the server are
S simply added to the outgoing stream, however, the server
may also need to query back end file servers and other
sources for objects that may be located at other compute~s
in the network. The server then assembles these objects
together and provides them to the client in a si~sle object
stream.
AMENDED S~IEE7
CA 022~6417 1998-11-23
,. '''''~ ,, . ~ ' ' ''.
_5~
The server assembles objects "on-the-fly", based upon
client-specific criteria. The present invention thus also
permits the mixture of different objects in an object
stream, depending upon the particular client or client
request. The assembly of object streams thus occurs
dynamically based upon any number of client-specific
criteria, such as the objects already available to the
client, the communication channel bandwidth, the desired
presentation quality, ciient buffer capability, or other
parameters associated with the client or the communications
channel.
For example, the server may maintain a log of objects
already sent to the client, and send only those objects
which are not already available at the client computer.
The client may also specify an object class tose~her
with information that enables the server to determine wh-ch
member object of the class is to be placed in the stream.
Such infor~ation may include the communication
bandwidth, graphical resolution, physical location, or
other information which varies from client to client.
In one implementation of the invention, typicall~ ~he
default implementation, the server may analyze the reouest
and assemble objects based upon a predefined order, such as
specified by an object map file located at the server.
The server may also send objects of a particular
quality targeted to particular clients. The selection of
objects may depend upon client parameters such as observed
network latency in real time or desired object qualit~.
The system may also include buffering, so that tre
rendering of the set of objects may be delayed until a
sufficient amount of data is received at the client.
BRIEF DESCRIPTIONS OF THE DRAWINGS
The foregoing and other objects, features and
advantages of tne invention will be apparent from the
AMENOED SHEET
. . ~ .
CA 022~6417 1998-11-23
W O 97/44942 P ~ ~US97/08679
--6--
following more particular description of preferred
embodiments and the drawings in which like reference
characters refer to the same parts throughout the different
views. The drawings are not nec~ rily to scale, emphasis
instead being placed upon illustrating the principles of
the invention.
Fig. 1 is a block diagram of a computer network
employing the present invention.
Fig. 2 is a schematic flow diagram of one embodiment
of the present invention.
Fig. 3 illustrates how a server dynamically assembles
an object stream in response to a client request.
DETAILED DESCRIPTION OF THE PREFERRED EM~ODIMENT
Illustrated in Fig. 1 is a block diagram of a general
computer network 21. A plurality of computers 13, 15, 17
are coupled across a communication channel 11 for
communication amongst each other. Various subsets of the
computers may themselves form a local area network (LAN) or
other local network 13, 15. Each of the various local
networks are coupled through a respective router 12a, 12b
to channel 11. This enables communication from one local
network to another across the channel 11 to form what is
known as an "internet". In the preferred embodiment, the
present invention is employed on what has become known as
the Internet (an international computer network linking an
estimated 35 million people to approximately 4.8 million
host computers or information sources).
In the preferred embodiment the computers 13, 15, 17
or digital processors employing the present invention are
of the PC or mini computer type, or the like, having
CA 022~6417 1998-11-23
W 097t44942 PCT~US97/08679
-7-
processing capabilities of the Intel XX386 processing chip
or better. The communication-channel 11 is a typical
telephone line or other transmission/communication cable
handling a 28,800 baud data rate or the like.
A sequence of steps are undertaken by the computers
13, 15, 17 to transfer data in the form of a stream of
objects according to the present invention. For example, a
given client computer 13a may issue a request for computer
data to another computer 17, which acts as a server.
Referring to Fig. 2, the client 13a is a computer
that executes an application (or other user interaction)
for which certain data needs to be made present. In steps
100 and 102, the client receives an object stream request
from the application that includes a global identification
of an object map which indicates certain objects existing
in the network 21 that the client application program
seeks. In particular, the object stream request includes a
list, or linear sequence of objects identified a global
object identification number. The client 13a transmits the
initial request to the serYer 17, which enters state 200 to
transfer back a global identification of the object map
listing subject objects.
The client next determines whether the object map is
stored locally. Thus, the client 13a checks multiple local
memories such as hardware caches, working memory, CD-Rom's
and local network memories for the object map in state
108.
If the object map is found locally, then the cl'ient
analyzes the object map. If the object map is not found
locally, then the client requests the object map from the
server in state 106.
In response to this request, the server enters states
202, 203 and 204 to (i) initialize a log of object
identifications for this client, (ii) initialize a steady
CA 022~6417 1998-11-23
W O 97/44942 PCTrUS97/08679
state connection with the client, and (iii) transmit the
object map identified by the client 13a.
The client 13a then analyzes the object map in state
108. This is accomplished by the client processing each
object referred in on the object map, as indicated by the
analyze loop of states 110,112 and 114.
For each such object, the client first determines, in
state 110, whether the object is in local cache. If not,
then the client 13a adds the identification of the object
to a request block. As long as the block is not full, this
loop continues with the client adding an identification of
each object not found in local cache in state 112.
When the block is full in state 114, the client
transmits a request to the server for the block of objects
as a list of object identifications.
Upon receipt of this request (i.e., a block of object
indentifications), the server 17 then initiates the
assembly of a data stream and compiles the stream of
objects based on (i) the sequence of requested objects
and/or ~ii) quality of the objects.
To accomplish this the server constructs blocks of
objects to form the data stream, in states 206 through 214.
In constructing the blocks, the server 17 maintains a log
of objects being transmitted to fulfill the client's
request. Specifically, in states 206 and 208, for each
object in the block, the server 17 first determines from
the log whether the object has previously been transmitted
to the particular client 13a. If so, the server 17 enters
state 214 to prevent that object from being placed in the
current block. Therefore, states llo and 212 are entered
only for the objects that the client is actually in need
of. In state 210, then, the server only fetches objects
from remote servers which are actually needed by the client
13a. This provides a significant performance advantage,
especially where the objects must be obtained elsewhere in
CA 022~6417 1998-11-23
W 097/44942 PCT~US97/08679
the network 21. As such, the server 17 constructs blocks
of data and hence compiles the stream of data for the
client 13a in real time, i.e., on the fly, without
duplication of any one object throughout the total data
stream.
On the receiving end, the client 13a receives the
object stream in state 116. More accurately, the data of
the object is then delivered to the requesting application
of the client for further processing and use.
In summary, for each such object request by the
client 13a, an object streaming type communication from the
server 17 to client 13a is performed. In particular, a
request for a sequence of non-local objects is made by the
client 13a and transmitted to the server 17. In turn, the
server 17 initializes a log of objects according to object
identifications, and then fulfills the request for objects
by transmitting the requested objects, in sequence order,
which have not previously been transmitted to that client
13a as indicated by the log.
It should be understood that the objects may be
computer data structures of various types and formats. The
objects may, for example, be compiled in any number of ways
within the object oriented computing model well known in
the art. For example, objects may include text, graphics,
audio, video, and other types of digitized information.
Furthermore, objects may be complete data files or only
portions of such files. In addition, the objects
themselves may be classes that consist of a number of
objects grouped together. The object request must then
typically include information to specify which member of
the object class is desired by the client 13a.
For example, an object class may consist of various
versions of a particular graphic object. The selected
version may depend upon the desired quality of the final
graphical rendering of the object desired by the client
CA 022~6417 1998-11-23
W O 97/44942 PCT~US97/08679
--10--
computer 13a. Quality may also have other meaning such as
bandwidth, graphical resolution, number of colors,
available client memory cache size, and other class
criteria that depend upon the type of client computer 13a.
In addition, object classes may depend upon various
other client-specific information such as domains, for
example. In this sc~nArio, when the client computer 13a is
located in one area of the cou~-L~, such as Massachusetts,
a different object may be returned than when the client 13b
is located in California, although each of the clients 13a,
13b actually requested the same global object.
Fig. 3 is a diagram illustrating how an example object
stream 300 may be assembled by the streaming servers 17,
and in particular showing how the object stream does not
have to originate from a single source or a single file.
Here the client 13a requests and receives a particular
object map 301 consisting of a list of object
identifications such as the list (IDl,ID4,ID7,ID6,ID2,
ID3), where each object identification IDx indicates a
global address for a particular object. According to the
process already described in connection with Fig. 2, the
client 13a first creates a request block 302 taking into
account any local objects 303 which it may already have
available. In the particular illustrated example, the
client 13a already has local objects (01, 06) available
locally.
After compiling the request block 302, the request
block 302 is sent to the streaming server 17. Streaming
server 17 receives the request block 302 and then assembles
a stream block 310a for the client 13a. It should be
understood that other stream blocks 310b may also be
constructed for other clients 13b at the same time as the
block being constructed for client 13a.
For example, assuming a first time interaction between
the client 13a and server 17 in a given stream, the server
CA 02256417 1998-11-23
W 097/44942 PCT~US97/08679
--11--
17 typically has a default data stream order regardless of
user interaction on the client 18 side.
In a fir~;t modification, the server 17 may have
available certain information concerning the client.
5 Because the server 17 may compose the data stream on-the-
fly, the default stream order may be changed in accordance
with prior history of requests made on the server 17. That
is, on the server processor, an analysis of multiple prior
usage of server objects by other clients is made. The
server 17 changes the default objects stream 300 order to
the closest substitution (i.e., object map) based on
demographics of clients 13a having prior server datatobject
usage. To accomplish such an analysis, a neural network
may be employed.
In yet another modification, the streaming server 17
may create the stream block 310a from information that is
known a~out the specific client 13a.
For example, the server 17 may maintain a log 311a of
objects that have already been provided to client 13a as
well as any available local objects 312 local to the server
17. In the illustrated example the log 311a indicates
objects (IDl,ID6) as already having been provided to client
13a. In addition, the available local objects 312 include
(04,012).
It should be understood, as previously described, that
a particular object such as object 04 may actually consist
of a class definition, as illustrated, wherein a number of
objects comprise the class. For example, object 04 here is
actually an object class (04a,0b4,...04x). The streaming
30 server 17 thus also receives together with the object
identification request block 302 information as to which
particular member of class 04 is appropriately provided to
the client 13a.
The streaming server 17 then assembles the stream
35 block 310a as illustrated, which lncludes all of the
.
CA 022~6417 1998-11-23
objects that the client 13a has requested. In the
illustrated example this includes objects (04a, 07, 02,
012, 03). After assembly of the stream block 310a the
streaming server 17 then provides the stream block 310a as
a single object stream 300 to the client 13a.
During assembly of the stream block 310a the s_r2am--g
serve~ 17 may not have all the necessary objects availaDle
in the local object list 312. In such instances the
streaming server 17 must query other remote server
computers l5a, 15D conrected to the network 21 in OrGer to
locate the objects. This is cone in a marner which is we l
known i~ the art by the streaming server 17 making reques.s
of the remote computers 15a, 15b to provide their
respective objects that they have made available. In F g.
3, objects (07, 02) are located at computer 15a anG objec_
(03) at computer 15b.
An identical object map may be ope~ated cr -n 2
dlfferent manner by server 17 for client 13b. In
particular, although the object map 301b is tne same as t:e
objects map 301a, because a different lis. of ob,ec- 3u3b
is available to client 13b, the request block 302b cr~a~2d
by client 13b will have different object identif ca- on
numbers (ID4, ID6, ID3). Furthermore, the client
parameter(s) prov~ded with the request block by clien~ 13O
may very well be different for that provided by clier' 13a.
Thus, an object of a particular quality may be targeted to
client 13b which is different than as that supplied to
client 13a. For example, when clients 13a and 13b reauest
that object 04 be provided to them, client 13a may actualiy
receive object 04a and client 13b may receive objec~ 04b,
despite the fact that the reference 04 was a common g obal
object identification.
The object classes may also be defined as bandwi c'h
selectable objects. In particular, the resulting data
stream 300 may be assembled based upon observed client
AMENCED S!~EE~
CA 022S6417 1998-11-23
W 097/44942 PCTAUS97/08679
-13-
bandwidth availability. Therefore, depending on a
periodically calculated data transfer rate, the client 13a
or server 17 may choose to request or transmit a data
stream of different objects. That is, for a given
requested object 04, a specific version 04a, 04b...04x may
be selected for transfer from the server 17 to the client
13a as a function of available bandwidth. This function is
termed "bandwidth scalabilityr of the object stream.
In another possible implementation, Uobject specific
compression" is provided by the server, such that on an
object by object basis, the object data stream 300 may be
compressed one object at a time depending upon client
criteria. In the preferred embodiment, the server 17
determines which compressed object version to include in
the object data stream 300 at the time of compilation.
The client 13a also manages the amount of data being
delivered, i.e., throughput to a client 13a. In
particular, this is useful to determine whether there is
enough data being timely transferred; that is, whether data
is being consumed on the client 13a end faster than the
server 17 is delivering the requested objects.
In the preferred embodiment, the client 13a builds a
map of uncompressed data consumption. The map tells how
fast data is being consumed (used by the client 13a
application). The client then measures the throughput
(client receipt) of data in real time and contrasts that
with the formulated map. Based on the comparison, the
client 13a is able to determine how much of the object
stream data 300 should be read by a buffer 320a at a time.
Thus, the client 13a effectively maps the physical
compressed ob3ect data stream 300 and logical consumption
of data at each point in time.
The client 13a continually monitors the real data
throughput versus data consumption. The client 13a wants
the delivery-to-consumption ratio to be greater than one so
CA 022~64l7 l998-ll-23
W O 97/44942 PCT~US97/08679
-14-
that the throughput (supply) is keeping up with the
consumption (demand). When the delivery-to-consumption
ratio is less than one, there is more data being consumed
than the amount of data being delivered, such that there is
a so-called "buffer debt" on the client 13a side. In that
case, the transmission of data needs to take advantage of
pause points in the object data stream 300, so that for a
period of time, data is not being transmitted over the
communication channel 11. In turn, the buffer 32Oa is
allowed to fill up with the requested data and thus
decrease or solve the "buffer debt", to assist with proper
real time delivery of objects.
The pause points may be pre-defined by the author of
the object content, or the pause points may be determined
on the fly in accordance with the client's ability to
consume data.
In the preferred embodiment this latter implementation
is accomplished as follows. The client 13a at each time
point, t, computes object data consumption. A running
average of throughput such as number of bytes received
divided by total time in seconds is employed. An adaptive
running average or weighted average or the like may also be
used to compute the data consumption. This is also known
as the physical throughput at a given time, i, (i.e.,
(pti).
The total logical data (tld) optimally needed at a
point in time t is calculated as follows:
t
tld = ~ rate map ( i )
Buffer debt is then calculated as follows:
CA 02256417 1998-11-23
-lS-
bu ff er debt=~, ( tl d ( i) - pti)
The client 13a then calculates the buffer cebt frcm
time to time. ~or a buffeY debt sreater t~an C tne client
calculates a maximum wait time
maxwait = burfer debt . physical throu~hput
which e~uals tre number of seconds of pausing needed to
rectify the buf,~er debt. At each wa t point or pause po-n.
in the object data stream 300, the client 13a will then
~ait a minimum of ma,~,~ait time or the maYimum time allowed
at that wait point. rO~~ a buffer debt OL less than zero,
the serve_ 17 transmissior of data is ahead of the
consumptior anc thus no pausing durirg the trarsmissicn o_
the object data stream 300 is warranted.
~QUIV~TS
1~ r~hile the inven_~on ras been particula~ly sho~ ard
described ~ith reference to a pre_erred embodiment trereo ,
it will be understood by those skilled in the art that
various changes in form ard details may be made there-n.
r or e~ample, the log maintained by the server 17 for
2C preventins duplication or objects in the trarsm;tted object
data stream 300 to the requesting client may be implementec
with tables, cache memory and the like. In the case o~
caching, a sparse re?resertation of the most recent
transmitted objects is mainta~ned in the log. Other
cachins or 105 i.mplementations are suitable and are
understood to be in tr.e purview of one skilled in the a-t.
AhlENDED SltEE1
CA 022564l7 l998-ll-23
W O 97/44942 PCT~US97/08679
-16-
Another example is the term "local to the client".
"Local" means in various memories including hard drives,
cache memories, CD's and other working memories in the
local network involving the client 13a.
