臺灣博碩士論文加值系統

隨著目前網路的蓬勃發展以及多媒體時代的來臨，對於各種的應用程式如：視訊會議（video conference）、遠距教學…等，所要求的服務品質（Quality of Service），除了直接地增加網路頻寬外，更重要的是如何配置網路的頻寬及限制延遲時間來符合各式應用程式的要求，傳統的交換機封包處理機制難以應付多樣服務交求，我將設計一排程器（Scheduler）針對不同的優先權的資料流（flow）給於不同的服務。
在排程演算法中均面臨在計算timestamps、system potential以及決定封包傳送順序上的複雜度，另外對於演算法的優劣，從演算法要求的特性：1)minimum service rate、2)deterministic delay bounds、3)fairness service以及其對封包產生的影響包括：1)Delay、2)Jitter、3)Throughout、4)Loss rate，以上各項效能本論文均提供模擬結果與分析。
目前封包排程演算法中，WFQ擁有最佳的的效能包括：1)最小延遲時間，及2)公平性等，但是由於計算複雜度為 ，N為連結的數目，基於以上的考量，本論文選擇仿效WFQ的Self-Clock Fair Queuing（SCFQ），其各項效能近似WFQ，計算複雜度只 ，另外在SCFQ的演算法中使用截短長度欄位（shorten length field）以及使用特定的權重（Weight）分配頻寬進而減少計算time stamp的時間，另外也分別使用：1）分區比較法（Zone Compare）以及2）time stamp搜尋引擎（time stamp search engine）這兩種技巧克服roll-over的問題並決定封包傳送順序，集合這些方法來使排程器可應用於高速網路。

Meeting quality of service (QoS) requirements for various services in networks has been very challenging to network designers. Besides of increase the bandwidth of network directly, it must allocate bandwidth and bound delay to meet the requirements of each application. The traditional scheduling mechanism can not meet differentiated service requirement. We will develop the scheduler, which can provide differentiated service for each priority flow.
There are two major complexities about scheduler:1)calculating time stamps and system potential; and 2)the packet sorting to determine the transmission order. we would evaluate the scheduler algorithm from three properties: 1)minimum service rate、2)deterministic delay bounds and 3)fairness service, and the four influences on traffic: 1)Delay, 2)Jitter, 3)Throughout and 4)Loss rate. This paper provides performance analysis and the VLSI architecture design of the packet scheduler.
Currently, WFQ has excellent performances which includes minimum delay bound and fairness, but it calculating complexity is , where N is the number of session. Because of the high complexity, we adopt Self-Clock Fair Queuing（SCFQ） which emulates WFQ, and its performance approximates to WFO and the calculating complexity is . For the hardware implement, we use “shorten length field” and “artificial weights” to reduce calculating time. We also adopt two skills: 1）Zone Compare, and 2）time stamp search engine, to determine the transmission order. These two skills can be implemented with RAM-base CAM-base in hardware design separately, and them can overcome roll-over problem. By the above skills, the VLSI architectures for scheduler are proposed to support high speed network scheduling.

中文摘要 -----------------------------------------------------i
英文摘要 ----------------------------------------------------ii
誌 謝 ----------------------------------------------------iv
本文目錄 -----------------------------------------------------v
附圖目錄 ---------------------------------------------------vii
附表目錄 -----------------------------------------------------x
一、緒論-------------------------------------------------------1
1.1 研究動機------------------------------------------------1
1.2 研究簡介------------------------------------------------2
1.3 研究內容------------------------------------------------3
1.4 內容編排------------------------------------------------4
二、二、排程演算法介紹與改善-----------------------------------5
2.1 排程演算法（Queuing algorithm）-------------------------5
2.1.1 演算法的要求------------------------------------------5
2.1.2 演算法的分類------------------------------------------5
2.1.3 演算法的介紹------------------------------------------6
2.1.4 演算法效能比較與優缺點-------------------------------14
2.2 時間要求及排程簡化----------------------------------------16
2.2.1 封包排程時間限制-------------------------------------16
2.2.2 有效長度及分類式排程--------------------------------17
三、 模擬結果-------------------------------------------------20
3.1 模擬架構（Simulation Architecture）--------------------20
3.1.1 封包產生樣式（Packet generate pattern）--------------20
3.1.2 網路拓撲（network topology）-------------------------22
3.2 模擬實驗（Simulation Experiment）----------------------23
3.3 模擬結果（Simulation Result）-----------------------------24
四、硬體實現--------------------------------------------------56
4.1 RAM-base 排程器（Scheduler）---------------------------56
4.1.1 Time stamp位元長度（bit length）---------------------56
4.1.2 架構實現---------------------------------------------60
4.2 CAM-base 排程器（Scheduler）---------------------------62
4.2.1 Time Domain搜尋觀念----------------------------------62
4.2.2 Time stamp位元長度（bit length）---------------------64
4.2.3 Time domain分割--------------------------------------64
4.2.4 搜尋技巧（Search Mechanism）-----------------------66
4.2.4.1 二元搜尋法（Binary Search Algorithm）---------------66
4.2.4.2 Back-Forth 搜尋演算法（Search Algorithm）-----------69
4.2.4.3 Top-down搜尋演算法（Search Algorithm）--------------71
4.2.5 搜尋演算法的比較分析---------------------------------73
4.2.6 CAM (Content Addressable Memory)---------------------73
4.2.7 架構實現---------------------------------------------74
4.3 CAM Cell Design ------------------------------------76
4.3.1 Tradition CAM Cell-----------------------------------76
4.3.2 平行CAM Cell-----------------------------------------77
4.4 RAM-base、CAM-base架構比較--------------------------------79
五、結論------------------------------------------------------80
參考文獻------------------------------------------------------81

