Abstract
網際網路近年來快速的成長，隨之而增的是各種有不同目的及不同需求的應用程式。由於各個應用程式之間所需頻寬不同，因此傳統網際網路的架構就受到了挑戰。例如VOD（Vedio On Demand）就是許多新興的應用程式中，需要改變目前網路架構以滿足它需要穩定而足夠的頻寬的一個例子。所以，對於有不同需求（如要求最少頻寬（minimal bandwidth）或最小的延遲保證（minimal delay guarantee））的應用程式，網路應該要能提供不同層級的服務，而不是如現今一般只提供最佳努力（Best-Effort）的服務。為了要整合不同的服務品質（QoS，Quality of Service）的需求，主要的關鍵就是在交換器（Switch）或邊緣設備（Edge Device）上執行良好的排程演算法。我們在FreeBSD 平台上實作了一種新的演算法- Fast Weighted-Fair Queueing[1]（FWFQ）。它的效能比起一般的P-GPS（Packetized Generalized Processor Sharing）類排程演算法並不遜色，但複雜度卻比較低。我們也將量測它在實作上性能的表現。我們除了將FWFQ實作出來外，相關的比重指定（weight assignment）與FWFQ在封包-基底（packet-based）網路下的變形也都完成了。另外也結合了RED（Random Early Detection）的變形，Weighted RED，作為緩衝區管理的機制。 另一方面，現版的TCP / IP通訊協定(第四版) 造就了近年來網際網路的風行，但隨著網路迅速擴張，及現代網路上應用程式對於即時傳輸、網路安全等特性之要求與日俱增，於是IETF (Internet Engineering Task Force) 乃針對網際網路通訊協定第四版的不足與缺點，修改而提出了下一代網際網路通訊協定 (第六版) 通訊協定。 新版TCP / IP通訊協定(第六版)的新增機制中，對於服務品質的支援，就在於20個位元長度的Flow Label 欄位。為了節省封包分類的時間，本實作將由Flow Label來達成直接分類（Cut Through）的功能，而不是如同傳統的第四版TCP/IP，藉由來源端及目的端的位址及埠號和通訊協定來將資料流分類（flow classification）。在上網人數成幾何級數成長的今日，提供單一的網路服務已經快不敷使用了。要能依服務型別的差異，提供各種不同等級的服務，是當務之急！而要達成此目的，就需要有良好的排程演算法。 在這篇文章裡，我們討論了關於一個新的GPS類的排程演算-Fast Weighted Fair Queueing的實作。除了細胞-基底的部份，為了在封包-基底的網路下也能使用，我們實作了兩種方法-Counting Method和Holding Method。雖然由於作業系統的架構使得Counting Method無法成功的完成，但Holding Method確實發生了作用。對於正確的變動比重，使得FWFQ能正確排程，我們也提出了兩套解決的方法-ABR-CBR Method及Fair Method，這部份也實作完成了，測試結果也相當令人滿意。甚至對於佇列緩衝區，我們也實作了Weighted RED來管理。因為若是在硬體的架構下，不可能無限制的讓佇列成長。由測試結果可以見到，封包會依成長的速率及資料流預約的頻寬，而產生丟棄比率的差異。 這次的實作，全是架於IPv6的平臺上。因為IPv6的封包有Flow Label的欄位，方便我們達成資料流分類（classification）和直接傳送（cut through）的功能。身為下一代的網際網路通訊協定，我們相信IPv6會扮演很稱職的角色。