Cloud-based Virtual Reality (VR) gaming enables immersive experiences without the need for costly high-end consumer hardware. However, it imposes substantial bandwidth requirements due to the need to stream high-resolution, high frame rate, and stereoscopic frames to maintain immersion and prevent motion sickness. Existing techniques like foveated rendering and encoding face challenges such as reliance on costly eye-tracking hardware and sensitivity to sudden gaze shifts. In addition, prior super-resolution methods can improve fidelity but are often too computationally heavy for practical deployment. To address these challenges, we propose iSR, a system that integrates stereo-aware colorization and super-resolution to reduce transmission cost while preserving visual quality. The key idea of iSR is that it first downsamples both stereo views to reduce the total number of transmitted pixels. Then, it transmits one view in full color and the other in monochrome. This removes redundant chrominance information and further reduces the required bandwidth. On the client side, iSR reconstructs full-color, high-resolution stereo frames by transferring chroma between views and enhancing spatial resolution. Extensive experiments across multiple VR games show that iSR achieves substantial bitrate reductions while maintaining high visual fidelity. These results highlight its potential for enabling high-quality VR streaming in bandwidth-limited environments.

We present GameLab, an open-source, AI-enabled cloud gaming testbed built on WebRTC. Unlike existing open-source stacks and deployment-oriented pipelines (e.g., GamingAnywhere, Sunshine/-Moonlight, and Unity Render Streaming), GameLab is designed for AI-in-the-loop systems research: it provides programmable interfaces on both the server and client, with well-defined hook points to plug in machine learning modules on demand (e.g., super-resolution, denoising, object detection, QoE estimation, and learned rate control). GameLab also collects detailed transport and application traces for online and offline analyses of gaming sessions and network behavior. To enable reliable objective evaluation in interactive settings, GameLab embeds compact QR-based frame identifiers into the video stream, allowing accurate computation of full-reference quality metrics, such as PSNR, SSIM, and VMAF, even under frame loss, reordering, and duplication. Finally, GameLab supports GPU-based visualization of frames and model outputs for interactive inspection without costly GPU-to-CPU transfers.

Several studies have shown that a significant fraction of fresh fruits is discarded at the retail and consumer levels, wasting precious resources, polluting the environment, and contributing to increased food prices. An important factor contributing to this problem is the lack of scalable solutions for determining fruit ripeness and remaining lifetime. We propose a cost-effective solution that leverages the sensing capabilities of phones and machine learning models to analyze the optical properties of fruits at various ripening stages. The proposed solution is non-invasive, works for different fruits, and produces intuitive outputs,e.g.Unripe/Ripe/Expired and the percentage of remaining lifetime, enabling retailers and consumers to minimize food waste. We implement a proof-of-concept mobile application, RipeTrack, and demonstrate the accuracy and robustness of the proposed approach using an extensive empirical study with multiple fruits, including avocados, pears, bananas, nectarines, and mangoes. Our results show, for example, that RipeTrack can identify the ripeness level of avocados and pears with an accuracy of 95% and 98%, respectively, and it can predict their remaining lifetimes with an accuracy of 93% and 97%. Our results also show that RipeTrack can easily be extended to new fruits using transfer learning, and it functions in realistic environments,e.g.homes and grocery stores, that have diverse illuminations.

Many recent video games require powerful hardware to render them. To reduce such high hardware requirements, upscalers have been proposed in the literature and industry. Upscalers save computing resources by first rendering games at lower resolutions and frame rates and then upscaling them to improve players' quality of experience. Current upscalers, however, are tightly coupled with the rendering logic of video games, which requires updating the source code of each game for every upscaler. This increases the development cost and limits the use of upscalers. The tight coupling also stifles the deployment of upscalers in cloud gaming platforms to reduce the required computing resources. We propose decoupling upscalers from game renderers, which allows utilizing various upscalers with games without changing their source code. It also accelerates deploying upscalers in cloud gaming. Decoupling upscalers from renderers is, however, challenging because of the diversity of upscalers, their dependency on information at different rendering stages, and the strict timing requirements of video games. We present an efficient solution that addresses these challenges. We implement the proposed solution and demonstrate its effectiveness with two popular upscalers. We also develop a cloud gaming system in the emerging Media-over-QUIC (MoQ) protocol and implement the proposed approach with it. Our experiments show the potential savings in computing resources while meeting the strict timing constraints of video games.

Regular glucose monitoring is crucial for diabetic patients to avoid the risk of health complications such as stroke, kidney failure, heart disease, and even death. Most current devices for measuring glucose are costly and painful. We propose GlucoSense, a non-invasive glucose sensing solution on mobile devices. GlucoSense builds on the fact that glucose is an optically active molecule, which interacts with various wavelengths. We first conduct spectral analysis to demonstrate the feasibility of measuring glucose in the visible and near-infrared range (400–1000 nm), which is the range available on mobile devices. We also identify the relative importance of various spectral bands in this range. We further propose multiple practical designs for obtaining the required spectral bands for measuring glucose. We then design GlucoSense exploiting the sensing capabilities of modern smartphones combined with machine learning models. We conduct an ethics-approved user study with a diverse set of participants in terms of age, sex, ethnicity, and body mass index (BMI). We compare GlucoSense against a widely-used, FDA-approved glucose measuring device. Our results show that 80.4% of GlucoSense predictions are within Zone A (clinically accurate), and the remaining 19.3% are in Zone B (clinically acceptable) of the Clarke Error Grid (CEG). In addition, 99.7% of the predictions are within the None and Slight risk zones of the Surveillance Error Grid (SEG), indicating their high accuracy. Both CEG and SEG are standard metrics for assessing glucose-measuring devices. These results were obtained by GlucoSense running on unmodified phones in realistic environments with diverse illuminations.

Recent AI tools can subtly manipulate images, eroding users’ trust in the authenticity of images they see on their displays. Current image authentication methods either detect artifacts that may result from manipulations or attach hashes of images as metadata for users to verify. The efficacy of the first approach is rapidly deteriorating with the continuous improvements in AI tools, leading to missing many serious manipulations. Hashes become invalid once images are subjected to any processing, such as re-sizing and transcoding. This makes the second approach impractical as most platforms, e.g., Facebook and X, perform several legitimate operations on images. Further, most platforms remove the metadata attached to images. We propose RDIAS, a robust and practical image authentication system. RDIAS securely embeds representative fingerprints into images without damaging their visual quality. We design these fingerprints to robustly detect malicious manipulations, e.g., adding/removing objects, while tolerating legitimate operations, e.g., image resizing and transcoding. Rigorous evaluation of RDIAS with diverse image datasets and realistic manipulations conducted by human subjects utilizing AI tools shows its high accuracy and efficiency. For example, RDIAS detects DeepFake manipulations that change facial features/expressions with an accuracy of 99%. The results also show that RDIAS preserves image quality and verifies authenticity in real time.

This article presents a review on the process of estimating player engagement in video gaming. To stay ahead of their competitors in entertainment, game developers need to understand, estimate, and maximize player engagement. We address the multidimensional nature of engagement, encompassing cognitive, emotional, and behavioral aspects across various gaming domains. We present a taxonomy of the diverse modalities for quantifying engagement, including physiological signals, observable behaviors, and gameplay data. We identify the challenges of conducting representative subjective studies in this domain and summarize various methods for establishing ground truth measurements. By synthesizing existing research, we provide insights into modeling techniques, highlight research gaps, and offer practical guidelines for implementing engagement measurement strategies. This review aims to aid researchers and industry professionals in navigating the complexities of player engagement estimation, ultimately contributing to enhanced game design, marketing, and user retention in the competitive gaming landscape.

Most current watermarking methods offer low and fixed capacity, which means they can only embed small-size watermarks into images. Additionally, they are typically robust to only a small subset of the known image transformations (aka distortions) that occur during the processing, transmission, and storage of images. These shortcomings limit their adoption in many practical multimedia applications. We propose FlexMark, a robust and adaptive watermarking method for images, which achieves a better capacity-robustness trade-off than current methods and can easily be used for different applications. FlexMark categorizes and models the fundamental aspects of various image transformations, enabling it to achieve high accuracy in the presence of many practical transformations. FlexMark introduces new ideas to further improve the performance, including double-embedding of the input message, employing self-attention layers to identify the most suitable regions in the image to embed the watermark bits, and utilization of a discriminator to improve the visual quality of watermarked images. In addition, FlexMark offers a parameter, α, to enable users to control the trade-off between robustness and capacity to meet the requirements of different applications. We implement FlexMark and assess its performance using datasets commonly used in this domain. Our results show that FlexMark is robust against a wide range of image transformations, including ones that were never seen during its training, which shows its generality and practicality. Our results also show that FlexMark substantially outperforms the closest methods in the literature in terms of capacity and robustness.

Hyperspectral imaging systems capture information in multiple wavelength bands across the electromagnetic spectrum. These bands provide substantial details based on the optical properties of the materials present in the captured scene. The high cost of hyperspectral cameras and their strict illumination requirements make the technology out of reach for end-user and small-scale commercial applications. We propose MobiSpectral, which turns a low-cost phone into a simple hyperspectral imaging system, without any changes in the hardware. We design deep learning models that take regular RGB images and near-infrared (NIR) signals (which are used for face identification on recent phones) and reconstruct multiple hyperspectral bands in the visible and NIR ranges of the spectrum. Our experimental results show that MobiSpectral produces accurate bands that are comparable to ones captured by actual hyperspectral cameras. The availability of hyperspectral bands that reveal hidden information enables the development of novel mobile applications that are not currently possible. To demonstrate the potential of MobiSpectral, we use it to identify organic solid foods, which is a challenging food fraud problem that is currently partially addressed by laborious, unscalable, and expensive processes. We collect large datasets in real environments under diverse illumination conditions to evaluate MobiSpectral. Our results show that MobiSpectral can identify organic foods, e.g., apples, tomatoes, kiwis, strawberries, and blueberries, with an accuracy of up to 94% from images taken by phones.

Reflections often degrade the quality of images by obstructing the background scenes. This is not desirable for everyday users, and it negatively impacts the performance of multimedia applications that process images with reflections. Most current methods for removing reflections utilize supervised learning models. These models require an extensive number of image pairs of the same scenes with and without reflections to perform well. However, collecting such image pairs is challenging and costly. Thus, most current supervised models are trained on small datasets that cannot cover the numerous possibilities of real-life images with reflections. In this paper, we propose an unsupervised method for single-image reflection removal. Instead of learning from a large dataset, we optimize the parameters of two cross-coupled deep convolutional neural networks on a target image to generate two exclusive background and reflection layers. In particular, we design a network model that embeds semantic features extracted from the input image and utilizes these features in the separation of the background layer from the reflection layer. We show through objective and subjective studies on benchmark datasets that the proposed method substantially outperforms current methods in the literature. The proposed method does not require large datasets for training, removes reflections from single images, and does not impose impractical constraints on the input images.

Cloud gaming enables users to play games on virtually any device. This is achieved by offloading the game rendering and encoding to cloud datacenters. As game resolutions and frame rates increase, cloud gaming platforms face a major challenge to stream high quality games due to the high bandwidth and low latency requirements. In this paper, we propose a new video encoding pipeline, called DeepGame, for cloud gaming platforms to reduce the bandwidth requirements with limited to no impact on the player quality of experience. DeepGame learns the player's contextual interest in the game and the temporal correlation of that interest using a spatio-temporal deep neural network. Then, it encodes various areas in the video frames with different quality levels proportional to their contextual importance. DeepGame does not change the source code of the video encoder or the video game, and it does not require any additional hardware or software at the client side. We implemented DeepGame in an open-source cloud gaming platform and evaluated its performance using multiple popular games. We also conducted a subjective study with real players to demonstrate the potential gains achieved by DeepGame and its practicality. Our results show that DeepGame can reduce the bandwidth requirements by up to 36% compared to the baseline encoder, while maintaining the same level of perceived quality for players and running in real time.

Reflections in videos are obstructions that often occur when videos are taken behind reflective surfaces like glass. These reflections reduce the quality of such videos, lead to information loss and degrade the accuracy of many computer vision algorithms. A video containing reflections is a combination of background and reflection layers. Thus, reflection removal is equivalent to decomposing the video into two layers. This, however, is a challenging and ill-posed problem as there is an infinite number of valid decompositions. To address this problem, we propose a user-assisted method for video reflection removal. We rely on both spatial and temporal information and utilize sparse user hints to help improve separation. The proposed method removes complex reflections in videos by including the user in the loop. The method is flexible and can accept various levels of user annotations, within each frame and in the number of frames being annotated. The user provides some strokes in some of the frames in the video, and our method propagates these strokes within the frame using a random walk computation as well as across frames using a point-based motion tracking method. We implement and evaluate the proposed method through quantitative and qualitative results on real and synthetic videos. Our experiments show that the proposed method successfully removes reflection from video sequences, does not introduce visual distortions, and significantly outperforms the state-of-the-art reflection removal methods in the literature.

