We study data integrity verification in peer-to-peer media streaming for content distribution. Challenges include the timing constraint of streaming as well as the untrustworthiness of peers. We show the inadequacy of existing data integrity verification protocols, and propose Block-Oriented Probabilistic verification (BOPV), an efficient protocol utilizing message digest and probabilistic verification. We then propose Tree-based Forward Digest Protocol (TFDP) to further reduce the communication overhead. A comprehensive comparison is presented by comparing the performance of existing protocols and our protocols, with respect to overhead, security assurance level, and packet loss tolerance. Finally, experimental results are presented to evaluate the performance of our protocols.

This paper presents design and evaluation of an adaptive streaming mechanism from multiple senders to a single receiver in Peer-to-Peer (P2P) networks, called P2P Adaptive Layered Streaming, or PALS. PALS is a receiver-driven mechanism. It enables a receiver peer to orchestrate quality adaptive streaming of a single, layer encoded video stream from multiple congestion controlled senders, and is able to support a spectrum of non-interactive streaming applications. The primary challenge in design of a multi-source streaming mechanism is that available bandwidth from each peer is not known a priori, and could significantly change during a session. In PALS, the receiver periodically performs quality adaptation based on aggregate bandwidth from all senders to determine (i) overall quality (i.e. number of layers) that can be collectively delivered from all senders, and more importantly (ii) specific subset of packets that should be delivered by each sender in order to gracefully cope with any sudden change in its bandwidth. Our detailed simulation-based evaluations illustrate that PALS can effectively cope with several angles of dynamics in the system including: bandwidth variations, peer participation, and partially available content at different peers. We also demonstrate the importance of coordination among senders and examine key design tradeoffs for the PALS mechanism.

Peer-to-peer (P2P) streaming is emerging as a viable communications paradigm. Recent research has focused on building efficient and optimal overlay multicast trees at the application level. However, scant attention has been paid to interactive scenarios where the end-to-end delay is crucial. Furthermore, even algorithms that construct an optimal minimum spanning tree often make the unreasonable assumption that the processing time involved at each node is zero. However, these delays can add up to a significant amount of time after just a few overlay hops and make interactive applications difficult. In this paper, we introduce a novel peer-to-peer streaming architecture called ACTIVE that is based on the following observation. Even in large group discussions only a fraction of the users are active at a given time. We term these users, who have more critical demands for low-latency, active users. The ACTIVE system significantly reduces the end-to-end delay experienced among active users while at the same time being capable of providing streaming services to very large multicast groups. ACTIVE uses realistic processing assumptions at each node and dynamically optimizes the multicast tree while the group of active users changes over time. Consequently, it provides virtually all users with the low-latency service that before was only possible with a centralized approach. We present results that show the feasibility and performance of our approach.

This paper presents the experimental design and implementation of Swarm, an integrated and scalable multimedia delivery platform. Swarm offers the adaptability, maintainability and scalability required to effectively support diversity in network and client access, including the provisioning for mobile devices. Based upon a topologically aware peer-to-peer substrate, comprised of a distributed set of cooperating nodes and a novel routing schemata, Swarm allows for the effective maintenance of multimedia transactions despite the dynamic properties introduced by wireless and mobile systems. We present the Swarm design, with particular emphasis on how the system maintains content and structural integrity whilst adaptability and dynamic stresses are prevalent. Finally, the experimental implementation of Swarm is discussed together with an analysis of its performance.

A number of technology and workload trends motivate us to consider the appropriate resource allocation mechanisms and policies for streaming media services in shared cluster environments. We present MediaGuard -- a model-based infrastructure for building streaming media services -- that can efficiently determine the fraction of server resources required to support a particular client request over its expected lifetime. The proposed solution is based on a unified cost function that uses a single value to reflect overall resource requirements such as the CPU, disk, memory, and bandwidth necessary to support a particular media stream based on its bit rate and whether it is likely to be served from memory or disk. We design a novel, segment-based memory model of a media server to efficiently determine in liner time whether a request will incur memory or disk access when given the history of previous accesses and the behavior of the server's main memory file buffer cache. Using the MediaGuard framework, we design a novel, more accurate admission control policy for streaming media servers that accounts for the impact of the server's main memory file buffer cache. Our evaluation shows that, relative to a pessimistic admission control policy that assumes that all content must be served from disk, MediaGuard delivers a factor of two improvement in server throughput.

