用Ｔｏｒｕｓ網(wǎng)絡(luò)構(gòu)建可擴展分組交換結(jié)構(gòu)的設(shè)計方案

摘要：提出了一種采用Torus網(wǎng)絡(luò)技術(shù)的模塊化交換子網(wǎng)結(jié)構(gòu)——可配置單板（CB），給出了應(yīng)用CB模塊構(gòu)建可擴展交換結(jié)構(gòu)的具體設(shè)計方案，并討論了關(guān)鍵設(shè)計參數(shù)的取值。該方案支持交換端口數(shù)與交換容量數(shù)百倍的平滑擴展。仿真實驗結(jié)果驗證了該方案的可行性。

關(guān)鍵詞：分組交換結(jié)構(gòu); 可擴展性; Torus網(wǎng)絡(luò)

中圖分類號：TP393.03文獻標志碼：A

文章編號：1001－3695(2008)03－0866－03

下一代核心交換機/路由器的關(guān)鍵部件——分組交換結(jié)構(gòu)除了需要有極大的交換容量外，還應(yīng)該具有很強的可擴展性，這已經(jīng)成為運營商、設(shè)備商與學術(shù)界的共識。傳統(tǒng)PSF大多采用crossbar、共享總線、共享緩存、多級互聯(lián)網(wǎng)絡(luò)（multistage interconnection networks， MIN）等結(jié)構(gòu)，由于受到crossbar規(guī)模、總線帶寬、緩存讀寫速率以及集中仲裁調(diào)度方式等方面的限制，其可擴展性不理想[1，2]。

Torus網(wǎng)絡(luò)具有大容量、高可靠性、良好的可擴展性等特點，所以是一種很有前景的下一代PSF技術(shù)。用Torus網(wǎng)絡(luò)構(gòu)建可擴展PSF已成為當前的研究熱點之一[3，4]。已有研究主要集中在IP業(yè)務(wù)對Torus網(wǎng)絡(luò)的交換能力的影響，針對IP業(yè)務(wù)特點所優(yōu)化的路由、調(diào)度算法等方面，還鮮有研究具體構(gòu)建和擴展方案的報道。本文提出了一種可用來構(gòu)建采用Torus網(wǎng)絡(luò)拓撲的可擴展PSF的交換子網(wǎng)結(jié)構(gòu)——可配置單板。選擇合適數(shù)量的CB模塊并靈活地配置模塊內(nèi)與模塊之間的連接方式，可以構(gòu)建出不同拓撲規(guī)模的Torus網(wǎng)絡(luò)，從而實現(xiàn)可擴展PSF。例如，使用有16個交換節(jié)點的CB，可以實現(xiàn)交換端口數(shù)量16~4 069的平滑擴展。合理選擇網(wǎng)絡(luò)拓撲以及交換節(jié)點間連接的帶寬，可以保證PSF所能支持的交換容量的增長不低于實際容量的增長，即保證PSF的性能不會隨著擴展而下降。

1定義

定義1n維Torus網(wǎng)絡(luò)是一個n維圖，每維ki個節(jié)點，ki≥2，0≤i≤n-1。圖中的每個節(jié)點X可用其坐標向量(x0，x1，…，xn-2，xn-1)來表示。其中對所有的0≤i≤n-1有0≤xi≤ki-1。任意兩個節(jié)點(x0，x1，…，xn-1)與(y0，y1，…，yn-1)相鄰（即通過鏈路相連）的條件是這兩個節(jié)點在某一維j上的坐標不相等，且yj=xj±1 mod kj，而其他各維上的坐標都相等[5]。

如果每一維上的節(jié)點個數(shù)相等，即對所有0≤i≤n-1有ki=k，則稱此Torus網(wǎng)絡(luò)為k元n方網(wǎng)絡(luò)（kary ncube）。

定義2把一個Torus網(wǎng)絡(luò)分為節(jié)點個數(shù)相等的兩部分所需要切斷的鏈路數(shù)的最小值被稱為對分寬度（bisection width），記為W。這些鏈路的帶寬之和被稱為對分帶寬（bisection bandwidth），記為B，于是B=2bW。其中b是單向鏈路的帶寬。

圖1(a)給出了一個4×3×2的3維Torus網(wǎng)絡(luò)示意圖（圖中的實心圓形代表節(jié)點；每兩個節(jié)點之間的連線代表了連接這兩個節(jié)點的一條雙向物理鏈路），并給出了計算該Torus網(wǎng)絡(luò)的對分帶寬的示意。

