`
`CONVERGING TECHNOLOGIES
`
`FOR ToMoAAow’S APPLIGATIDNS
`
`7.96.101 EL-paun.1IEC
`
`Ice '96
`
`JUNE 23 - 27,1996
`
`DALLAS CDHVENTIDN CENTER
`
`DALLAS, TEXAS USA
`
`CONFERENCE Rzconn
`
`VDLIJME 3 or 3
`
`SPONSORED BY THE IEEE COMMUNICATIONS Socmv AND THE DALLAS Szcnou or
`
`IEEE
`
`0
`
`IEEE
`
`ICC
`
`GLOBECOM
`
`WWI
`
`00ianO0
`
`RPX Exhibit 1128
`
`RPX Exhibit 1128
`RPX v. DAE
`
`RPX V. DAE
`
`
`
`
`
`96CH359 1 6
`
`O-7803-3250-4
`O—7803—325 1-2
`0-7803-3252-O
`0-7803-3382-9
`81-64954?
`
`IEEE Catalog Number:
`
` ISBN Numbers:
`
`Softbound Edition:
`Casebound Edition:
`Microfiche Edition:
`CD—ROM
`Library of Congress Number:
`
`WllmmMm'ICAmmEC
`
`COPYRIGHTS AND REPRINT PERMISSIONS
`
`Copyright Clearance Center
`222 Rosewood Drive
`
`Danvers, MA 01923
`
`For copying, reprint, or republication permission, Write:
`
`Manager of Copyrights
`IEEE
`
`44-5 Hoes Lane, PO. Box 1331
`
`Piscataway, NJ 08855-1331
`
`Additional copies of this publication are available from:
`
`IEEEIOperations Center
`P. O. Box 1331
`
`445 Hoes Lane
`
`Piscataway, NJ 08855-1331 USA
`
`1-800-678-IEEE
`
`1-908-981-1393
`
`1-908-981-9667 (Fax)
`
`833-233 (Telex)
`
`email: customer.service@ieee.org
`
`All rights reserved. © 1996 by The Institute of Electrical and Electronics Engineers, Inc.
`
`
`
`11
`
`
`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`
`
`buffer and the mean playout rate. The optimal TH can then be
`selected by trading off the rise in the probability of having an
`empty buffer against the increase in the playout rate. In what
`follows, the analytic model is given in detail.
`
`Let p,-J denote the transition probability of the queue
`occupancy altered from 1' to j frames, as seen by departure frames.
`Thus, the queue occupancies at frame departing epoches form an
`embedded Markov chain, as shown in Figure 2, with the state
`transition probability matrix (P) given as
`
`’
`Po,o Po,i P0,:
`Pm P1,: Pm '
`P = [Pu] = 172.0 P2.1 172,2
`'
`PN,o PN.1 PN,2
`'
`
`' Pow
`'
`' ‘PM!
`'
`‘ Pzgv -
`'
`‘ pN,N
`
`(1)
`
`Pu =
`
`To derive the steadywstate buffer size distribution, one has to
`first determine p,-J’ which is dependent on both the current state (1)
`and the frame arrival process. The arrival is modelled by the
`Poisson process. Let /I be the mean frame anival rate, and B,-(t) be
`the service—time Cummulative Distribution Function (CDF)
`when 1' customers are in the buffer. Then,
`P5,; ‘‘
`
`B.-(t) =
`
`1- e‘£“ri+)"’
`1 — e""’,
`
`7
`
`7
`i < TH‘
`i 2 TH.
`
`(3)
`
`Thus, p,-_,- can be obtained by applying Equation (3) to Equation (2)
`as
`
`.
`.
`.
`Ara
` , l=0,l—1SJ<N;
`TH
`I
`hffiy
`i=Q0Sj=M
`A}-_‘-+l_ min[TH,t'}
`T" ",o<isN,0sj<1v;
`(A + mm ‘I
`.“)’''+2
`j—n‘+1
`
`TH
`
`/1
`—-—.—.-—
`
`(1 +fl}f##)
`
`, 0 <
`
`.
`
`I
`
`s N,
`
`.
`
`I
`
`-1 s
`
`.
`
`J
`
`= N;
`
`0,
`
`elsewhere.
`
`(4).
`
`With p,-J/s given in Equation (4), the stochastic equilibrium
`distribution for the queue occupancies, H E [:ro,:r,, -
`-
`- JIN],
`can be directly computed by solving the stationary equation,
`17 = HP. In addition, the frame loss probability (pL), given the
`buffer size of N, can be obtained as
`15/+1
`
`N—i+2
`
`_
`
`PL — no
`
`_
`
`/I
`
`(A + TL”)
`
`,
`
`”
`
`+i§1:t,-
`
`,1
`
`TH
`
`(5)
`
`Furthermore, the mean playout rate (F) can be formulated as
`
`F ___ gm . min {TH,Tr;_i[ax{i,1}}#_
`i=0
`
`(6)
`
`2.2 Analytic Results
`
`We have so far obtained the steady—state buffer size
`distribution as a function of the TH. To optimize the TH, we
`consider three variables: the probability of having an empty buffer
`(.710), the frame loss probability (p,), and the mean playout rate
`(F). To analyze how the TH, 1:0, pL, and F are related, we
`performed simulations on a system of buffer size = 100 frames,
`frame size = 15K bytes, network access rate = 100 Mbps
`(implying a slot time of 1.2 ms), and the maximal playout rate (p)
`= 1/25 frames/slot—time (corresponding to a rate of 30 frames per
`second).
`
`In Figure 3, no decreases with the TH, as was expected. This
`is because,
`the greater the TH is,
`the faster the playout rate
`reduces, thus the smaller the probability of having an empty
`buffer. We also observe that, for any given TH, 1:0 increases as the
`mean arrival rate declines. Figure 4 unsurprisingly illustrates that
`pL increases with the TH and Figure 5 demonstrates that the mean
`playout rate decreases with the TH. This is because the larger the
`TH, the faster the playout rate reduces. In addition, the figures also
`show that both the frame loss probability and the mean playout
`rate increase with the mean arrival rate.
`
`On the whole, a larger TH which results in a smaller 1:0,
`implies pausedless playout; whereas a smaller TH implies better
`playout quality. In what follows, we present a paradigm of the
`determination of approprite THs under various arrivals.
`
`i=0,i—1sj<N;
`
`Iiififlwm,
`J
`L
`”
`L d3:(l).
`k§N w,(t),0 < 1 s N, 1-1 s 1 = N;
`
`an
`-1 I
`I
`k.::N‘’—/C!(—)dB,(z),
`
`I
`.
`'
`; = 0, 1-1 s j = N;
`
`e—/1 1(1)) ;—r+i
`
`O<isN,i—1_<_j<N;
`
`m
`
`tn
`
`-1 la, k—i+l
`
`‘
`
`’
`
`‘
`
`00
`,
`
`'
`
`elsewhere.
`
`Let i be the current number of frames in the buffer. Consider a
`smoothing strategy in which the mean service rate is set to a
`maximum value (it) when i exceeds the TH,
`and is set to
` y when 2' decreases below the TH. Suppose the service
`time is exponentially distributed, i.e.,
`
`Queue occupancy=0
`
`Queue occupancy=l
`
`PL
`P 1
`P1,2
`P1,:
`Q) C 9 9
`
`171,,‘
`
`Queue occupancy=i Figure 2. State—tIansition diagram for queue occupancies.
`
`1366
`
`
`
`
`
`01020304050607080
`
`H“I
`
`Figure 4. Effect of TH on PL under various arrival rates.
`
`l\1/I82(1)n playout rate (E) (narmalize to it)
`0.98
`
`0.96
`
`0.94
`
`0.92
`
`0.90
`
`0.88
`
`0.86
`
`01020304050607080
`
`TH
`
`Figure 5. Effect of TH on E under various arrival rates.
`
`Teleconferencing
`
`
`
`I
`
`2.3 Formal Description of Algorithm
`
`We now formally present the playout smoothing algorithm
`employed in the Video Smoother.
`[Video Playout Smoothing Algorithm]
`(1) Determine a suitable TH. Based on the analytic results
`obtained from the previous subsection, a paradigm of the TH
`determination can be constructed for each case of arrivals.
`Tables 1 shows the paradigm for the Video Smoothers achieving
`four different playout qualities under a given traffic characteristic
`(zl=0.875pt).
`(2) Determine the playout rate.
`_
`while (a frame to be playbacked) do
`if (the number of frames in the buffer 2 TH)
`playout_rate = maximum_playout_rate;
`else
`
`playout_rate = Dynamic_reduced_rate(TH, i);
`where the dynamic reduced rate can be selected according to
`Equations (3).
`
`[End of Algorithm]
`
`3. Prototyping System and Results
`
`The prototyping system (see Figure 6) was developed in Intel
`80486 personal computers under the MS—Windows environment.
`The prototyping system is composed of a teleconferencing
`multimedia application using Intel Smart Video Recorder,
`WinKing [11] and an Ethernet network. The WinKing package is
`an implementation of TCP/IP including the API, called Winsock,
`developed by Institute for Information Industry (III), Taiwan. In
`particular, the Video Smoother was implemented as a part of
`WinKing. The simulated frame arrivals are assumed to follow the
`Poisson process with }.=0.875tt. According to the constructed
`paradigm shown above, we employed an optimal TH of 7 for the
`Video Smoothers to achieve the playout quality of 1co<1O'3,
`p,_<l0‘6, and F>0.93p..
`A motion picture (see Figure 7) was adopted to demonstrate
`the viability of the Video Smoother. In the experiment, the film
`was captured every 96 ms with and without the Video Smoother.
`Figures 7(b) and (a) show a series of scenes taken from the film
`with and without the Video Smoother, respectively. Without the
`Video Smoother, part
`(a) of the figure reveals the playout
`discontinuity problem. In particular, playout pauses occur in
`a02—a03 and a10—a1l. By contrast, with the Video Smoother, as
`shown in the part (b), the movements of the bus in Figure 7(b) are
`much smoother than the ones in Figure 7(a), without delays.
`
` 0
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`TH
`
`Figure 3. Effect of TH on no under various arrival rates.
`
`
`
`
`
`
`
`Local Disk
`
`TCP/IP
`
`Simulated Frame Arrivals
`
`WinKin g
`
`
`
`Figure 6. Prototyping system architecture.
`
`Table 1. Recommended TH’s assuming Poisson arrivals
`
`6
`
`
`
`1
`
`
`
`
`
`
`
`
`1367
`
`
`
`[a0-4
`
`T
`
`>b04
`
`T
`
`[V
`
`_’
`
`_T T b10
`
`
`
`a06
`
`bO6
`
`S
`
`M
`
`’
`
`an
`
`A
`
`biz
`
`(a) Without Video Smoother
`
`(b) With Vido Smoother
`
`(a) Without Video Smoother
`
`(b) With Vido Smoother
`
`Figure 7. Playout of a motion picture with and without the Video Smoother.
`
`1368
`
`
`
`4. Conclusions
`
`The paper proposed a dynamic video playout smoothing
`method, called the Video Smoother, to prevent potential playout
`discontinuity.
`In contrast with existing methods,
`the Video
`Smoother dynamically adopts various playout rates according to a
`threshold (TH) the current number of frames in the playout buffer.
`To precisely determine THs under various traffic conditions, we
`established an analytic model assuming the Poisson arrival. Based
`on the analytic results, we then proposed a paradigm of
`determining THs and playout rates achieving different playout
`qualities under various loads of networks. To demonstrate the
`viability of the Video Smoother, we developed a prototyping
`system, including a multimedia teleconferencing application and
`the Video Smoother as a part of TCP/IP, on an Ethernet network.
`The prototyping results showed that
`the Smoother achieves
`smooth playout at the expense of only unnoticeable delays.
`
`[1]
`
`[2]
`
`[3]
`
`[4]
`
`[5]
`
`[6]
`
`[7]
`
`[8]
`
`[9]
`
`[10]
`
`[11]
`
`.[12]
`
`References
`
`F. Alvarez—Cuevas, M. Bertran, and J.M. Selga, “Voice
`Synchronization in Packet Switching Networks,” IEEE
`Network, Sep. 1993, pp. 20-25.
`
`L. Aguilar, J. J. Garcia—Luna-Aceves, D. Moran, E. J .
`Craighill,
`and R. Brungardt,
`“Architecture
`for. a
`Multimedia Teleconferencing System,” Proc. ACM
`SIGCOMM'86 Symposium, Aug. 1986, pp. 126-136.
`G. Barberis, “Buffer Sizing of a Packet-Voice Receiver,”
`IEEE Transactions on Communications, vol. COM-29,
`no. 2, Feb. 1981, pp. 152-156.
`
`J. C. Bolot, “End-to-End Packet Delay and Loss Behavior
`in the Internet,” Proc. ACM SIGCOMM, Sept. 1993, pp.
`289-298.
`
`in Transnet Packetized Voice
`“Issues
`D. Cohen,
`Communication,” Proc. Fifth Data Communications
`Symposium, Sept. 1977, pp. 6.10-6.13.
`
`G. C. Elmore, “Integrated Techonologies: An Approach to
`Establishing Multimedia Applications for Learning, ”
`Educom Review, vol. 27, no. 1, 1992, pp. 20-26.
`D. Gross and C. M. Harris, Fundamentals of Queueing
`Theory, 2nd Edition,Wiley, 1985.
`T. Hoshi, et al., “B-ISDN Multimedia Communication
`and Collaboration Platform Using Advanced Video
`Workstations
`to Support Cooperative Work,” IEEE
`Journal on Selected Areas in Communcations, vol. 10, no.
`9, Dec. 1992, pp. 1403-1412.
`
`V. Jacobson, “Congestion Avoidance and Control,” Proc.
`1988 ACM SIGCOMM, Aug. 1988, pp. 314-329.
`
`W. F. Leung, T. J. Baumgartner, Y. H. I-Iwang, M. J.
`Morgan, and S. Tu, “A Software Architecture fo
`Workstations Supporting Multimedia Conferencing in
`Packet Switching Networks,” IEEE Journal on Selected
`Areas in Communications on Multimedia Communication,
`April 1990, pp. 380-390.
`
`J. Lin and J. Chen, “The Design and Implementation of
`TCP/1P - WinKing,” Document A3k11221-2, Institute for
`Information Industry (III), 1994.
`
`Thomas D.C. Little and A. Ghafoor, “Multimedia
`Synchronization Protocols
`for Broadband Integrated
`Services,"
`IEEE Journal
`on
`Selected Areas
`in
`Communications, vol. 9, no. 9, Dec. 1991, pp. 1368-1382.
`
`[13]
`
`[14]
`
`[15]
`
`[16]
`
`[17]
`
`[18]
`
`[19]
`
`[20]
`
`[21]
`
`[22]
`
`[23]
`
`[24]
`
`[25]
`
`[26]
`
`[27]
`
`[28]
`
`[29]
`
`“Network
`and A. Ghafoor,
`Thomas D.C. Little
`Considerations
`for Distributed Multimedia Object
`Composition and Communication,” IEEE Network, vo1.4,
`no. 6, Nov. 1990, pp. 32-49.
`
`D. Mills, “Intemet Delay Experiments,” ARPANET
`Working Group Requests for Comment, Dec. 1983, RFC
`889.
`
`for Packet Voice
`“Techniques
`W.A. Montgomery,
`Synchronization,” IEEE Journal on Selected Areas in
`Communications, vol. SAC-1, no. 6, Dec. 1983, pp.
`1022-1028.
`
`A. D. Narasimhalu, and S. Christodoulakis, “Multimedia
`Information Systems: The Unfolding of a Reality,” IEEE 1
`Computer, vol. 8, no. 3, April 1990, pp. 391-400.
`W.E. Naylor
`and L. Kleinrock,
`“Stream Traffic
`Communication
`in
`Packet
`Switched Networks:
`Destination Beffuring Considerations,” IEEE Tansactions
`on Communications, vol. COM-30, no. 12, Dec. 1982, pp.
`2527-2534.
`
`C. Nicolaou, “An Architecture for Real-Time Multimedia
`Communication Systems,” IEEE Journal on Selected
`Areas in Communications, vol. 8, no. 3, April 1990, pp.
`391-400.
`
`Y. Ohba, M. Murata, and H. Miyahara, “Analysis of
`Interdeparture Processes for Bursty Traffic in ATM
`Networks,”
`IEEE Journal
`on Selected Areas
`in
`Communications, Vol.9, no. 3, April 1991, pp. 468-476.
`T. Ohmori, K. Maeno, S. Sakata, H. Fukuoka, and K.
`Watabe, “Cooperative Control for Sharing Applications
`Based on Distributed Multiparty Desktop Conferencing
`System: MERMAID,” IEEE ICC, 1992, pp. 1069-1075.
`S. Ramanathan and P. V. Rangan, “Adaptive Feedback
`Techniques for Synchronized Multimedia Retrieval over
`Integrated Networks,”
`IEEE/ACM Transactions on
`Networking, vol. 1, no. 2, April 1993, pp. 246-259.
`
`S. Ramanathan and P. V. Rangan, “Feedback Techniques
`for
`Intra-Media
`Continuity
`and
`Inter—Media
`Synchronization in Distributed Multimedia Systems,”
`The Computer Jounal, vol. 36, no. 1, 1993, pp. 19-31.
`
`R. Ramjee, J. Kurose, and D. Towsley, “Adaptive Playout
`Mechanisms
`for Packetized Audio Applications
`in
`Wide-Area Networks,” IEEE INFOCOM, 1994
`
`P. V. Rangan, “Software Implementation of VCRs on
`Personal Computing Systems, ” IEEE Transactions on
`Consumer Electronics, vol. 38, no. 3, Aug. 1992, pp.
`635-640.
`
`S. M. Ross, Stochastic Process, 1983.
`
`the
`“Voice Communication Across
`H. Schulzrinne,
`Internet: a Network Voice Terminal,” Technical Report,
`Dep. of Computer Science, U. Massachusetts, Amherst
`MA, July 1992.
`
`D. Shepherd and M. Salmony, “Extending OSI to Support
`Synchronization Required by Multimedia Applications,"
`High Speed Networks, Vol.13, no. 7, Sep. 1990, pp.
`399-406.
`
`R. Steinmetz, “Synchronization Properties in Multimedia
`Systems,”
`IEEE Journal
`on Selected Areas
`in
`Communications, vol. 8, no. 3, April 1990, pp. 401-412.
`
`Thomas E. Stern, “A Queueing Analysis of Packet
`Voice,” IEEE GLOBECOM, 1983, pp. 71-76.
`
`1369