(12) United States Patent
`Ravi et al.
`
`USOO6292834B1
`(10) Patent No.:
`US 6,292,834 B1
`(45) Date of Patent:
`*Sep. 18, 2001
`
`(54)
`
`(75)
`
`(73)
`
`DYNAMIC BANDWIDTH SELECTION FOR
`EFFICIENT TRANSMISSION OF
`MULTIMEDIA STREAMS IN A COMPUTER
`NETWORK
`
`Inventors: Hemanth Srinivas Ravi, Milpitas;
`Anders Edgar Klemets; Navin
`Chaddha, both of Sunnyvale; David de
`Val, Mountain View, all of CA (US)
`Assignee: Microsoft Corporation, Redmond, WA
`(US)
`This patent issued on a continued pros
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Notice:
`
`(21)
`(22)
`
`Appl. No.: 08/818,127
`Filed:
`Mar. 14, 1997
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`Int. Cl." ........................ G06F 15/167; G06F 15/173
`
`U.S. Cl. ........................... 709/233; 709/216; 709/225
`
`Field of Search ..................................... 370/232, 233,
`370/234, 236; 709/203, 207, 212, 216,
`217, 218, 219, 223, 224, 225, 231, 232,
`233, 102, 104, 105; 707/10
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,862.264
`4,931,950
`
`8/1989 Wells et al. .......................... 358/138
`6/1990 Isle et al. ............................. 364/513
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`Yuang, M.C. et al. “Dynamic Video Playout Smoothing
`Method for Multimedia Applications” IEEE ICC'96, 1996.*
`Feng, Wu-Chi et al. “A Comparison of Bandwidth Smooth
`ing Techniques for the Transmission of Prerecorded Com
`pressed Video” 16th Joint Conference of IEEE CCS, 1997.*
`(List continued on next page.)
`Primary Examiner Zarni Maung
`ASSistant Examiner Jason D. Cardone
`(74) Attorney, Agent, or Firm-Lee & Hayes, PLLC
`(57)
`ABSTRACT
`An efficient transmission protocol for transmitting multime
`dia Streams from a server to a client computer over a diverse
`computer network including local area networks (LANs)
`and wide area networks (WANs) such as the internet. The
`client computer includes a playout buffer, and the transmis
`sion rate is dynamically matched to the available bandwidth
`capacity of the network connection between the Server and
`the client computer. If a playtime of the playout buffer,
`which is one measure of the number of data packets cur
`rently in the playout buffer, drops below a dynamically
`computed Decrease Bandwidth (DEC BW) threshold,
`then the transmission rate is decreased by Sending a DEC
`BW message to the server. Conversely, if the number of
`packets remaining in the playout buffer rises above a
`dynamically computed Upper Increase Bandwidth (INC
`BW) threshold and does not drop below a Lower INC BW
`threshold for at least an INC BW wait period, then the
`transmission rate is incremented. The transmission rate can
`be selected from among a predetermined Set of discrete
`bandwidth values or from within a continuous range of
`bandwidth values. In one variation, in addition to responding
`to changes in network connection capacity, the client com
`puter also determines an average client computational
`capacity. Accordingly, if the average client computational
`capacity is less than the network capacity, the lower of the
`two capacities is the determining one, thereby avoiding a
`playout buffer overrun.
`
`42 Claims, 18 Drawing Sheets
`
`20
`
`STREAM
`SERVER
`
`WIDEOfAUD10
`STREAMS)
`ANNOTATON
`STREAM(s)
`
`WEB
`PAGES)
`
`BROWSER
`
`352
`BROWSER
`Pue-N woule
`VIDEAUDO STREAMS
`EssaEs
`
`WENT
`REGISTRY ss
`ANNOTION INTERFETER
`
`PLAYOUT
`sess- BUFFERS)
`364. DEADS
`DECObERS)
`WIDEOfAUDIO
`365- RENERS)
`36
`
`
`
`-240
`
`350
`350
`CLENT
`UE
`362
`
`Petitioners' Exhibit 1004
`Page 0001
`
`

`