Hyperspectral imaging provides rich information across many wavelengths of the captured scene, which is useful for many potential applications such as food quality inspection, medical diagnosis, material identification, artwork authentication, and crime scene analysis. However, hyperspectral imaging has not been widely deployed for such indoor applications. In this paper, we address one of the main challenges stifling this wide adoption, which is the strict illumination requirements for hyperspectral cameras. Hyperspectral cameras require a light source that radiates power across a wide range of the electromagnetic spectrum. Such light sources are expensive to setup and operate, and in some cases, they are not possible to use because they could damage important objects in the scene. We propose a data-driven method that enables indoor hyper-spectral imaging using cost-effective and widely available lighting sources such as LED and fluorescent. These common sources, however, introduce significant noise in the hyperspectral bands in the invisible range, which are the most important for the applications. Our proposed method restores the damaged bands using a carefully-designed supervised deep-learning model. We conduct an extensive experimental study to analyze the performance of the proposed method and compare it against the state-of-the-art using real hyperspectral datasets that we have collected. Our results show that the proposed method outperforms the state-of-the-art across all considered objective and subjective metrics, and it produces hyperspectral bands that are close to the ground truth bands captured under ideal illumination conditions.

Multicast service chaining refers to the orchestration of network services for multicast traffic. Paths of a multicast session that span the source, destinations and required services form a complex structure that we refer to as the multicast distribution graph. In this paper, we propose a new path-based algorithm, called Oktopus, that runs at the control plane of the ISP network to calculate the multicast distribution graph for a given session. Oktopus aims at minimizing the routing cost for each multicast session while satisfying all service chaining requirements. Oktopus consists of two steps. The first one generates a set of segments from the given ISP network topology, and the second step uses these segments to efficiently calculate the multicast distribution graph. Oktopus has a fine-grained control over the selection of links in the distribution graphs that leads to significant improvements. Specifically, Oktopus increases the number of allocated sessions because it can reach ISP locations that have the required services, and thus includes them in the calculated graph. Moreover, Oktopus can reduce the routing cost per session as it carefully chooses links belonging to the graph. We compared Oktopus against the optimal and closest algorithms using real ISP topologies. Our results show that Oktopus has an optimality gap of 5% on average, and it computes the distribution graphs multiple orders of magnitude faster than the optimal algorithm. Moreover, Oktopus outperforms the closest algorithm in the literature in terms of the number of allocated multicast sessions by up to 37%.

Face-based authentication systems are among the most commonly used biometric systems, because of the ease of capturing face images at a distance and in non-intrusive way. These systems are, however, susceptible to various presentation attacks, including printed faces, artificial masks, and makeup attacks. In this paper, we propose a novel solution to address makeup attacks, which are the hardest to detect in such systems because makeup can substantially alter the facial features of a person, including making them appear older/younger by adding/hiding wrinkles, modifying the shape of eyebrows, beard, and moustache, and changing the color of lips and cheeks. In our solution, we design a generative adversarial network for removing the makeup from face images while retaining their essential facial features and then compare the face images before and after removing makeup. We collect a large dataset of various types of makeup, especially malicious makeup that can be used to break into remote unattended security systems. This dataset is quite different from existing makeup datasets that mostly focus on cosmetic aspects. We conduct an extensive experimental study to evaluate our method and compare it against the state-of-the art using standard objective metrics commonly used in biometric systems as well as subjective metrics collected through a user study. Our results show that the proposed solution produces high accuracy and substantially outperforms the closest works in the literature.

A hyperspectral camera captures a scene in many frequency bands across the spectrum, providing rich information and facilitating numerous applications. The potential of hyperspectral imaging has been established for decades. However, to date hyperspectral imaging has only seen success in specialized and large-scale industrial and military applications. This is mainly due to the high cost of hyperspectral cameras (upwards of $20K) and the complexity of the acquisition system which makes the technology out of reach for many commercial and end-user applications. In this paper, we propose a deep learning based approach to convert RGB image sequences taken by regular cameras to (partial) hyperspectral images. This can enable, for example, low-cost mobile phones to leverage the characteristics of hyperspectral images in implementing novel applications. We show the benefits of the conversion model by designing a vein localization and visualization application that traditionally uses hyperspectral images. Our application uses only RGB images and produces accurate results. Vein visualization is important for point-of-care medical applications. We collected hyperspectral data to validate the proposed conversion model. Experimental results demonstrate that the proposed method is promising and can bring some of the benefits of expensive hyperspectral cameras to the low-cost and pervasive RGB cameras, enabling many new applications and enhancing the performance of others. We also evaluate the vein visualization application and show its accuracy.

Live streaming of immersive multimedia content, e.g., 360-degree videos, is getting popular due to the recent availability of commercial devices that support interacting with such content such as smartphones/tablets and head-mounted displays. Streaming live content to mobile users using individual connections (i.e., unicast) consumes substantial network resources and does not scale to large number of users. Multicast, on the other hand, offers a scalable solution but it introduces multiple challenges, including handling user interactivity, ensuring smooth quality, conserving the energy of mobile receivers, and achieving fairness among users. We propose a new solution for the problem of live multicast streaming of 360-degree videos to mobile users, which addresses the aforementioned challenges. The proposed solution, referred to as VRCast, is designed for cellular networks that support multicast, such as LTE. We show through trace-driven simulations that VRCast outperforms the closest algorithms in the literature by wide margins across several performance metrics. For example, compared to the state-of-the-art, VRCast improves the viewport quality by up to 2.5 dB. We have implemented VRCast in an LTE testbed to show its practicality. Our experimental results show that VRCast ensures smooth video quality and saves energy for mobile devices.

Telco-CDNs refer to content distribution networks deployed and managed by Internet Service Providers (ISPs). They are getting popular among major ISPs because they offer new revenue streams and have the potential of providing better performance compared to traditional CDNs. Managing telco-CDNs is, however, a complex problem, because it requires jointly managing the network resources (links and switches) and the caching resources (processing and storage capacities), while supporting the adaptive nature and skewed popularity of multimedia content. To address this problem, we present a new algorithm called CAD (Cooperative Active Distribution), which strives to serve as much as possible of the requested multimedia objects within the ISP while carefully engineering the traffic paths through the network. This is achieved by enabling the cooperation among caches within the ISP not only to serve various representations of multimedia objects, but also to create them on demand using the available processing capacity of caches. We have implemented CAD and evaluated it on top of a network emulator that runs deployment code and processes real traffic. Using an actual ISP topology, our experimental results show that CAD achieves substantial performance improvements compared to the closest work in the literature, e.g., up to 64% reduction in the total inter-domain traffic.

Due to recent technological advances in capturing and processing devices, hyperspectral imaging is becoming available for many commercial and military applications such as remote sensing, surveillance, and forest fire detection. Hyperspectral cameras provide rich information, as they capture each pixel along many frequency bands in the spectrum. The large volume of hyperspectral images as well as their high dimensionality make transmitting them over limited-bandwidth channels a challenge. To address this challenge, we present a method to prioritize the transmission of various components of hyperspectral data based on the application needs, the level of details required, and available bandwidth. This is unlike current works that mostly assume offline processing and the availability of all data beforehand. Our method jointly and optimally selects the spectral bands and their qualities to maximize the utility of the transmitted data. It also enables progressive transmission of hyperspectral data, in which approximate results are obtained with small amount of data and can be refined with additional data. This is a desirable feature for large-scale hyperspectral imaging applications. We have implemented the proposed method and compared it against the state-of-the-art in the literature using hyperspectral imaging datasets. Our experimental results show that the proposed method achieves high accuracy, transmits a small fraction of the hyperspectral data, and significantly outperforms the state-of-the-art; up to 35% improvements in accuracy was achieved.

Cloud gaming allows users with thin-clients to play complex games on their end devices as the bulk of processing is offloaded to remote servers. A thin-client is only required to have basic decoding capabilities which exist on most modern devices. The result of the remote processing is an encoded video that gets streamed to the client. As modern games are complex in terms of graphics and motion, the encoded video requires high bandwidth to provide acceptable Quality of Experience (QoE) to end users. The cost incurred by the cloud gaming service provider to stream the encoded video at such high bandwidth grows rapidly with the increase in the number of users. In this paper, we present a content-aware video encoding method for cloud gaming (referred to as CAVE) to improve the perceptual quality of the streamed video frames with comparable bandwidth requirements. This is a challenging task because of the stringent requirements on latency in cloud gaming, which impose additional restrictions on frame sizes as well as processing time to limit the total latency perceived by clients. Unlike many of the previous works, the proposed method is suitable for the state-of-the-art High Efficiency Video Coding (HEVC) encoder, which by itself offers substantial bitrate savings compared to prior encoders. The proposed method leverages information from the game such as the Regions-of-Interest (ROIs), and optimizes the quality by allocating different amounts of bits to various areas in the video frames. Through actual implementation in an open-source cloud gaming platform, we show that the proposed method achieves quality gains in ROIs that can be translated to bitrate savings between 21% and 46% against the baseline HEVC encoder and between 12% and 89% against the closest work in the literature.

Multimedia services like Skype, WhatsApp, and Google Hangouts have strict Service Level Agreements (SLAs). These services attempt to address the root causes of SLA violations through techniques such as detecting anomalies in the inputs of the services. The key problem with current anomaly detection and handling techniques is that they can't adapt to service changes in real-time. In current techniques, historic data from prior runs of the service are used to identify anomalies in the service inputs like number of concurrent users, and system states like CPU utilization. These techniques do not evaluate the current impact of anomalies on the service. Thus, they may raise alerts and take corrective measures even if the detected anomalies do not cause SLA violations. Alerts are expensive to handle from a system and engineering support perspectives, and should be raised only if necessary. We propose a dynamic approach for handling service input and system state anomalies in multimedia services in real-time, by evaluating the impact of anomalies, independently and associatively, on the service outputs. Our proposed approach alerts and takes corrective measures like capacity allocations if the detected anomalies result in SLA violations. We implement our approach in a large-scale operational multimedia service, and show that it increases anomaly detection accuracy by 31%, reduces anomaly alerting false positives by 71%, false negatives by 69%, and enhances media sharing quality by 14%.

A wide adoption of 3-D videos is hindered by the lack of high-quality 3-D content. One promising solution to this problem is through data-driven 2-D-to-3-D video conversion. Such approaches are based on learning depth maps from a large dataset of 2-D+Depth images. However, current conversion methods, while general, produce low-quality results with artifacts that are not acceptable to many viewers. We propose a novel, data-driven method for 2-D-to-3-D video conversion. Our method transfers the depth gradients from a large database of 2-D+Depth images. Capturing 2-D+Depth databases, however, are complex and costly, especially for outdoor sports games. We address this problem by creating a synthetic database from computer games and showing that this synthetic database can effectively be used to convert real videos. We propose a spatio-temporal method to ensure the smoothness of the generated depth within individual frames and across successive frames. In addition, we present an object boundary detection method customized for 2-D-to-3-D conversion systems, which produces clear depth boundaries for players. We implement our method and validate it by conducting user studies that evaluate depth perception and visual comfort of the converted 3-D videos. We show that our method produces high-quality 3-D videos that are almost indistinguishable from videos shot by stereo cameras. In addition, our method significantly outperforms the current state-of-the-art methods. For example, up to 20% improvement in the perceived depth is achieved by our method, which translates to improving the mean opinion score from good to excellent.

Mobile devices are getting increasingly popular all over the world. Mobile users in developing countries however rarely have Internet access which puts them at economic and social disadvantages compared to their counterparts in developed countries. We propose mBridge: A distributed system to disseminate multimedia content to mobile users with intermittent Internet access and opportunistic ad hoc connectivity. By disseminating various multimedia content such as news reports notification messages targeted advertisements movie trailers and TV shows mBridge aims to eliminate the digital divide. We formulate an optimization problem to compute personalized distribution plans for individual mobile users to maximize the overall user experience under various resource constraints. Our formulation jointly considers the characteristics of multimedia content mobile users and intermittent networks. We present an efficient distribution planning algorithm to solve our problem and we develop several online heuristics to adapt to the system and network dynamics. We implement a prototype system and demonstrate that our algorithm outperforms the existing algorithms by up to 206% 472% and 188% in terms of user experience disk efficiency and energy efficiency respectively. In addition we conduct trace-driven simulations to rigorously evaluate the proposed system in different environments and for large-scale deployments. Our simulation results demonstrate that the proposed algorithm substantially outperforms the closest ones in the literature in all performance measures. We believe that mBridge can allow multimedia content providers to reach out to more mobile users and mobile users to access multimedia content without always-on Internet access.

Reflections can obstruct content during video capture and hence their removal is desirable. Current removal techniques are designed for still images, extracting only one reflection (foreground) and one background layer from the input. When extended to videos, unpleasant artifacts such as temporal flickering and incomplete separation are generated. We present a technique for video reflection removal by jointly solving for motion and separation. The novelty of our work is in our optimization formulation as well as the motion initialization strategy. We present a novel spatiotemporal optimization that takes n frames as input and directly estimates 2n frames as output, n for each layer. We aim to fully utilize spatio-temporal information in our objective terms. Our motion initialization is based on iterative frame-to-frame alignment instead of the direct alignment used by current approaches. We compare against advanced video extensions of the state of the art, and we significantly reduce temporal flickering and improve separation. In addition, we reduce image blur and recover moving objects more accurately. We validate our approach through subjective and objective evaluations on real and controlled data.

