用Ｔｏｒｕｓ網絡構建可擴展分組交換結構的設計方案

摘要：提出了一種采用Torus網絡技術的模塊化交換子網結構——可配置單板（CB），給出了應用CB模塊構建可擴展交換結構的具體設計方案，并討論了關鍵設計參數的取值。該方案支持交換端口數與交換容量數百倍的平滑擴展。仿真實驗結果驗證了該方案的可行性。

關鍵詞：分組交換結構; 可擴展性; Torus網絡

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

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

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

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

1定義

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

如果每一維上的節點個數相等，即對所有0≤i≤n-1有ki=k，則稱此Torus網絡為k元n方網絡（kary ncube）。

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

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

一般情況下，一個n維Torus網絡的對分寬度為

W=2∏i≠jki。

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

B=4b∏i≠jki(1)

其中： j是節點數最多的那一維；b是單向鏈路的帶寬。顯然，對于k元n方網絡有

B=4bkn-1。

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

(a) 4×3×2 Torus網絡及其對分帶寬的計算

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

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

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

定義4在Torus網絡中，每個節點上都有一個雙向交換端口，設其I/O帶寬為c，則Torus網絡的實際容量為C0=NC0。其中N是節點總數。

2可擴展PSF的設計方案

2．1用Torus網絡構建PSF需注意的原則

2．1．1合理選擇Torus網絡的維度數

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

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

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

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

在采用Torus網絡構建可擴展PSF時，通常是通過擴大拓撲規模增加節點、鏈路數量，而不改變節點與鏈路的類型，所以c固定不變，而kj則隨著拓撲規模的變化而變化，需要根據最大規模時的kj的值來確定b的值。

2．2可配置單板

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

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

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

2．3用CB構建可擴展PSF的方案

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

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

本文設計在實際系統中采用2倍內部提速，即使用帶寬為2 Gbps的鏈路來構建最大擴展到512 Gbps的PSF，使用帶寬為4 Gbps的鏈路來構建最大擴展到4 096 Gbps的PSF。

3仿真結果

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

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

4結束語

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

參考文獻：

[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.

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