單樹與多樹架構之串流機制的研究與分析

Abstract

本篇論文提出一套單樹(single-tree)與多樹(multiple-tree)架構之串流機制的效能分析模型以及一套樹狀串流架構的選擇演算法。我們針對視訊會議(video conferencing)的多個來源(multiple sources)、無伺服器(serverless)且樹狀串流架構(tree-based streaming)的應用情境來進行分析。透過分析影響影像串流(video streaming)表現的三項因素(metrics): 頻寬(bandwidth)、延遲(delay)和同步(synchronization)，對樹狀串流提出新的分析模組與演算法，將影響因素模組化，且設計生成單樹與多樹架構及計算其延遲長短的演算法。 首先，我們對單樹與多樹串流系統所需消耗的頻寬進行分析，得知單樹與多樹架構對於頻寬需求的差異性，然而，因為我們假設系統上的每個參與者都擁有足夠的下載頻寬接收影像，所以我們更有興趣的是上傳頻寬的需求，經過分析得到單樹架構整體所需消耗的上傳頻寬大於多樹架構。其次，在分析延遲因素上，因為兩串流系統的運作方式不同，單樹需考慮上傳與下載延遲的問題，而多樹則僅考慮系統上每棵樹的上傳延遲的問題。最後，在分析同步因素上，單樹的影像同步問題是集中在擁有最大上傳頻寬的參與者處理，多樹的影像同步問題則是每個參與者各自處理。 依前面的分析為基礎進行頻寬與延遲的模組化，然而，我們在論文中將同步的overhead視為一種延遲，故將同步因素併入，與延遲因素一起做延遲模組化。對於頻寬的模組化，以分析建構兩串流架構整體所需消耗的上傳頻寬為基礎，進一步探討樹狀架構的組成；對於單樹系統而言，利用加總每個參與者可以將影像傳送給幾個其他參與者的最大個數值來判斷是否可以成功建構單樹架構。對於多樹系統而言，加總每個參與者所擁有的上傳頻寬，而此結果滿足建構多樹所需的上傳頻寬，所以多樹架構可以成功被建構。對於延遲的模組化，以頻寬模組所建構出樹狀串流架構為依據，由於同步因素已被視為一種延遲，所以會以有無加入同步因素分別探討單樹與多樹整體系統的延遲。 此外，為了驗證本論文提出的分析模組與設計的演算法，我們運用程式模擬得到實驗數據，進一步綜合分析與模擬的比較結果，以表現因素(performance metrics)的條件狀況為根基，歸納出一套選擇單樹或多樹進行影像串流分配，其會有較好傳輸表現的結果。

In this thesis, we propose a performance analytical model for single-tree and multiple-tree streaming mechanisms and an algorithm to determine if a single-tree or multiple-tree structure should be used according to these analysis results. Our analytical model targets multiple sources, server-less, and tree-based streaming for video conferencing application. Through analyzing and modeling three performance metrics of video streaming, such as bandwidth, delay, and synchronization, and according to our analyses of tree-based streaming, we embody these models and design the algorithms for spanning tree and calculation of maximum delay. First, in regards to analysis of bandwidth, we discuss bandwidth requirement for single-tree and multiple-tree. We need to identify the required bandwidth to send all streams and differences between single-tree and multiple-tree. However, since we assume that each peer with sufficient bandwidth receives the streams directly or indirectly from other peers, we are interested in uploading bandwidth requirement. Through analyzing, the total upload bandwidth requirement of single-tree is larger than that of multiple-tree. Second, in analysis of delay, operation of single-tree is different from multiple-tree. Single-tree must be considered upload and download delay, and multiple-tree just is considered upload delay of each tree. Finally, in analysis of synchronization, in the single-tree system, a participant with the maximum upload bandwidth serves as a centralized multipoint control unit (MCU) who deals with synchronization. In a multiple-tree system, each participant deals with its own synchronization. Bandwidth and delay modeling are based on our analyses. Nevertheless, since we regard overhead of synchronization as a kind of delay in our thesis, we integrate synchronization into delay to create delay modeling. We accord with our analyses of total upload bandwidth requirement for single-tree and multiple-tree streaming to do bandwidth modeling and realize their tree-based formations. Single-tree formation can be successfully constructed based on the total maximum number of receivers for each participant streaming. Multiple-tree can be constructed successfully because the total upload bandwidth is sufficient for multiple-tree streaming. Our delay models depend on the tree-based formations for design. We do delay modeling both with and without synchronization. Moreover, in order to verify the reasonability of our analytical model and proposed algorithm, we use a series of simulations. Furthermore, for single-tree and multiple-tree, we make the comparison between results of analyses and simulations to conclude what conditions of metrics have better performance. Based on conditions of performance metrics, we can determine which (single-tree or multiple-tree) is better suited for transmitting streams.