Multiview videos offer unprecedented experience by allowing users to explore scenes from different angles and perspectives. Thus, such videos have been gaining substantial interest from major content providers such as Google and Facebook. Adaptive streaming of multiview videos is, however, challenging because of the Internet dynamics and the diversity of user interests and network conditions. To address this challenge, we propose a novel rate adaptation algorithm for multiview videos (called MASH). Streaming multiview videos is more user centric than single-view videos, because it heavily depends on how users interact with the different views. To efficiently support this interactivity, MASH constructs probabilistic view switching models that capture the switching behavior of the user in the current session, as well as the aggregate switching behavior across all previous sessions of the same video. MASH then utilizes these models to dynamically assign relative importance to different views. Furthermore, MASH uses a new buffer-based approach to request video segments of various views at different qualities, such that the quality of the streamed videos is maximized while the network bandwidth is not wasted. We have implemented a multiview video player and integrated MASH in it. We compare MASH versus the state-of-the-art algorithm used by YouTube for streaming multiview videos. Our experimental results show that MASH can produce much higher and smoother quality than the algorithm used by YouTube, while it is more efficient in using the network bandwidth. In addition, we conduct large-scale experiments with up to 100 concurrent multiview streaming sessions, and we show that MASH maintains fairness across competing sessions, and it does not overload the streaming server.

With the recent availability of commodity Virtual Reality (VR) products, immersive video content is receiving a significant interest. However, producing high-quality VR content often requires upgrading the entire production pipeline, which is costly and time-consuming. In this work, we propose using video feeds from regular broadcasting cameras to generate immersive content. We utilize the motion of the main camera to generate a wide-angle panorama. Using various techniques, we remove the parallax and align all video feeds. We then overlay parts from each video feed on the main panorama using Poisson blending. We examined our technique on various sports including basketball, ice hockey and volleyball. Subjective studies show that most participants rated their immersive experience when viewing our generated content between Good to Excellent. In addition, most participants rated their sense of presence to be similar to ground-truth content captured using a GoPro Omni 360 camera rig.

Recent advances in video capturing and rendering technologies have paved the way for new video streaming applications. Free-viewpoint video (FVV) streaming is one such application where users are able to interact with the scene by navigating to different viewpoints. Free-viewpoint videos are composed of multiple streams representing the captured scene and its geometry from different vantage points. Rendering non-captured views at the client requires transmitting multiple views with associated depth map streams, thereby increasing the network traffic requirements for such systems. Adding to the complexity of these systems is the fact that different component streams contribute differently to the quality of the final rendered view. In this paper, we present a free-viewpoint video streaming system based on HTTP adaptive streaming and the multi-view-plus-depth (MVD) representation. We propose a novel quality-aware rate adaptation method for FVV streaming based on a virtual view distortion model. This view distortion model represents the relation between the distortion of the texture and depth components of reference views and a target virtual view and enables the streaming client to find the best set of representations to request from the server. We have implemented the proposed rate adaptation method in a prototype FVV DASH-based streaming system and performed objective and subjective evaluation experiments. Our experimental results show that the proposed FVV streaming rate adaptation method improves the user's quality-of-experience and increases the visual quality of rendered virtual views by up to 4 dB for some video sequences. Moreover, users have rated the quality of videos streamed using our proposed method higher than videos streamed using other rate adaptation methods in the literature.

Interactive multimedia communication services, such as Skype, are complex and composed of software components typically implemented as web services. Efficient coordination of web services is challenging and expensive, due to the statelessness nature of web services, and because web services change over time. The existing protocols implementing web service transactions are inefficient. They waste resources due to their inability to selectively add/remove individual web services in transactions without incurring high overhead that affects the quality of multimedia sessions. We propose a simple and effective optimization to current web service transaction management protocols that allows individual web services to selectively participate in distributed transactions they contribute to. We implement the proposed approach in one of the largest multimedia communication services in the world, and find that it enhances the throughput of multimedia service distributed transactions by 36%, reduces failure rate by 35%, improves multimedia quality (Mean Opinion Score (MOS)) of succeeded transactions by 9%, and reduces the overall time required by all transactions by 35%.

Current cellular networks support video streaming over unicast or multicast. However, there exists a tradeoff between utilizing the two: i) unicast leads to higher network load, but lower energy consumption of mobile devices, and ii) multicast results in lower network load, but higher energy consumption. To make the best out of both, we propose to concurrently utilize unicast and multicast for minimizing the energy consumption of mobile devices and minimizing the load on cellular networks. Cellular networks support two multicast schemes: i) independent cell networks and ii) multi-cell single frequency networks, where multiple adjacent base stations operate on the same frequency. We first consider the less-complicated independent cell networks, and then extend our solution to single frequency networks for better performance. We formulate the resource allocation in hybrid multicast -unicast streaming systems as a binary integer programming problem. We describe optimal algorithms for the two multicast schemes. We then propose two efficient, heuristic, algorithms that run faster and provide close to optimal results. While our solution is general, for concreteness, we conduct detailed LTE packet-level simulations using OPNET. Our simulation results show the proposed algorithms i) scale to many more mobile devices than the state-of-the-art unicast-only approaches and ii) result in lower energy consumption than the latest multicast-only approaches. In addition, the algorithms designed for multi-cell single frequency networks outperform the algorithms designed for independent cell networks in all aspects, such as service ratio, spectral efficiency, energy saving, video quality, frame loss rate, initial buffering time, and number of re-buffering events.

Producing a high quality stereoscopic impression on current displays is a challenging task. The content has to be carefully prepared in order to maintain visual comfort, which typically affects the quality of depth reproduction. In this work, we show that this problem can be significantly alleviated when the eye fixation regions can be roughly estimated. We propose a new method for stereoscopic depth adjustment that utilizes eye tracking or other gaze prediction information. The key idea that distinguishes our approach from the previous work is to apply gradual depth adjustments at the eye fixation stage, so that they remain unnoticeable. To this end, we measure the limits imposed on the speed of disparity changes in various depth adjustment scenarios, and formulate a new model that can guide such seamless stereoscopic content processing. Based on this model, we propose a real-time controller that applies local manipulations to stereoscopic content to find the optimum between depth reproduction and visual comfort. We show that the controller is mostly immune to the limitations of low-cost eye tracking solutions. We also demonstrate benefits of our model in off-line applications, such as stereoscopic movie production, where skillful directors can reliably guide and predict viewers' attention or where attended image regions are identified during eye tracking sessions. We validate both our model and the controller in a series of user experiments. They show significant improvements in depth perception without sacrificing the visual quality when our techniques are applied.

The demand for multimedia streaming over mobile networks has been steadily increasing over the past several years. For instance, it has become common for mobile users to stream full TV episodes, sports events, and movies while on the go. Unfortunately, this growth in demand has strained the wireless networks despite the significant increase of their capacities with recent generations. Hence, efficient utilization of the expensive and limited wireless spectrum remains an important problem, especially in the context of multimedia streaming services that consume a large portion of the bandwidth capacity. In this article, we introduce the idea of dynamically configuring cells in wireless cellular networks to form single-frequency networks based on the multimedia traffic demands from users in each cell. We formulate the resource allocation problem in such complex networks with the goal of maximizing the number of served multimedia streams, and we prove that this problem is NP-Complete. Then we present an optimal solution to maximize the number of served multimedia streams within a cellular network. This optimal solution, however, may suffer from an exponential time complexity in the worst case, which is not practical for real-time streaming over large-scale networks. Therefore, we propose a heuristic algorithm with polynomial running time to provide faster and more practical solution for real-time deployments. Through detailed packet-level simulations, we assess the performance of the proposed algorithms with respect to the average service ratio, energy saving, video quality, frame loss rate, initial buffering time, rate of re-buffering events, and bandwidth overhead. We show that the proposed algorithms achieve substantial improvements in all of these performance metrics compared to the state-of-the-art approaches. For example, for the service ratio metric, our algorithms can serve up to 11 times more users compared to the unicast approach, and they achieve up to 54% improvement over the closest multicast approaches in the literature.

Current three-dimensional displays cannot fully reproduce all depth cues used by a human observer in the real world. Instead, they create only an illusion of looking at a three-dimensional scene. This leads to a number of challenges during the content creation process. To assure correct depth reproduction and visual comfort, either the acquisition setup has to be carefully controlled or additional postprocessing techniques have to be applied. Furthermore, these manipulations need to account for a particular setup that is used to present the content, for example, viewing distance or screen size. This creates additional challenges in the context of personal use when stereoscopic content is shown on TV sets, desktop monitors, or mobile devices. We address this problem by presenting a new system for streaming stereoscopic content. Its key feature is a computationally efficient depth adjustment technique which can automatically optimize viewing experience for videos of field sports such as soccer, football, and tennis. Additionally, the method enables depth personalization to allow users to adjust the amount of depth according to their preferences. Our stereoscopic video streaming system was implemented, deployed, and tested with real users.

Video magnification reveals subtle variations that would be otherwise invisible to the naked eye. Current techniques require all motion in the video to be very small, which is unfortunately not always the case. Tiny yet meaningful motions are often combined with larger motions, such as the small vibrations of a gate as it rotates, or the microsaccades in a moving eye. We present a layer-based video magnification approach that can amplify small motions within large ones. An examined region/layer is temporally aligned and subtle variations are magnified. Matting is used to magnify only region of interest while maintaining integrity of nearby sites. Results show handling larger motions, larger amplification factors and significant reduction in artifacts over state of the art.

Current data mining techniques used to create failure predictors for online services require massive amounts of data to build, train, and test the predictors. These operations are tedious, time consuming, and are not done in real-time. Also, the accuracy of the resulting predictor is highly compromised by changes that affect the environment and working conditions of the predictor. We propose a new approach to creating a dynamic failure predictor for online services in real-time and keeping its accuracy high during the services run-time changes. We use synthetic transactions during the run-time lifecycle to generate current data about the service. This data is used in its ephemeral state to build, train, test, and maintain an up-to-date failure predictor. We implemented the proposed approach in a large-scale online ad service that processes billions of requests each month in six data centers distributed in three continents. We show that the proposed predictor is able to maintain failure prediction accuracy as high as 86% during online service changes, whereas the accuracy of the state-of-the-art predictors may drop to less than 10%.

A wide spread adoption of 3D videos and technologies is hindered by the lack of high-quality 3D content. One promising solution to address this problem is to use automated 2D-to-3D conversion. However, current conversion methods, while general, produce low-quality results with artifacts that are not acceptable to many viewers. We address this problem by showing how to construct a high-quality, domain-specific conversion method for soccer videos. We propose a novel, data-driven method that generates stereoscopic frames by transferring depth information from similar frames in a database of 3D stereoscopic videos. Creating a database of 3D stereoscopic videos with accurate depth is, however, very difficult. One of the key findings in this paper is showing that computer generated content in current sports computer games can be used to generate high-quality 3D video reference database for 2D-to-3D conversion methods. Once we retrieve similar 3D video frames, our technique transfers depth gradients to the target frame while respecting object boundaries. It then computes depth maps from the gradients, and generates the output stereoscopic video. We implement our method and validate it by conducting user-studies that evaluate depth perception and visual comfort of the converted 3D videos. We show that our method produces high-quality 3D videos that are almost indistinguishable from videos shot by stereo cameras. In addition, our method significantly outperforms the current state-of-the-art method. For example, up to 20% improvement in the perceived depth is achieved by our method, which translates to improving the mean opinion score from Good to Excellent.

We present a complete system, called Challenged Content Delivery Network (CCDN), to efficiently deliver multimedia content to mobile users who live in developing countries, rural areas, or over-populated cities with no or weak network infrastructure. These mobile users do not have always-on Internet access. We demo our CCDN, implemented on a Linux server, Raspberry Pi proxies, and Android phones from three aspects: multimedia, networking, and machine learning tools. We propose multiple optimization algorithm modules that compute personalized distribution plans, and maximize the overall user experience. CCDN allows people living in area with challenged networks access to multimedia content, like news reports, using mobile devices, such as smartphones. This in turn will help in eliminating the digital divide, which refers to information inequality to persons with different Internet accessing abilities.

Online multimedia communication services, such as Skype and Google Hangout, are used by millions of users every day. Although these services provide acceptable quality on average, users occasionally suffer from reduced audio quality, dropped video streams, and even failed sessions. To mitigate some of these problems, service providers closely monitor the performance of different parts of the system. However, most current techniques for monitoring and managing the quality of service (QoS) of online multimedia communication services are reactive and lack the ability to adapt to dynamic changes in real time. We propose a novel proactive approach for continuously monitoring the health of large-scale multimedia communication services, and dynamically managing and improving the quality of the multimedia sessions. The proposed approach, called Proactive QoS Manager, has novel light-weight methods for estimating the capacity of different components of the system and for using this capacity estimation in allocating resources to multimedia sessions in real time. We implement the proposed approach in one of the largest online multimedia communication services in the world and evaluate its performance on more than 100 million audio, video, and conferencing sessions. Our empirical results show that substantial quality improvements can be achieved using our proactive approach, without changing the production code of the service or imposing significant overheads. For example, in our experiments, the Proactive QoS Manager reduced the number of failed sessions by up to 25% and improved the quality (in terms of the Mean Opinion Score (MOS)) of the succeeded sessions by up to 12%. These improvements are achieved for the well-engineered and highly-provisioned online service examined in this paper; we expect higher gains for other similar services.

Although the capacity of cellular networks has increased with recent generations, the growth in demand of wireless bandwidth has outpaced this increase in capacity. Not only more users are relying on wireless networks, but also the demand from each user has substantially increased. For example, it has become common for mobile users to stream full TV episodes, sports events, and movies while on the go. Further, as the capabilities of mobile devices improve, the demand for higher quality and even 3D videos will escalate, which will strain cellular networks. Therefore, efficient utilization of the expensive and limited wireless spectrum remains an important problem, especially in the context of multimedia streaming services that consume a large portion of the wireless capacity. In this paper, we introduce the idea of dynamically configuring cells in wireless networks to form single frequency networks based on the multimedia traffic demands from users in each cell. We formulate the resource allocation problem in such complex networks with the goal of maximizing the number of served multimedia streams. We prove that this problem is NP-Complete, and we propose a heuristic algorithm to solve it. Through detailed packet-level simulations, we show that the proposed algorithm can achieve substantial improvements in the number of streams served as well the energy saving of mobile devices. For example, our algorithm can serve up to 40 times more users compared to the common unicast streaming approach, and it achieves at least 80% and up to 400% improvement compared to multicast approaches that do not use single frequency networks.

