The goal of this paper is to minimize service disruption, a unique phenomenon in peer-to-peer (P2P) streaming system and the major contributing factor to degrade user experience. In order to improve its streaming quality and stability, a P2P system should select peers with abundant bandwidth resource and prospect longevity as the parents of other peers. Towards this end, we propose PRW (peer resilient weight), a metric to evaluate a peer's healthiness regarding these two aspects. The theoretical background of PRW originates from the optimization framework based on the generalized flow theory. To show PRW's applicability to a wide variety of P2P streaming solutions, we propose several parent selection algorithms guided by PRW under the single-tree, multi-tree, and mesh structures. Using MSN and PPLive traces, we find our algorithms to be able to achieve lower service disruption and lower peer rejection, compared to several existing heuristics and algorithms.

In this paper we propose a quantitative model to study user satisfaction level in online video streaming, which features great variety across video access sessions under the impact of network conditions and user-specific factors. By applying survival analysis to video session duration ratio, which in our study is regarded to be a measure of user satisfaction level, we find user satisfaction is not only related to network QoS factors, such as buffer time and buffer count, but also susceptible to the users' inclination to the contents of videos. Based on Cox regression model, we analyze the quantitative relationship between user satisfaction level in video streaming and several predictor variables such as buffer count rate, buffer time rate and video popularity degree. Experimental results prove that the model can accurately evaluate user satisfaction levels of our test video access sessions with high probability.

Receiver heterogeneity of a P2P network can be effectively addressed by scalable video streams. Due to the discontinuous nature of scalable video, traditional convex-optimization approach is not applicable. We propose a message-passing based approach for optimization using the sum- product update algorithm. Advantage of this simple but elegant approach over other heuristic-based algorithm is that the optimization algorithm itself is independent of the underlying constraints. The algorithm iteratively updates layer allocation decision based on a given set of codewords. The codewords are binary representation of various network and video constraints. Therefore, any number of constraints can be used to generate a set of codewords without modifying the algorithm. To the best of our knowledge, this is the first work that systematically addresses the scalable video optimization problem. Preliminary simulation with up to 8 layers shows that the sum- product update process achieves an average layer delivery of 95% or higher.

Peer-to-peer (P2P) traffic is arguably the biggest contributor to today's Internet traffic. So far, very limited effort has been paid to theoretically analyze the effect of bringing locality-awareness into P2P applications. In this paper, we analyze three locality-awareness policies for BitTorrent-like system: tracker locality(neighbor selection), choker locality(choking and unchoking) and picker locality(piece picking). Based on an H-sphere model which captures the essential property of Internet topology, we analyze how much network load saving can be expected for these locality policies, as well as their impact to the downloading efficiency of the system. Through analytical study and simulation, we have the following findings. First, when the system enters the steady state, the locality policies proposed in this paper can achieve the same downloading efficiency as the standard BitTorrent system. Second, these locality policies can significantly alleviate the traffic load on the Internet. Finally, we find that there exists no all-around winner. Instead, each policy performs the best under different system configuration parameters, such as number of unchoked peers.

This paper addresses the problem of optimal rate allocation for video stream in peer-to-peer networks. We present a distributed rate allocation algorithm with the goal of minimizing the total video distortion among peers receiving the same video. The scheme assumes that video streams can be transcoded/re- quantized at intermediate peers. We deploy a double pricing solution that simultaneously incorporates the network and the relay constraints in the peer-to-peer network and compare it with a single pricing solution where the relay constraint is applied only after all the communicating peers converge to optimality. We combine our solution with two video adaptation techniques: transcoding using times 264 and scalable coding using H.264 SVC (scalable video coding) extension. Our experiment shows that the double pricing solution consistently achieves a smaller aggregate distortion for all peers over the single pricing solution.

