作為分組交換結(jié)構(gòu)的torus網(wǎng)絡(luò)研究.pdf

1、下一代核心路由器除了應(yīng)具有極大的交換容量以外，還應(yīng)具有靈活經(jīng)濟(jì)的可擴(kuò)展性與極高的可靠性。作為路由器的核心部件，分組交換結(jié)構(gòu)(PacketSwitchingFabrics，PSF)對路由器在上述各方面的表現(xiàn)具有決定性的作用。傳統(tǒng)的分組交換結(jié)構(gòu)技術(shù)由于受到crossbar規(guī)模、總線帶寬、緩存讀寫速率以及集中仲裁調(diào)度方式等方面的限制，在實(shí)現(xiàn)極大交換容量與端口數(shù)量時(shí)面臨著較大的技術(shù)難度，而且其可擴(kuò)展性不理想。同時(shí)，集中仲裁調(diào)度方式所帶來的單點(diǎn)失

2、效(singlepointfailure)問題降低了系統(tǒng)的可靠性。 另一方面，在過去的二十年里，以torus網(wǎng)絡(luò)為代表的直接網(wǎng)絡(luò)技術(shù)被廣泛應(yīng)用于高性能計(jì)算系統(tǒng)中，主要作為處理器/存儲(chǔ)器之間的連接。torus網(wǎng)絡(luò)具有大容量、易擴(kuò)展、高可靠性等優(yōu)點(diǎn)，正好滿足下一代核心路由器對分組交換結(jié)構(gòu)技術(shù)的要求。然而作為分組交換結(jié)構(gòu)的torus網(wǎng)絡(luò)(TorusnetworksusedaSPSF，T-PSF)與高性能計(jì)算系統(tǒng)中的torus網(wǎng)絡(luò)在網(wǎng)絡(luò)

3、規(guī)模、業(yè)務(wù)的特性、交換性能要求等方面都有著較大差異。如何有效地采用torus網(wǎng)絡(luò)構(gòu)建大容量可擴(kuò)展分組交換結(jié)構(gòu)仍然是一項(xiàng)充滿挑戰(zhàn)的、有待深入研究的課題。本論文致力于研究這一課題中的關(guān)鍵技術(shù)，主要研究內(nèi)容包括：torus網(wǎng)絡(luò)中的自適應(yīng)路由算法，T-PSF的負(fù)載模式及其對網(wǎng)絡(luò)性能的影響，針對惡性負(fù)載模式的解決方法，T-PSF的擴(kuò)展方案。 描述torus網(wǎng)絡(luò)的特征與研究其性能需要用到一些基本概念。本論文的第二章集中介紹了這些概念，并給出

4、了必要的數(shù)學(xué)定義與形式化表示方式。根據(jù)作者自己的理解，對一些概念之間的聯(lián)系進(jìn)行了說明。對已有文獻(xiàn)(尤其是一些較早期的研究工作)中使用比較混亂、容易造成誤解的術(shù)語進(jìn)行了解釋和澄清。 本論文的第三章研究torus網(wǎng)絡(luò)中的無死鎖自適應(yīng)路由算法。首先概述并比較了已有的兩種解決死鎖問題的策略：死鎖避免與死鎖恢復(fù)。然后提出了一種采用死鎖避免策略的完全自適應(yīng)路由算法的設(shè)計(jì)方案DALD(Deadlock-AvoidancewithLocalDe

5、tection)。采用DALD方案所設(shè)計(jì)的路由算法只需要每個(gè)物理通道上具有兩個(gè)虛通道(VirtualChannel，VC)即可實(shí)現(xiàn)無死鎖(deadlock-free)，并且具有不錯(cuò)的性能。這是所有torus網(wǎng)絡(luò)的路由算法中對緩存資源需求最少的，并且已經(jīng)達(dá)到了緩存需求的事實(shí)上的最小極限。本章還提出了一種自適應(yīng)路由算法的設(shè)計(jì)方案PDR(Path-DivisionRouting)，并且給出了采用該方案的路由算法的兩種設(shè)計(jì)方法：分解法與合成法。

6、然后詳細(xì)描述了一種采用分解法所設(shè)計(jì)的路由算法ELadder。ELadder以增加虛通道為代價(jià)，在保持算法非常簡單、易于實(shí)現(xiàn)的同時(shí)，能夠達(dá)到不錯(cuò)的性能。 torus網(wǎng)絡(luò)的性能在很大程度上受其負(fù)載模式的影響。然而已有的負(fù)載模式模型是針對應(yīng)用于高性能計(jì)算系統(tǒng)中的torus網(wǎng)絡(luò)或傳統(tǒng)分組交換結(jié)構(gòu)所設(shè)計(jì)的，并不適用于T-PSF。本論文的第四章首先簡述了已有最好的分組交換結(jié)構(gòu)的負(fù)載模式模型--ZD(ZipfDistribution)模型。通

