United States Patent (19)
`Wang et al.
`
`54 SYSTEM, DEVICE, AND METHOD FOR
`STREAMING AMULTIMEDIA FILE
`ENCODED AT AWARIABLE BITRATE
`
`75 Inventors: Feng Chi Wang, Newton; Thomas
`Goetz, Attleboro; Krystyna
`Wieckiewicz, Plainville, all of Mass.
`73 Assignee: Motorola Inc., Schaumburg, Ill.
`
`21 Appl. No.: 885,271
`22 Filed:
`Jun. 30, 1997
`
`Related U.S. Application Data
`63 Continuation-in-part of Ser. No. 711,701, Sep. 6, 1996.
`51) Int. Cl. ............................... H04N 7/26; H04N 7/52;
`H04N 7/56; H04N 7/62
`... 348/845; 348/423
`-
`58 Field of Search ................................. 348/845, 845.2,
`348/845.3, 423, 12, 13; HO4N 7/26, 7/52,
`7/56, 7/62
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`1/1996 Cash ..................................... 348/845.2
`
`5,481,312
`
`USOO586723OA
`Patent Number:
`11
`(45) Date of Patent:
`
`5,867,230
`Feb. 2, 1999
`
`5,612,742 3/1997 Krause .................................... 348/385
`5,659,539 8/1997 Porter.
`... 348/13
`5,768,539 6/1998 Metz ....................................... 348/385
`5,790,543 8/1998 Cloutier .................................. 348/423
`
`Primary Examiner-Howard Britton
`Attorney, Agent, or Firm-Peter Dichiara
`57
`ABSTRACT
`System, Device, And Method For Streaming A Multimedia
`File Encoded at a Variable Bitrate. The data is encoded at a
`variable bit rate and formed into packets having a Server
`time Stamp. The Server time Stamps are constructed So that
`the Streaming of the packets will be Substantially constant,
`not variable, and equal to a desired, budgeted bandwidth,
`Such as one corresponding to fully utilizing a modem link.
`To Schedule the Sending of packets, the Server uses the Server
`time Stamp, rather than, for example, the play-back time
`Stamp. By having the data encoded at a variable bit rate, the
`otherwise-unused capacity, i.e., the capacity not used by the
`Server, can be used to Send packets needed in the future. This
`is accomplished by the Server time Stamps Scheduling pack
`ets for transmission that will not be needed until the future.
`
`2 Claims, 8 Drawing Sheets
`
`
`
`PACKET OFFSET
`
`TIME STAMP
`
`PACKET LENGTH
`
`IMPORTANCE
`
`RESERVED
`
`SEND TIME
`
`Petitioners' Exhibit 1009
`Page 0001
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 1 of 8
`
`5,867,230
`
`11O
`
`TO
`VIDEO
`MULTIPLEX
`CODER
`
`VIDEO
`IN
`
`
`
`PACKET LENGTH
`
`IMPORTANCE
`
`RESERVED
`
`SEND TIME
`
`A/VG.. 6
`
`Petitioners' Exhibit 1009
`Page 0002
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 2 of 8
`
`5,867,230
`
`OOZ
`
`L- - - - - - - - -
`
`TlOH.] NOOEl LV/H_LIE
`
`
`
`
`HETTIOHI NOO
`
`
`
`
`
`092
`
`OL
`
`XI}JONALEN
`
`HEAHES
`
`HETTIOHINOO
`
`NI OEC?IA
`
`Petitioners' Exhibit 1009
`Page 0003
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 3 of 8
`
`5,867,230
`
`START
`
`3OO
`
`NIT
`
`310
`
`399
`
`32O
`
`N
`
`MORE BLKS2
`
`
`
`Y
`
`33O
`
`INCREMENT FRAME
`NUMBER BY FRAMES
`SKIPPED
`
`
`
`
`
`
`
`ENCODE
`CURRENT FRAME
`(FRAMENUMBER)
`
`340
`
`INCREMENT
`BITBACKLOG
`
`350
`
`FRAMESSKIPPED =
`MIN FRAMES
`SKPPED
`
`360
`
`DECREMENT
`BTBACKLOG
`
`370
`
`AVG. 34 N/
`
`N/
`
`Petitioners' Exhibit 1009
`Page 0004
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 4 of 8
`
`5,867,230
`
`
`
`
`
`
`
`
`
`DOES FRAMES
`SKIPPED NEED
`ADJUSTMENT
`
`DECREMENT
`BTEBACKLOG
`
`INCREMENT FRAMES
`SKIPPED
`
`A/VG. 3A
`
`Petitioners' Exhibit 1009
`Page 0005
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 5 of 8
`
`5,867,230
`
`
`
`RECEIVE USER
`VALUE OF OUANT
`
`|MT OUANT WITHIN
`MAX AND MIN
`VALUES
`
`ADJUST
`MAX FRAMES
`SKPPED IN VIEW OF
`OUANT
`
`ADJUST
`MIN FRAMES
`SKIPPED IN VIEW OF
`CRUANT
`
`ADJUST VALUES FOR
`HIGH TARGET RATES
`
`A77G. 4
`
`Petitioners' Exhibit 1009
`Page 0006
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 6 of 8
`
`5,867,230
`
`STAR
`
`5OO
`
`INITIALIZE BIT
`COUNT &
`TIME STAMP
`
`51O
`
`
`
`
`
`515
`
`MORE
`FRAMESP
`
`599
`
`END
`
`GET NEXT
`FRAME
`
`520
`
`
`
`FILL PACKET
`
`53O
`
`
`
`
`
`INSERT SERVER 540
`TMESTAMP
`INTO PACKET
`
`Az7G. a 4.
`
`Petitioners' Exhibit 1009
`Page 0007
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 7 of 8
`
`5,867,230
`
`SAVE PACKET 550
`TO FILE
`
`UPDATE
`BIT COUNT BY
`PACKET SIZE
`
`56O
`
`
`
`UPDATE TIME
`STAMP VALUE
`
`570
`
`
`
`
`
`NEED ADDITIONAL
`PACKET FOR FRAME?
`
`AVG. A.A.
`
`Petitioners' Exhibit 1009
`Page 0008
`
`

