基于排隊論的VoIP低延時排隊算法分析

楊俊葉 王訓偉

（1.石家莊理工職業學院 互聯網應用學院，河北 石家莊 050091;2.石家莊智庫科技有限公司，河北 石家莊 050091）

引言

排隊論是研究計算機網絡通信的重要工具，它能有效地對通信系統進行描述和建模，特別是針對其中的通信隊列。在VoIP網絡中，目前主流排隊算法包括FIFO(First In FIRST Out Queueing algorithm,先入先出排隊算法)、PQ (Priority Queueing algorithm,優先級排隊算法)、CQ(Custom Queueing algorithm,定制排隊算法)、WFQ(Weighted Fair Queueing algorithm,加權公平排隊算法)、CBWFQ(Class-Based WFQ Queueing algorithm,基于類的加權公平排隊算法)、LLQ(Low Latency Queueing algorithm,低延時排隊算法)等[1]。其中，LLQ在CBWFQ基礎上增加了優先級隊列，從而可以提供絕對的優先權，同時還能保證實時業務的低延時要求。VoIP是一種實時性業務，對通信延時的要求比較高。因此可以將LLQ算法應用于VoIP網絡，通過LLQ優化排隊算法，來保證其數據傳輸的服務質量。本文詳細分析了在VoIP中的低延時排隊算法。

一、排隊論理論簡介

排隊論又叫做隨機服務系統理論，主要解決與隨機到來、排隊服務現象有關的應用問題，在計算機網絡等領域有著廣泛的應用。排隊論主要研究三個方面的內容：(1)形態問題, 即研究各種排隊系統的規律性,這包括隊長分布、等待時間分布、忙閑期分布等, 同時又分穩態和瞬態兩種情形。(2)最優化問題, 又分靜態最優和穩態最優; 前者指最優設計, 后者指現在排隊系統的最優運用。(3)排隊系統的統計推斷, 即判斷一個給定的排隊系統符合哪種類型,以便根據排隊理論進行分析研究[2]。

一般的排隊系統都具有三個要素，這就是輸入過程、排隊規則和服務機構。常見的排隊模型包括M/M/S、M/M/S/K、M/G/1等。計算機網絡通信過程與排隊系統具有相互對應的關系，網絡中的信道數相當于排隊論中的窗口數、單位時間內的平均呼叫數相當于顧客的到達率λ、每次呼叫占用線路的平均時間相當于平均服務時間[3]，通信過程也可以利用排隊過程來表示。這樣就可以利用排隊論理論對不同的網絡通信進行建模和分析。

二、VoIP網絡模型的建立與分析

（一）VoIP網絡

VoIP（Voice-over-IP）是一種可以在IP網絡上互傳音訊或視訊的一種通信技術。簡單地說，就是通過語音壓縮算法對語音信號進行壓縮編碼處理，然后把這些語音數據按TCP/IP標準進行打包，經過網絡把數據包發送到接收端；接收端把這些語音數據包串起來，經過解碼，解壓縮處理將其恢復成原來的語音信號，從而達到由Internet傳送語音的目的[4]。IP電話系統的基本組成如圖1所示。

圖1 VoIP電話系統基本組成

IP電話系統有4個基本組件：終端設備，網關、多點控制單元和網守。

1.終端設備是一個IP客戶終端，可以直接連接在IP網上進行實時的語音或多媒體通信。

2.網關是通過IP網絡提供語音通信的關鍵設備，完成實時語音壓縮，完成尋址和呼叫控制。

3.網守負責用戶注冊和管理。

4.MCU(多點控制單元)的功能在于利用IP網絡實現多點通信，使得IP電話能夠支持諸如網絡會議的多點通信[4]。

VoIP網絡通信的發送、接收、處理過程具有如圖2所示的模式。發送方將IP語音數據進行編碼，并按照相關協議打包封裝，由發送單元將數據包送入IP分組網絡通道中。相應地，接收單元將接收到的數據包放在緩沖區中，經過解碼和轉換后進入處理單元進行處理，最后到達接收方。

圖2 VoIP網絡通信一般模式

（二） VoIP網絡模型

在網絡傳輸的過程中，假定沒有數據包丟失，只考慮網絡傳輸延時TN,發送方以一個輸出速率為λo的隊列加以抽象，那么接收方就是一個典型的M/M/1的排隊系統[5]。兩個M分別代表發送方的輸出過程和接收方的處理過程為馬爾可夫過程，服從泊松分布，1代表一條信道。圖2所示的VoIP通信過程可抽象為圖3所示的模型：λO 為發送方的數據包輸出速率，λI 為數據包到達接收模塊的速率，LQ 為緩沖區的數據包個數，γ為接收模塊的數據丟失率,TJ為解碼時間，TD為調度時間,TC為處理時間,TS為數據包在隊列中的服務時間，且TS=TJ+TD+TC 。

圖3 VoIP通信系統抽象模型

（三）抽象模型分析

VoIP通信系統模型中，主要參數的含義為：① LQ，它確定在保證丟失率可接受的數值范圍內，應為系統分配的緩沖區大小；②λI，在確定保持多大的輸入速率下，有確定緩沖區大小的系統能夠在一定的時間范圍內，處理完數據，不產生丟失；③TS，系統處理時間越短越好。設處理模塊（服務臺）的使用率為ρ，圖2中所示的各個變量均為隨機變量，發送方和接收方的輸出隊列和輸入隊列均可假定為泊松分布。用L表示在系統平衡狀態下的隊長，根據概率論和排隊論可以得出如下關系式[6]：

