交叉點(diǎn)單緩存的Crossbar交換結(jié)構(gòu)調(diào)度算法及性能研究.pdf

1、互聯(lián)網(wǎng)(Internet)的出現(xiàn)、個(gè)人計(jì)算機(jī)的普及和各類微、小型化計(jì)算裝置的廣泛應(yīng)用，對人類社會產(chǎn)生了巨大的沖擊，極大地改變了人們的工作和生活方式。互聯(lián)網(wǎng)的廣泛應(yīng)用造成了網(wǎng)絡(luò)應(yīng)用種類和數(shù)量大大增加以及用戶數(shù)量呈指數(shù)規(guī)律增長的局面，進(jìn)而對大容量、高速、高效的通信子網(wǎng)中繼設(shè)備的需求急劇增加；網(wǎng)絡(luò)應(yīng)用模式的變化(B/S與P2P并存)和多媒體化的趨勢使網(wǎng)絡(luò)應(yīng)用的服務(wù)質(zhì)量保障問題日益嚴(yán)峻；網(wǎng)絡(luò)運(yùn)行環(huán)境的惡化使互聯(lián)網(wǎng)(通信子網(wǎng)、端系統(tǒng)和網(wǎng)絡(luò)應(yīng)用系統(tǒng)

2、)面臨各類安全性問題的挑戰(zhàn)，移動終端與無線通信技術(shù)的廣泛應(yīng)用使移動訪問成為網(wǎng)絡(luò)訪問的新型模式。所有這一切都不斷地挑戰(zhàn)有30多年歷史的互聯(lián)網(wǎng)技術(shù)，特別是網(wǎng)絡(luò)體系結(jié)構(gòu)，也呼喚著下一代大容量、高速、高效的交換、服務(wù)質(zhì)量可保障的網(wǎng)絡(luò)交換設(shè)備和高性能、安全可靠、易管理和高可用性的通信子網(wǎng)，呼喚著高性能的新型網(wǎng)絡(luò)應(yīng)用系統(tǒng)。
　　本博士學(xué)位論文的研究工作以下一代互聯(lián)網(wǎng)體系結(jié)構(gòu)和技術(shù)研究為背景，以高性能交換技術(shù)為對象，研究網(wǎng)絡(luò)節(jié)點(diǎn)的交換結(jié)構(gòu)和交換

3、技術(shù)。本項(xiàng)研究的重點(diǎn)是一類“輸入及交叉點(diǎn)聯(lián)合排隊(duì)(Combined Input-Crosspoint Queued，CICQ)結(jié)構(gòu)”，即在各交叉點(diǎn)設(shè)有單個(gè)信元長度緩存(對定長信元交換)或單個(gè)最大幀長緩存(對變長幀交換)的CICQ結(jié)構(gòu)。CICQ是一種特殊的Crossbar交換結(jié)構(gòu)，在保留Crossbar完全無阻塞的特性的基礎(chǔ)上，它通過在交叉點(diǎn)(Cross Point)引入緩存，將輸入和輸出端口邏輯分離，從而緩解了傳統(tǒng)基于輸入排隊(duì)的Cros

4、sbar結(jié)構(gòu)中存在的輸入和輸出沖突問題，進(jìn)而為引入高效、復(fù)雜度較低的分布式調(diào)度算法、改善交換結(jié)構(gòu)的性能和交換服務(wù)質(zhì)量保障提供有利的條件。隨著大容量存儲技術(shù)的發(fā)展和存儲器價(jià)格的不斷下降，CICQ結(jié)構(gòu)越來越受到學(xué)界和業(yè)界的重視，與傳統(tǒng)的Crossbar結(jié)構(gòu)相比，它除了支持定長信元交換方式外，還能支持變長數(shù)據(jù)交換，為提供高性能的交換結(jié)構(gòu)開辟了新的途徑。
　　本文反映的主要研究成果涵蓋與CICQ結(jié)構(gòu)相關(guān)的兩類數(shù)據(jù)交換技術(shù)：經(jīng)典的基于定長信

5、元(例如64字節(jié))交換技術(shù)和迄今為止研究尚不多的變長數(shù)據(jù)交換技術(shù)。
　　在定長信元交換技術(shù)研究方面，作者首先提出了長隊(duì)列優(yōu)先的CICQ調(diào)度算法-LQP-RR(Long Queue Prioritized-Round Robin)，以解決典型的LQF-RR(Longest Queue First-Round Robin)算法的輸入端排序操作的計(jì)算復(fù)雜度較高(平均時(shí)間復(fù)雜度下界為O(NlogN))、難于用硬件實(shí)現(xiàn)的問題。LQP-RR利