一般情況下，一個n維Torus網(wǎng)絡(luò)的對分寬度為

W=2∏i≠jki。

其中：j是節(jié)點數(shù)最多的那一維，即kj=max(ki)，0≤i≤n-1。于是其對分帶寬為

B=4b∏i≠jki(1)

其中： j是節(jié)點數(shù)最多的那一維；b是單向鏈路的帶寬。顯然，對于k元n方網(wǎng)絡(luò)有

B=4bkn-1。

對分帶寬表征了Torus網(wǎng)絡(luò)理論上的交換容量。交換容量C與對分帶寬B之間存在如下關(guān)系[5]：按照計算對分帶寬的辦法，沿分界面P把整個Torus網(wǎng)絡(luò)劃分為節(jié)點數(shù)相等的兩個部分。假設(shè)使用最短路由算法，對于任何業(yè)務(wù)，當其源、目的節(jié)點位于同一部分內(nèi)時則該業(yè)務(wù)不經(jīng)過P；反之則經(jīng)過P。當業(yè)務(wù)呈均勻分布時，一個業(yè)務(wù)的源、目的節(jié)點位于同一部分內(nèi)的概率是1/2，所以通過分界面P的業(yè)務(wù)量為C/2，即B=C/2。

(a) 4×3×2 Torus網(wǎng)絡(luò)及其對分帶寬的計算

(b) 注入業(yè)務(wù)量、被接受業(yè)務(wù)量與吞吐率

定義3單位時間內(nèi)由信息源注入網(wǎng)絡(luò)的信息量（可以用分組數(shù)或比特數(shù)來表示）稱為注入業(yè)務(wù)量（applied load）；網(wǎng)絡(luò)在單位時間內(nèi)所交付的信息量稱為被接受業(yè)務(wù)量（accepted traffic）。被接受業(yè)務(wù)量的大小通常隨著注入業(yè)務(wù)量的大小而變化，其最大值被稱為吞吐率。使被接受業(yè)務(wù)量達到最大值（即吞吐率）的注入業(yè)務(wù)量的值被稱為飽和點[5]。

吞吐率是衡量PSF交換能力最重要的指標。一般情況下，在Torus網(wǎng)絡(luò)中，在注入業(yè)務(wù)量達到飽和點之前，所有分組都可以及時被交付，所以被接受業(yè)務(wù)量約等于注入業(yè)務(wù)量；當達到飽和點之后，對于確定性路由算法，被接受業(yè)務(wù)量通常保持在其最大值（即吞吐率）不變，而對于完全自適應(yīng)路由算法，在不引入額外的注入控制機制時，被接受業(yè)務(wù)量往往會隨著注入業(yè)務(wù)量的增大而減小[6]（圖1(b)）。

定義4在Torus網(wǎng)絡(luò)中，每個節(jié)點上都有一個雙向交換端口，設(shè)其I/O帶寬為c，則Torus網(wǎng)絡(luò)的實際容量為C0=NC0。其中N是節(jié)點總數(shù)。

2可擴展PSF的設(shè)計方案

2．1用Torus網(wǎng)絡(luò)構(gòu)建PSF需注意的原則

2．1．1合理選擇Torus網(wǎng)絡(luò)的維度數(shù)

比較不同維度數(shù)的Torus網(wǎng)絡(luò)：如果節(jié)點總數(shù)（即PSF的規(guī)模）固定不變，維度高就意味著每維節(jié)點數(shù)少、節(jié)點連接度高，因此網(wǎng)絡(luò)的直徑小、對分帶寬大。直徑小有利于減小交換延遲，而對分帶寬大有利于提高吞吐率。因為理論上Torus網(wǎng)絡(luò)的交換容量與其對分帶寬成正比。所以高維Torus網(wǎng)絡(luò)在交換延遲、吞吐率等性能指標上具有天生的優(yōu)勢。表1列出了節(jié)點總數(shù)相同但維度數(shù)不同的幾種Torus網(wǎng)絡(luò)的直徑與對分帶寬，其中單向鏈路帶寬設(shè)為1 Gbps。

高維度也會帶來成本與技術(shù)上的問題。由于每個節(jié)點的連接度高，從而需要更多的節(jié)點緩存與節(jié)點間鏈路。這直接增加了交換結(jié)構(gòu)的實現(xiàn)成本，同時加大了交換節(jié)點上的緩存管理、調(diào)度、控制信息傳輸與處理等模塊的復(fù)雜度，不利于節(jié)點實現(xiàn)。表2列出了節(jié)點總數(shù)相同但維度數(shù)不同的幾種Torus網(wǎng)絡(luò)的節(jié)點連接度與鏈路總數(shù)。

