高性能大容量多級交換結(jié)構(gòu)與調(diào)度算法研究.pdf

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

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

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

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

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

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

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

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

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

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

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

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