P2P流媒体中的数据分配算法

最近兴起的P2P技术在充分利用客户资源、提高系统的可伸缩性方面具有巨大的潜力,基于P2P提供视频服务已成为Internet的一项重要应用.在多对单P2P模式下,对多个发送端最优地分配发送速率和数据是一个难题.为此,提出了一种新的分配算法.首先,应用排队论把最优速率分配问题模型化为非线性最优化问题,推导出求解最优化问题的速率分配公式;然后,基于该公式提出最优速率分配算法(ORAA),并对ORAA输出解的最优性给出证明;最后,提出动态速率分配算法(DRAA).DRAA对动态的网络环境具有自适应性,能根据网络条件的变化最优地为多个发送端进行速率和数据分配.仿真实验结果表明,在不同的参数条件下,DRAA算法减少了计算和通信开销,比同类算法有更好的性能.     

Rate-distortion optimized streaming of packetized media

This paper addresses the problem of streaming packetized media over a lossy packet network in a rate-distortion optimized way. We show that although the data units in a media presentation generally depend on each other according to a directed acyclic graph, the problem of rate-distortion optimized streaming of an entire presentation can be reduced to the problem of error-cost optimized transmission of an isolated data unit. We show how to solve the latter problem in a variety of scenarios, including the important common scenario of sender-driven streaming with feedback over a best-effort network, which we couch in the framework of Markov decision processes. We derive a fast practical algorithm for nearly optimal streaming in this scenario, and we derive a general purpose iterative descent algorithm for locally optimal streaming in arbitrary scenarios. Experimental results show that systems based on our algorithms have steady-state gains of 2-6 dB or more over systems that are not rate-distortion optimized. Furthermore, our systems essentially achieve the best possible performance: the operational distortion-rate function of the source at the capacity of the packet erasure channel.     

Complexity of cloud-based transcoding platform for scalable and effective video streaming services

Nowadays, a fast network improves the quality of our daily life and we can enjoy a variety of services over the Internet. Different types of media streaming services have been proposed and utilized as the network speed is now sufficiently fast to deliver high-quality live streaming. Usually, different media streaming services deliver streaming data by using different protocols such as the real-time message protocol (RTMP), real-time streaming protocol (RTSP), and Windows media HTTP streaming protocol (WMSP). In this paper, we propose and implement a cloud-based scalable and cost-effective video streaming transcoding service platform to provide the service of changing real-time streaming protocols (RTMP/RTSP) and codecs (H.263/H.264). A transcoder dispatching problem (TDP) over the cloud platform is also defined, which attempts to serve all the transcoding requests by minimizing the cost of virtual machines. Further, a transcoder dispatching algorithm and an online transcoder dispatching algorithm are proposed for the TDP. These algorithms are implemented on the Amazon EC2 platform. Experimental results demonstrate that by renting different levels of virtual machines dynamically and intelligently, we can provide a scalable and cost-effective transcoding service for bridging heterogeneous streaming media.     

Optimizing the Throughput of Data-Driven Peer-to-Peer Streaming

During recent years, the Internet has witnessed a rapid growth in deployment of data-driven (or swarming based) peer-to-peer (P2P) media streaming. In these applications, each node independently selects some other nodes as its neighbors (i.e. gossip-style overlay construction), and exchanges streaming data with the neighbors (i.e. data scheduling). To improve the performance of such protocol, many existing works focus on the gossip-style overlay construction issue. However, few of them concentrate on optimizing the streaming data scheduling to maximize the throughput of a constructed overlay. In this paper, we analytically study the scheduling problem in data-driven streaming system and model it as a classical min-cost network flow problem. We then propose both the global optimal scheduling scheme and distributed heuristic algorithm to optimize the system throughput. Furthermore, we introduce layered video coding into data-driven protocol and extend our algorithm to deal with the end-host heterogeneity. The results of simulation with the real world traces indicate that our distributed algorithm significantly outperforms conventional ad hoc scheduling strategies especially in stringent buffer and bandwidth constraints.     

Adaptive topology formation for peer-to-peer video streaming

In this paper we propose an adaptive P2P video streaming framework to address the challenges due to bandwidth heterogeneity and peer churn on the Internet. This adaptive streaming framework consists of two major components, source rate adaptation and adaptive overlay topology formation, to maximize the video quality and fully utilize the overall peer upload capacity. In the source rate adaptation, the video server adapts the video source rate automatically based on the local measurement of peers’ download rates, so that the P2P network is not overloaded beyond its bandwidth capacity and peers are able to achieve smooth video playback. To combat bandwidth heterogeneity, we propose to construct a desirable link-level homogeneous overlay topology using a Markov chain Monte Carlo method, so that peers achieve an equal per-connection upload/download bandwidth. In this link-level homogeneous network, video flows do not encounter any bottlenecks along the delivery paths, and peers achieve high download rates to ensure smooth video playback. We also design a fully distributed algorithm to implement the dual mechanisms of the adaptive topology formation and the source rate maximization. To evaluate the performance of our streaming framework, we conduct both mathematical analysis and extensive simulations. The simulation results confirm our analysis and show that the proposed distributed algorithm is able to maximize the video playback quality with fast convergence.     

