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

朱小流，廖曉談

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

0 引言

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

1 系統模型

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

1.1 方案1 系統模型

如圖1所示，信息在經過網關路由器后，以概率P中間路由1、P中間路由2傳到兩個路由器，在這里，我們假設信息等概傳輸到兩個中間路由器。信息傳輸速率為λ，則到達后面的兩個路由器時，信息速率減半為λ/2，最終到達收端網關路由器速率為λ。發端網關、中間路由和收端網關的服務速率為μ1、μ2、μ3。假設三種路由器的服務員數量為c1、c2、c3。

圖1 方案1傳輸網絡

1.2 方案2 系統模型

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

圖2 方案2傳輸網絡

1.3 方案3 系統模型

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

圖3 方案3傳輸網絡

2 平均信息傳輸時間

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

2.1 方案1 傳輸時間

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

2.2 方案2 傳輸時間

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

2.3 方案3 傳輸時間

在方案2的基礎上，進一步減少路由器數量，由發端的網關路由器同時實現收集信息和選路的作用，信息傳輸速率為：

3 仿真結果與分析

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

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

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

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

圖5 信息傳輸時間隨服務速率變化圖

4 結束語

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

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