請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35021
標題: | 多媒體網路群播演算法 Multicasting Algorithms in Multimedia Networks |
作者: | Hsu-Chen Cheng 鄭旭成 |
指導教授: | 林永松 |
關鍵字: | 群播網路,多重速率群播,多階層編碼技術,史坦那樹,允入控制,網路規劃,拉格蘭日鬆弛法,數學規劃,網路最佳化, Multicast Network,Multi-rate Multicasting,Layered encoding,Steiner Tree,Call Admission Control,Network Planning,Lagrangean Relaxation,Mathematical Modeling,Optimization, |
出版年 : | 2005 |
學位: | 博士 |
摘要: | 隨著近年來傳輸與編碼技術的發展,有愈來愈多的多媒體應用被推出並廣泛使用,例如視訊會議與隨選視訊。大部份這些應用都需要大量的頻寬來同步傳輸多媒體資訊給許多的使用者,其中可能最有效率的方式就是透過群播網路來達到這個目標。在多媒體傳輸的環境中,由於使用者可能使用不同的傳輸技術與網際網路進行連接(例如撥接數據機、Cable modem或者xDSL…等),並且不同使用者對於品質的需求亦不相同。因為網路頻寬與使用者需求之差異,如何透過良好的設計架構與傳輸機制,有效率的利用頻寬並達到服務的彈性是個重要的研究議題。
由於高階視訊編碼技術與視訊閘道器的推出,當不同的使用者向傳輸端要求不同的品質視訊時,傳輸端只要將滿足最高頻寬需求的視訊,透過單一群播樹傳輸進行傳輸即可,這種群播技術稱為階層編碼群播技術或者多重速率群播技術。單一速率最小成本群播樹的問題就是大家熟知支史坦那樹問題,這是一個NP-Complete的問題,而多重速率群播樹問題將是比史坦那樹更複雜的問題。 在此論文中,我們將針對單一速率與多重速率群播樹之路由問題進行探討,使用數學模型來描述此類網路規劃與網路運作問題,並使用拉格蘭日鬆弛法作為基礎,以最佳化的方式提出適合的演算法。本論文的研究內涵與成果簡述如下: *最小成本多重速率群播路由問題:同時考慮路由決策與多重群播技術下每個鏈結上所應傳輸之資料量,以求得最小成本傳輸群播樹。我們成功的將此問題以數學模型進行描述,並提出以最佳化為基礎的演算法。根據實驗的結果顯示,我們所提出的演算法較之前相關研究所提出之演算法優越。此外,我們亦針對在網路鏈結有容量限制下的多群組群播問題進行研究,並提出相關的演算法。 *單一速率與多重速率群播允入控制研究:傳統的演算法在計算是否允入群播群組時是以整個群組為單位,在此我們提出群組部分允入的作法來求得最大收入之群播路由指定與資源預留機制。所謂的部份允入是指在無法允入全部群播群組內之使用者時,系統會以最大收入為目標嘗試對於群組內的部份使用者提供服務,以充分使用網路資源並最大化系統營收。此外,我們也從長期收益最大化的觀點,提出及時性的群播允數控制機制,並針對允入控制決策時間與系統負載流量之間的關係進行研究。我們所提出的演算法分別在單一速率群播與多重速率群播上可達到186%與905%的改善。 *考慮使用行為之最小成本群播樹研究:在既定的群播群組成員中,由於使用者並不一定全時的在接收傳輸端的資訊,其接收的行為可以以機率來表示。若考慮使用者是否正在接收的行為,傳統的最小成本樹演算法並無法有效率的被應用。因此我們將此問題以數學模式來表示,並提出最佳化的演算法。根據實驗的結果,我們的演算法較傳統的最小成本數演算法可改善達到38%。 論文的最後,我們提出五個未來重要的延續研究議題,並根據本論文的研究成果明確地提出這些問題之數學模式供後續學者進行研究。這些議題包括:最小成本多速率多群播樹問題、最大使用者滿意度之多速率多群播樹問題、最大利潤多速率群播樹問題、考慮重新路由之多速率群播樹問題與考慮次群組行為之群播問題。 Based on recent developments in transmission and computing technologies, multimedia applications, such as the teleconferencing and video on demand, have already become achievable and are comprehensively and widely used. Nevertheless, most of these applications require a large amount of bandwidth to deliver multimedia information to multiple destinations simultaneously. One possible way to meet this requirement is via multicasting. Multimedia application environments are characterized by large bandwidth variations due to the heterogeneous access technologies of networks (e.g. analog modem, cable modem, xDSL, and wireless access etc.) and different receivers’ quality requirements. In video multicasting, the heterogeneity of the networks and destinations makes it difficult to achieve bandwidth efficiency and service flexibility. There are many challenging issues that need to be addressed in designing architectures and mechanisms for multicast data transmission. Taking advantage of recent advances in video encoding and transmission technologies, either by a progress coder or video gateway, different destinations can request a different bandwidth requirement from the source. The source then only needs to transmit signals that are sufficient for the highest bandwidth destination into a single multicast tree. In this dissertation, we study several multicast routing problems, which belong to both single-rate and multi-rate categories. Mathematical formulations are used to model the planning and operational problems, and Lagrangean relaxation techniques, based on the proposed mathematical formulations, are adopted to solve the network planning and operational problems. The scope and contributions of this dissertation are highlighted by the following. For the min-cost multirate multicasting routing problem, we propose some heuristics to jointly determine the following decision variables: (1) the routing assignment; and (2) the maximum allowable traffic rate of each multicast user group through each link. We successfully model the traffic flow on the links for multi-rate multicasting, and the proposed optimization-based heuristic outperform than the heuristic proposed in the earlier researches. We also deal with the multi-group multicasting planning problem with a capacity constraint. We also consider the call admission control issues for the single-rate and multi-rate multicasting. We consider the problem of maximum-revenue routing with a partial admission control mechanism. The mechanism means that the admission policy of a multicast group is not based on a traditional “all or none” strategy. Instead it considers accepting partial destinations for the requested multicast group. For a given network topology, a given link capacity, destinations of a multicast group, and the bandwidth requirement of each destination, we attempt to find a feasible routing solution to execute call admission control and apply resource reservation to maximize the revenue of the multicast trees. In addition, we propose a real-time model to deal with long term revenue analysis. The improvement is up to 186% better than the simple algorithm in single-rate transmission, and 905% in multi-rate transmission. Furthermore, we address the problem of constructing a minimum cost multicast tree by considering dynamic user membership. The motivation of this is to create a mechanism for finding and evaluating the cost-efficiency of a multicast tree with a given network and a fixed set of group members. Unlike other minimum cost multicast tree algorithms, this problem consists of one multicast group of fixed members, where each destination member is dynamic and has a probability of being active, which is observed over some period of time. The improvement of our proposed algorithm is up to 38%. Finally, we point out five challenging issues to be tackled in the future. We also proposed some feasible mathematical models to formulate these problems. These models are based on the research results of the dissertation. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/35021 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 2.33 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。