DIMACS Workshop on Multimedia Streaming on the Internet
June 12 - 13, 2000
DIMACS Center, Rutgers University, Piscataway, NJ
Presented under the auspices of the Special Focus on Next Generation Networks Technologies and Applications and the Special Year on Networks.
- Lixin Gao, Smith College, email@example.com
- Jennifer Rexford, AT&T Labs, firstname.lastname@example.org
The role of network proxies in supporting multimedia streaming
University of Southern California
In this talk present an overview of recent research in video
streaming, where our focus is exploring the potential benefits of
introducing video specific functions at proxies. Examples of such
functions include caching, local retransmission and
introduction/removal of error protection. We will argue that in a
network which shows increasing heterogeneity in terms of bandwidth,
delay and reliability, proxies can serve as the preferred tool to
enable adaptation, without requiring an end-to-end involvement of the
application. Moreover, we will argue that application- and
media-specific functions should be preferred to generic ones. We will
briefly discuss three examples to illustrate the benefits of
media-specific, proxy-based adaptation. First, we consider video
caching where the cache has the ability to store only a selected set
of frames from a video sequence. We show how this increases the
robustness of delivery to the receiver, in cases where cache storage
is limited. Second, we consider an example of local error control via
ARQ, where the final link to the client is assumed to be lossy. We
show how ARQ combined with rate control at the proxy can minimize the
loss of video information at the receiver. Finally, we discuss the
application of multiple description coding (MDC) for error robustness,
and describe an MDC approach where redundancy can be easily
controlled. This allows a proxy to increase or decrease the level of
redundancy, depending on whether the link to the client is more or
less reliable than the rest of the network.
Video Caching and Delivery Using Proxy Server for Reducing Bandwidth
Requirement over Wide Area Networks
Weihsiu Ma and David H.C. Du
Department of Compute Science and Engineering
University of Minnesota
Minneapolis, MN 55455
Due to the high bandwidth requirement and rate variability of compressed
video, delivering video across wide area networks (WANs) is a challenging
issue. Proxy servers have been used to cache web objects to alleviate the
of the web servers and to improve client access time on the Internet.
We assume a central server is connected to a proxy server via WAN and
a proxy server can reach many clients via Local Area Networks (LANs).
The proxy server allows partial video caching and thus a certain number
of video frames are stored in its storage such that the network bandwidth
requirement over WAN can be reduced. Since there are two video sources,
video data has to be synchronized before playback at a client.
Two delivery models, client-synchronization model and proxy-synchronization
model in terms of where to synchronize data are identified. The two models
have different complexity and resource consumption in proxy server and
In this talk, we mainly focus on the fundamental understanding on delivering
single video by using the two models and investigate the effectiveness of
the partial video caching in bandwidth reduction. We study the tradeoffs
between client buffer, start-up delay, resource requirement in the proxy
server, and bandwidth requirement over WAN for video transport.
Given a video delivery rate for the WAN, we propose several frame caching
selection algorithms to determine which frames of the video are to be stored
in the proxy server. In client-synchronization model, a scheme, which
partitions a video into different segments (chunks of frames) with
alternating chunks stored in the proxy server, is shown to offer the best
tradeoff. In proxy-synchronization model, caching the initial portion
(prefix) of a video is adopted and this approach is proved to minimize
the space requirement in proxy storage.
Issues in Design and Evaluations of Multimedia Proxy Caching
Mechanisms for the Internet.
Reza Rejaie; AT&T Labs - Research
Haobo Yu; USC/ISI
Most of the existing Internet multimedia streaming applications are
based on the client-server architecture; a media server pipelines a
stream to a client through the network while the client plays back
the available portion of the stream. This client-server architecture
has two major limitations: 1) The quality of the delivered streams
is limited to the bottleneck bandwidth between the server and the
client. Thus a client with a high bandwidth local connectivity may
receive low quality streams due to a remote bottleneck. 2) Its
scalability is limited, in that it is difficult to support a large
number of concurrent high quality sessions due to network and server
Multimedia proxy caching(MCaching) is a natural extension of the
client-server architecture that addresses all the above challenges
simultaneously. The idea is to cache popular streams with maximum
deliverable quality at a proxy close to interested clients. Thus the
proxy can effectively maximize delivered quality and improve
scalability by significantly reducing the load on the network and the
In this talk, we provide insight in the design and performance evaluations
of MCaching mechanisms. We argue that in addition to cache efficiency
(measured by hit ratio), MCaching introduces the notion of ``quality''
for delivered streams as a new dimension to Web caching. We first outline
the design of an efficient MCaching mechanism that consists of: 1) an
internal structure (e.g. layered) for cached streams, 2) a fine-grain
replacement mechanism based on fine-grain popularity and encoding-specific
information (e.g. utility), and 3) an online fine-grain prefetching
mechanism to further improve the delivered quality on-the-fly.
We then argue that performance of MCaching mechanisms should be
collectively evaluated along two dimensions: caching efficiency and
delivered quality. Specifically, we identify a fundamental tradeoff
between these two dimensions. Our simulation results show that our
proposed MCaching design can adaptively exploit this tradeoff to improve
overall performance whereas simple extension of current Web caching
schemes can only enhance the performance along one dimension.
Traffic Smoothing for Network Wide Streaming of Multimedia Traffic
JunBiao Zhang and Joseph Hui
Arizona State University
Traffic smoothing for video streams are considered
for network configurations such as single nodes, nodes in tandem and
routes in parallel. We may place constraints on
the smoothed traffic, such as rate constraints or on-off
constraints. Optimal algorithms are derived for some of these cases
minimizing delay or buffer requirements or
maximum rates. Experimental results are also presented
for traffic smoothing. We also explore how these results
could have an impact on practical implementations of video
streaming applications and signaling requirements.
Decentralized movie distribution in the Internet
Carsten Griwodz and Michael Zink
Damstadt University of Technology, Germany
After the failures of initial video-on-demand developments, the rapid growth
of the Internet is rising a new attraction to VoD-like applications. Intranet
VoD is successfully following the track of centrally managed video
distribution system. For public VoD, we consider it likely that such an
approach would fail as it did some years ago. Rather, decentralized
distribution systems that are organized in a similar way as the existing
video rental store infrastructures seem to be more adequate for adaptable
growth. In this talk, we present one consistent distribution infrastructure
based on caching and the results that we have produced so far in
investigating the unsolved issues of the infrastructure. Specifically, this
concerns protocol support, support for copyright violator tracing, and the
efficiency of the distribution system. A protocol suite that allows low
overhead reliable transfer of data into cache servers is introduced. In the
absence of multicast-capable watermarking !
schemes, an alternative, straight-forward, personalized movie marking scheme
is offered for discussion. Finally, the efficiency gains that can be achieved
by an interaction of caching strategies and new distribution mechanisms are
On Content Delivery Networks for Streaming Media
Abstract: We describe our ongoing project on a content
distribution network (CDN) for streaming media. CDNs support the delivery
of streaming media in an efficient and scalable manner. Multimedia sources
send a single stream to the CDN.
Based on the location and number of end-users, the CDN replicates the stream
(typically via a tree topology) as needed. Our architecture consists of an
overlay network of servers which exploit the functionality of IP Multicast
where available. Where IP Multicast is not available, the overlay servers
utilize unicast forwarding to reach end-systems. The servers also provide
packet recovery protocols which enable high perceived quality of service
through real-time recovery of lost packets. We compare our system with
emerging commercial CDNs, and discuss the challenges in this area.
Selecting among Replicated Multicast Video Servers
Mostafa H. Ammar
College of Computing
Georgia Institute of Technology
Server replication is often used to improve the scalability of a service.
One of the important factors in the efficient utilization of replicated
servers is the ability to direct clients to a server according to some
optimality criteria. Most server replication and selection work to date
has focused on traditional unicast services. We will first motivate the
need to replicate multicast video servers and argue that this is somewhat
different rationale from the one used to motivate unicast server replication.
We will then show some results from on-going work aimed at developing a
framework and a set of algorithms and protocols for multicast server
Frame-Based Periodic Broadcast and Fundamental Resource Tradeoffs
University of Massachusetts, Amherst
The Internet is witnessing a rapidly increasing load of continuous
media traffic in the form of streaming audio and video. Video streams
typically have high transmission bandwidth requirements, and exhibit
burstiness on multiple time scales, making it expensive to deliver
In this talk, we explore fundamental resource tradeoffs in periodic
broadcast, a technique for reducing network transmission bandwidth
requirements for streaming a popular video to multiple asynchronous
clients. We consider a class of frame-based periodic broadcast
schemes which assign a fixed transmission bandwidth to each frame in
the video, and continuously transmit each frame at this rate. The
model accommodates both CBR and VBR streams. We describe a novel
broadcast scheme that minimizes the transmission bandwidth overhead
under client buffer constraints. We also consider the problem of using
a single transmission scheme to satisfy clients with heterogeneous
resource constraints, and present a heuristic client reception scheme
to jointly minimize the client playback startup delay and client
buffer requirements. Finally, the talk concludes with results from
extensive evaluations that explore the tradeoffs among the network
transmission bandwidth requirement, and client resources (buffer,
reception bandwidth, and playback startup delay).
Algorithms for On-Demand Stream Merging
AT&T Shannon Labs
Richard E. Ladner
University of Washington and AT&T Shannon Labs
As the Internet grows so does the desire for on-demand streams
of many types: movies, songs, news stories, stock quotes,
and others. The popularity of a specific stream may be so high
that multicasting may be the only way to satisfy the demand.
In addition, clients requesting a stream will want service as quickly
as possible. This may require repeated multicasts of the same stream
to satisfy the delay guarantees. Stream merging has the potential to
help solve the bandwidth problems created by heavy, low delay, demand
for the same stream. In this talk we describe the stream merging
technique and how it can be used to reduce bandwidth requirements at
the stream server. We describe a new quadratic off-line algorithm for
minimizing bandwidth. We describe the optimal solution for the fully
loaded case, where streams are requested at unit time intervals.
We analyze the approximation ratio for oblivious off-line algorithms that
only know the number of requests and not their arrival times.
Finally, we briefly describe a new approach to on-line stream merging
based on our optimal oblivious offline algorithm. It turns
out that the Fibonacci numbers play an important role in the analysis.
TCP-like flow control for multimedia streaming using TCP
emulation at receiver (TEAR)
North Carolina State University
Congestion and flow control is an integral part of any Internet data
transport protocol. It is widely accepted that the congestion avoidance
mechanisms of TCP have been one of the key contributors to the success
of the Internet. However, TCP is ill-suited to real-time multimedia
streaming applications. Its bursty transmission, and abrupt and frequent
wide rate fluctuations cause delay jitters and sudden
quality degradation of multimedia applications. For asymmetric networks
such as wireless networks, cable modems, ADSL, and satellite networks,
transmitting feedback for (almost) every packet received as it is done in
TCP causes congestion in the reverse path, causing feedback losses and
delays. In this environment, TCP may severely under-utilize the forward
path throughput. Use of multicast further complicates the problem;
TCP-like frequent feedback from each receiver to the sender in a large
scale multicast session cause well-known scalability limitations,
such as acknowledgment implosion.
I have developed a new flow control approach for multimedia streaming,
called TCP emulation at receivers (TEAR). TEAR shifts most of flow control
mechanisms to receivers. In TEAR, a receiver does not send to the sender
the congestion signals detected in its forward path but rather processes
them immediately to determine its own appropriate receiving rate. TEAR
can determine this rate using congestion signals observed at the
receiver, such as packet arrivals, packet losses, and timeouts.
These signals are used to emulate the TCP sender's flow control functions
at receivers including slow start, fast recovery, and congestion
avoidance. The emulation allows receivers to estimate a TCP-friendly rate
for the congestion conditions observed in their forward paths.
TEAR also smoothes estimated values of steady-state
TCP throughput by filtering out noise. This smoothed rate estimate will
be reflected into the rate adjustment of receiving rates. Therefore,
TEAR-based flow control can adjust receiving rates to a TCP-friendly rate
without actually modulating the rates to probe for spare bandwidth, or to
react to packet losses directly. Thus, the perceived rate fluctuations
at the application are much more smooth than in TCP.
A unicast version of TEAR is implemented. In this talk, I will describe
the implementation of TEAR, examine the performance of this TEAR
implementation from the NS simulation and Internet experiments, and
compare it with that of other TCP-friendly flow control techniques. Our
preliminary tests indicate that TEAR shows superior fairness to TCP with
significantly lower rate fluctuations than TCP. TEAR's sensitivity
to feedback interval is very low, so that even under high feedback
latency, TEAR flows exhibit acceptable performance in terms of fairness,
TCP-friendliness, and rate fluctuations.
The Design and Implementation of a Media Independent
Streaming Service for Stored Video Applications
The Ohio State University
In this talk, we describe our work focused on delivering high-quality
content over best-effort networks (such as the Internet) for stored video
streams. The goal of this work is two-fold. First, we are interested
in using algorithms that adapt stored video sources efficiently to
the available network resources, avoiding high packet losses and
congestion collapse. Our approach advocates the use of TCP as the
transport mechanism for stored video delivery. In addition, our
delivery technique uses a priority-based algorithm that helps smooth
the frame rates delivered to the end user effectively. Second, we have
designed a media independent streaming service to show the viability of
our approach. By providing this media-independent interface, we hope
to catalyze future video-based applications such as scientific
Scaling Up Reliability for Broadband Video
The Internet is the number one broadcast medium of the future.
In a system where live and on-demand audio/video should reach
millions of people, thousands of network components are involved.
While the Internet was engineered based on basic
fault-tolerant paradigms, the complexity of the current video
networking technology increases the gap between
rich functionality and systems reliability.
We show an increase of over 48000% in mean time to failure for a
distributed video system over the standard solution.
Adaptive Streaming of Stored Layered Video over Lossy Channels
Srihari Nelakuditi Zhi-Li Zhang Sandeep C. Rao
University of Minnesota, Minneapolis
In recent years, most popular Internet application is web-based audio
and video playback where stored video is streamed from the server to a
client upon request. Rigid playback deadlines coupled with resource
constraints make video delivery a challenging task. Video smoothing
techniques reduce the bandwidth requirement by using client buffer for
pre-fetching. However, when both network bandwidth and client buffer are
limited it may not be possible to deliver full-quality video. In such a
situation, it is desirable to minimize the degradation in the video
quality while operating within the resource constraints. Layered
encoding is proposed to provide finer control on video quality where the
video signal is split into layers and a prefix of these layers is chosen
such that the resource constraints are met. However its is not feasible
to precompute the optimal number of layers since the network conditions
are continually varying. So the main concern is how to choose the ideal
number of layers adaptively based on the prevailing network conditions.
In our work, we address this layer selection problem for the case of
stored layered video delivery over lossy networks such as wireless. We
propose layer selection schemes that utilize the knowledge about the
bandwidth and buffer requirements of the stored video in delivering
smoother quality video.
One of the problems in assessing the performance of a video delivery
scheme is the lack of a good metric that captures the user's perception
of video quality. In general, the higher the amount of detail in the
played video, the better is its quality. However, it is generally
agreed that it is visually more pleasing to watch a video with
consistent, albeit lower, quality than one with highly varying quality.
Thus, a good metric should capture both, namely, the amount of detail
per frame as well as its uniformity across frames. In a layered video
delivery, ideally we would like to have a high mean and a low variance
in the number of layers per frame played. We devise a metric called
"mean layer run" which is defined as the number of layers a user is
expected to see continuously when the video is watched for a given
observation period starting at any arbitrary frame. This metric thus
accounts for both mean and variance and hence measures both detail and
uniformity of the video playback. In our work we use this metric to
measure the perceived quality of the delivered video for evaluating the
performance of various video delivery schemes.
We propose a MINimal Layer Discard algorithm (MINLD) that maximizes the
quality, under given network bandwidth and client buffer constraints, by
selectively discarding higher layers in order to minimize the likelihood
of future lower layers arriving late, thereby increasing the overall
quality of the video delivered. We develop an online variant of this
offline algorithm, called Finite Horizon based Minimal Layer Discard
(FHMLD) for adaptive layer selection. We apply this scheme to a
wireless setting where channel bandwidth is fixed and known but of
varying loss with retransmissions for error recovery. The video delivery
based on FHMLD scheme can be summarized as follows: periodic estimation
of loss rate based on observed channel conditions; estimation of
effective bandwidth and effective delay based on measured loss rate;
selective layer level discard based on effective bandwidth, effective
delay; discarding of packets that would anyway arrive late. We simulate
and show that FHMLD is better in maintaining consistent quality playback
than a simple greedy layer selection scheme. We are currently in the
process of extending our scheme to the case where both bandwidth and
loss are unknown and varying.
Optimal Streaming of Layered Video
This paper presents a model and theory for streaming layered video. We
model the bandwidth available to the streaming application as a stochastic
process whose statistical characteristics are unknown a priori. The random
bandwidth models short term variations due to congestion control (such as
TCP-friendly conformance). We suppose that the video has been encoded
into a base and an enhancement layer, and that to decode the enhancement
layer the base layer has to be available to the client. We make the
natural assumption that the client has abundant local storage and attempts
to prefetch as much of the video as possible during playback. At any
instant of time, starvation or partial starvation can occur at the client
in either of the two layers. During periods of starvation, the client
applies video error concealment to hide the loss. We study the dynamic
allocation of the available bandwidth to the two layers in order to
minimize the impact of client starvation. For the case of an
infinitely-long video, we find that the optimal policy takes on a
surprisingly simple and static form. For finite-length videos, the optimal
policy is a simple static policy when the enhancement layer is deemed at
least as important as the base layer. When the base layer is more
important, we design a threshold policy heuristic which switches between
two static policies. We provide numerical results that compare the
performance of no-prefetching, static and threshold policies.
Striping Doesn't Scale: How to Achieve Scalability for
Continuous Media Servers with Replication
University of Maryland
Multimedia applications place high demands for QoS, performance, and
reliability on storage servers and communication networks. These, often
stringent, requirements make design of cost-effective and scalable
continuous media (CM) servers difficult. In particular, the choice of
data placement techniques can have a significant effect on the scalability
of the CM server and its ability to utilize resources efficiently.
In the recent past, a great deal of work has focused on ``wide'' data striping.
Another approach to dealing with load imbalance problems is replication.
The appropriate compromise between the degree of striping and the degree of
replication is key to the design of scalable CM servers. Thus, the main focus
of this work is a study of scalability characteristics of CM servers as a
function of tradeoffs between striping and replication.
Semantic Transformation of Multimedia Streams inside an
C&C Research Laboratories, NEC USA, Inc.
Providing multimedia services to a large number of heterogeneous clients
raises the fundamental problem of incompatibility between the native
format of the media on the server, and the optimal format for each client.
This brings up the need for transforming a multimedia stream, not only to
reduce bit-rate, but also to enhance the acceptability of its play-out. We
discuss the implications of performing such media stream transformations
at different positions in the network, and propose a programmable network
architecture for providing this service. We also describe an experimental
testbed we built to determine the feasibility of our ideas.
eSeminar Project Overview
Martin G. Kienzle
The research objective of the eSeminar project is to provide a test bed for
experiments with advanced multimedia technology in the operational setting
of a complete end-to-end system, and to provide an integration point for
many multimedia technologies. The operational goal of the system is to
improve communication in the IBM Research Division by recording video of
talks and meetings, as well as collateral information, and making it
available to all Research employees worldwide. In order to make this
system truly usable, we want to automate all aspects of recording and
distribution to radically reduce the operational complexity cost, and to
let the system completely "fade into the background". A second usability
goal is to facilitate focused video access through indexing and other meta
data, and to improve ease of access, to make the information available and
usable to a very large number of people.
One of the greatest inhibitors of the deployment of digital video
information systems has been that many technologies, such as capture,
encoding, application design, hosting, and distribution have been developed
as individual technologies, but have rarely been integrated in systems that
have sufficient functional breadth and operational stability to evaluate
the individual technologies in a broader context. eSeminar is an
integration point to evaluate advanced media technologies in an operational
setting that is to be used in the everyday lives of people. More
specifically, the eSeminar objectives are:
? Create a video library of events for everybody at any IBM Research
site to watch on-demand.
? Support a large number of videos for on-demand viewing .
? Support a large number of simultaneous on-demand streams.
? Transmit videos of events live as appropriate
? Make slides and other collateral data available where possible.
? Support sophisticated indexing tools and allow users focused access to
the material: turn video from a sequential medium into a direct access
eSeminar is operational at the Watson, Zurich, Austin, Almaden, and Tokyo
sites, with work ongoing to bring the Beijing and Haifa labs into the
system. Each site has a VideoCharger server to stream the videos locally
on the LAN, and a web site to provide access to the videos and to
collateral information. The eSeminar system is comprised of three workflow
Production: The videos are being recorded on portable video servers in
MPEG-1. In a specially equipped conference room, we use an automated
camera management system for operator less video recording. When
appropriate, speakers' slides are captured as images and are
synchronized with the video. Our next research target is to automate
the production and recording to the point that a user has only to fill
some information into a web form, click a button, and the recording
proceeds automatically without further human intervention.
Postproduction: The videos are transcoded into low bit rate videos
(MPEG-1, CIF, 10 fps, 200 kbps video, 64 kbps audio). This low bit
rate is required to avoid overloading the LANs at the various sites.
Next, we are using scene change recognition to create thumbnails of
video scenes for directly accessing scenes of the video. Then, we are
integrating thumbnails of recorded slides into the video story board.
Once an MPEG-1 file exists, the story board creation and the web page
generation are well automated.
We are now looking to integrate other indexing methods such as
audio-based speech recognition and keyword indexing. After indexing
off-line is complete we expect to move to on-line indexing. This will
allow users instantaneous access to meta data. For instance, somebody
who joins a talk late can use the capture data to catch up.
Distribution & hosting: The videos, the collateral material, and the
related web pages are transmitted to the other sites using ftp. The
content of the remote servers is managed from a central site. We have
prototyped a content distribution management system that uses usage
frequency as well as storage constraints to manage the media on
distributed media server. We expect this system to be integrated into
eSeminar to automate content management.
This is a brief overview of the current function, and of our near-term
research objectives. In addition, we will present our experience in
operating the system, and we will discuss problems we are currently
Contacting the Center
Document last modified on May 9, 2000.