Peer-to-peer (P2P) is a powerful platform for a variety of multimedia streaming applications over the Internet such as video-on-demand, video conferencing, live broadcasting, etc. A P2P system is extremely cost-effective since it utilizes the resources (CPU cycles, storage space, and uplink bandwidth) of peer machines.The decentralized and shared bandwidth nature of a P2P network, therefore, makes it an effective choice for implementing video conferencing applications. In this work, Vanets is presented , a P2P based video conferencing system that takes advantage of transcoding to optimally allocate streaming rates for all participating peers. The solution presented in this paper distinguishes between active and passive participants and enhances the video quality of the active participant.

Recent advancement in multimedia and network has enabled the development of video accelerator for video sharing website where users can upload, view and share video clips (e.g. YouTube) to achieve better user experience. Several applications have already been developed. The paper examines these technical issues. The benefits of these techniques are discussed. Also the performances of these applications are evaluated by analyzing the network traffic.

This paper addresses the problem of optimal rate allocation for video streaming in a multi-path peer-to-peer mesh network. We present a distributed rate allocation algorithm that minimizes the total rate distortion among receiving peers. The scheme assumes that video streams can be transcoded/re-quantized at intermediate peers. We deploy a double pricing solution that simultaneously incorporates both the network and the relay constraints. We compare it with a single pricing solution where the relay constraint is applied only after all the communicating peers have converged. Our simulation shows that the double pricing solution consistently achieves a smaller aggregate distortion for all peers in comparison to the single pricing solution and thus achieves higher video quality.

Layered streaming is an effective solution to address receiver heterogeneity in a peer-to-peer (P2P) network. This paper addresses the problem of rate allocation for layered video stream in p2p mesh networks. We present a distributed rate allocation algorithm that achieves close to optimal layer allocation among peers receiving the same video. We use load balancing technique that evenly distributes layer requests to a parent peer. Weight based layer allocation technique ensures that a child peer with higher children receives higher priority in servicing layer allocation request from its parents. Results show that for up to seven layers streamed by a server, the algorithm maintains a layer delivery ratio of 88% or more among all peers in a network.

This paper presents the measurement study of locality-aware P2P solutions over real-world Internet autonomous systems (AS) topology. By using the accesses of nodes of PlanetLab testbed, we create a detailed AS-level map including the end-to-end path of all nodes, as well as the relationship of all involved ASes. Based on this map, we evaluate the performance of a set of locality-aware P2P solutions, including an optimal solution guaranteeing the minimum AS hop count, as well as modified BitTorrent system with locality-awareness built into its neighbor selection, peer choking/unchoking, and piece selection processes. Our findings suggest that locality-awareness can help existing P2P solution to significantly decrease load on Internet, and achieve shorter downloading time. By comparing the performance of different kinds of locality-aware and traditional BitTorrent systems, we also point out the necessity to tradeoff between the goals of optimizing AS-related performance and achieving fairness among peers such as intra-AS traffic and peer burden fairness.

A unique challenge in P2P network is that the peer dynamics (departure or failure) cause unavoidable disruption to the downstream peers. While many works have been dedicated to consider fault resilience in peer selection, little understanding is achieved regarding the solvability and solution complexity of this problem from the optimization perspective. To this end, we propose an optimization framework based on the generalized flow theory. Key concepts introduced by this framework include resilience factor, resilience index, and generalized throughput, which collectively model the peer resilience in a probabilistic measure. Under this framework, we divide the domain of optimal peer selection along several dimensions including network topology, overlay organization, and the definition of resilience factor and generalized flow. Within each subproblem, we focus on studying the problem complexity and finding optimal solutions. Simulation study is also performed to evaluate the effectiveness of our model and performance of the proposed algorithms.

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution into practice, one must take into account the dynamic and unpredictable nature of wireless traffic demand. This paper presents an integrated framework for network routing in multi-radio multi-channel wireless mesh networks under dynamic traffic demand. This framework consists of two important components: traffic estimation and routing optimization. By analyzing the traces collected at wireless access points, the traffic estimation component predicts future traffic demand based on its historical value using time-series analysis, and represents the prediction result in two forms - mean value and statistical distribution. The optimal mesh network routing strategies then take these two forms of traffic demand estimations as inputs. In particular, two routing algorithms are proposed based on linear programming which consider the mean value and the statistical distribution of the predicted traffic demands, respectively. The trace-driven simulation study demonstrates that our integrated traffic estimation and routing optimization framework can effectively incorporate traffic dynamics in mesh network routing, where both algorithms outperform the shortest path algorithm in about 80% of the test cases.

