779
`
`Multimedia Over High Speed Networks: Reducing Network
`Requirements With Fast Buffer Fillup
`
`Bing Zheng and Mohammed Atiquzzaman
`
`Department of Electrical and Computer Engineering
`The University of Dayton, Dayton, Ohio 45469-0226.
`E-mail: zhengbin@Ayernet.udayton.edu, atiqoengr. udayton.edu
`
`Abstract
`The cost effective ABR service is suitable for trans-
`mitting bursty compressed video over ATM network.
`Here, toe propose a Fast Busfer Fillup (FBF) scheme
`to run VoD oiier ATM network with ABR service. We
`develop models to determine buffer size at the client
`and the server for our scheme. We also develop re-
`lationships between the startup delay, the ABR ser-
`vice parameters, and the network congestion status.
`Our results indicate that the new scheme minimizes
`the startup delay and has simple network resource re-
`quirements.
`Key Words: Multimedia transmission, ATM net-
`work, ABR service, Buffer size.
`1 Introduction
`Because of the high bandwidth and the capability
`of carrying real-time voice and video, there has been a
`strong interest in operating Video on Demand (VoD)
`systems over an ATM network. Available bit sate
`(ABR) service uses the available bandwidth of the
`network and controls the data rate of the sources by
`providing feedback to the source. Compressed video
`is highly bursty in nature, its bit rate depends on
`the type of video and also varies significantly between
`frames. Since ABR has the highest utility of the net-
`work resource and offers an acceptable QoS at a low
`cost, it is important to study the suitability of trans-
`mitting highlg interactive video over ATM using an
`ABR service.
`A VoD sysbem consists of a video source/server,
`a client including the video decoder/display, and the
`network over which t,he video is to be transmitt,ed.
`The client also need some buffer space to smooth out
`fluctuations in the data receiving rate from the net-
`work. A t the start of a session or after a fast forward,
`the buffer needs t,o be filled up first before the video
`can be viewed. This results in a startup delay which
`depends on the buffer size at the client and the band-
`width available from the network. The buffer needs
`to be proper dimensioned so that the video display is
`continuous without underflow at the client buffer due
`to a reduced bandwidth available when the network
`is congested. Moreover, over-dimensioning the buffer
`
`results in expensive client systems and large startup
`delay.
`To increase the network bandwidth efficiency, au-
`thors in [l, 21, have investigated the effectiveness
`of the feedback control scheme in bandwidth allo-
`cation and management. They came to a very im-
`portant conclusion that feedback control is effective
`in transporting video over an ATM network. Buffer
`and memory requirements have been discussed in [3].
`However, there has been no detailed study on the
`buffering requirements at the client and server or the
`network requirements for VoD over the ABR service.
`A first step towards determining the buffering require-
`ments was been made in [4]. The architecture requires
`the server to renegotiate bandwidth frequently. In
`this paper, we have:
`proposed a new Fast Buffer Fillup scheme for a
`VoD system for transporting MPEG-2 video over
`an ATM network using the ABR service.
`developed analytical models to determine the
`minimum server and client buffer sizes required
`to allow continuous playback without underflow;
`defined the expression for the network eonges-
`tion status and evaluated the startup delay at the
`client;
`developed the relationship between the expected
`allocated rate, the network congestion status,
`and the PCR/MCR rate; and
`The rest of the paper is organized as follows. In
`Section 2, we propose the Fast Buffer Fillup (FBF)
`scheme and define the operating principles and the
`system model. In Section 3, we develop methodolo-
`gies to determine the minimum buffer requirements
`for the client and the server. We define and study
`the startup delay at, the client in Section 4. Numeri-
`cal results are presented in Section 5, with conclusions
`in Section 6.
`2 System Model and Operating Prin-
`ciple
`We consider a Video on Demand system (Figure 1)
`consisting of a video source/server, the ATM back-
`
`0-7803-4984-9/98/$10.00 01998 IEEE.
`
`PAGE 1 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009
`
`

`
`780
`
`The time spent in a FFW/FBW state is much
`smaller than that spent in the Playback state.
`2.3 The server model
`The server negotiates the ABR service param-
`eters with the ATM network during connec-
`tion setup. These parameters include the PCR
`(Peak Cell Rate), MCR(Minimum Cell Rate)
`and ACE (Available Cell Rate). The server
`transmits data at t.he PCR (or the maximum
`bandwidth available from the network) when the
`client, buffer level goes below C$,. When the
`the ACR is set to the
`buffer level reaches C&,
`average rate of the video.
`On receipt of a start or FFW/FBW request, the
`server requests a bandwidth equal to PGR. If
`the PCR is not allocat,ed by the network, it ac-
`cepts whatever bandwidth is offered by t.he net-
`work.
`0 The server has a buEer to smooth out the data
`stream sent to the net.work during the normal
`playback state.
`2.4 Network Performance
`The ATh4 network acts as a transmission channel
`with Fixed Round Trip Time (FRTT) delay of T d .
`In response to the server's request for bandwidth,
`the network allocaies bandwidth to the server with
`an exponential distribution within the PCR- M C R
`range(see Eqn. 12).
`2.5 Fast Buffer Fill-Up Scheme
`When the client moves from the Stop state t,o the
`Playback state, or immediately after a FFW/FBW
`operation, the client buffer needs to be filled to C$,
`before the start of the display. In order to reduce the
`startup delay, we propose the FBF scheme where the
`server attempts to renegot,iate a bandwidth of PCR
`from the network in an attempt to fill up the client
`buffer in the minimum possible time.
`3 Client/Server Buffer Requirements
`In this section, we model the user behavior and
`use it to determine the client, and server buffering
`requirements.
`3.1 Modeling User Behavior
`Figure 2 shows the client which can be in one of the
`four states: Stop, Playback, Fastforward (FFW) or
`Fastbackward (FBW). Since the buffer requirement
`for the client, is related to its state, it is necessary
`to determine the stationary state probability of the
`client. Let the elements of the state probability vect,or
`V,"} represent the Stop, Play-
`57" = {lbc,l~','';
`back, FFW and FBW states.
`JVe represent t,he state transitions of the client by
`a Markov chain as in Figure 3, where 7:;. denot,es
`the st,ate transition probability from stat,e z to st,ate
`.I. By following equation t,o find the sta,tionary state
`probabilities.
`
`Figure 1: A video on demand system using the ATTM
`network.
`
`bone network and clients with video deroderldisplay.
`Video is stored in MPEG-2 compressed format. There
`are buffers at the client and the server to smooth
`out fluctuations in the instantaneous data rate of the
`compressed video and the available bandwidth from
`the network.
`In MPEG-2, video is encoded in three type of
`frames, namely I, P and B. Frames are arranged in
`groups of pictures (GoP) denoted by MrnNn. An
`MmNn GoP contains n frames, and the B and P
`frames are arranged periodically with one P frame
`and (rn - 1) frames of B per period. For example,
`a GoP of M3N9 represents the group IBBPBBPBB.
`If we denot,e the dat,a rate of the I, P and B frames
`by P I , p p and
`respectively, then, the average rat,e
`E[P] of an MmNn GoP can be expressed as:
`
`Next, we outline the assumptions and operating
`principles of the client,. server and the network, which
`are used t,o evaluat,e the performance of our FBF
`scheme in Sections 3 and 4.
`2.1 User model
`We assume a highly interactive user who can be in
`one of the four states, viz., Stop; Playback, Fastfor-
`ward (FFW) and Fastbackward (FBW) correspond-
`ing to VCR-like operations. The client responds to
`the user state by requesting video from source. We
`assume that during the FFW/FBW operation, the
`video display scrolls at a very high speed.
`2.2 The Client model
`The client buffer must be filled to a minimum fill
`level C$i,l before the client starts displa,ying.
`
`When the client starts from the Stop state: t,he
`client only sends a request to server; no other
`action is required until its buffer reaches C:in.
`
`For a FFW-/FBW operation, the client sends a
`FFWJFBW request to the server; at the same
`time it consumes its buffcr at, a speed k times
`that of normal playback.
`
`At thc end of the FFW/FB\V operation. the
`client, does not display video until its huffer
`reaclies C:;in.
`
`PAGE 2 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009
`
`

`
`I
`
`781
`
`Client buffer
`
`Decoder/
`Display
`
`Client
`
`network
`
`Ri.
`
`Figure 2: The client model
`
`Figure 4: Illustration of C, and minimum client buffer
`size (C:in)
`for FFW/FBW operation.
`
`ATM network. Because of the fixed round trip delay
`(FRTT) of the network, the client has to wait for a
`time 0.5Td + T d + 0.5T, = ZTd before it receives the
`video at a higher rate. Therefore, the client buffer
`must have a minimum fill level Cs for no underflow
`while waiting for the new segment of the video to
`arrive. During the waiting period, the client con-
`sumes video at a rate kX(t) from the client buffer,
`and the buffer receives video at a rate X ( t ) from the
`network. Therefore, the client buffer is depleted at
`a rate (k - l ) X ( t ) during the waiting period. The
`minimum buffer size required at the client to prevent,
`underflow during the waiting period of 2Td is there-
`fore given by:
`
`Ll
`
`t i + %
`
`(k - l)X(t)d(t)
`
`(4)
`
`Cg =
`where tl denotes the time when the client starts a
`FFW/FBW operation. Since video is sent to the
`client buffer at the ACR which is approximately equal
`to the average rate of the video, C, can be approxi-
`mately expressed by the expected rate as:
`c, = 2(k - l)TdE[X]
`( 5 )
`However, the client, consumes video at a rate which
`varies from frame to frame, with the I-frame having
`the highest data rate which is several times higher
`than the average rate. In the worst case of the user
`performing the FFW/FBW operation just after the
`client decodes an I-frame, we must ensure that there is
`no buffer underflow at the client as shown in Figure 4.
`To calculate the minimum fill level of the client buffer,
`we should therefore take the difference between the I-
`frame rate and the average rate into consideration.
`Therefore, the minimum fill level C,",( which is also
`the minimum capacity of the client buffer) can be
`expressed as:
`CEin = 2(k - l)Tdfl[X] + Tf(E[/?1] - B[01)
`( 6 )
`where E[Pr] and E[P] are the average rates of the
`I-frame and the GoP respectively. T'
`is the time
`duration for a single frame of MPEG-2 video, and
`-E[/?]) accounts for the buffer required due
`Tf(E[@r]
`to the rate difference between the I-frame rate and
`the average rate. From Eqn.(6), the minimum client
`buffer size depends on T d , E[P] and E[X]. E[p] de-
`pends on the type of the movie, and E[X] depends on
`
`Figure 3: State transitions of the client.
`,,c = v"p"
`(2)
`where the state transition matrix P" for the client is
`given by:
`
`Note that under normal circumstances, the client has
`a relatively small probability tobe in the FFW/FBW
`state. From the above transition matrix, we can ob-
`tain the steady &ate probability of the different client
`states. these equations, we obtain the st.ationarystate
`probabilities for the client states as:
`3.2 Client Buffer Size
`At any given time, the expected data rate con-
`sumed by the client is given by:
`
`where X i denote the rate at which data is consumed in
`state i . Since the frame rate of RIIPEG-2 is constant,
`pressed a,s: E[X] = [Vc + k(v," + VF)]E[@] where,
`the expected data consumption rate E[X] can be ex-
`E[p] is the average rate of the MPEG-2 video dur-
`ing playback. From our client model in Section 2.2,
`when the client performs a FFW/FBW operation,
`the server requests PCR from the network. Hon.-
`ever, during the bandwidth renegotiation process, the
`server keeps sending video at the playback rate. The
`renegotiation involves the server sending an RA{ cell
`and waiting for the RAJ cell to be returned from t,he
`
`PAGE 3 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009
`
`