On scalability of proximity-aware peer-to-peer streaming

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 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.     

Video Packet Selection and Scheduling for Multipath Streaming

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under network bandwidth and playback delay constraints. The streaming policy consists in a joint selection of the network path and of the video packets to be transmitted, along with their sending time. A simple streaming model is introduced, which takes into account the video packet importance, and the dependencies between packets. A careful timing analysis allows to compute the quality perceived by the receiver for a constrained playback delay, as a function of the streaming policy. We derive an optimization problem based on a video abstraction model, under the assumption that the server knows, or can predict accurately the state of the network. A detailed analysis of constrained multipath streaming systems provides helpful insights to design an efficient branch and bound algorithm that finds the optimal streaming strategy. This solution allows to bound the performance of any scheduling strategy, but the complexity of the algorithm becomes rapidly intractable. We therefore propose a fast heuristic-based algorithm, built on load-balancing principles. It allows to reach close to optimal performance with a polynomial time complexity. The algorithm is then adapted to live streaming scenarios, where the server has only a partial knowledge of the packet stream, and the channel bandwidth. Extensive simulations show that the proposed algorithm only induces a negligible distortion penalty compared to the optimal strategy, even when the optimization horizon is limited, or the rate estimation is not perfect. Simulation results also demonstrate that the proposed scheduling solution performs better than common scheduling algorithms, and therefore represents a very efficient low-complexity multipath streaming algorithm, for both stored and live video services     

P2P视频点播中的VCR方法综述

近几年,P2P视频点播技术得到了广泛的发展,使用P2P流媒体播放器(如PPStream、PPLive)来点播视频已经被广泛接受。但是,由于种种原因,用户在播放视频时进行快进、快退和跳转操作时,总是要等待一个比较长的时间,与用户在本地执行此操作的时间相差较大,因此用户得不到好的点播体验,同时也浪费带宽。为了解决这个问题,研究者们已经提出了许多关于提高VCR质量的方法,其中有被动式技术,也有主动式技术。被动的VCR技术主要是着眼于缩短对资源节点定位时间和从该资源节点下载资源的时间,同时提高节点保存资源节点信息的概率。主动的VCR技术主要是提高预存内容的概率和预存资源节点的信息的概率,同时缩短对资源节点定位的时间。本文将着重介绍这些方法的特征,并比较他们的优缺点,最后对VCR算法研究做出展望。     

User density sensitive P2P streaming in wireless mesh networks

Link rate allocation is very important for supporting high video playback rate in Peer-to-Peer video streaming. Although many studies can be found on resource allocation in P2P streaming in wired networks, very few studies have studied the problem in wireless networks, especially in Wireless multi-hop Mesh Networks (WMNs), which is still challenging. To maximize the users’ satisfaction of P2P streaming in WMNs, this paper focuses on link rate allocation problem and proposes a fully distributed algorithm to efficiently utilize the upload and download bandwidth of wireless mesh nodes. We first build an efficient P2P streaming system based on the experimental results from real deployment of our wireless mesh testbed. Then we design an efficient distributed algorithm based on the solution to a linear optimization model, which optimizes towards a user-density-related objective to decide the best streaming rates among peers. Our scheme is resilient to network dynamics that is characteristic in wireless multi-hop peer-to-peer networks. The simulation experiments demonstrate the significant performance enhancement by using the proposed rate allocation algorithm in WMNs.     

An efficient scheduling algorithm for scalable video streaming over P2P networks

During recent years, the Internet has witnessed rapid advancement in peer-to-peer (P2P) media streaming. In these applications, an important issue has been the block scheduling problem, which deals with how each node requests the media data blocks from its neighbors. In most streaming systems, peers are likely to have heterogeneous upload/download bandwidths, leading to the fact that different peers probably perceive different streaming quality. Layered (or scalable) streaming in P2P networks has recently been proposed to address the heterogeneity of the network environment. In this paper, we propose a novel block scheduling scheme that is aimed to address the P2P layered video streaming. We define a soft priority function for each block to be requested by a node in accordance with the block’s significance for video playback. The priority function is unique in that it strikes good balance between different factors, which makes the priority of a block well represent the relative importance of the block over a wide variation of block size between different layers. The block scheduling problem is then transformed to an optimization problem that maximizes the priority sum of the delivered video blocks. We develop both centralized and distributed scheduling algorithms for the problem. Simulation of two popular scalability types has been conducted to evaluate the performance of the algorithms. The simulation results show that the proposed algorithm is effective in terms of bandwidth utilization and video quality.     