[1] A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: the single-node case,” IEEE/ACM Transactions on Networking, Vol. 1, pp. 344 -357, June 1993.
[2] D. C. Stephens and H. Zhang, “Implementing distributed packet fair queueing in a scalable switch architecture,” in Proc. IEEE INFOCOM 98, pp. 282-290 1998.
[3] H. J. Chao, Yau-Ren Jenq, Xiaolei Guo and C.H. Lam, “Design of packet-fair queuing schedulers using a RAM-based searching engine,” IEEE Journal on Communications, Vol. 17, pp. 1105-1126, June 1999.
[4] A. Hashmi, A. Pimplapure and T. Znati, “Comparative analysis of scheduling algorithms for integrated service networks Simulation,” in Proc. 31st 1998.
[5] S. W. Moon, K. G. Shin, and J. Rexford, “Scalable hardware priority queue architectures for high-speed packet switches,” Real-Time Technology and Applications Symposium, in Proc. pp. 203-212, Third IEEE Published: 1997.
[6] H. J. Chao, H. Cheng, Y. R. Jeng, and D. Jeong, ” Design of a generalized priority queue manager for ATM switches,” IEEE J. Select. Areas Commun., Volume: 15, pp. 867-880, June 1997.
[7] S. J. Golestani, “A self-clocked fair queueing scheme for broadband applications,” in Proc. IEEE INFOCOM 94, Toronto, Ont., June, 1994.
[8] Hui Zhang, “Service disciplines for guaranteed performance service in packet-switching networks,” Proceedings of the IEEE 83(10), pp. 1374-1396, Oct. 1995.
[9] A. Varma and D. Stiliadis, “Hardware implementation of fair queuing algorithms for asynchronous transfer mode networks” IEEE Communications Magazine Volume: 3, pp. 54 - 68, Dec. 1997.
[10] G. Mamais, M. Markaki, G. Politis and I. S. Venieris, “Efficient buffer management and scheduling in a combined IntServ and DiffServ architecture: a performance study ATM” 2nd International Conference on, pp. 236 —242, 1999
[11] R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin, “Resource ReSerVation Protocol (RSVP) — Version1 Functional Specification”, RFC 2205, September 1997.
[12] Kathleen Nichols and Steven Blake, “Differentiated Services Operational Model and Definitions” Internet Draft, February 1998.
[13] S. Blake et al., “An Architecture for Differentiated Services,” IETF RFC 2475, Dec. 1998
[14] K.Nichols et al., “Definition of the Differentiated Service Field (DS Filed) in the IPv4 and IPv6 Headers,” IETF RFC 2474, Dec 1998.
[15] J. Heinanen et al., “Assure Forwarding PHB Group,” RFC2957, June 1999.
[16] V. Jacobson, K. Nichols, and K. Poduri, “ An Expedited Forwarding PHB,” IETF RFC 2598, June 1998.
[17] Raj Yavatkar, Don Hoffman, Yoram Bernet, Fred Baker, Michael Speer, Sun Microsystems SBM (Subnet Bandwidth Manager): A Protocol for RSVP-based Admission Control over IEEE 802-style networks.
[18] Thompson, K.; Miller, G.J.; Wilder, R. “Wide-area Internet traffic patterns and characteristics “IEEE Network, pp. 10-23, Nov.-Dec. 1997.
[19] B. Suter, T. V. Lakshman, D. Stiliadis and A. K. Choudhury, “Buffer management schemes for supporting TCP in gigabit routers with per-flow queueing” Selected Areas in Communications, IEEE Journal, pp. 1159 - 1169, June 1999.
[20] H. J. Chao and N. Uzun, “A VLSI sequencer chip for ATM traffic shaper and queue manager” Solid State Circuits, IEEE Journal, pp. 1634 -1643, Nov. 1992.
[22] F. Shafai, K. J. Schultz, G. F. R. Gibson, A. G. Bluschke and D. E. Somppi, “Fully parallel 30-MHz, 2.5-Mb CAM ” Solid State Circuits, IEEE Journal, pp. 1690 -1696, Nov. 1998.
[23] Bo Li and Yang Qin, “Traffic scheduling in a photonic packet switching system with QoS guarantee” Lightwave Technology, Journal, pp. 2281-2295 Dec. 1998.
[24] Henderson, “United States Patent, Paten Number: 5999435”, Dec. 1999.
[25] Xipeng Xiao, L. M. Ni and V. Vuppala, “An overview of IP switching and Tag switching” Parallel and Distributed Systems, 1997. Proceedings., 1997 International Conference on, pp. 669 -675, 1997.