公平可擴(kuò)展網(wǎng)絡(luò)交換調(diào)度算法及其FPGA實(shí)現(xiàn).pdf

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

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

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

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

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

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