時戳式循環排程演算法在 Linux 核心之設計與實作

Abstract

現在網路封包排程方式以 FCFS 方式無法提供使用頻寬保證，而 Weighted Fair Queue 在建構上複雜度過高，本論文主要目的探討網路新封包排程方式，以減輕封包排程系統的額外負擔(overhead)，我們提出一個新的封包排程方法稱為 Timestamp Round-Robin(TRR)，封包重新初割成固定大小封包，利用 Time-Shift 概念來計算時間戳記(timestamp)，配合雜湊函數(hash function)以循環的方式來安排封包輸出的先後順序。並在 Linux 的網路核心程式(kernel)建構封包排程系統的方法。經實驗測量結果顯示，我們所發展 TRR 演算法性能優越，在執行速度上優於 Time-Shift Scheduling 演算法，在延遲限制(delay bound)優於 Deficit Round-Roubin 演算法。