公平可擴展網絡交換調度算法及其FPGA實現(xiàn).pdf

1、隨著Intemet的迅速發(fā)展，對網絡交換技術也提出了越來越高的要求。下一代網絡交換的核心技術就是高性能的網絡交換設備，優(yōu)良的性能主要表現(xiàn)在具有較大的交換容量、較高的吞吐率、較小的延遲時間并且能夠在任意流量下都具有較低的丟包率。目前，雖然交換機和調度器都有成功開發(fā)的集成電路芯片，但大多都是由國外廠商研制開發(fā)的，其核心技術和知識產權也掌握在國外開發(fā)商的手中，而且受到半導體制造工藝限制，單個芯片在電路規(guī)模、I/O管腳數(shù)及處理速度上都受到了限制

2、，要想實現(xiàn)多端口、大規(guī)模的交換和調度芯片十分困難。因此，有必要對網絡交換和調度技術作進一步研究，尋求一種可擴展的網絡交換結構以適應下一代網絡發(fā)展的需要。 在多個網絡交換方式中，輸入隊列(IQ)交換方式由于其速度不受存儲器存取速度的限制成為網絡交換的主要方式。IQ交換采用虛擬輸出隊列(VOQ)機制，將每個到達的包按照其目的地址的不同存放存在相應的輸入緩沖中，有效地降低了頭部阻塞(HoL)給IQ交換帶來的，從而使系統(tǒng)的最大吞吐率達到

3、100％。IO調度算法主要分為兩大類：最大權匹配算法(MWM)和極大尺寸匹配算法(MSM)。前者以LQF算法為代表，擁有優(yōu)秀的性能，但其硬件復雜度高達O(N<'3>logN)，使其很難實際應用；后者以iSLIP，F(xiàn)IRM和RDSRR等算法為代表，擁有較低的硬件復雜度，其性能卻遜于前者，尤其在非均勻流量及大負載情況下算法不穩(wěn)定。自1999年提出了iSLIP算法之后，近年來不斷有新的IQ調度算法提出，其目的都是為了改善MSM算法在非均勻流量

4、下性能不理想的狀況。本文對這一問題也作了研究，提出了一種自適應雙門限算法SATRR。該算法通過為輸入隊列施加隊列長度閾值和隊首包等待時間閾值，使得具有較大權重的隊列得到優(yōu)先調度，從而在控制硬件復雜度的前提下，改善了算法的性能。仿真結果表明，在均勻流量模式和非均勻流量模式下，SATRR算法的延遲特性均優(yōu)于其它MSM算法，取得了性能與硬件復雜度的良好折中。 在設計高性能調度算法的基礎上，本文研究了可擴展網絡調度系統(tǒng)FSSA的硬件實現(xiàn)

5、。FSSA是在國家自然科學基金資助下提出的一種公平可擴展網絡交換調度結構，它由若干片容量較小的調度器串聯(lián)而成，在中心控制器的控制下，各子調度器并行工作完成大容量、多端口的調度任務。在實際應用中，F(xiàn)SSA可根據(jù)需要擴展成不同容量和端口數(shù)的調度器，不僅速度高，而且規(guī)?？蓴U展，從根本上解決單個調度器容量和端口受限的問題。研究采用Xilinx FGPA設計實現(xiàn)了64x64的基于FSSA的調度器。該調度器由4片Xilinx Virtex-4芯片級

6、聯(lián)構成，每片完成16x64．的子調度器任務。設計中充分合理地應用了Xilinx Virtex-4 FPGA的新特性以及其內嵌的IP核及功能模塊，如高性能輸入輸出串/并、并/串轉換器ISERDES和OSERDES、數(shù)字時鐘控制器DCM等，從而節(jié)省了大量寶貴的邏輯資源，提高了芯片的速度和性能。仿真和驗證結果表明，本設計功能正確，每個子調度器可以同時處理16路800Mbps的數(shù)據(jù)，滿足設計要求。 文章第一章主要介紹課題背景及意義，第二