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

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

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

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

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

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

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

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

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

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

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

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