互連網(wǎng)絡(luò)中的路由算法研究.pdf

1、互連網(wǎng)絡(luò)是一種流行的網(wǎng)絡(luò)拓撲，現(xiàn)已廣泛應(yīng)用于電話網(wǎng)絡(luò)、多處理器系統(tǒng)、分布式計算機系統(tǒng)及路由器交換機等領(lǐng)域。作為互連網(wǎng)絡(luò)結(jié)構(gòu)之一的直連網(wǎng)絡(luò)，以其簡單的結(jié)構(gòu)、良好的擴展性及便于實現(xiàn)分布式管理等，正被引入到新一代的大容量核心路由器中。 直連網(wǎng)絡(luò)中不均勻業(yè)務(wù)的存在要求現(xiàn)有路由算法具有負載均衡能力。然而直連網(wǎng)絡(luò)中傳統(tǒng)的路由算法未能很好地均衡網(wǎng)絡(luò)流量，如確定性的維序算法對于一對源宿結(jié)點只提供一條固定的路徑，使得分組無法繞過網(wǎng)絡(luò)中的擁塞區(qū)域；

2、最短路徑算法的Duato算法無法充分利用網(wǎng)絡(luò)中的非最短路徑資源；非最短路徑算法的GAI算法是針對惡性流量模式設(shè)計的，善意模式下性能不佳。 本文主要對直連網(wǎng)絡(luò)的負載均衡路由算法進行了研究，主要的工作和貢獻包括如下兩個方面： 1.根據(jù)自然界中的氣體擴散現(xiàn)象，提出了一種新的負載均衡路由算法-GD(Gas diffusion based routing algorithm)。該算法是最短路徑完全適應(yīng)性算法，使用基于軟件的死鎖恢復(fù)

3、機制來檢測和解除死鎖；它根據(jù)端口的超時分組數(shù)來確定端口的擁塞程度，然后以此為參考來隨機路由分組，將分組從擁塞程度重的端口分流到擁塞程度輕的端口來均衡網(wǎng)絡(luò)負載。我們使用OPNET軟件在基于虛切通交換機制下的k-ary n-cube網(wǎng)絡(luò)中對其進行仿真，發(fā)現(xiàn)在相同的網(wǎng)絡(luò)仿真環(huán)境下， GD算法的性能要優(yōu)于傳統(tǒng)路由算法(如維序算法、Duato算法、GAL算法等)。 2.研究了生物智能在路由算法中的應(yīng)用，并提出了一種適用于直連網(wǎng)絡(luò)的智能路由

4、算法-FOA(Forward-only Agent muting algorithm)。該算法仍是最短路徑完全適應(yīng)性算法，采用基于軟件的死鎖恢復(fù)機制來檢測和解除死鎖：它使用前向代理來收集網(wǎng)絡(luò)中的有限全局信息即當(dāng)前結(jié)點到其源結(jié)點的旅行時間，并以此來更新結(jié)點的旅行時間表；算法根據(jù)結(jié)點旅行時間表所記錄的歷史信息和當(dāng)前的鏈路狀態(tài)來共同確定一個鄰結(jié)點的路由質(zhì)量，并以此為參考隨機路由分組來均衡網(wǎng)絡(luò)負載。我們將FOA算法與傳統(tǒng)算法(如維序算法、Dua