Modeling and generating realistic streaming media server workloads

Currently, Internet hosting centers and content distribution networks leverage statistical multiplexing to meet the performance requirements of a number of competing hosted network services. Developing efficient resource allocation mechanisms for such services requires an understanding of both the short-term and long-term behavior of client access patterns to these competing services. At the same time, streaming media services are becoming increasingly popular, presenting new challenges for designers of shared hosting services. These new challenges result from fundamentally new characteristics of streaming media relative to traditional web objects, principally different client access patterns and significantly larger computational and bandwidth overhead associated with a streaming request. To understand the characteristics of these new workloads we use two long-term traces of streaming media services to develop MediSyn, a publicly available streaming media workload generator. In summary, this paper makes the following contributions: (i) we propose a framework for modeling long-term behavior of network services by capturing the process of file introduction, non-stationary popularity of media accesses, file duration, encoding bit rate, and session duration. (ii) We propose a variety of practical models based on the study of the two workloads. (iii) We develop an open-source synthetic streaming service workload generator to demonstrate the capability of our framework to capture the models.     

一种面向线性相关冗余优化的源节点选择算法

基于网络编码的P2P流媒体直播系统的优势之一在于多个源节点之间不需要显式的协同调度也能有效地服务于请求节点。但正是由于缺乏协同,即使编码系数的有限域足够大,仍然存在线性相关冗余数据,从而浪费了源节点的带宽。分析了这一问题产生的原因,并提出采用从tracker提供的源节点集合中选择部分节点作为活动源节点来解决该问题。活动源节点最优选择问题可以归约为0-1背包问题的变种,是NP难的,因此我们设计了一个多项式时间的近似算法来逼近最优解。通过形式化证明和模拟,我们验证了该算法的可行性。数据表明该方法能够进一步提高P2P流媒体直播系统的服务质量。     

Proxy caching for peer-to-peer live streaming

Peer-to-Peer (P2P) live streaming has become increasingly popular over the Internet. To alleviate the inter-ISP traffic load and to minimize the access latency, proxy caching has been widely suggested for P2P applications. In this paper, we carry out an extensive measurement study on the properties of P2P live streaming data requests. Our measurement demonstrates that the P2P living streaming traffic exhibits strong localities that could be explored by caching. This is particularly noticeable for the temporal locality, which is often much weaker in the conventional P2P file sharing applications. Our results further suggest that the request time of the same data piece from different peers exhibits a generalized extreme value distribution. We then propose a novel sliding window (SLW)-based caching algorithm, which predicts and caches popular data pieces according to the measured distribution. Our experimental results suggest that the P2P live streaming can greatly benefit from the proxy caching. And, with much lower overhead, our SLW algorithm works closer to an off-line optimal algorithm that holds the complete knowledge of future requests.     

基于遗传算法的P2P流媒体多播模型

为解决P2P流媒体通信中的流量控制问题，给出一个P2P社区覆盖多播通信优化模型及其建立覆盖核心多播树OCMT的QoS约束条件，并采用一个面向目标的遗传算法解决建立OCMT中的路径优化问题。仿真实验结果表明该模型能为建立具有低延迟和强扩展能力的核心多播树获得较优化的方案，并且有效地降低不同P2P社区间的数据流量，实现控制Internet流量的目的。     

Resource allocation for multimedia streaming over the Internet

This paper addresses the resource allocation problem for multiple media streaming over the Internet. First, we present an end-to-end transport architecture for multimedia streaming over the Internet. Second, we propose a new multimedia streaming TCP-friendly protocol (MSTFP), which combines forward estimation of network conditions with information feedback control to optimally track the network conditions. Third, we propose a novel resource allocation scheme to adapt media rate to the estimated network bandwidth using each media's rate-distortion function under various network conditions. By dynamically allocating resources according to network status and media characteristics, we improve the end-to-end quality of services (QoS). Simulation results demonstrate the effectiveness of our proposed schemes     

CoreCast: How core/edge separation can help improving inter-domain live streaming

