高速路由器交換結(jié)構(gòu)和調(diào)度算法的研究.pdf

1、隨著網(wǎng)絡(luò)流量和業(yè)務(wù)種類(lèi)的劇增，交換設(shè)備性能的提升已經(jīng)成為影響網(wǎng)絡(luò)服務(wù)質(zhì)量的關(guān)鍵因素。交換結(jié)構(gòu)和調(diào)度算法是當(dāng)今高速路由設(shè)備的核心技術(shù)和重點(diǎn)研究方向，其性能直接決定了高速路由設(shè)備的整體性能。
　　 本文首先從隊(duì)列結(jié)構(gòu)和體系結(jié)構(gòu)兩方面研究了交換結(jié)構(gòu)的發(fā)展過(guò)程和現(xiàn)狀。輸出排隊(duì)的隊(duì)列結(jié)構(gòu)能夠提供較好的服務(wù)質(zhì)量，但其對(duì)隊(duì)列緩沖的讀寫(xiě)速度的苛求極大的限制了發(fā)展。輸入排隊(duì)對(duì)于隊(duì)列緩沖的讀寫(xiě)速度不存在苛刻的要求，同時(shí)本身存在的隊(duì)首阻塞的問(wèn)題被研究

2、者提出的虛擬輸出隊(duì)列(virtualoutput queue)的方式完全解決。另一方面，單機(jī)分布式交叉開(kāi)關(guān)(crossbar)的體系結(jié)構(gòu)能夠保證交換內(nèi)核并行處理多路數(shù)據(jù)流，大幅提升了系統(tǒng)整體的交換容量。輸入排隊(duì)的crossbar交換結(jié)構(gòu)成為現(xiàn)今主流路由設(shè)備的首選結(jié)構(gòu)。
　　 本文隨后對(duì)采用輸入排隊(duì)crossbar交換結(jié)構(gòu)的調(diào)度算法進(jìn)行了研究。通過(guò)對(duì)調(diào)度模型的分析，將其抽象為無(wú)向二分圖的匹配問(wèn)題。本文選擇了幾種典型的極大匹配算法進(jìn)

3、行研究：并行迭代匹配算法由于采用隨機(jī)仲裁的方式，實(shí)現(xiàn)復(fù)雜度較高；輪轉(zhuǎn)匹配調(diào)度算法使用輪轉(zhuǎn)優(yōu)先級(jí)的仲裁方式，降低了實(shí)現(xiàn)的復(fù)雜度，但由于輪轉(zhuǎn)指針更新規(guī)則存在缺陷，導(dǎo)致端口出現(xiàn)同步現(xiàn)象，影響了吞吐性能；滑動(dòng)多次迭代調(diào)度算法解決了指針同步現(xiàn)象和不公平性導(dǎo)致的餓死現(xiàn)象，已經(jīng)被交換設(shè)備廠商應(yīng)用到實(shí)際產(chǎn)品中；較新提出的先到先服務(wù)輪轉(zhuǎn)匹配調(diào)度算法做了進(jìn)一步的優(yōu)化，改善了延時(shí)性能和公平性?；瑒?dòng)多次迭代調(diào)度算法和先到先服務(wù)輪轉(zhuǎn)匹配調(diào)度算法由于其實(shí)現(xiàn)簡(jiǎn)單和性

4、能良好，成為如今主流的調(diào)度算法。但是，這兩種算法在處理非均勻業(yè)務(wù)的時(shí)候，性能表現(xiàn)不佳。后文在這兩種算法的基礎(chǔ)上，提出了一種優(yōu)化指針策略的low-FIRM算法，并對(duì)這種新算法進(jìn)行詳盡的性能分析和實(shí)現(xiàn)介紹。
　　 最后，本文設(shè)計(jì)并實(shí)現(xiàn)了針對(duì)輸入排隊(duì)crossbar交換結(jié)構(gòu)的調(diào)度算法仿真平臺(tái)，應(yīng)用這個(gè)平臺(tái)對(duì)新算法和兩張典型算法進(jìn)行了仿真實(shí)驗(yàn)。通過(guò)實(shí)驗(yàn)結(jié)果的比較，可以得出，本文提出的新算法不僅保持了典型算法在均勻業(yè)務(wù)流下的良好性能，而且