跳到主要內容

臺灣博碩士論文加值系統

(3.87.250.158) 您好!臺灣時間:2022/01/25 19:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:姜文忠
研究生(外文):Wen-Chung Chiang
論文名稱:以速率為基礎的封包排程演算法其局部延遲配置之研究
論文名稱(外文):The Study on Local Delay Allocation for Rate-based Packet Scheduling Algorithms
指導教授:朱延平朱延平引用關係
指導教授(外文):Yen-Ping Chu
學位類別:博士
校院名稱:國立中興大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:德文
論文頁數:141
中文關鍵詞:服務品質保證封包排程演算法傳輸延遲分配交通模型平均分配策略剩餘頻寬分配策略
外文關鍵詞:quality of servicepacket scheduling algorithmdelay allocationtraffic modelequal allocation policyremained capacity allocation policy
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1350
  • 評分評分:
  • 下載下載:288
  • 收藏至我的研究室書目清單書目收藏:1
為了能提供多媒體應用系統(如視訊會議、隨選視訊、網路電話等等)即時連續的資料傳輸,網路必須能提供連線包括傳輸延遲(delay)、資料流量(throughput)、傳輸延遲變異程度(delay-jitter)與公平性(fairness)的服務品質(quality of service)保證。未來的高速網路亦必須提供不同等級的服務品質,來滿足各種網路應用程式的需求。在探討如何提供服務品質保證的研究中,封包排程演算法(packet scheduling algorithm)的設計是一重要的課題,在封包交換網路上,各資料封包來自不同的連線,且在交換節點內互相影響,封包排程演算法能控制封包被服務的順序,並決定每個連線在交換節點的相互關係。
對於多數要求高服務品質的應用程式,網路必須能對每個連線的封包提供明確之最大延遲保證,稱為限制延遲服務(bounded delay service)。為了提供此服務品質的保證,通常會對每個交換節點採用資源保留的方式。一般使用者僅會關心他的應用程式在網路上傳輸時,整體連線(end-to-end)的總服務品質。因此,如何將整體連線的總服務品質需求,分配對應到每個區域性的交換節點上,並藉以提昇整體網路的使用率,將是網路設計者所需考量的問題。
在本研究的第一個部份,提出如何在交換節點以公平性排班(fair queuing)演算法所進行的傳輸延遲分配(delay allocation)策略。首先,我們使用Leaky-bucket的(s,r)作為交通模型(traffic model)來描述應用程式的來源傳輸特性,可依此進一步推導出連線延遲上限(delay bound)與允許連線(allowable connections)個數的關係。同時亦發現,不同分配策略將導致不同的網路服務效能。此外,我們也引用一個可分析不同分配策略的評估模式,針對不同的連線服務需求與不同網路服務狀態,比較平均分配策略(equal allocation policy)與剩餘頻寬分配策略(remained capacity allocation policy)的網路服務效能差異,藉以證明分配策略選取的正確性與有效性。
在本研究的第二個部份,依第一部份推導出的結果,進一步歸納出一個可運用於以傳輸速率為基礎的排程演算法,並進一步計算網路可提供的最大連線數的通用型模組。以PGPS、SCFQ及SFQ等排程演算法,分別應用於平均分配法則與剩餘頻寬分配法則,並在不同的網路條件下進行連線的數值分析比較。

