`Chen et al.
`
`USOO5822524A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,822,524
`Oct. 13, 1998
`
`54 SYSTEM FOR JUST-IN-TIME RETRIEVAL
`OF MULTIMEDIA FILES OVER COMPUTER
`NETWORKS BY TRANSMITTING DATA
`RESSENSEATE
`
`(75)
`
`Inventors: Huey-Shiang Chen; Mon-Song Chen,
`both of Katonah, N.Y.; Shiow-Laang
`Huang, Herndon, Va.; Deyang Song,
`Oradell, N.J.
`Assignee: InfoValue Computing, Inc., Elmsford,
`N.Y.
`
`Appl. No.: 505,488
`Filed:
`Jul. 21, 1995
`Int. Cl. .................................................... G06F 13/00
`U.S. Cl. ......................................................... 395/200.33
`Field of Search ............................... 395/600, 200.33,
`395/200.47, 200.49, 200.61, 200.76; 358/468;
`370/60.1, 84, 94, 60,364/200; 360/73;
`235/375; 381/41; 375/13, 357; 348/7, 10,
`12, 13, 14
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1977 Mack et al. ............................. 370/316
`4,001,690
`4,027,337 5/1977 De Loye et al. ......................... 360/73
`4,051,530 9/1977 Kuroda et al. ...
`... 348/415
`4,606,044 8/1986 Kudo ......................................... 375/13
`4,630,196 12/1986 Bednar, Jr. et al. ..
`... 364/200
`4,729,020 3/1988 Schaphorst et al. ..
`... 358/133
`4,833,535 5/1989 Ozeki et al. ..........
`... 348/400
`4,839,891
`6/1989 Kobayashi et al. ....................... 370/94
`5,025,457 6/1991 Ahmed ..............
`... 370/507
`5,029,164
`7/1991 Goldstein et al.
`... 370/235
`5,126.845
`6/1992 Yamashita .....
`... 358/160
`5,136,655 8/1992 Bronson .................................... 381/41
`5,208.810 5/1993 Park ..............
`... 370/230
`5,237,156 8/1993 Konishi et al. ...
`... 235/375
`5,262,875 11/1993 Mincer et al. .............................. 348/6
`5,319,638 6/1994 Lin ............................................ 370/60
`5,428,774 6/1995 Takahashi et al.
`... 395/600
`5,446,734 8/1995 Goldstein ..
`... 370/397
`5,457,687 10/1995 Newman ................................. 370/232
`
`
`
`5,463,422 10/1995 Simpson et al. ........................ 348/390
`5,491.565 2/1996 Naper ...................................... 358/468
`5,491,801
`2/1996 Jain et al. ...
`395/200.71
`5,497,404 3/1996 Grover et al. .......................... 375/357
`5,515,511 5/1996 Nguyen et al. .................... 395/200.49
`5,521,630 5/1996 Chen et al. ................................. 348/7
`5,533,021
`7/1996 Branstad et al.
`370/60.1
`5,541,919 7/1996 Yong et al. .....
`... 370/61
`5,544,170 8/1996 Kasahara .....
`... 370/253
`5,550,982 8/1996 Long et al.
`395/200.13
`5,566,175 10/1996 Davis ........................................ 370/84
`5,583,561 12/1996 Baker et al. ................................ 348/7
`5,621,660 4/1997 Chaddha et al.
`395/200.77
`5,633,859 5/1997 Jain et al. ............................... 370/234
`5,644,355 7/1997 Koz et al. .......
`... 348/17
`5,666,161 9/1997 Kohiyama et al.
`348/408
`5,721,878 2/1998 Ottesen et al. .............................. 348/7
`
`FOREIGN PATENT DOCUMENTS
`
`62-299148 12/1987 Japan ............................. HO4L 13/OO
`02-092153 3/1990 Japan.
`... HO4N 1/32
`03-133255 6/1991 Japan.
`... HO4N 1/32
`04-72838 3/1992 Japan.
`... HO4L 7/OO
`06-014080 1/1994 Japan ............................. HO4L 29/06
`Primary Examiner Moustafa M. Meky
`Attorney, Agent, or Firm Eliot S. Gerber
`57
`ABSTRACT
`A method in computer networks in which a client machine
`(playback client computer) requests multimedia files, Such
`as compressed video clips, from a server (storage server
`computer). The transmission uses digital data packets. In the
`case of Video files, 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
`byte Stream or an average of bytes to be transmitted. Instead,
`in the case of Video, the frame rate determines 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 filled within its normal range. The timing
`information required for transmission, in one embodiment,
`is Stored in a separate indeX file associated with each
`multimedia file.
`
`42 Claims, 6 Drawing Sheets
`
`Petitioners' Exhibit 1027
`Page 0001
`
`
`
`Oct. 13, 1998
`Oct. 13, 1998
`
`Sheet 1 of 6
`Sheet 1 of 6
`
`U.S. Patent
`
`U.S. Patent
`
`
`
`5,822,524
`5,822,524
`
`Petitioners’ Exhibit 1027
`Page 0002
`
`Petitioners' Exhibit 1027
`Page 0002
`
`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 2 of 6
`
`5,822,524
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Command
`Processor
`
`Client
`Controller
`
`Application
`Interface
`
`Network Interface
`
`Data
`Receiver
`
`
`
`Output
`Processor
`
`Multimedia Application
`
`4
`
`FG.2
`
`Petitioners' Exhibit 1027
`Page 0003
`
`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 3 of 6
`
`5,822,524
`
`(525
`
`25/.
`
`a3
`
`A9
`worn 1
`NLD, cer
`
`22
`
`Data Queue
`
`s
`
`PktSeqNo
`FrameNo
`InFrameSeqNo
`Offset
`Size
`
`
`
`52 List of lost Pkt
`
`Y
`
`M
`V 7
`
`
`
`27, 7
`o PktSeqNo
`o TineOutValue
`
`FG.3
`
`Petitioners' Exhibit 1027
`Page 0004
`
`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 4 of 6
`
`5,822,524
`
`
`
`as s as ss e g
`
`p
`
`v
`
`S.
`
`Co o
`
`Frane
`Time
`
`d
`
`a
`
`as s s a
`
`a a E.
`
`Timing
`Information
`
`g
`
`as
`
`e a pigs as a v
`O. :
`S ..."
`
`...--
`
`Frane
`
`Data 65
`
`s p we e s
`
`A.
`CP
`
`... Data
`Packet 66
`
`Petitioners' Exhibit 1027
`Page 0005
`
`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 5 of 6
`
`5,822,524
`
`JOSS3301&
`
`pupuuuu00
`
`IOSS3001&
`
`
`
`23ejons LZ/
`
`
`
`33eguguI \IOAA13N
`
`(~~~~
`
`
`
`
`
`uoissiusuell No.g/
`
`Petitioners' Exhibit 1027
`Page 0006
`
`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 6 of 6
`
`5,822,524
`
`
`
`
`
`
`
`
`
`
`
`
`
`TxMode=NORMA
`&FrameTxTime a
`Current Tine
`
`InFrameTx = True
`
`InFrameTx = False
`o Adjust Time to Tx of
`the next frame
`Read one more frame
`from the disks
`
`Exit
`
`FG.6
`
`Petitioners' Exhibit 1027
`Page 0007
`
`
`
`5,822,524
`
`1
`SYSTEM FOR JUST-IN-TIME RETRIEVAL
`OF MULTIMEDIA FILES OVER COMPUTER
`NETWORKS BY TRANSMITTING DATA
`PACKETS AT TRANSMISSION RATE
`DETERMINED BY FRAME SIZE
`
`15
`
`2
`for example, has data rates (rates of information flow) 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 configurations in a data
`network. In those configurations, 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
`file'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.
`
`FIELD OF THE INVENTION
`The present invention relates to methods for retrieval of
`multimedia files, Such as Video, Over computer networks.
`BACKGROUND OF THE INVENTION
`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-profit 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 floor 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 files. 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 files 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 films in video form (90-180 minutes). A plurality of
`users may simultaneously retrieve their preferred Video
`features at their Selected viewing times.
`Multimedia computing has significantly greater process
`ing power and Storage requirements than computing that
`only involves text and numeric data. Typical motion video,
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners' Exhibit 1027
`Page 0008
`
`
`
`3
`Due to their isochronous property (regular timing of a
`Stream), transmission of multimedia data files 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 fixed intervals (fixed
`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 files 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 specific amount of
`information-carrying capacity reserved for its use. While
`these approaches provide Some improvement, they still treat
`a multimedia file 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 efficient to treat
`a multimedia file 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 flow 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 flow. A need exists for an efficient 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 flexibility in Satisfying a
`variety of application requirements, with the final 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 Sufficient
`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 files 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 files from a Server computer to a client computer
`over computer networks.
`In the preferred embodiment the server transmits the
`multimedia file in the form of digital data packets. The
`transmission rate is based on the frame rate of the file. 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 Specified in the multi
`media file. Multimedia data streams have well-defined
`building blocks (objects) which should be the basis for
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,822,524
`
`4
`transmission timing in order to insure playback quality. In
`MPEG-1 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 file to (i) 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 flexibility 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 fine-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 files
`according to a fixed 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 /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
`Specified in multimedia files,
`FIG. 5 is a schematic illustration of the design of the
`Server; and
`FIG. 6 is a schematic illustration of the transmission
`Scheduling algorithm.
`
`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)
`
`Petitioners' Exhibit 1027
`Page 0009
`
`
`
`5,822,524
`
`15
`
`25
`
`35
`
`40
`
`S
`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 files 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 (4). 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 (2).
`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 (1).
`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. Specifically, 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 (4). 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 (4). 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 specific 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 (3).
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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: (i) 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 conflicting factors. Three transmission modes are
`defined: 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 (1).
`The client agent (30) changes the transmission mode based
`on a Series of rules, explained below.
`To understand these rules, one must first 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 traffic 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 /30 second), as FIG. 6 will discuss in detail.
`Transmission occurs very efficiently in this NORMAL mode
`because no need exists for the client agent (30) to send
`periodic feedback to the server control (1).
`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 five 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 first packet of a Video
`frame, 2 the Second, and So on, and 0 is the last packet of the
`frame
`
`Petitioners' Exhibit 1027
`Page 0010
`
`
`
`7
`Offset: file offset of the first 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 specific
`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 file. The buffer
`manager maintains the packet Structure until delivering the
`data to the applications. Two consecutive packets in the
`buffer need not have contiguous file offsets. For example, the
`user may select file 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 file offset
`must be explicitly checked before delivering a data packet to
`the multimedia application (4). Otherwise an incorrect set of
`data may be delivered to the multimedia application (4).
`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 overflow. 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.
`Specifically, 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) (i) 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 (i) 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 Significantly 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 (1).
`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 efficiency and
`reliability in the transmission and display of multimedia
`files. A multimedia file may be played, i.e., displayed, in a
`variety of fashions. Some applications (or printing of a
`multimedia file) require error-free data, while Some other
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,822,524
`
`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. Specifically, the design of the client agent (30)
`allows the client agent to (i) eliminate unnecessary protocol
`overhead (wasted memory and processing resources due to
`redundant computing instructions) embedded in typical
`transport protocols (data transmiss