The rapid growth of broadband access has popularized multimedia services, which nowadays contribute to a large part of Internet traffic. Among this content, the broadcasting of live events requires streaming from a single source to a large set of users. For such content, network-layer multicast is the most efficient solution, but it has not found wide-spread adoption due to its high deployment cost. As a result, several application-layer solutions have been proposed based on large-scale P2P systems. These solutions however, are unable to provide a satisfactory quality of experience to all users, mainly because of the variability of the peers and their limited upload capacity. In this paper we advocate for a network-layer solution that circumvents the prohibitive deployment costs of previous approaches, taking advantage of the rare window of opportunity offered by the locator/identifier separation protocol (LISP). This new architecture, motivated by the alarming growth rate of the default-free zone (DFZ) routing table, is developed within the IETF, and aims to upgrade the current inter-domain routing system. We present CoreCast, an efficient inter-domain live streaming architecture operating on top of LISP. LISP involves upgrading some Internet routers and our proposal can be introduced along with these new deployments. To evaluate its feasibility in terms of processing overhead in networking equipment we have implemented CoreCast in the Linux kernel. Further, we compare the performance of CoreCast to the popular P2P streaming services both analytically and experimentally. The results show that CoreCast reduces inter-domain bandwidth consumption and that introduces negligible processing overhead in network equipment.     

分组交换网络中分布式调度控制算法研究

文章首先对目前分组交换网络中支持QoS的队列调度算法进行了比较研究,分析了其性能指标和技术特点。然后以Internet核心路由器中线卡级和交换级的队列调度设计为例,从控制论的角度提出了一种支持QoS的分布式加权轮询调度控制算法,同时对交换网络进行了仿真实验,吞吐率达到96％的仿真实验结果表明所提出的算法是有效的,最后,文章认为在实际应用中,应针对不同情况设计不同的调度控制算法,以便在复杂性、公平性、快速性及有效性等特性方面取得了一个折衷方案,以使分组交换网络的整体性能更好。     

基于流媒体相关的视频安全组播协议(MSMP)研究

随着无线网络的快速发展和Internet中流媒体视频的巨大成功,无线网络中的视频服务有望在不久的将来得到大规模部署,无线网络上的实时流媒体传输技术已成为研究热点,而其中视频安全组播协议是一个关键问题。但是,由于无线网络中有限的带宽和有限的存储空间,外部的攻击与自适应机制带来的安全性问题在无线流媒体视频中是不可避免的。一个精心设计的密钥管理算法不仅可以明显地提高流媒体视频的性能,还能够保证可靠的数据嵌入以及实时视频应用提供安全支持。如何设计一个高效的密钥管理算法,是当前流媒体视频应用中一个备受关注的问题。针对无线视频应用,针对一个处于开放和不安全的网络环境中的自适应视频应用的密钥管理算法进行了研究,并进行了算法评价。     

A moving switching sequence approach for nonlinear model predictive control of switched systems with state‐dependent switches and state jumps

In this paper, we propose an approach for real‐time implementation of nonlinear model predictive control (NMPC) for switched systems with state‐dependent switches called the moving switching sequence approach. In this approach, the switching sequence on the horizon moves to the present time at each time as well as the optimal state trajectory and the optimal control input on the horizon. We assume that the switching sequence is basically invariant until the first predicted switching time reaches the current time or a new switch enters the horizon. This assumption is reasonable in NMPC for systems with state‐dependent switches and reduces computational cost significantly compared with the direct optimization of the switching sequence all over the horizon. We update the switching sequence by checking whether an additional switch occurs or not at the last interval of the present switching sequence and whether the actual switch occurs or not between the current time and the next sampling time. We propose an algorithm consisting of two parts: (1) the local optimization of the control input and switching instants by solving the two‐point boundary‐value problem for the whole horizon under a given switching sequence and (2) the detection of an additional switch and the reconstruction of the solution taking into account the additional switch. We demonstrate the effectiveness of the proposed method through numerical simulations of a compass‐like biped walking robot, which contains state‐dependent switches and state jumps.     

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

A sliding-window k-NN query (k-NN/w query) continuously monitors incoming data stream objects within a sliding window to identify k closest objects to a query. It enables effective filtering of data objects streaming in at high rates from potentially distributed sources, and offers means to control the rate of object insertions into result streams. Therefore k-NN/w processing systems may be regarded as one of the prospective solutions for the information overload problem in applications that require processing of structured data in real-time, such as the Sensor Web. Existing k-NN/w processing systems are mainly centralized and cannot cope with multiple data streams, where data sources are scattered over the Internet. In this paper, we propose a solution for distributed continuous k-NN/w processing of structured data from distributed streams. We define a k-NN/w processing model for such setting, and design a distributed k-NN/w processing system on top of the Content-Addressable Network (CAN) overlay. An extensive evaluation using both real and synthetic data sets demonstrates the feasibility of the proposed solution because it balances the load among the peers, while the messaging overhead within the P2P network remains reasonable. Moreover, our results clearly show the solution is scalable for an increasing number of queries and peers.