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

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

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

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

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