提供比例式延遲差異性服務相關排程演算法之研究

Abstract

在現今網際網路上，即時性的應用日漸增多，為了保證此類應用在網路上傳送封包的品質，亟需一套機制來確保其服務品質（QoS），其中IETF在RFC2475所提出的差異性服務（Differentiated Services）可在網際網路上實現不同類輸入間性能表現（如平均封包延遲、平均封包遺失率）達到相對差異的服務品質保證。在本篇論文中，我們設計一套排程理論以達成不同類別間倍比式延遲的差異性服務。在此模型中，性能表現必須具備兩個特性。第一為可預測性，指即使在短期時間內高優先權類別仍然可得到比低優先權類別更好的服務；第二為可控制性，指不同類別間性能表現的預設差異不會因網路情況的變化而有所改變。 故我們先針對Kleinrock所提出的WTP (waiting-time priority)封包排程理論作分析，並就其在可控制性表現方面的不足作改進。我們提出的D-WTP (dynamic waiting-time priority)是依據排隊理論所得結果，並預測下一個調整視窗的系統負載，動態的設定一個決定優先權的控制參數，如此可使在此調整視窗內離開的不同類別封包其平均延遲達到一個預設的比例，因而達到可控制性的要求。然而，當這個方法運用到多個輸入類別及更真實的網路訊務時，其表現則不如預期。故我們進一步提出了ADP (average-delay priority)封包排程理論來解決這些問題，ADP在決定優先權時是根據不同類別的平均延遲，其定義是將已離開封包之平均延遲和仍在佇列封包之平均等待時間做一個權重式的加總，如此可在長期時間延遲比例及短期時間延遲變異上取得均衡，由模擬結果可知ADP改善D-WTP性能表現上的障礙，並達成了無論在長期或短期時間上可預測性及可控制性的要求。

Recently, the Differentiated Services (DiffServ) model has been proposed to provide different degrees of QoS guarantee. In this thesis, we aim to design scheduling mechanisms that provide proportional delay differentiation among different classes. These scheduling algorithms have two important goals need to be achieved. First one is predictability, which means the higher classes will always get better services than the lower classes (or at least no worse) even under short timescales. The second critical factor is controllability. That is, we claim that a scheduling algorithm should also provide consistent quality differentiation regardless of any system load, class load distribution, or stochastic arrival process. First, we investigate the behavior of waiting-time priority (WTP) scheduler, which was regarded as the most effective method in achieving proportional delay differentiation. By referencing the result from its theoretical queueing analysis, we propose an algorithm, which called dynamic waiting-time priority (D-WTP). It indeed improves the system performance under both long-term and short-term situations, especially in moderate load condition. However, D-WTP still has some drawbacks. It is only valid when two classes exist and the performance downgrades with non-Poisson traffic arrivals. So we innovate another method, which called average-delay priority (ADP) algorithm, to solve these problems. ADP differs from D-WTP in the fact that it does not use the theoretical results and avoids the error caused by prediction. The simulation results show that ADP can have a very good short-term performance as well as the precise long-term achieved ratios among classes independent of any traffic intensity or class load distribution. It is also robust for bursty traffic pattern and suitable for multiple classes.