可插隊式餘額累積輪循法:一個在封包交換網路下的新排程演算法

Abstract

這些年來，有許多以近似GPS (generalized processor sharing)為目的的PFQ (Packet Fair Queueing)演算法相繼被提出。大部分皆能提供良好的端點對端點延遲保證及公平對待所有共同分享同一傳輸途徑的資料流。然而，就實際應用的角度而言，可擴充及簡單是兩個更重要而必須考慮的議題。DRR (Deficit Round Robin) 是一個不錯的範例，選擇傳送一個封包的工作複雜度只有O(1)，而且很容易便可以被實際運用在硬體設計上。但是當資料流的個數增加時，所產生的延遲和不公平性便難以令人忍受。在我們這篇論文裡，描述了一個名為Preemptive Deficit Round Robin的新演算法。它藉由使用一些額外而固定數量的佇列來使封包傳送順序近似於PGPS的順序，進而突破了DRR難以克服的問題。我們對於延遲及公平性兩個參數作了一些分析，結果顯示在所有工作複雜度只有O(1)的演算法中，我們的演算法是較好的選擇。一些模擬的數據更進一步說明它一般的運作情形。

In recent years, many packet fair queueing algorithms have been proposed to approximate GPS (generalized processor sharing). Most of them can provide low end-to-end delay bound and ensure that all connections share the link in a fair manner. However, scalability and simplicity are two more important issues in practice. Deficit Round Robin requires only O(1) work to process a packet and is simple enough to implement in hardware, but its latency is too large to tolerate as the number of flows increases. In this work, we describe a new scheme, Preemptive Deficit Round Robin, which overcomes the problem of DRR. A fixed number of pre-order queues are placed to enable the transmission order of our scheme to approximate the order of PGPS (packet by packet generalized processor sharing). We provide an analysis of delay bound and fairness which shows our scheme as the better choice among all work-conserving schedulers with a worst-case time complexity of O(1) per packet. Simulation results are also provided to further illustrate its average behavior.