季保啟

菏澤家政職業(yè)學(xué)院，山東菏澤 274300

1 傳統(tǒng)的路由選擇算法

傳統(tǒng)的路由選擇算法通?？煞譃閮深悾红o態(tài)路由選擇算法與動態(tài)路由選擇算法。

1.1 靜態(tài)路由選擇算法

靜態(tài)路由選擇算法是指對網(wǎng)絡(luò)信息既不進(jìn)行利用也不進(jìn)行測量，按某種固定規(guī)律進(jìn)行計(jì)算的路由選擇的算法。

1.1.1 隨機(jī)路徑選擇算法

隨機(jī)路徑選擇算法是指在數(shù)據(jù)傳輸過程中，當(dāng)數(shù)據(jù)包到達(dá)某一節(jié)點(diǎn)后，則在該節(jié)點(diǎn)上，通過完全隨機(jī)法和輪選法兩種隨機(jī)方法，選擇出一條輸出路徑進(jìn)行轉(zhuǎn)發(fā)。隨機(jī)路徑選擇算法實(shí)現(xiàn)過程簡單，但由于計(jì)算過程中有可能將其收到的數(shù)據(jù)包通過原來的路徑折回，從而使數(shù)據(jù)包在網(wǎng)絡(luò)中無限循環(huán)傳達(dá)，而最終無法到達(dá)目的節(jié)點(diǎn)，因此具有一定的局限性。

1.1.2 擴(kuò)散路徑算法

擴(kuò)散路徑算法是指當(dāng)某一個網(wǎng)絡(luò)節(jié)點(diǎn)從某條線路收到一個分組后，再向其除了該條線路以外的所有線路發(fā)送收到的分組，最先到達(dá)的目的節(jié)點(diǎn)的一個或者若干組，耗時最短，必定為最短路徑，在此過程中所有可能的分組都被嘗試過。但此種方法會產(chǎn)生很多的相同分組，甚至可能產(chǎn)生無限多個分組。

1.1.3 最短路徑選擇法

最短路徑選擇算法是指用一個無向圖來表示網(wǎng)絡(luò)，認(rèn)定無向圖的每條邊即為一條鏈路，在鏈路上用測度的數(shù)據(jù)進(jìn)行標(biāo)識，例如節(jié)點(diǎn)之間的距離，帶寬，平均吞吐量等。然后通過計(jì)算，得出從本節(jié)點(diǎn)到其他節(jié)點(diǎn)的最優(yōu)路徑，同時將計(jì)算結(jié)果進(jìn)行記錄。當(dāng)某一節(jié)點(diǎn)收到一個數(shù)據(jù)包需要轉(zhuǎn)發(fā)時，可在數(shù)據(jù)包的計(jì)算結(jié)果中進(jìn)行目的地址查找，找出最優(yōu)鏈路進(jìn)行轉(zhuǎn)發(fā)[2]。

1.2 動態(tài)路由選擇算法

動態(tài)路由選擇算法根據(jù)網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息來進(jìn)行節(jié)點(diǎn)網(wǎng)絡(luò)策略的選擇，又稱自適應(yīng)路由選擇算法。

1.2.1 距離矢量算法

距離矢量算法中每個路由器都對應(yīng)一張路由表，它以每個路由器為索引，在表中已詳細(xì)列出了已知的路由器到每個目標(biāo)路由器的最短距離及其所使用的線路，在執(zhí)行過程中，相鄰節(jié)點(diǎn)通過交換信息來更新表中的內(nèi)容。距離矢量算法一般將距離用所通過的節(jié)點(diǎn)數(shù)或鏈路數(shù)表示，在一定周期時間內(nèi)，每個節(jié)點(diǎn)將自己的距離矢量發(fā)送給相鄰節(jié)點(diǎn)。若某個節(jié)點(diǎn)在給定的時間范圍內(nèi)，沒有接到鄰接點(diǎn)的距離矢量表，則可認(rèn)定該鄰接點(diǎn)的距離為∞，表示不可達(dá)到。在收到鄰接點(diǎn)對應(yīng)的距離矢量表后，節(jié)點(diǎn)根據(jù)優(yōu)化原則，同步更新自己的距離矢量表。

1.2.2 鏈路選擇算法

鏈路選擇算法通過發(fā)現(xiàn)鄰居節(jié)點(diǎn)、測量鄰接點(diǎn)延遲、創(chuàng)建鏈路狀態(tài)分組、發(fā)布鏈路狀態(tài)分組、計(jì)算新的路由這五步進(jìn)行實(shí)現(xiàn)。鏈路選擇算法應(yīng)用廣泛，可應(yīng)用于大型網(wǎng)絡(luò)。

2 路由選擇算法的改進(jìn)

2.1 改進(jìn)的路由選擇算法的基本思想

由于源節(jié)點(diǎn)和目的節(jié)點(diǎn)并不相同，可能出現(xiàn)多個數(shù)據(jù)包流量所選擇的最佳路徑為同一鏈路的現(xiàn)象，這就使得某一鏈路被過分使用，而其他鏈路被閑置。流量淘汰算法即是當(dāng)出現(xiàn)情況時，按照流量淘汰算法進(jìn)行淘汰，將不適宜的流量進(jìn)行轉(zhuǎn)移，使其選擇到其他閑置鏈路上，從而降低同一鏈路的使用率，最大程度的避免網(wǎng)絡(luò)擁塞[3]。

2.2 改進(jìn)的路由選擇算法的模型

已知每段鏈路帶寬為H，每段鏈路最大數(shù)據(jù)流量為qi， 若流量G選擇了該段鏈路則會得到效益fiai，其中表示該流量被選擇；ai=0表示該流量被淘汰。算法建立的數(shù)學(xué)描述如下：

2.3 算法的實(shí)現(xiàn)

此算法由于設(shè)置了過濾條件，可以使得可行解通過過濾條件直接過濾，而不用進(jìn)行其他約束條件的判斷，這種計(jì)算過程減少了運(yùn)算次數(shù)，同時，每次得到的過濾條件的判斷值是可以動態(tài)改變的，從而減少了計(jì)算量。

3 結(jié)論

與傳統(tǒng)的路由選擇算法相比，改進(jìn)后得到的應(yīng)用于流量控制的路由選擇算法經(jīng)，可較好的解決流量在選擇數(shù)據(jù)傳輸時選擇同一鏈路而產(chǎn)生的網(wǎng)絡(luò)擁塞問題，鏈路的使用率得到均衡，大大提高了網(wǎng)絡(luò)的吞吐量，對于緩解流量在數(shù)據(jù)傳輸過程中的數(shù)據(jù)包丟失情況有顯著效果。改進(jìn)的路由選擇算法對于提高網(wǎng)絡(luò)的數(shù)據(jù)傳輸速率，減少網(wǎng)絡(luò)費(fèi)用具有重要的意義。

[1]方敏，孫勁光，楊勇.基于流量控制的路由選擇算法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2002，21（6）：767-769.

[2]陶滔，馬淑萍，羅江琴.網(wǎng)絡(luò)路由信息安全應(yīng)用研究-基于流量預(yù)測的路由選擇新算法[J].中國安全科學(xué)學(xué)報(bào)，2003，13（5）：62-64.

[3]錢程.路由選擇算法分析[J].信息科技，2010，21（5）：87-89.