廖婉君臺灣大學：電機工程學研究所楊得年Yang, De-NianDe-NianYang2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53419目前群播服務仍無法普及的一個主要原因便是目前群播機制缺乏擴充性。因此，網路無法支援釵h群播群組，且一個群組無法支援很多個成員。目前群播機制缺乏擴充性的原因可分為兩點。第一，目前的群播協定要求路由器必須記錄群播傳送狀態。因此，路由器需記錄釵h傳送狀態，且群播傳送狀態在路由器之間的分配極不平均。故路由器在傳送每一個封包時，均需花費釵h時間來找出其所需要的群播傳送狀態。此外，路由器需配置釵h記憶體來儲存所需之群播傳送狀態。第二，目前的群播路由協定所使用的群播路由樹使用大量的網路頻寬，使得網路無法擁有足夠頻寬來支援大量群播群組。 在本篇論文中，我們提出兩個機制來分別解決前述兩點問題。我們首先提出一個新的群播遞送機制，其可有效減少每個路由器所需記錄的群播傳送狀態數量，並使得群播傳送狀態在路由器之間的分配較為平均。接著我們提出一個新的群播傳送及路由機制，其使用較少的網路頻寬。此二機制可讓網路支援較多的群播群組，且讓每個群組支援較多的成員。 在此二機制中，我們採用一個新的群播遞送機制：指定位址群播技術。由於此機制和之前群播技術完全不同，因此我們需要重新定義問題並設計機制。在本論文中，我們以整數規劃來描述問題，設計了近似及啟發式演算法，並以所設計的演算法為基礎設計了網路協定。我們亦以模擬實驗來驗證我們所設計的機制。我們的分析及模擬結果顯示我們的機制可以有效地減少路由器所記錄的群播傳送狀態數量，使得群播傳送狀態在路由器之間分配較平均，並使用較少的網路頻寬，而達成改進網路的擴充性之目標。Scalability is one of the most important reasons that prevent multicast from universal deployment. The scalability problem of multicast is that the network can not support a large number of members in a multicast group and a large number of multicast groups in the network due to the following two reasons. First, in control plane, each router needs to store lots of multicast forwarding states, and the distribution of multicast forwarding states among routers is not balanced. Therefore, each packet suffers from a large forwarding delay in each router, and each router requires a large memory to store all forwarding states. Second, in data plane, the trees used in current multicast mechanisms consume much more bandwidth than the optimal multicast trees, namely, the Steiner trees. Current multicast mechanisms waste the network bandwidth such that the network can not support a large number of multicast trees. In this dissertation, we solve the scalability problem of multicast from both the control-plane perspective and the data-plane perspective. In control plane, we propose a new multicast forwarding mechanism that is scalable in terms of both the number of members in a group and the number of groups in the network. Our mechanism reduces the number of forwarding states stored in each router and balances the distribution of forwarding states among routers. In data plane, we propose a new multicast delivery mechanism that uses much less bandwidth than current multicast mechanisms. Both proposed mechanisms adopt an emerging IP forwarding mechanism, Explicit Multicast (Xcast). Since Xcast is a new IP forwarding mechanism, the forwarding and routing problem in our mechanisms is much different from current multicast mechanisms. In this dissertation, we model the forwarding and routing in our mechanisms as optimization problems. We formulate them as integer linear programming problems, propose approximation and heuristic algorithms for our problems, and design protocols for our mechanisms. We also conduct simulations for all proposed algorithms. Our results shows that our mechanisms requires much fewer multicast forwarding states than current multicast mechanisms, and the distribution of forwarding states among routers is more balanced. Beside, our mechanisms also use much less bandwidth than current multicast mechanisms. Therefore, we believe that our mechanism can solve the scalability problem of multicast.List of Figures VI List of Tables IX 1 Introduction 1 1.1 Scalability Problem in Control Plane …………………………………………….……….. 2 1.2 Scalability Problem in Data Plane ……………………………………………………….... 4 2 Optimization of State Allocation for Multicast Communications Using Xcast 6 2.1 Introduction ……………………………………………………………………………….. 7 2.2 Problem Description ……………………………………………………………………..... 7 2.3 Minimizing the Number of State Nodes in Each Multicast Trees ………………………... 9 2.3.1 Dynamic Programming Algorithm ………………………………………………… 9 2.3.2 Distributed Greedy Algorithm ……………………………………………………... 12 2.4 Minimizing the Maximum Number of Forwarding States Stored in a Router ………….… 16 2.4.1 Proof of NP-Complete ……………………………………………………………... 16 2.4.2 Integer Linear Programming Formulation …………………………………………. 19 2.4.3 -Approximation Algorithm ……………………………………………………… 21 2.4.4 Heuristic Algorithm Based on Lagrangean Relaxation ……………………………. 25 2.4.5 Distributed Greedy Algorithm ……………………………………………………... 28 2.5 Protocol Design …………………………………………………………………………… 28 2.6 Simulation ………………………………………………………………………………… 35 2.7 Discussion ………………………………………………………………………………… 45 2.8 Conclusion ………………………………………………………………………………… 47 Appendix ………………………………………………………………………………….. 3 Bandwidth-Efficient Overlay Multicast Using Xcast 51 3.1 Introduction ……………………………………………………………………………….. 51 3.2 Problem Description ………………………………………………………………………. 53 3.2.1 Proof of NP-Complete ……………………………………………………………... 55 3.2.2 Integer Linear Programming Formulation …………………………………………. 58 3.3 2-Approximation Algorithm ………………………………………………………………. 59 3.3.1 First Greedy Algorithm …………………………………………………………….. 59 3.3.2 2-Approximation Algorithm ………………………………………………………... 62 3.4 Heuristic Algorithms Based on Lagrangean Relaxation …………………………………... 68 3.4.1 First Lagrangean Relaxation ………………………………………………………... 68 3.4.2 Second Lagrangean Relaxation and the Leaf Selection Problem …………………... 70 3.5 Destination Assignment Problem ………………………………………………………….. 80 3.6 Protocol Design ……………………………………………………………………………. 82 3.7 Simulation …………………………………………………………………………………. 88 3.8 Conclusion ………………………………………………………………………………… 95 4 Conclusion and Future Work 97 Bibliography 991667390 bytesapplication/pdfen-US群播路由網路multicastnetworkroutingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53419/1/ntu-93-F88921033-1.pdf