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

2、味著每維節(jié)點數少,節(jié)點連接度高,從而交換結構的直徑更小,對分帶寬更大。直徑小有利于減小交換延遲,而對分帶寬大有利于提高吞吐率,因為多維交換結構理論上能達到的交換能力與其對分帶寬成正比。 但是高維度也會帶來成本上與技術上的問題。維度高意味著每個節(jié)點的連接度高,從而需要更多的互連通道及節(jié)點緩存。這直接增加了交換結構的實現成本,同時加大了交換節(jié)點上的緩存管理、調度、控制信息傳輸與處理等模塊的難度,不利于節(jié)點實現。而且由于互連通道數隨著

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

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

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

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