Multicasting Algorithms in Multimedia Networks

隨著近年來傳輸與編碼技術的發展，有愈來愈多的多媒體應用被推出並廣泛使用，例如視訊會議與隨選視訊。大部份這些應用都需要大量的頻寬來同步傳輸多媒體資訊給許多的使用者，其中可能最有效率的方式就是透過群播網路來達到這個目標。在多媒體傳輸的環境中，由於使用者可能使用不同的傳輸技術與網際網路進行連接(例如撥接數據機、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.CHAPTER 1 INTRODUCTION 1 1.1 OVERVIEW 1 1.2 RESEARCH SCOPE 3 CHAPTER 2 RESEARCH BACKGROUND 8 2.1 QOS ROUTING 8 2.2 QOS MULTICASTING 13 2.3 MULTIRATE MULTICASTING 18 2.5 LAGRANGEAN RELAXATION METHOD 25 2.6 NETWORK TOPOLOGIES FOR EXPERIMENTS AND SIMULATIONS 29 CHAPTER 3 MINIMUM-COST MULTIRATE MULTICASTING ROUTING PROBLEM 33 3.1 OVERVIEW 33 3.2 HEURISTICS OF MULTIRATE MULTIMEDIA MULTICASTING 36 3.2.1 Some Scenarios of the Modified T-M Heuristic 37 3.2.2 Enhanced Modified T-M Heuristic 39 3.3 THE MODEL 40 3.3.1 Problem Description 40 3.3.2 Mathematical Formulation 41 3.4 SOLUTION APPROACH 43 3.4.1 Lagrangean Relaxation 43 3.4.2 Getting Primal Feasible Solutions 46 3.5 COMPUTATIONAL EXPERIMENTS 47 3.6 CONCLUDING REMARKS 50 CHAPTER 4 CAPACITATED MINIMUM-COST MULTIRATE MULTICAST ROUTING PROBLEM 51 4.1 OVERVIEW 51 4.2 A SIMPLE HEURISTIC FOR LINK CONSTRAINED MULTIRATE MULTIMEDIA MULTICASTING 52 4.3 PROBLEM FORMULATION 53 4.3.1 Problem Description 53 4.3.2 Mathematical Formulation 55 4.4 SOLUTION APPROACH 56 4.4.1 Lagrangean Relaxation 56 4.4.2 Getting Primal Feasible Solutions 60 4.5 EXPERIMENTAL RESULTS 61 4.6 CONCLUDING REMARKS 64 CHAPTER 5 THE PARTIAL ADMISSION CONTROL PROBLEM OF SINGLE-RATE MULTICASTING 65 5.1 OVERVIEW 65 5.2 PROBLEM FORMULATION 66 5.3 SOLUTION PROCEDURE 70 5.3.1 Lagrangean relaxation 70 5.3.2 Getting primal feasible solutions 72 5.4 COMPUTATIONAL EXPERIMENTS 74 5.5 REAL-TIME ADMISSION CONTROL 77 5.5.1 A Real-time LR-based CAC algorithm 79 5.5.2 Performance metrics 81 5.5.3 Simulation Results 82 5.6 CONCLUDING REMARKS 95 CHAPTER 6 THE PARTIAL ADMISSION CONTROL PROBLEM OF MULTIRATE MULTICASTING 96 6.1 INTRODUCTION 96 6.2 PROBLEM FORMULATION 97 6.3 SOLUTION PROCEDURE 100 6.3.1 Lagrangean relaxation 100 6.3.2 Getting primal feasible solutions 103 6.4 COMPUTATIONAL EXPERIMENTS 105 6.5 REAL-TIME PARTIAL ADMISSION CONTROL FOR MULTIRATE MULTICASTING 108 6.5.1 A Real-time LR-based CAC algorithm 108 6.5.2 Performance metrics 109 6.5.3 Simulation Results 110 6.6 CONCLUDING REMARKS 122 CHAPTER 7 MINIMUM-COST MULTICAST ROUTING PROBLEM WITH THE CONSIDERATION OF DYNAMIC USER MEMBERSHIP 124 7.1 OVERVIEW 124 7.2 PROBLEM FORMULATION 126 7.2.1 Problem Description 126 7.2.2 Mathematical Formulation 127 7.3 SOLUTION APPROACH 128 7.3.1 Lagrangean Relaxation 128 7.3.2 Getting Primal Feasible Solutions 131 7.4 COMPUTATIONAL EXPERIMENTS 132 CHAPTER 8 CONCLUSION AND FUTURE WORK 136 8.1 SUMMARY 136 8.2 FUTURE WORK 137 8.2.1 Min-Cost Multi-tree Multirate Multicast Problem 137 8.2.2 Max-Revenue Multi-tree Multirate Multicast Problem 140 8.2.3 Max-Profit Multirate Multicast Problem 143 8.2.4 Routing Algorithms Considering Multirate Multicast Service and Traffic Rerouting 147 8.2.5 Considering Subgroup Behavior 151 REFERENCES 15