需要指出的是L在此的含義是進入處理模塊和存儲在緩沖區中的所有數據包的平均數量，因此還可以得出如下關系式：

如果把VoIP通信過程處理模塊看做是一個閉合區域，根據Little定律[3]，得到

由圖2可知：

通過整理可以得到以下式子：

由此可以看出，⑷式是一個關于λo 、TS 、LQ的三元方程，只要在服務時間、發送速率和緩沖區大小三者中有兩項

為已知條件的情況下，都可以求得第三者的值。這樣就得出了在VoIP通信網絡中，服務時間、發送速率、接收緩沖區的大小之間的數學關系。

三、低延時排隊算法分析

（一） VoIP的隊列調度

IP電話是對實時性要求很高的數據傳送。延時會影響VoIP通話中的語音質量，因此提供高品質的語音應該從減少延時這方面入手。在VoIP電話系統中，通過相應地QOS策略對IP數據包進行合理的排隊，對其中特定的數據包賦以較高的優先級，從而加速傳輸的進程，并實現實時交互[1]。

排隊機制作為IP網絡QoS 的實現機制之一，無論是在綜合業務體系（IntServ）還是在區分業務體系（DiffServ）里，都有著重要的作用。路由器中排隊算法所要完成的功能就是如何從多個（或一個）隊列中選擇下一個待轉發的分組，其結構如圖4所示。

圖 4 路由器中的隊列管理

VoIP網絡中所要調度的分組數據包大體上可以分為兩類：一是具有優先級，二是不具有優先級[7]。

VoIP網絡中路由器中的隊列調度分為以下幾種方式：

1.當擁有絕對優先級隊列中有IP數據包分組時，調度器會優先發送此隊列，直到此隊列中沒有任務了，才對其他隊列進行調度。若該優先級隊列本來為空，但在調度其他隊列時，不具備絕對優先級的分組卻進入了此優先級隊列，那么就應該在當前調度的分組出隊時立刻轉去調度進入優先隊列里的分組。

2.如果在網絡設備接口沒有發生擁塞，屬于優先隊列的分組獲得空閑的帶寬，此隊列中的分組就都可以被發送。

3.如果在其接口發生擁塞，優先級隊列中的分組就會被限制傳輸速度，超出規定流量的那部分分組也將被丟棄，這樣就保證了屬于優先隊列的分組不會占用超出規定的帶寬，同時也保護了其他分組的應得帶寬。只要優先隊列中有分組，調度器就會發送此優先隊列中的分組。

（二）LLQ算法分析

LLQ是一種集合了PQ、CQ、WFQ算法優點、能有效地應對延時要求頗高的實時性業務的算法。此算法最重要的一點就是增加了一個優先級隊列，在IP數據包傳送的過程中擁有絕對的優先權。

根據VoIP通信系統模型和路由器中的隊列調度，我們可以知道VoIP網絡中低延時排隊的通信隊列是一個M/M/1排隊模型，所以低延時排隊的通信隊列模型也應該滿足第2節中列出的幾個式子。

在⑶式中，λI是一個定值時，TS隨著ρ值的變化而發生相應地變化。當TS取得最大值時，即系統處理數據的時間取最大值，也就是說隊列等待的時間取最大值，相應地服務臺的使用率取最大值(傳輸的數據包平均數取最大值)。在⑵式中，LQ隨著ρ值的變化而發生相應地變化。當ρ取得最大值時，相應地緩沖區的長度取得最大值，即是通信隊列的隊長取得最大值。

當本來為空的優先級隊列中有數據分組進入時，調度器會在當前調度的分組出隊時立刻轉去調度進入優先級隊列里的數據分組，也就是說優先級隊列隊頭分組接受調度的最大延時為一個最大分組的發送時間。那么當數據分組個數是一個定值時，數據分組長度越大，優先級隊列隊頭等待調度的延時會越長。

當⑵式中的LQ 取最大值時，⑶式中的ρ隨之取得相應地最大值，這就使得系統處理數據的時間TS取得最大值，因此就得到了優先級隊列隊頭等待調度的最大延時。

如果在數據平均到達率一定的情況下，減小了數據分組的長度，也就是說上式中LQ的值減小，就會降低優先級隊列隊頭等待調度的延時。

對于VoIP通信網絡來說，對延時的要求比較高，低延時排隊算法在實時業務上能比較理想地實現低延時處理效果，所以在VoIP通信隊列選擇低延時排隊算法。但低延時排隊算法并不能夠完全代替FIFO，PQ 或者CQ，我們應該根據網絡中不同的QoS要求，進行合理的選擇，因為任何一種排隊算法都不是盡善盡美的。

四、總結

將排隊論理論用于分析VoIP網絡系統的通信處理過程，具有很大的優越性。這一方面可以將研究對象(發送、接收和處理過程)抽象化，便于利用精確的數學語言來描述，另一方面也可以拋棄次要因素，一定程度上簡化了研究對象，使得建模和分析成為可能。如今的網絡，需要我們積極探索開發新的、具有實質性飛躍的排隊算法。新算法可以從嚴格的、多層的分類或組合，以及算法復雜度低等方面入手，盡可能讓數據分組里的附加信息減少，從而降低網絡總體負荷。而排隊論則是對這些算法分析的重要手段和方法。相信通過這一系列的改進能夠使網絡上的各種應用，尤其是實時業務的應用得到長足的發展。