楊俊葉 王訓(xùn)偉

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

引言

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

一、排隊(duì)論理論簡介

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

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

二、VoIP網(wǎng)絡(luò)模型的建立與分析

（一）VoIP網(wǎng)絡(luò)

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

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

IP電話系統(tǒng)有4個(gè)基本組件：終端設(shè)備，網(wǎng)關(guān)、多點(diǎn)控制單元和網(wǎng)守。

1.終端設(shè)備是一個(gè)IP客戶終端，可以直接連接在IP網(wǎng)上進(jìn)行實(shí)時(shí)的語音或多媒體通信。

2.網(wǎng)關(guān)是通過IP網(wǎng)絡(luò)提供語音通信的關(guān)鍵設(shè)備，完成實(shí)時(shí)語音壓縮，完成尋址和呼叫控制。

3.網(wǎng)守負(fù)責(zé)用戶注冊和管理。

4.MCU(多點(diǎn)控制單元)的功能在于利用IP網(wǎng)絡(luò)實(shí)現(xiàn)多點(diǎn)通信，使得IP電話能夠支持諸如網(wǎng)絡(luò)會議的多點(diǎn)通信[4]。

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

圖2 VoIP網(wǎng)絡(luò)通信一般模式

（二） VoIP網(wǎng)絡(luò)模型

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

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

（三）抽象模型分析

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

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

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

由圖2可知：

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

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

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

三、低延時(shí)排隊(duì)算法分析

（一） VoIP的隊(duì)列調(diào)度

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

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

圖 4 路由器中的隊(duì)列管理

VoIP網(wǎng)絡(luò)中所要調(diào)度的分組數(shù)據(jù)包大體上可以分為兩類：一是具有優(yōu)先級，二是不具有優(yōu)先級[7]。

VoIP網(wǎng)絡(luò)中路由器中的隊(duì)列調(diào)度分為以下幾種方式：

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

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

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

（二）LLQ算法分析

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

根據(jù)VoIP通信系統(tǒng)模型和路由器中的隊(duì)列調(diào)度，我們可以知道VoIP網(wǎng)絡(luò)中低延時(shí)排隊(duì)的通信隊(duì)列是一個(gè)M/M/1排隊(duì)模型，所以低延時(shí)排隊(duì)的通信隊(duì)列模型也應(yīng)該滿足第2節(jié)中列出的幾個(gè)式子。

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

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

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

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

對于VoIP通信網(wǎng)絡(luò)來說，對延時(shí)的要求比較高，低延時(shí)排隊(duì)算法在實(shí)時(shí)業(yè)務(wù)上能比較理想地實(shí)現(xiàn)低延時(shí)處理效果，所以在VoIP通信隊(duì)列選擇低延時(shí)排隊(duì)算法。但低延時(shí)排隊(duì)算法并不能夠完全代替FIFO，PQ 或者CQ，我們應(yīng)該根據(jù)網(wǎng)絡(luò)中不同的QoS要求，進(jìn)行合理的選擇，因?yàn)槿魏我环N排隊(duì)算法都不是盡善盡美的。

四、總結(jié)

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