寬頻網路頻寬分配公平性之研究

Abstract

在寬頻網路中，用戶的資料流可以依據他們對服務品質的需求來請求不同的頻寬。服務品質可由資料流□的封包在傳送中的延遲、延遲變異、流失量等數據評量之。根據用戶們的需求，網路服務者應該提出方法在用戶資料流間達成公平的頻寬分配。我們的研究集中在兩種主要服務，線路模式服務(Circuit Mode Service)與流失量控制服務(Controlled-loss Service)，以提供有效率的頻寬公平分配方案。線路模式服務目標在於提供資料流有保證的頻寬與有限的傳輸延遲，而流失量控制服務則在於使資料流能調整流速來適應網路的變化以避免資料流失。在非同步傳輸模式網路(ATM)與網際網路(Internet)中都有這類的服務。例如：網際網路的保證服務(Guaranteed Service)與負載控制服務(Controlled-load Service)便分別是所謂的線路模式服務與流失量控制服務。兩種重要的頻寬分配的方法，公平候伺(Fair Queueing)與速率基礎的擁塞控制(Rate-based Congestion Control)，能分別提供線路模式服務與流失量控制服務。它們有一共同的設計訴求，便是頻寬公平分配。頻寬公平分配使得受線路模式服務的資料流彼此間有良好的區隔，也使得受流失量控制服務的資料流彼此間無頻寬分配不均的現象。基於公平候伺(Fair Queueing)方法，我們提出Bounded Tag Fair Queueing (BTFQ)方案，此方案對公平候伺的三大訴求：有限的不公平性、有限的延遲、與執行效率，有較好的成效。此外，增強版的BTFQ，稱為BTFQ+，也被提出，它改進了BTFQ的公平性，而我們也設計了一個低成本高速度的硬體來配合BTFQ+，以縮短BTFQ+的執行時間。 根基於速率基礎的擁塞控制(Rate-based Congestion Congrol)方法，我們提出Weighted Max-min Fairness with Queue Control (WMFQC)方案。此方案保證資料流的最小流速，而且將可用的頻寬快速而公平地分配給資料流。一旦資料流的流速降到它們公平配給的頻寬量時，資料流□的封包流失量將幾近於零。然而當資料流的流速尚未完全達到公平配給的頻寬量時，此方案中的Queue Control方法亦能幫助減少封包流失量。因此，WMFQC方案能將資料流失率壓的很低。在未來，我們將研究在網際網路上TCP擁塞控制方法的頻寬分配公平性。TCP擁塞控制會被如此的重視是因為它在網際網路上提供流失量控制服務。目前使用最多的TCP擁塞控制法已被知曉會有頻寬分配不均的現象。這現象是在那些通過同一瓶頸點的TCP連線中，具有較長環遊時間(round-trip time)的連線會得到一個較小的頻寬配給。我們試圖發現一個基於TCP擁塞控制的新演算法去置換現行常用的TCP擁塞控制法，以達成頻寬公平分配。