In order to support the requirements for the real-time transmission of multimedia application system, such as video conference, video on demand, voice over IP and so on, multi-service packet-switching networks must provide service guarantees to the connections, including guarantees on network delay, throughput, network delay-jitter, loss, and fairness. Anyhow, one of the most important issues in providing performance guaranteed service is the design of the packet-scheduling algorithm at each switching node. In packet-switched networks, packets come from different connections interact with each other at switching node. The packet-scheduling algorithms control the sequence in which packets are serviced and determine the relation of interaction at each connection.
In addition, for the most demanding applications, the network must offer a service, which can provide deterministic guarantees for the maximum delay of packets from all connections, referred as bounded delay service. To provide guaranteed service, resources have to be reserved within the network switching nodes. A typical user is concerned only with the quality of service of a network on an end-to-end basis. Therefore, how the end-to-end requirements are mapped into the local switching nodes requirement and the maximum network utilization is a critical function of the network internal design.
In the first part of this thesis, we propose a general framework based on the mapping of the end-to-end quality of service requirement into the local switching node quality of service requirements. We use the delay allocation policies under fair queuing scheduling algorithm at each switching node. With Leaky-bucket, (s,r), as the input traffic model, we derived a formula for delay bound and the number of connections. At the same time, we found that the delay bound as the quality of service metric; there is a significant difference in the performance of allocation policies. We also reference an evaluation strategy to analyze equal allocation policy and remaining capacity allocation policy. The numerical results compare these two allocation policies and show the correctness and efficiency.
In the second part of this thesis, we refer the result of first part to induce a general model for rate-based scheduling algorithms. This model can be applied for the rate-based packet scheduling algorithms, including Packet-by-packet Generalized Processor Sharing (PGPS), Self-Clocked Fair Queuing (SCFQ), and Starting-time Fair Queuing (SFQ). We apply two allocation policies, equal allocation and remaining capacity allocation to construct this model, and derive the relation between the network utilization and the allocation policy through mathematical analysis.

1. Introduction
2. Background and Previous Approaches
3. Call Admission and End-to-end Delay Allocation for Fair Queuing Networks
4. A Generalized Delay Allocation Model for Rate-based Packet Scheduling Algorithms
5. Conclusions and Future Works