Web sites, social networks, sensors, and scientific experiments currently generate massive amounts of data. Owners of this data strive to obtain insights from it, often by applying machine learning algorithms. Many machine learning algorithms, however, do not scale well to cope with the ever increasing volumes of data. To address this problem, we identify several optimizations that are crucial for scaling various machine learning algorithms in distributed settings. We apply these optimizations to the popular Principal Component Analysis (PCA) algorithm. PCA is an important tool in many areas including image processing, data visualization, information retrieval, and dimensionality reduction. We refer to the proposed optimized PCA algorithm as scalable PCA, or sPCA. sPCA achieves scalability via employing efficient large matrix operations, effectively leveraging matrix sparsity, and minimizing intermediate data. We implement sPCA on the widely-used MapReduce platform and on the memory-based Spark platform. We compare sPCA against the closest PCA implementations, which are the ones in Mahout/ MapReduce and MLlib/Spark. Our experiments show that sPCA outperforms both Mahout-PCA and MLlib-PCA by wide margins in terms of accuracy, running time, and volume of intermediate data generated during the computation.

We propose a new design for large-scale multimedia content protection systems. Our design leverages cloud infrastructures to provide cost efficiency, rapid deployment, scalability, and elasticity to accommodate varying workloads. The proposed system can be used to protect different multimedia content types, including 2-D videos, 3-D videos, images, audio clips, songs, and music clips. The system can be deployed on private and/or public clouds. Our system has two novel components: (i) method to create signatures of 3-D videos, and (ii) distributed matching engine for multimedia objects. The signature method creates robust and representative signatures of 3-D videos that capture the depth signals in these videos and it is computationally efficient to compute and compare as well as it requires small storage. The distributed matching engine achieves high scalability and it is designed to support different multimedia objects. We implemented the proposed system and deployed it on two clouds: Amazon cloud and our private cloud. Our experiments with more than 11,000 3-D videos and 1 million images show the high accuracy and scalability of the proposed system. In addition, we compared our system to the protection system used by YouTube and our results show that the YouTube protection system fails to detect most copies of 3-D videos, while our system detects more than 98% of them. This comparison shows the need for the proposed 3-D signature method, since the state-of-the-art commercial system was not able to handle 3-D videos.

New cloud services are being developed to support a wide variety of real-life applications. In this paper, we introduce a new cloud service: industrial automation, which includes different functionalities from feedback control and telemetry to plant optimization and enterprise management. We focus our study on the feedback control layer as the most time-critical and demanding functionality. Today's large-scale industrial automation projects are expensive and time-consuming. Hence, we propose a new cloud-based automation architecture, and we analyze cost and time savings under the proposed architecture. We show that significant cost and time savings can be achieved, mainly due to the virtualization of controllers and the reduction of hardware cost and associated labor. However, the major difficulties in providing cloud-based industrial automation systems are timeliness and reliability. Offering automation functionalities from the cloud over the Internet puts the controlled processes at risk due to varying communication delays and potential failure of virtual machines and/or links. Thus, we design an adaptive delay compensator and a distributed fault tolerance algorithm to mitigate delays and failures, respectively. We theoretically analyze the performance of the proposed architecture when compared to the traditional systems and prove zero or negligible change in performance. To experimentally evaluate our approach, we implement our controllers on commercial clouds and use them to control: (i) a physical model of a solar power plant, where we show that the fault-tolerance algorithm effectively makes the system unaware of faults, and (ii) industry-standard emulation with large injected delays and disturbances, where we show that the proposed cloud-based controllers perform indistinguishably from the best-known counterparts: local controllers.

Producing high-quality stereoscopic 3D content requires significantly more effort than preparing regular video footage. In order to assure good depth perception and visual comfort, 3D videos need to be carefully adjusted to specific viewing conditions before they are shown to viewers. While most stereoscopic 3D content is designed for viewing in movie theaters, where viewing conditions do not vary significantly, adapting the same content for viewing on home TV-sets, desktop displays, laptops, and mobile devices requires additional adjustments. To address this challenge, we propose a new system for 3D video streaming that provides automatic depth adjustments as one of its key features. Our system takes into account both the content and the display type in order to customize 3D videos and maximize their perceived quality. We propose a novel method for depth adjustment that is well-suited for videos of field sports such as soccer, football, and tennis. Our method is computationally efficient and it does not introduce any visual artifacts. We have implemented our 3D streaming system and conducted two user studies, which show: (i) adapting stereoscopic 3D videos for different displays is beneficial, and (ii) our proposed system can achieve up to 35% improvement in the perceived quality of the stereoscopic 3D content.

This paper presents the design and evaluation of DIMO, a distributed system for matching high-dimensional multimedia objects. DIMO provides multimedia applications with the basic function of computing the K nearest neighbors on large-scale datasets. It also allows multimedia applications to define application-specific functions to further process the computed nearest neighbors. DIMO presents a novel method for partitioning, searching, and storing high-dimensional datasets on distributed infrastructures that support the MapReduce programming model. We have implemented DIMO and extensively evaluated it on Amazon clusters with number of machines ranging from 8 to 128. We have experimented with large datasets of sizes up to 160 million data points extracted from images, and each point has 128 dimensions. Our experimental results show that DIMO: (i) results in high precision when compared against the ground-truth nearest neighbors, (ii) can elastically utilize varying amounts of computing resources, (iii) does not impose high network overheads, (iv) does not require large main memory even for processing large datasets, and (v) balances the load across the used computing machines. In addition, DIMO outperforms the closest system in the literature by a large margin (up to 20%) in terms of the achieved average precision of the computed nearest neighbors. Furthermore, DIMO requires at least three orders of magnitudes less storage than the other system, and it is more computationally efficient.

Three dimensional (3D) content is becoming attractive in entertainment events such as soccer games and movies. Also, 3D displays are widespread at homes, offices, and theaters. Yet, 3D content may lack good 3D experience due to varying display technologies and sizes. In addition, 3D content providers may not be able to deliver their content to all potential subscribers, which leads to viewership reduction or dissatisfaction. In this work, we propose the design of a system for enhanced 3D content streaming. In order to support all 3D display technologies and sizes in the system, we design different 3D versions of the original videos that are optimized for various displays. Moreover, we propose a storage optimization algorithm that optimizes storage usage in our system depending on versions popularity as well as storage and processing requirements. The algorithm satisfies the limited processing resources, maximum delay, and request rate requirements. We implemented and deployed the proposed system on the cloud for live testing. We simulated the proposed algorithm to study its effect on the storage requirements in 3D streaming systems. The results of the simulations show that the algorithm can achieve storage gain up to 360x compared to storing all versions.

Mobile on-demand videos are getting tremendously popular and incurring staggering overhead on cellular net-works. Fortunately, next generation cellular networks support video streaming over either unicast or multicast, but how to capitalize both unicast and multicast for optimal on-demand video streaming remains an open question. In this paper, we consider a resource allocation problem that concurrently utilizes unicast/multicast in order to support many more mobile streaming users and minimize the energy consumption of the battery-powered mobile devices. We formulate this problem as a Binary Integer Programming (BIP) problem. We present an optimal algorithm, SCOPT, for this problem. We also develop an efficient heuristic algorithm, SCG, for lower overhead. We conduct detailed packet-level simulations to evaluate the algorithms in LTE networks using OPNET. Our simulation study shows that the proposed algorithms: (i) result in lower energy consumption than multicast-only approach, (ii) scale to many more mobile users than unicast-only approach, and (iii) are more energy efficient with more network bandwidth or fewer videos. In addition, we discuss how our solution can be extended to support Single Frequency Networks in which multiple adjacent base stations operate on the same frequency.

We present an interactive free-viewpoint video (FVV) streaming system that is based on the dynamic adaptive streaming over HTTP (DASH) standard. The system uses standard HTTP Web servers to achieve scalability with a large number of users and performs view synthesis and rate adaptation at the client-side to achieve high response time. We propose a rate adaptation logic based on sampled rate-distortion (R-D) values, which relate the distortion of synthesized view to the bit rates of the texture and depth components of the reference views, to maximize the quality of rendered virtual views. Initial results indicate that the proposed R-D-based rate adaptation strategy outperforms equal bit rate allocation among the reference streams components.

Sudden temporal depth changes, such as cuts that are introduced by video edits, can significantly degrade the quality of stereoscopic content. Since usually not encountered in the real world, they are very challenging for the audience. This is because the eye vergence has to constantly adapt to new disparities in spite of conflicting accommodation requirements. Such rapid disparity changes may lead to confusion, reduced understanding of the scene, and overall attractiveness of the content. In most cases the problem cannot be solved by simply matching the depth around the transition, as this would require flattening the scene completely. To better understand this limitation of the human visual system, we conducted a series of eye-tracking experiments. The data obtained allowed us to derive and evaluate a model describing adaptation of vergence to disparity changes on a stereoscopic display. Besides computing user-specific models, we also estimated parameters of an average observer model. This enables a range of strategies for minimizing the adaptation time in the audience.

There has been an increasing demand for interactive video transmission over the Internet for applications such as video conferencing, video calls, and telepresence applications. These applications are increasingly moving towards providing High Definition (HD) video quality to users. A key challenge in these applications is to preserve the quality of video when it is transported over best-effort networks that do not guarantee lossless transport of video packets. In such conditions, it is important to protect the transmitted video by using intelligent and adaptive protection schemes. Applications such as HD video conferencing require live interaction among participants, which limits the overall delay the system can tolerate. Therefore, the protection scheme should add little or no extra delay to video transport. We propose a novel Adaptive Loss Protection (ALP) scheme for interactive HD video applications such as video conferencing and video chats. This scheme adds negligible delay to the transmission process and is shown to achieve better quality than other schemes in lossy networks. The proposed ALP scheme adaptively applies four different protection modes to cope with the dynamic network conditions, which results in high video quality in all network conditions. Our ALP scheme consists of four protection modes ; each of these modes utilizes a protection method . Two of the modes rely on the state-of-the-art protection methods, and we propose a new Integrated Loss Protection (ILP) method for the other two modes. In the ILP method we integrate three factors for distributing the protection among packets. These three factors are error propagation, region of interest and header information. In order to decide when to switch between the protection modes, a new metric is proposed based on the effectiveness of each mode in performing protection, rather than just considering network statistics such as packet loss rate. Results show that by using this metric not only the overall quality will be improved but also the variance of quality will decrease. One of the main advantages of the proposed ALP scheme is that it does not increase the bit rate overhead in poor network conditions. Our results show a significant gain in video quality, up to 3dB PSNR improvement is achieved using our scheme, compared to protecting all packets equally with the same amount of overhead.

Cloud computing requires further research and development to accommodate more application areas [5]. We introduce a new application area: industrial automation. A current industrial automation (IA) system is a multi-tiered architecture entailing different layers from feedback control to enterprise management. If adopted in large-scale IA systems, cloud computing can offer over 40% cost saving and 25--85% time saving [4, 1]. However, IA requires tighter timeliness, reliability, and security than most other cloud applications. We propose a cloud-based IA architecture and focus on the timeliness and reliability requirements. Addressing such requirements for the lowest layer (feedback control) is the most challenging. We addressed the timeliness problem in [2]. To address reliability and further address timeliness, we propose a distributed fault tolerance algorithm for cloud-based controllers. We theoretically and practically prove that the proposed fault-tolerant, cloud-based controllers offer the same performance of the local ones.

We propose a distributed method to compute similarity (also known as kernel and Gram) matrices used in various kernel-based machine learning algorithms. Current methods for computing similarity matrices have quadratic time and space complexities, which make them not scalable to large-scale data sets. To reduce these quadratic complexities, the proposed method first partitions the data into smaller subsets using various families of locality sensitive hashing, including random project and spectral hashing. Then, the method computes the similarity values among points in the smaller subsets to result in approximated similarity matrices. We analytically show that the time and space complexities of the proposed method are sub quadratic. We implemented the proposed method using the Message Passing Interface (MPI) framework and ran it on a cluster. Our results with real large-scale data sets show that the proposed method does not significantly impact the accuracy of the computed similarity matrices and it achieves substantial savings in running time and memory requirements.

We propose a novel algorithm to efficiently transmit multiple Variable-Bit-Rate (VBR) video streams from a base station to mobile receivers in wide-area wireless networks. The algorithm multicasts video streams in bursts to save the energy of mobile devices. In addition, the algorithm adaptively controls the buffer levels of mobile devices receiving different video streams according to the bit rate of the video stream being received by each device. Compared to previous algorithms, the new algorithm enables dynamic control of the wireless channel and allows the base station to transmit more video data on time to mobile receivers. This is done by providing finer control over the bandwidth allocation of the wireless channel. The problem of optimizing energy saving has been shown to be NP-Complete. We prove that our algorithm finds a feasible schedule if one exists and always produces a correct schedule even when dropped frames are unavoidable. We analytically bound the gap between the energy saving resulting from our algorithm and the optimal energy saving and show that our results are close to optimal. We analyze the tradeoff between the fine control over bandwidth allocation and energy saving and demonstrate that in practical situations, flexible and finer control of bandwidth allocation will result in significantly lower frame loss rates while achieving higher energy saving. We have implemented the proposed algorithm as well as two other recent algorithms in a mobile video streaming testbed. Our extensive analysis and results demonstrate that the proposed algorithm outperforms the other two algorithms; it results in higher energy saving for mobile devices and fewer dropped video frames.

