寬頻網路排程器的軟體設計研究

Abstract

現在的電腦網路僅支援最佳努力（Best Effort）的服務，未來的網路系統將整合目前的網路架構，同時增加效能保證的服務以提供及時通訊的網路應用程式。在提供網路效能保證的服務中，改良網路中各個節點內的排程器是很重要的議題，本篇論文主要針對排程器，提供在實作上一套快速的軟體排程，我們主要將排程器分為兩類：一為支援非及時性封包的排程器，另一為支援及時性封包的排程器。對於非及時性的排程器，為了能降低實作上的複雜度主要以DRR（Deficit Round Robin）為基本實作架構，但是我們的方法改進了DRR短時間輸出不公平的缺點，分析後發現，我們的演算法無論在公平性、速度和實作上是很好的機制，適用於高速網路的路由器或交換機。對於及時性封包的排程器，主要針對封包搜尋的部分制訂出實作的方法，我們主要改良以旋轉優先權佇列（Rotate Priority Queue）為架構的排程，來達到快速且工作複雜度只有O（1）的演算流程。經由分析，我們的方法雖然增加了精確度的誤差，但是卻降低了實作上的複雜度，在最壞情況下精確度的誤差只有11%，對於及時性封包的排程是不錯的選擇。

Today’s computer network supports only best-effort service. Future networks will not only integrate current network architecture, but also support the guaranteed performance service. In order to support the guaranteed performance service, it is a very important issue to improve the ability of schedulers. We classify the scheduler into two kinds: One is for non-real time traffic, the other is for real-time traffic. In order to reduce the job complexity of non-real time traffic’s scheduler, we use DRR (Deficit Round Robin) as our basic implementation architecture. Our method really overcomes the DRR’s disadvantage in short time unfairness. Our analysis shows that it is really a better choice in fairness, speed and implementation. For the real time traffic’s scheduler, we focus on searching to improve the basic rotate priority queue architecture. Our method increases the precision error, but decreases the complexity of implementation. We show that the worst case precision error is just 11%, so this method is good for real time traffic scheduling.