跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 21:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李春良
研究生(外文):Chun-Liang Lee
論文名稱:在網際網路上提供具擴充性服務品質之研究
論文名稱(外文):A Study for Providing Scalable QoS over the Internet
指導教授:陳耀宗陳耀宗引用關係
指導教授(外文):Yaw-Chung Chen
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:90
語文別:英文
論文頁數:153
中文關鍵詞:網際網路差異式服務服務品質加權式比例公平性無狀態核心公平排隊法
外文關鍵詞:InternetDifferentiated ServicesQuality of ServiceWeighted Proportional FairnessCore-Stateless Fair Queueing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:2103
  • 評分評分:
  • 下載下載:866
  • 收藏至我的研究室書目清單書目收藏:3
現在的網際網路只提供單一種類的服務,也就是best-effort 服務,這種服務無法保證傳輸及時性以及傳輸速率。隨著網際網路轉變為商業架構,對於在其上提供更好的服務品質需求也隨之增加。
在本論文中,我們提出了四種能有效支援具有擴充性服務品質的方法。這些方法的目標在於達到傳輸速率的加權式公平分配,也就是說,每一條資料流能得到的傳輸速率取決於它被指定的權值。我們提出的方法遵循差異式服務的設計理念,亦即儘可能簡化核心路由器功能而達成良好的擴充性。
我們提出的第一個方法是由端點主機的觀點來解決服務品質的議題。與現行的網際網路架構相似,流量控制主要是由端點主機的演算法來達成,而路由器不需要對服務品質提供特殊的支援。不同於大部份的端點對端點協定所採用的被動式流量控制方式,我們的方法採用主動式流量控制方式,透過保持每一條資料流在網路上多餘的封包與其權值成比例的方式,我們能利用一個簡單且有效的演算法來達到速率的加權式公平分配。我們利用電腦模擬及在Linux上實作的方式來驗證提出方法的效能。
第一個方法的優點在於其十分簡單,很容易被實作。但是,由於很難要求每一個使用者都遵循相同的控制方法,當有不遵循控制方法的使用者時,第一個方法就無法保證其他使用者的效能。因此,我們將第一個方法延伸為邊緣對邊緣的流量控制方法,在這個方法中,封包在被送進核心網路前會先在入口的邊緣路由器上等候,同時我們採用以速率為主的流量控制方法,而非在第一個方法中所使用的滑動窗式的方法。由於核心路由器不需要提供任何支援,因此,第二個方法可以說是差異式服務模式的一個極端實現的例子。
在第三個方法中,我們提出了一個稱為多層級公平排隊演算法,其中需要修改邊緣及核心路由器。與現有的方法如CSFQ以及RFQ相比,我們的方法能達到更好的公平性及效能,同時它也支援分層編碼的應用程式,並且不會帶來額外的設計複雜度。
最後,我們提出一個基於虛擬資料流概念的封閉性流量控制方法,它能有效地避免在公平排隊演算法中可能造成的資源浪費。電腦模擬的結果證實它的確能明顯地提高網路效能,我們同時也利用分析的方式來證明這個方法的收斂性質。在一個單一瓶頸的網路下,我們證明該系統能在O(log N)的控制週期內達到速率的加權式公平分配,其中N代表資料流的數目。