選擇合理的維度數(shù)也就意味著在性能與成本及實現(xiàn)難度之間取得折中。由于4維及更高維的Torus網(wǎng)絡(luò)實現(xiàn)難度太大，實際系統(tǒng)通常采用2或3維的拓撲。本文所提出的設(shè)計方案采用3維Torus網(wǎng)絡(luò)。

在實際系統(tǒng)中，由于Torus網(wǎng)絡(luò)不是內(nèi)部無阻塞結(jié)構(gòu)，同時為了處理峰值業(yè)務(wù)和不均勻分布的業(yè)務(wù)，通常需要一定的內(nèi)部提速。一般鏈路帶寬b取根據(jù)式(3)所計算得到的理論值的2~4倍。

在采用Torus網(wǎng)絡(luò)構(gòu)建可擴展PSF時，通常是通過擴大拓撲規(guī)模增加節(jié)點、鏈路數(shù)量，而不改變節(jié)點與鏈路的類型，所以c固定不變，而kj則隨著拓撲規(guī)模的變化而變化，需要根據(jù)最大規(guī)模時的kj的值來確定b的值。

2．2可配置單板

每個CB模塊上共有16個交換節(jié)點，節(jié)點的結(jié)構(gòu)如圖2所示。每個節(jié)點上都有一個雙向交換端口與外界的信道相連。同時節(jié)點上還有小型的交換單元連接到其他節(jié)點。當一對交換端口需要通信時，分組從源端口所在節(jié)點出發(fā)，通過若干個交換節(jié)點進行轉(zhuǎn)發(fā)，最終到達目的端口所在節(jié)點。從Torus網(wǎng)絡(luò)與交換節(jié)點的結(jié)構(gòu)可以看出：只要增加交換節(jié)點數(shù)量，即擴大Torus網(wǎng)絡(luò)的拓撲規(guī)模，則交換端口的數(shù)量也會隨之增加，而且全網(wǎng)的交換單元與鏈路的數(shù)量也會增加。正是這一特點保證了Torus網(wǎng)絡(luò)的交換容量能夠隨著端口數(shù)量的增長而增長，從而具有良好的可擴展性。

在CB模塊上，這16個節(jié)點可以通過板內(nèi)連接互連。板內(nèi)連接是可配置的，共有三種連接方式，如圖3(a)所示。圖中圓圈表示節(jié)點，虛線表示板內(nèi)連接。Ⅰ型連接方式其實是一種4×4的二維拓撲；Ⅱ型連接方式是一種8×2的二維拓撲，Ⅲ型連接方式是16×1的一維拓撲。

CB模塊之間還可以通過板間連接互連，從而構(gòu)成Torus網(wǎng)絡(luò)的拓撲。圖3(b)給出了采用Ⅰ型CB實現(xiàn)4×4 Torus的板間連接方式；(c)給出了采用Ⅱ型CB實現(xiàn)8×4×3 Torus的板間連接方式。圖中虛線表示板內(nèi)連接，實線表示板間連接。

2．3用CB構(gòu)建可擴展PSF的方案

按照圖3所示的板內(nèi)、板間連接方式，采用CB模塊可以方便地實現(xiàn)從4×4 Torus到16×16×16 Torus的擴展。其中X維的鏈路主要由板內(nèi)連接來實現(xiàn)，而Y維與Z維的鏈路則由板內(nèi)與板間連接共同實現(xiàn)。考慮到2．1．2節(jié)的要求，對每一維的節(jié)點個數(shù)需要進行合理選擇。表3列出了筆者設(shè)計選用的拓撲規(guī)模。

由式(2)，Torus網(wǎng)絡(luò)的鏈路帶寬與其拓撲規(guī)模有關(guān)，隨著每維節(jié)點數(shù)最大值的增加而增加。由于本方案設(shè)計的是可擴展PSF，鏈路帶寬由其所能擴展到的最大規(guī)模來決定。圖4給出了本設(shè)計方案的交換容量與實際容量隨節(jié)點數(shù)的增加而增長的情況。圖4中單個交換節(jié)點的I/O帶寬c為1 Gbps，鏈路帶寬分別為1與2 Gbps。可以看出：當使用帶寬為1 Gbps的鏈路時，可以滿足PSF的節(jié)點數(shù)（實際容量）從4×4（16 Gbps）擴展到8×8×8（512 Gbps），在此過程中PSF的交換容量始終大于等于其實際容量，即交換性能不會隨著擴展而下降；當使用帶寬為2 Gbps的鏈路時，可以滿足PSF的節(jié)點數(shù)（實際容量）擴展到16×16×16（4 096 Gbps）。

