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

楊俊葉 王訓偉

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

引言

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

一、排隊論理論簡介

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

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

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

（一）VoIP網絡

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

圖1 VoIP電話系統(tǒng)基本組成

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

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

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

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

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

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

圖2 VoIP網絡通信一般模式

（二） VoIP網絡模型

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

圖3 VoIP通信系統(tǒng)抽象模型

（三）抽象模型分析

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

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

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

由圖2可知：

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

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

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

三、低延時排隊算法分析

（一） VoIP的隊列調度

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

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

圖 4 路由器中的隊列管理

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

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

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

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

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

（二）LLQ算法分析

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

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

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

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

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

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

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

四、總結

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