`US 6,292,834 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`10/1997 Majeti et al. ................... 395/200.01
`5,675,732
`5,717,691 * 2/1998 Dighe et al..
`5,774,668
`6/1998 Choquier et al. ............... 395/200.53
`5,796,724
`8/1998 Rajamani et al. .
`5,812,788
`9/1998 Agarwal .......................... 395/200.77
`5,815,505
`9/1998 Mills .................................... 370/522
`5,822,524 * 10/1998 Chen et al. .......................... 709/203
`5,825,771 * 10/1998 Cohen et al..
`5,852,565
`12/1998 Demos ............................ 364/715.02
`5,859,667
`1/1999 Kondo et al. ...
`... 348/414
`5,886,995
`3/1999 Arsenault et al.
`... 370/477
`5,892,549
`4/1999 Feng ................
`348/422
`5,916,307
`6/1999 Piskie et al.
`... 709/314
`5,918,002 * 6/1999 Klemets et al.
`395/182.16
`5,926,226
`7/1999 Proctor et al. ..
`... 348/422
`5,940,072
`8/1999 Jahanghir et al.
`... 345/327
`5.956,088
`9/1999 Shen et al. ...
`... 348/385
`5,978,544
`11/1999 Shimada et al.
`... 386/112
`5.991,307
`11/1999 Komuro et al.
`... 370/473
`5,995,650
`11/1999 Migdal et al. ..
`... 382/154
`5.999,906
`12/1999 Mercs et al. ...
`... 704/500
`6,012,100
`1/2000 Frailong et al. ..................... 709/250
`OTHER PUBLICATIONS
`Rosado-Sosa, Carlos et al. “Jitter Compensation Scheduling
`ss
`Schemes for the Support of Real-Time Communictions
`IEEE ICC'98. 1998.
`66
`s
`ss
`Web Theater Product User Guide, Version 2.0', Palo Alto,
`CA: VXtreme, Inc., (1997).
`Bolot, J.C., et al., “Scalable Feedback Control for Multicast
`Video Distribution in the Internet”, Conference Proceedings,
`ACM SIGCOMM 94, London, England, 58–67, (1994).
`Yavatkar, R., et al., “Optimistic Strategies for Large-Scale
`Dissemination of Multimedia Information’, Conference
`s
`
`Proceedings, Multimedia '93, 13–20, (1993).
`* cited by examiner
`
`5,025,457 * 6/1991 Ahmed r 375/354
`5,050,161
`9/1991 Golestani ....
`... 370/60
`5,088,107
`2/1992 Piasecki et al.
`... 375/10
`5,119,474
`6/1992 Beitel et al. ...
`... 395/154
`5,208,810
`5/1993 Park ..................................... 370/230
`5,231,599
`7/1993 Peters et al.
`364/709.16
`5,274,758
`12/1993 Beitel et al. ......................... 395/154
`5,313.454
`5/1994 Bustini et al. ......................... 370/13
`5,359,593 * 10/1994 Derby et al..
`5,434,848
`7/1995 Chimento, Jr. et al. ............. 370/170
`5,442,389
`8/1995 Blahut et al. ............................ 348/7
`5,455,910
`10/1995 Johnson et al.
`... 395/650
`5,463,422 * 10/1995 Simpson et al.
`... 348/390
`5,467,413
`11/1995 Barrett ........
`... 382/236
`5,485.211
`1/1996 Kuzma.
`... 348/409
`5,487,167
`1/1996 Dinallo et al. .
`... 395/650
`5,490.252
`2/1996 Macera et al. .
`395/2001
`5,504,744
`4/1996 Adams et al. .
`... 370/60.1
`5,519,701
`5/1996 Colmant et al. ...
`370/60.1
`5,524,193
`6/1996 Covington et al.
`... 395/154
`5,533,021
`7/1996 Branstad et al. ...
`370/60.1
`5,537,408
`7/1996 Branstad et al.
`... 370/79
`5,543,850
`8/1996 Pratt et al. ...
`... 348/617
`5,544,170 * 8/1996 Kasahara.
`... 370/253
`5,566,175 * 10/1996 Davis ......
`... 370/468
`5,574,724
`11/1996 Bales et al. ......................... 370/68.1
`5,574,861 * 11/1996 Lorvig et al..
`5,577.258
`11/1996 Cruz et al. ..
`395/800
`5,583,980
`12/1996 Anderson ...
`... 395/173
`5,594911
`1/1997 Cruz et al. ..
`... 395/800
`5,600,775
`2/1997 King et al. ..
`... 395/806
`5,602,992
`2/1997 Danneels ...
`... 709/248
`SE 19. RA - - - - - - - - - - - - - - - - - - - - - - - 3.
`2 - - -2
`alldal el all. . . . . . . . . . . . . . . . . . . . . . . .
`
`5,633,859
`5,666,487
`
`...
`5/1997 Jain et al. ............................
`9/1997 Goodman et al. .............. 395/200.76
`
`Petitioners' Exhibit 1004
`Page 0002
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 1 of 18
`
`US 6,292,834 B1
`
`WasHdldad
`
`sng
`
`Bel
`
`
`
`
`
`YOSSIOONdOYOINASOWSN
`
`sng
`
`00}
`
`SLt
`
`Oct
`
`col
`
`ee we wm mw www em ewes seer eee meen ee meme
`
`Petitioners’ Exhibit 1004
`Page 0003
`
`Petitioners' Exhibit 1004
`Page 0003
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 2 of 18
`
`US 6,292,834 B1
`US 6,292,834 B1
`
`g
`NN
`
`2
`—N
`
`
`
`
`gN
`
`i
`E
`=
`o@
`
`=E
`
`
`
`e .
`
`e
`
`——
`wad
`
`maLod=eLat
`
`a
`
`So
`~»
`N
`
`
`
`
`
`u>-
`—™N
`
`
`
`z
`2z
`5S
`ze
`Sh
`ow
`a
`
`as
`=
`Fi
`”
`
`2
`N
`
`bd
`N
`
`83||MBIAXJENOIS30
`
`@w
`
`=S
`
`N
`oO
`Li
`
`Pa
`bj
`z©
`aw
`tu
`OQ
`
`Petitioners’ Exhibit 1004
`Page 0004
`
`Petitioners' Exhibit 1004
`Page 0004
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 3 of 18
`
`US 6,292,834 B1
`
`220 O 250 CSD
`
`STREAM
`SERVER
`
`WEB
`SERVER(S)
`
`O O.
`
`O.
`
`VIDEO/AUDIO
`STREAM(S)
`ANNOTATION
`STREAM(S)
`
`WEB
`PAGE(S)
`
`COMPUTER
`NETWORK
`
`290
`
`f
`
`|
`
`
`
`
`
`
`
`BROWSER
`BROWSER
`PLUG-IN MODULE
`MDEO/AUDIO STREAMS)
`Esses
`
`
`
`
`
`350
`360
`
`240
`
`
`
`EVENT
`8
`REGISTRY
`ANNOTATION INTERPRETER
`
`
`
`
`
`CUENT
`MODULE
`
`EGS
`
`366- G
`1 BUFFER(S)
`VIDEO/AUDIO
`DECODER(S)
`VIDEO/AUDIO
`RENDER(S)
`
`364
`
`365
`
`
`
`Petitioners' Exhibit 1004
`Page 0005
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 4 of 18
`
`US 6,292,834 B1
`
`COMPUTE PERFORMANCE
`VARIABLES
`
`
`
`
`
`
`
`NEED
`TO DECREASE
`BANDWIDTH
`
`
`
`YES
`
`42OY
`
`
`
`
`
`
`
`
`
`DECREASE
`BANDWIDTH
`
`
`
`
`
`
`
`
`
`44OY YES
`
`INCREASE
`BANDWIDTH
`
`DESIRABLE
`TO INCREASE
`BANDWIDTH
`?
`
`
`
`FIG. 4
`
`Petitioners' Exhibit 1004
`Page 0006
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 5 of 18
`
`US 6,292,834 B1
`
`(st)
`
`;
`
`COMPUTE UPPER INCBWTHRESHOLD 512
`AND DECBWTHRESHOLD
`
`COMPUTE PLAYTIME &
`DELTAPLAYTIME
`
`513
`
`DETERMINE IF
`ROUNDTRIPTIMEBIT IS HIGH
`
`514
`
`DETERMINE IF
`LOSSRATE BIT IS HIGH
`
`UPDATE LOSSRATE
`PERIODICALLY
`
`516
`
`518
`
`FIG. 5A
`
`Petitioners' Exhibit 1004
`Page 0007
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 6 of 18
`
`US 6,292,834 B1
`
`420
`
`522
`
`
`
`
`
`
`
`
`
`524
`
`
`
`
`
`IS (DELTA PLAYTIME < C1)
`& (PLAYTIME < DECBWTHRESHOLD))
`OR (ROUNDTRIPTIME BIT=HIGH)
`OR (LOSSRATE BIT=HIGH)?
`
`
`
`DD PLAYTIME INCREASE PAST
`NCBW THRESHOLD SINCE THE LAST
`REDUCE BANDWIDTH MESSAGE WAS
`SENT TO THE SERVER
`
`WAS (NO REDUCE BANDWIDTH MESSAGE
`SENT) OR (AN INCEASE BANDWIDTH
`MESSAGE SENT AFTER THE LAST
`REDUCE BANDWIDTH MESSAGE SENT)?
`
`IS DIFF BTW (CURRENT TIME AND
`TIME OF LAST REDUCE BANDWIDTH MSG)
`> SUM OF (IDEALPLAYOUT BUFFERSIZE AND
`AVERAGE ROUNDTRIPTIME TO SERVER)?
`
`42OY
`
`420N
`
`FIG. 5B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Petitioners' Exhibit 1004
`Page 0008
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 7 of 18
`
`US 6,292,834 B1
`
`(Sir)
`
`531
`
`*
`
`INITIALIZE TIME BEFORE INCREASE IF NEEDED
`
`532
`
`COMPUTE TIME WHEN AN INCREASE BANDWIDTH
`MESSAGE FROM A PARTICULAR BANDWIDTH
`WAS SENT (T1)
`
`533
`
`DD BANDWIDTH REDUCTION REACH
`THE PARTICULAR BANDWIDTH
`
`NO
`
`IS DIFFERENCE BETWEEN
`(TIME OF REDUCTION) AND (ABOVE COMPUTED
`TIME OF INCREASE (T1) LESS THAN C2?
`
`
`
`
`
`FOR PARTICULARBANDWIDTH, SET
`TIME BEFORE INCREASE TO MAX
`(C3, C4" TIME BEFORE INCREASE)
`
`
`
`SET
`TIME BEFORE INCREASE
`TO C5
`
`SEND A REDUCE BANDWIDTH MESSAGE TO SERVER
`
`537
`
`FIG. 5C
`
`Petitioners' Exhibit 1004
`Page 0009
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 8 of 18
`
`US 6,292,834 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GSAD
`
`st
`
`1
`
`4
`
`IS PLAYTIME > UPPER INCBW THRESHOLD
`YES
`542
`
`NO
`
`TIMEBUFFERFUL = TIME PLAYOUT BUFFERSIZE
`FIRST INCREASES PAST UPPER INCBW THRESHOLD
`
`543
`
`IF PLAYOUT BUFFERSIZE C P2, OF
`IDEALPLAYOUT BUFFERSIZE,
`THEN TIME BUFFERFUL = 0
`544
`IS (REDUCE BANDWIDTH MSG SENT
`>
`INCREASE BANDWIDTH MSG) & (DIFF
`BTW (CURRENT TIME & PREVIOUS TIME BANDWIDTH
`WAS SWITCHED) > TIME BEFORE INCREASE
`& (AVERAGE LOSSRATE < C6)?
`YES
`545
`WAS (BANDWIDTH REDUCED BECAUSE
`LOSSRATE BIT WASHIGH) & (AVERAGE
`LOSSRATE < C7)?
`
`
`
`YES
`
`WAS (LAST BANDWIDTH SWITCH NOT DUE TO
`HIGH LOSSRATE BIT) & (AVERAGE LOSSRATE
`< C8) & (DIFF Biw (CURRENT TIME AND
`TIME BUFFERFULL) >
`TIME BEFORE INCREASE)?
`
`
`
`
`
`440N
`
`44OY
`
`FIG. 5D
`
`Petitioners' Exhibit 1004
`Page 0010
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 9 of 18
`
`US 6,292,834 B1
`
`
`
`
`
`552
`SEND AN INCREASEBANDWIDTH
`MSG TO THE SERVER
`
`FIG. 5E
`
`Petitioners' Exhibit 1004
`Page 0011
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 10 of 18
`
`US 6,292,834 B1
`
`(snR)
`
`512
`
`612
`
`D1:= DIFF BTW (CURRENT TIME) &
`(LAST TIME ADJUST BWPROC WAS INVOKED)
`614
`D2:= DIFF BTW (TIMESTAMP OF LAST PACKET
`N PLAYOUT BUFFER) & (TIMESTAMP OF LAST PACKET
`DURING LAST INVOCATION OF ADJUST BWPROC)
`616
`D3:= DIFF BTW (; BYTES RECEMED BY LAST
`INVOCATION) AND (; BYTES RECEMED PRESENTLY
`(THIS INVOCATION)
`622
`
`NO
`
`NO
`
`IS D1 > C9?
`YES 624
`ISD2 > C10?
`YES
`
`632
`
`Q1: = D3 - D2 COMPUTE
`AVERAGE OF LAST C10 SAMPLES OF Q1
`
`654
`
`NO
`
`IS D1 > 0
`
`YES
`
`638
`
`O2: = D3 + D1 COMPUTE
`AVERAGE OF LAST C11 SAMPLES OF Q2
`
`
`
`
`
`
`
`
`
`
`
`
`
`(cont.)
`
`(cont.)
`
`FIG. 6A
`
`Petitioners' Exhibit 1004
`Page 0012
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 11 of 18
`
`US 6,292,834 B1
`
`(cot)
`
`(or 2)
`
`NO
`
`IS C11 > C12?
`YES
`
`640
`
`
`
`
`
`
`
`
`
`
`
`
`
`DECBWTHRESHOLD:= ((((IDEAL-PLAYOUT BUFFERSIZE)
`+ (CODEC SPECIFICCONSTANT))" (AVERAGE OF Q1)
`+ (AVERAGE OF Q2) + (IDEALPLAYOUT BUFFERSIZE) * C13)
`660
`
`UPPER INCBWTHRESHOLD:= (IDEAL-PLAYOUT BUFFERSIZE)
`- (AVERAGE PACKETSIZE) + (AVERAGE OF Q2)
`
`UPPER INCBWTHRESHOLD:= MAX (MIN (UPPER
`INCBWTHRESHOLD, (IDEAL PLAYOUT BUFFERSIZE) * C14),
`(IDEALPLAYOUT BUFFERSIZE) * C15)
`
`
`
`UPPERINCBW THRESHOLD:=
`(IDEALPLAYOUT BUFFERSIZE) * C16
`
`
`
`DECBWTHRESHOLD:= MAX (DECBWTHRESHOLD,
`DECBW THRESHOLD C17
`
`690
`
`FIG. 6B
`
`Petitioners' Exhibit 1004
`Page 0013
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 12 of 18
`
`US 6,292,834 B1
`
`513
`
`710
`
`PLAYTIME:= DUE TIME OF LAST PACKET IN PLAYOUT BUFFER
`
`DETERMINE CHANGE IN PLAYOUT BUFFERSIZE
`
`720
`
`730
`
`DELTA PLAYTIME= PLAYTIME -
`(PLAYTIME AT LAST INVOCATION OF ADJUST BW PROC)
`
`FIG. 7A
`
`Petitioners' Exhibit 1004
`Page 0014
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 13 of 18
`
`US 6,292,834 B1
`
`GSIRD
`
`710
`
`/
`
`BASELTS:= TIMESTAMP OF FIRST PACKET
`
`712
`
`714.
`
`BASE TIME= TIME WHEN FIRST PACKET WAS RECEIVED
`
`TS:= TIMESTAMP OF CURRENT PACKET
`
`DUETIME= (IDEAL-PLAYOUT_BUFFERSIZE)
`+ (TS-BASETS) - (CURRENT TIME-BASE TIME)
`
`716
`
`718
`
`FIG. 7B
`
`Petitioners' Exhibit 1004
`Page 0015
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 14 of 18
`
`US 6,292,834 B1
`
`IS (ROUNDTRIPTIME > C18) &
`NO /(ROUNDTRIPTIME HAS INCREASED RECENTLY) &
`(NEW SAMPLE OF. ROUND TRIPTIME SINCE LAST
`REDUCE BANDWIDTH MSG WAS SENT TO SERVER
`BECAUSE ROUNDTRIPTIME BIT= HIGH)?
`YES
`820
`
`
`
`ROUNDTRIPTIMEBT:= HIGH
`
`ROUNDTRIPTIME_BIT:= HIGH
`
`
`
`FIG. 8
`
`Petitioners' Exhibit 1004
`Page 0016
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 15 of 18
`
`US 6,292,834 B1
`
`
`
`
`
`
`
`IS (; OF SAMPLES OF LOSSRATE > C20)
`& (LOSSRATE > C21) & NEW SAMPLE OF
`LOSSRATE TAKEN SINCE LAST
`REDUCE BANDWIDTH MSG TO SERVER
`BECAUSE LOSSRATE BIT= HIGH)?
`YES
`920
`
`LOSSRATEBT:= HIGH
`
`LOSSRATE BIT:= HIGH
`
`
`
`FIG. 9
`
`Petitioners' Exhibit 1004
`Page 0017
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 16 of 18
`
`US 6,292,834 B1
`
`(sa)
`
`"
`
`1010
`SET EXPECTED LAST:= MAX SEQUENCE OF PACKET
`RECEMED WHEN LOSSRATE WAS LAST COMPUTED
`
`SET EXPECTED:= MAX SEQUENCE OF PACKETS
`RECEMED SO FAR
`
`PACKETS RECEMED
`RECEIVED-LAST:= TOTAL
`WHEN LOSSRATE WAS LAST COMPUTED
`
`1020
`
`1030
`
`1040
`
`RECEMED:= TOTAL - PACKETS
`RECEMED SO FAR
`
`
`
`1050
`LOSSRATE:= ((EXPECTED - EXPECTED LAST) - (RECEIVED -
`RECEMEDLAST): 100) + (EXPECTED - EXPECTEDLAST)
`
`FIG. 1 O
`
`Petitioners' Exhibit 1004
`Page 0018
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 17 of 18
`
`US 6,292,834 B1
`
`1100
`
`
`
`
`
`COMPUTE PERFORMANCE WARIABLES
`
`410
`
`1110
`
`COMPUTE AMERAGE CLIENT COMPUTATIONAL RATE
`
`
`
`1120
`
`IS AVERAGE CLIENT COMPUTATION RATE
`> SELECTED TRANSMISSION RATE
`
`
`
`
`
`
`
`DESIRABLE
`TO INCREASE
`BANDWIDTH
`p
`
`
`
`
`
`
`
`INCREASE
`BANDWIDTH
`
`TO DECREASE
`BANDWIDTH
`
`DECREASE
`BANDWIDTH
`
`FIG. 11
`
`Petitioners' Exhibit 1004
`Page 0019
`
`

`

`U.S. Patent
`
`Sep. 18, 2001
`
`Sheet 18 of 18
`
`US 6,292,834 B1
`
`IS SEQUENCE OF ARRMING
`PACKET OUT OF SEQUENCE2
`
`IS "SKIPPED" PACKET REALLY
`"MISSING"?
`
`COMPUTE ROUNDTRIPTIME
`OF MISSING PACKET
`
`IS THERE SUFFICIENT TIME TO
`REASONABLY EXECUTE A TIMELY
`RETRANSMISSION?
`
`SENT RETRANSMISSION REQUEST
`TO SERVER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 12
`
`Petitioners' Exhibit 1004
`Page 0020
`
`

`

`1
`DYNAMIC BANDWIDTH SELECTION FOR
`EFFICIENT TRANSMISSION OF
`MULTIMEDIA STREAMS IN A COMPUTER
`NETWORK
`
`RELATED APPLICATIONS
`This application is related to U.S. application Ser. No.
`08/818,805, filed on Mar. 14, 1997, entitled “Method and
`Apparatus for Implementing Motion Detection in Video
`Compression,” U.S. application Ser. No. 08/819,507, filed
`Mar. 14, 1997, entitled “Digital Video Signal Encoder and
`Encoding Method,” U.S. application Ser. No. 08/818,804,
`filed on Mar. 14, 1997, entitled “Production of a Video
`Stream with Synchronized Annotations over a Computer
`Network,” U.S. application Ser. No. 08/819,586, filed on
`Mar. 14, 1997, entitled “Method and apparatus for Imple
`menting Control Functions in a Streamed Video Display
`System,” U.S. application Ser. No. 08/818,769, filed on Mar.
`14, 1997, entitled “Method and apparatus for Automatically
`Detecting Protocols in a Computer Network, U.S. applica
`tion Ser. No. 08/818,127, filed on Mar. 14, 1997, entitled
`“Dynamic Bandwidth Selection for Efficient Transmission
`of Multimedia Streams in a Computer Network,” U.S.
`application Ser. No. 08/819,585, filed on Mar. 14, 1997,
`entitled “Streaming and Display of a Video Stream with
`Synchronized Annotations over a Computer Network, U.S.
`application Ser. No. 08/818,664, filed on Mar. 14, 1997,
`entitled “Selective Retransmission for Efficient and Reliable
`Streaming of Multimedia Packets in a Computer Network.”
`U.S application Ser. No. 08/819,579, filed Mar. 14, 1997,
`entitled “Method and apparatus for Table-Based Compres
`sion with Embedded Coding.” U.S. application Ser. No.
`08/819,587, filed Mar. 14, 1997, entitled “Method and
`apparatus for Implementing Motion Estimation in Video
`Compression,” U.S. application Ser. No. 08/818,826, filed
`on Mar. 14, 1997, entitled “Digital Video Signal Encoder
`and Encoding Method,” all filed concurrently herewith, U.S.
`application Ser. No. 08/822,156, filed on Mar. 17, 1997,
`entitled “Method and apparatus for Communication Media
`Commands and Data Using the HTTP Protocol,” U.S.
`provisional application Serial No. 60/036, 662, filed on Jan.
`30, 1997, entitled “Methods and apparatus for Autodetecting
`Protocols in a Computer Network,” U.S. application Ser.
`No. 08/625,650, filed on Mar. 29, 1996, entitled “Table
`Based Low-Level Image Classification System.” U.S. appli
`cation Ser. No. 08/714,447, filed on Sep. 16, 1996, entitled
`“Multimedia Compression System with Additive Temporal
`Layers, and is a continuation-in-part of U.S. application
`Ser. No. 08/623,299, filed on Mar. 28, 1996, entitled “Table
`Based Compression with Embedded Coding,” which are all
`incorporated by reference in their entirety for all purposes.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to multimedia communica
`tions. More particularly, the present invention relates to the
`efficient and reliable delivery of multimedia streams over a
`diverse computer network with dynamically variable band
`width capacity.
`2. Description of the Related Art
`With the proliferation of connections to the internet by a
`rapidly growing number of users, the viability of the internet
`as a widely accepted medium of communication has
`increased correspondingly. Bandwidth requirements can
`vary significantly depending on the type of multimedia data
`being delivered. For example, a low resolution, low frame
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,292,834 B1
`
`2
`rate video telephone call may require only an ISDN
`connection, while a high resolution video broadcast of a live
`event to a large group of viewers may require the bandwidth
`of a T1 connection to the server. Hence, the ability to
`efficiently deliver multimedia data over a diverse computer
`network such as the internet is severely limited by the
`reliability and bandwidth capacity of the network connec
`tion.
`The first problem is the average transmission capacity. In
`an ideal packet-based delivery System with an input buffer at
`a client computer, data packets arrive at the client computer
`in the same order and at the same interval the packets were
`Sent by the Server. In an ideal example, at time t, the client
`computer receives data packet #1 with a time Stamp of 0.0
`Second. Subsequently, at time t+1 Second, data packet #2
`with a time stamp of 1.0 second arrives, followed by data
`packet #3 with a time stamp of 2.0 seconds at time t--2
`Seconds. As a result, packets arrive at and are consumed by
`the client computer at the same rate as they were Sent.
`However in a more realistic example, the network con
`nection may be unable to keep up with the demands of the
`Server/client Stream traffic, i.e., the average bandwidth
`capacity of the network connection may be insufficient.
`Consequently, data packets will arrive at the client computer
`later and later in time, causing the input buffer to empty at
`a faster rate than it can be replenished, and eventually
`depleting the input buffer. For example, data packet #2 with
`the time Stamp of 1.0 seconds may arrive at time t+1.2
`seconds, followed by data packet #3 with the time stamp of
`2.0 Seconds arriving at time t+2.4 Seconds. In other words,
`the average bandwidth capacity of the network connection is
`insufficient to Support the transmission rate Selected by the
`server/client. This is a first order bandwidth capacity prob
`lem.
`The second problem is the rate of change of bandwidth
`capacity over time of the network connection. Since overall
`traffic within the internet is not constant, and Since the
`internet is packet-Switched, the bandwidth capacity provided
`by the internet for the network connection can vary dynami
`cally over time. Accordingly, if an application is too aggres
`Sive in demanding bandwidth, during peak demand periods,
`the internet may be unable to cope with the peak demand,
`causing packets to be discarded/lost and requiring
`retransmission, which further degrades the overall perfor
`mance of the network connection. This is a Second order
`network bandwidth problem, i.e., changes in the bandwidth
`capacity over time.
`In a real time application, e.g., a video on demand (VOD)
`application, the discarded/lost packets result in jitter. Jitter is
`defined as the Second order timing difference in the packet
`arrival times. In the ideal example, where packet #2 and
`packet #3 arrive at t+1.0 Second and t+2.0 Seconds,
`respectively, jitter is Zero., because the inter-arrival times,
`i.e., differences in arrival times, are identical.
`However, in a more realistic example, packets #2 and #3
`may arrive at t+0.9 second and t+2.1 Seconds, with inter
`arrival times of 0.9 second and 1.2 Seconds, respectively.
`Although the input buffer of the client computer provides
`partial relief by buffering the incoming packets and releasing
`them to applications on the client computer at a less jittery
`rate, unfortunately, in the real time application, the length of
`the input buffer has to be kept to a minimum, thereby
`Severely limiting the relief attainable.
`In View of the foregoing, there are desired improved
`techniques for reliable and efficient transmission of multi
`media Streams to client(s) which efficiently utilize the net
`work resources available over a period of time.
`
`Petitioners' Exhibit 1004
`Page 0021
`
`

`

`US 6,292,834 B1
`
`3
`SUMMARY OF THE INVENTION
`The present invention provides efficient transmission of
`multimedia Streams from a Server to a client computer over
`a diverse computer network including local area networks
`(LANs) and wide area networks (WANs) such as the inter
`net. Examples of multimedia Streams provided to the client
`computer include a compressed Video Stream, a compressed
`audio Stream, and an annotation Stream with pointers to
`textual/graphical data in the form of HTML pages.
`In one embodiment, the client computer includes a play
`out buffer, and the transmission rate is dynamically matched
`to the available bandwidth capacity of the network connec
`tion between the Server and the client computer.
`If a playtime of the playout buffer, which is one measure
`of the number of data packets currently in the playout buffer,
`drops below a dynamically computed Decrease Bandwidth
`(DEC BW) threshold, then the transmission rate is
`decreased by sending a DEC BW message to the server.
`Conversely, if the number of packets remaining in the
`playout buffer rises above a dynamically computed Upper
`Increase Bandwidth (INC BW) threshold and does not
`drop below a Lower INC BW threshold for at least an
`INC BW wait period, then the transmission rate is incre
`mented.
`In this embodiment, the transmission rate is Selected from
`among a predetermined Set of discrete bandwidth values.
`However the invention is also applicable to a System in
`which the transmission rate is Selected from within a con
`tinuous range of bandwidth values.
`In another embodiment, in addition to responding to
`variations in network connection capacity, the client com
`puter also determines an average client computational
`capacity. Accordingly, if the average client computational
`capacity is less than the network capacity, the lower of the
`two capacities is the determining one, thereby avoiding a
`playout buffer overrun.
`These and other advantages of the present invention will
`become apparent upon reading the following detailed
`descriptions and Studying the various figures of the draw
`ings.
`
`15
`
`25
`
`4
`FIG. 7B illustrates the determination of the Duetime of a
`data packet.
`FIG. 8 is a flowchart showing the determination of the
`Round Trip Time Bit.
`FIG. 9 is a flowchart showing the determination of the
`LOSSrate Bit.
`FIG. 10 illustrates a periodic update of Lossrate.
`FIG. 11 is a flowchart showing a dynamic bandwidth
`Selection which optimizes the computational capacity of the
`client computer and which is also Sustainable by the network
`connection.
`FIG. 12 is a flowchart illustrating the selective retrans
`mision of the present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The present invention will now be described in detail with
`reference to a few preferred embodiments thereof as illus
`trated in the accompanying drawings. In the following
`description, numerous Specific details are Set forth in order
`to provide a thorough understanding of the present inven
`tion. It will be apparent, however, to one skilled in the art,
`that the present invention may be practiced without Some or
`all of these specific details. In other instances, well known
`process Steps have not been described in detail in order to
`not unnecessarily obscure the present invention.
`FIG. 1 is a block diagram of an exemplary computer
`System 100 for practicing the various aspects of the present
`invention. Computer system 100 includes a display screen
`(or monitor) 104, a printer 106, a floppy disk drive 108, a
`hard disk drive 110, a network interface 112, and a keyboard
`114. Computer system 100 includes a microprocessor 116, a
`memory bus 118, random access memory (RAM) 120, read
`only memory (ROM) 122, a peripheral bus 124, and a
`keyboard controller 126. Computer system 100 can be a
`personal computer (Such as an Apple computer, e.g., an
`Apple Macintosh, an IBM personal computer, or one of the
`compatibles thereof), a workStation computer (Such as a Sun
`Microsystems or Hewlett-Packard workstation), or some
`other type of computer.
`Microprocessor 116 is a general purpose digital processor
`which controls the operation of computer system 100.
`Microprocessor 116 can be a Single-chip processor or can be
`implemented with multiple components. Using instructions
`retrieved from memory, microprocessor 116 controls the
`reception and manipulation of input data and the output and
`display of data on output devices.
`Memory bus 118 is used by microprocessor 116 to access
`RAM 120 and ROM 122. RAM 120 is used by micropro
`ceSSor 116 as a general Storage area and as Scratch-pad
`memory, and can also be used to Store input data and
`processed data. ROM 122 can be used to store instructions
`or program code followed by microprocessor 116 as well as
`other data.
`Peripheral bus 124 is used to access the input, output, and
`storage devices used by computer system 100. In the
`described embodiment(s), these devices include display
`screen 104, printer device 106, floppy disk drive 108, hard
`disk drive 110, and network interface 112. Keyboard con
`troller 126 is used to receive input from keyboard 114 and
`Send decoded Symbols for each pressed key to micropro
`cessor 116 over bus 128.
`Display screen 104 is an output device that displays
`images of data provided by microprocessor 116 via periph
`eral bus 124 or provided by other components in computer
`
`35
`
`40
`
`BRIEF DESCRIPTION OF THE DRAWING
`FIG. 1 is a block diagram of an exemplary computer
`System for practicing the various aspects of the present
`invention.
`FIG. 2 is a block diagram showing an exemplary hard
`ware environment for practicing the reliable and efficient
`video-on-demand (VOD) system of the present invention.
`FIG. 3 is a block diagram showing a producer which
`includes a capture module and an author module for cap
`turing video Streams and for generating annotation Streams,
`respectively.
`FIG. 4 is a flowchart including steps 410, 420, 430, 440
`and 450 which illustrate the Adjust Bandwidth procedure
`of one embodiment of the present invention.
`FIG. 5A, 5B, 5C, 5D and 5E, are detailed flowcharts
`illustrating steps 410, 420, 430, 440 and 450, respectively, of
`FIG. 4.
`FIGS. 6A and 6B are two halves of a flowchart illustrating
`the dynamic determination of the Upper INC BW threshold
`and the DEC BW threshold.
`FIG. 7A is a flowchart illustrating the computation of
`variables Playtime and Delta Playtime of the playout
`buffer.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners' Exhibit 1004
`Page 0022
`
`

`

`US 6,292,834 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`system 100. Printer device 106 when operating as a printer
`provides an image on a sheet of paper or a similar Surface.
`Other output devices Such as a plotter, typesetter, etc. can be
`used in place of, or in addition to, printer device 106.
`Floppy disk drive 108 and hard disk drive 110 can be used
`to store various types of data. Floppy disk drive 108 facili
`tates transporting Such data to other computer Systems, and
`hard disk drive 110 permits fast access to large amounts of
`Stored data.
`Microprocessor 116 together with an operating System
`operate to execute computer code and produce and use data.
`The computer code and data may reside on RAM 120, ROM
`122, or hard disk drive 120. The computer code and data
`could also reside on a removable program medium and
`loaded or installed onto computer system 100 when needed.
`Removable program mediums include, for example,
`CD-ROM, PC-CARD, floppy disk and magnetic tape.
`Network interface circuit 112 is used to send and receive
`data over a network connected to other computer Systems.
`An interface card or Similar device and appropriate Software
`implemented by microprocessor 116 can be used to connect
`computer System 100 to an existing network and transfer
`data according to Standard protocols.
`Keyboard 114 is used by a user to input commands and
`other instructions to computer system 100. Other types of
`user input devices can also be used in conjunction with the
`present invention. For example, pointing devices Such as a
`computer mouse, a track ball, a Stylus, or a tablet can be used
`to manipulate a pointer on a Screen of a general-purpose
`computer.
`The present invention can also be embodied as computer
`readable code on a computer readable medium. The com
`puter readable medium is any data Storage device that can
`Store data which can be thereafter be read by a computer
`System. Examples of the computer readable medium include
`read-only memory, random-acceSS memory, magnetic data
`Storage devices Such as diskettes, and optical data Storage
`devices such as CD-ROMs. The computer readable medium
`can also be distributed over a network coupled computer
`Systems So that the computer readable code is Stored and
`executed in a distributed fashion.
`FIG. 2 is a block diagram showing an exemplary hard
`ware environment for practicing the reliable and efficient
`video-on-demand (VOD) system of the present invention.
`The VOD system includes a production station 210, a stream
`server 220, at least one web server 230 and at least one client
`computer 240, each of which can be implemented using
`computer system 100 described above. Stream server 220
`and web server 230 are coupled to client computer 240 via
`a computer network 290, e.g., the internet. Note that the
`disclosed hardware environment is exemplary. For example,
`production station 210 and stream server 220 can be imple
`mented using two se