7、過理論分析與仿真結(jié)果，闡明了ZD模型不適用于T-PSF的原因是因?yàn)樗话P(guān)于分組的源、目的節(jié)點(diǎn)之間距離的信息。然后提出了兩種適用于T-PSF的負(fù)載模式模型，分別采用不同的方法，把關(guān)于源、目的節(jié)點(diǎn)之間距離的信息與ZD模型結(jié)合起來。通過設(shè)置參數(shù)的值，可以控制模型中負(fù)載分布的均勻程度與源、目的節(jié)點(diǎn)之間的平均距離。這是業(yè)界首次提出的適用于T-PSF的負(fù)載模式模型。這兩個(gè)模型都對網(wǎng)絡(luò)的拓?fù)渑c節(jié)點(diǎn)總數(shù)不敏感，因而可以適用于不同拓?fù)渑c規(guī)模的網(wǎng)絡(luò)。

8、 不少實(shí)際應(yīng)用要求torus網(wǎng)絡(luò)對于各種負(fù)載模式都能達(dá)到較高的吞吐量，包括所謂惡性負(fù)載模式(即可能造成負(fù)載不均衡的模式)。目前針對這一問題的最佳解決方法是采用全局自適應(yīng)負(fù)載均衡路由算法。本論文的第五章提出了一種全局自適應(yīng)負(fù)載均衡路由算法GALME(GloballyAdaptiveLoad-balancedroutingwithMutualExclusion)。GALME根據(jù)節(jié)點(diǎn)轉(zhuǎn)發(fā)分組的歷史信息來達(dá)到全局負(fù)載均衡，根據(jù)虛通道的當(dāng)前

9、狀態(tài)來達(dá)到局部負(fù)載均衡。GALME還使用了基于“互斥性”的死鎖避免方案，具有很強(qiáng)的路由自適應(yīng)性，從而對于各種負(fù)載模式所能達(dá)到的吞吐量都超過了已有的最佳算法。T-PSF的負(fù)載模式與節(jié)點(diǎn)的具體位置無關(guān)，本章還針對這一特點(diǎn)，提出了一種適用于T-PSF的負(fù)載配置算法。通過把彼此之間有較大通信流量的節(jié)點(diǎn)配置到鄰近位置，能夠有效地減小分組源、目的節(jié)點(diǎn)之間的平均距離，從而提高網(wǎng)絡(luò)性能。這是業(yè)界首次提出的針對T-PSF特點(diǎn)的惡性負(fù)載模式的解決方法。

10、 本論文的第六章研究T-PSF的擴(kuò)展方案。首先總結(jié)了構(gòu)建T-PSF時(shí)所應(yīng)遵循的原則，然后提出了一種模塊化的子網(wǎng)結(jié)構(gòu)--可配置單板(ConfigurableBoard，CB)。每個(gè)CB上集成有16個(gè)節(jié)點(diǎn)。通過逐漸增加CB的數(shù)量，并合理配置其板內(nèi)、板間連接方式，可以方便地實(shí)現(xiàn)從4×4torus到16×16×16torus的擴(kuò)展(即從16個(gè)節(jié)點(diǎn)到4096個(gè)節(jié)點(diǎn)的擴(kuò)展)。通過合理選擇各維節(jié)點(diǎn)數(shù)與板內(nèi)、板間連接的帶寬，可以保證在擴(kuò)展過程中，T

11、-PSF的交換容量始終大于其端口容量，從而保證T-PSF的性能不會(huì)隨著擴(kuò)展而下降。 本論文的第七章介紹了使用OPNETModeler系統(tǒng)與C++語言自行開發(fā)的torus網(wǎng)絡(luò)軟件仿真平臺。該仿真平臺可以支持從1維到4維的任意規(guī)模的torus/mesh拓?fù)?、多種分組到達(dá)模型、多種負(fù)載模式模型、多種長度分布的變長分組、多種路由算法與調(diào)度算法，并且支持多優(yōu)先級業(yè)務(wù)，支持組播/廣播。在設(shè)計(jì)該仿真平臺時(shí)重點(diǎn)考慮了其擴(kuò)展能力，在該平臺上可以較