`

`U.S. Patent
`
`Feb. 2, 1999
`
`Sheet 8 of 8
`
`5,867,230
`
`7OO
`
`START
`
`799
`
`END
`
`710
`
`CONTINUE
`STREAMNG?
`
`
`
`
`
`72O
`
`STREAM A TIME
`SLICE OF PACKETS
`
`735
`
`GO TO SLEEP
`
`Az7G. Z.
`
`Petitioners' Exhibit 1009
`Page 0009
`
`

`

`1
`SYSTEM, DEVICE, AND METHOD FOR
`STREAMING AMULTIMEDIA FILE
`ENCODED AT AWARIABLE BITRATE
`
`This application is a continuation-in-part of the following
`co-pending application, which is assigned to the assignee of
`this application and which is incorporated by reference
`herein
`System, Device, And Method For Streaming A Multime
`dia File (Ser. No. 08/711,701, to Tom Goetz, Manickam
`R. Sridhar, and Mukesh Prasad, filed on Sep. 9, 1996).
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`This application is related to the following U.S. patent
`applications, all of which are assigned to the assignee of this
`application and all of which are incorporated by reference
`herein:
`Improved Video Encoding System And Method (Ser. No.
`08/711,702, to Manickam R. Sridhar and Feng Chi
`Wang, filed on Sep. 9, 1996);
`Apparatus, System, and Method for Improved Error
`Recovery in a Video Encoding System (Ser. No.
`08/741,455, to Feng Chi Wang, filed on Oct. 31, 1996);
`and System and Device for, and Method of, Encoding
`Video Information for Improved Streaming Thereof,
`filed on even date herewith, having inventor Feng Chi
`Wang Ser. No. 08/885,076.
`BACKGROUND
`1. Field of the Invention
`The invention generally relates to multimedia applica
`tions and, more particularly, to the encoding and Streaming
`of Video information over a communication network.
`2. Discussion of Related Art
`Generally Speaking, there are two modern approaches to
`"playing-back’ multimedia information located at a remote
`location, Such as playing-back a “video clip' on the Internet.
`The first approach is to have a client node download a file
`having the Video information from a corresponding
`“website,” or server node, and to then play-back the
`information, once the file has been completely transferred.
`The second approach is to have the sever node “stream” the
`information to the client node So that the client may begin
`play-back Soon after the information Starts to arrive. Because
`the Streaming approach does not Suffer from the long Start-up
`delays inherent in the downloading approach, it is believed
`to be preferable in certain regards.
`It is believed that a Substantial number of remote access
`users, Such as Internet users, access the network via a
`Voiceband modem. To this end, various communication
`standards have been proposed. H.261 and H.263, for
`example, each Specify a coded representation that can be
`used for compressing video at low bitrates. (See ITU-T
`Recommendation H.263 of 2 May 1996, which is hereby
`incorporated by reference in its entirety.)
`Because typical voiceband modems have maximum data
`rates of less than 56 Kb/s, the quality of a streamed play
`back depends on how effectively the channel is used. Tru
`eStream TM Streaming Software, version 1.1, for example,
`keeps the channel at full utilization to improve the play
`back's appearance. (TrueStream TM Streaming Software, ver
`sion 1.1, is available from Motorola, Inc.)
`In short, with version 1.1 of the TrueStream TM Streaming
`Software, a target data rate is first Selected, for example, 20
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,867,230
`
`2
`Kb/sec for a 28.8 Kb/sec modem, the other 8.8 Kb/sec of
`bandwidth being Saved for audio information and packet
`overhead. If a Sequence of Video frames is to be encoded and
`because of its inherent informational content the Streaming
`of the encoded data would require a data rate higher than the
`target rate, then the TrueStreamTM system adjusts certain
`encoding parameters So that encoded frames require leSS
`bits. On the other hand, if a Sequence of Video frames is to
`be encoded such that the streaming of it would not fully
`utilize the channel, the TrueStreamTM system applies a “use
`it or lose it” approach and adjusts certain encoding param
`eters to improve the Video quality and So that the channel
`capacity is used. The consequence of the above is that in the
`former case the Sequence will be played-back with pictures
`having a relatively coarser level of detail and a relatively
`Smaller frame rate, and that in the latter case, the Sequence
`will be played-back with pictures having a finer level of
`detail and a higher frame rate.
`BRIEF DESCRIPTION OF THE DRAWINGS
`In the Drawing,
`FIG. 1 shows a standard source encoder 100 having a
`known architecture;
`FIG. 2 shows a System architecture of an exemplary
`embodiment of the invention;
`FIGS. 3A-B are a flowchart of bitrate controller logic of
`an exemplary embodiment of the invention;
`FIG. 4 is a flowchart of a portion of the bitrate controller
`logic of FIG. 3 in more detail;
`FIGS. 5A-B are a flowchart of packetizer logic of an
`exemplary embodiment of the invention;
`FIG. 6 shows an exemplary packet descriptor of an
`exemplary embodiment of the invention; and
`FIG. 7 shows exemplary server logic of an exemplary
`embodiment of the invention.
`
`DETAILED DESCRIPTION
`The invention involves a System and device for, and a
`method of, encoding information for improved Streaming
`thereof.
`Exemplary embodiments of the invention encode video
`information at variable bitrates and by doing So can utilize
`the channel in new and useful ways. For example, if the
`informational content of certain Video frames can be
`encoded at a relatively low bitrate, the otherwise-unused
`channel capacity can be used to transmit information that
`will be needed for future video frames. This might be helpful
`in that a future portion of a Video Stream might require So
`much data that it might otherwise have been Streamable only
`by Sacrificing the quality of its play-back.
`The exemplary embodiments are particularly concerned
`with video information encoded according to H.263. Thus,
`material aspects of H.263 are outlined below, followed by a
`description of the exemplary embodiments.
`I. Outline of H.263
`A video Sequence is encoded and decoded as a Sequence
`of frames or pictures. Each picture is organized as groups of
`blocks (GOBs), macroblocks, and blocks, and each picture
`may be of a variety of picture formats and Subformats. In
`addition, each picture may be of INTER type, also known as
`an “I” frame, or INTRA type, which includes entities known
`as “P” frames and “PB frames.
`An "I' frame is independent in that it represents a
`complete image, or portion of an image. Its encoding and
`decoding has no dependencies on prior frames. With “P” and
`“PB” frames, on the other hand, the encoding and decoding
`depends on prior frames. P and PB frames may be thought
`
`Petitioners' Exhibit 1009
`Page 0010
`
`

`

