分散式QoS群播路由演算法的設計與分析

Abstract

自從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.