Recent theoretical and simulation-based studies have confirmed the tremendous benefit of peer-to-peer (P2P)communication at reducing the cost of running a VoD service.To date, very limited effort has been paid to validate the concept of peer-assisted VoD service, especially in terms of system implementation and service deployment. In this paper, we present the case study of a peer-assisted video-on-demand (VoD) system. We designed and developed Bit-Tube, a BitTorrent-compliant VoD system. By combining client/server and P2P downloading, it supports seamless transition across the spectrum from pure client-server mode to BitTorrent mode. Within this framework, we experiment with a series of piece picking policies to enhance BitTubepsilas support to video streaming and promote locality-aware P2P downloading. We evaluate our system over PlanetLab,which hosts the user-side component of the BitTube system and emulates the global-scale user requests to the VoD service.

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution in practice, one must take into account the dynamic and uncertain nature of wireless traffic demand. There are two basic approaches to address the traffic uncertainty in network routing: (1) predictive routing which infers the traffic demand with maximum possibility based in its history and optimizes the routing strategy based on the predicted traffic demand and (2) oblivious routing which considers all the possible traffic demands and selects the routing strategy where the worst-case network performance could be optimized. This paper conducts a systematic comparison study of these two approaches based on the extensive simulation study over a variety of network and traffic scenarios. It identifies the key factors of the network topology and traffic profile that affect the performance of each routing strategy and provides guidelines towards the strategy selection in mesh network routing under uncertain traffic demands.

This paper considers two important issues for video sensor networks: (1) timely delivery of captured video stream and (2) energy-efficient network design. Based on network calculus, it presents a unified analytical framework that is able to quantitatively weigh the tradeoff between these two factors. In particular, it derives the service curve, buffer and delay bound under single-hop and multi-hop scenarios for video sensor networks under power management. To the best of our knowledge, this is the first work that extends the network calculus theory to the domain of wireless network with the consideration of power management and wireless interference. Our analysis has been validated through experiments conducted on a video sensor network testbed.

High-throughput P2P streaming relies on peer selection, the strategy a peer uses to select other peer(s) as its parent(s) of streaming. Although this problem has been thoroughly investigated in the classical optimization framework, it still remains unaddressed as how to sustain throughput competitive to the optimum under highly dynamic peer churning. We propose an online distributed peer selection algorithm based on "shortest- path" routing where the overlay edge length is an asymptotic function of its traffic load. This basic algorithm is further extended under practical settings such as multi-parent streaming, admission control, delay constraint, and simplified topology. In all above settings, we prove approximation bound of our algorithm to the optimal throughput. Through evaluation under different topological setups and peer churning sequences, we show our solution to consistently deliver competitive throughput, which greatly outperform its theoretical bound.

Multicast is an important communication paradigm, also a problem well known for its difficulty (NP-completeness) to achieve certain optimization goals, such as minimum network delay. Recent advances in network coding has shed a new light onto this problem. In network coding, forwarding nodes can perform arbitrary operations on data received, other than forwarding or replicating, to enhance throughput of a multicast session. In this paper, we show that with the aid of network coding, the once intractable optimal multicast routing problem becomes tractable. In this problem, given a set of multicast sessions and their traffic demands, one tries to route the multicast traffic regarding various objectives, such as to minimize overall delay, or to maximize the battery life of each node. We further show that his problem can be solved in a distributed fashion: each node akes its own routing decisions based on periodic updating information from neighboring nodes. We prove that starting from any initial routing assignment, the proposed distributed routing algorithm is able to converge to the point where the value of the objective function is optimized. Our solution can be fit into a variety of networks to achieve different optimization goals. The example in this paper is maximum lifetime routing in multi-hop wireless network.

