階層式自我時序公平排隊演算法的Latency分析

Abstract

有人提出了一種簡單的方法來實現自我時序公平排隊 (SCFQ) 訊務排 程演算法。然而此一架構僅適合於中度範圍的頻寬要求，而不適合於大範 圍的頻寬要求。 階層式的架構可以有效地處理上千個不同頻寬要求的連 接。Latency 是用來評估以速率為基準的 (rate-based) 排程演算法的重 要參數。Lacency 的定義為一個連結的封包如果到達時該連接的佇列為空 的，該封包在系統內最大的排隊時間。有人導出自我時序公平排隊排程演 算法的 latency，結果顯示其值和系統的連結個數成正比。此一特性使得 自我時序公平排隊演算法並不適用於即時性的排程演算法。在本篇論文中 ，作者導出了階層式自我時序公平排隊排程演算法和自我時序公平排隊排 程演算法的 latency。推導的過程利用了正規化工作量 (normalized work) 的觀念。作者並得到了何時階層式的架構可以得到較好 latency 的法則。除了可以改進 latency 之外，電腦模擬的結果也顯示出階層式 的架構在減少高頻寬連結的輸出叢聚 (output burstiness) 時比自我時 序公平排隊排程演算法來的更好。論文中並對兩個群體 (group) 的系統 做了更進一步的分析。 A hardware-efficient implementation for theself-clocked fair queueing (SCFQ)traffic scheduling algorithm usingsorting bins has recently been proposed. This architecture is suitable for a moderate range of throughput requirements. A hierarchical architecure can be scaled to handle thousands of connections with a wide range of throughput requirements. Latency which is defined as the maximum queueing time a connection i packet spent in the system, conditioning on connection i is empty upon its arrival, is an important parameter to evaluate rate-based scheduling algorithms. The latency of SCFQ wasto be propotional to the number of connections. Due to this property, SCFQ is not considered to be a good candidate for realizing real-time scheduling algorithms. In this thesis, we derived the latency for a hierarchical SCFQ together with the latency of SCFQ. The derivation was based on the concept of normalized work. We derived a criterion for a connection to benefit from thehierarchical design. In addition to the improvement of latency,it was also demonstrated viacomputer simulations that hierarchical architecture may result in a better performance than the SCFQ algorithm in the sense that the output burstiness of high-rate connections can be significanlty reduced. Some numerical examples for two-group systems are provided.