`
`782
`
`3
`
`server t - + L L L L t - - + ~
`
`Figure 5: The server model
`
`Client
`
`Server
`
`bandwidth
`
`E[P] and the level of interact,ivity of the user. Since
`we can assume Td to be a constant for a network, the
`client buffer size is therefore determined by the type
`of movie and the level of user interactivity.
`3.3 Server Buffer Size
`Since the server sends video at the ACR denoted
`by pa, for no overflow/underflow at the server buffer,
`the long term dynamic variation of the server huffer
`accumulation per GoP should he zero:
`
`C J(buffer accumulation in a GOP) = o
`
`(7)
`
`all COP
`The expected value of ACR ( E [ p e ] ) should therefore
`satisfy the following condition:
`
`op(n/Tll - 1)Tf f , f l ~ ( 7 7 L - 1)78,/7id'f
`
`(8)
`The left, hand side of Eqn.(8) represent,s the amount
`of data sent, by the server, and the right hand side
`represents the sum of the data contained in movie.
`Snbstituting Eqn.(l) in Eqn.(8), we get:
`
`= E[B1
`(9)
`Because of the difference in ACR and the I-frame
`rat,e, t,he server buffer can be determined by raking
`into account the fact that difference must he stored
`in the server hnffer. Therefore, the minimum server
`buffer capacity C&can be expressed as:
`
`C,:,,, = ( W I I - m3I)Ts
`(10)
`Typically, for an MPEG-2 video with an M3N9 GoP,
`= 8.25 Mb/s, flp = 2.25 Mb/s and
`= 0.6
`Mb/s [SI. For a 30 frames per second video: Tf =
`0.033 sec and Eqn.(l) gives E[P] = 1.817 Mb/s. From
`Eqn.(lO), we obtain the minimum server buffer size
`to he about 25 Kbytes.
`4 Startup Delay Characteristics
`We define the .stavtup delay as the time between
`the user presses Playback (from t,he Stop state) to
`the start, of the video display, or the time between
`the user presses FFW/FBW to the start of the video.
`The startup dcluy- (Tu) consists of two puts: a fixcd
`part arising dne to the FRTT of the network and a
`dynamic part Tl which is required to fill the client
`
`Figure 6: Illustration of startup delay after a trick
`mode.
`
`buffer to the minimum fill level Cg, as shown in Fig-
`ure 6.
`To = 2Td + Tf
`(11)
`Assuming T d as constant, the startup delay depends
`on t,he minimum buffer fill level and the fillup rate
`which depends on the bandwidth allocated hy the
`network. When the server requests PCR from the
`network, the network may not he able to allocate
`the requested bandwidth. We assume an exponen-
`tial distribution for the ACR and we can express the
`approval probability of an ACR of p7 by:
`-o-
`P(pLT) = e
`(12)
`where cy is a parameter describing the network con-
`gestion; pcp and pm are the PCR and MCR respec-
`tively. We can obtain the expected value of the ACR
`(E[pLT]) during FFW/FBW as:
`
`* p - * -
`
`The denominator in Eqn. (13) can be expressed as:
`
`where a = -A. The numerator in Eqn.(l3) can
`/aP-l'm
`be expressed as:
`
`up,,, + l)il5)
`-
`Substituting Eqns.(ll) and (15) into Eqn.(13) we get
`
`where q = p p / p m is the ratio of the PCR to MCR.
`To study the relationship between the expected ACR
`and the PCR, we differentiate Eqn.(lG) wit,li respect
`to q to obtain:
`
`PAGE 4 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009
`
`

`
`Figure 7:
`The minimum client buffer size versus
`FRTT for FFW/FBW probability of 0.05.
`
`Figure 8. The minimum client buffer size versus
`FFW/FBW probability for T d = 50 ms.
`
`520
`0
`
`002
`
`ow
`
`0 0 1
`0 0 8
`0 1
`P-IiholFiWorFBW
`
`012
`
`Old
`
`0 1 1
`
`018
`
`0 1
`
`From Eqn.(l6), we see that E[/1,] contains q. How-
`
`ever, from Eqn.(l7), 9 is independent of q.
`
`Therefore, we conclude that E[fiL,] linearly depends
`on q. Since M C R is chosen equal t o the average rate
`of the video which is constant for a specific movie,
`E[pr] therefore directly depends on P C R . Moreover,
`since the buffer fillup rate directly depends on E[fi,],
`we conclude that the expected buffer fillup rate varies
`linearly with P C R . This implies that the startup de-
`lay can be minimized simply by requesting a high
`P C R during connection set up. The expected dy-
`namic part of the startup delay E[Tf] in Eqn.(ll)
`can be obtained by:
`
`Since there is no closed form solution for the above
`integration, we evaluate it by numerical integration.
`5 Numerical Results
`The relationship between the minimum client
`buffer size and the FRTT as shown in Figure 7 for
`a probability of 0.05 of moving to the FFW/FBW
`state, and two different GoPs representing two differ-
`ent video rates. We not,ice that the minimum client
`buffer size increases linearly wit,h the FRTT. Note
`that an M3N9 GoP has a higher bit rate than an
`M3N15 GoP. For large values of FRTT (correspond-
`ing to a WAN/MAN), the buffer required for M3N9
`COP is larger than for M3N15 GoP. For small FRTT
`(corresponding to a LAN), M3N15 GoP requires a
`larger buffer than M3N9 GoP. This is explained by
`the fact that, for small FRTT, the first part of Eqn. (6)
`is small and the client buffer size is dominated by the
`second term of Eqn. (6) which is the rate difference
`between the I-frame and the average rate.
`Figure 8 illustrates the minimum client buffer
`size corresponding to FFW/FBW probabilities in the
`
`Figure 9: Expected A C R versus P C R / M C R for a
`constant network congestion status.
`
`range 0-0.2 with a fixed FRTT. Since an M3N9 GoP
`has a higher data rate than an M3N15 GoP, M3N9
`GoP requires a larger buffer.
`In FBF scheme, the server requests a high band-
`width only if the client performs a FFW/FBW opera-
`tion or performs a Start operation. It doesn’t need to
`renegotiate bandwidth for each GoP as in [4]. There-
`fore, the FBF scheme simplifies bandwidth allocation
`for the network at the price of increasing the mini-
`mum buffer size requirement at the client.
`The expected A C R (obtained from Eqn. (16)) ver-
`sus the P C R for a constant network congestion is
`shown in Figure 9, while the expected ACE versus the
`network congestion status for a constant P C R I M C R
`The expected ACE
`ratio is shown in Figure 10.
`depends on the network congestion status and the
`negotiated P C R and M C R during connection set
`up. From Figure 9, we find that, the expected ACR
`increases linearly with an increase in the ratio of
`
`PAGE 5 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009
`
`

`
`784
`
`Figure 10: Expected ACR versus the network con-
`gestion status for fixed PCRjhICR.
`
`PCRIMCR as predicted Eqn. (16). This implies that
`the expected ACR citii be set to a desired value by
`setting a suitable PCR during connection set up.
`Figure 10 shows that the expected ACR decrease
`rapidly when the network congestion increases. This
`means that, when the net,work is congested.
`the
`startup delay will increase dramatically. Also, Fig-
`nres 9 and Figure 10 show that the expected ACR
`depends only on the net,work congestion status.
`The expected value of the dynamical startup delay
`MCR is cal-
`( E [ T f ] ) versus the difference PCR
`culated from Eqn. (18) and is shown in Figure 11.
`We find that the M3N9 and M3N15 GoPs have the
`same dynamic startup delay for the same level of net-
`work congestion. Moreover, (E[T/]) decreases expo-
`nentially with higher values of PCR ( M C K is chosen
`to equal to the average rates of the video)
`6 Conclusion
`In this paper, we proposed the FBF scheme to run
`video on demand over the 4BR service of an ATM
`
`~
`
`network. We have developed models for the client,
`the server, the network and a highly interactive user.
`We have used the models to determine the minimum
`buffering requirements at the client and the server.
`The proposed FBF scheme simplifies the network-
`ing bandwidth allocation because it does not need
`t,o renegotiate bandwidth frequently.
`Numerical results show that the minimum size of
`the client buffer depends linearly on the FRTT of the
`system. It also depends on the GoP which affects
`the burstiness of the video stream. For a LAN, the
`contribution to the minimum client buffer size is dom-
`inated by the burstiness of the video stream. For a
`WAN, the minimum client buffer size is mainly de-
`cided by the FKTT of the network. The startup de-
`lay depends directly on the network congestion sta-
`tus, the PCR, and MCR negotiated at connection
`set, up. The higher the PCR; the faster is the filling
`up of the client buffer. Resuks also illustrate that
`there is no difference in the startup delay for differ-
`ent GoPs. Therefore, a video with any GoP can be
`used as the source in a multimedia system using the
`proposed FBF scheme.
`References
`and
`Hemant Kanakia, Partho P. Mishra,
`.4my R. R.eihman, "An adaptive congestion con-
`trol scheme for real time packet video transport,"
`IEEE/ACM Transaction on Networking, vol. 3,
`no. 6, pp. 671-682, December, 1995.
`Marwan Krunz and Satish K. Tripath, "Exploit-
`ing the temporal structure of MPEG-'2 video for
`the reduction of bandwidth requirement," JEEE
`INFOCOM'S'I. Kobe, Japan, pp. 143-150, April
`1997.
`Jean M. Macmanus and Keith W. Ross, "Video
`on demand over ATRI: constant-rate transmission
`INFOCOM'SG,
`and transport," Proceedings of
`San Francisco, pp. 1357.-1362; March 1996.
`
`Bing Zheng and Mohammed Atiquzzaman,
`"Video on demand over ATM system design and
`networking requirements." ENCOM'S8-The En-
`terprise Networkiiq and Computing'&?, Atlanta,
`June 7-11 1998.
`Lawrence G. Roberts: "Can ABR. service replace
`VBR service in ATM network," Proceedings of
`the COMPCON'SJ' Conference, Piscatway, New
`Jersy, pp. 346-348: 1995.
`
`PAGE 6 OF 6
`
`I.M.L. SLU'S EXHIBIT 1009