本文設(shè)計在實際系統(tǒng)中采用2倍內(nèi)部提速，即使用帶寬為2 Gbps的鏈路來構(gòu)建最大擴展到512 Gbps的PSF，使用帶寬為4 Gbps的鏈路來構(gòu)建最大擴展到4 096 Gbps的PSF。

3仿真結(jié)果

本文使用OPNET Modeler平臺搭建了本設(shè)計方案的仿真系統(tǒng)，從4×4到16×16×16這一擴展范圍內(nèi)選取不同規(guī)模的網(wǎng)絡(luò)進行仿真，并比較其所能達到的吞吐率。仿真系統(tǒng)采用帶寬為4 Gbps的鏈路，并使用蟲孔交換（wormhole switching）技術(shù)[7]。本文選用了Duato’s protocol路由算法[8]。這是一種經(jīng)典的Torus網(wǎng)絡(luò)中的自適應(yīng)路由算法，在性能與算法復(fù)雜度和實現(xiàn)代價之間取得了很好的平衡，有著廣泛的應(yīng)用。受篇幅限制，只在圖5中給出4×4×4、8×8×8與16×16×16這三種規(guī)模下的仿真結(jié)果，其他規(guī)模下的結(jié)果具有類似的變化趨勢。

可以看出：當采用帶寬為4 Gbps的鏈路時，擴展至最大規(guī)模（16×16×16）的PSF的飽和點約為1.2 Gbps（由于Duato’s protocol是完全自適應(yīng)路由算法，進一步增大注入業(yè)務(wù)量會導致被接受業(yè)務(wù)量減小）；對于更小的規(guī)模，如4×4×4與8×8×8，其飽和點遠大于1.2 Gbps。這一結(jié)果證明本文的設(shè)計方案足以支持節(jié)點I/O帶寬為1 Gbps的PSF擴展至16×16×16的規(guī)模。

4結(jié)束語

本文研究了在采用Torus網(wǎng)絡(luò)構(gòu)建可擴展分組交換結(jié)構(gòu)時，怎樣設(shè)計具體構(gòu)建方案才能有效發(fā)揮Torus網(wǎng)絡(luò)良好的可擴展性。在概括了三個需要注意的設(shè)計原則之后，提出了一種采用模塊化的交換子網(wǎng)結(jié)構(gòu)（可配置單板）構(gòu)建可擴展分組交換結(jié)構(gòu)的設(shè)計方案，并舉例說明了一些重要的設(shè)計參數(shù)應(yīng)怎樣確定。仿真結(jié)果表明本設(shè)計方案可以支持交換端口數(shù)與容量上百倍的擴展。

參考文獻：

[1]Dune Networks Inc. Nextgeneration switchfabric[EB/OL］. http://www.dunenetworks.com/products/papers/DNScalabilityWP v1.2.pdf.

[2]許都， 朱旭東， 李樂民. 下一代可擴展交換機/路由器[J]. 電子科技大學學報， 2003， 32(3):230－234.

[3]DALLY W J. Scalable switching fabrics for Internet routers[EB/OL]. http://www.avici.com/technology/whitepapers/TSRfabricWhitePaper.pdf.

[4]ZHU Xudong， WANG Hong， LI Lemin. A terabit switching fabric employing direct interconnection networks[C]//Proc of IEEE GLOBECOM’03. San Francisco：[s.n.]， 2003:2982－2986.

[5]DUATO J， YALAMANCHILI S， NI L. Interconnection networks: an engineering approach[M]. revised ed. San Francisco: Morgan Kaufmann， 2002.

[6]BAYDAL E， LOPEZ P， DUATO J. A family of mechanisms for congestion control in wormhole networks[J]. IEEE Trans on Parallel and Distributed Systems， 2005，16(9):772－784.

[7]NI L M， McKINLEY P K. A survey of wormhole routing techniques in direct network[J]. IEEE Computer， 1993，26(2):62－76.

[8]GAUGHAN P T， YALAMANCHILI S. Adaptive routing protocols for hypercube interconnection networks[J]. IEEE Computer， 1993，26(5):12－23.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”