跳到主要內容

臺灣博碩士論文加值系統

(44.200.171.74) 您好!臺灣時間:2022/08/12 19:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:許文彬
研究生(外文):Wen-Pin Hsu
論文名稱:應用於封包交換器之公平排程演算法的設計與實作
論文名稱(外文):Design and Implementation of Fair Queueing Algorithms for Packet Switches
指導教授:紀新洲
指導教授(外文):Hsin-Chou Chi
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:56
中文關鍵詞:超大型積體電路排程器公平佇列服務品質
外文關鍵詞:Fair Queueing AlgorithmQoSSchedulerVLSI
相關次數:
  • 被引用被引用:0
  • 點閱點閱:241
  • 評分評分:
  • 下載下載:42
  • 收藏至我的研究室書目清單書目收藏:0
近年來,網路的應用隨著網路和應用程式的進步使得多媒體的應用(例如: 視訊會議、網路電話、遠距教學及串流視訊..等)在網際網路上是越來越盛行。這些應用通常都需要一個高速且延遲又小的網路網路環境來傳輸資料。在未來,高速的封包交換網路將同時支援許多類型的服務在同一個網路架構上。而這些高速的網路除了必須對不同的封包等級提供不同的服務之外還必須有管理封包和分類不同類型封包的能力。
網路流量的管理方式將成為未來評估網路的一個重要指標。它能夠提供一個品質服務保證Quality of Service(QoS)。品質服務保証通常定義了點對點的延遲時間、封包遺失率、延遲變異量和頻寬的分配..等參數。
許多排程的演算法的發展和評估都是為了滿足服務品質保證QoS。General Processor Sharing(GPS)是第一個被提出而且是一個理想化的排程演算法。它提供了:(a)它能夠保證最小點對點的延遲;(b)當某些鏈結不再使用頻寬時,它能夠將多餘的頻寬分配給需要使用的鏈結;(c)它能夠依鏈結的權重公平的分配頻寬。但因為GPS在現實世界中實在無法被實現,所以,另一個專為封包網路設計的公平排程演算法Packet Fair Queueing(PFQ)被發展出來,而每個演算法依照其複雜性和精確性之間而提供不同的效能。
我們將以其中的兩種公平排程演算法SCFQ和FWFQ實作成二個排程晶片,除了比較二個演算法的實作複雜度之外,在實作完成後還將比較二個排程晶片的效能。在實作過程中,除了降低其架構的複雜度之外,還要排程晶片符合在高速網路的應用中。在實作的結果中,我們所設計的晶片具有不錯的效能。
In recent years, multimedia applications are more and more popular on the Internet. These applications require high-speed networks to provide high-bandwidth low-delay communication. In the future, high-speed, packet-switched networks will simultaneously support multiple types of services over a single physical infrastructure. In these packet-switched networks, packets from different sessions belonging to different service and administrative classes interact with each other.
Traffic scheduling algorithms are a critical component of future integrated-service packet networks. It provides a broad range of quality-of-service (QoS) guarantees. These guarantees usually define the bounds on end-to-end delay, packet loss rate, delay jitter (variation in delay), bandwidth, or a combination of these parameters.
Several scheduling algorithms for providing QoS guarantees have been proposed and analyzed. General processor sharing (GPS) is an ideal scheduling algorithm since it possesses the following properties (a) it can guarantee an end-to-end delay to a leaky-bucket-constrained session regardless of the behavior of the other sessions; (b) it can ensure instantaneous fair allocation of bandwidth among all backlogged sessions regardless of whether or not their traffic is constrained; and (c) it ensures fairness among backlogged connections. Therefore, a type of service disciplines called packet fair queueing (PFQ) algorithms have received much attention, and different packet fair queueing algorithms with different tradeoffs between complexity and accuracy have been proposed.
This paper presents two QoS schedulers in VLSI used in high-speed networks with reasonable hardware cost.
目錄
第一章 導論 1
1.1. 研究動機與目的 1
1.2. 論文組織 2
第二章 服務品質(Quality of Service)與第三層交換器(Layer 3 Switch) 3
2.1. 服務品質(Quality of Service)簡介 3
2.2. 第三層交換器(Layer 3 Switch)簡介 6
2.2.1. 交換單元與佇列管理器 8
2.2.2. 封包分類器 10
2.2.3. 封包公平排程器 11
第三章 公平佇列排程演算法介紹 12
3.1. 公平佇列排程演算法介紹 12
3.1.1. First In First Out (FIFO) 14
3.1.2. 參數定義 14
3.1.3. Generalized Processor Sharing (GPS) 15
3.1.4. Weight Fair Queueing (WFQ) 19
3.1.5. Self-Clocked Fair Queueing (SCFQ) 21
3.1.6. Fast Weight Fair Queueing (FWFQ) 22
3.2. 公平佇列排程演算法之比較 24
3.2.1. 功能比較 25
3.2.2. 複雜度比較 27