To improve rendered video quality and serve more receivers, peer-to-peer (P2P) video-on-demand streaming systems usually deploy seed servers. These servers complement the limited upload capacity offered by peers. In this paper, we are interested in optimally managing the capacity of seed servers, especially when scalable video streams are served to peers. Scalable video streams are encoded in multiple layers to support heterogeneous receivers. We show that the problem of optimally allocating the seeding capacity to serve scalable streams to peers is NP-complete. We then propose an approximation algorithm to solve it. Using the proposed allocation algorithm, we develop an analytical model to study the performance of P2P video-on-demand streaming systems and to manage their resources. The analysis also provides an upper bound on the maximum number of peers that can be admitted to the system in flash crowd scenarios. We validate our analysis by comparing its results to those obtained from simulations. Our analytical model can be used by administrators of P2P streaming systems to estimate the performance and video quality rendered to users under various network, peer, and video characteristics.

This article presents a novel content-based copy detection system for 3D videos. The system creates compact and robust depth and visual signatures from the 3D videos. Then, signature of a query video is compared against an indexed database of reference videos' signatures. The system returns a score, using both spatial and temporal characteristics of videos, indicating whether the query video matches any video in the reference video database, and in case of matching, which portion of the reference video matches the query video. Analysis shows that the system is efficient, both computationally and storage-wise. The system can be used, for example, by video content owners, video hosting sites, and third-party companies to find illegally copied 3D videos. We implemented Spider, a complete realization of the proposed system, and conducted rigorous experiments on it. Our experimental results show that the proposed system can achieve high accuracy in terms of precision and recall even if the 3D videos are subjected to several transformations at the same time. For example, the proposed system yields 100% precision and recall when copied videos are parts of original videos, and more than 90% precision and recall when copied videos are subjected to different individual transformations.

Data-intensive applications are becoming important in many science and engineering fields, because of the high rates in which data are being generated and the numerous opportunities offered by the sheer amount of these data. Large-scale datasets, however, are challenging to process using many of the current machine learning algorithms due to their high time and space complexities. In this paper, we propose a novel approximation algorithm that enables kernel-based machine learning algorithms to efficiently process very large-scale datasets. While important in many applications, current kernel-based algorithms suffer from a scalability problem as they require computing a kernel matrix which takes O(N2) in time and space to compute and store. The proposed algorithm yields substantial reduction in computation and memory overhead required to compute the kernel matrix, and it does not significantly impact the accuracy of the results. In addition, the level of approximation can be controlled to tradeoff some accuracy of the results with the required computing resources. The algorithm is designed such that it is independent of the subsequently used kernel-based machine learning algorithm, and thus can be used with many of them. To illustrate the effect of the approximation algorithm, we developed a variant of the spectral clustering algorithm on top of it. Furthermore, we present the design of a MapReduce-based implementation of the proposed algorithm. We have implemented this design and run it on our own Hadoop cluster as well as on the Amazon Elastic MapReduce service. Experimental results on synthetic and real datasets demonstrate that significant time and memory savings can be achieved using our algorithm.

Video copy detection algorithms are used to find copies of original video content even if the content has been altered. Given the prevalence of video recording and copying devices as well as the availability of many Internet sites for hosting videos, detecting video copies has become an important problem especially for companies interested in managing and controlling copyrights of their content. We propose a new content-based video copy detection algorithm. The proposed algorithm creates signatures that capture the spatial and temporal features of videos. These spatio-temporal signatures enable the algorithm to provide both high precision and recall. In addition, these signatures require small storage and are easy to compute and compare. Our extensive experimental analysis with a large video dataset shows that the proposed algorithm achieves high precision and recall values while remaining robust to many video transformations that commonly occur in practice. The algorithm is simple to implement and is more computationally efficient than previous algorithms in literature.

We present a novel system to detect copies of 3D videos. The system creates signatures from the depth signals of 3D videos. It also extracts visual features from video frames and creates compact spatial signatures for videos. The system then uses the depth and spatial signatures to compare a given query video versus a reference video database. The system returns a score indicating whether the query video matches any video in the reference video database, and in case of matching, which portion of the reference video matches the query video. The system is computationally efficient and can be implemented in distributed manner. The system can be used, for example, by video content owners, video hosting sites, and third-party companies to find illegally copied 3D videos. To the best of our knowledge, this is the first complete 3D video copy detection system in the literature. We implemented the proposed system and conducted a rigorous evaluation study using 3D videos with diverse properties. Our experimental results show that the proposed system can achieve high accuracy in terms of precision and recall even if the 3D videos are subjected to several transformations at the same time. For example, the proposed system yields 100% precision and recall when copied videos are parts of original videos, and more than 90% precision and recall when copied videos are subjected to different individual transformations.

The 14 papers in this special issue are extended versions of papers presented at ICME 2011, held in Barcelona, Spain, on 11-15 July 2011.

Multicasting multiple video streams over wireless broadband access networks enables the delivery of multimedia content to large-scale user communities in a cost-efficient manner. Three dimensional (3D) videos are the next natural step in the evolution of digital media technologies. In order to provide 3D perception, 3D video streams contain one or more views that greatly increase their bandwidth requirements. Due to the limited channel capacity and variable bit rate of the videos, multicasting multiple 3D videos over wireless broadband networks is a challenging problem. In this article, we consider a 4G wireless access network in which a number of 3D videos represented in two-view plus depth format and encoded using scalable video coders are multicast. We formulate the optimal 3D video multicasting problem to maximize the quality of rendered virtual views on the receivers' displays. We show that this problem is NP-complete and present a polynomial time approximation algorithm to solve it. We then extend the proposed algorithm to efficiently schedule the transmission of the chosen substreams from each video in order to maximize the power saving on the mobile receivers. Our simulation-based experimental results show that our algorithm provides solutions that are within 0.3 dB of the optimal solutions while satisfying real-time requirements of multicast systems. In addition, our algorithm results in an average power consumption reduction of 86%.

This article presents the design of a complete, open-source, testbed for broadcast networks that offer mobile TV services. Although basic architectures and protocols have been developed for such networks, detailed performance tuning and analysis are still needed, especially when these networks scale to serve many diverse TV channels to numerous subscribers. The detailed performance analysis could also motivate designing new protocols and algorithms for enhancing future mobile TV networks. Currently, many researchers evaluate the performance of mobile TV networks using simulation and/or theoretical modeling methods. These methods, while useful for early assessment, typically abstract away many necessary details of actual, fairly complex, networks. Therefore, an open-source platform for evaluating new ideas in a real mobile TV network is needed. This platform is currently not possible with commercial products, because they are sold as black boxes without the source code. In this article, we summarize our experiences in designing and implementing a testbed for mobile TV networks. We integrate off-the-shelf hardware components with carefully designed software modules to realize a scalable testbed that covers almost all aspects of real networks. We use our testbed to empirically analyze various performance aspects of mobile TV networks and validate/refute several claims made in the literature as well as discover/quantify multiple important performance tradeoffs.

10.1145/2348816.2348820

Advertising in online videos is a large and growing market. In this paper, we propose a new approach to match ads with online videos based on the shopping interests of the target audience of videos. The proposed approach increases the relevance of ads to the actual viewers (humans) of videos, which increases the number of users who purchase goods and services offered by the advertisers. This in turn will increase the revenues for advertisers as well as for the video sites as video sites usually charge advertisers based on the number of user clicks on their ads. The proposed approach is different from current approaches used in practice or proposed in the literatures, which most of them try to maximize the relevance of ads to the tags or contents of videos (objects). We conduct a subjective study to evaluate the performance of the proposed approach on many videos retrieved from YouTube. Our results show that the proposed approach yields more relevant ads to viewers than the YouTube's approach. We also compare against other approaches proposed in the literature and we show that the new approach outperforms them.

Peer-to-peer (P2P) systems generate a major fraction of the current Internet traffic, and they significantly increase the load on ISP networks and the cost of running and connecting customer networks (e.g., universities and companies) to the Internet. To mitigate these negative impacts, many previous works in the literature have proposed caching of P2P traffic, but very few (if any) have considered designing a caching system to actually do it. This paper demonstrates that caching P2P traffic is more complex than caching other Internet traffic, and it needs several new algorithms and storage systems. Then, the paper presents the design and evaluation of a complete, running, proxy cache for P2P traffic, called pCache. pCache transparently intercepts and serves traffic from different P2P systems. A new storage system is proposed and implemented in pCache. This storage system is optimized for storing P2P traffic, and it is shown to outperform other storage systems. In addition, a new algorithm to infer the information required to store and serve P2P traffic by the cache is proposed. Furthermore, extensive experiments to evaluate all aspects of pCache using actual implementation and real P2P traffic are presented.

We study the scalable video broadcasting problem in mobile TV broadcast networks, where each TV channel is encoded into a scalable video stream with multiple layers, and several TV channels are concurrently broadcast over a shared air medium to many mobile devices with heterogeneous resources. Our goal is to encapsulate and broadcast video streams encoded in scalable manner to enable heterogeneous mobile devices to render the most appropriate video substreams while achieving high energy saving and low channel switching delay. The appropriate streams depend on the device capability and the target energy consumption level. We propose two new broadcast schemes, which are flexible in the sense that they allow diverse bit rates among layers of the same stream. Such flexibility enables videos to be optimally encoded in terms of coding efficiency, and allows the coded video streams to be better matched with the capability of mobile devices. We analyze the performance of the proposed broadcast schemes. In addition, we have implemented the proposed schemes in a real mobile TV testbed to show their practicality and efficiency. Our extensive experiments confirm that the proposed schemes enable energy saving differentiation: between 75 and 95 percent were observed. Moreover, one of the schemes achieves low channel switching delays: 200 msec is possible with typical system parameters.

Long network latency negatively impacts the performance of online games, and thus mechanisms are needed to mitigate its effects in order to provide a high-quality gaming experience. In this paper, we propose an indirect relay system (IRS) to forward game-state updates over detour paths in order to reduce the round-trip time (RTT) among players. We first collect extensive traces for RTTs among actual players in online games. We then analyze these traces to quantify the potential performance gain of the detour routing. Our analysis reveals that substantial reduction in the RTTs is possible. For example, our results indicate that more than 40% of players can observe at least 100 ms of RTT reduction by routing game-state updates through 1-hop detour paths. Because of the reduction in RTTs, players can join more gaming sessions that were not available to them due to long RTTs of the direct paths. Most importantly, we design and implement a complete IRS system for online games. To the best of our knowledge, this is the first system that directly reduces RTTs among players in online games, while previous works in the literature mitigate the long RTT issue by either hiding it from players or preventing players with high RTTs from being in the same game session. We implement the proposed IRS system and deploy it on 500 PlanetLab nodes. The results from real experiments show that the IRS system improves the online gaming quality from several aspects, while incurring negligible network and processing overheads. In particular, we observe that, with the proposed IRS system, more than 80% of game sessions achieve 100 ms or higher RTT reduction.

The Multicast/Broadcast Service (MBS) feature of mobile WiMAX network is a promising technology for providing wireless multimedia, because it allows the delivery of multimedia content to large-scale user communities in a cost-efficient manner. In this paper, we consider WiMAX networks that transmit multiple video streams encoded in scalable manner to mobile receivers using the MBS feature. We focus on two research problems in such networks: 1) maximizing the video quality and 2) minimizing energy consumption for mobile receivers. We formulate and solve the substream selection problem to maximize the video quality, which arises when multiple scalable video streams are broadcast to mobile receivers with limited resources. We show that this problem is NP-Complete, and design a polynomial time approximation algorithm to solve it. We prove that the solutions computed by our algorithm are always within a small constant factor from the optimal solutions. In addition, we extend our algorithm to reduce the energy consumption of mobile receivers. This is done by transmitting the selected substreams in bursts, which allows mobile receivers to turn off their wireless interfaces to save energy. We show how our algorithm constructs burst transmission schedules that reduce energy consumption without sacrificing the video quality. Using extensive simulation and mathematical analysis, we show that the proposed algorithm: 1) is efficient in terms of execution time, 2) achieves high radio resource utilization, 3) maximizes the received video quality, and 4) minimizes the energy consumption for mobile receivers.

In mesh-based peer-to-peer (P2P) streaming systems, each video sequence is divided into segments, which are then streamed from multiple senders to a receiver. The receiver needs to coordinate the senders by specifying a transmission schedule for each of them. We consider the problem of scheduling segment transmission in P2P streaming systems, where different segments have different weights in terms of quality improvements to the received video. Our goal is to compute the transmission schedule for each receiver in order to maximize the perceived video quality. We first show that this scheduling problem is NP-Complete. We then present an integer linear programming (ILP) formulation for it, so that it can be solved with any ILP solver. This optimal solution, however, is computationally expensive and is not suitable for real-time P2P streaming systems. Thus, we propose two approximation algorithms to solve this segment scheduling problem. These algorithms provide theoretical guarantees on the worst-case performance. The first algorithm considers the weight of each video segment. The second algorithm is simpler and it assumes that segments carry equal weights. We analyze the performance and complexity of the two algorithms. In addition, we rigorously evaluate the proposed algorithms with simulations and experiments using a prototype implementation. Our simulation and experimental results show that the proposed algorithms outperform other algorithms that are commonly used in deployed P2P streaming systems and that have been recently proposed in the literature.

