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

1、隨著因特網(wǎng)(Internet)應(yīng)用的日益廣泛，音視數(shù)據(jù)逐漸成為網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)的主體，對(duì)等(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ù)量有多個(gè)數(shù)量級(jí)的增長(zhǎng)。網(wǎng)絡(luò)應(yīng)用環(huán)境的上述變化，加上安全問題日益惡化，對(duì)通信子網(wǎng)(特別是骨干通信子網(wǎng))及其核心設(shè)備提出嚴(yán)峻挑戰(zhàn)。人們期待未來的通信子網(wǎng)更加安全可靠、易管理，可用性高，能夠根據(jù)用戶需求和服務(wù)性質(zhì)提

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

3、毫微秒級(jí)的門傳輸時(shí)延和存儲(chǔ)器訪問時(shí)間的制約，以及印制板工藝等方面的原因，構(gòu)建單波長(zhǎng)100Gbps速率和多端口的大容量高性能的交換機(jī)仍然是交換機(jī)設(shè)計(jì)中的難題。2010年發(fā)布IEEE802.3ba標(biāo)準(zhǔn)就因?yàn)槭茈娖骷南拗疲坏貌徊捎?0個(gè)10 Gbps的波長(zhǎng)合成100Gbps的端口速率，而未能直接利用光纖100 Gbps的波長(zhǎng)速率。因此，高光纖通信速率與電域內(nèi)相對(duì)較長(zhǎng)門傳輸時(shí)延及存儲(chǔ)器訪問時(shí)間之間的反差正是構(gòu)建大容量、高性能的交換結(jié)構(gòu)(Sw

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

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

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

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

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

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

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

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

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