應用于網(wǎng)絡流量控制的路由選擇算法分析

季保啟

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

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

傳統(tǒng)的路由選擇算法通常可分為兩類：靜態(tài)路由選擇算法與動態(tài)路由選擇算法。

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

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

1.1.1 隨機路徑選擇算法

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

1.1.2 擴散路徑算法

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

1.1.3 最短路徑選擇法

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

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

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

1.2.1 距離矢量算法

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

1.2.2 鏈路選擇算法

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

2 路由選擇算法的改進

2.1 改進的路由選擇算法的基本思想

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

2.2 改進的路由選擇算法的模型

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

2.3 算法的實現(xiàn)

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

3 結論

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

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

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

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