In a broadband network, the flows of applications are allowed to request various amounts of bandwidth according to their requirements in the quality of service (QOS), evaluated in terms of delay, delay jitter (delay variance), and loss. A network service provider should provide a mechanism to achieve fair bandwidth allocation among flows according to their requirements. Our research focuses on providing efficient fair-allocation schemes for two main types of services, the circuit mode and the controlled-loss services. The circuit mode service aims to provide guaranteed bandwidth and delay bound while the controlled-loss service aims to enable flows to adjust their rates adapting to the network state for avoiding data loss. There have been such kinds of services defined in the ATM and the Internet. For example, in the Internet, the Guaranteed and Control-load services are the circuit mode and packet mode services, respectively. Two significant mechanisms of bandwidth allocation, Fair Queueing and Rate-based Congestion Control support circuit mode and controlled-load services, respectively. The common design issue of the two mechanisms is the fairness of bandwidth allocation. Fair allocation makes good separation between circuit mode applications and prevents the arguments of unfairness from packet mode applications. Based on Fair Queueing, we propose Bounded Tag Fair Queueing (BTFQ) scheme, which performs better in the three main issues of Fair Queueing: bounded unfairness, bounded packet delay, and computation efficiency. In addition, the enhanced version BTFQ+ is also proposed to improve the fairness property of BTFQ and a low-cost, high-speed hardware is designed for reducing computation time. Based on Rate-based Congestion Control, we propose Weighted Max-min Fairness with Queue Control scheme (WMFQC). The scheme guarantees minimum rates of flows and distributes the available bandwidth fairly to flows much quickly. Once the rates of flows are reduced to their fair allocation shares, the packet loss will be reduced almost to zero. The queue control mechanism of the scheme also helps to reduce the packet loss while the fair allocation is not achieved yet. As a result, the scheme introduces a very low degree of packet loss. In the future, we will study on the fairness of bandwidth allocation in the Internet introduced by the TCP Congestion Control mechanism. TCP Congestion Control is paid much attention to because it provides the controlled-loss service in the Internet. An unfairness phenomenon resulting from the popular version of the TCP Congestion Control mechanism has been known that for the TCP connections passing through the same bottleneck link, the one with a longer round-trip delay receives a smaller bandwidth share. We seek to find an algorithm based on TCP Congestion Control to replace the popular version of TCP Congestion Control in order to achieve fair allocation. Abstract (in English) Acknowledgements Table of Contents List of Tables List of Figures List of Symbols Chapter 1. Introduction Chapter 2. Survey of Related Works 2.1 Services 2.1.1 ATM Service 2.1.2 Internet Transport Service 2.1.3 Integrated Services/RSVP 2.1.4 Differentiated Services 2.2 Circuit Emulation 2.2.1 Time-frame Based Packet Scheduling 2.2.1.1 Stop-and-Go 2.2.1.2 Hierarchical Round Robin 2.2.2 Priority Based Packet Scheduling 2.2.2.1 Delay Earliest-Due-Date 2.2.2.2 Jitter Earliest-Due-Date 2.2.2.3 Rate-Controlled Static-Priority 2.2.2.4 Virtual Clock 2.2.2.5 Fair Queueing 2.2.3 Adopting Fair Queueing for Circuit Emulation 2.2.4 Related Works of Fair Queueing 2.3 Available Bandwidth Access 2.3.1 Rate-based Mechanisms with Explicit Feedback 2.3.2 Rate-based Mechanisms with Implicit Feedback 2.3.3 Window-based Mechanisms with Implicit Feedback 2.3.4 Window-based Mechanisms with Explicit Feedback 2.3.5 Related Works of Rate-based Congestion Control Chapter 3. Bounded Tag Fair Queueing 3.1 Fair Queueing 3.1.1 System Model 3.1.2 Goal of Fair Queueing 3.1.3 Theoretic Scheme for Fair Queueing 3.2 Bounded Tag Fair Queueing Scheme 3.2.1 Bounded Delay of BTFQ 3.2.2 Fairness of BTFQ 3.2.3 Efficiency of BTFQ 3.3 BTFQ+ 3.3.1 Supporting Hardware for BTFQ+ 3.4 Comparison 3.4.1 Classification and Comparison 3.4.2 Comparison with the SPFQ Scheme 3.4.3 Comparison with the LFVC Scheme 3.5 Simulation and Results 3.5.1 Fairness Degree 3.5.2 Experiments 3.6 Summary Chapter 4. Weighted Max-min Fairness with Queue Control 4.1 Background 4.1.1 Rate-adaptive Mechanism 4.1.2 Switch Model 4.1.3 Max-Min Scheme 4.2 Weighted Max-min Fairness with Queue Control Scheme 4.2.1 Bandwidth Allocation 4.2.2 Queue Control 4.3 Correctness in Fairness 4.4 Simulation 4.4.1 Efficiency of WMFQC Scheme 4.4.2 Performance of WMFQC Scheme 4.5 Summary Chapter 5. Concluding Remarks and Future Works 5.1 Concluding Remarks 5.2 Future Works Reference Appendix Publication List Vita