基于排隊論的路由選擇策略研究

朱小流，廖曉談

（南京熊貓漢達(dá)科技有限公司，江蘇 南京 210000）

0 引言

隨著通信行業(yè)的蓬勃發(fā)展，新的技術(shù)層出不窮。低時延、高效率是通信質(zhì)量的一個重要指標(biāo)，而通信過程中信息的傳輸離不開路由的選擇，如何優(yōu)化路由器的選路模型，減少信息傳輸?shù)臅r間，降低時延是一個十分重要的課題。本文針對某區(qū)域設(shè)置局域網(wǎng)的實際問題，分別設(shè)計了不同的路由器方案，通過將信息在各個路由器節(jié)點處的逗留時間進(jìn)行求和，得到了總的信息傳輸時間。將平均的信息傳輸時間進(jìn)行比較，得到了時延最低的路由器選擇方案。最后，通過蒙特卡洛仿真驗證了理論分析的正確性。

1 系統(tǒng)模型

在實際通信過程中，同一個網(wǎng)段的終端設(shè)備都會連接同一個路由器，該路由器為網(wǎng)關(guān)路由器。不同網(wǎng)段的終端設(shè)備在通信的過程中，發(fā)端發(fā)出的信息需要經(jīng)過自身網(wǎng)段的網(wǎng)關(guān)路由器后，再經(jīng)過路由選擇到達(dá)收端的網(wǎng)關(guān)路由器，最終再傳給收端。本文通過建立三種傳輸模型，分析比較三種網(wǎng)絡(luò)模型下信息的平均傳輸時間，尋找信息傳輸時間最短的方案，使得系統(tǒng)的延遲降低，為系統(tǒng)的路由選擇提供參考。

1.1 方案1 系統(tǒng)模型

如圖1所示，信息在經(jīng)過網(wǎng)關(guān)路由器后，以概率P中間路由1、P中間路由2傳到兩個路由器，在這里，我們假設(shè)信息等概傳輸?shù)絻蓚€中間路由器。信息傳輸速率為λ，則到達(dá)后面的兩個路由器時，信息速率減半為λ/2，最終到達(dá)收端網(wǎng)關(guān)路由器速率為λ。發(fā)端網(wǎng)關(guān)、中間路由和收端網(wǎng)關(guān)的服務(wù)速率為μ1、μ2、μ3。假設(shè)三種路由器的服務(wù)員數(shù)量為c1、c2、c3。

圖1 方案1傳輸網(wǎng)絡(luò)

1.2 方案2 系統(tǒng)模型

如圖2所示，信息在經(jīng)過網(wǎng)關(guān)路由器后，經(jīng)過一個中間路由，中間路由器的服務(wù)員數(shù)為方案 1兩個中間路由器服務(wù)員數(shù)之和。最終信息在匯總到收端的網(wǎng)關(guān)路由器。發(fā)端網(wǎng)關(guān)、中間路由和收端網(wǎng)關(guān)的服務(wù)速率為μ1、μ2、μ3。服務(wù)員數(shù)量分別為c1、c2=c21+c22、c3。

圖2 方案2傳輸網(wǎng)絡(luò)

1.3 方案3 系統(tǒng)模型

如圖3所示，信息在經(jīng)過網(wǎng)關(guān)路由器后，不經(jīng)過中間路由的傳遞，直接將信息發(fā)送給接收端的網(wǎng)關(guān)路由器。此方案也加大了發(fā)端路由器的負(fù)荷，使得信息處理速率降低，假設(shè)速率為μ1、μ3。服務(wù)員數(shù)量分別為c=c1+c2、c3。

圖3 方案3傳輸網(wǎng)絡(luò)

2 平均信息傳輸時間

在得到M/M/c 排隊模型的平均逗留時間的基礎(chǔ)上，計算各個方案的信息傳輸時間，即信息在每個節(jié)點的平均逗留時間之和。

2.1 方案1 傳輸時間

