應用于網絡流量控制的路由選擇算法分析

季保啟

菏澤家政職業學院，山東菏澤 274300

1 傳統的路由選擇算法

傳統的路由選擇算法通常可分為兩類：靜態路由選擇算法與動態路由選擇算法。

1.1 靜態路由選擇算法

靜態路由選擇算法是指對網絡信息既不進行利用也不進行測量，按某種固定規律進行計算的路由選擇的算法。

1.1.1 隨機路徑選擇算法

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

1.1.2 擴散路徑算法

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

1.1.3 最短路徑選擇法

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

1.2 動態路由選擇算法

動態路由選擇算法根據網絡當前的狀態信息來進行節點網絡策略的選擇，又稱自適應路由選擇算法。

1.2.1 距離矢量算法

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

1.2.2 鏈路選擇算法

鏈路選擇算法通過發現鄰居節點、測量鄰接點延遲、創建鏈路狀態分組、發布鏈路狀態分組、計算新的路由這五步進行實現。鏈路選擇算法應用廣泛，可應用于大型網絡。

2 路由選擇算法的改進

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

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

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

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

2.3 算法的實現

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

3 結論

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

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

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

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