基于輸入排隊(duì)的可擴(kuò)展交換結(jié)構(gòu)調(diào)度算法的研究.pdf

1、交換結(jié)構(gòu)(switch fabric)作為交換機(jī)和路由器的核心，如何提高其交換容量可擴(kuò)展性和服務(wù)質(zhì)量可預(yù)測性，是近十年來網(wǎng)絡(luò)研究的一個熱點(diǎn)和難點(diǎn)問題。一個典型的交換結(jié)構(gòu)由三部分組成：輸入端口、輸出端口和交換內(nèi)核。為了避免來自不同輸入端口的信元同時發(fā)往同一個輸出端口，需要在輸出端口或者輸入端口設(shè)置緩沖區(qū)，從而形成輸出排隊(duì)和輸入排隊(duì)兩大基本交換結(jié)構(gòu)。盡管輸出排隊(duì)型交換結(jié)構(gòu)可以提供良好的服務(wù)質(zhì)量保證(100％的吞吐率，有界的延遲，帶寬公平性等

2、)，然而其存儲器的帶寬卻需要所有輸入端口帶寬總和，這極大限制了其擴(kuò)展性。與之相比，輸入排隊(duì)型交換結(jié)構(gòu)允許內(nèi)部存儲器的帶寬工作在線速，其良好的可擴(kuò)展性使其成為高性能路由器的主流交換結(jié)構(gòu)。由于交換結(jié)構(gòu)的調(diào)度算法負(fù)責(zé)將輸入端口的信元通過交換內(nèi)核發(fā)送至輸出端口，所以它在提高交換設(shè)備的利用率及其服務(wù)質(zhì)量保證方面起著關(guān)鍵性作用。本文從交換容量的可擴(kuò)展性及服務(wù)質(zhì)量可預(yù)測性的角度出發(fā)，研究了基于輸入排隊(duì)的不同類型交換結(jié)構(gòu)下的調(diào)度算法設(shè)計。 目前

3、，核心交換機(jī)／路由器的主流交換結(jié)構(gòu)一般采用交叉開關(guān)(crossbar)以保證交換內(nèi)核無阻塞，并采用集中式調(diào)度器調(diào)度定長信元通過交叉開關(guān)。對于該交換結(jié)構(gòu)，具有較強(qiáng)理論意義的一類算法為最大權(quán)重匹配算法，已證明對于任意容許的流量，均能達(dá)到100％的吞吐率，并且平均延遲有界，然而其算法的復(fù)雜度高達(dá)O(N<'3>)，本文從局部搜索的角度研究了最大權(quán)重匹配的近似算法，結(jié)合局部搜索的可并行計算的特點(diǎn)，提出了一種并行隨機(jī)調(diào)度算法及一種并行確定性調(diào)度算法

4、，并且證明了算法的穩(wěn)定性，與已有近似算法相比，具有更低的平均延遲。 緩沖交叉開關(guān)型交換結(jié)構(gòu)由于具有分布式存儲及分布式調(diào)度的特點(diǎn)，是構(gòu)建特比特級(Terabit)路由器的一種理想選擇。由于輪轉(zhuǎn)型調(diào)度算法易于硬件實(shí)現(xiàn)，具有較高的應(yīng)用價值，從而得到了廣泛的研究?，F(xiàn)有輪轉(zhuǎn)型算法在調(diào)度均勻流量時具有逼近100％的吞吐率，然而對于非均勻的流量，現(xiàn)有輪轉(zhuǎn)型算法的吞吐率卻明顯下降。為解決此問題，與當(dāng)前的單輪轉(zhuǎn)指針不同，本文提出了一類雙輪轉(zhuǎn)指針的

5、調(diào)度算法，即在每個輸入調(diào)度器均設(shè)置了主指針與輔助指針，主指針對應(yīng)的隊(duì)列具有最高的調(diào)度優(yōu)先級，算法可以根據(jù)各個隊(duì)列的狀態(tài)來動態(tài)決定何時更新主指針，當(dāng)主指針對應(yīng)的隊(duì)列被流控機(jī)制阻塞時，將根據(jù)輔助指針依次公平服務(wù)其他隊(duì)列。仿真實(shí)驗(yàn)表明，對于每個交叉點(diǎn)緩沖區(qū)僅有一個信元的交換結(jié)構(gòu)，基于雙指針的調(diào)度算法可以顯著提高該交換結(jié)構(gòu)在已知多種非均勻流量下的性能。 對于緩沖交叉開關(guān)型交換結(jié)構(gòu)，一般采用基于份額的流控機(jī)制，在這種方式下，為了確保輸入和

6、輸出端口都可以工作保持(work-conservingl)，每一個交叉點(diǎn)緩沖區(qū)大小至少需要線速乘以交換結(jié)構(gòu)內(nèi)部環(huán)路延遲，對于特比特級、多機(jī)柜的交換機(jī)，其交叉點(diǎn)緩沖區(qū)的需求必然很大，從而給實(shí)現(xiàn)帶來困難。本文從均勻交換的角度研究了該交換結(jié)構(gòu)下的服務(wù)質(zhì)量保證問題，提出了一種新型的支持流一級均勻交換的內(nèi)核，該交換結(jié)構(gòu)采用基于位率信息的流控機(jī)制，允許任意大小的交換內(nèi)核至線卡的往返延遲，并且在容許的流量下，每個交叉點(diǎn)緩沖區(qū)的容量僅需四個信元即可保證