臺灣博碩士論文加值系統

本論文提出一個應用於差異性服務之適應性公平頻寬配置方法(AFABA)，此頻寬配置方法基於網路中封包的特性要求並考量網路流量及排程現況，動態分配資源。
在此配置方法中第一個特色是對於差異性服務具有彈性的架構；針對服務特徵多樣化的類型，我們提出以效能指標為特色的差異性規劃，依據此具有特性的效能指標發展出效能分佈的函式為頻寬配置參考，結合方針轉換(Policy Translator)和網路流量的量測架構出適應性公平頻寬配置方法的服務模型。此服務模型適應性協同其他的服務類型決定一個權重值以提供權重公平佇列排程(WFQ)分配頻寬。因此，我們得到一個精確而且具適應性的頻寬分配法則。
公平性是此配置方法中的第二個特色；AFABA的基本原則在於最大化網路資源的使用效益並使之具公平性的規則，根據實際網路流量及效能衡量(Utility Func-tions)的滿意程度，最大化頻寬分配並反應出成比例式的公平原則且平衡分配目前存在的所有服務類型。
此配置方法也具有延展性的優點；對任何新增的服務類型，我們將能很容易的建構它的服務模式整合於目前已存在的服務模型中參與頻寬的分配。
為了證實適應性公平頻寬配置方法優勢，我們做了數個模擬，觀察分析在不同的流量狀況下及效益參數的影響，分配的效能及速度上的收斂情形，這些模擬表示出我們提出想法的正向結果。

This thesis presents a framework of Adaptive FAir Bandwidth Allocation (AFABA) for differentiated services. In AFABA, the bandwidth allocation is based on the packet characteristics, traffic conditions, and scheduler’s policies to dynamically adjust.
The first feature of AFABA is in its flexible architecture for differentiated services. Based on the characteristics of various kinds of services, we present differentiated for-mulation in featured performance indices for them, and then develop their distribution function of utility based on the featured indices to be the references of bandwidth alloca-tion in AFABA, and they combine with policy translator and traffic state meter to com-pose the AFABA’s service model. The service model determines the weight coefficients adaptively and invokes Weighted Fair Queue (WFQ) to work. Therefore, we get a precise and adaptive bandwidth allocation scheme.
Fairness is the second feature of AFABA. The basic principle of AFABA is to maximize the utilization of network resources regulated by the rule of fairness. According to the satisfaction degree between practical network traffic status and performance re-quirements (utility function), AFABA applies proportional fairness strategy to maximize bandwidth utilization and balance the allocation among all of the existing service classes.
AFABA also has the advantage of scalability. For any new-created service class, we can easily construct its service mode and integrate it into the existing service model to take part in the allocation of bandwidth.
To confirm the superiority of AFABA, we have made several simulations to ob-serve and analyze the performance and convergence rate in different traffic conditions and parameter values of utility. The simulations exhibit positive results for the proposed idea.

List of Figures： VI
List of Tables： VII
Chapter 1. Introduction 1
1.1. Motivation 1
1.2. Network Utilization 2
1.3. Thesis Organization 4
Chapter 2. Background 5
2.1. Conventional QoS Models 5
2.1.1. Integrated Services 5
2.1.2. Differentiated Services 6
2.2. The Fairness Criteria of Bandwidth Sharing 8
2.2.1. Max-Min Fairness 9
2.2.2. Proportional Fairness 10
2.2.3. Utility Approach to Fairness 12
2.3. Philosophy of Service Model 12
2.3.1. Basic Concept of Service Model 12
2.3.2. Types of Conventional Service Model 13
2.3.3. The Fairness Issue of Service Model 15
2.4. The Previous Works of Packet Scheduling with Fairness Guarantee 15
2.4.1. Generalized Processor Sharing 16
2.4.2. Weighted Fair Queue 17
2.4.3. Worst-case Fair Weighted Fair Queueing 19
2.4.4. VirtualClock 20
Chapter 3. Differentiated Service Model for Optimal Resource Utilization 22
3.1. System Architecture 22
3.2. System Operation 24
3.3. Interface of Quality Requirement 25
3.4. AFABA Service Model 27
3.4.1. State Meters of Traffic and Scheduling 28
3.4.2. Policy Translator 29
3.4.3. Adaptive FAir Bandwidth Allocation 30
3.4.3.1. Objective Function of Resource Utilization 31
3.4.3.2. Optimal Bandwidth Allocation on Lagrangian /Kuhn-Tucker Condition 32
3.4.3.3. Fairness Analysis 33
3.5. Packet Classifier and Scheduler 34
3.6. The Features of AFABA Service Model 35
3.6.1. Scalability of Service Model on Network 36
3.6.2. The Saturation of Bandwidth Allocation 36
Chapter 4. Policy Descriptions and Utility Functions for Service Classes 38
4.1. Implementation of AFABA 38
4.2. Categories of Service Classes 40
4.3. Designs of Service Class for Different Policies 40
4.3.1. The Design of Delay Sensitive Class 40
4.3.2. The Design of Reliability-Demanded Class 43
4.3.3. The Design of Elastic(Best-Effort) Class 44
4.4. Designs of Utility Functions 45
4.4.1. Translation from Service Characteristics to Utility 45
4.4.2. Utility Functions of Service Classes 46
4.5. Procedure on Resource Allocation 49
Chapter 5. Simulation and Performance Analysis 52
5.1. Simulation Scenarios 52
5.2. Utility Behaviors of Differentiated Service Classes 53
5.3. The Parameter Effect on Bandwidth Allocation 57
5.3.1. The Impact of Parameters of Utility Functions 57
5.3.2. The Impact of Parameters of Requirement Criteria 60
5.3.2.1. Buffer Space of Reliability-Demand Class 60
5.3.2.2. Delay Time on Delay Sensitive Class 64
5.4. The Effect of Sampling Interval on Performance 65
5.5. The Effect of Traffic Characteristics on Performance 67
Chapter 6. Conclusion and Future Work 69
6.1. Conclusion 69
6.2. Future Works 70
References 72

