以FPGA設計與實現DRR的有效公平序列

Design and Implementation on Efficient Fair Queuing of Deficit Round Robin with FPGA.

楊忻曄(Shin-Ye Yang)

指導教授 ： 呂振森 ； 宋國明

國立臺北科技大學/電資學院/電力電子產業研發碩士專班/碩士(2010年)

https://doi.org/10.6841/NTUT.2010.00093

摘要

一般而言，網路的端對端(End-to-End)是使用微處理器(Microprocessor)的高效能精簡指令集(RISC)來移動資料封包的，成本高且速度緩慢，同時還需要相當大的快閃記憶體，所以，在此對原先的先進先出排序機制(FIFO，First In First Out)做改進，讓此進行封包控管，其後，搭配差額循環執行排序機制(DRR，Deficit Round Robin)，並以資料暫存於記憶體(Memory)的方式，來取代微處理器，不僅可以暫存資料封包，也利於往後對封包進行檢查確認。

本論文，係使用Verilog硬體描述語言撰寫程式碼，可依資料封包尺寸判斷傳送路徑，或是進行封包切割，並利用差額循環執行排序(DRR，Deficit Round Robin)去對封包進行定量(Quantum)分配，讓其減緩等待時間，降低遺失率，並給予網際網路(Internet)一個流量管理機制環境，讓封包頻寬能公平分配，使用訊號以可程式邏輯閘陣列(FPGA，Field Programmable Gate Array)去實現DRR有效公平序列的傳遞執行。

關鍵字

Verilog硬體描述語言 ； 先進先出排序 ； 差額循環執行排序 ； 精簡指令集 ； 可程式邏輯閘陣列

並列摘要

Generally, the end-to-end communication of network is completed with microprocessor using RISC to move those packets, even though it needs large flash memory and works slowly. A FIFO is utilized to solve the numerous memories, but the transmitting speed is still slow and needs to be improved. Moreover, replacing the microprocessor with DRR is proposed to have good throughput by checking the packets.
In this thesis, the DRR is completed with Verilog hardware description language. As the packets need to be transmitted, they need to be judged according to their sizes using the DRR mechanism. The destination is to reduce the waiting time and to decrease the loss rates. In addition, a traffic management is presented to have a fair distribution of bandwidth for the packets. Finally, the efficient fair queuing with DRR is implemented with FPGA.

並列關鍵字

Verilog ； FIFO(First In First Out) ； DRR(Deficit Round Robin) ； RISC (Reduced Instruction Set Computing) ； FPGA (Field Programmable Gate Array)

參考文獻

[1] A. Demers, S. Keshav, and S. Shenker, “Analysis and simulation of a fair queueing algorithm,” J. Internetworking Res. Experience, Oct. 1990, pp. 3-26.

[2] M. Shreedhar and G. Varghese, “Efficient fair queueing using deficit round robin,” in Proc. ACM SIGCOMM, 1995, pp. 231–242.

[3] H. Zhang, “Service disciplines for guaranteed performance service in packet -switching networks,” in Proc. of the IEEE, vol. 83, no. 10, oct. 1995.

[4] K. H. Cho and Hyunsoo Yoon, “Design and analysis of a fair scheduling algorithm for QoS guarantees in high-speed packet-switched networks,” in Proc. of the IEEE, 1998.

[5] C. Evéquoz, F. Kordon, and T. Vardanega (Eds.), “Practical, fast and simple concurrent FIFO queues using single word synchronization imitives,” in Ada-Europe 2008, LNCS, 2008, pp. 59 – 72.