Nowadays the Internet only provides one service class, the best-effort service, which does not guarantee any timeliness or transmission rate. With the transition to a commercial infrastructure, there is an increasing need to provide better service quality in the Internet.
In this dissertation, we present four efficient approaches for supporting scalable quality of service (QoS) over the Internet. The proposed approaches aim at achieving weighted fair rate allocations. More specifically, each flow is assigned a weight which determines the service rate it will receive. The proposed approaches follow the design philosophy of the differentiated services (Diffserv) model; that is, keeping the core network as simple as possible for good scalability.
The first approach addresses QoS issues from the aspect of end-hosts. Similar to the current Internet architecture, the traffic control is mainly accomplished through end-host algorithms. Routers in the network do not have to provide any particular support for the service quality. Instead of using a reactive flow control scheme commonly used in end-to-end protocols, the proposed approach uses a proactive flow control scheme. By keeping a certain amount of extra packets in proportion to its weight for each flow in the network, the proposed approach is able to achieve weighted fair rate allocations with a simple and efficient distributed algorithm. We evaluate the performance of the proposed approach through both simulations and experiments on Linux.
The main advantage of the first approach is the simplicity, which eases the deployment. However, since it is difficult to ask every user to follow the same flow control rule, the first approach cannot guarantee the throughput of a well-behaved user if any ill-behaved traffic is present. Therefore, we extend the first approach to an edge-to-edge flow control algorithm, in which the packets of each flow are queued at ingress edge routers before they can be forwarded to the core network. In contrast to the window-based flow control used in the first approach, rate-based flow control is used in the second one. With the proposed approach, core routers do not have to provide any particular supports. Therefore, this approach can be considered as an extreme case for realization of the Diffserv model.
In the third approach, we propose the so-called Multi-Level Fair Queueing (MLFQ) algorithm, in which both edge routers and core routers are required to be modified. As compared with existing approaches, such as Core-Stateless Fair Queueing (CSFQ) and Rainbow Fair Queueing (RFQ), MLFQ achieves better fairness of rate allocations and higher throughput. Moreover, it supports layer-encoded applications. In particular, it does not incur extra implementation complexity.
Finally, a closed-loop flow control based on the idea of virtual flow is proposed. This approach avoids the potential bandwidth waste in Fair Queueing algorithms. Through simulations, we show that it significantly improves the network throughput. We also give an analytical argument for the convergence of the proposed approach. For a single bottleneck configuration, we prove that the system is guaranteed to achieve weighted fair rate allocations in O(log N) cycles, where N is the number of flows.

Abstract in Chinese i
Abstract in English iii
Acknowledgements v
Contents vi
List of Figures x
List of Tables xiii
1 Introduction 1
1.1 Goal and Scope 2
1.2 Contributions 3
1.3 Structure of Dissertation 5
2 Background 6
2.1 Integrated Services 6
2.1.1 Guaranteed Service 7
2.1.2 Controlled-Load Service 8
2.1.3 Drawbacks of Integrated Service 9
2.2 Differentiated Services 10
2.2.1 Premium Service 11
2.2.2 Assured Service 12
2.3 Weighted Fair Rate Allocations 13
3 End-to-End Flow Control Scheme for Differentiated Services 15
3.1 Related Studies 16
3.2 Proposed Approach 16
3.2.1 Service Differentiation 17
3.2.2 Flow Control 18
3.2.3 Error Recovery 22
3.3 Simulation and Numerical Results 23
3.3.1 Simulation Environment 23
3.3.2 Numerical Results 23
3.4 Implementation of the Proposed Approach on Linux 28
3.4.1 Test Configuration 28
3.4.2 Experimental Results 29
3.5 Chapter Summary 34
4 Edge-to-Edge Flow Control Scheme for Dumb Core Networks 35
4.1 Background 36
4.2 Proposed Architecture 38
4.3 Rate Adaptation at Edge Routers 41
4.3.1 Service Differentiation 41
4.3.2 Rate Adaptation 42
4.4 Implementation Issues 45
4.4.1 Selection of the Parameter Nctrl 45
4.4.2 Overhead of Control Packets 46
4.4.3 Dealing with the Unfixed Routing Path of a Flow 46
4.5 Performance Evaluation 47
4.5.1 Experiment 1: Simple Configuration 47
4.5.2 Experiment 2: Parking-lot Configuration 49
4.5.3 Experiment 3: VBR Traffic 53
4.6 Chapter Summary 61
5 Multi-Level Fair Queueing (MLFQ): An Efficient Strategy for Weighted Fair Bandwidth Sharing 62
5.1 Related Studies 65
5.1.1 Brief Review of CSFQ 65
5.1.2 Brief Review of RFQ 66
5.2 Multi-Level Fair Queueing 67
5.2.1 Motivation 67
5.2.2 Behavior of an Edge Router 70
5.2.3 Behavior of a Core Router 70
5.2.4 Comparison Among CSFQ, RFQ and MLFQ 75
5.3 Performance Evaluation 76
5.3.1 Experiment 1: A Single Congested Link 76
5.3.2 Experiment 2: Multiple Congested Links 84
5.3.3 Experiment 3: Weighted MLFQ 84
5.3.4 Experiment 4: Performance Improvement for Layer-Encoded Applications 85
5.4 Chapter Summary 88
6 Providing Service Differentiation Based on Virtual Flows 90
6.1 Proposed Approach 91
6.1.1 Network Model 91
6.1.2 Definition of Virtual Flow 92
6.1.3 Behavior of an Edge Router 93
6.1.4 Behavior of a Core Router 94
6.1.5 A Simple Example Using the Proposed Approach 96
6.2 Implementation Issues 101
6.3 Analytical Argument of Convergence to Weighted Proportional Fairness of Rate Allocations 102
6.4 Performance Evaluation 110
6.4.1 Experiment 1: Basic Behavior of the Proposed Approach 111
6.4.2 Experiment 2: Improvement of Network Throughput 113
6.4.3 Experiment 3: Impact of Multiple Congested Nodes 115
6.4.4 Experiment 4: Performance of an ON-OFF Source 117
6.5 Chapter Summary 119
7 Conclusions and Future Work 121
7.1 Summary of Contributions 121
7.2 Future Work 123
A Pseudo code of MLFQ 124
Bibliography 128
Curriculum Vitae 135
Publication List 137