[1]R. Braden. et al. “Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification.”, RFC 2205, September 1997.
[2]A. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks：The Single-Node Case”, IEEE/ACM Transactions on. Networking, vol. 1, no. 3, pp. 34-357, June 1993.
[3]J. C. R. Bennett and H. Shang, “WF2Q：Worst-case Fair Weighted Fair Queueing ”, INFOCOM '96. Fifteenth Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation., Proceedings IEEE , vol: 1 , pp.120 -128 1996
[4]S. Shenker, “Fundamental Design Issues for the Future Internet,” IEEE Journal on Selected Areas in Communications, Vol. 13, no. 7, pp.1176-1188, September 1995.
[5]Z. Cao and E. W. Zegura, “Utility Max-Min：An Application-Oriented Bandwidth Allocation Scheme”, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , Volume: 2 , pp.793 -801, 1999
[6]F. P. Kelly and A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: shadow prices, proportional fairness and Stability,” Journal of the Opera-tional Research Society, pp.237-252, 1998.
[7]Frank Kelly, “Charging and rate control for elastic traffic” European. Transactions on. Telecommunications. 8, pp.33-37, 1997.
[8]D. A. Wismer and R. Chattergy, Introduction to nonlinear optimization :a problem solving approach . New York: North-Holland, 1978.
[9]Lixia Zhang, “VirtualClock: a new traffic control algorithm for packet-switched networks”, ACM Transactions on Computer Systems. Vol. 9, no. 2, pp. 101-124, May 1991.
[10]K. Kar and S. Sarkar, L. Tassiulas, “A Simple Rate Control Algorithm for Maximiz-ing Total User Utility”, Networking, IEEE/ACM Transactions on , Vol: 10 Issue: 2 , pp. 272 -286, April 2002.
[11]N. S. Ko and H. S. Park, “Emulated weighted fair queueing algorithm for high-speed packet-switched networks”, Information Networking, 2001. Proceedings. 15th In-ternational Conference on , pp.52 -58, 2001.
[12]S. H. Low, “Optimization Flow Control with On-line Measurement”, Proceedings of the 16th International Teletraffic Congress, Edinburgh, U.K.,June 1999.
[13]L. Massoulie and J. Roberts. “Bandwidth sharing：objectives and algorithms”, Net-working, IEEE/ACM Transactions on , Volume: 10 Issue: 3, pp. 320 -328, Jun 2002
[14]S. H. Rhee and T. Konstantopoulos, “Optimal Flow Control and Capacity Allocatin in Multi-Service Networks”, Decision and Control, 1998. Proceedings of the 37th IEEE Conference on , vol.2, pp. 1662 -1667,1998.
[15]H. Yaïche, R. R. Mazumdar, and C. Rosenberg, “Distributed algorithms for fair bandwidth allocation to elastic services in broadband networks”, INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , vol.3., pp.1511 -1517, 2000
[16]S. Kunniyur and R. Srikant, “End-to-End Congestion Control Schemes：Utility Functions, Random Losses and ECN Marks” INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceed-ings. IEEE , vol.3, pp.1323 -1332 , 2000
[17]E.L. Hahne, “Round-Robin Scheduling for Max-Min Fairness in Data Networks”, Selected Areas in Communications, IEEE Journal on , Volume: 9 Issue: 7 , pp. 1024 -1039, Sept. 1991
[18]K. Nichols. et al. “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers”. RFC 2474, December 1998.
[19]S. Blake. et al. “An Architecture for Differentiated Service”, RFC 2475, December 1998.
[20]P. Almquist. et al. “Type of Service in the Internet Protocol Suite”. RFC 1349, July 1992.