We present a general framework for optimizing the quality of video streaming in wireless networks that are composed of multiple wireless stations. The framework is general because: (i) it can be applied to different wireless networks, such as IEEE 802.11e WLAN and IEEE 802.16 WiMAX, (ii) it can employ different objective functions for the optimization, and (iii) it can adopt various models for the wireless channel, the link layer, and the distortion of the video streams in the application layer. The optimization framework controls parameters in different layers to optimally allocate the wireless network resources among all stations. More specifically, we address this video optimization problem in two steps. First, we formulate an abstract optimization problem for video streaming in wireless networks in general. This formulation exposes the important interaction between parameters belonging to different layers in the network stack. Then, we instantiate and solve the general problem for the recent IEEE 802.11e WLANs, which support prioritized traffic classes. We show how the calculated optimal solutions can efficiently be implemented in the distributed mode of the IEEE 802.11e standard. We evaluate our proposed solution using extensive simulations in the OPNET simulator, which captures most features of realistic wireless networks. In addition, to show the practicality of our solution, we have implemented it in the driver of an off-the-shelf wireless adapter that complies with the IEEE 802.11e standard. Our experimental and simulation results show that significant quality improvement in video streams can be achieved using our solution, without incurring any significant communication or computational overhead. We also explain how the general video optimization problem can be applied to other wireless networks, in particular, to the IEEE 802.16 WiMAX networks, which are becoming very popular.

Many mobile TV standards dictate using energy saving schemes to increase the viewing time on mobile devices, since mobile receivers are battery powered. The most common scheme for saving energy is to make the base station broadcast the video data of a TV channel in bursts with a bit-rate much higher than the encoding rate of the video stream, which enables mobile devices to turn off their radio frequency circuits when not receiving bursts. Broadcasting TV channels in bursts, however, increases channel switching delay. The switching delay is important, because long and variable switching delays are annoying to users and may turn them away from the mobile TV service. In this article, we first analyze the burst broadcasting scheme currently used in many deployed mobile TV networks, and we show that it is not efficient in terms of controlling the channel switching delay. We then propose new schemes to guarantee that a given maximum switching delay is not exceeded and that the energy consumption of mobile devices is minimized. We prove the correctness of the proposed schemes and analytically analyze the achieved energy saving. We also use scalable video coding to generalize the proposed schemes in order to support mobile devices with heterogeneous resources. We implement the proposed schemes in a mobile TV testbed to show their practicality and to validate our theoretical analysis. The experimental results show that the proposed schemes: (i) significantly increase the energy saving achieved on mobile devices: up to 95% saving is observed, and (ii) support both homogeneous and heterogeneous mobile devices.

We address the problem of broadcasting multiple video streams over a broadcast network to many mobile devices, so that: (i) streaming quality of mobile devices is maximized, (ii) energy consumption of mobile devices is minimized, and (iii) goodput in the network is maximized. We consider two types of broadcast networks: closed-loop networks, in which all video streams are jointly encoded to ensure their total bit rate does not exceed the broadcast network bandwidth, and open-loop networks, in which videos are encoded using standalone coders, and thus must be carefully broadcast to avoid playout glitches. We first show that the problem of optimally broadcasting multiple videos is NP-complete. We then propose an approximation algorithm to construct burst schedules for multiple VBR (Variable-Bit-Rate) streams. The proposed algorithm frees network operators from the manual and error-prone bandwidth reservation process which is currently used in practice. We prove that the proposed algorithm achieves optimal goodput and near-optimal energy saving. We show that it produces glitch-free schedules in closed-loop networks, and it minimizes number of glitches in open-loop networks. We implement the proposed algorithm in a trace-driven simulator, and conduct extensive simulations for both open- and closed-loop networks. The simulation results show that the proposed algorithm outperforms the existing algorithms in many aspects, including number of late frames, number of concurrently broadcast video streams, and energy saving of mobile devices. To show the practicality and efficiency of the proposed algorithm, we also implement it in a real mobile TV testbed as a proof of concept. The results from the testbed confirm that the proposed algorithm: (i) does not result in playout glitches, (ii) achieves high energy saving, and (iii) runs in real time.

Broadcasting multiple scalable video streams over wireless broadband access networks in real time is a challenging problem, because of the limited channel capacity and variable bit rate of the videos. The difficulty is further increased in the presence of receiver buffer size limitations which may introduce buffer overflow possibilities. The Multicast/Broadcast Service feature of mobile WiMAX network is a promising technology for providing wireless video broadcast services. In this article, we describe a substream selection problem which arises when multiple scalable video streams are broadcast based on the Multicast/Broadcast Service feature to a number of buffer size constrained receivers. We first show that the problem is NP-Complete and design a polynomial time approximation algorithm based on convex optimization and dynamic programming techniques. We mathematically prove that the solution obtained through our algorithm is always within a constant factor of the optimal solution. Through simulation we show that under real time requirements our algorithm provides solutions which are within 1 dB of the optimal solutions.

Increasingly more users use mobile devices to watch videos streamed over wireless networks, and they demand more content at better quality. For example, market forecasts reveal that mobile video streaming, such as mobile TV, will catch up with gaming and music, and become the most popular application on mobile devices. In this tutorial, we will present different approaches to deliver multimedia content over various wireless networks to a large number of mobile users. We will study and analyze the main research problems in modern wireless networks that need to be addressed in order to enable efficient mobile video services. The tutorial will cover common research problems in wireless networks such as HSDPA, MBMS, WiMAX, LTE, DVB-H, MediaFLO, and ATSC M/H. After giving the preliminaries of the considered wireless network standards, we will focus on important research problems and present their solutions in details. Finally, we will discuss open problems and future research directions in mobile video. The tutorial will be composed of five parts, which are briefly described in Sec. 1-5.

We study the problem of improving the user perceived quality of online games in which multiple players form a game session and exchange game-state updates over an overlay network. We propose an Indirect Relay System (IRS) to forward game-state updates over detour paths in order to reduce the round-trip time (RTT) among players. The IRS system efficiently identifies and ranks potential detour paths between any two players, and dynamically selects the most suitable one based on network and client conditions. To the best of our knowledge, this is the first system that directly reduced RTTs among players in online games, while previous works in the literature mitigate the network latency issue by either hiding it from players or preventing players with high RTTs from being in the same game session. We implement the proposed IRS system and deploy it on 500 PlanetLab nodes. The results from real experiments show that the IRS system improves the online gaming quality from several aspects, while incurring negligible network and processing overheads. We also deploy the IRS system on a number of residential computers with DSL and cable modem access links and we successfully found several detour paths among them. To evaluate the IRS system with wider ranges of system parameters we conduct extensive trace-driven simulations using a large number of real game client IPs. The experimental and simulation results show that the proposed IRS system: (i) significantly reduces RTTs among players, (ii) increases number of peers a player can connect to and maintain good gaming quality, (iii) imposes negligible network and processing overheads, and (iv) improves gaming quality and player performance.

We propose a general quality-power adaptation framework that controls the perceived video quality and the length of viewing time on battery-powered video receivers. The framework can be used for standalone video devices (e.g., DVD players and notebooks) as well as mobile receivers obtaining video signals from wireless networks (e.g., mobile TV and video streaming over WiMAX). Furthermore, the framework supports both live streams (e.g., live TV shows) and pre-encoded video streams (e.g., DVD movies). We present an adaptation algorithm for each mobile device to determine the optimal substream that can be received, decoded, and rendered to the user at the: (i) highest quality for a given viewing time, and (ii) longest viewing time for a given quality without exceeding the battery level constraint. We instantiate this framework and work out its details for mobile video broadcast networks. In particular, we propose a new video broadcast scheme that enables mobile video devices to efficiently adapt scalable video streams and achieve power saving proportional to the bit rates of the received streams. We implement the proposed framework in an actual mobile video streaming testbed and we conduct experiments using real video streams broadcast to mobile phones. These experiments show the practicality of the proposed framework and the possibility of achieving viewing time scalability. For example, on a mobile phone receiving and decoding the same video program, a viewing time in the range from 4 to 11 hours can be achieved by adaptively controlling the frame rate and visual quality of the video stream.

In peer-to-peer (P2P) mesh-based streaming systems, each video sequence is typically divided into segments, which are then streamed from multiple senders to a receiver. The receiver needs to coordinate the senders by specifying a transmission schedule for each of them. We consider the scheduling problem in both live and on-demand P2P streaming systems. We formulate the problem of scheduling segment transmission in order to maximize the perceived video quality of the receiver. We prove that this problem is NP-Complete. We present an integer linear programming (ILP) formulation for this problem, and we optimally solve it using an ILP solver. This optimal solution, however, is computationally expensive and is not suitable for real-time streaming systems. Thus, we propose a polynomial-time approximation algorithm, which yields transmission schedules with analytical guarantees on the worst-case performance. More precisely, we show that the approximation factor is at most 3, compared to the absolutely optimal solution as a benchmark. We implement the proposed approximation and optimal algorithms in a packet-level simulator for P2P streaming systems. We also implement two other scheduling algorithms proposed in the literature and used in popular P2P streaming systems. By simulating large P2P systems and streaming nine real video sequences with diverse visual and motion characteristics, we demonstrate that our proposed approximation algorithm: (i) produces near-optimal perceived video quality, (ii) can run in real time, and (iii) outperforms other algorithms in terms of perceived video quality, smoothness of the rendered videos, and balancing the load across sending peers. For example, our simulation results indicate that the proposed algorithm outperforms heuristic algorithms used in current systems by up to 8 dB in perceived video quality and up to 20% in continuity index.

We study the problem of broadcasting video streams over a WMAN to many mobile devices. We propose to form a cooperative network among mobile devices that receive the same video stream, and share received video data over a WLAN. The proposed system significantly reduces the energy consumption and the channel switching delay. We design a distributed leader election algorithm for the cooperative system and analytically show that the proposed system outperforms current systems in terms of energy consumption and channel switching delay. We evaluate the proposed system in a real mobile video streaming testbed as well as in a trace driven simulator. Our experimental results show that the proposed system: (i) achieves as high as 70% of energy saving gain, (ii) outperforms current systems with only three cooperative mobile devices, (iii) reduces channel switching delay by up to 98%, (iv) is robust under device failures and quickly reacts to network dynamics, and (v) uniformly distributes load across all cooperative devices.

We present the design of a peer-to-peer (P2P) live streaming system that uses scalable video coding as well as network coding. The proposed design enables flexible customization of video streams to support heterogeneous receivers, highly utilizes upload bandwidth of peers, and quickly adapts to network and peer dynamics. Our design is simple and modular. Therefore, other P2P streaming systems could also benefit from various components of our design to improve their performance. We conduct an extensive quantitative analysis to demonstrate the expected performance gain from the proposed design. Our analysis uses actual scalable video traces and realistic P2P streaming environments with high churn rates, heterogeneous peers, and flash crowd scenarios. Our results show that the proposed system can achieve: (i) significant improvement in the visual quality perceived by peers (several dBs are observed), (ii) smoother and more sustained streaming rates, (iii) higher streaming capacity by serving more requests from peers, and (iv) more robustness against high churn rates and flash crowd arrivals of peers. This paper shows that the integration of network coding and scalable video coding in P2P live streaming systems yields better performance than current systems that use single-layer streams and proposed systems that use either network coding alone or scalable video coding alone.

In recent years, peer-to-peer (P2P) and peer-assisted streaming have emerged as promising models for low-cost multimedia distribution to large scale user communities. In this paper, we study streaming of scalable video streams over these systems. Scalable video streams are composed of multiple layers and can easily be adapted according to the characteristics and needs of receivers. Thus, they can efficiently support a wide spectrum of heterogeneous peers participating in a P2P streaming system. We present an analytical model for forecasting the long-term behavior of a P2P streaming system with scalable video streams. Our analysis takes as inputs the characteristics of a dynamic P2P streaming system and the video streams. It then analytically computes the expected throughput of the streaming system and the expected video quality delivered to peers. The analysis also provides an upper bound on the maximum number of peers that can be admitted to the system at once (i.e., in flash crowd scenarios), while ensuring a certain video quality. We present a general analysis framework that can be customized to various practical P2P streaming systems with different characteristics. Then, we show the detailed analysis of a typical P2P streaming system and we explain how other systems can be analyzed using our model. We validate our analysis by comparing its results to those obtained from simulations, which confirm the accuracy of our analysis. Our analysis and simulations enable administrators of P2P streaming systems to predict the throughput and the video quality that can be delivered to users.

The large prevalence of multimedia systems in recent years makes the security of multimedia communications an important and critical issue. We study the problem of securing the delivery of scalable video streams so that receivers can ensure the authenticity of the video content. Our focus is on recent scalable video coding (SVC) techniques, such as H.264/SVC, which can provide three scalability types at the same time: temporal, spatial, and visual quality. This three-dimensional scalability offers a great flexibility that enables customizing video streams for a wide range of heterogeneous receivers and network conditions. This flexibility, however, is not supported by current stream authentication schemes in the literature. We propose an efficient and secure authentication scheme that accounts for the full scalability of video streams, and enables verification of all possible substreams that can be extracted from the original stream. In addition, we propose an algorithm for minimizing the amount of authentication information that need to be attached to streams. The proposed authentication scheme supports end-to-end authentication, in which any third-party entity involved in the content delivery process, such as stream adaptation proxies and caches, does not have to understand the authentication mechanism. Our simulation study with real video traces shows that the proposed authentication scheme is robust against packet losses, incurs low computational cost for receivers, has short delay, and adds low communication overhead. Finally, we implement the proposed authentication scheme as an open source library called svcAuth, which can be used as a transparent add-on by any multimedia streaming application.

