李德財臺灣大學：資訊工程學研究所黃子倫Huang, Tzu-LunTzu-LunHuang2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53870自從1990年左右開始, 專家們便開始討論如何在廣域網路或是網際網路上提供具有服務品質保證的路由. 這個問題到目前為止一直都是一個很重要且尚未解決的研究議題. 在博士論文內, 我們將提出以經驗為主的分散式演算法去對付多條件限制群播路由的問題. 議題將分成兩個部分討論, 雙條件限制路由與多條件限制路由. 在雙條件限制路由的部分, 我們首先針對現有相關文獻的做法做探討並列出這些做法的優缺點. 接著, 我們提出兩個反例去證明賈 教授在論文[24]內演算法上所發生的兩個嚴重的錯誤與我們所提出相對的解決的方法(演算法). 我們所提出的演算法不僅能夠提供正確的解答之外, 而且在假設上我們還延伸了賈 教授在論文內的限制, 亦即在我們的論文內delay與cost這兩個參數彼此是相互獨立的. 此外, 我們也提供了有效率的演算法讓網路內的節點能夠動態的加入或離開現有的群播連線. 同時, 我們也提供了容錯的機制以避免因為某個或是某些節點發生錯誤而造成其它節點在服務品質上的影響. 在多條件限制路由的議題上, 我們是以雙條件限制路由的做法為基礎並做延伸. 我們先對所要解決的問題做正確的數學定義, 然後提出相對的分散式演算法去求解多條件限制路由的問題. 我們把演算法的過程與結果與三篇知名的論文做比較並對比較結果做詳細的解釋與說明. 不管是雙條件限制或是多條件限制路由, 我們所提出的演算法的表現均優於同等級的被比較論文. 是否存在更有效率與表現更好的演算法, 值得我們做更近一步的研究與探討.How to provide an efficient quality of service (QoS) routing in wide area networks (WAN) or in Internet has been an important research issue since about 1990. In the dissertation, we propose efficient heuristic-based distributed algorithms for addressing the problem of multicast routing with multiple QoS constraints. Two types of multicast routing problem are considered, bi-criteria routing and multi-criteria routing. In bi-criteria routing, we first review some existing algorithms, and point out errors in the well-known algorithm due to Jia [24] by two counter examples. We then propose an algorithm that improves Jia’s algorithm. A fix to Jia’s algorithm is given, and a generalization of his algorithm, including relaxation of routing constraints, allowing for dynamic updating of multicast group, and consideration of fault-tolerance and recovery in the routing network. In multi-criteria routing, we extend our result, based on our new algorithm of bi-criteria routing, to consider a generalized model of the QoS routing. We point out an inherent distinction between these two problems in terms of solution complexities. For both algorithms, we have made a computational analysis and given correctness proofs. To compare with many well-known algorithms/protocols, we perform simulations. Our simulation results indicate that our proposed algorithms have a better performance than existing ones.1. Introduction 10 2. Bi-Criteria Routing 14 2.1 Problem Definition 14 2.2 Related Work 15 2.3 Counterexamples to Jia’s and Prior Works 18 2.4 Routing Information and Assumptions 22 2.4.1 Routing Information 22 2.4.2 Assumptions 25 2.5 Our Algorithm 25 2.5.1 Heuristic Function of the Distributed Algorithm 25 2.5.2 Basic Idea of the Distributed Algorithm 28 2.5.2.1 Construction of the MRT 28 2.5.2.1.1 Tree Construction 28 2.5.2.1.2 Cycle Processing 30 2.5.2.1.3 Tree Pruning 31 2.5.2.2 Dynamic Join and Leave of Multicast Memberships 32 2.5.2.3 Fault Recovery of the MRT 35 2.5.3 The Distributed Algorithm 37 2.6 Analysis, Correctness Proof, and Comparison 46 2.6.1 Analysis of the Algorithm 46 2.6.2 Correctness of the Algorithm 51 2.6.3 Complexity Comparison with other related Algorithms 56 2.7 Simulations 57 2.7.1 Simulation Environment 57 2.7.2 Performance Evaluation 59 2.7.2.1 Comparison with Jia’s Algorithm 59 2.7.2.2 Comparison with other Algorithms 62 2.7.2.3 The frequency of cycle occurrences 66 3. Multi-Criteria Routing 68 3.1 Problem Definition 68 3.2 Related Work 72 3.3 Our Iterative Distributed Algorithm 77 3.3.1 Architecture and Assumptions 77 3.3.2 Algorithm Description 79 3.3.2.1 Basic Idea 79 3.3.2.2 An Example of the Algorithm 84 3.3.2.3 The Iterative Distributed Algorithm 94 3.3.3 Dynamic Join/Leave of the MRT 100 3.4 Analysis and Comparison 102 3.4.1 Analysis 102 3.4.2 Comparison 104 3.5 Simulation 109 3.5.1 Simulation Environment 109 3.5.2 Simulation Result 110 4. Conclusion 116 References 118 Publication 125767954 bytesapplication/pdfen-US群播路由分散式演算法多條件限制路由多條件限制QoS 路由演算法QoS 路由協定容錯multicast routingdistributed algorithmconstrained Steiner treemulti-constrained routingmultiple constraintsQoS routing algorithmQoS routing protocolfault tolerantNP-completenessheuristicsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53870/1/ntu-95-D88526002-1.pdf