基于排隊論的最優流路由算法探討

劉 珂,湯 震

（黃淮學院，河南駐馬店,463000）

0.引言

隨著網絡應用的普及，網絡用戶的增加使得網絡流量急劇上升，網絡流量負擔過大，如果信息量過大不加以限制，超額的網絡流量就會導致設備反映緩慢，造成網絡延遲。使得通信緩慢，給網絡傳輸帶來很大的不便。如何解決網絡流量負擔過大、緩解網絡延遲、解決網絡擁塞等問題，是目前互聯網研究的熱門。本文所要介紹的最優流路由算法，可以調整網絡的最優的數據流，實現疏通網絡擁塞的目的。

1 排隊論理論

排隊論（隨機服務系統理論）是一門研究擁擠現象的理論。排隊論理論是根據排隊系統概率的規律性，提出網絡服務的最優設計和控制的方案。排隊系統由輸入過程、服務規則和服務臺等3個組成部分構成。排隊系統運行狀況的主要數量指標有隊長和排隊長、等待時間和逗留時間、忙期和閑期等。如圖1所示。

圖1 隨機服務系統

2 最優流路由算法的建模

排隊系統以M/M/1無限源系統建模。即對排隊系統的容量和數據流數目不限制，將進入系統待處理的數據流作為一個集合，記為 R={R1 ,R2 ,…,Rλ}，規定每個數據流分別以概率pi(其中i=1,2，…)分配到路徑Ti 上。所有pi之和為1.。用單服務臺系統，統計計算并比較路徑長度，然后確定分配方案。服務速率可以用傳播時延來表示。即，路徑Ti 的服務速率為ui。最優流路由算法的建模如圖2所示。

圖2 最優流路由算法模型

最優流路由算法模型過程是外來的數據流(速率為λ)進入排隊系統，，數據流排隊系統根據服務時間的不同，以pi的概率分別將數據流分配到路徑Ti上，數據流以速率為piλ的速度從排隊系統進入到已分配的路徑。

根據最優流路由算法模型，排隊系統處理數據流的平均處理時延為 。如果可以分配的路徑有n條可以選擇，則n條路徑的平均處理時延是：

（2）各路徑被分配到的概率都是不相容的，即pi之和為應該為1

3 算法設計

最優流路由算法是在滿足條件的可行域上找到最優的一個分配方案。是一個多次求最優分配路徑的集合T。求最優解的過程：首先是對與路徑長度有關的參數μ進行排序，找到最小值；然后取兩個中間變量，計算待分配的可到達路徑長度最小的路徑的概率 ；循環刪除淘汰那些路徑長度最小但是非法的路徑，將剩下的可選路徑依次計算其概率 。最后就得到可選最優路徑組成的一個集合。

基于排隊論的最優流路由算法如下：

4 實驗與分析

4.1 實驗

本算法使用模擬15個節點的網絡拓撲圖，設置節點之間的路徑，如圖3所示。

圖3 15個節點網絡拓撲圖

在本次實驗中，假設各個鏈路的帶寬是相同的，數據流的大小是固定的，設定為最大的帶寬值4500。數據流以靜態方式進入的，暫不考慮數據包丟失的情況。圖中路徑長度為2的用實線表示；路徑長度為1的用虛線表示。數據流流入源點和終點是隨機的，本實驗隨機選擇的數據流進入節點1，輸出節點是13，得到1-＞3-＞7-＞10-＞13的最優路徑。當網絡拓撲中的數據流達到飽和狀態，實驗立即結束。

4.2 分析

本算法優點是能夠同時處理網絡中各個位置的問題。對網絡中多個節點發生網絡故障或擁塞事件時，可以實現再次重新分配數據流的流向，高效的解決網絡擁塞情況。符合網絡運營管理的及時性原則，網絡故障處理的效率得到了提高，算法具有一定的可行性及安全性。

根據圖4中的網絡拓撲進行測試，在1到100中，隨機的選擇分配各個路徑長度。來驗證算法同時解決多個位置的問題的功能。

圖4 網絡拓撲圖

實驗假設圖中數據流起點為A，到達終點為B。數據流經過拓撲中的各個節點時可能會造成擁塞等，經過對路徑1—5的測試結果表明，本算法可以很好的同時解決多個擁塞問題。

測量時數據流個數設為200。每次測量的結果表示當前路徑已分配的數據流的個數，每一行是一次最優的分配結果。當某一路徑發生故障時，分配數據流0。實驗結果如表1所示。

表1 測量結果

分析表1中的測試結果，第1次測量是在初始時的數據流狀態，路徑3中沒有分配數據流，當前沒有產生擁塞；第2次測量，算法為路徑3被分配了數據流，完成路徑選擇的優化；第3次測量，因為節點3出現了擁塞故障，所以路徑4、5沒有被分配數據流；第4次測量，節點1和節點2出現故障了，路徑1、2、3也沒有被分配數據流；第5次測量，算法解決了節點1和節點2的擁塞問題，并重新得到一個最優的路徑分配方案。實驗表明本算法可以同時處理網絡中的擁塞和故障。

根據排隊論設計的最優流路由算法，可以有效地同時解決網絡中多個節點的擁塞或故障。提高了網絡故障處理的效率，減小網絡資源的消耗，使得網絡流量更加均衡，服務質量更加高效。

[1]胡勇,李訓銘,高莉莎.基于 NS2 的改進隊列管理算法及其實現[J]電力自動化設備,2008,(01):641-665

[2]鄭福,高超,朱廣田.M/G/1 排隊論系統的漸近穩定性[J].應用泛函分析學報,2011,(02):56-65