高性能大容量多級交換結構與調度算法研究.pdf

1、隨著因特網(wǎng)(Internet)應用的日益廣泛，音視數(shù)據(jù)逐漸成為網(wǎng)絡應用數(shù)據(jù)的主體，對等(P2P)關系也因此成為繼瀏覽器朋艮務器(B/S)模式之后的新型應用模式。加上網(wǎng)絡應用的種類和數(shù)量不斷增加，網(wǎng)絡用戶數(shù)呈指數(shù)規(guī)律劇增，網(wǎng)絡應用數(shù)據(jù)量有多個數(shù)量級的增長。網(wǎng)絡應用環(huán)境的上述變化，加上安全問題日益惡化，對通信子網(wǎng)(特別是骨干通信子網(wǎng))及其核心設備提出嚴峻挑戰(zhàn)。人們期待未來的通信子網(wǎng)更加安全可靠、易管理，可用性高，能夠根據(jù)用戶需求和服務性質提

2、供不同質量的數(shù)據(jù)傳輸服務；要求骨干通信子網(wǎng)的核心交換設備具有更大容量(端口數(shù)與單口速率的乘積)、更優(yōu)的交換性能(轉發(fā)速率、傳輸時延、抖動等)。
　　以密集波分復用為代表的光通信技術，將單個波長的數(shù)據(jù)傳輸速率提高到160Gbps以上，為構建高速率的交換機提供了良好的通信條件。但是，由于缺少可用的光存儲器件和光處理器，在全光域內實現(xiàn)分組交換尚不現(xiàn)實，現(xiàn)代的交換機的交換結構的構建還只能在電域內實現(xiàn)，或采用光電相結合的方式。然而電子器件的

3、毫微秒級的門傳輸時延和存儲器訪問時間的制約，以及印制板工藝等方面的原因，構建單波長100Gbps速率和多端口的大容量高性能的交換機仍然是交換機設計中的難題。2010年發(fā)布IEEE802.3ba標準就因為受電器件的限制，不得不采用10個10 Gbps的波長合成100Gbps的端口速率，而未能直接利用光纖100 Gbps的波長速率。因此，高光纖通信速率與電域內相對較長門傳輸時延及存儲器訪問時間之間的反差正是構建大容量、高性能的交換結構(Sw

4、itch fabric)的難點，也正是本論文研究工作的大背景。
　　多年以來，網(wǎng)絡中繼設備(路由器、交換機)的核心部件--“交換結構”經(jīng)歷了總線結構、共享存儲器結構和交叉連接(Crossbar)三大階段。盡管Crossbar仍然是當今交換機使用的核心交換結構，但由于受電子技術和工藝水平的限制，“單級crossbar交換”在交換速率和端口數(shù)量方面已經(jīng)達到現(xiàn)有技術的極限，難以適應現(xiàn)代和未來交換機對容量和性能的需要，于是出現(xiàn)了多級cro

5、ssbar交換結構。典型的多級交換結構包括“負載均衡交換結構”(LB switch fabric)和“Clos網(wǎng)絡互聯(lián)結構”兩種，也正是本文研究的主題。
　　LB交換結構利用多個交換單元(交叉開關或陣列波導光柵)組成多級交換機以改進其性能，單個交換單元的調度采用簡單但嚴格的時分復用調度，即可獲得100％的吞吐率。其代價是總交換的時延增加，還可能出現(xiàn)信元(Cell)錯序的問題。作者在本論文中對LB交換結構的貢獻主要兩方面：1)提出了

6、增強型LB交換結構以解決其時延大的問題，即用適應性時分復用(ATDM)取代嚴格的TDM調度，避免時槽利用不充分問題(稱為“連接浪費”)；2)提出用虛擬中間級隊列(VCQ)和虛擬輸入隊列集(VIQ set)相結合的方式，保證交換信元不失序，首次將整個交換機的調度時間復雜度降低為O(1)，并且保證了100％的吞吐率和良好的時延性能。作者還分別探討了用交叉開關電子器件和陣列波導光柵光器件作為基本交換單元的可行性和利弊。
　　對LB交換結

