IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`429
`
`Video Staging: A Proxy-Server-Based Approach
`to End-to-End Video Delivery over Wide-Area
`Networks
`
`Zhi-Li Zhang, Member, IEEE, Yuewei Wang, Member, IEEE, David H. C. Du, Fellow, IEEE, and Dongli Su
`
`Abstract—Real-time distribution of stored video over wide-area
`networks (WANs) is a crucial component of many emerging dis-
`tributed multimedia applications. The heterogeneity in the under-
`lying network environments is an important factor that must be
`taken into consideration when designing an end-to-end video de-
`livery system.
`In this paper, we present a novel approach to the problem of
`end-to-end video delivery over WANs using proxy servers situated
`between local-area networks (LANs) and a backbone WAN. A
`major objective of our approach is to reduce the backbone WAN
`bandwidth requirement. Toward this end, we develop an effec-
`tive video delivery technique called video staging via intelligent
`utilization of the disk bandwidth and storage space available at
`proxy servers. Using this video staging technique, only part of a
`video stream is retrieved directly from the central video server
`across the backbone WAN whereas the rest of the video stream
`is delivered to users locally from proxy servers attached to the
`LANs. In this manner, the WAN bandwidth requirement can be
`significantly reduced, particularly when a large number of users
`from the same LAN access the video data. We design several
`video staging methods and evaluate their effectiveness in trading
`the disk bandwidth of a proxy server for the backbone WAN
`bandwidth. We also develop two heuristic algorithms to solve the
`problem of designing a multiple video staging scheme for a proxy
`server with a given video access profile of a LAN. Our results
`demonstrate that
`the proposed proxy-server-based approach
`provides an effective and scalable solution to the problem of the
`end-to-end video delivery over WANs.
`
`Index Terms—End-to-end video delivery, heterogeneous net-
`working environment, MPEG, proxy server, video smoothing,
`video staging, video streaming.
`
`I. INTRODUCTION
`
`R EAL-TIME distribution of stored video over high-speed
`
`networks is a crucial component of many emerging
`multimedia applications including distance learning, digital li-
`brary, Internet TV broadcasting and video-on-demand systems.
`Because of its high bandwidth requirement, video is typically
`stored and transmitted in compressed format. As a result, video
`
`Manuscript received August 21, 1998; revised December 19, 1998 and
`July, 1999; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor
`S. McCanne. This work was supported in part by University of Minnesota
`Graduate School Grant-in-Aid, National Science Foundation CAREER Award
`Grant NCR-9734428, and National Science Foundation Grant ANI-9903228.
`This paper was presented in part at the IEEE INFOCOM’98 conference.
`Z.-L. Zhang and D. H. C. Du are with the Department of Computer Sci-
`ence and Engineering, University of Minnesota, Minneapolis, MN 55455 USA
`(e-mail: zhzhang@cs.umn.edu; du@cs.umn.edu).
`Y. Wang and D. Su are currently with 3CX Inc., San Jose, CA 95125 USA
`(e-mail: ywang@3cx.com; dsu@3cx.com).
`Publisher Item Identifier S 1063-6692(00)06797-2.
`
`traffic can be highly bursty, possibly exhibiting rate variability
`spanning multiple time scales. This is particularly the case
`when constant-quality variable-bit-rate (VBR) compression
`algorithms are used [3]. Due to the bursty nature of compressed
`video, support for quality-of-service (QoS) guarantees for
`real-time transport of stored video across a network is therefore
`a challenging problem. This problem is further compounded
`when video is delivered over a wide-area network (WAN)
`where several heterogeneous networks are interconnected.
`The heterogeneity in the underlying network environments
`is an important factor that must be taken into consideration in
`the design of many distributed multimedia applications. For ex-
`ample, consider a distance learning application in a large univer-
`sity which has several geographically separate campuses. Each
`campus has its own campus-wide high-speed local area network
`(LAN). These campus networks are typically interconnected to
`each other through a backbone WAN owned by a third party.
`Suppose that the distance learning center is situated in the main
`campus with a central video server supplying video-based mul-
`timedia course materials to all campuses over the WAN. The
`backbone WAN is typically shared by a large number of insti-
`tutions or users, and it is generally more expensive to deploy
`additional resources in the backbone WAN than in local area
`networks. Given the emerging gigabit networking technologies
`such as Gigabit Ethernet and Fiber Channel, the cost of in-
`stalling and running a local-area gigabit network becomes in-
`creasingly cheaper. On the other hand, the WAN bandwidth is a
`much more critical and costly resource than that of campus-wide
`LANs. Therefore, reducing the total bandwidth requirement of
`the backbone WAN should be an important objective in the de-
`sign of a real-time video delivery system in such a scenario. The
`heterogeneous networking environment of the aforementioned
`example is also fairly common in other settings, e.g., in a large
`corporation where its intranet consists of several geographically
`dispersed LANs interconnected by a WAN leased from a net-
`work service provider, or in a residential setting where several
`residential access networks (operated by one network service
`provider) are connected to a large backbone WAN operated by
`another service provider.
`In this paper, we present a novel proxy-server-based approach
`to the end-to-end video delivery over WANs. For simplicity of
`discussion, the WAN in question is assumed to comprise sev-
`eral local area networks interconnected by a backbone WAN
`(see Fig. 1 for a simple example), although our approach can
`be applied to networks with more general topology and config-
`uration. Video streams are delivered from a central video server
`
`1063–6692/00$10.00 © 2000 IEEE
`
`Comcast - Exhibit 1021, page 1
`
`

`

`430
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`Fig. 1. Video delivery over a simple heterogeneous networking environment.
`
`through the backbone WAN to a large number of users in the
`local area networks. As part of the network system architecture,
`we also assume that a special server with a disk storage system,
`which we shall refer to as a proxy (video) server,1 is installed in
`each LAN and is directly attached to the gateway router con-
`necting the LAN to the backbone WAN. This assumption is
`quite reasonable, given the relatively low cost of PC servers
`today. The major objective of our proxy-server-based video de-
`livery approach is to reduce the bandwidth requirement in the
`backbone WAN, whereas the bandwidth of LANs is assumed to
`be bountiful and thus not a major concern. We develop an effec-
`tive video delivery technique called video staging via intelligent
`utilization of the disk bandwidth and storage capacity available
`at proxy serves attached to the LANs. The basic idea behind the
`video staging technique is to prefetch a predetermined amount
`of video data and store them a priori at proxy servers—this op-
`eration is referred to as staging. Using the video staging tech-
`nique, only part of video data is retrieved directly from the cen-
`tral video server across the backbone WAN, whereas the rest of
`the video data is delivered to users from proxy servers attached
`to the LANs. In this manner, the WAN bandwidth requirement
`can be significantly reduced, particularly when a large number
`of users from the same LAN access the video data.
`Our proxy-server-based approach to the problem of
`end-to-end video delivery across WANs has several salient
`features. Because of the large storage space at a proxy server,
`for a given video, a sizable portion of its data can be staged at a
`proxy server. The video staging technique is designed in such a
`manner that the video data can be delivered across the backbone
`WAN using a constant-bit-rate (CBR) network service. Hence
`only fixed amount of (peak) bandwidth needs to be reserved
`
`1Although we use “proxy server” as the name for this special server, however,
`as will be clear later, the usage of proxy server in our context of real-time video
`delivery is quite different from the typical usage of a proxy server as a caching
`device in the context of web-based data applications. Despite this difference, we
`decide to borrow the terminology proxy server for lack of better nomenclature.
`
`from the central video server across the backbone WAN to
`a LAN, allowing simple admission control and scheduling
`mechanisms to be employed to ensure QoS guarantees for video
`delivery across the backbone WAN. This bandwidth reservation
`can also be done on an aggregate basis when multiple video
`streams are delivered from the central video server across the
`backbone WAN to the same LAN, thereby further simplifying
`the resource management and control in the backbone WAN.
`Furthermore, since the disk bandwidth and storage capacity
`available at a proxy server are shared by all users attached to
`the same LAN, statistical multiplexing gains can be effectively
`exploited to improve resource (e.g., disk bandwidth) utilization
`at the proxy server when multiple staged video streams are
`retrieved from the disk storage system of the proxy server
`across the LAN to various users on the LAN.
`We design several video staging methods and study their
`effectiveness in trading the disk bandwidth of a proxy server for
`the backbone WAN bandwidth. Given this trade-off in the disk
`bandwidth requirement of proxy server and the backbone WAN
`bandwidth requirement for each video stream, we proceed to in-
`vestigate the problem of how to determine the amount of video
`data from a collection videos to be staged at a proxy server
`with fixed disk bandwidth and disk storage space. We develop
`two heuristic algorithms to solve this problem. We evaluate our
`approach using simulations based on MPEG-1 video traces.
`Our results demonstrate that the proposed proxy-server-based
`approach provides an effective and scalable solution to the
`problem of the end-to-end video delivery over WANs.
`The remainder of our paper is organized as follows. In Sec-
`tion II, we describe our problem setting and present our proxy-
`server-based approach. In Section III, we present various video
`staging techniques in the context of a single video stream. In
`Section IV, we develop two heuristic algorithms to solve the
`problem of designing multiple video staging scheme for a proxy
`server with a given video access profile of a LAN. The paper is
`concluded in Section V.
`
`Comcast - Exhibit 1021, page 2
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`431
`
`Fig. 2. Proxy-server-assisted video delivery.
`
`II. PROBLEM SETTING
`
`In this paper, we study the problem of end-to-end video de-
`livery over heterogeneous networking environments. A simple
`example is shown in Fig. 1, where several local area networks
`are interconnected by a backbone WAN. As an important part
`of the network system architecture, we also assume that a proxy
`video server is installed in each LAN and is directly attached to
`the gateway router connecting the LAN to the backbone WAN.
`A central video server system with a large disk farm is con-
`nected to the backbone WAN through a high-speed LAN back-
`bone (from the perspective of clients in other LANs across the
`backbone WAN, the central video server system can be viewed
`as if it is attached directly to the backbone WAN).
`In a typical heterogeneous networking environment we
`consider in this paper, we assume that the backbone WAN and
`the LANs belong to different administrative domains, in other
`words, owned by different entities. There are frequently a large
`number of users concentrated at a LAN concurrently accessing
`the central video server across the backbone WAN. Under
`these circumstances, reducing the backbone WAN bandwidth
`required to delivery video from the central video server to users
`on the LANs is therefore a major objective in the design of
`the end-to-end video delivery system. Instead of replicating
`the central video server at each LAN, which is generally too
`expensive to be practical, installing inexpensive proxy (video)
`server with appropriate amount of resources such as disk
`bandwidth and storage space is likely to be a most feasible and
`cost-effective approach to achieve this objective.
`The fundamental contribution of our proxy-server-based ap-
`proach to the problem of end-to-end video delivery over het-
`erogeneous networks is the notion of video staging. The basic
`idea behind the video staging technique is to prefetch a pre-
`determined amount of video data and store them a priori at
`proxy servers—this operation is referred to as staging. Unlike
`the caching technique commonly used in a proxy web server,
`where data files are cached in and purged out of the proxy web
`server based on on-line prediction of the random user access
`pattern, the video staging technique we develop in this paper
`determines the video data to be staged at a proxy video server
`based on several important factors which we will explain below.
`The video data are staged at the proxy server on a fairly long
`
`period of time instead of caching in and purged out dynami-
`cally. For example, in the case of a distance learning applica-
`tion, staged video data can be determined on a daily basis based
`on the course materials offered each day and the expected user
`access pattern to these materials.
`The objective of the video staging technique is to reduce
`the total backbone WAN (peak) bandwidth required for deliv-
`ering video to a large number of users on a LAN. As illustrated
`in Fig. 2, for a given video, if a portion of its video data is
`staged at a proxy server attached to a LAN, then when a user
`on the LAN accesses the video, only part of the video data is
`retrieved directly from the central video server across the back-
`bone WAN while the rest of the video data is delivered to the
`user from the proxy server. Since only a portion of the video
`data is transmitted across the backbone WAN, the bandwidth
`required is thus reduced. Moreover, if the video is accessed
`by a large number of users at the LAN, then this reduction
`in the backbone WAN bandwidth requirement can be signifi-
`cant. In the extreme case where the whole video is staged at the
`proxy server, then no backbone WAN bandwidth is required,
`and the video is delivered locally from the proxy server. Clearly,
`this reduction in the backbone WAN bandwidth requirement is
`achieved by consuming certain amount of resources such as the
`disk bandwidth and storage capacity at the proxy server. In light
`of the limited resources at a proxy server, it is therefore impor-
`tant to stage video data at a proxy server in such a manner that
`the total backbone WAN bandwidth required to deliver video to
`users on the associated LAN is maximally reduced while effi-
`ciently utilizing the resources at the proxy server.
`For a given video, the decision of whether to stage the entire
`video, or a portion of it, or none of it at a proxy server hinges on
`many factors. One important factor is the effectiveness of video
`staging in reducing the backbone WAN bandwidth requirement
`for the given video. This effectiveness will depend on both the
`characteristics of the video and the method used to decide which
`portion of the video to be staged at the proxy server. Such a
`method is referred to as a video staging method. Another impor-
`tant factor is the access pattern of a LAN, namely, the expected
`concurrent accesses to the video during a certain period of time.
`If the video is expected to be accessed numerous times by a large
`number of users on a LAN, it will likely be a good idea to stage
`the entire or a large portion of the video at the proxy server to
`
`Comcast - Exhibit 1021, page 3
`
`

`

`432
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`Fig. 3. Simple video staging method using a cut-off rate.
`
`WAN bandwidth reduction when clients have extra buffering
`capabilities available for smoothing.
`
`A. Video Staging Without Smoothing
`We first consider the case where clients have no extra
`buffering capabilities available for smoothing and describe a
`simple video staging method for this case. This simple method
`will form the basis for our study. In order to simplify resource
`management at the backbone WAN, we will assume that a
`CBR network service with minimal delay and no loss is used
`for video transport across the backbone WAN. Without the
`presence of a proxy server, when a video is delivered from the
`central video server to a user at a LAN, the bandwidth reserved
`across the backbone WAN must then be equal to the peak rate of
`the video. With the presence of a proxy server, however, we can
`stage a portion of the video at the proxy server so that a portion
`of the video data is delivered directly from the proxy server
`to a user on the LAN. In this way, we can use the resources
`(disk bandwidth and storage space among others) available at
`the proxy to reduce the backbone WAN bandwidth required
`for video delivery across the backbone WAN. However, this
`reduction is achieved by devoting certain amount of disk
`bandwidth and storage capacity available at the proxy server
`to store and deliver the staged video data. Since the resources
`(especially the disk bandwidth) at the proxy server are limited,
`it is important to consider the effectiveness of video staging in
`reducing the backbone WAN bandwidth for a given video.
`Consider a video indexed by
`
`reduce the backbone WAN bandwidth required to transmit the
`video. On the other hand, if the video is infrequently accessed,
`it may be better only to stage a small portion of it or none at
`all so that the disk bandwidth and storage space can be used
`for staging other videos. Given the video collection at the cen-
`tral video server, the expected number of accesses to each video
`can be derived from user access pattern of a LAN. This infor-
`mation is referred to the video access profile of the LAN. For a
`proxy server with limited amount of resources, particularly lim-
`ited amount of disk bandwidth and storage capacity, it is crucial
`to take both the video access profile and video characteristics
`into consideration when deciding the amount of video data to
`be staged at the proxy server. For a given collection of videos
`and a video access profile of a LAN, the problem of determining
`the amount of video data to be staged at the proxy server so as to
`minimize the total backbone bandwidth requirement is referred
`to as the multiple video staging design problem. The focus of
`the paper is thus on the developing video staging methods and,
`based on these methods, solving the multiple video staging de-
`sign problem.
`Before we delve into the details of our approach, we would
`like to point out that there are several implementation issues that
`must be resolved when applying the video staging technique in
`practice. For instance, if a portion of a video is staged at a proxy
`server while the rest of it is stored at the central video server,
`then these two portions of the video data must be synchronized
`during the playback of the video. This synchronization can be
`done either at the proxy server side or at the user side. In the
`former case, the video data stored at the central video server
`will be transmitted to the proxy server first, merged with the
`video data staged at the proxy server, and then delivered to a
`user. The disadvantage of this approach is that the processing
`capability of the proxy server can be a potential performance
`bottleneck. In the latter case, the two portion of the video data
`are delivered to a user separately, and then synchronized. This
`requires extra buffering capability and incurs more overhead at
`the user side. Another related issue is the signaling of the video
`delivery system, i.e., the issue of sending control signals to both
`the central video server and the proxy server to initiate the play-
`back of a video stream. For instance, these issues may be inves-
`tigated in the context of real-time transport protocol (RTP) [7]
`and real-time streaming protocol (RTSP) [8] protocols. Investi-
`gation of these issues is outside the scope of this paper, and will
`be the topics of future research.
`
`III. VIDEO STAGING: A SINGLE VIDEO CASE
`
`The effectiveness of staging video data at a proxy server in
`reducing the backbone bandwidth requirement can be measured
`by the ratio of the amount of the backbone WAN bandwidth
`reduction to that of the disk bandwidth required at the proxy.
`This ratio will be referred to as bandwidth reduction ratio. In this
`section, we present several video staging methods for a single
`video, and based on these methods, we study the effectiveness
`of video staging in reducing the backbone WAN bandwidth. We
`also integrate the optimal video smoothing technique [6] into
`the design of video staging methods to achieve further backbone
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`433
`
`server). From Fig. 3, we note that the smaller
`
`

`

`434
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`retrieval. Based on the experimental study in [10], we choose a
`block size of 200 kB which yields an effective bandwidth of ap-
`proximately 5 MB/s. From Table I, we observe that the storage
`capacity of an Elite-9 disk is about 9 GB.
`The purpose of our empirical study is to evaluate the effective-
`ness of using the disk bandwidth at the proxy server to reduce
`the backbone WAN bandwidth requirement. We first consider the
`case where only a single video stream is accessed, and thus there
`is no statistical multiplexing gain in disk retrieval. Assume that
`clients have no extra buffering capability for smoothing the video
`transmission. It is clear that for each unit of disk bandwidth con-
`sumed at the proxy server, we can reduce one unit of the back-
`boneWANbandwidthrequiredbystagingtheappropriateamount
`of video data at the proxy server. Thus the bandwidth reduction
`ratio
`
`(a)
`
`(b)
`
`Fig. 4. Video traces of (a) Wizard of Oz and (b) Star Wars.
`
`TABLE I
`ELITE-9 DISK PARAMETERS
`
`total of 41 762 frames and is approximately 23 minutes long,
`while the video Star Wars has a total of 174 055 frames and is
`approximately 96 minutes long. The frame rate is 24 frames/s
`for both videos.
`In our simulation, the disk system at the proxy server is mod-
`eled based on the Seagate Elite-9 disk, the relevant parameters
`of which is listed in Table I. We assume that the proxy server
`employs a simple two-buffer scheme for delivering staged video
`data of a video stream to a user on the LAN: during each round,
`one buffer is used to retrieve a block of video data from the disk
`system while the other is used to hold the previously retrieved
`video data block that is currently being transferred to the LAN.
`In the next round, the role of the buffers are swapped. The ef-
`fective disk bandwidth depends on the block size used in disk
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`435
`
`(a)
`
`(b)
`Fig. 5. Proxy server disk resource requirements for a single stream of Wizard of
`Oz. (a) Proxy server disk bandwidth requirement. (b) Proxy server disk storage
`requirement.
`
`tion ratio
`
`

`

`436
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`(a)
`
`(a)
`
`(b)
`Fig. 7. Ratio of backbone WAN bandwidth reduction to proxy server disk
`bandwith: single stream. (a) Wizard of Oz. (b) Star Wars.
`
`(b)
`Fig. 8. Effective per-stream disk bandwidth requirement when 100 streams of
`Wizard of Oz are statistically multiplexed (a) as a function of cut-off rate, and
`(b) as a function of percentage of staged video.
`
`conducted using the Star Wars trace are shown in Fig. 10. These
`figures show that the CAS method outperforms the three CBS
`methods most of the time and their performance tends to con-
`verge when a large amount of video data is staged at the proxy
`server.
`Before we leave this section, however, we would like to point
`out one shortcoming of the CAS method. For simplicity, we
`have assumed that all clients have a smoothing buffer of the
`same size. When client smoothing buffer sizes differ, the CAS
`method has to use the smallest buffer size to smooth a video
`stream before selecting a cut-off rate and then stage the corre-
`sponding upper part at a proxy server. On the other hand, the
`CBS approach can better accommodate this heterogeneity in
`client buffer capabilities by performing smoothing at the time
`of video retrieval and transfer. Due to space limitation, the re-
`sults from our study investigating this issue will not be included
`here.
`
`IV. VIDEO STAGING: MULTIPLE VIDEO CASE
`
`In the previous section, we have studied the effectiveness of
`video staging in reducing the backbone WAN bandwidth for a
`
`given video. One important problem remaining to be addressed
`is how to choose the cut-off rate so as to determine the amount
`of video data to be staged at a proxy server. In this section, we
`will study this problem in the context of multiple video staging
`with a given video access profile for a LAN. We first formulate
`the problem formally and then develop two heuristic algorithms.
`Lastly the two algorithms are empirically evaluated. Compar-
`ison with the approach where no proxy server is used is also
`made.
`
`A. Problem Formulation
`Given a set of videos, the expected number of accesses to
`these videos may vary dramatically depending on their popu-
`larity. User access pattern is thus an important factor that must
`be taken into account when determining the amount of video
`data to be staged at a proxy server. Zipf-like distributions [11]
`have been commonly used to characterize user access pattern
`in a video-on-demand environment [1], [9]. In Zipf distribution,
`the skew in the popularity of a set of
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`437
`
`(a)
`
`(b)
`Fig. 9. Bandwidth reduction ratio for multiple streams of Wizard of Oz. (a) 10
`streams. (b) 100 streams.
`
`

`

`438
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`Multiple Video Staging Design Problem: Given a video ac-
`cess profile
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`439
`
`Fig. 11. LBRRF algorithm.
`
`the algorithm is
`
`

`

`440
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`(a)
`
`(a)
`
`(b)
`Impact of proxy server disk resources: clients have no smoothing
`Fig. 13.
`buffer,  = 0:3. (a) Backbone WAN bandwidth reduction. (b) Proxy server
`disk storage utilization.
`
`(b)
`Impact of proxy server disk resources: clients have 64 kB smoothing
`Fig. 14.
`buffer,  = 0:3. (a) Backbone WAN bandwidth reduction. (b) Proxy server disk
`storage utilization.
`
`the current disk system, the disk bandwidth at the proxy server
`is more likely to be the bottleneck than the disk storage ca-
`pacity. We observe that the LBRRF algorithm consumes more
`disk storage space than the SHVO algorithm. The reason is as
`follows. Although the LBRRF algorithm only stages a portion
`of a video, it stages more videos than the SHVO algorithm does.
`Furthermore, by only storing the lower portion of the videos, the
`LBRRF algorithm can more effectively utilize the disk band-
`width of the proxy server and thus can afford to store more video
`data than the SHVO algorithm can.
`In the second set of experiments, we assume that clients have
`a smoothing buffer of size 64 kB. In Fig. 14(a), the backbone
`WAN bandwidth requirement under both the SHVO algorithm
`and the LBRRF algorithm is plotted as a function of the number
`of Elite-9 disks available at the proxy server. In this case, the
`LBRRF algorithm also outperforms the SHVO algorithm. In
`particular, when there are more than 9 disks, the total backbone
`WAN bandwidth requirement under the LBRRF algorithm is
`close to zero whereas the SHVO algorithm requires 15 disks to
`reduce the backbone WAN bandwidth requirement to zero. In
`order to demonstrate the superiority of the proxy-server-based
`
`approach in reducing the backbone WAN bandwidth, we also
`plot the backbone WAN bandwidth requirement when no proxy
`server is used but video smoothing is performed with the given
`client buffer. As shown in Fig. 14(b), the storage utilization of
`the two algorithms in this case is still less than 20% of the total
`disk storage space available at the proxy server.
`The results from two more sets of experiments are shown in
`Fig. 15(a) and (b), where the size of client smoothing buffer is
`increased to 1 and 8 MB respectively. The same observation ap-
`plies to these two cases, although the difference in the perfor-
`mance of the two heuristic algorithms appears to get smaller as
`the size of client smoothing buffer increases. In these cases, the
`proxy-server-based approach can still achieve significant reduc-
`tion in the backbone WAN bandwidth even when the number of
`disks at the proxy server is small. As before, the storage utiliza-
`tion of the two algorithms in these two cases is also less than 20%
`of the total disk storage space available at the proxy server. Due
`to space limitation, the corresponding figures are not shown here.
`In the last set of experiments, we investigate the impact of the
`skew parameters
`
`

`

`ZHANG et al.: VIDEO STAGING
`
`441
`
`(a)
`
`(a)
`
`(b)
`Fig. 15. Backbone WAN bandwidth reduction as clients have larger smoothing
`buffer.  = 0:3. (a) With 1 MB smoothing buffer. (b) With 8 MB smoothing
`buffer.
`
`(b)
`Impact of proxy server disk resources: clients have 1 MB smoothing
`Fig. 16.
`buffer.  = 0:9. (a) Backbone WAN bandwidth reduction. (b) Proxy server disk
`storage utilization.
`
`tion becomes less skewed. In other words, the accesses to the
`videos are more evenly distributed. Since the disk storage space
`is not the bottleneck, the “flatter” video access profile would en-
`able more videos to be staged in the proxy server. As a result,
`we would expect that the performance of the SHVO algorithm
`should somewhat be improved.This is confirmed by our exper-
`iments, as the results in Fig. 16(a) show. It is also interesting to
`notice that Fig. 16(b) shows that the SHVO algorithm has a higher
`disk storage utilization than the LBRRF algorithm in this case. In
`summary, the simulation results demonstrate that the LBRRF al-
`gorithm consistently outperforms the SHVO algorithm in terms
`of the WAN bandwidth reduction. We believe that the superior
`performance of the LBRRF algorithm is due to the fact that it
`takes both the video characteristics and the video access pattern
`into account via the WAN bandwidth reduction ratio.
`
`V. CONCLUSION
`
`In this paper, we have presented a novel approach to the
`problem of end-to-end video delivery over WANs using proxy
`servers situated between local-area networks (LANs) and a
`
`backbone WAN (WAN). A major objective of our approach
`is to reduce the backbone WAN bandwidth requirement.
`Toward this end, we have developed an effective video delivery
`technique called video staging through intelligently utilizing
`the disk bandwidth and storage space available at the proxy
`servers. We have designed various video staging methods and
`evaluated their effectiveness in trading the disk bandwidth of
`a proxy server for the backbone WAN bandwidth. We also
`developed heuristic algorithms for designing a multiple video
`staging scheme in a proxy server with a given video access
`profile for the associated LAN. Our results demonstrate that the
`proposed proxy-server-based video staging technique provides
`a cost-effective and scalable solution to the problem of the
`end-to-end video delivery over WANs.
`
`REFERENCES
`[1] A. Dan, D. Sitaram, and P. Shahabuddin, “Scheduling policies for an
`on-demand video server with batching,” in Proc. ACM Multimedia’94,
`Oct., pp. 15–21.
`[2] W. Feng and S. Sechrest, “Critical bandwidth allocation for delivery of
`compressed video,” Comput. Commun. (Special Issue on Systems Sup-
`port for Multimedia), Oct. 1995.
`
`Comcast - Exhibit 1021, page 13
`
`

`

`442
`
`IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 4, AUGUST 2000
`
`[3] M. Garrett and W. Willinger, “Analysis, modeling and generation of self-
`similar VBR video traffic,” in Proc. ACM SIGCOMM, London, U.K.,
`Aug. 1994, pp. 269–280.
`[4] A. R. Reibman and A. W. Berger, “Traffic descriptors for VBR video
`teleconferencing over ATM networks,” IEEE/ACM Trans. Networking,
`vol. 3, pp. 329–339, June 1995.
`[5] A. R. Reibman and B. G. Haskell, “Constraints on variable bit-rate video
`for ATM networks,” IEEE Trans. Circuits Syst. II, vol. 4, pp. 361–372,
`Dec. 1992.
`[6] J. Salehi, Z.-L. Zhang, J. Kurose, and D. Towsley, “Supporting stored
`video: Reducing rate variability and end-to-end resource requirements
`through optimal smoothing,” in ACM Int. Conf. Measurement and Mod-
`eling of Computer Systems (ACM SIGMETRICS), Philadelphia, PA, May
`1996.
`[7] H. Schulzrinne, S. Casner, R. Frederick, and S. McCane, “RTP: A trans-
`port protocol for real-time ap