In this paper, we propose a novel loopback approach in a two-level streaming architecture to exploit collaborative client/proxy buffers for improving the quality and efficiency of large-scale streaming applications. At the upper level we use an overlay to deliver video from a central server to proxy servers, at the lower level a proxy server delivers video with the help of collaborative caches. In particular, a proxy server and its clients in a local domain cache different portions of a video and form delivery loops. In each loop, a single video stream originates at the proxy, passes through a number of clients, and is passed back to the proxy. As a result, with limited bandwidth and storage space contributed by collaborative clients, we are able to significantly reduce the requirements of network bandwidth, I/O bandwidth, and cache space at a proxy. Furthermore, we develop local repair schemes to address the client failure issues for enhancing server quality and eliminating most repairing load at servers. For popular videos, our local repair schemes are able to handle most of single-client failures without service disruption and retransmissions from a central server. Our analysis and simulations have shown the efficacy of loopback in various settings.

We present Dagster, an end-host multicast scheme for delivering multimedia streams. Unlike previous schemes, Dagster does not constrain the amount of bandwidth a node must donate. Instead, it relies on a novel incentive scheme to encourage nodes to contribute more bandwidth to improve the total capacity of the system. The key idea behind the incentive is that Dagster allows a node with more donated bandwidth to preempt another node in the system. Dagster also allows a host to receive from multiple parents at the same time, thus is more resilient to node failures. Our simulation results show that Dagster's design leads to low rejection rate, high resilience to failure and smaller diameter. Furthermore, nodes that donate more bandwidth have lower rejection rate and are positioned fewer overlay hops away from the source, providing incentives for nodes to increase their contribution.

This paper describes the AutoQoS mechanism, which improves the timeliness of disk accesses for multimedia applications without requiring any explicit information about their constraints. Multimedia applications typically have periodic time constraints, meaning that they must complete data processing at periodic intervals in order to function correctly. This requirement extends to the disk system, because the application must access data on time in order to meet deadlines. By using Quality of Service algorithms for disk services, an application may receive enough bandwidth and isolation from other disk accesses to read data on time. Nevertheless, past approaches are restrictive because they require that disk bandwidth or deadlines be known and specified in advance. Our system infers from I/O behavior the bandwidth requirement of multimedia streams, and automatically adjusts allocations in order to provide Quality of Service without knowing the constraints or requiring intervention from the application.

Presently, IP-networked real-time streaming media storage has become increasingly common as an integral part of many applications. In recent years, a considerable amount of research has focused on the scalability issues in storage systems. Random placement of data blocks has been proven to be an effective approach to balance heterogeneous workload in a multi-disk environments. However, the main disadvantage of this technique is that statistical variations can still result in short term load imbalances in disk utilization, which in turn, cause large variances in latencies. In this paper, we propose a packet level randomization (PLR) technique to solve this challenge. We quantify the exact performance trade-off between our PLR approach and the traditional block level randomization (BLR) technique through analytical analysis. Our preliminary results show that the PLR technique outperforms the BLR approach and achieves much better load balancing in multi-disk storage systems.

We introduce Nemo, a novel peer-to-peer multicast protocol that achieves high delivery ratio without sacrificing end-to-end latency or incurring additional costs. Based on two simple techniques: (1) co-leaders to minimize dependencies and, (2) triggered negative acknowledgments (NACKs) to detect lost packets, Nemo's design emphasizes conceptual simplicity and minimum dependencies, thus achieving performance characteristics capable of withstanding the natural instability of its target environment. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We contrast the scalability and performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show that Nemo can achieve delivery ratios similar to those of comparable protocols under high failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 90%) and control-related traffic.

Modern mobile processors offer dynamic voltage and frequency scaling, which can be used to reduce the energy requirements of embedded and real-time applications by exploiting idle CPU resources, while still maintaining all applications' real-time characteristics. However, accurate predictions of task run-times are key to computing the frequencies and voltages that ensure that all tasks' real-time constraints are met. Past work has used feedback-based approaches, where applications' past CPU utilizations are used to predict future CPU requirements. Inaccurate predictions in these approaches can lead to missed deadlines, less than expected energy savings, or large overheads due to frequent voltage and frequency changes. Previous solutions ignore other `indicators' of future CPU requirements, such as the frequency of I/O operations, memory accesses, or interrupts. This paper addresses this shortcoming for memory-intensive applications, where measured task run-times and cache miss rates are used as feedback for accurate run-time predictions. Cache miss rates indicate the frequency of memory accesses and enable us to derive the latencies introduced by these operations. The results shown in this paper indicate improvements in the number of deadlines met and the amount of energy saved.

TCP is the de-facto standard transport-layer protocol in the Internet. However, TCP is generally considered to be inappropriate for delay-sensitive applications such as multimedia. This paper proposes a novel receiver-centered TCP (TCP-RC), which is a TCP modification at the receiver that is intended for delay-sensitive applications. The basic principle behind TCP-RC is that it achieves low latency at the expense of reliability. In particular, TCP-RC forges lost packets, passing them on to an enabled application. This allows low-latency transmission for a class of applications that do not demand full reliability. Results obtained from emulated experiments show that over a range of loss rates and round-trip times, TCP-RC has a significantly smaller average- and worst-case per-packet delay than regular TCP.