7、構的嚴重的批評是：為了改進交換機的性能或擴容，與另一類多級交換結構(Clos)相比，它使用的基本交換單元過多。論文中作者對Clos結構的研究包括三個方面：
　　首先，本文提出了一種在無緩存的Clos網(wǎng)絡結構中實現(xiàn)100％吞吐率的調度算法StablePlus。利用StablePlus的特點，作者將Clos網(wǎng)絡中的Karol路徑分配的算法的復雜度降低為O(1)，可以方便地利用筆者設計的專用硬件來實現(xiàn)。StablePlus是首個在O(1

8、)的調度復雜度下，使Clos網(wǎng)絡交換機達到100％吞吐率和良好時延性能的調度算法。通過對StablePlus執(zhí)行過程和執(zhí)行順序的進一步優(yōu)化，交換機整體的調度時間大大縮短，盡管StablePlus能夠在較大范圍內適應較大容量和高性能交換的需要，但是受無緩存Clos網(wǎng)絡結構的局限性的影響，進一步擴大超大容量交換受到制約，需要探索新的技術。本文的其余部分將聚焦于帶存儲的Clos網(wǎng)絡結構。
　　作者對于帶緩存的Clos網(wǎng)絡交換機的貢獻主要

9、在于提出了創(chuàng)新的“模塊級匹配”的概念。作者首先將這個概念應用于MSM(Memory-Space-Memroy)的Clos網(wǎng)絡交換機之中，它將傳統(tǒng)“端口級匹配”的調度方式轉變?yōu)椤澳K級匹配”的調度，這個轉變帶來的優(yōu)勢有：減少了調度器需要處理的請求和相應的數(shù)量，并且避免了在Clos網(wǎng)絡中復雜的路徑分配問題。因此，這樣的一個調度器可以在單個電路板、甚至是單個芯片當中實現(xiàn)，這對于實現(xiàn)大容量交換機是非常必要的，而這個優(yōu)勢在無緩存的交換機當中是無法

10、實現(xiàn)的。使用“模塊級匹配”所帶來的另外一大好處在于可以避免信元錯序的問題。因為每次都有一個幀的信元同時穿過Clos網(wǎng)絡的所有中間級。此外，在MSM的Clos網(wǎng)絡交換機中應用“模塊級匹配”可以應用大量文獻中成熟的單級輸入排隊交換機的調度算法，并且如果選擇穩(wěn)定的調度算法，Clos網(wǎng)絡便可達到100％的吞吐率。為了彌補基于幀的調度所帶來的較長的等待成幀時間的問題，作者提出了靜態(tài)信元分發(fā)和動態(tài)信元分發(fā)兩種各有特點的解決方案，并通過仿真實驗驗證了

11、他們的有效性。
　　然后，作者嘗試將“模塊級匹配”的概念應用到三級帶緩存(MMM，Memory-Memory-Memory)的Clos網(wǎng)絡結構中，獲得了很好的效果。MMM的Clos網(wǎng)絡可以完全模擬一個單級CICQ(Combined Input and Crosspoint Queued)交換機。因此所有CICQ交換機的優(yōu)點都可以被繼承，例如其僅使用簡單調度即可達到的高性能以及僅需要較小的緩存即可達到很高的吞吐率。并且文獻中關于CI

12、CQ交換機的大量的成熟調度算法都可以直接應用到Clos網(wǎng)絡中。作者試圖在Clos網(wǎng)絡中應用CICQ交換機中的經(jīng)典算法SQUISH，并達到了100％的吞吐率。更加重要的是，使用SQUISH的Clos網(wǎng)絡表現(xiàn)出了極強的抗突發(fā)性，在極大的突發(fā)流量下，仍然可以達到95％以上的吞吐率。而在低負載下，和MSM的模塊級匹配交換機類似，可以使用靜態(tài)或者動態(tài)信元分發(fā)的方法彌補以幀為單位調度的不足。
　　最終，對于所有有緩存的多級交換機都會遇到的擁塞