方案1可看作三個獨立的M/M/c 排隊模型，具體的參數(shù)設(shè)置在系統(tǒng)模型中已經(jīng)給出，在此不再贅述。因此，信息傳輸時間為：

2.2 方案2 傳輸時間

方案 2在方案 1的基礎(chǔ)上將中間路由合并，減少路由器數(shù)量，增多單個路由器中服務(wù)員數(shù)量，得到信息傳輸時間為：

2.3 方案3 傳輸時間

在方案2的基礎(chǔ)上，進(jìn)一步減少路由器數(shù)量，由發(fā)端的網(wǎng)關(guān)路由器同時實現(xiàn)收集信息和選路的作用，信息傳輸速率為：

3 仿真結(jié)果與分析

本節(jié)通過matlab 對通信過程進(jìn)行仿真，分析比較不同方案下的傳輸性能。為了避免系統(tǒng)崩潰，輸入速率和服務(wù)速率需要滿足如無特殊說明，系統(tǒng)參數(shù)設(shè)置如下：λ=120、μ1=60、μ2=80、μ3=80，服務(wù)員數(shù)量分別為：c1=5、c21=1、c22=1、c3=2，時間單位為s。

圖4 信息傳輸時間隨輸入速率變化圖

如圖4所示，仿真點與理論曲線基本重合，驗證了理論分析的正確性。隨著信息速率的提高，系統(tǒng)節(jié)點的阻塞概率C（c，a）提高，使得信息在單個節(jié)點的逗留時間增大，增大了信息的平均傳輸時間，這與實際情況相符，在信息量較大的情況下，網(wǎng)絡(luò)的延遲會提高。同時，從圖4可以發(fā)現(xiàn)，在本文設(shè)定的系統(tǒng)參數(shù)下，方案3的信息傳輸時間最短，方案1的傳輸時間最長，說明方案3的路由選擇方案最好。

如圖5所示，仿真點與理論曲線基本重合，驗證了理論分析的正確性。由于方案3的性能最優(yōu)，在此我們單獨對方案3進(jìn)行研究。在方案3中，由于發(fā)端的網(wǎng)關(guān)路由同時實現(xiàn)接收集信息和選路功能，使得路由器的負(fù)荷增大，使得方案3中的發(fā)端網(wǎng)關(guān)路由器的信息處理速率低于系統(tǒng)預(yù)設(shè)。通過仿真分析可以發(fā)現(xiàn)，當(dāng)方案3中發(fā)端網(wǎng)關(guān)路由器信息服務(wù)速率低于25時，傳輸時間長于方案2，當(dāng)信息服務(wù)速率低于21時，傳輸時間長于方案1。說明當(dāng)路由器負(fù)荷過大，使得方案3的發(fā)端網(wǎng)關(guān)路由器信息服務(wù)速率降低時，方案 3可能并不是最佳選擇。

圖5 信息傳輸時間隨服務(wù)速率變化圖

4 結(jié)束語

本文基于排隊論理論知識，建立了三種信息傳輸過程中的路由選擇模型，研究得到了信息傳輸時間隨信息輸入速率的變化圖和最優(yōu)方案下信息傳輸時間隨路由器服務(wù)速率的變化圖。研究表明，當(dāng)網(wǎng)關(guān)路由器結(jié)合中間路由器后，如能保持較高的服務(wù)速率，信息的傳輸時間最低，系統(tǒng)的延遲最小。

但應(yīng)注意在實際中，通常情況下不會采用只有兩個網(wǎng)關(guān)路由的通信方式。這是因為采用此方案時，若一個終端想要和其他終端通信，需要單獨建立一條鏈路，然而物聯(lián)網(wǎng)時代的終端數(shù)目龐大，不論是在經(jīng)濟(jì)性還是可行性的考慮下都不是一個好的選擇。然而，在小型局域網(wǎng)中，當(dāng)終端的數(shù)目較少，不同網(wǎng)段的終端較少時，可以每個網(wǎng)關(guān)路由器直接建立通路，此方案以其高效性可以展現(xiàn)出巨大的優(yōu)勢。