`5,867,230
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`15
`
`3
`of as an encoded representation of the difference between
`one picture and a prior picture.
`FIG. 1 shows a standard source encoder 100. Coding
`controller 110, among other things, controls Switches 120
`and 130 and quantizer Q. In short, the controller 110 controls
`the Sampling rate, or frame rate, of the Video Sequence by
`Selecting particular frames of Video In, and it controls the
`level of detail of each encoded picture by Supplying quan
`tization parameters qZ to quantizer Q. The output informa
`tion q is a compressed version of a picture: an I frame is
`a compressed version of a current picture, or portion thereof,
`and a P or PB frame is a compressed version of difference
`information, representing the difference between the current
`picture, or portion thereof, and the last.
`For I frame blocks, coding controller 110 connects Switch
`120 to input 121 and switch 130 to input 131. Thus, Video
`In is connected to the transform block T, which processes the
`data according to a known discrete cosine transform (DCT).
`The transformed data, known as transform coefficients, are
`then quantized by quantizer Q, and the quantized informa
`tion q is received by inverse quantizer Q. The inverse
`quantized information, in turn, is received by inverse trans
`form T, and the inverse transformed information is
`received by Summation node 140. Consequently, Summation
`node 140 adds unconnected input 131 and the reconstituted
`picture information from the inverse transform T, the
`reconstituted picture information being the picture Video In
`after it has been transformed, quantized, inverse quantized,
`and inverse transformed. The output of the Summation node
`140 is thus the reconstituted picture information, which is
`Stored in picture memory P.
`For P or PB type blocks, coding controller 110 controls
`Switches 120 and 130 to connect to inputs 122 and 132,
`respectively. Difference node 150 produces the difference
`between the current block, Video In, and the prior, recon
`stituted block, provided by picture memory P. This differ
`ence information is then transformed (T), quantized (Q),
`inverse quantized (Q'), and inverse transformed (T)
`analogously to that described above. The information pro
`vided by inverse transform (T), in this arrangement,
`however, is not the reconstituted picture, but rather the
`reconstituted difference information originally provided by
`difference node 150. Summation node 140 adds the recon
`stituted difference information to the prior block, provided
`by input 132, to yield a reconstituted version of the current
`picture, which is Stored in picture memory P.
`The compression gains achieved by the above arrange
`ment result from the Statistical nature of Video information
`and from the quantization rules. In particular, a given pixel
`in one frame is likely to be the same or nearly the Same as
`a corresponding pixel of a prior frame. Moreover, pixels
`having no difference from one picture to the next tend to run
`contiguously So that many adjacent pixels might be identical
`to the corresponding pixels of a prior frame. The H.263
`quantization rules address the above with a variety of
`techniques that can be Summarized by Stating that the more
`probable video information events require leSS encoded bits
`than the less probable events. (See ITU-T Recommendation
`H.263 of 2 May 1996, at 25–27, variable and fixed length
`codes for transform coefficients.)
`The amount of bits needed to represent a picture or block
`depends on three things: (a) whether the blocks are being
`encoded as INTER or INTRA type; (b) the informational
`nature of a block in relation to a prior block; and (c) the level
`of quantization used in the encoding. Typically, INTRA
`65
`based encoding requires less bits than INTER-based encod
`ing for a given frame, and coarser detail requires leSS
`
`4
`encoded bits than finer detail, everything else being equal.
`Thus, the selection of INTER or INTRA and the level of
`quantization are the only independent variables affecting the
`amount of data required to encode a given picture, Video In.
`II. Overview of a System and Device for, and Method of,
`Encoding Video Information for Improved Streaming
`Thereof
`FIG. 2 shows an exemplary system 200 for encoding and
`packetizing files of variable bitrate video data. Video. In is
`received by encoder 220, which encodes the information,
`under the control of coding control 225 and bitrate controller
`210. The encoded data 227 is received by packetizer 230,
`which is partially controlled by bitrate controller 210, and
`which packetizes the information into a Specified format to
`create a file 235. File 235 may then be used by server logic
`240 to stream the information over the network 250.
`
`a. Encoder and Controller
`Encoder 220 includes the elements of FIG. 1, except that
`the coding controller 110 of FIG. 1 is divided into controller
`225 and bitrate controller 210, discussed below. Controller
`225 includes control features known in the art as well as
`control features described in the related applications iden
`tified and incorporated above. (The application entitled
`Improved Video Encoding System And Method includes
`features that would control the bitrate of the data stream in
`a mutually-exclusive manner to that covered by the bitrate
`controller 210. Under one embodiment of the invention, a
`user input allows Selection between the two.)
`b. Bitrate Controller
`The bitrate controller 210 partially controls the encoding
`of Video. In so that it is encoded at an efficient, variable
`bitrate while also attempting to Satisfy Specified quality
`criteria. The actual amount of data needed to encode a
`picture, and thus the bitrate, will depend on the informa
`tional content of the Video frames. In an exemplary
`embodiment, the quality criteria are to keep the quantization
`level, or the level of detail, the same for all macroblocks
`within a picture and for all pictures in a Sequence.
`The instant approach implements a “use it or lose it”
`philosophy, but “uses” the otherwise-unused bandwidth in a
`novel way. In particular, when frames are encoded at a
`relatively low bitrate (i.e., less than the target rate or Encoder
`rate, e.g., 20 Kb/sec), the unused bandwidth is effectively
`conserved So that it may be used to transmit information
`corresponding to a future portion of the Video.
`Consequently, future portions of Video having a high infor
`mational content, and thus requiring a large amount of data
`for the encoding thereof, are more likely to be Streamable
`without Sacrificing quality of the picture and in any even if
`quality needs to be Sacrificed for the encoding leSS Sacrifice
`will be needed. (Quality in this sense refers to the quanti
`zation level, or the level of detail of the picture(s), and the
`frame rate, or the number of pictures eventually displayed
`per Second)
`FIGS. 3A-B are a flowchart describing an exemplary
`bitrate controller 210. An exemplary embodiment is imple
`mented as a modified version of Telenor H.263 encoder
`version 2.0. In this example, the variables are the ones used
`by the Telenor encoder.
`The logic begins at step 300 and proceeds to step 310,
`which initializes certain variables. In particular, Min
`Frames Skipped is set to 3; Max Frames Skipped is Set
`to 8; Frame Number is set to 0; Frames Skipped is set to
`0; BitBacklog is set to 0; and Delay Between Frames is
`
`Petitioners' Exhibit 1009
`Page 0011
`
`

`

`S
`set to /30. These variables and how they are used are
`discussed below. ASSume a target encoding rate (Encoding
`Rate) of 20 Kb/s, leaving extra bandwidth in a 28.8 Kb/s
`channel for audio data and for packet overhead.
`Besides the above, step 310 initializes a quantization
`parameter Quant and adjusts the frame rate limits Min and
`Max Frames Skipped as shown in FIG. 4. Quant refers to
`the pictures quantization level. A higher Quant means rela
`tively coarser detail; a lower Quant means relatively finer
`detail. The frame rate is adjusted dynamically in accordance
`with a variable Frames Skipped, but the amount of adjust
`ment is limited by Min and Max Frames Skipped, as
`will be described below.
`The Quant initialization and the frame rate limits adjust
`ment logic starts in step 400 and proceeds to step 410, which
`receives a user input indicating the level of quantization
`desired. This may be Supplied, for example, from Software
`that interprets a graphical user interface's slider bar control.
`The logic proceeds to Step 420, which limits the quantization
`variable Quant between a maximum and minimum value.
`For example, any received value greater than 30 may force
`Quant to 30, and any value less than 8 may force Quant to
`8. The logic proceeds to step 430 and 440, which analyze
`Quant and adjusts Max and Min Frames Skipped,
`accordingly. For example, in Step 430, relatively low values
`of Quant, in particular values less than 12, force Max
`Frames Skipped to 20. Thus, step 430 may be thought of
`forcing down the maximum frame rate for pictures having
`fine detail. Analogously, in Step 440, relatively high values
`of Quant, in particular values greater than 29, force Min
`Frames Skipped to 2. Thus, step 440 may be thought of
`forcing up the minimum frame rate for pictures having
`coarse detail. The above StepS use empirically determined
`values that were chosen to provide a relatively simple
`production environment. Obviously, many other values are
`applicable, and for environments, where increased user
`control makes Sense, these parameters may be set by the
`production user.
`Step 450 determines if the target rate is higher than 30
`Kb/s, as might be the case for PCM modems or ISDN
`connections or the like. If the target rate is higher, other
`adjustments are made. In particular, Min Frames Skipped
`is Set to 2, Min Frames Skipped is Set to 1, if Quant is
`higher than 28, and Max Frames Skipped is set to 17, if
`Quant is less than 12. Again this Step uses empirically
`determined values that were chosen to provide a relatively
`Simple production environment.
`The logic ends in step 499, which returns the flow back to
`the flowcharts of FIGS 3A-B.
`Referring back to FIGS. 3A-B, after step 310, the limits
`on the frame rate and the quantization parameters are Set.
`These values are used throughout the encoding. By main
`taining the quantization at a constant level, the amount of
`data necessary to encode the frame will depend on the
`informational content of the frame. Thus, the bitrate will
`vary as the informational content of frames vary. Moreover,
`perceptually the quality of the Video will remain Substan
`tially level, with Some fluctuation resulting from varying
`frame rates, as discussed below.
`The logic proceeds to step 320, which determines if more
`frames, or blocks, need to be encoded. If not, the logic
`proceeds to step 399, which ends the encoding process.
`If there are more frames and blocks to be encoded, the
`logic proceeds to step 330, which increments the Frame
`Number by a value equal to Frames Skipped. Frame
`Number identifies the frame of Video. In to be encoded, and
`Frames Skipped controls the frame rate.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,867,230
`
`6
`The logic proceeds to step 340, which encodes the current
`block, identified by Frame Number.
`The logic proceeds to step 350, which increments the
`variable BitBacklog by the number of bits used to encode the
`frame. BitBacklog effectively keeps a running total of the
`number of bits used in encoding the Sequence in comparison
`to the number of bits that can be sent up to the current time,
`i.e., a budgeted amount. The budgeted amount is not a hard
`budget in that slightly exceeding the budget is not fatal. An
`exemplary Server includes logic for Sending an initial burst
`of data to compensate for network jitter and the like, slightly
`exceeding the budget is essentially indistinguishable from
`jitter.
`The logic proceeds to step 360, which sets Frames
`Skipped to Min Frames Skipped. This is done as an initial
`attempt to encode the Video at a maximum frame rate. Thus,
`for a Min Frames Skipped of 2, the frame rate is 15
`(30/2); for a Min Frames Skipped of 3, the frame rate is
`10 (30/3). The numerator “30” in the preceding parenthetical
`Statements refers to the absolute maximum frame rate of
`H.263, which is about 30 frames per second.
`The logic proceeds to step 370, which adjusts BitBacklog
`in a manner to reflect the increment in time associated with
`the Streaming of the new frame corresponding to Frames
`Skipped. Namely, BitBacklog is adjusted to represent that
`the corresponding encoded data will not be Sent until Some
`time in the future as reflected by Frames Skipped. In
`particular, the BitBacklog decrements by an amount equal to
`the following:
`Frames Skipped target rate Delay Between Frames
`The logic proceeds to step 380, which determines whether
`Frames Skipped needs adjustment in view of BitBacklog.
`In particular, step 380 compares the BitBacklog to determine
`whether the encoding proceSS would be over a budgeted
`amount if a frame were encoded at the currently Set frame
`rate. In brief, if the encoding would be over budget,
`Frames Skipped is adjusted to decrease the frame rate until
`the minimum frame rate is reached or until the encoding
`process is within budget. In either case, the next frame is
`encoded and the process is repeated. If the above iteration is
`Stopped because the minimum frame rate is reached and the
`encoding proceSS is Still over budget, it is not necessarily
`fatal. This is So, because, as described above, the System can
`Slightly exceed budget due to the Server's logic for address
`ing network jitter and the like. In Such case, the next
`iterations of encoding frames may cause the encoding to
`catch up to the budget by continuing to minimize the frame
`rate.
`More specifically, the BitBacklog is compared to see if it
`is greater than or equal to the Encoder Rate multiplied by the
`Delay Between Frames, i.e., the highest possible amount of
`data that can be sent in the time Delay Between Frames.
`If BitBacklog is greater than or equal to that amount, the
`encoding would be over budget.
`If the encoding is under budget or if Frames Skipped is
`equal (or greater than) Max Frames Skipped then the
`logic proceeds to Step 320 to encode the next frame, as
`outlined above.
`If the encoding is over budget and if Frames Skipped can
`be adjusted higher without equaling or exceeding Max
`Frames Skipped, then the logic proceeds to step 385. In
`step 385, the BitBacklog decrements, this time however by
`an amount equal to the Delay Between Frames multiplied
`by the Encoder Rate. This decrement corresponds to holding
`off the encoding for another frame time slot, and is done in
`view of the following step 390.
`
`Petitioners' Exhibit 1009
`Page 0012
`
`

`

`7
`In step 390, Frames Skipped is incremented by one.
`Thus, the encoding of a frame is held off for one frame time
`slot. Thus the adjustment of BitBacklog by one Delay
`Between Frames. The logic loops back to step 380 to
`determine whether this dynamic adjustment of Frames
`Skipped (and thus the frame rate) has helped the encoding
`process fall within budget or if the minimum frame rate has
`been attained. The loop between 380 and 390 continues as
`necessary to adjust Frames Skipped, thereby decreasing the
`frame rate, and to adjust BitBacklog correspondingly until
`BitBacklog indicates the encoding proceSS is within budget
`or until Max Frames Skipped (or conversely the mini
`mum frame rate) is reached.
`c. Packetizer
`The packetizer 230 packetizes the encoded frames 227
`into a specified format to form a file 235 that may be used
`by server 240 to stream the contents thereof. Much of the
`details of the packetizer are discussed in the related
`applications, identified and incorporated above.
`In short, a new aspect of the packetizer is that it time
`Stamps the packets with a Server time Stamp. This Stamp may
`eventually be used by an exemplary Server to Schedule the
`Sending of packets containing the encoded data. The Server
`time Stamps are constructed Such that, if used by the Server
`240 to schedule the delivery of the packets, the channel will
`be used efficiently, and in a manner in which for a given time
`quanta the Video that is Sent may correspond not only to the
`data needed currently but also for data that will be needed in
`the future. All packets, in an exemplary embodiment, are
`Sent in order, but Some packets may be sent Sooner than
`needed.
`More specifically, the encoded video frames 227 are
`applied to packetizers 230. In Short, the packetizer arranges
`the encoded data in pre-packetized form with the necessary
`packet information, See for example, U.S. application Ser.
`Nos. 08/711,701 and 08/711,702, identified and incorpo
`rated above. For the most part, each video frame will have
`its own corresponding packet, Such as a UDP packet, but
`Some large frames may be divided up into Several packets.
`FIGS. 5A-B are a flowchart of exemplary packetizing
`logic. The logic begins at step 500 and proceeds to step 410,
`which initializes a server time stamp and Bit Count variable,
`each to Zero.
`The logic proceeds to step 515, which determines if more
`frames need to be packetized. If not, the logic proceeds to
`step 599, which ends the flow.
`If more frames need to be packetized, the logic proceeds
`to step 520, which gets the next encoded video frame 227,
`along with control information indicating the Encoder Rate,
`or target rate, for which the data is encoded.
`The logic proceeds to step 530 which constructs a UDP
`packet, filling it with the encoded Video and other informa
`tion. In this regard, the construction is analogous to that
`described in the above co-pending application U.S. patent
`applications.
`The logic proceeds to step 540, which inserts the server
`time Stamp within the packet, in particular, within a portion
`of the packet known as the packet descriptor. The packet
`descriptor is an entity used by an exemplary Server 240 to
`control Streaming. The time Stamp is Set to the following:
`BitCount/(1.1* Encoder Rate)
`The factor 1.1, which is empirically determined, is used to
`keep the modem at full capacity.
`The logic proceeds to step 550, which writes the video
`packet in a specified format to a file 235.
`
`8
`The logic proceeds to step 560, which increments the Bit
`Count by the size of the packet written to the file.
`The logic proceeds to step 570, which updates the server
`time Stamp. In particular, the Server time Stamp is updated by
`an amount equal to the Bit Count divided by the Encoder
`Rate.
`The logic proceeds to step 580, which determines if more
`packets are needed for the current frame. If So, the logic
`proceeds back to step 530. If not, the logic loops back to step
`515.
`(Other encoders, not shown, for example, an audio
`encoder, may encode and packetize information to be for
`matted into the eventual file 235.)
`d. File Format
`The related applications, identified and incorporated
`above, describe a multimedia file and method for forming
`Same. The same arrangement may be used in an exemplary
`embodiment, except that the packet descriptorS Should now
`include a separate field for holding the Server time Stamp.
`FIG. 6 shows an exemplary descriptor having Send time
`stamp 610. (The other fields are discussed in the co-pending
`applications.)
`
`e. Server
`Analogously, the related applications, identified and
`incorporated above, describe an exemplary System for Send
`ing multimedia files of the above type. Though the same
`arrangement may be used in an exemplary embodiment with
`the exception that the Server would use a Server time Stamp
`for the Scheduling of packets, an exemplary embodiment
`includes certain modifications to the embodiment described
`in the related applications.
`First, unlike the embodiments described in the related
`applications, an exemplary embodiment does not use
`retransmit logic (steps 1240-1260 of FIG. 12 and corre
`sponding text of the related applications). Second, an exem
`plary embodiment does not include the “throttle-up' and
`“throttle-down” logic of the related applications (FIG. 13
`and corresponding text of the related applications). Third, an
`exemplary embodiment does not include the calculation of
`“round-trip delay' as part of channel characterization.
`FIG. 7 is a flowchart of the exemplary server logic and is
`Somewhat similar to the flowchart of FIG. 12 of the related
`applications. Step 710 determines whether the server needs
`to send more packets. If not, the logic ends in step 799; if so,
`the logic proceeds to Step 720, which sends a time Slice's
`worth of packets. A time slice's worth is determined from
`looking at the server time stamp 610 in relation to the server
`Scheduling clock. (This step is analogous to the logic of the
`related applications, except the related application used the
`Same time Stamp for Server Scheduling and for play-back
`Scheduling) After sending a time slice's worth of packets,
`the logic goes to Sleep 730, informing the Scheduler of a
`corresponding wake-up time.
`An exemplary Server is able to Support file formats of the
`current type and of the type described in the related appli
`cations. In particular, the directory preamble, described in
`the related applications, is modified to include a descriptor
`Size field. The values Stored therein uniquiely distinguish
`between the two formats, informing the server which time
`Stamp should be used for Scheduling.
`III. Other Embodiments
`The above embodiment was primarily focused on video
`data according to H.263. Skilled artisans will appreciate that
`the above prin