基于排隊論的最優(yōu)流路由算法探討

劉 珂,湯 震

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

0.引言

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

1 排隊論理論

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

圖1 隨機服務系統(tǒng)

2 最優(yōu)流路由算法的建模

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

圖2 最優(yōu)流路由算法模型

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

根據(jù)最優(yōu)流路由算法模型，排隊系統(tǒng)處理數(shù)據(jù)流的平均處理時延為 。如果可以分配的路徑有n條可以選擇，則n條路徑的平均處理時延是：

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

3 算法設計

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

基于排隊論的最優(yōu)流路由算法如下：

4 實驗與分析

4.1 實驗

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

圖3 15個節(jié)點網(wǎng)絡拓撲圖

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

4.2 分析

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

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

圖4 網(wǎng)絡拓撲圖

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

測量時數(shù)據(jù)流個數(shù)設為200。每次測量的結(jié)果表示當前路徑已分配的數(shù)據(jù)流的個數(shù)，每一行是一次最優(yōu)的分配結(jié)果。當某一路徑發(fā)生故障時，分配數(shù)據(jù)流0。實驗結(jié)果如表1所示。

表1 測量結(jié)果

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

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

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

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