k元n方的高維交換結(jié)構(gòu)和多播研究.pdf

1、在因特網(wǎng)快速發(fā)展的今天,寬帶視頻、多媒體等業(yè)務(wù)對(duì)路由器技術(shù)提出了史高的要求,快速增長(zhǎng)的網(wǎng)絡(luò)流量也要求交換容量不斷升級(jí)。k元n方交換結(jié)構(gòu)由于其靈活的擴(kuò)展性,已成為構(gòu)建大容量可擴(kuò)展路由器的常用選擇。 一方面,采用多維交換結(jié)構(gòu)建分布式的大容量交換網(wǎng)絡(luò)是分組交換技術(shù)的發(fā)展趨勢(shì)。比較相同拓?fù)漕愋?、不同維度的多維交換結(jié)構(gòu),一般情況下,高維的結(jié)構(gòu)在吞吐率、交換延遲等性能指標(biāo)上具有天生的優(yōu)勢(shì)。如果交換節(jié)點(diǎn)總數(shù)(即交換結(jié)構(gòu)規(guī)模)固定不變,維度高意

2、味著每維節(jié)點(diǎn)數(shù)少,節(jié)點(diǎn)連接度高,從而交換結(jié)構(gòu)的直徑更小,對(duì)分帶寬更大。直徑小有利于減小交換延遲,而對(duì)分帶寬大有利于提高吞吐率,因?yàn)槎嗑S交換結(jié)構(gòu)理論上能達(dá)到的交換能力與其對(duì)分帶寬成正比。 但是高維度也會(huì)帶來(lái)成本上與技術(shù)上的問(wèn)題。維度高意味著每個(gè)節(jié)點(diǎn)的連接度高,從而需要更多的互連通道及節(jié)點(diǎn)緩存。這直接增加了交換結(jié)構(gòu)的實(shí)現(xiàn)成本,同時(shí)加大了交換節(jié)點(diǎn)上的緩存管理、調(diào)度、控制信息傳輸與處理等模塊的難度,不利于節(jié)點(diǎn)實(shí)現(xiàn)。而且由于互連通道數(shù)隨著

3、節(jié)點(diǎn)數(shù)的增加而快速增大,使得其可擴(kuò)展性受到限制。因?yàn)槭芟抻趶?fù)雜互連的可實(shí)現(xiàn)性限制等,所以今后的研究方向之一是采用光介質(zhì)來(lái)連接多維交換結(jié)構(gòu)。 另一方面,面對(duì)視頻會(huì)議、計(jì)算機(jī)協(xié)同工作等新業(yè)務(wù)的快速增長(zhǎng),多播通信的應(yīng)用越來(lái)越廣泛,相對(duì)傳統(tǒng)的點(diǎn)到點(diǎn)通信方式,多播不僅能夠節(jié)約大量的網(wǎng)絡(luò)帶寬,而且可以提高工作效率。隨著對(duì)多播性能要求的不斷增加,多播應(yīng)用逐漸從應(yīng)用層向網(wǎng)絡(luò)結(jié)構(gòu)的下層延伸,在交換和路由層上實(shí)現(xiàn)多播已經(jīng)成為當(dāng)前國(guó)內(nèi)外研究的熱點(diǎn)。

4、 k元n方中的多播既可以通過(guò)軟件,也可以依靠硬件的支持得以實(shí)現(xiàn)。但硬件開(kāi)銷會(huì)增加系統(tǒng)的設(shè)計(jì)成本和實(shí)現(xiàn)的復(fù)雜度,并會(huì)降低路由硬件的速度。同時(shí),現(xiàn)有的k元n方實(shí)現(xiàn)系統(tǒng)大多只支持點(diǎn)對(duì)點(diǎn)的單播路由。因此,利用現(xiàn)有的單播技術(shù)在軟件層面上實(shí)現(xiàn)多播是目前和今后很長(zhǎng)一段時(shí)間內(nèi)的很好的選擇。 針對(duì)以上問(wèn)題,對(duì)現(xiàn)有的軟件多播算法做出了改進(jìn)；設(shè)計(jì)了以單播路由為基礎(chǔ)的多播路由算法:KMPAMR(K-Mesh Pattition-based Ada

5、ptive Multicast Routing)算法；搭建了k元n方交換結(jié)構(gòu)的通用仿真模型,采用面向策略的設(shè)計(jì)模式為不同的路由算法提供了通用的訪問(wèn)接口,并對(duì)算法性能進(jìn)行了分析和討論。實(shí)驗(yàn)表明,本文提出的兩種算法能夠取得較好的性能。首先,本文從k元n方交換結(jié)構(gòu)、死鎖問(wèn)題、蟲(chóng)孔交換、路由算法和虛通道流控制幾個(gè)角度出發(fā),介紹了本文研究的背景知識(shí)。接著描述了構(gòu)建多維交換結(jié)構(gòu)需要注意的問(wèn)題和介紹了多播的前景。 其次,介紹了多維交換結(jié)構(gòu)的研

6、究背景,并對(duì)不同維數(shù)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了仿真。分析了由維數(shù)引起的torus交換結(jié)構(gòu)性能和復(fù)雜度上的變化。 再次,本文在分析已有的軟件多播算法的基礎(chǔ)上,提出一種針對(duì)并發(fā)多播業(yè)務(wù)設(shè)計(jì)的多播路由算法:KMPAMR,算法。KMPAMR算法具有更為靈活的分區(qū)方式,通過(guò)增大多播的并行性和路由的靈活性來(lái)改善多播性能。仿真表明,KMPAMR算法在負(fù)載較低的情況下能取得較高的吞吐率和較低的延遲,但會(huì)加速交換結(jié)構(gòu)“過(guò)飽和”現(xiàn)象的出現(xiàn)。一旦出現(xiàn)“過(guò)飽和”