蔡志宏臺灣大學：電信工程學研究所王永安Wang, Yung-AnYung-AnWang2007-11-272018-07-052007-11-272018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/58797　　在這篇論文中，我們提出了分級回覆封包(ACK)間隔器的實作方法，並且將其實現在Linux系統中。此分級ACK間隔器可以被安裝在伺服器端、使用者端、或是在路由器端的網路核心中，並且提供了不同優先權的排程以及頻寬管理的功能。ACK相對於資料封包來說，封包大小較小，是為控制與分析的理想對象。 　　對於不同類別(Class)的封包，分級ACK間隔器採用固定的優先權順序來控管。對於同一Class，不同的TCP Session之間，採用Token Round Robin (TRR)與Frequency-Based Rotation Priority Queue (FBRPQ) 來達到公平性的要求。 　　最後以實作來驗證提出的演算法，並改善了TCP傳輸的速率與穩定性。此外，也比較了在不同的排程方法下，分級ACK間隔器處理器的使用率。　　In this thesis,we propose a novel architecture of the Class-Based ACK Spacer and implement it on Linux platforms. This ACK spacer could be installed on the server side, client side, or on the router to provide different priorities and bandwidth allocations of each TCP class and session over ACK packet control. Since ACK is relatively small compared to TCP data packet, we hypothesize that ACK is better for buffering or in CPU load. 　　We use static priority algorithm and token bucket to solve multi-class scheduling problem. To control the sessions in the same priority class, we propose two session scheduling algorithms, Token Round Robin and Frequency-Based Rotation Priority Queue, to achieve fairness between sessions. 　　Finally, we construct experiment environment to verify our implementations. The TCP throughput could be stabilized and improved with proper parameters set. Bandwidth fair-share could be achieved. At last, we also analyze CPU load using different scheduling algorithms.Contents Abstract i 1　Introduction 1 1.1 TCP Burstiness and TCP Pacing 1 1.2 TCP Congestion Control 5 1.3 Related Work on TCP Pacing and Bandwidth Management 7 1.4 Motivation and Goals 9 2　Class-Based ACK Spacer Architecture and Algorithms 12 2.1 Class-Based ACK Spacer Architecture 12 2.2 Packet Classification 14 2.3 Decision Flow 18 2.4 Multi-Class Scheduling Algorithm 20 2.5 Multi-Session Scheduling Algorithm – The Token Round Robin Algorithm 24 2.6 Multi-Session Scheduling Algorithm – The Frequency-Based Rotation Priority Queue Algorithm 26 3　 ACK Spacer Implementation in Linux 30 3.1 Introduction of Linux Network Architecture 30 3.2 netfilter/iptables Architecture 33 3.3 Linux Programming Space Design 37 3.4 The ACK Spacer using libipq in iptables 38 3.5 Implementation Flexibility 41 3.6 Spacer Automation Requirement 43 3.7 Timing Control Issue and RTLinux 43 4　Implementation Results 48 4.1 Throughput Improvement and Stabilization 48 4.1.1 Environment Setup 48 4.1.2 Class with Static Priority Algorithm 50 4.1.3 Session Control with Token Round Robin Algorithm 57 4.1.4 Session Control with Frequency-Based Rotation Priority Queue Algorithm 62 4.1.5 Conclusions 66 4.2 Session Fairness Verification 68 4.2.1 Environment Setup 68 4.2.2 Results Analysis 70 4.2.3 Conclusions 79 4.3 CPU Load Comparison 80 4.3.1 Environment Setup 81 4.3.2 Results Analysis 83 4.3.3 Conclusions 84 5　Conclusions 86 5.1 Conclusions 86 5.2 Future Works 88 Appendix 90 A. Buffer Usage Comparison between ACK and data spacer 90 Reference 922150020 bytesapplication/pdfen-US服務品質排程器TCP調節Quality of ServiceSchedulerTCP Pacingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58797/1/ntu-94-R92942045-1.pdf