Ulllted States Patent [19]
`Chen et al.
`
`US005 8225 24A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,822,524
`Oct. 13, 1998
`
`[54] SYSTEM FOR JUST-IN-TIME RETRIEVAL
`()1? MULTIMEDIA FILES OVER COMPUTER
`
`NETWORKS BY TRANSMITTING DATA
`
`gggllgggggggmggggfzgATE
`
`_
`[75] Inventors: Huey-ShIang Chen; Monjsong Chen,
`both of Katonah, N-Y; shlow-Laallg
`Huang, Herndon, Va; Deyang Song,
`
`Oradell, N.J.
`
`[73] Assignee: Infovalue Computing, Inc., Elmsford,
`NY
`
`_
`[21] APPl- N°~~ 505,488
`
`[22] Flled:
`
`Jul‘ 21’ 1995
`
`6
`[51] Int. Cl. .................................................... .. G06F 13/00
`[52] US. Cl. ....................................................... .. 395/200.33
`[58] Field Of Search ............................. .. 395/600, 200.33,
`395/200.47, 200.49, 200.61, 200.76; 358/468;
`370/601, 84, 94, 60; 364/200; 360/73;
`235/375; 381/41; 375/13, 357; 348/7, 10,
`12 13 14
`’
`’
`
`5,463,422 10/1995 Simpson et al. ...................... .. 348/390
`5,491,565
`2/1996 Naper . . . . . . . . . .
`. . . .. 358/468
`
`21“ ct alt-
`
`-l--
`
`,
`
`,
`
`rover e a .
`
`........................ ..
`
`5,521,630
`
`5,533,021
`575417919
`5,544,170
`5,550,982
`
`
`
`Nguyen a .................. .. 5/1996 Chen 6161. . . . . . . . . . . . . .. 348/7
`
`
`
`7/1996 Branstad et al.
`7/1996 Yong etaL
`8/1996 Kasahara
`8/1996 Long et al.
`
`370/60.1
`370/61
`.. 370/253
`395/200.13
`
`. . . . . .. 370/84
`5,566,175 10/1996 Davis . . . . . . . . . .
`....... .. 348/7
`5,583,561 12/1996 Baker et al.
`395/200-77
`5,621,660
`4/1997 Chaddha et al'
`370/234
`5,633,859
`5/1997 Jain e161.
`348/17
`5,644,355
`7/1997 KOZ et al. ..... ..
`. 348/408
`5,666,161
`9/1997 Kohiyama et al.
`5,721,878
`2/1998 Ottesen et al. ............................ .. 348/7
`
`FOREIGN PATENT DOCUMENTS
`
`62299148 12/1987 Japan ~~~~~~~~~~~~~~~~~~~~~~~~~~~ " H04L 13/00
`O2_O92153 3/199O Japan __
`H04N 1/32
`03-133255 6/1991 Japan ..
`H04N 1/32
`04-72838 3/1992 Japan ..
`H04L 7/00
`06-014080
`1/1994 Japan ........................... .. H04L 29/06
`
`_
`_
`Primary Exammer—Moustafa M. Meky
`Attorney, Agent, or Firm—Eliot S. Gerber
`
`
`
`References U'S' PATENT DOCUMENTS
`
`A method in computer networks in Which a client machine
`
`4,001,690
`4,027,337
`4,051,530
`
`,
`
`,
`
`1/1977 Mack et a1. ........................... .. 370/316
`5/1977 De Loye et a1. .
`360/73
`9/1977 Kuroda et al
`-- 348/415
`- - - - ~~ 375/13
`476067044
`8/1986 Kudo - - - - - - - - - - - - - - - - -
`364/200
`4530496 12/1986 Bednar’ Jr‘ et a1‘ "
`358/133
`4’729’020
`3/1988 schaphorst et a1‘ "
`.. 348/400
`4,833,535
`5/1989 OZeki et al. ........ ..
`370/94
`478397891
`6/1989 Kobayashi et a1‘
`370/507
`5,025,457
`6/1991 Ahmed ............ ..
`370/235
`5,029,164
`7/1991 Goldstein et a1_
`__ 358/160
`5,126,845
`6/1992 Yamashita
`.... .. 381/41
`5,136,655
`8/1992 Bronson
`370/230
`5,208,810
`5/ 1993 Park --~_ --------- ~
`235/375
`572377156
`8/1993 K9nlshl ct a1~
`"""
`ymcer et a1‘
`395/600
`6/1995 Takahashietal.
`5,428,774
`370/397
`8/1995 Goldstein ..
`5,446,734
`5,457,687 10/1995 Newman ............................... .. 370/232
`
`(playback client computer) requests multimedia ?les, such
`as compressed video clips, from a server (storage server
`computer). The transmission uses digital data packets. In the
`case of video ?les, the packet headers identify the video
`frame and the sequence number of each packet derived from
`the frame The transmission timing is not based on a steady
`b
`'
`fb
`b
`.
`d I
`d
`'yte stream or an average 0 ytes to e transmit'te . nstea ,
`1“ the/F2156 of V1de°> th‘? frame Fate dete?mnes normal
`transmission and a frame is transmitted during each frame
`time. The client agent has a normal packet buffer, normally
`holding 1—5 video frames. The transmission rate is adjusted
`to keep that buffer ?lled Within its normal range. The timing
`information required for transmission, in one embodiment,
`is stored in a separate index ?le associated With each
`mulnmedla ?le‘
`
`-
`
`-
`
`42 Claims, 6 Drawing Sheets
`
`1n . . . . . . . . . . . . . . . . . . . .
`
`. . . . ..
`
`,
`
`20
`A
`
`Z/
`L
`r
`/‘7
`2X
`31
`f 4 3 30 ‘l
`5 Network Server Control
`MM Client Agent Network
`Application
`Interface Control Charm] Interface
`//~_1
`
`w
`
`6
`
`/2
`
`Storage
`Subsystem
`
`Page 1 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`US. Patent
`
`Oct. 13, 1998
`
`Sheet 1 0f 6
`
`5,822,524
`
`
`
`Page 2 of 15
`
`PETITION ERS' EXHIBIT 1014
`
`Page 2 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 2 0f 6
`
`5,822,524
`
`Network
`
`Network Interface
`
`3*1 1
`T
`L
`
`[J
`3 7
`\ Command
`Processor
`
`3'6
`\ Client
`Controller
`
`36 '1
`Buffer
`Manager
`
`5'5
`\ Application
`Interface
`
`/
`
`32
`1
`Data /
`Receiver ‘
`
`35
`Packet /
`Buffer
`
`‘
`
`‘
`34
`Output /
`Processor
`
`Multimedia Application
`/ 4
`
`1
`
`Page 3 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`U.S. Patent
`
`0a. 13, 1998
`
`Sheet 3 of6
`
`5,822,524
`
`Framc'runc
`
`LastPktS cqNo
`
`TxModc
`
`AWDMR“
`52
`
`/50
`
`Data Queue
`
`59
`
`DataQucucSizc
`
`I
`I
`I
`I
`I
`
`m
`
`\\
`
`I
`I
`
`Packs! Hcadcr
`
`DATA
`
`/,54
`
`PktS eqN 0
`FramcNo
`InFramcSeqNo
`Offset
`Size
`
`jé List of lost Pkt
`
`l
`'
`
`(J- PktS cqN 0
`
`\
`
`o TimcOutValuc
`
`Page 4 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`U.S. Patent
`
`0a. 13, 1998
`
`Sheet 4 0f 6
`
`5,822,524
`
`53.;
`6A
`6/“ Multimedia _’ Parser -’
`File
`
`Index
`Frle
`
`Server Control
`
`J Tuning
`
`Information
`
`Time I
`
`
`
`ME ME Wag. WEE
`
`____Frarnc
`Data é5
`
`Data
`Packet 65
`
`Page 5 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`US. Patent
`
`Oct. 13, 1998
`
`Sheet 5 0f 6
`
`5,822,524
`
`omSQmN\
`
`Sagan—ammmv_H_
`
`Rx
`
`uwSQm
`
`ecstas—
`
`838on
`
`guts:—35382
`
`x5352
`
`3
`
`as;E
`
`5.6550
`
`Signum
`
`
`
`:Emmgmcfih(MN
`
`mmuuo<
`
`Eaubm
`
`USE—Eco
`
`8388;
`
` gramA®\
`
`Page 6 of 15
`
`PETITION ERS' EXHIBIT 1014
`
`Page 6 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`0a. 13, 1998
`
`Sheet 6 0f 6
`
`5,822,524
`
`InFrameTx
`
`TxMode
`
`FrameTxTmle
`
`Frame'l'une
`
`-4/
`42
`40A
`40B
`
`InFramsTx =
`Adjust Timc_to_Tx of
`the next framc
`Read one more frame
`
`F3158
`
`from the disks
`
`I
`
`j
`
`43
`InPrameTx = Tru
`
`YES
`
`NO
`44
`TxModc = RUSH
`
`TxMode=NORMA
`&FrameTxTime 4
`Current Time'
`
`InFrameTx = True
`
`Exit
`
`Page 7 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`5,822,524
`
`1
`SYSTEM FOR J UST-IN-TIME RETRIEVAL
`OF MULTIMEDIA FILES OVER COMPUTER
`NETWORKS BY TRANSMITTING DATA
`PACKETS AT TRANSMISSION RATE
`DETERMINED BY FRAME SIZE
`
`FIELD OF THE INVENTION
`
`The present invention relates to methods for retrieval of
`multimedia ?les, such as video, over computer netWorks.
`
`10
`
`BACKGROUND OF THE INVENTION
`
`2
`for example, has data rates (rates of information ?oW) Well
`exceeding 100 Mbps (million bits (megabits) per second),
`Without compression, and betWeen 1 to 8 Mbps With video
`compression. Video compression uses algorithms to pack
`video data in a form taking up less memory and requiring
`less transmission speed. It strives to make the data look
`realistic When it is played back on a computer monitor
`screen or TV set. “Video playback boards” are hardWare
`used to decompress data and utiliZe various compression
`standards. These compression standards, Which vary in their
`Mbps utiliZation, govern the vieWing quality of videos.
`Compression standards include Indeo (1.2 Mbps), MPEG-1
`(Motion Picture Experts Group-1) (1.5 Mbps), motion JPEG
`(Joint Photographic Experts Group) (5—6 Mbps) and
`MPEG-2 (Motion Picture Experts Group-2) (6—8 Mbps).
`In most situations, only compressed video can be stored
`and delivered across netWorks due to the limits of transmis
`sion speed and computer memory. Even With compression,
`hoWever, video still has a high memory storage requirement,
`and thus is ideal for client server con?gurations in a data
`netWork. In those con?gurations, a server holds compressed
`video clips although, less preferably, it may hold uncom
`pressed video clips and compress the video as it transmits it.
`Many client machines, Which individuals control, can access
`the server and obtain the video clips in compressed form.
`The client machine then decompresses the video clips and
`displays them on its screen for the user to vieW. Hence, the
`high cost of installing expensive large capacity storage in all
`client machines is avoided.
`HoWever, transmitting multimedia data across computer
`netWorks for immediate playback at the receiving end is
`complicated by both the nature of computer netWorks and
`the elaborate processing necessary for effective playback.
`Today’s prevalent computer netWorks use statistical multi
`plexing for transmission. This process “packetiZes”, i.e.,
`divides data into segments so that it can be transmitted
`Within and betWeen computers. The data, in packet format,
`can then be transmitted through a series of store-and
`forWard operations, because the packet contains a “header”,
`Which is a set of bytes identifying the packet and usually
`identifying its destination, i.e., the identity of the computer
`to Which it should be transmitted. Each time a netWorking
`computer stores-and-forWards (puts into its memory and
`then transmits to another computer) an additional element of
`variable delay is added to the end-to-end transmission
`latency (the time it takes to move a packet from one end of
`the netWork to another). The variability of this store-and
`forWard delay depends on the number of other packets that
`are queued (Waiting in line) and competing for the same
`transmission resources. Due to this variability, different
`packets of the same video stream experience differential
`transmission latency (different amounts of delay). This dif
`ferential latency causes a phenomenon knoWn as “delay
`jitter”, Which the vieWer sees as jerky motion and inferior or
`unacceptable picture quality.
`The prevailing approaches to transmission of video over
`computer netWorks focus on transmitting the same average
`rate of data to the client machines from the server. The
`average rate, in bytes per second, is computed by dividing a
`?le’s total siZe by its playback length (in seconds). This
`average data rate, hoWever, only indirectly measures motion
`smoothness, because video frame siZes may vary by as much
`as a factor of 10. In MPEG-1 (Motion Picture Experts
`Group), a video compression standard, the siZe of an I (Intra)
`frame, on average, is about 2 to 3 times that of a P
`(Predictive) frame, and the siZe of a P frame is about 4 to 5
`times that of a B (Bi-directional interpolated) frame.
`
`15
`
`20
`
`Multimedia computing has recently emerged as an impor
`tant information technology. Multimedia computing obtains
`information from a variety of media retained in information
`storage in the form of digital data, for example, motion video
`clips (segments) and audio clips. This alloWs businesses and
`non-pro?t organiZations to create highly effective computer
`presentations and, using computers, provide superior train
`ing and education.
`For example, instead of storing paper technical manuals,
`Which must be searched manually, Workers on a manufac
`turing ?oor could use a computer terminal, called a “client
`machine”, to interactively access a large collection of mul
`timedia training materials stored in a centraliZed “server”. A
`25
`“client machine” is a computer or terminal having a screen
`that an individual uses to access and display video ?les. It
`has at least three component processes: MM (Multimedia)
`application, i.e., the display of a video clip; Client Agent,
`i.e., softWare (computer program to access the server) and
`NetWork Interface, i.e., an interface card. A server (server
`machine) is a computer, for example, a “mini-computer” or
`Workstation computer or super-computer, connected to a
`number of computer terminals (client machines) in a Local
`Area NetWork (LAN) or other computer netWorks, such as
`metropolitan area netWorks, i.e., FDDI and high speed Wide
`areas netWorks, such as ATM. The server stores and delivers
`digital video clips to multiple client machines in a netWork.
`The server includes, at least, three component process:
`NetWork Interface, i.e., an interface card; Server Control,
`i.e., softWare to control access and delivery of stored video
`clips; and Storage Subsystem, i.e., digital memory storage of
`video. In interactive access, the user operates his client
`machine to request multimedia ?les from the server for
`display on the screen of the client machine and the server
`responds to the user’s requests. For example, a Worker, at the
`press of a key, could have the server retrieve more detail, on
`the subject of his choice, using text and video. In this
`arrangement, a centraliZed server (as opposed to an indi
`vidual computer) stores the necessary multimedia informa
`tion. This arrangement exists because video clips (usually
`video 0.1 to 10 minutes long) require a large amount of
`computer storage. For example, a one-minute video clip,
`compressed, may be over 12,000,000 bytes (12 Mb—a byte
`here being 8 digital bits) in siZe. Thus, having a large
`selection of video clips on the individual computers of a
`netWork Would not be economical. Multimedia technology
`may also provide neW forms of entertainment, video-on
`demand being one Well-knoWn example. In a video-on
`demand system, a centraliZed netWorked storage server
`stores a large collection of videos, such as entire full-length
`feature ?lms in video form (90—180 minutes). Aplurality of
`users may simultaneously retrieve their preferred video
`features at their selected vieWing times.
`Multimedia computing has signi?cantly greater process
`ing poWer and storage requirements than computing that
`only involves text and numeric data. Typical motion video,
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 8 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`5,822,524
`
`3
`Due to their isochronous property (regular timing of a
`stream), transmission of multimedia data ?les requires con
`sideration of factors that traditional data transport protocols,
`such as TCP/IP, do not consider. Transmission of video
`requires that frames are played back at ?xed intervals (?xed
`time frames) to ensure motion smoothness and thus vieWing
`quality. Traditional systems such as TCP/IP simply manage
`the data in blocks, addressing only throughput but not timing
`considerations. NeW proposals tailored for transmitting mul
`timedia ?les focus on utiliZing additional and/or stronger
`netWork functionality, such as priority transmissions and
`guaranteed bandWidth. Guaranteed bandWidth means that a
`transmission Will alWays have up to a speci?c amount of
`information-carrying capacity reserved for its use. While
`these approaches provide some improvement, they still treat
`a multimedia ?le as a byte stream, and consequently aim to
`maintain an average transmission rate. Such an average
`transmission rate does not take into account the variability in
`individual frame siZe, i.e., hoW many bytes are in each
`frame.
`Given the large variations in frame siZes, frame rates and
`end-to-end transmission latencies, it is not ef?cient to treat
`a multimedia ?le simply as a byte stream. HoWever, that is
`the conventional and prevailing approach Which is presently
`being commercially implemented. Even though both video
`and text are transmitted in the form of digital data in packet
`format, video transmission is more problematic. To regulate
`the How of video transmissions, the client machines and
`server machines should frequently exchange control mes
`sages. These messages should result in adjustments of the
`rate of data ?oW. A need exists for an ef?cient method for a
`client machine to retrieve multimedia data from a server
`With minimum latency (delay) and minimum overhead (use
`of memory and processing); With ?exibility in satisfying a
`variety of application requirements; With the ?nal picture on
`the client machine monitor being of high quality, i.e., not
`being jerky; and Without the use of additional memory or
`other additional hardWare.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides a method for a client
`machine to retrieve multimedia data from a server machine
`With minimum latency and overhead. The method is pref
`erably implemented by installing softWare programs on the
`client machines and server, Without any hardWare changes;
`assuming that the client machine and server have suf?cient
`memory and the client machine has adequate video decom
`pression capabilities.
`The method of the present invention also provides mul
`timedia data as readily available to application programs as
`if that data Were in the form of ?les in the data memory
`storage of the client machine. This invention minimiZes the
`amount of buffer (memory space for temporarily storing
`multimedia data) in the client machine.
`Accordingly, this invention is a method for retrieving
`multimedia ?les from a server computer to a client computer
`over computer netWorks.
`In the preferred embodiment the server transmits the
`multimedia ?le in the form of digital data packets. The
`transmission rate is based on the frame rate of the ?le. There
`is no attempt to provide an even data stream based on
`averaging.
`First, there is provided a means for extracting essential
`timing information Which has been speci?ed in the multi
`media ?le. Multimedia data streams have Well-de?ned
`building blocks (objects) Which should be the basis for
`
`4
`transmission timing in order to insure playback quality. In
`MPEG-l motion video (Motion Picture Experts Group-1), a
`video compression standard, the video picture or frame
`serves as the building block. Although a constant number of
`video frames are played in 1 second, generally 30, the
`amount of data in one second of video varies With the
`complexity of its content. For example, a video clip shoWing
`a bar graph has loW complexity compared to a video clip of
`a football game.
`Secondly, the present invention uses the timing informa
`tion in the index ?le to
`ensure transmission of a video
`frame in a frame time under normal circumstances, e.g., 30
`frames per second, and (ii) provide an explicit hand-shake
`protocol (a series of back and forth prearranged digital
`messages coordinating a set of operations) betWeen client
`agent and server processes. This protocol regulates the
`transmission rate in exceptional situations.
`Thirdly, the present invention provides a process in the
`client agent to receive data from the server With minimum
`latency (delay); With minimum overhead (use of memory
`and processing resources); and With the ?exibility to satisfy
`a variety of application requirements. The process in the
`client agent has the intelligence to selectively execute the
`explicit processing required for additional features When
`such additional features are needed.
`Finally, this invention provides a process in the client
`machine to monitor and log the behavioral characteristics of
`the applications. The log enables the process in the client
`machine to ?ne-tune its processing during run time (the time
`it is operating) and optimiZe its interactions With the process
`in the server computer.
`This invention times the transmission of multimedia ?les
`according to a ?xed rate, generally the frame rate during
`normal transmission. For example, if the client machine can
`display 30 frames per second, the server Will transmit a
`frame of compressed video starting at each 1/30th second,
`regardless of the complexity of the video frame. The client
`machine needs to store in its memory only one, or a feW,
`frames as neW frames are transmitted to it at a regular rate
`(frame rate). HoWever, if the data in the buffer of the client
`agent is beloW a selected standard (“Water mark”), the
`transmission rate is increased; if above a selected standard it
`is decreased.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic illustration (block diagram) of the
`client machine retrieving multimedia data from the server
`machine over a computer netWork;
`FIG. 2 is a schematic illustration of the structure of the
`client agent;
`FIG. 3 is a schematic illustration of the buffer manage
`ment in the client agent;
`FIG. 4 is a schematic illustration of the desirable frame
`level pacing based on the essential timing information
`speci?ed in multimedia ?les;
`FIG. 5 is a schematic illustration of the design of the
`server; and
`FIG. 6 is a schematic illustration of the transmission
`scheduling algorithm.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`FIG. 1 represents schematically the overall system. The
`client machine (20) is the computer upon Which a user types
`his commands, for example, a PC (Personal Computer)
`
`65
`
`Page 9 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`5
`Which may have a relatively loW end integrated circuit
`microprocessor such as an Intel (TM) 386 processor,
`although any type of PC may be used. The user Wishes to
`retrieve multimedia ?les from the server (21) via data
`connections and over a computer netWork. The client
`machine (20) has three interacting processes: the client agent
`(30) Which interfaces With the netWork interface (3) and the
`multimedia application (4) in the client machine. For
`example, the server (21) may be a Workstation such as a Sun
`(TM) Workstation or IBM PC Server 300 and having a high
`throughput and storage capability, for example, using a disk
`array. A typical multimedia application is the playback of a
`full-motion video clip. The netWork, for example, may be an
`Ethernet (bus netWork topology) Which may be implemented
`With coaxial Wiring and 1000—3000 feet betWeen nodes, or
`a Token Ring system (high speed token that checks in at each
`node, available from IBM).
`The client agent (30) has the primary responsibility of
`retrieving from the server control (1) the right set of mul
`timedia data at the right time to satisfy the needs of the
`multimedia application
`The client agent (30) maintains
`a packet buffer (31) (a structure for temporary data storage)
`as a cache storage (temporary data storage center). For
`example, the packet buffer (31) may be a section of the RAM
`(Random Access Memory) of the PC. Correspondingly, the
`primary responsibility of the server (21) is to read from disks
`and make just-in-time delivery of the appropriate set of
`multimedia data. The server (21) has three component
`processes: the server control (1) Which interfaces With the
`
`storage subsystem (12) and With the netWork interface Similar to the packet buffer (31) in the client agent (30), a
`stream buffer (11) in the server control (1) holds the data that
`has been read from the storage subsystem (12). The stream
`buffer (11) serves as a temporary data storage center for the
`server control
`The interactions betWeen the server control (1) and the
`client agent (30) go through the netWork connecting the tWo
`machines. The netWork interface (2) in the server (21) and
`the netWork interface (3) in the client machine (20) support
`netWork connectivity. Speci?cally, the present embodiment
`uses tWo logical connections. The control channel (5) serves
`to exchange control messages. The data channel (6) serves
`to transmit multimedia data from the server (1) to the client
`agent (30). One possible implementation Would use a reli
`able TCP protocol line for the control channel, and a fast and
`mostly reliable UDP protocol for the data channel.
`FIG. 2 schematically represents the preferred detailed
`structure of the client agent (30). As depicted in FIG. 1, the
`client agent (30) interfaces With the netWork interface (3)
`and the multimedia application
`TWo execution paths
`exist, one for data and one for control messages. The data
`execution path starts from the data receiver (32), Which
`receives incoming data packets from the netWork. Then the
`data receiver (32) signals the buffer manager (38) to place
`the data packets properly into the structure of the packet
`buffer (33). The application interface (35) accesses the
`multimedia application 4 and translates its commands to the
`client controller 36. The output processor (34) delivers data
`to the multimedia application 4. The packet buffer (33)
`stores data packets until the multimedia application requests
`that they be delivered to the multimedia application
`If
`the packet buffer (33) does not have the requested data
`available, the client controller (36) signals the command
`processor (37) to send a command packet (a packet of
`information making a speci?c request) to the server control
`(1 in FIG. 1) for immediate retrieval of the requested data.
`The command processor (37) sends out the command packet
`via the control channel (5 in FIG. 1) and through the netWork
`interface
`
`15
`
`25
`
`35
`
`45
`
`55
`
`5,822,524
`
`6
`The buffer manager (38) manages the structure of the data
`in the packet buffer (33). FIG. 3 describes in detail the
`structure of the packet buffer (33). As to the amount of data,
`ideally the packet buffer (33) should have enough data:
`to
`minimiZe the possibility of not having the requested data,
`and (ii) still have enough free buffer space (memory space)
`to receive neW data packets. “Water Marks” regulate the
`server’s transmission rate thereby balancing betWeen these
`tWo con?icting factors. Three transmission modes are
`de?ned: NORMAL, RUSH, and PAUSE. Based on the
`amount of data in the packet buffer (33) the client agent (30)
`decides Which is the appropriate mode. When a change
`
`
`
`occurs, the client agent (30) informs the server control The client agent (30) changes the transmission mode based
`
`on a series of rules, explained beloW.
`To understand these rules, one must ?rst understand the
`“Water Mark” model. This model draWs a parallel betWeen
`the client agent buffer and a Water bucket With a spout at the
`bottom that brings Water to a person. Water entry
`(Application Data Unit, ADU entry) occurs intermittently.
`For example, other netWork traf?c could sloW ADU entry, or
`a collision sequence in the Ethernet, could stop it entirely.
`Assuming the bucket (client agent packet buffer) never
`empties, Water exits from the spout at a constant rate.
`Continuing the bucket analogy, the bucket constitutes a set
`of frames in the packet buffer (33) Which is the cache
`(temporary memory, generally RAM) used by the client
`agent. The bucket has high and loWer “Water marks”. In the
`just-in-time retrieval method, When the amount of data falls
`betWeen the Water marks, transmission occurs in NORMAL
`mode. In the present invention the transmission should be in
`NORMAL mode most of the time. For example, the packet
`buffer Will normally store 1—5 frames of video. In this mode
`the server (1) paces its transmission so that the data for a
`single video frame is transmitted in the time of a single video
`frame (normally 1/30 second), as FIG. 6 Will discuss in detail.
`Transmission occurs very ef?ciently in this NORMAL mode
`because no need exists for the client agent (30) to send
`periodic feedback to the server control
`Transmission enters PAUSE mode When the amount of
`data exceeds the high Water mark, i.e., there is too much data
`in the client agent packet buffer (33). Transmission occurs in
`RUSH mode When the amount of data falls beloW the loWer
`Water mark, i.e., there is not enough data in the client agent
`packet buffer (33). The client agent (30) sends a
`“NORMAL-TO-RUSH” command if the amount of data
`decreases beloW the loW Water mark. The client agent (30)
`sends a “NORMAL-TO-PAUSE” command if the amount of
`data increases above the high Water mark. The client agent
`sends a “PAUSE-TO-NORMAL” command if the amount of
`data decreases from above to beloW the high Water mark.
`The client agent (30) sends a “RUSH-TO-NORMAL” com
`mand if the amount of data increases from beloW the loWer
`Water mark to above the loW Water mark.
`FIG. 3 schematically represents the structure of the packet
`buffer (33). Each data packet contains a packet header (53)
`and the multimedia data (60). The packet header (53) should
`contain at least the folloWing ?ve elements of information
`(54):
`Pkt. Seq. No: a unique packet sequence number
`Frame No.: the video frame number to Which the data in
`the packet belongs
`InFrame Seq. No: the sequence number of the packets
`Within the same frame, e. g., 1 is for the ?rst packet of a video
`frame, 2 the second, and so on, and 0 is the last packet of the
`frame
`
`65
`
`Page 10 of 15
`
`PETITIONERS' EXHIBIT 1014
`
`

`

`5,822,524
`
`7
`Offset: ?le offset of the ?rst data byte in the packet
`Size: the number of data bytes in this packet.
`The transmission scheduler sets these data during
`packetiZation, as FIG. 6 discusses in detail. The data queue
`(52) organizes the packets by putting them in a speci?c
`order; the packets are sorted according to the “offsets” of the
`data. “Offset” is a number representing the relative position
`of a byte, generally in regard to the start of a ?le. The buffer
`manager maintains the packet structure until delivering the
`data to the applications. TWo consecutive packets in the
`buffer need not have contiguous ?le offsets. For example, the
`user may select ?le portions Which are not in order, i.e., one
`minute of video from the start of a video clip folloWed by
`one minute from the end of the clip. Therefore the ?le offset
`must be explicitly checked before delivering a data packet to
`the multimedia application
`OtherWise an incorrect set of
`data may be delivered to the multimedia application
`Fast and mostly reliable UDP-like channels transmit data
`packets. At some netWork nodes, packets may be lost, for
`example, due to line noise or buffer over?oW. In one
`error-free embodiment the lost packets are traced and
`replaced and in another embodiment, not error-free, there is
`no attempt to replace lost packets.
`To detect lost packets, in an error-free embodiment, the
`client agent (30) uses a register to maintain a variable Last
`Pkt. Seq. No. (51), Which is the packet sequence number of
`the last received packet. If the Pkt. Seq. No. of the neWly
`arriving packet denoted as NeW Pkt Seq No differs from
`(Last Pkt. Seq. No. +1), then a packet loss has occurred.
`Speci?cally, the packets With Pkt. Seq. No.’s from (Last Pkt.
`Seq. No. +1) to (NeW Pkt. Seq. No. —1) have been lost.
`To deal With packet loss, the client agent (30) maintains
`a list of lost packets (56) in a linked list or other data
`structure. That list records the tWo most important pieces of
`information about the lost packet, namely, its Pkt. Seq. No.
`and Time Out Value (57). When the client agent (30) sends
`the “retransmission request” for lost packets to the server
`control (1) the Time Out Value is set. If the missing data
`packet arrives correctly before the Time Out Value expires,
`this removes that data packet from the list. If not, the client
`agent (30)
`either sends another “retransmission request”
`to the server control (1) or (ii) gives up on obtaining the
`missing data packet and removes its number from the lost
`packet list.
`While providing data to the multimedia applications (40)
`the client agent (30) also monitors the characteristics of
`those applications. The frametime (55) and Ave. Data Rate
`(50) registers record the application’s tWo most important
`characteristics, Which are
`average frame time and (ii)
`average data rate. In one embodiment, such monitoring is
`executed for each frame, i.e., executing the monitoring When
`the delivered packet has In Frame Seq. No. equal to Zero. If
`these tWo average data rates differ signi?cantly from the
`expectation of the server, Which is transmitted to the client
`agent (30), the client agent (30) sends the corresponding
`commands, i.e., Frame Time Req. and Data Rate Req. to the
`server control
`To support regulation of the transmission pace With the
`amount of data in the packet buffer as described in connec
`tion With FIG. 2, the client agent (30) also maintains the Tx.
`Mode (58) and Data Queue SiZe (59) registers.
`The design of the client agent provides ef?ciency and
`reliability in the transmission and display of multimedia
`?les. A multimedia ?le may be played, i.e., displayed, in a
`variety of fashions. Some applications (or printing of a
`multimedia ?le) require error-free data, While some other
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`8
`applications require constant and minimum transmission
`latency (delay) at the expense of losing a small amount of
`packets, i.e., the transmission need not be error-free. The
`client agent (30) With its direct interfaces to the applications,
`can respond to the requirement of each application. The
`client agent provides only the support required by the
`application. Speci?cally, the design of the client agent (30)
`alloWs the client agent to
`eliminate unnecessary protocol
`overhead (Wasted memory and processing resources due to
`r