With the rapid increase in the demand for multimedia services, securing the delivery of multimedia content has become an important issue. Accordingly, the problem of multimedia stream authentication has received considerable attention by previous research and various solutions have been proposed. However, these solutions have not been rigorously analyzed and contrasted to each other, and thus their relative suitability for different streaming environments is not clear. This article presents comprehensive analysis and comparison among different schemes proposed in the literature to authenticate multimedia streams. Authentication schemes for nonscalable and scalable multimedia streams are analyzed. To conduct this analysis, we define five important performance metrics, which are computation cost, communication overhead, receiver buffer size, delay, and tolerance to packet losses. We derive analytic formulas for these metrics for all considered authentication schemes to numerically analyze their performance. In addition, we implement all schemes in a simulator to study and compare their performance in different environments. The parameters for the simulator are carefully chosen to mimic realistic settings. We draw several conclusions on the advantages and disadvantages of each scheme. We extend our analysis to authentication techniques for scalable streams. We pay careful attention to the flexibility of scalable streams and analyze its impacts on the authentication schemes. Our analysis and comparison reveal the merits and shortcomings of each scheme, provide guidelines on choosing the most appropriate scheme for a given multimedia streaming application, and could stimulate designing new authentication schemes or improving existing ones. For example, our detailed analysis has led us to design a new authentication scheme that combines the best features of two previous schemes.

Mobile TV broadcast networks have received significant attention from the industry and academia, as they have already been deployed in several countries around the world and their expected market potential is huge. In such networks, a base station broadcasts TV channels in bursts with bit rates much higher than the encoding bit rates of the videos. This enables mobile receivers to receive a burst of traffic and then turn off their receiving circuits till the next burst to conserve energy. The base station needs to construct a transmission schedule for all bursts of different TV channels. Constructing optimal (in terms of energy saving) transmission schedules has been shown to be an NP-complete problem when the TV channels carry video streams encoded at arbitrary and variable bit rates. In this paper, we propose a near-optimal approximation algorithm to solve this problem. We prove the correctness of the proposed algorithm and derive its approximation factor. We also conduct extensive evaluation of our algorithm using implementation in a real mobile TV testbed as well as simulations. Our experimental and simulation results show that the proposed algorithm: 1) is practical and produces correct burst schedules; 2) achieves near-optimal energy saving for mobile devices; and 3) runs efficiently in real time and scales to large scheduling problems.

Various sensor types, e.g., temperature, humidity, and acoustic, sense physical phenomena in different ways, and thus, are expected to have different sensing models. Even for the same sensor type, the sensing model may need to be changed in different environments. Designing and testing a different coverage protocol for each sensing model is indeed a costly task. To address this challenging task, we propose a new probabilistic coverage protocol (denoted by PCP) that could employ different sensing models. We show that PCP works with the common disk sensing model as well as probabilistic sensing models, with minimal changes. We analyze the complexity of PCP and prove its correctness. In addition, we conduct an extensive simulation study of large-scale sensor networks to rigorously evaluate PCP and compare it against other deterministic and probabilistic protocols in the literature. Our simulation demonstrates that PCP is robust, and it can function correctly in presence of random node failures, inaccuracies in node locations, and imperfect time synchronization of nodes. Our comparisons with other protocols indicate that PCP outperforms them in several aspects, including number of activated sensors, total energy consumed, and network lifetime.

This paper analyzes the potential of cooperative proxy caching for peer-to-peer (P2P) traffic as a means to ease the burden imposed by P2P traffic on Internet Service Providers (ISPs). In particular, we propose two models for cooperative caching of P2P traffic. The first model enables cooperation among caches that belong to different autonomous systems (ASs), while the second considers cooperation among caches deployed within the same AS. We analyze the potential gain of cooperative caching in these two models. To perform this analysis, we conduct an eight-month measurement study on a popular P2P system to collect traffic traces for multiple caches. Then, we perform extensive trace-based simulations to analyze different angles of cooperative caching schemes. Our results demonstrate that: 1) significant improvement in byte hit rate can be achieved using cooperative caching, 2) simple object replacement policies are sufficient to achieve that gain, and 3) the overhead imposed by cooperative caching is negligible. In addition, we develop an analytic model to assess the gain from cooperative caching in different settings. The model accounts for number of caches, salient P2P traffic features, and network characteristics. Our model confirms that substantial gains from cooperative caching are attainable under wide ranges of traffic and network characteristics.

Mobile TV networks have received significant attention from the industry and academia, as they have already been deployed in several countries and their expected market potential is huge. In such networks, a base station broadcasts TV channels in bursts with bit rates much higher than the encoding bit rates of the videos. This enables mobile receivers to receive a burst of traffic and then turn off their receiving circuit till the next burst to conserve energy. The base station needs to construct a transmission schedule for all bursts of different TV channels. Constructing optimal (in terms of energy saving) transmission schedules has been shown to be an NP-complete problem when the TV channels are encoded at arbitrary bit rates. In this paper, we propose a near-optimal approximation algorithm to solve this problem. We prove the correctness of the proposed algorithm and derive its approximation factor. We also conduct extensive evaluation of our algorithm using real implementation in a mobile TV testbed and simulations. Our experimental and simulation results show that the proposed algorithm: (i) is practical and produces correct burst schedules, (ii) achieves near-optimal energy saving for mobile devices, and (iii) runs efficiently in real time.

We study and analyze segment transmission scheduling algorithms in swarm-based peer-to-peer (P2P) streaming systems. These scheduling algorithms are responsible for coordinating the streaming of video data from multiple senders to a receiver in each streaming session. Although scheduling algorithms directly impact the user-perceived visual quality in streaming sessions, they have not been rigorously analyzed in the literature. In this paper, we first conduct an extensive experimental study to evaluate various scheduling algorithms on many PlanetLab nodes distributed all over the world. We study three important performance metrics: (i) continuity index which captures the smoothness of the video playback, (ii) load balancing index which indicates how the load is spread across sending peers, and (iii) buffering delay required to ensure continuous playback. Our experimental analysis reveals the strengths and weaknesses of each scheduling algorithm, and provides insights for developing better ones in order to improve the overall performance of P2P streaming systems. Then, we propose a new scheduling algorithm called on-time delivery of VBR streams (ODV). Our experiments show that the proposed scheduling algorithm improves the playback quality by increasing the continuity index, requires smaller buffering delays, and achieves more balanced load distribution across peers.

We study streaming of scalable videos over peer-to-peer (P2P) networks. We focus on efficient management of seed servers resources, which need to be deployed in the network to make up for the limited upload capacity of peers in order to deliver higher quality video streams. These servers have finite serving capacity and are often loaded with a volume of requests larger than their capacity. We formulate the problem of allocating this capacity for optimally serving scalable videos. We show that this problem is NP-complete, and propose two approximation algorithms to solve it. The first one allocates seeding resources for serving peers based on dynamic programming, and is more suitable for small seeding capacities (les 10 Mbps). The second algorithm follows a greedy approach and is more efficient for larger capacities. We evaluate the proposed algorithms analytically and in a simulated P2P streaming system. The results confirm the efficiency and near-optimality of the proposed algorithms, and show that higher-quality videos are delivered to peers if our algorithms are employed for allocating seed servers.

We consider the problem of broadcasting multiple variable-bit-rate (VBR) video streams from a base station to many mobile devices over a wireless network, so that: (i) perceived quality on mobile devices is maximized, (ii) bandwidth utilization is maximized, and (iii) energy consumption of mobile devices is minimized. We show that this problem is NP-Complete. We propose an approximation algorithm for the base station to statistically multiplex and transmit multiple VBR streams to achieve these objectives. We analytically analyze the performance of our algorithm and prove that it achieves optimal bandwidth utilization and near-optimal energy saving. Our algorithm frees network operators from the manual and error-prone bandwidth reservation process, which is usually used in practice for broadcasting VBR streams. We implement the proposed algorithm in a trace-driven simulator, and conduct extensive simulations. The simulation results show that our algorithm outperforms the existing algorithms in many aspects, including number of late frames, number of concurrently broadcast video streams, and energy saving of mobile devices. We also implement the proposed algorithm in a real testbed for video broadcasting as a proof of concept. The results from the testbed confirm that the proposed algorithm: (i) does not result in playout glitches, (ii) achieves high energy saving, and (iii) runs in real time.

We study the problem of broadcasting video streams over a WMAN to many mobile devices. We propose to form a cooperative network among mobile devices that receive the same video stream, and share received video data over a WLAN. We analytically show that the proposed system outperforms current systems in terms of energy consumption and channel switching delay. Our trace-based simulation results show that the proposed system: (i) achieves as high as 70% of energy saving gain, (ii) outperforms current systems with only two cooperative mobile devices, (iii) reduce channel switching delay by up to 98%, (iv) is robust under device failure and quickly reacts to network dynamics, and (v) uniformly distributes the load on all cooperative devices.

We investigate the problem of securing the delivery of scalable video streams so that receivers can ensure the authenticity (originality and integrity) of the video. Our focus is on recent scalable video coding techniques, e.g., H.264/SVC, that can provide three scalability types at the same time: temporal, spatial, and quality (or PSNR). This three-dimensional scalability offers a great flexibility that enables customizing video streams for a wide range of heterogeneous receivers and network conditions. This flexibility, however, is not supported by current stream authentication schemes in the literature. We propose an efficient authentication scheme that accounts for the full scalability of video streams: it enables verification of all possible substreams that can be extracted and decoded from the original stream. Our evaluation study shows that the proposed authentication scheme is robust against packet losses, adds low communication and computation overheads, and is suitable for live streaming systems as it has short delay.

In peer-to-peer (P2P) systems, a receiver needs to be matched with multiple senders, because peers have limited capacity and reliability. Efficient peer matching can reduce the cost on Internet Service Providers (ISPs) for carrying the P2P traffic. We study the following peer-matching problem: given a set of potential senders, find the best subset of them that will minimize the transit cost on ISPs. This problem is fairly general and the proposed algorithms for solving it can be used in many P2P systems. We propose two ISP-friendly algorithms for solving this problem: ISPF and ISPF-Lite. These two matching algorithms leverage public available information, such as BGP tables, to infer the network topology, and to minimize the cost on ISPs. The inference algorithms, however, are fairly complex, and we propose optimization techniques to reduce the inference time and to lower the memory requirement. We use trace-driven simulations to show that the proposed algorithms outperform other popular matching algorithms by a large margin. Between the two proposed algorithms, ISPF results in better matching, but incurs higher complexity. Hence, we recommend ISPF if resources are not stringent, otherwise ISPF-Lite is recommended.

This paper analyzes the potential of cooperative proxy caching for peer-to-peer (P2P) traffic as a means to ease the burden imposed by P2P traffic on Internet service providers (ISPs). In particular, we propose two models for cooperative caching of P2P traffic. The first model enables cooperation among caches that belong to different autonomous systems (ASes), while the second considers cooperation among caches deployed within the same AS.We analyze the potential gain of cooperative caching in these two models. To perform this analysis, we conduct an eight-month measurement study on a popular P2P system to collect actual traffic traces for multiple caches. Then, we perform an extensive trace-based simulation study to analyze different angles of cooperative caching schemes. Our results demonstrate that: (i) significant improvement in byte hit rate can be achieved using cooperative caching, (ii) simple object replacement policies are sufficient to achieve that gain, and (iii) the overhead imposed by cooperative caching is negligible.

We present a complete, running, testbed for mobile TV networks that employ the Digital Video Broadcast - Handheld (DVB-H) open standard. DVB-H based networks have been deployed in several countries around the world and currently being pilot-tested in many others. Nevertheless, there exists no open-source testbed in the literature to enable researchers to analyze and optimize the performance of such networks; most testbeds are proprietary. Our testbed implements the complete stack of the DVB-H standard and it streams real videos to actual handheld devices. It integrates several off-the-shelf hardware components and devices with software components. Some of the software components are developed by us and others are leveraged (after bug fixes and modifications) from open-source projects. In addition, we present several experiments to: (i) evaluate and compare multiple energy-saving techniques recently proposed for mobile TV networks, and (ii) demonstrate a new method to reduce the channel switching delay.

Modern wireless mobile devices have evolved to small computers that can render multimedia content, while desktop/laptop computers have become more computationally powerful with faster Internet access. As these computing devices getting more popular, users demand for more and higher quality videos in many communication applications, where clients are heterogeneous in terms of network bandwidth and computing power. The goal of this thesis is to improve client perceived-quality of various video communication systems by adopting scalable video coding tools that enable efficient rate adaptation. We seek to understand scalable coding standards and design optimization and streaming algorithms to make the best possible use of them in practical systems. We consider practical problems of video communication systems in three different environments: Internet streaming systems, TV broadcast networks, and mobile video communication systems. We propose efficient algorithms to solve the considered problems. We evaluate the proposed algorithms using numerical methods and/or simulations. Most importantly, we design and implement testbeds to validate our algorithms. The expected results of applying our algorithms to video communication systems are better video quality and higher user satisfaction as well as better bandwidth utilization and lower processing overhead.

