寬頻網路輸出緩衝交換器之逐步服務品質排程技術

Abstract

考量在輸出緩衝交換器內，服務品質排程機制強調的重點，已經轉移至可擴充規模的排程技術上，亦即資料流數量大量增加之下，仍能確保公平性與服務品質表現。目前主要的加權基礎排程演算法皆採用靜態或簡單粗調方式之時間標籤，結果在一般的資料流量情形下，不該降低的成效降下來，我們的目的是設計一套排程器，可以提供微調機制，在成效與複雜度之間取得動態權衡。在本論文中，我們提出了逐步服務品質排程技術（SQS），此乃根基於一個新的概念－資料窗，亦即在同一資料窗中採用簡單的先進先出服務，並在不同的資料窗保證逐步加權比例服務。藉由設定資料窗尺寸（W）為極小或極大，SQS可以分別表現出分權公平佇列（WFQ）及先進先出法（FIFO）的行為模式，更甚於此，對資料流而言，這樣的服務保證可以藉由逐步服務曲線明確說明。若Theta_min為資料流在忙碌區段第一個封包的最小上限延遲，則此曲線為W與Theta_min的函數。最後本論文透過模擬實驗的結果說明，在小資料窗（W<=10）之下，SQS表現的近似最差狀況公平分權公平佇列在輸出公平性、平均延遲、最差狀況延遲公平性上。

Pertaining to Quality of Services (QoS) scheduling in output-buffered switches, emphasis has been placed on the design of scalable schedulers that assure fairness and QoS performance despite ever-increasing magnitude of flows. Prevailing weight-based scheduling algorithms advocate static or coarse-grained simplification of timestamp computation, resulting in unnecessary performance downgrade under normal flow intensity. Our goal is to design a scheduler that enables fine-grained, dynamic trade-off balance between performance and complexity. In this thesis, we propose a Stepwise QoS Scheduler (SQS), based on a new notion of window, which exerts simple FIFO service within the window and guarantees stepwise weight-proportional service at the window boundary. By setting the window size (W) infinitesimal or infinitely large, SQS behaves as the Weighted Fair Queueing (WFQ) and FIFO policies, respectively. Moreover, such service guarantee for a flow is formally specified by a stepwise service curve, a function of W and Theta_min- the least-upper-bound delay incurred by the first packet of the busy period of the flow. Finally, the thesis demonstrates through experimental results that, by applying a small window (W<=10), SQS performs as superior as Worst-case Fair Weighted Fair Queueing (WF2Q) with respect to throughput fairness, mean delay, and worst-case delay fairness.