Multimedia systems use stream modules to perform operations on the streams that pass through them. To create services, programmers hand-code modules together to form a pipeline. While some advances have been made in automating this process, none yet exist that create pipelines that are fully aware of the system's resources. In this paper, we present the design and evaluation of the Graph Manager (GM), a pipeline scheduler that determines, on-the-fly, the best way to satisfy requests using stream modules and reusing existing streams in the system.

Streaming media servers send many datagrams, very quickly, on many different connections, hopefully without congesting the network. In addition, in order to adapt to constantly changing network conditions, they often demand the capability of late data choice, where they choose which data to send immediately before transmission. In this paper, we present a novel user-kernel interface for congestion-controlled datagram protocols that is both efficient and flexible. Our API consists of a packet ring located in shared memory. Applications enqueues packet descriptors directly onto the ring, without crossing the user-kernel boundary, and the kernel dequeues packets from the ring and sends them. This minimizes control and data transfers and gives good throughput. In addition, our API provides a mechanism that allows the application to go back and safely change, remove or even reorder previously-enqueued packets, right up until the kernel sends them. This design separates the mechanism for achieving QoS support from any particular QoS policy. We describe the interface and evaluate its performance. By reducing control transfers, the packet ring can even send zero-length packets through the kernel faster than conventional send()-based UDP. Furthermore, on a congested network, an MPEG-like application using our DCCP API can deliver more than twice as many important "I-frames" than a CBR UDP sender in the same network conditions.

Wireless communication today supports heterogeneous wireless devices with a number of different wireless network interfaces (WNICs). A large fraction of communication is infrastructure based, so the wireless access points and hotspot servers have become more ubiquitous. Battery lifetime is still a critical issue, with WNICs typically consuming a large fraction of the overall power budget in a mobile device. In this work we present a new technique for managing power consumption and QoS in diverse wireless environments using Hotspot servers. We introduce a resource manager module at both Hotspot server and the client. Resource manager schedules communication bursts between it and each client. The schedulers decide what WNIC to employ for communication, when to communicate data and how to minimize power dissipation while maintaining an acceptable QoS based on the application needs. We present two new scheduling policies derived from well known earliest deadline first (EDF) and rate monotonic (RM) [26] algorithms. The resource manager and the schedulers have been implemented in the HP's Hotspot server [14]. Our measurement and simulation results show a significant improvement in power dissipation and QoS of Bluetooth and 802.11b for applications such as MP3, MPEG4, WWW, and email.

In order to enable a truly pervasive computing environment, next generation networks (including B3G and 4G) will merge the broadband wireless and wireline networking infrastructure. However, due to the tremendous complexity in administration and the unreliability of the wireless channel, provision of hard-guarantees for services on such networks will not happen in the foreseeable future. This consequently makes it particularly challenging to offer viable AV conferencing services due to their stringent synchronization, delay and data fidelity requirements. We propose in this paper a robust application-level solution for wireless mobile AV conferencing on B3G/4G networks. Expecting no special treatment from the network, we apply a novel adaptive delay and synchronization control mechanism to maintain the synchronization and reduce the latency as much as possible. We also employ a robust video coding technique that has better error-resilience capability. We investigate the performance of the proposed solution through simulations using a three-state hidden Markov chain as the generic end-to-end transport channel model. The results show that our scheme yields tight synchronization performance, relatively low end-to-end latency and satisfactory presentation quality. The scheme successfully provides a fairly robust AV conferencing service.

An optimal broadcasting scheme under the presence of secondary content (i.e. advertisements) is proposed. The proposed scheme works both for movies encoded in a Constant Bit Rate (CBR) or a Variable Bit Rate (VBR) format. It is shown experimentally that secondary content in movies can make Video-on-Demand (VoD) broadcasting systems more efficient. An efficient algorithm is given to compute the optimal broadcasting schedule with secondary content, which in particular significantly improves over the best previously known algorithm for computing the optimal broadcasting schedule without secondary content.

Efficient delivery of video data over computer networks has been studied extensively for decades. Still, multi-receiver video delivery represents a challenge. The challenge is complicated by heterogeneity in network availability, end node capabilities, and receiver preferences. This paper demonstrates that content-based networking is a promising technology for efficient multi-receiver video streaming. The contribution of this work is the bridging of content-based networking with techniques from the fields of video compression and streaming. In the presented approach, each video receiver is provided with fine grained selectivity along different video quality dimensions, such as region of interest, signal to noise ratio, colors, and temporal resolution. Efficient delivery, in terms of network utilization and end node processing requirements, is maintained. A prototype is implemented in the Java programming language and the software is available as open source. Experimental results are presented which demonstrate the feasibility of our approach.

