現今的網際網路上傳輸著各種不同應用的訊務，而大多數的訊務都被處以相同的待遇：best effort，也就是儘可能的傳送這些封包，並未考慮其服務品質（quality of service，簡稱QoS）之需求，因此品質服務路由（QoS routing）的觀念被提出來改善這樣的情況。QoS路由的觀念就是根據某種訊務所需的QoS需求，計算一條符合其需求的路徑，故一個QoS路由演算法在計算路徑時非常依賴各鏈路之狀態資訊。隨著時間的推移，網路環境不斷改變將的不確定性鏈路狀態資訊（uncertain link state information）可能會使得QoS路由演算法做出錯誤的決策，如何在此不確定的鏈路狀態條件下做出適當的決策是很重要的課題。 本篇論文提出了一個名為最小變異路徑（Minimum Variant Path，簡稱MVP）的QoS路由演算法。不同於其他的演算法只著重於單一的鏈路成本，此演算法考量的是整體的路徑成本，其方法是找出一條鏈路品質與所需求之值差異量最小的路徑，如此能增加可用的鏈路數目，藉以計算出更多之路徑。另外此演算法還採用了一個稱為最小滿足比率（minimum satisfactory ratio）的概念來增進網路的整體效率。最小滿足比率的基本概念是某些訊務可允許某種程度上的品質服務損耗，因此此演算法可以根據一品質服務路由請求所指定的最小滿足比率來找出一條符合其需求的路徑。 以接受請求比率與接受頻寬比率的模擬結果顯示，在封包遺失率相似的情況之下，本篇論文所提出之最小變異路徑品質服務路由演算法的效能要比線性（Linear）品質服務路以及雙取線（Hyperbolic）由演算法平均分別高了5.58%與3.22%。 Today’s Internet is about to carry various types of traffic generated from different applications. Most of them are treated as the same way, “best effort”, which forwards packets as possible without providing quality of services (QoS). The concept of QoS routing was proposed to provide guaranteed services done by finding a path satisfying the QoS requirements of the traffic. Thus a QoS routing algorithm heavily depends on the link state information, such as available bandwidth, delay, etc. For the network environment changes as time goes by, the link state information may no longer precious. Thus a QoS routing algorithm might make an inappropriate decision with uncertain link state information. A QoS routing algorithm named Minimum Variant Path (MVP) is proposed in the thesis. The proposed algorithm focuses on the cost of the whole path instead of that of a single link. It tries to find a routing path that has the minimum mean variance between the available bandwidth of a link and the requested bandwidth specified in a QoS routing request. In the thesis, the traffic is assumed to be a certain degree of mission the QoS requirement, called satisfactory ratio. The proposed QoS routing algorithm is able to select a routing path to satisfy the QoS requirement with satisfactory ratio. Simulation results show that without any increase in the packet loss rater, the proposed MVP QoS routing algorithm is capable of offering extra 5.58% and 3.22% requests in average than the Linear and Hyperbolic QoS routing algorithm, respectively.