Traditional video servers partially cope with heterogeneous client populations by maintaining a few versions of the same stream with different bit rates. More recent video servers leverage multilayer scalable coding techniques to customize the quality for individual clients. In both cases, heuristic, error-prone, techniques are currently used by administrators to determine either the rate of each stream version, or the granularity and rate of each layer in a multilayer scalable stream. In this paper, we propose an algorithm to determine the optimal rate and encoding granularity of each layer in a scalable video stream that maximizes a system-defined utility function for a given client distribution. The proposed algorithm can be used to compute the optimal rates of multiversion streams as well. Our algorithm is general in the sense that it can employ arbitrary utility functions for clients. We implement our algorithm and verify its optimality, and we show how various structuring of scalable video streams affect the client utilities. To demonstrate the generality of our algorithm, we consider three utility functions in our experiments. These utility functions model various aspects of streaming systems, including the effective rate received by clients, the mismatch between client bandwidth and received stream rate, and the client-perceived quality in terms of PSNR. We compare our algorithm against a heuristic algorithm that has been used before in the literature, and we show that our algorithm outperforms it in all cases.

Fine-grained scalable (FGS) coding of video streams has been proposed in the literature to accommodate client heterogeneity. FGS streams are composed of two layers: a base layer, which provides basic quality, and a single enhancement layer that adds incremental quality refinements proportional to number of bits received. The base layer uses nonscalable coding which is more efficient in terms of compression ratio than scalable coding used in the enhancement layer. Thus for coding efficiency larger base layers are desired. Larger base layers, however, disqualify more clients from getting the stream. In this paper, we experimentally analyze this coding efficiency gap using diverse video sequences. For FGS sequences, we show that this gap is a non-increasing function of the base layer rate. We then formulate an optimization problem to determine the base layer rate of a single sequence to maximize the average quality for a given client bandwidth distribution. We design an optimal and efficient algorithm (called FGSOPT) to solve this problem. We extend our formulation to the multiple-sequence case, in which a bandwidth-limited server concurrently streams multiple FGS sequences to diverse sets of clients. We prove that this problem is NP-Complete. We design a branch-and-bound algorithm (called MFGSOPT) to compute the optimal solution. MFGSOPT runs fast for many typical cases because it intelligently cuts the search space. In the worst case, however, it has exponential time complexity. We also propose a heuristic algorithm (called MFGS) to solve the multiple-sequence problem. We experimentally show that MFGS produces near-optimal results and it scales to large problems: it terminates in less than 0.5 s for problems with more than 30 sequences. Therefore, MFGS can be used in dynamic systems, where the server periodically adjusts the structure of FGS streams to suit current client distributions.

We present optimal schemes for allocating bits of fine-grained scalable video sequences among multiple senders streaming to a single receiver. This allocation problem is critical in optimizing the perceived quality in peer-to-peer and distributed multi-server streaming environments. Senders in such environments are heterogeneous in their outgoing bandwidth and they hold different portions of the video stream. We first formulate and optimally solve the problem for individual frames, then we generalize to the multiple frame case. Specifically, we formulate the allocation problem as an optimization problem, which is nonlinear in general. We use rate-distortion models in the formulation to achieve the minimum distortion in the rendered video, constrained by the outgoing bandwidth of senders, availability of video data at senders, and incoming bandwidth of receiver. We show how the adopted rate-distortion models transform the nonlinear problem to an integer linear programming (ILP) problem. We then design a simple rounding scheme that transforms the ILP problem to a linear programming (LP) one, which can be solved efficiently using common optimization techniques such as the Simplex method. We prove that our rounding scheme always produces a feasible solution, and the solution is within a negligible margin from the optimal solution. We also propose a new algorithm (FGSAssign) for the single-frame allocation problem that runs in O ( n log n ) steps, where n is the number of senders. We prove that FGSAssign is optimal. Furthermore, we propose a heuristic algorithm (mFGSAssign) that produces near-optimal solutions for the multiple-frame case, and runs an order of magnitude faster than the optimal one. Because of its short running time, mFGSAssign can be used in real time. Our experimental study validates our analytical analysis and shows the effectiveness of our allocation algorithms in improving the video quality.

Rate-distortion (R-D) models are functions that describe the relationship between the bitrate and expected level of distortion in the reconstructed video stream. R-D models enable optimization of the received video quality in different network conditions. Several R-D models have been proposed for the increasingly popular fine-grained scalable video sequences. However, the models' relative performance has not been thoroughly analyzed. Moreover, the time complexity of each model is not known, nor is the range of bitrates in which the model produces valid results. This lack of quantitative performance analysis makes it difficult to select the model that best suits a target streaming system. In this article, we classify, analyze, and rigorously evaluate all R-D models proposed for FGS coders in the literature. We classify R-D models into three categories: analytic, empirical, and semi-analytic. We describe the characteristics of each category. We analyze the R-D models by following their mathematical derivations, scrutinizing the assumptions made, and explaining when the assumptions fail and why. In addition, we implement all R-D models, a total of eight, and evaluate them using a diverse set of video sequences. In our evaluation, we consider various source characteristics, diverse channel conditions, different encoding/decoding parameters, different frame types, and several performance metrics including accuracy, range of applicability, and time complexity of each model. We also present clear systematic ways (pseudo codes) for constructing various R-D models from a given video sequence. Based on our experimental results, we present a justified list of recommendations on selecting the best R-D models for video-on-demand, video conferencing, real-time, and peer-to-peer streaming systems.

We propose a new probabilistic coverage protocol (denoted by PCP) that considers probabilistic sensing models. PCP is fairly general and can be used with different sensing models. In particular, PCP requires the computation of a single parameter from the adopted sensing model, while everything else remains the same. We show how this parameter can be derived in general, and we actually do the calculations for two example sensing models: (i) the probabilistic exponential sensing model, and (ii) the commonly-used deterministic disk sensing model. The first model is chosen because it is conservative in terms of estimating sensing capacity, and it has been used before in another probabilistic coverage protocol, which enables us to conduct a fair comparison. Because it is conservative, the exponential sensing model can be used as a first approximation for many other sensing models. The second model is chosen to show that our protocol can easily function as a deterministic coverage protocol. In this case, we compare our protocol against two recent deterministic protocols that were shown to outperform others in the literature. Our comparisons indicate that our protocol outperforms all other protocols in several aspects, including number of activated sensors and total energy consumed. We also demonstrate the robustness of our protocol against random node failures, node location inaccuracy, and imperfect time synchronization.

We propose new algorithms to achievek-coverage in dense sensor networks. In such networks, covering sensor locations approximates covering the whole area. However, it has been shown before that selecting the minimum set of sensors to activate from an already deployed set of sensors is NP-hard. We propose an efficient approximation algorithm which achieves a solution of size within a logarithmic factor of the optimal. We prove that our algorithm is correct and analyze its complexity. We implement our algorithm and compare it against two others in the literature. Our results show that the logarithmic factor is only a worst-case upper bound and the solution size is close to the optimal in most cases. A key feature of our algorithm is that it can be implemented in a distributed manner with local information and low message complexity. We design and implement a fully distributed version of our algorithm. Our distributed algorithm does not require that sensors know their locations. Comparison with two other distributed algorithms in the literature indicates that our algorithm: (i) converges much faster than the others, (ii) activates near-optimal number of sensors, and (iii) significantly prolongs (almost doubles) the network lifetime because it consumes much less energy than the other algorithms.

Video coders, such as H.264/SVC, can encode a video stream into multiple layers, each with a different rate. Moreover, each layer can either be coarse-grained scalable (CGS) or fine-grained scalable (FGS). FGS layers support wider ranges of client bandwidth than CGS layers, but suffer from higher coding inefficiency. Currently there are no systematic ways in the literature to determine the optimal stream structure that renders the best average quality for all clients. In this paper, we formulate an optimization problem to determine the optimal rate and encoding granularity (CGS or FGS) of each layer in a scalable video stream that maximizes a system-defined utility function for a given client distribution. We design an efficient, yet optimal, algorithm to solve this optimization problem. Our algorithm is general in the sense that it can employ arbitrary utility functions for clients. We implement our algorithm and verify its optimality. We show how various structuring of scalable video streams affect individual client utilities. We compare our algorithm against a heuristic algorithm that has been used before in the literature, and we show that our algorithm outperforms the other one in all cases.

Several previous works have experimentally shown that communication ranges of sensors are not regular disks. Rather, they follow probabilistic models. Yet, many current connectivity maintenance protocols assume the disk communication model for convenience and ease of analysis. In addition, current protocols do not provide any assessment of the quality of communication between nodes. In this paper, we take a first step in designing connectivity maintenance protocols for more realistic communication models. We propose a distributed connectivity maintenance protocol that explicitly accounts for the probabilistic nature of communication links and achieves a given target communication quality between nodes. Our protocol is simple to implement, and we demonstrate its robustness against random node failures, inaccuracy of node locations, and imperfect time synchronization of nodes using extensive simulations. We compare our protocol against others in the literature and show that it activates fewer number of nodes, consumes much less energy, and significantly prolongs the network lifetime.

We present the design and evaluation of a wireless sensor network for early detection of forest fires. We first present the key aspects in modeling forest fires. We do this by analyzing the Fire Weather Index (FWI) System, and show how its different components can be used in designing efficient fire detection systems. The FWI System is one of the most comprehensive forest fire danger rating systems in North America, and it is backed by several decades of forestry research. The analysis of the FWI System could be of interest in its own right to researchers working in the sensor network area and to sensor manufacturers who can optimize the communication and sensing modules of their products to better fit forest fire detection systems. Then, we model the forest fire detection problem as a k-coverage problem in wireless sensor networks. In addition, we present a simple data aggregation scheme based on the FWI System. This data aggregation scheme significantly prolongs the network lifetime, because it only delivers the data that is of interest to the application. We validate several aspects of our design using simulation.

Peer-to-peer (P2P) file sharing systems generate a major portion of the Internet traffic, and this portion is expected to increase in the future. We explore the potential of deploying proxy caches in different autonomous systems (ASes) with the goal of reducing the cost incurred by Internet service providers and alleviating the load on the Internet backbone. We conduct a measurement study to model the popularity of P2P objects in different ASes. Our study shows that the popularity of P2P objects can be modeled by a Mandelbrot-Zipf distribution, regardless of the AS. Guided by our findings, we develop a novel caching algorithm for P2P traffic that is based on object segmentation, and partial admission and eviction of objects. Our trace-based simulations show that with a relatively small cache size, less than 10% of the total traffic, a byte hit rate of up to 35% can be achieved by our algorithm, which is close to the byte hit rate achieved by an off-line optimal algorithm with complete knowledge of future requests. Our results also show that our algorithm achieves a byte hit rate that is at least 40% more, and at most triple, the byte hit rate of the common Web caching algorithms. Furthermore, our algorithm is robust in face of aborted downloads, which is a common case in P2P systems.

Recent research efforts have demonstrated the great potential of building cost-effective media streaming systems on top of peer-to-peer (P2P) networks. A P2P media streaming architecture can reach a large streaming capacity that is difficult to achieve in conventional server-based streaming services. Hybrid streaming systems that combine the use of dedicated streaming servers and P2P networks were proposed to build on the advantages of both paradigms. However, the dynamics of such systems and the impact of various factors on system behavior are not totally clear. In this article, we present an analytical framework to quantitatively study the features of a hybrid media streaming model. Based on this framework, we derive an equation to describe the capacity growth of a single-file streaming system. We then extend the analysis to multi-file scenarios. We also show how the system achieves optimal allocation of server bandwidth among different media objects. The unpredictable departure/failure of peers is a critical factor that affects the performance of P2P systems. We utilize the concept of peer lifespan to model peer failures. The original capacity growth equation is enhanced with coefficients generated from peer lifespans that follow an exponential distribution. We also propose a failure model under arbitrarily distributed peer lifespan. Results from large-scale simulations support our analysis.

No abstract available.

We present the design, implementation, and evaluation of PROMISE, a novel peer-to-peer media streaming system encompassing the key functions of peer lookup, peer-based aggregated streaming, and dynamic adaptations to network and peer conditions. Particularly, PROMISE is based on a new application level P2P service called CollectCast. CollectCast performs three main functions: (1) inferring and leveraging the underlying network topology and performance information for the selection of senders; (2) monitoring the status of peers and connections and reacting to peer/connection failure or degradation with low overhead; (3) dynamically switching active senders and standby senders, so that the collective network performance out of the active senders remains satisfactory. Based on both real-world measurement and simulation, we evaluate the performance of PROMISE, and discuss lessons learned from our experience with respect to the practicality and further optimization of PROMISE.

In this paper, we study a peer-to-peer media streaming system with the following characteristics: (1) its streaming capacity grows dynamically; (2) peers do not exhibit server-like behavior; (3) peers are heterogeneous in their bandwidth contribution; and (4) each streaming session may involve multiple supplying peers. Based on these characteristics, we investigate two problems: (1) how to assign media data to multiple supplying peers in one streaming session and (2) how to quickly amplify the system's total streaming capacity. Our solution to the first problem is an optimal media data assignment algorithm OTS/sub p2p/, which results in minimum buffering delay in the consequent streaming session. Our solution to the second problem is a distributed differentiated admission control protocol DAC/sub p2p/. By differentiating between requesting peers with different outbound bandwidth, DAC/sub p2p/ achieves fast system capacity amplification; benefits all requesting peers in admission rate, waiting time, and buffering delay; and creates an incentive for peers to offer their truly available out-bound bandwidth.