支援QOS路由器的封包排程與服務分流之設計與實作

Abstract

要在網路上提供好的多媒體應用的 服務，我們需要一個能保證傳輸品質的 網路架構;而一個網路的傳輸品質好壞 取決於網路對end-to-end delay 、頻寬以及delay jitter 等傳輸效能的保證。 欲支援網路傳輸品質控制服務，其 中最重要的是每個網路節點，如子網路 或IP 路由器所使用的排程方法，必須能 保障封包在傳輸路徑上傳輸的品質。在本計畫，我們設計了一個frame-based 的weighted-fair queueing algorithm 。跟以往WFQ 和 WF 2 Q 中，利用virtual finishing time 來作為排程依據的方式 不同，我們是以queueing jitter 作為排程 的依據。我們希望能將同一flow 的 packets 盡量平均的分散在時間軸上，如此才能讓worst-case fair index 和網路封包間的delay jitter 最小。這對在網路 上傳輸即時的多媒體的資料十分的重 要。我們也證明所提出的方法在達到這個目的的同時，也能兼顧bounded-delay 和 fairness 的要求。為了讓不同的分類及排程方法可以 得到檢驗與比較，我們建置了一個易於 實作且可提供正確效能檢測的路由器雛 形，在這個雛形中，我們主要實作可提 供priority queueing 及WFQ 兩種排程方 法的封包排程器模組，此外一個以”資料 流”及”網際網路協定標頭欄位的服務類 別”做為分類依據的簡易分類器也包含 在雛形中，最後我們並做了一系列的實驗用以驗證路由器雛形的效能。

As the Internet continues to grow in terms of the amount of traffic and the number of users, there are currently a lot of interests in providing multimedia communication services. Many of these new applications rely on the ability of the networks to provide QoS guarantees typically in the form of bounded end-to-end delay, bandwidth and delay jitter. In this paper, we propose a new scheduling algorithm called Maximum Jitter First (MJF) algorithm. It is a frame-based weighted-fair queueing algorithm. Different from WFQ and WF 2 Q, the algorithm uses delay jitter to describe the timestamps of the packets and to assign service order between flows within a frame. Slots assigned to a flow are spaced out within the frame so to minimize the Worse-case Fair Index and to achieve minimal delay jitter for packets of a flow. It as well possesses the bounded-delay and fairness properties. Furthermore, in MJF, the service order is calculated only upon call arrival and departure. It therefore has O(1) computational cost. In order to allow various classifier and scheduling policies to be examined and evaluated, a QoS router is prototyped. Currently, two scheduling algorithms: priority queueing and WFQ and a simple classifier based on “per-flow queueing” and the “Type of Service” field, have been implemented. We also conducted a number of experiments to evaluate the performance of the prototype in QoS provisioning.