Layered streaming is an effective solution to address the receiver heterogeneity in peer-to-peer (P2P) multimedia distribution. This paper targets a fundamental challenge in this application, i.e., how to find optimal routing structure maximizing receiver throughput and achieving intra-layer and inter-layer fairness. We formulate the problem using the multicommodity flow theory, and propose a series of routing algorithms that fully explore the tradeoff between theoretical optimality and practicability. For each algorithm, we have proved its optimality to achieve maximum throughput under fairness constraint, or approximation bound to the optimal rate. Experimental results confirm our algorithms to greatly outperform their theoretical bounds.

P2P (peer-to-peer) technology has proved itself an efficient and cost-effective solution to support large-scale multimedia streaming. Different from traditional P2P applications, the quality of P2P streaming is strictly determined by performance metrics such as streaming delay. To meet these requirements, previous studies resorted to intuitions and heuristics to construct peer selection solutions incorporating topology and proximity concerns. However, the impact of proximity-aware methodology and delay tolerance of peers on the scalability of P2P system remains an unanswered question. In this paper, we study this problem via an analytical approach. To address the challenge of incorporating Internet topology into P2P streaming analysis, we construct a H-sphere network model which maps the network topology from the space of discrete graph to the continuous geometric domain, meanwhile capturing the the power-law property of Internet. Based on this model, we analyze a series of peer selection methods by evaluating their performance via key scalability metrics. Our analytical observations are further verified via simulation on Internet topologies.

Wireless mesh networks have attracted increasing attention and deployment as a high-performance and low-cost solution to last-mile broadband Internet access. Network routing plays a critical role in determining the performance of a wireless mesh network. To study the best mesh network routing strategy which can maximize the network throughput while satisfying the fairness constraints, existing research proposes to formulate the mesh network routing problem as an optimization problem. These works usually make ideal assumptions such as known static traffic input. Whether they could be applied for practical use under the highly dynamic and uncertain traffic in wireless mesh network is still an open issue. The main objective of this paper is to understand the effects of traffic uncertainty in wireless mesh networks and consider these effects in throughput maximization routing. It identifies the appropriate optimization framework that could integrate the statistical user traffic demand model into a tractable throughput maximization problem. The trace-driven simulation study demonstrates that our algorithm can effectively incorporate the traffic demand uncertainty in routing optimization, and outperform the throughput maximization routing which only considers static traffic demand.

Video sensor network is evolving from an isolated system to an integral component of the global information infrastructure. In this paper, we argue that when video sensor network becomes a public information source on the Internet, DRM (digital rights management) must be enforced, due to the sensitivity and the privacy natures of sensor content. Moreover, existing DRM solutions do not suffice because the explicit one-to-one mapping between content producer and consumer does not apply in the sensor network domain. We propose a DRM-enabled content service architecture for video sensor network. Within this architecture, we propose a binary-tree-based hierarchical key generation scheme for data encryption, and adopt a label-guided watermarking strategy to address the unique challenges of video sensor content. We present the evaluation results of our solution based on a preliminary video sensor testbed system

In this paper, the traffic confidentiality and study of the traffic pattern concealment problem via routing control is focused. First, the number of nodes in a WMN is limited. Second, traffic forwarding relationship among nodes is strongly dependent on their locations and the network topology, which is static and known a priori in WMN. To better utilize the wireless channel resource and enhance the data delivery performance, a short path is usually selected. In light of these problems, it is aimed to design a light weight traffic privacy preserving mechanism for WMN. The penalty-based routing algorithm is proposed to achieve the goal of hiding traffic pattern by exploiting the richness of available paths between two nodes in WMN. The algorithm operates in three phases, path pool generation, candidate path selection and individual packet routing. These results show that with this algorithm, the destination node is able to consistently limit the proportion of mutual information it shares with the observing nodes.

