In the recent decade, peer-to-peer (P2P) technology has greatly enhanced the scalability of multimedia streaming on the Internet by enabling efficient cooperation among end-users. However, existing streaming applications are plagued by the problems of long playback latency and long churn-induced delays. First of all, many streaming applications, such as IPTV and video conferencing, have rigorous constraints on end-to-end delays. Moreover, churn-induced delays, including delays from channel switching and streaming recovery, in current P2P streaming applications are typically in the scale of 10-60 seconds, which is far below the favorable user experience as in cable TV systems. These two issues in terms of playback latency and churn-induced delays have hindered the extensive commercial deployment of P2P systems. Motivated by this, in this dissertation, we focus on reducing delays in P2P live streaming systems. Specifically, we propose solutions for reducing delays in P2P live streaming systems in four problem spaces: (1) minimizing the maximum end-to-end delay in P2P streaming; (2) minimizing the average end-to-end delay in P2P streaming; (3) minimizing the average delay in multi-channel P2P streaming; and (4) reducing churn-induced delays. We devise a streaming scheme to minimize the maximum end-to-end streaming delay under a mesh-based overlay network paradigm. We call this problem, the MDPS problem. We formulate the MDPS problem and prove its NP-completeness. We then present a polynomial-time approximation algorithm, called Fastream-I, for this problem, and show that the performance of Fastream-I is bounded by a ratio of O(SQRT(log n)), where n is the number of peers in the system. We also develop a distributed version of Fastream-I that can adapt to network dynamics. Our simulation study reveals the effectiveness of Fastream-I, and shows a reasonable message overhead. While Fastream-I yields the minimum maximum end-to-end streaming delay (within a factor of O(SQRT(log n)), in many P2P settings, users may desire the minimum average end-to-end P2P streaming delay. Towards this, we devise a streaming scheme which optimizes the bandwidth allocation to achieve the minimum average end-to-end P2P streaming delay. We call this problem, the MADPS problem. We first develop a generic analytical framework for the MADPS problem. We then present Fastream-II as a solution to the MADPS problem. The core part of Fastream-II is a fast approximation algorithm, called APX-Fastream-II, based on primal-dual schema. We prove that the performance of APX-Fastream-II is bounded by a ratio of 1+w, where w is an adjustable input parameter. Furthermore, we show that the flexibility of w provides a trade-off between the approximation factor and the running time of Fastream-II. The third problem space of the dissertation is minimizing the average delay in multi-channel P2P streaming systems. Toward this, we present an algorithm, called Fastream-III. To reduce the influence from frequent channel-switching behavior, we build Fastream-III for the view-upload decoupling (VUD) model, where the uploaded content from a serving node is independent of the channel it views. We devise an approximation algorithm based on primal-dual schema for the critical component of Fastream-III, called APX-Fastream-III. In contrast to APX-Fastream-II, APX-Fastream-III addresses the extra complexity in the multichannel scenario and maintains the approximation bound by a ratio of 1+w. Besides playback lag, delays occurring in P2P streaming may arise from two other factors: node churn and channel switching. Since both stem from the re-connecting request in churn, we call them churn-induced delays. Optimizing churn-induced delays is the dissertation's fourth problem space. Toward this, we propose NAP, a novel agent-based P2P scheme, that provides preventive connections to all channels. Each channel in NAP selects powerful peers as agents to represent the peers in the channel to minimize control and message overheads. Agents distill the bootstrapping peers with superior bandwidth and lifetime expectation to quickly serve the viewer in the initial period of streaming. We build a queueing theory model to analyze NAP. Based on this model, we numerically compare NAP's performance with past efforts. The results of the numerical analysis reveal the effectiveness of NAP. / Ph. D.

In this paper, we propose two schemes for layer allocations to adjust the number of layers of SVC (Scalable Video Coding) segments according to the bandwidth variation in P2P video streaming networks. The first scheme is Periodical Layer Allocation (PLA) that can adjust the number of layers to fully satisfy the available bandwidth measured periodically. However, when the available bandwidth is changed abruptly, two major drawbacks may be occurred by PLA algorithm; first, the quality of video frames may become unsmooth so that users would feel uncomfortable about the picture quality, and second, the cost is increased due to the periodical measurement of the available bandwidth. Therefore, we propose Dynamic Layer Allocation (DLA), to dynamically change the time interval for adjusting SVC layers. When freeze-up occurred or when there was not enough buffer space to store the video segments during the interval, the interval would be reduced. When the interval for adjusting SVC layers was expired, available bandwidth can be determined by the number of video segments waiting in the buffer. Compared with PLA, DLA adjusts the SVC layers gracefully so that the quality of picture becomes smoother and users feel more comfortable while watching the film. We built a simulator written in C++ under two scenarios: the available bandwidth is changed abruptly and the one changed gradually. Simulation results show that the performance of PLA is quite similar to DLA when the available bandwidth is changed gradually. However, when the available bandwidth is changed abruptly, DLA can not only obtain the smoother video film but also decrease the freeze-up time significantly.

O desenvolvimento da Internet motivou o surgimento de inúmeras aplicações que utilizam sua infra-estrutura. Dentre elas destacam-se as aplicações P2P para a transmissão de streamings de voz/vídeo. Essas aplicações exigem que determinados requisitos como largura de banda, latência, variação de atraso, escalabilidade, disponibilidade, entre outros, sejam satisfeitos para que possa haver qualidade no serviço provido (QoS Quality of Service). Satisfazer a todos esses requisitos torna-se um grande desafio quando é utilizada a infra-estrutura da Internet para transmissão. Deste modo, impulsionado pelo grande atrativo que existe no paradigma P2P, assim como todos os desafios por trás dessa abordagem, o objetivo principal deste trabalho é a proposta de um protocolo para a construção de overlays para a distribuição de streamings de vídeo em redes P2P. O protocolo proposto visa garantir que o overlay a ser empregado na distribuição de streamings seja construído, levando-se em consideração as características da rede física (nesse trabalho, a Internet) sob o mesmo. A idéia fundamental deste protocolo é organizar os pares de forma dinâmica, agrupando aqueles que estão mais próximos em termos de latência. O segundo objetivo a ser alcançado neste trabalho é a validação do protocolo por meio de experimentos (prova de conceito) realizados com o PlanetLab, de modo a validar os mecanismos propostos. / The Internet development has leveraged several kinds of application that depends on its infrastructure, such as P2P applications to voice/video streaming transmission. These applications have a plenty of requirements, such as bandwidth, latency, jitter, scalability, availability, and so on, that should be fulfilled in order to achieve the required level of Quality of Service (QoS). When it is used the Internet infrastructure to transmission, it is a great challenge fulfill all these requirements. In this manner, the main goal of this work is to propose a protocol to build an overlay to distribute video streaming in P2P networks, taking into account the network characteristics. The fundamental idea of this protocol is dynamically organize the peers, gathering these peers considering the latency between them. Another goal of this work is the protocol assessment by means of experiments (proof of concept) performed in PlanetLab, in order to verify the proposed mechanisms.

O desenvolvimento da Internet motivou o surgimento de inúmeras aplicações que utilizam sua infra-estrutura. Dentre elas destacam-se as aplicações P2P para a transmissão de streamings de voz/vídeo. Essas aplicações exigem que determinados requisitos como largura de banda, latência, variação de atraso, escalabilidade, disponibilidade, entre outros, sejam satisfeitos para que possa haver qualidade no serviço provido (QoS Quality of Service). Satisfazer a todos esses requisitos torna-se um grande desafio quando é utilizada a infra-estrutura da Internet para transmissão. Deste modo, impulsionado pelo grande atrativo que existe no paradigma P2P, assim como todos os desafios por trás dessa abordagem, o objetivo principal deste trabalho é a proposta de um protocolo para a construção de overlays para a distribuição de streamings de vídeo em redes P2P. O protocolo proposto visa garantir que o overlay a ser empregado na distribuição de streamings seja construído, levando-se em consideração as características da rede física (nesse trabalho, a Internet) sob o mesmo. A idéia fundamental deste protocolo é organizar os pares de forma dinâmica, agrupando aqueles que estão mais próximos em termos de latência. O segundo objetivo a ser alcançado neste trabalho é a validação do protocolo por meio de experimentos (prova de conceito) realizados com o PlanetLab, de modo a validar os mecanismos propostos. / The Internet development has leveraged several kinds of application that depends on its infrastructure, such as P2P applications to voice/video streaming transmission. These applications have a plenty of requirements, such as bandwidth, latency, jitter, scalability, availability, and so on, that should be fulfilled in order to achieve the required level of Quality of Service (QoS). When it is used the Internet infrastructure to transmission, it is a great challenge fulfill all these requirements. In this manner, the main goal of this work is to propose a protocol to build an overlay to distribute video streaming in P2P networks, taking into account the network characteristics. The fundamental idea of this protocol is dynamically organize the peers, gathering these peers considering the latency between them. Another goal of this work is the protocol assessment by means of experiments (proof of concept) performed in PlanetLab, in order to verify the proposed mechanisms.

無線網狀網路(WMNs)為目前熱門的廣域無線網路接取技術。使用者可以透過WMNs隨時在各處使用即時影音播放的服務。相較於傳統的主從式架構，低成本且容易建置的點對點架構更適用於影音串流的應用；在進行即時影音播放的時候，影音播放的品質便為相當重要的目標。因為多媒體應用服務對於延遲及網路傳輸效能相當敏感，且WMNs的傳輸過程中常會面臨同頻道干擾的問題而使得傳輸的效能銳減，當每個網路節點都具有多張無線網路卡時，如何善用WMNs多頻道傳輸的特性提升效能更是顯得特別重要。在本篇論文中，我們利用WMNs多頻道傳輸的特性進行多媒體群播傳輸，參考史坦納樹的概念來改善現有的MAODV路由演算法，以傳輸品質較佳的鏈結改良原本尋找最小跳躍數路徑的方式，建立兩棵完全互斥的群播樹作為點對點傳輸的骨幹網路，並以MDC的概念將影像串流編碼成兩份獨立的子串流分別經由不同的群播樹傳輸。經實驗評估，我們的方法在網路負載較高的環境下能有效的降低延遲並提高整體系統的效能。 / In WMNs, users can enjoy the real-time video streaming service anytime and anywhere through the services. Compared to the client/server model, P2P approaches is more suitable for video streaming applications because of its low cost and easy deployment. But when using the real-time multimedia service in WMNs, the multimedia applications are very sensitive to delay time and the performance of packets transmission. And the performance is significantly influenced by the co-channel interference, so that it is important to know how to transmit by multi-channel to enhance the performance. In our approach, we choose the better quality links for routing instead of the minimum hop-count path in MAODV. Then we distribute the video streaming to receivers by multicast in multi-channel WMNs, and refer to the Steiner tree concept to modify the MAODV routing protocol to construct two disjoint multicast trees as the backbone for the P2P structure. Therefore, we can adopt the MDC scheme to encode the video into two independent sub-streams and transmit separately along these trees. Experiment results show that in higher network traffic load environment, our scheme is more effective to reduce the latency and improve overall system performance.