6、用VOQ隊(duì)列在實(shí)際調(diào)度過程中的局部變化特性來尋找較長的輸入隊(duì)列，在輸入端進(jìn)行一次比較即可達(dá)到目的，從而使計(jì)算復(fù)雜度簡化為O(I)，因而易于用硬件實(shí)現(xiàn)。此外，通過引入輔助輪詢指針配合調(diào)度，可進(jìn)一步保證調(diào)度算法的公平性。LQP-RR算法的上述特點(diǎn)為筆者進(jìn)一步提出計(jì)算復(fù)雜度低、交換結(jié)構(gòu)利用率高和交換時(shí)延短的新型交換算法--“混合優(yōu)化的調(diào)度算法”(Hybrid OptimizationPacket Scheduling，HOPS)奠定了基礎(chǔ)。<

7、br>　　HOPS算法以每一時(shí)槽都有盡可能多的輸出端口有信元可輸出為策略，提高對輸出端口的利用率，從而使CICQ的總吞吐率最大。為此，通過輸入、輸出調(diào)度策略聯(lián)動，即輸入調(diào)度算法向交叉節(jié)點(diǎn)輸出的信元時(shí)，盡量保證輸出調(diào)度可輸出信元端口數(shù)最大。筆者用流體模型證明：對滿足強(qiáng)大數(shù)定律的許可輸入流，HOPS的總吞吐率趨近交換結(jié)構(gòu)理論轉(zhuǎn)發(fā)能力的100％。仿真結(jié)果還表明：HOPS調(diào)度算法在各種許可流量模型下都能穩(wěn)定運(yùn)行，而且在交換結(jié)構(gòu)無加速比條件下，其

8、時(shí)延性能相對現(xiàn)有的算法有明顯的提高。因?yàn)镠OPS算法計(jì)算復(fù)雜度與LQP-RR相同的，因此容易實(shí)現(xiàn)。
　　本文有關(guān)變長數(shù)據(jù)交換技術(shù)的研究成果涉及變長直接交換和變長切分交換兩類。在變長直接交換技術(shù)方面，本文提出一種基于單緩存CICQ交換結(jié)構(gòu)的“兩級流控變長幀調(diào)度”(Two-stage Flow-control for Variable-length Data，TFVD)算法。該算法除改進(jìn)了現(xiàn)有CICQ變長數(shù)據(jù)直接交換算法的公平性外，還

9、提高了交換吞吐率，縮短了時(shí)延。該算法的核心思想是在交換結(jié)構(gòu)的兩級調(diào)度過程中分別進(jìn)行流量控制，并通過令牌配額(Token Quota)機(jī)制延遲長幀發(fā)送時(shí)間，直至積累足夠配額位置，從而減小長幀對交換鏈路產(chǎn)生的影響。仿真結(jié)果表明該算法在保證調(diào)度公平性的同時(shí)，提高了交換系統(tǒng)的轉(zhuǎn)發(fā)性能，在負(fù)載為98％的突發(fā)流量模型下，其時(shí)延比現(xiàn)有的變長幀直接交換算法MQF-RR、DRR和PP-VOQ分別縮短了11％，17％和25％。
　　在變長切分交換技術(shù)

10、研究方面，本文提出了一種“反饋式多幀變長切分”(Multi-frame Variable-length Segmentation with Feedback，MVSF)策略。該策略采用多幀合并切分以避免單幀定長切分常見的填充開銷；為了避免了現(xiàn)有的切分策略因交叉點(diǎn)存儲空間限制可能出現(xiàn)系統(tǒng)某路輸入調(diào)度暫時(shí)停頓的問題，交叉點(diǎn)緩存的狀態(tài)信息的反饋被用作動態(tài)調(diào)整切分單元的大小的依據(jù)。仿真結(jié)果表明：反饋式多幀變長切分策略使CICQ的變長切分交換，在

11、交換時(shí)延和系統(tǒng)總吞吐率方面均優(yōu)于已有的切分策略。
　　服務(wù)質(zhì)量保障機(jī)制是關(guān)系到下一代交換機(jī)/路由器性能的重要技術(shù)。本論文第五章對CICQ交換時(shí)延上下界進(jìn)行了分析研究。應(yīng)用于OQ結(jié)構(gòu)中的WF2Q算法的性能接近通用處理器共享(Generalized Processor Sharing，GPS)模型的理想性能，筆者將WF2Q算法應(yīng)用于交叉點(diǎn)單緩存的CICQ結(jié)構(gòu)，同時(shí)作為輸入調(diào)度和輸出調(diào)度的算法，即WF2Q*-WF2Q。本文還導(dǎo)出了該算法