Although initially proposed as the deployable alternative to IP multicast, the overlay network actually revolutionizes the way network applications can be built. In this paper, we study the rate allocation problem in overlay-based multirate multicast, which can be understood as a utility-based resource allocation problem. Each receiver is associated with a utility defined as a function of its streaming rate. Our goal is to maximize the aggregate utility of all receivers, subject to network capacity constraint and data constraint. The latter constraint is unique in overlay multicast, mainly due to the dual role of end hosts as both receivers and senders. We use a price-based approach to address this problem. Two types of prices, network price and data price, are generated with regard to the two constraints of the problem. A distributed algorithm is proposed, where each receiver adjusts its flow rate according to the associated network price and data price. The algorithm is proved to converge to the optimal point, where the aggregate utility of all receivers is maximized. We implement our algorithm using an end-host-based protocol. Our protocol purely relies on the coordination of end hosts to accomplish tasks originally assigned to network routers, which makes it directly deployable to the existing network infrastructure.

Tele-immersive 3D multi-camera room environments are starting to emerge and with them new challenging research questions. One important question is how to organize the large amount of visual data, being captured, processed, transmitted and displayed, and their corresponding resources, over current COTS computing and networking infrastructures so that "everybody" would be able to install and use tele-immersive environments for conferencing and other activities. In this paper, we propose a novel cross-layer control and streaming framework over general purpose delivery infrastructure, called TEEVE (tele-immersive environments for everybody). TEEVE aims for effective and adaptive coordination, synchronization, and soft QoS-enabled delivery of tele-immersive visual streams to remote room(s). The TEEVE experiments between two tele-immersive rooms residing in different institutions more than 2000 miles apart show that we can sustain communication of up to 12 3D video streams with 4/spl sim/5 3D frames per second for each stream, yielding 4/spl sim/5 tele-immersive video rate.

Energy efficient routing is a critical problem in multihop wireless networks due to the severe power constraint of wireless nodes. Despite its importance and many research efforts towards it, a distributed routing algorithm that maximizes network lifetime is still missing. To address this problem, we propose a novel utility-based nonlinear optimization formulation to the maximum lifetime routing problem. Based on this formulation, we further present a fully distributed, localized routing algorithm, which is proved to converge to the optimal point, where the network lifetime is maximized. Solid theoretical analysis and simulation results are presented to validate our solution.

Although initially proposed as the deployable alternative to IP multicast, overlay multicast actually offers us great flexibilities on QoS-aware resource allocation for network applications. For example, in overlay multicast streaming, (1) the streaming rate of each client can be diversified to better accommodate network heterogeneity, through various end-to-end streaming adaptation techniques; and (2) one can freely organize the overlay session by rearranging the multicast tree, for the purpose of better resource utilization and fairness among all clients. The goal of this paper, is to find the max-min rate allocation in overlay multicast, which is pareto-optimal in terms of network resource utilization, and max-min fair. We approach this goal in two steps. First, we present a distributed algorithm, which is able to return the max-min rate allocation for any given overlay multicast tree. Second, we study the problem of finding the optimal tree, whose max-min rate allocation is optimal among all trees. After proving its NP-hardness, we propose a heuristic algorithm of overlay multicast tree construction. A variation of the heuristic is also designed to handle the dynamic client join/departure. Both of them have approximation bound of 1/2 to the optimal value. Experimental results show that they achieve high average throughput, almost saturate link utilization, and consistent min-favorability.

In this paper, we examine the problem of large-volume data dissemination via overlay networks. A natural way to maximize the throughput of an overlay multicast session is to split the traffic and feed them into multiple trees. While in single-tree solutions, bandwidth of leaf nodes may remain largely under-utilized, multi-tree solutions increase the chances for a node to contribute its bandwidth by being a relaying node in at least one of the trees. We study the following problems: (1) What is the maximum capacity multi-tree solutions can exploit from overlay networks? (2) When multiple sessions compete within the same network, what is the relationship of two contradictory goals: achieving fairness and maximizing overall throughput? (3) What is the impact of IP routing in achieving at constraining the optimal performance of overlay multicast.We extend the multicommodity flow model to the case of overlay data dissemination, where each commodity is associated with an overlay session, rather than the traditional source-destination pair. We first prove that the problem is solvable in polynomial time, then propose an ε-approximation algorithm, assuming that each commodity can be split in arbitrary ways. The solution to this problem establishes the theoretical upper bound of overall throughput that any multi-tree solution could reach. We then study the same problem with the restriction that each commodity can only be split and fed into a limited number of trees. A randomized rounding algorithm and an online tree-construction algorithm are presented. All these algorithms are evaluated by extensive simulations.