[1] S. Floyd and K. Fall, "Promoting the use of end-to-end congestion control in the Internet," IEEE/ACM Trans. Networking, vol.7, pp.458-472, Aug. 1999.
[2] R. Braden, D. Clark, and S. Shenker, "Integrated services in the Internet architecture: An overview," IETF RFC 1633, June 1994.
[3] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource reservation protocol (RSVP) - Version 1 functional specification," IETF RFC 2205, Sept. 1997.
[4] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated services," IETF RFC 2475, Dec. 1998.
[5] E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol lable switching architecture," IETF RFC 3031, Jan. 2001.
[6] D. O. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, "Overview and principles of internet traAc engineering." Internet Draft, draft-ietf-tewg-principles-06.txt, Aug. 2001.
[7] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus, "Requirements for traffic engineering over MPLS," IETF RFC 2702, Sept. 1999.
[8] E. Crawley et al., "A framework for QoS-based routing in the Internet," IETF RFC 2386, Aug. 1998.
[9] X. Xiao and L. M. Ni, "Intetnet QoS: A big picture," IEEE Network, pp.8-18, March/April 1999.
[10] J. Crowcroft and P. Oechslin, "Differentiated end-to-end Internet services using a weighted proportional fair sharing TCP," ACM Computer Communication Review, vol.28, pp.53-69, July 1998.
[11] T. Nandagopal, T. E. Kim, P. Sinha, and V. Bharghavan, Service differentiation through end-to-end rate control in low bandwidth wireless packet networks," in Proc. of IEEE MoMuC, pp.211-220, 1999.
[12] I. Stoica, S. Shenker, and H. Zhang, "Core-stateless fair queueing: Achieving approximately fair bandwidth allocations in high speed networks," in Proc. of ACM SIGCOMM, pp.118-130, 1998.
[13] Z. Cao, Z. Wang, and E. Zegura, "Rainbow fair queueing: Fair bandwidth sharing without per-flow state," in Proc. of IEEE INFOCOM, pp.922-931, 2000.
[14] G. Karlsson, "Asynchronous transfer of video," IEEE Communications Magazine, pp.118-126, Aug. 1996.
[15] M. Baldi and Y. Ofek, "End-to-end delay analysis of video-conferencing over packet switched networks," IEEE/ACM Trans. Networking, vol.4, no.8, pp.479-492, 2000.
[16] A. Tam, "How to survive as an ISP," in Networld Interop, 1997.
[17] S. Shenker and C. Patrige, "Specification of guaranteed quality of service," IETF RFC 2212, Sept. 1997.
[18] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: a new resource ReSerVation Protocol," IEEE Network, vol.7, pp.8-18, Sept. 1993.
[19] J. Wroclawski, "The use of RSVP with IETF Integrated Services," IETF RFC 2210, Sept. 1997.
[20] J. Wroclawski, "Specification of the controlled-load network element service," IETF RFC 2211, Sept. 1997.
[21] K. Nichols, S. Blake, F. Baker, and D. Black, "Definition of the Differentiated Services field (DS field) in the IPv4 and IPv6 headers," IETF RFC 2474, Dec. 1998.
[22] J. Postel, "Internet protocol," IETF RFC 791, Sept. 1981.
[23] J. Reynolds and J. Postel, "Assigned numbers," IETF RFC 1340, July 1992.
[24] P. Almquist, "Type of service in the Internet protocol suite," IETF RFC 1349, July 1992.
[25] S. Deering and R. Hinden, "Internet protocol, version 6 (IPv6) specification," IETF RFC 2460, Dec. 1998.
[26] K. Nichols, V. Jacobson, and L. Zhang, "A two-bit differentiated services architecture for the Internet." IETF Internet Draft, draft-nichols-diff-svc-arch-01.pdf, April 1999.
[27] D. Clark and J. Wroclawski, "An approach to service allocation in the Internet." IETF Internet Draft, draft-clark-diff-svc-alloc-00.txt, 1997.
[28] J. Heinanen, F. Baker, W. Weiss, and J. Wroclawski, "Assured forwarding PHB group," IETF RFC 2597, June 1999.
[29] S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Networking, vol.1, pp.397-413, Aug. 1993.
[30] Z. Wang, "User-share differentiation (USD) scalable bandwidth allocation for differentiated services." IETF Internet Draft, draft-wang-diff-serv-usd-00.txt, Nov. 1997.
[31] D. Bertsekas and R. Gallager, Data Networks. Prentice Hall, 1992.
[32] F. P. Kelly, "Charging and rate control for elastic traffic," European Transactions on Telecommunications, vol.8, pp.33-37, 1997.
[33] F. P. Kelly, A. K. Maulloo and D. K. H. Tan, "Rate control in communication networks: shadow prices, proportional fairness and stability," Journal of the Operational Research Society, vol.49, pp.237-252, 1998.
[34] J. Postel, "Transmission control protocol," IETF RFC 793, Sept. 1981.
[35] V. Jacobson, "Congestion avoidance and control," in Proc. of ACM SIGCOMM, pp.314-329, Aug. 1988.
[36] P. Sinha, T. Nandagopal, and N. Venkitaraman, "WTCP: A reliable transport protocol for wireless wide-area networks," in Proc. of 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp.231-241, 1999.
[37] L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion avoidance on a global Internet," IEEE J. Select. Areas Commun., pp.1465-1480, Oct. 1995.
[38] S. Keshav, "A control theoretic approach to flow control," in Proc. of ACM SIGCOMM, pp.189-201, 1991.
[39] V. Jacobson, R. Braden, and D. Borman, "TCP extensions for high performance," IETF RFC 1323, May 1992.
[40] W. R. Stevens, "TCP slow start congestion avoidance, fast retransmission and fast recovery algorithms," IETF RFC 2001, Jan. 1997.
[41] J. C. Hoe, "Improving the start-up behavior of a congestion control scheme for TCP," in Proc. of ACM SIGCOMM, pp.270-280, 1996.
[42] M. Mathis and J. Mahdavi, "Forward acknowledgement: Refining TCP congestion control," ACM Computer Communication Review, vol.26, no.4, pp.281-291, 1996.
[43] M. Allman, H. Balakrishnan, and S. Floyd, "Enhancing TCP's loss recovery using early duplicate acknowledgement response." Internet Draft, draft-allman-tcp-lossrec-00.txt, Oct. 1999.
[44] M. Allman, S. Dawkins, D. Glover, J. Griner, D. Tran, T. Henderson, J. Heidemann, J. Touch, H. Kruse, S. Ostermann, K. Scott, and J. Semke, "Ongoing TCP research related to satellites," IETF RFC 2760, Feb. 2000.
[45] H. Balakrishnan, V. Padmanabhan, S. Seshan, S. Stemm, and R. Katz, "TCP behavior of a busy web server: analysis and improvements," in Proc. of IEEE INFOCOM, March 1998.
[46] K. Fall and S. Floyd, "Simulation-based comparisons of Tahoe, Reno, and SACK TCP," ACM Computer Communication Review, vol.26, pp. 5-21, July 1996.
[47] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, "TCP selective acknowledgement options," IETF RFC 2018, Oct. 1996.
[48] UCB/LBNL/VINT Network Simulator - ns (version 2). http://www.isi.edu/nsnam/ns/.
[49] R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. NewYork: Wiley, 1991.
[50] W. C. Feng, D. D. Kandlur, D. Saha, and K. G. Shin, "Adaptive packet marking for maintaining end-to-end throughput in a differentiated services Internet," in Proc. of International Conference on Network Protocols, pp.108-117, Oct. 1998.
[51] R. Sivakumar, T. Kim, N. Venkitaraman and V. Bharghavan, "Achieving per-foow weighted rate fairness in a core stateless network," in Proc. of IEEE Conference on Distributed Computing Systems, pp.188-196, March 2000.
[52] V. P. Kumar, T. V. Lakshman and D. Stiliadis, "Beyond best effort: Router architectures for the differentiated services of tomorrow's Internet," IEEE Communications Magazine, pp.152-164, May 1998.
[53] A. Feldmann and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. of IEEE INFOCOM, pp.1193-1202, March 2000.
[54] P. Gupta and N. McKeown, "Packet classification on multiple fields," in Proc. of ACM SIGCOMM, pp.147-160, Sept. 1999.
[55] V. Srinivasan, G. Varghese, and S. Suri, "Packet classification using tuple space search," in Proc. of ACM SIGCOMM, pp.135-146, Sept. 1999.
[56] The ATM Forum Technical Committee, "Atm forum traffic management specification version 4.1." ATM Forum AF-TM-0121.000, March 1999.
[57] J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Networking, vol.8, pp.556-567, Oct. 2000.
[58] T. Nandagopal, N. Venkitaraman, R. Sivakumar and V. Bharghavan, "Delay differentiation and adaptation in core stateless networks," in Proc. of IEEE INFOCOM, pp.421-430, 2000.
[59] B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V.Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, and L. Zhang, "Recommendations on queue management and congestion avoidance in the Internet," IETF RFC 2309, April 1998.
[60] A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," Journal of Internetworking Research and Experience, pp.3-26, Oct. 1990.
[61] P. McKenny, "Stochastic fairness queueing," in Proc. of IEEE INFOCOM, pp.733-740, 1990.
[62] A. Manin and K. Ramakrishnan, "Gateway congestion control survey," IETF RFC 1254, Aug. 1991.
[63] S. Floyd and K. Fall, "Router mechanisms to support end-to-end congestion control," tech. rep., LBL, Feb. 1997.
[64] D. Lin and R. Morris, "Dynamics of random early detection," in Proc. of ACM SIGCOMM, Sept. 1997.
[65] J. Lee, T. Kim, and S. Ko, "Motion prediction based on temporal layering for layered video coding," in Proc. of ITC-CSCC, July 1998.
[66] S. McCanne and M. Vetterli, "Joint source/channel coding for multicast packet video," in Proc. of IEEE International Conference on Image Processing, Oct. 1995.
[67] M. Vishwanath and P. Chou, "An efficient algorithm for hierarchical compression of video," in Proc. of IEEE International Conference on Image Processing, Nov. 1994.
[68] T. Kurimoto, T. Shimizu, and R. Kawamura, "Core-stateless RED algorithm for improving fairness in a best-effort network," IEICE Trans. Commun., vol.E84-B, pp.1413-1422, May 2001.
[69] CSFQ implementation in ns-2. http://www.cs.berkeley.edu/~istoica/csfq/.
[70] T. Sikora, "MPEG digital video-coding standards," IEEE Signal Processing Magazine, pp.82-100, Sept. 1997.
[71] E. Altman, T. Basar, and R. Srikant, "Multi-user rate-based flow control with action delays: A team-theoretic approach," in Proc. of 36th Conf. Decision and Control, pp.2387-2392, Dec. 1997.
[72] L. Benmohamed and S. M. Meerkov, "Feedback control of congestion in packet switching networks: The case of a single congested node," IEEE/ACM Trans. Networking, vol.1, pp.693-707, 1993.
[73] H. Ozbay, S. Kalyanaraman, and A. Ifar, "On rate-based congestion in high speed networks: Design of an H-infinity based flow controller for single bottleneck," in Proc. of Amer. Control Conf., Sept. 1998. see also http://www.ecse.rpi.edu/Homepages/shivkuma/.
[74] C. Rohrs and R. Berry, "A linear control approach to explicit rate feedback in ATM networks," in Proc. of IEEE INFOCOM, April 1997.
[75] S. Kalyanaraman, R. Jain, S. Fahmy, R. Goyal, and B. Vandalore, "The ERICA switch algorithm for ABR traffic management in ATM networks," IEEE/ACM Trans. Networking, vol.8, pp.87-98, Feb. 2000.
[76] A. Arora and M. Gouda, "Closure and convergence-A foundation of fault-tolerant computing," IEEE Trans. Software Eng., vol.19, pp.1015-1027, Oct. 1993.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