第四章 公平佇列排程演算法之架構 28
4.1. SCFQ 排程演算法之架構 28
4.1.1. Time Stamp 計算單元 28
4.1.2. 排程封包選擇單元 30
4.2. FWFQ排程演算法之架構 32
4.2.1. Time Stamp 計算單元 32
4.2.2. 排程封包選擇單元 34
4.3. 平行輸入計算單元 35
第五章 實作與測試 36
5.1. 實作 36
5.1.1. SCFQ Scheduler Chip實作 39
5.1.2. FWFQ Scheduler Chip實作 41
5.2. 測試 43
5.2.1. SCFQ Scheduler Chip測試 43
5.2.2. FWFQ Scheduler Chip測試 47
5.3. 比較 51
第六章 結論與未來研究 53
參考文獻 54
參考文獻
[1]http://www.qosforum.com
[2]IETF RFC 2475, “Architecture for Differentiated Services”, December 1998.
[3]R. Burden, L. Zhang, S. Berson, S. Herzog, S. Jamin, “Resource Reservation Protocol (RSVP)- Version 1 Functional Specification”, RFC 2205, September 1997.
[4]J. C. R. Bennett and H. Zhang, “WF2Q : Worst-case Fair Weighted Fair Queueing,” IEEE INFOCOM’96, March 1996, pp. 120-128.
[5]Yuan-Sun Chu, Chi-Fang Li, Chih-Yang Chiu, “An Interleaved Round-Robin Scheduling Chip for ATM Networking” VLSI Design/CAD 2001, August 2001.
[6]A. Demers, S. Keshav and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” Internetworking: Research and Experience, vol. 1,no.1, 1990, pp. 3-26
[7]S. Jamaloddin Golestani, “A Self-Clocked Fair Queueing Scheme for Broadband Applications,” in Proc. IEEE INFOCOM’94, Toronto, CA, June 1994, pp 636-646
[8]David A. Patterson, John L. Hennessy, Computer Organization & Design, The Hardware/Software Interface, 2nd Edition, Morgan Kaufmann, 1998
[9]A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control – The Single Node Case,” Proc. INFOCOM’92, vol. 2, May 1992, pp. 915-924.
[10]Larry L. Peterson, Bruce S Davie, Computer Networks-A System Approach 2nd Edition, Morgan Kaufmann, 2000.
[11]Chi-An Su, “Resource Management Schemes for Mobile and High-Speed Networks,” NCTU, 1999
[12]Donpaul C. Stephens, Jon C. R. Bennett, and Hui Zhang, “Implementing Scheduling Algorithms in High-Speed Networks” IEEE JSAC, 1999, vol. 17, no. 6,pp.1145-1158
[13]D. Stiliadis and A. Varma, “Efficient Fair Queueing Algorithms for Packet-Switched Networks,” IEEE/ACM Trans. On Networking, vol. 6, no. 2, April 1998, pp. 175-185
[14]D. Stiliadis and A. Varma, “Design and Analysis of Frame-based Fair Queueing: A New Traffic Scheduling Algorithm for Packet Switched Netwoks,” ACM SIGMETRICS, May 1996, pp. 104-115
[15]D. Stilliadis and A. Varma, “Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms.” IEEE INFOCOM’96, March 1996, pp. 111-119
[16]M. Shreedhar and G. Varghese, “Efficient Fair Queueing using Deficit Round Robin,” ACM SIGCOMM’95. October 1995, pp. 231-242
[17]Dong Wei, Jianguo Chen, Nirwan Ansari, “An Efficient Expression of Timestamp and Period in Packet-based and Cell-based Schedulers” IEEE ICC 2001, 2001, vol. 1, pp 95-99.
[18]Haijun Yang, Dawei Wang, Peilin Hong, Jinsheng Li, “Hardware Implementaion of Packet-Fair Queueing Scheduler In High Speed Networks” IEEE APCCAS 2000 pp. 62-65
[19]Yang Hanijun, Hong Peilin, Li Jinsheng. “Design of Packet-Fair Queueing Schedulers in Router” IEEE WCC - ICCT 2000, vol. 2. pp. 1653 – 1656
[20]Hui Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks” Proceedings of IEEE VOL. 83 NO. 10, OCT. 1995
[21]區域網路與高速網路,黃能富 編著,維科出版社,1996
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top