[1] A. Banerjea and S. Keshav. Queuing delays in rate controlled networks. In Proc. of IEEE INFOCOM, pp. 547-556, 1993.
[2] A. Banerjea, D. Ferrari, B. A. Mah, M. Moran, D. C. Verma, and H. Zhang. The Tenet real time protocol suite: design, implementation, and experience. In IEEE/ACM Trans. on Networking, Vol.4, No. 1, pp. 1-10, Feb., 1996.
[3] A. Birman, V. Firoiu, R. Gu’erin, and D. Kandlur. Provisioning of RSVP-Based Services over a Large ATM Network. Technical Report RC 20250, IBM T.J Waston Research Center, Nov., 1995.
[4] A. Demers. S. Keshav, and S. Shenker. Analysis and simulation of fair queuing algorithm. In Journal of Internetworking Research and Experience, pp.3-26, Oct., 1990.
[5] A. Elwalid, D. Mitra, and R. Wentworth. A new approach for allocating buffers and bandwidth to heterogeneous regulated traffic in an ATM node. IEEE Journal on Selected Area in Comm., Vol. 13, No., 6, pp. 1115-1127, Aug., 1995.
[6] A. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple-node case. IEEE/ACM Trans. on Networking ", Vol. 2, No. 2, pp.137-150, Apr., 1994.
[7] A. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Trans. on Networking, Vol. 2, No. 2, pp.344-357, Jun., 1993.
[8] A. R. Reibman and A. W. Berger. Traffic descriptors for VBR video teleconferencing over ATM networks. IEEE/ACM Trans. on Networking, Vol. 3, No. 3, pp. 329-339, Jun., 1995.
[9] A. S. Ayad, K.M.F. Elsayed, and M. T. El-hadidi. Local Resource Allocation for Providing End to End Delay Guarantees in ATM Networks Using PGPS Scheduling, International symposium on Modeling. Analysis and Simulation of Computer and Telecommunication System, pp. 30-37, 1999
[10] ATM Forum. ATM forum traffic management specification version 4.0, contribution 95-0013R11, Mar., 1996.
[11] ATM Forum. ATM user-network interface specification version 3.0, Prentice-Hall, 1993
[12] C. Aurrecoechea, A. T. Campbell, L. Hauw. A Survey of QoS Architectures. Multimedia System (1998) 6: 138-151
[13] C. Kalmanek, H. Kanakia, and S. Keshav. Rate controlled servers for very high-speed networks. Proc. of IEEE GLOBECOM, pp. 300.3.1-300.3.9, Dec., 1990
[14] C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne. Real-time communication in packet switched network. Proc. of IEEE, Vol. 81, No. 1, pp. 122-139, Jan., 1994.
[15] C. Partridge. Gigabit Networking. Addison Wesley, 1993.
[16] C. Toplcic. Experimental Internet Stream Protocol: Version 2 (ST-II). Internet RFC 1190, Oct., 1990.
[17] CCITT Draft Recommendation I.371. Traffic control and resources management in B-ISDN, Dec., 1991.
[18] D. A. Anderson. Meta-scheduling for Continuous Media. ACM Transactions on Computer Systems, 11(3). Aug., 1993.
[19] D. Clark, S. Shenker, and L. Zhang, Supporting real-time applications in an integrated service packet network: Architecture and mechanism, Proceeding of ACM SIGCOMM, pp.14-16, Baltimore, Maryland, Aug., 1992.
[20] D. Ferrari, A. Banerjea, and H. Zhang. Network support for multimedia: a discussion of the Tenet approach. Computer Network and ISDN Systems, Vol.26, No. 10, pp. 1167-1180, Jul., 1994.
[21] D. Ferrari, and D. Verma. A scheme for real time channel establishment in wild area networks. IEEE Journal on Selected Area in Comm., Vol. 8, No. 3, pp.368-379, Apr., 1990.
[22] D. Ferrari. Client requirement for real-time communication services. IEEE Comm. Mag., 28(11), pp.65-72, Nov., 1990.
[23] D. Ferrari. Real time communication in an inter-network. Journal of High Speed Networks, Vol. 1, No. 1, pp. 79-103, 1992.
[24] D. Kandlur, K. Shin, and D. Ferrari. Real time communication in multi-hop networks. Proc. of 11th International Conference on Distributed Computer Systems May, 1991.
[25] D. Le Gall, MPEG: a video compression standard for multimedia application. Communication of ACM, Vol. 34, No. 4, pp. 46-58, Apr., 1991.
[26] D. Stiliadis and A. Verma. Efficient fair queuing algorithm for packet switched networks. IEEE/ACM Trans. on Networking, Vol. 6, No. 2, pp. 175-185, Apr., 1998
[27] D. Stiliadis and A. Verma. Latency-rate servers: a general model for analysis of traffic scheduling algorithms. IEEE/ACM Trans. on Networking, pp. 611-624, Vol. 6, No. 5, Oct., 1998
[28] D. Stiliadis and A. Verma. Rate-proportional servers: a design methodology for fair queuing. IEEE/ACM Trans. on Networking, Vol. 6, No. 2, pp. 164-174, Apr., 1998
[29] D. Stiliadis. Traffic scheduling in packet-switched networks: analysis, design and implementation, PhD dissertation. Univ. of California at Santa Cruz, 1996.
[30] D. Verma. Guaranteed performance communication in high-speed networks, PhD Dissertation. Univ. of California at Berkeley, Nov., 1991.
[31] D. Verma, H. Zhang, and D. Ferrari. Guaranteeing delay jitter bounds in packet switching networks. Proc. og TRICOMM, pp. 35-46, Apr., 1991.
[32] E. Crawley, R. Nair, B. Rajagopalan, and H Sandick. A Framework for QoS-base Routing in the Internet. Internet Draft, Apr., 1998.
[33] E. Knightly, D. Wrege, J. Liebeherr and H. Zhang. Fundamental limits and tradeoffs for providing deterministic guarantees to VBR video traffic. IEEE/ACM Trans. On Networking, Vol. 4, No.3, pp.352-362, Jun., 1996.
[34] E. P. Rathgeb. Modeling and performance comparison of policing mechanisms for ATM networks. IEEE Journal on Selected Area in Comm., Vol. 9, No. 4, pp.325-341, Apr., 1991.
[35] E. P. Rathgeb. Policing of realistic VBR video traffic in an ATM network. International Journal of Digital and Analog Comm. System, Vol. 6, pp. 213-226, 1993.
[36] E. W. knightly and H. Zhang. Traffic characterization and switch utilization using deterministic bounding interval dependent traffic model. Proc. of INFOCOM, pp. 1137-1145, Apr., 1995.
[37] E. W. Knightly, D. E. Wrege, J Liebeherr, and H. Zhang. Fundamental limits and tradeoffs of providing deterministic guarantees to VBR video traffic. Proc. of ACM SIGMETRICS, pp. 98-107, May, 1995.
[38] E. W. Knightly. H-BIND: A new approach to providing statistical performance guarantees to VBR traffic. Proc. of IEEE Infocom., pp. 1091-1099, Mar., 1996.
[39] E. W. Knightly. Traffic models and admission control for integrated services networks, PhD thesis. University of California at Berkeley May, 1996.
[40] G. G. Xie and S. S. Lam. Delay guarantee of Virtual Clock server. IEEE/ACM Trans. on Networking, Vol. 3, No. 6, pp.683-689, Dec., 1995.
[41] H. Sariowan. A Service-Curve Approach to Performance Guarantees in Integrated-Service Networks, Ph.D. thesis. Department of Electrical and Computer Engineering, UCSD, Jun., 1996.
[42] H. Sariowan, R. L. Cruz, and G. C. Polyzos. Scheduling for Quality of Service Guarantees via Service Curves, Proc. of the International Conference on Computer Communications and Networks (ICCCN) 1995. Las Vegas, September 20-23, pp. 512-520, 1995.
[43] H. Schulzrinne. Voice Communication Across the Internet: A Network Voice Terminal. Technical Report TR 92-50. Department of Computer Science, University of Massachusetts, Amherst, Jul., 1992.
[44] H. Zhang and D. Ferrari. Improving utilization for deterministic service in multimedia communication. In 1994 International Conference on Multimedia Computing and Systems, pp.295-304, Boston, MA, May, 1994.
[45] H. Zhang and D. Ferrari. Rate-controlled service disciplines. Journal of High Speed Networks, 3(4), PP.389-412, 1994.
[46] H. Zhang and D. Ferrari. Rate-controlled static priority queuing. Proc. of IEEE INFOCOM, pp. 227-236, Apr., 1993.
[47] H. Zhang and S. Keshav. Comparison of Rate-Based Service Disciplines. In Proceedings of ACM Sigcomm, pp. 113-121, Aug., 1991
[48] H. Zhang. Service disciplines for guaranteed performance service in packet- switching networks. Proceeding of IEEE, 83(10): pp.1374-1399, Oct., 1995.
[49] H. Zhang, and E. W. Knightly. Providing end-to-end statistical performance guarantees with bounding interval dependent stochastic models. Proc. of ACM SIGMETRICS, pp. 211-220, May, 1994.
[50] H. Zhang. Providing end-to-end performance guarantees using non-work-conserving disciplines. Computer Communication: special issue on system support for multimedia networking, Vol. 18, No. 10, Oct., 1995.
[51] J. Kurose. On computing per-session performance bounds in high-speed multi-hop computer networks. Proc. of ACM SIGMETRICS, 1992.
[52] J. Kurose. Open issues and challenges in providing quality of service guaranteed in high-speed networks. ACM Comp. Comm. Review, 23(1): pp. 6-15, Jan., 1993.
[53] J. Leibeherr, D. E. Wrege, and D. Ferrari. Exact admission control in networks with bounded delay services. IEEE/ACM Trans. on networking, Dec., 1996.
[54] J. Liebeherr. Multimedia Networks: Issues and Challenges. IEEE Computer, Vol. 28, No. 4, pp.68-69, Apr., 1993.
[55] J. S. Turner. Managing bandwidth in ATM networks with burst traffic. IEEE Network, Vol. 6, No. 5, pp.50-68, Sep., 1992.
[56] J. Turner. New directions in communications (or which way to the information age?) . IEEE Comm. Mag., Vol. 24, pp.8-15, Oct., 1986.
[57] L. Dittman, S. B. Jacobson, and K. Moth. Flow enforcement algorithm for ATM networks. IEEE Journal on Selected Area in Comm., Vol. 9, No. 3, pp.343-350, Apr., 1991.
[58] L. Georgiadis, R. Guerin, and A Parekh. Optimal multiplexing on a single link: delay and buffer requirements. Proc. of IEEE INFOCOM, pp. 524-532, Jun., 1994.
[59] L. Georgiadis, R. Guerin, and V. Peris, and K. N. Sivarajan. Efficient network QOS provisioning based on per node traffic shaping. IEEE/ACM Trans. on Networking, Vol.4, No.4, pp.482-501, Aug. 1996.
[60] L. Georgiadis, R. Guerin, and V. Peris, and R. Rajan. Efficient support of delay and rate guarantees in an Internet. Proc. of ACM SIGCOMM, 1996.
[61] L. Kleinrock. Queuing systems. John Wiley and Sons, 1975.
[62] L. Kleinrock. Queuing systems. Vol. 2: computer applications, Wiley, 1976.
[63] L. Zhang. Virtual Clock: a new traffic control algorithm for packet switching networks. ACM Trans. on Comp. Systems, Vol. 9, No.1, pp.3-26, 1990.
[64] L. Zhang, S. E. Deering, S. Extrin, S. Shenker, and D. Zappala. RSVP: A New Resource Reservation Protocol. IEEE Network, 7(5):8-18, Sep., 1993.
[65] M. Krunz and H. Hughes. A traffic model for MPEG-Coded VBR streams. Proc. Of ACM SIGMETRICS, pp. 47-55, May, 1995.
[66] N. R. Figueira and J. Pasquale. An upper bound on delay for the Virtual Clock service discipline. IEEE/ACM Trans. on Networking, Vol.3, No. 4, Aug., 1995.
[67] O. Yaron and M. Sidi. Calculating performance bounds in communication networks. Proc. of INFOCOM, pp. 539-546, Apr., 1993.
[68] P. E. Boyer, F. M. Guillemin, M. J. Servel, and J. P. Coudreuse. Spacing cells protects and enhances utilization of ATM network links. IEEE Network, Vol. 6, No. 5, pp. 38-49, Sep., 1992.
[69] P. Goyal and H. M. Vin. Generalized guaranteed rate scheduling algorithms: A framework. IEEE/ACM Trans. on Networking, Vol. 5, No. 4, pp.561-571, Aug., 1997.
[70] P. Goyal, S. Lam and H. Vin. Start-time Fair Queuing: a scheduling algorithm for integrated services packet switching networks. Proceedings of SIGCOMM, 1996.
[71] P. Goyal, S. Lam and H. Vin. Start-time Fair Queuing: a scheduling algorithm for integrated services packet switching networks. Technical report TR-96-02, Department of Computer Sciences, and University of Texas at Austin.
[72] P. Goyal, S. Lam and H. Vin. Determining end-to-end delay bounds in heterogeneous networks. Proceeding of the 5th International Workshop on Network and Operating System Support For Digital Audio and Video, pp. 287-298, Durham, New Hampshire, Apr., 1995.
[73] Private Network-Network Interface Specification v1.0 (PNNI). ATM Forum Technical Committee, Mar., 1996.
[74] Q. Zheng and K. Shin. On the ability of establishing real-time channel in point-to-point packet-switching networks. IEEE Trans. on Comm., pp. 1096-1105, Mar.,1994.
[75] R. Agrawal and R. Rajan. Performance bounds for guaranteed and adaptive service. IBM RC 20649, 1996, Also in Proc. 34th Allerton Conf. on Comm., Cont. and Comp., Monticello, IL, Oct., 1996.
[76] R. Cruz. Service burstiness and dynamic burstiness measures: A framework. Journal of High Speed Networks, Vol. 1, No. 2, pp.105-127, 1992.
[77] R. Frederik. nv. Manual Pages. Verox Palo Alto Research Center.
[78] R. Guerin and A. Orda. QoS-Based Routing in Networks with Inaccurate Information: Theory and Algorithms. In Proceedings of the IEEE INFOCOM’97, pages 75-83, Kobe, Japan, Apr., 1997.
[79] R. Guerin, H. Ahmadi, and M. Naghshineh. Equivalent capacity and its application to bandwidth allocation in high-speed networks. IEEE JSAC, Vol 9, pp.968-981, 1991.
[80] R. Guerin, S. Kamat, A Orsa. T. Pezygienda, and D. Williams. QoS routing mechanisms and OSPF extensions. Internet Draft Jan., 1998.
[81] R. Jain. Congestion control and traffic management in ATM networks: recent advances and a survey. Comp. Networks and ISDN Sys., Oct., 1996.
[82] R. L. Cruz. A Calculus for network delay, part I: network elements in isolation. IEEE Trans. on Information Theory, Vol. 36, No. 1, pp. 114-131, Jan., 1991.
[83] R. L. Cruz. A Calculus for network delay, part II: network analysis. IEEE Trans. on Information Theory, Vol. 36, No. 1, pp. 132-141, Jan., 1991.
[84] R. L. Cruz. Quality of service guarantees in virtual circuit switched networks. IEEE Journal on Selected Area in Comm., Vol.13, No. 6, Aug., 1995.
[85] R. Nagarajan and J. Kurose. On defining, computing and guaranteeing quality-of-service in high-speed networks. In IEEE Infocom'92, pp.8C.2.1-8C.2.10, May, 1992.
[86] R. Nagarajan, J. Kurose and D. Towsley. Local allocation of end-to-end quality-of-service in high-speed networks. In IFIP TC6 Task Group / WG 6.4 International Workshop on Performance of Comm. Systems, pp.99-118, Martinique, Jan., 1993.
[87] S. Shenker and J. Wroclawski. Network element specification template. IETF Internet-Draft, Jun., 1995.
[88] S. Golestani. A self-clocked fair queuing scheme for broadband application. Proceedings of IEEE INFOCOM'94, pp.636-646, Toronto, Jun., 1994.
[89] S. Golestani. Network delay analysis of a class of fair queuing algorithms. IEEE Journal on Selected Areas in Comm., Vol. 13, pp.1057-1070, Aug., 1995.
[90] S. Golestani,. A Stop-and-Go queuing framework for congestion management. Proc. Of ACM SIGCOMM, pp.8-18, Sep., 1990.
[91] S. Golestani. Congestion-free transmission of real-time traffic in packet networks. Proc. of INFOCOM, pp. 527-542, Jun., 1990.
[92] S. J. Golestani. A framing strategy for congestion management. IEEE Journal on Selected Area in Comm., Vol. 9, No. 7, pp. 1064-1077, Sep., 1991.
[93] S. J. Golestani., A Self-Clocked Fair Queuing Scheme for High-Speed Application. In Proceedings ACM Sigcomm'98, Sep., 1998.
[94] S. Keshav. Congestion control for computer networks. PhD thesis, Univ. of California at Berkeley, 1991.
[95] Schulz-Rinne, H., et al. Congestion control by selecting packet discarding for real-time traffic in high-speed networks. Proc. of INFOCOM, pp. 543-550, Jun., 1990.
[96] V Froiu and D. Towsley. Call Admission and Resource Reservation for Multicast Sessions. Proceeding of the IEEE INFCOM’96, San Francisco, CA, Apr., 1996.
[97] V. Jacobson and S. McCanne. Vat. Manual Pages, Lawrence Berkeley Laboratory, Berkeley, CA.
[98] Y.P. Chu, E.H. Hwang, K.C. Lin, and C.H. Chin. Local allocation of end-to end delay requirement. IEICE Trans. Communication, E82-B, (9), pp.1380-1387, 1999.
[99] Y.P. Chu, C.H. Chen, and K.C. Lin. Call Admission and Allocation for Delay Guarantees. IEICE Trans. Communication, E84-D, (8), pp.1039-1047, 2001.
[100] Z. Wang and J. Crowcroft. Quality-of-service Routing for Supporting Multimedia Applications. IEEE JSAC, 14(7): 1288-1234, Sep., 1996.
[101] Z. Zhand, D. Towsley, and J. Kurose. Statistical analysis of generalized processor sharing scheduling discipline. Proc. of ACM SIGCOMM, 1994.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top