本文選題：路由算法 + 可擴(kuò)展性��； 參考：《電子科技大學(xué)》2015年博士論文

【摘要】：隨著Internet的快速發(fā)展,數(shù)據(jù)流量與網(wǎng)絡(luò)應(yīng)用呈爆炸式增長,傳輸系統(tǒng)的傳輸速率隨著DWDM技術(shù)的成熟提高很快,而交換技術(shù)(包括交換結(jié)構(gòu)及調(diào)度算法)發(fā)展卻相對滯后,日漸成為通信網(wǎng)絡(luò)的性能瓶頸。單級結(jié)構(gòu)(crossbar)在核心路由器/交換機(jī)中占有非常重要的位置,其研究成果十分豐富,對交換結(jié)構(gòu)的發(fā)展起到了舉足輕重的推動作用,但它的不足在如今的網(wǎng)絡(luò)環(huán)境中也是致命的。由于單級結(jié)構(gòu)先天缺乏可擴(kuò)展性,因其實現(xiàn)成本隨交換容量N呈平方增長,很難在有限的芯片上實現(xiàn)大容量交換系統(tǒng)。Log2N網(wǎng)絡(luò)與Clos網(wǎng)絡(luò)是兩種完全不同的多級結(jié)構(gòu),無論是拓?fù)浣Y(jié)構(gòu)還是路由屬性都有很大的區(qū)別,但有一點卻是相同的,那就是它們都具有良好的可擴(kuò)展性,很容易構(gòu)建高速、大容量交換結(jié)構(gòu)。本論文以多級多平面交換結(jié)構(gòu)(包括log2N,Multi-log2N,Clos,Multi-Clos)為研究重點,主要的研究內(nèi)容及研究成果包括以下幾個方面:分析研究了單級結(jié)構(gòu)(crossbar)及相應(yīng)的調(diào)度算法因可擴(kuò)展性原因,單級結(jié)構(gòu)無法適應(yīng)信息容量急劇膨脹和網(wǎng)絡(luò)應(yīng)用復(fù)雜多樣的實際需求,但它是其它可擴(kuò)展交換結(jié)構(gòu)的基礎(chǔ),無論從拓?fù)浣Y(jié)構(gòu),還是從調(diào)度算法都如此。因此,我們首先分析研究了單級結(jié)構(gòu)及相應(yīng)的調(diào)度算法,主要分析討論各種形式的單級結(jié)構(gòu)及各自的優(yōu)缺點,包括OQ,IQ和CIOQ等。其次,分析研究了針對單級結(jié)構(gòu)的經(jīng)典的調(diào)度算法,如PIM算法,iSLIP算法等。分析研究了多級結(jié)構(gòu)Log2N,Multi-log2N及調(diào)度算法就拓?fù)浣Y(jié)構(gòu)而言,log2N網(wǎng)絡(luò)的相鄰級采用部分連接,這導(dǎo)致log2N網(wǎng)絡(luò)的路由路徑唯一性。路徑唯一性產(chǎn)生兩個方面的結(jié)果:自選路由和內(nèi)部阻塞。自選路由簡化了路由控制,而內(nèi)部阻塞卻影響了交換性能。為了解決內(nèi)部阻塞,通過將多個log2N網(wǎng)絡(luò)構(gòu)建Multi-log2N結(jié)構(gòu)來破壞路徑唯一性。由于HC型(水平級連)的Multi-log2N增加了網(wǎng)絡(luò)直徑,不利于光交換,因此我們在論文中重點研究VS(垂直堆疊)型Multi-log2N結(jié)構(gòu)。為了實現(xiàn)真正的無阻塞路由,本論文提出了基于沖突鏈路集的控制算法(CA-CLS)。CA-CLS算法解決了內(nèi)部阻塞的問題,但未解決SE的共享問題,以至于在光交換過程產(chǎn)生光串?dāng)_,嚴(yán)重影響交換性能,于是又提出基于置換多重分解的控制算法(CA-MDP),并詳細(xì)分析了CA-MDP算法性能及解決光串?dāng)_問題的有效性。分析研究Clos,Multi-Clos結(jié)構(gòu)及調(diào)度算法Clos網(wǎng)絡(luò)的相鄰級采用完全互連模式,因此Clos是多路徑網(wǎng)絡(luò),任意輸入-輸出之間都存在多條路由路徑,因此路由控制較log2N復(fù)雜,當(dāng)然可通過適當(dāng)?shù)木W(wǎng)絡(luò)配置來實現(xiàn)嚴(yán)格無阻塞,可重排無阻塞等的無阻塞結(jié)構(gòu)。Clos網(wǎng)絡(luò)中輸入-輸出之間的路徑條數(shù)是由中間級(CS)的交換模塊(CM)數(shù)來決定的,即Clos網(wǎng)絡(luò)中路徑的選擇(或分配)問題可等價地轉(zhuǎn)化為CM的分配問題,于是本文提出基于矩陣分解的并行路由控制算法(PRD-MD)。PRD-MD算法不同于已有的矩陣分解算法,它采用了逐行分解,不僅實現(xiàn)路徑的選擇,而且解決了其它同類算法的不完全性,能徹底分解滿足條件的任意業(yè)務(wù)矩陣。另外,針對CRRD算法存在的不足,本論文提出了主動授權(quán)的CRRD算法(CRRD-AG)。CRRD-AG不僅能有效降低額外的仲裁信息量,而且充分利用CS級的鏈路帶寬,可提高吞吐率。Multi-Clos結(jié)構(gòu)具有很強(qiáng)的可擴(kuò)展性,很容易通過添加平面來實現(xiàn)大容量交換系統(tǒng)。我們在TrueWay的基礎(chǔ)上也提出了關(guān)于Multi-Clos的一些基本思路,目前雖無成熟的研究成果,但將是我們后續(xù)的研究目標(biāo)。
[Abstract]:With the rapid development of Internet , data traffic and network application are exploding , the transmission rate of transmission system increases rapidly with the maturity of DWDM technology , and the switching technology ( including switching fabric and scheduling algorithm ) is very important . In this paper , we propose a control algorithm ( CA - MDP ) based on permutation multiple decomposition , and analyze the performance of the CA - MDP algorithm and the effectiveness of solving the problem of optical crosstalk . The path number between the input - output in the Clos network is determined by the number of switching modules ( CM ) of the intermediate stage ( CS ) .

【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP393.01

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 張賓;楊家海;吳建平;;Internet流量模型分析與評述[J];軟件學(xué)報;2011年01期

，

本文編號：1826925