可擴(kuò)展多級(jí)多平面交換網(wǎng)絡(luò)及調(diào)度算法研究.pdf

1、隨著Internet的快速發(fā)展，數(shù)據(jù)流量與網(wǎng)絡(luò)應(yīng)用呈爆炸式增長(zhǎng)，傳輸系統(tǒng)的傳輸速率隨著DWDM技術(shù)的成熟提高很快，而交換技術(shù)（包括交換結(jié)構(gòu)及調(diào)度算法）發(fā)展卻相對(duì)滯后，日漸成為通信網(wǎng)絡(luò)的性能瓶頸。單級(jí)結(jié)構(gòu)（crossbar）在核心路由器/交換機(jī)中占有非常重要的位置，其研究成果十分豐富，對(duì)交換結(jié)構(gòu)的發(fā)展起到了舉足輕重的推動(dòng)作用，但它的不足在如今的網(wǎng)絡(luò)環(huán)境中也是致命的。由于單級(jí)結(jié)構(gòu)先天缺乏可擴(kuò)展性，因其實(shí)現(xiàn)成本隨交換容量 N呈平方增長(zhǎng)，很難在

2、有限的芯片上實(shí)現(xiàn)大容量交換系統(tǒng)。
　　Log2N網(wǎng)絡(luò)與Clos網(wǎng)絡(luò)是兩種完全不同的多級(jí)結(jié)構(gòu)，無(wú)論是拓?fù)浣Y(jié)構(gòu)還是路由屬性都有很大的區(qū)別，但有一點(diǎn)卻是相同的，那就是它們都具有良好的可擴(kuò)展性，很容易構(gòu)建高速、大容量交換結(jié)構(gòu)。本論文以多級(jí)多平面交換結(jié)構(gòu)（包括log2N, Multi-log2N, Clos, Multi-Clos）為研究重點(diǎn)，主要的研究?jī)?nèi)容及研究成果包括以下幾個(gè)方面：
　　?分析研究了單級(jí)結(jié)構(gòu)（crossbar）及相

3、應(yīng)的調(diào)度算法
　　因可擴(kuò)展性原因，單級(jí)結(jié)構(gòu)無(wú)法適應(yīng)信息容量急劇膨脹和網(wǎng)絡(luò)應(yīng)用復(fù)雜多樣的實(shí)際需求，但它是其它可擴(kuò)展交換結(jié)構(gòu)的基礎(chǔ)，無(wú)論從拓?fù)浣Y(jié)構(gòu)，還是從調(diào)度算法都如此。因此，我們首先分析研究了單級(jí)結(jié)構(gòu)及相應(yīng)的調(diào)度算法，主要分析討論各種形式的單級(jí)結(jié)構(gòu)及各自的優(yōu)缺點(diǎn)，包括 OQ，IQ和 CIOQ等。其次，分析研究了針對(duì)單級(jí)結(jié)構(gòu)的經(jīng)典的調(diào)度算法，如PIM算法，iSLIP算法等。
　　?分析研究了多級(jí)結(jié)構(gòu)Log2N，Multi-log

4、2N及調(diào)度算法
　　就拓?fù)浣Y(jié)構(gòu)而言，log2N網(wǎng)絡(luò)的相鄰級(jí)采用部分連接，這導(dǎo)致log2N網(wǎng)絡(luò)的路由路徑唯一性。路徑唯一性產(chǎn)生兩個(gè)方面的結(jié)果：自選路由和內(nèi)部阻塞。自選路由簡(jiǎn)化了路由控制，而內(nèi)部阻塞卻影響了交換性能。為了解決內(nèi)部阻塞，通過(guò)將多個(gè)log2N網(wǎng)絡(luò)構(gòu)建Multi-log2N結(jié)構(gòu)來(lái)破壞路徑唯一性。由于HC型（水平級(jí)連）的Multi-log2N增加了網(wǎng)絡(luò)直徑，不利于光交換，因此我們?cè)谡撐闹兄攸c(diǎn)研究 VS（垂直堆疊）型Multi-

5、log2N結(jié)構(gòu)。為了實(shí)現(xiàn)真正的無(wú)阻塞路由，本論文提出了基于沖突鏈路集的控制算法（CA-CLS）。CA-CLS算法解決了內(nèi)部阻塞的問(wèn)題，但未解決SE的共享問(wèn)題，以至于在光交換過(guò)程產(chǎn)生光串?dāng)_，嚴(yán)重影響交換性能，于是又提出基于置換多重分解的控制算法（CA-MDP），并詳細(xì)分析了CA-MDP算法性能及解決光串?dāng)_問(wèn)題的有效性。
　　?分析研究Clos，Multi-Clos結(jié)構(gòu)及調(diào)度算法
　　Clos網(wǎng)絡(luò)的相鄰級(jí)采用完全互連模式，因此

6、Clos是多路徑網(wǎng)絡(luò)，任意輸入-輸出之間都存在多條路由路徑，因此路由控制較log2N復(fù)雜，當(dāng)然可通過(guò)適當(dāng)?shù)木W(wǎng)絡(luò)配置來(lái)實(shí)現(xiàn)嚴(yán)格無(wú)阻塞，可重排無(wú)阻塞等的無(wú)阻塞結(jié)構(gòu)。Clos網(wǎng)絡(luò)中輸入-輸出之間的路徑條數(shù)是由中間級(jí)（CS）的交換模塊（CM）數(shù)來(lái)決定的，即 Clos網(wǎng)絡(luò)中路徑的選擇（或分配）問(wèn)題可等價(jià)地轉(zhuǎn)化為 CM的分配問(wèn)題，于是本文提出基于矩陣分解的并行路由控制算法（PRD-MD）。PRD-MD算法不同于已有的矩陣分解算法，它采用了逐行分解，

7、不僅實(shí)現(xiàn)路徑的選擇，而且解決了其它同類(lèi)算法的不完全性，能徹底分解滿(mǎn)足條件的任意業(yè)務(wù)矩陣。另外，針對(duì) CRRD算法存在的不足，本論文提出了主動(dòng)授權(quán)的CRRD算法（CRRD-AG）。CRRD-AG不僅能有效降低額外的仲裁信息量，而且充分利用CS級(jí)的鏈路帶寬，可提高吞吐率。
　　Multi-Clos結(jié)構(gòu)具有很強(qiáng)的可擴(kuò)展性，很容易通過(guò)添加平面來(lái)實(shí)現(xiàn)大容量交換系統(tǒng)。我們?cè)赥rueWay的基礎(chǔ)上也提出了關(guān)于Multi-Clos的一些基本思路，