The emergence of 3G networks gives rise to new mobile services in many different areas of our daily life. Examples of demanding mobile services are mobile-healthcare (i.e. m-health) services allowing the continuous monitoring of a patient’s vital signs. However, a prerequisite for the successful deployment of m-health services are appropriate performance characteristics of transport services offered by an underlying wireless network (e.g. 3G). In this direction, the EU MobiHealth project targeted the evaluation of 3G networks and their ability to support demanding m-health services. The project developed and trialled a patient monitoring system, evaluating at the same time the network's performance. This paper presents measurements based performance evaluation methodology developed and applied to assess network performance from an end-user perspective. In addition, it presents the (selected) speed-related evaluation (best-case scenario) results collected during the project. Our measurements show the dynamicity in the performance of 3G networks and phenomena negatively influencing this performance. Based on the evaluation results, we conclude that in-spite of certain shortcomings of existing 3G networks, they are suitable to support a significant set of m-health services. A set of recommendations provide a road map for both operators and service developers for design and deployment of m-health services.

Finding the causes of intermittent bugs and performance problems in modern systems is a challenging task. Conventional profilers focus on improving aggregate performance metrics in an application and disregard many problems that are highly visible to users but are deemed statistically insignificant. Finding intermittent bugs is also hard -- breakpoint debuggers change the timing of events, often masking the problem. To address these limitations, we propose a novel approach called self-propelled instrumentation -- using an autonomous agent to perform self-directed exploration of the system. We inject the agent into a running application, and the agent starts propagating through the code, carried by the application's flow of control. As it propagates, it inserts instrumentation dynamically to collect and analyze detailed execution information. The key feature of this approach lies in its ability to meet three requirements: high level of detail, low overhead, and autonomy (here, little reliance on human help). Existing techniques for tracing and profiling violate at least one of the requirements. As a proof of concept, we implemented a tool called spTracer that uses self-propelled instrumentation to obtain function-level traces from applications and the kernel. The tool enabled us to locate and fix three problems in unfamiliar code in the Linux environment.

Nowadays, multiple video cameras are employed for live broadcast and recording of almost all major social events in the TV industry, and all these camera streams have to be aggregated and rendered into one video program for audiences. While this content composition process aims at presenting the most interesting perspective of an event, it leads to the problem of how to fully customize the finally composed video program to different audience interests without requiring too much input from the audience. The goal of this work is to solve this problem by proposing the Automatic Video Production with User Customization (AVPUC) system that separates the video stream interestingness comparison from video program rendering to provide space for maximized customization. The unique feature of the AVPUC systems is that Human-controlled video selection and automatic video evaluation are combined to support video content customization and reduce redundant audience inputs. Preliminary evaluation results confirm that AVPUC's capturing-evaluation-render model for video production improves audiences' satisfaction for customized multi-perspective viewing of social events.

Quality of service (QoS) in delivery of continuous media (CM) over the Internet is still relatively poor, which is largely a result of packet losses often due to congestion. Previous work has shown that the use of multiple paths, existing in the network between a set of senders and a receiver, to deliver CM can be beneficial and should lead to improved QoS. In this paper, we study the problem of load distribution, i.e., properly distributing a CM stream among the multiple paths. We first focus on determining an appropriate optimization objective for computing the load distribution. We then conduct a performance study to understand the goodness of our optimization objectives and the resulting benefits of using multiple paths to deliver CM data.

By composing distributed, autonomous services dynamically to provide new functionalities, service composition provides an attractive way for customized multimedia content production and delivery. Previous research work has addressed various aspects of service composition such as composibility, QoS-awareness, and load balancing. However, most of the work has focused on applications where data flow from a single source is processed by intermediate services and then delivered to a single destination. In this paper, we address the service composition problem for advanced multimedia applications where data flows from multiple content sources are processed and aggregated into a composite flow, which is then delivered to one or more destinations, possibly after being customized for each receiver. We formally define the problem and prove its NP hardness. We also design a heuristic algorithm to solve the problem. Our algorithm has the following attractive features: (1) it is effective at finding low cost composition solutions; (2) it has the ability to trade off computation overhead for better results; (3) it is efficient and can scale to relatively large number of network nodes and component services.

This paper presents the architectural trade-offs to support fine-grain multi-resolution video over a wide range of resolutions. In the future, video streaming systems will have to support video adaptation over an extremely large range of display requirements (e.g. 90x60 to 1920x1080). While several techniques have been proposed for multi-resolution video adaptation, which is also known as spatial scalability, they have focused mainly on limited spatial resolutions. In this paper, we examine the ability of current techniques to support wide-range spatial scalability. Based upon experiments with real video, we propose an architecture that can support wide-range adaptation more effectively. Our results indicate that multiple encodings with limited spatial adaptation from each encoding provides the best trade-off between efficient coding and the ability to adapt the stream to various resolutions.