Although initially proposed as the deployable alternative to Internet protocol multicast, the application-layer overlay network actually revolutionizes the way network applications can be built, since each overlay node is an end host and is able to carry out more functions than simply forwarding packets. The paper addresses the on-demand media distribution problem in the context of an overlay network. We take advantage of the strong buffering capabilities of end hosts, and propose a novel overlay multicast strategy, oStream. We have performed extensive analysis and performance evaluation with respect to the scalability and the efficiency of oStream. With respect to the required server bandwidth, we show that oStream defeats the theoretical lower bound of traditional multicast-based approaches, under both sequential and nonsequential stream access patterns. oStream is also robust against bursty requests. With respect to bandwidth consumption on the backbone network, we show that the benefit introduced by oStream overshadows the topological inefficiency (e.g., link stress and stretch) introduced by using application-layer multicast.

The paper targets the problem of optimal resource allocation in overlay multicast, which poses both theoretical and practical challenges. Theoretically, resource allocation among overlay flows is not subject to the network capacity constraint but also the data constraint, mainly due to the dual role of end hosts as both receivers and senders. Practically, existing distributed resource allocation schemes assume the network links to be capable of measuring flow rates, calculating and communicating price signals, none of which actually exists in the Internet today. We address these challenges as follows. First, we formalize the problem using nonlinear optimization theory, which incorporates both network constraint and data constraint. Based on our theoretical framework, we propose a distributed algorithm, which is proved to converge to the optimal point, where the aggregate utility of all receivers is maximized. Second, we propose an end-host-based solution, which relies on the coordination of end hosts to accomplish tasks originally assigned to network links. our solution can be directly deployed without any changes to the existing network infrastructure.

In this paper, we propose a peer-to-peer streaming solution to address the on-demand media distribution problem. We identify two issues, namely the asynchrony of user requests and heterogeneity of peer network bandwidth. Our key techniques to address these two issues are cache-and-relay and layer-encoded streaming. A unique challenge of layered peer-to-peer streaming is that the bandwidth and data availability (number of layers received) of each receiving peer are constrained and heterogeneous, which further limits the bandwidth and data availability of its downstream node when it acts as the supplying peer. This challenge distinguishes our work from existing studies on layered multicast. Our experiments show that our solution is efficient at utilizing bandwidth resource of supplying peers, scalable at saving server bandwidth consumption, and optimal at maximizing streaming qualities of all peers.

Building and dynamically configuring component-based systems is an important topic in distributed systems and ubiquitous computing. However, the systematic and automatic configuration management remains a challenging problem for the following reasons: (1) QoS-enforced service delivery demands to maximize the system performance out of the best configuration, (2) dynamically varied resource availability in the distributed environment makes it desirable to achieve the optimized system resource consumption. We present a graph-based dependency management model to address the above problems. Our model integrates the management of inter-component functional dependency, including consistency checking and automatic system configuration, as well as QoS-aware resource dependency management. Based on the model, we present a pruning-based configuration selection algorithm, which is able to consistently optimize the system resource consumption, while preserving the QoS level in a heteregeneous environment. Our initial simulation results prove the soundness of our model and algorithm.

A scalable middleware solution for QoS-aware multimedia service delivery in the ubiquitous computing environment remains a challenging problem. Its heterogeneous and dynamic nature demands a more flexible and intelligent framework. We present SMART, a self-reconfigurable component-based middleware solution to address this issue. The system responds to the reconfiguration requests from applications and users to offer extensibility and efficiency. Furthermore, we present an active controlling mechanism, in which the middleware is able to adapt to the environment variation in a timely fashion. In addition, we describe user management in our framework, which preserves our user-centric philosophy. Finally, we discuss MobiMan, an integrated multimedia service platform as the proof-of-concept application of SMART .

No abstract available.