楊志軍 蘇楊 丁洪偉

輪詢服務系統(tǒng)代表了一類調度控制的模型,因為其擁有較好的公平性,所以它不僅可以讓有限的資源得到有效的分配,而且可以讓資源得到共享[1?2].按服務方式的不同,輪詢服務系統(tǒng)可以分為門限、完全以及限定三類[3?4].在三種基本的輪詢服務模型的基礎上,可以構成多種混合式區(qū)分優(yōu)先級的輪詢服務.文獻[4]利用延遲周期的概念,給出了各類型客戶等待時間的精確LST(Laplace steltjes transform)表達式和表示方法.此外,證明了優(yōu)先級較小的平均服務時間的客戶可以縮短平均響應時間,尤其是在繁忙的交通當中.文獻[5]提出了一種基于閘門式多級門限服務的兩級優(yōu)先級輪詢系統(tǒng),該輪詢系統(tǒng)滿足了周期性系統(tǒng)服務資源分配過程中業(yè)務多樣性和彈性服務的發(fā)展需求,使得輪詢控制策略應用方面更為廣泛.文獻[6]提出了一種新型的兩級優(yōu)先級輪詢系統(tǒng),既保證了隊列優(yōu)先級的需求,又避免了空閑查詢時造成的時間延遲,達到了提高系統(tǒng)的利用率,減少時延的效果.文獻[7]分析了隊列中在不區(qū)分優(yōu)先級和區(qū)分優(yōu)先級的情況下,對每一個隊列提供門限服務或者是完全服務.并根據于此建立數學模型,然后對此模型的聯(lián)合隊列長度、循環(huán)周期、邊際隊列長度和時延等性能特點進行了解析,驗證了區(qū)分優(yōu)先級所帶來的顯著成效.對輪詢系統(tǒng)區(qū)分優(yōu)先級主要目的,是旨在讓輪詢系統(tǒng)的性能得到顯著的提升.在優(yōu)先級輪詢的應用方面,它可以用于藍牙技術和IEEE 802.11無線局域網協(xié)議的研究或是在Web服務器的路由器和I/O子系統(tǒng)中的調度策略.例如,保證服務質量(Quality of service,QoS)是無線LAN協(xié)議中非常重要的問題,雖然延遲對響應或數據傳輸不會產生重大影響,如網頁瀏覽或電子郵件流量,但是視頻傳輸和無線局域網語音(VoWLAN)對延遲或數據丟失卻是非常的敏感.所以,802.11e則引入了不同的優(yōu)先級來區(qū)分為類型之間的數據提高流媒體業(yè)務的服務質量.優(yōu)先級輪詢模型也可以用來研究流量,比如在交通路口,交通流同時面對綠燈時的情況.由此看出,對輪詢系統(tǒng)進行優(yōu)先級區(qū)分的研究有著重大的意義.

本文也是對區(qū)分優(yōu)先級的兩級輪詢服務進行了研究,所不同的是,本文選擇了一種對稱性輪詢服務與非對稱性輪詢服務相結合的混合式服務模型.為了更好地適應實際應用的需求,非對稱的輪詢服務分析一直是研究的熱點,但實質性突破相對較難.由于在實際應用中,經常會有不同類信息或不同類站點,相應要求在同一種服務策略下,系統(tǒng)設置的參數需要滿足不同類站點自身所需的要求,這就需要非對稱的服務策略.由于輪詢系統(tǒng)中各隊列之間是相互聯(lián)系的,而且系統(tǒng)的概率分布特性非常復雜,所以在對多隊列的非對稱輪詢系統(tǒng)進行解析時,具有一定的困難度.而本文采用的對稱與非對稱相結合的混合服務模式,在對其性能解析過程中有著巨大的挑戰(zhàn)性.同時,多隊列的非對稱輪詢服務的二階特性(平均等待時間)很難給出其精確的數學解析式,所以選擇一種合理的近似方法去解析平均等待時間是研究非對稱性輪詢服務最關鍵的一點.

針對以上的分析過程,本文首先建立兩級優(yōu)先級非對稱性的服務模型,給出一階特性量平均排隊隊長及循環(huán)查詢周期的精確表達式.然后對模型的二階特性量進行分析,并且參照文獻[8]運用查詢周期的二階特性近似相等的方法,對平均等待時間進行解析.最后在軟件Matlab中進行實驗仿真,并與理論計算結果進行對比.本文在構建數學模型當中,則是采用了完全的調度策略服務于中心隊列,而普通隊列則采用了非對稱的門限服務的方式.在服務的過程當中,服務器優(yōu)先對高優(yōu)先級的中心隊列進行發(fā)送服務,直到中心隊列所存在數據信息量為空時,服務器會轉換到第i(i=1,2,···,N)個普通隊列,因為該服務模型由中心隊列轉換到普通隊列時,采用的是并行服務模式,所以當服務器由中心隊列轉向對普通隊列進行服務時,就不需要再經歷一個查詢轉換時間,而是直接轉向普通隊列對其進行服務.當普通隊列i的數據信息量完成發(fā)送之后,服務器會經歷一個查詢轉換時間再一次轉向中心隊列,對其進行完全服務,當中心隊列的發(fā)送服務完成之后,第i+1個普通隊列將會得到服務,該模型的查詢順序如下圖2所示.服務器采用兩種混合式的輪詢服務,可以讓中心隊列獲得更多的服務時間,實現(xiàn)了中心隊列與普通隊列之間優(yōu)先級的區(qū)分,同時也保證了一般的業(yè)務能夠得到普通隊列的服務[10].

1 系統(tǒng)模型

兩級優(yōu)先級非對稱輪詢控制系統(tǒng)的控制機制是由一個服務器及N+1個隊列來構建組成的,N+1個隊列中包括N個普通隊列和一個中心隊列[9],分析過程中則用h來對中心隊列進行代替.因為兩級優(yōu)先級非對稱輪詢系統(tǒng),是一種對稱與非對稱相結合的混合式輪詢服務系統(tǒng),在這種服務模式中,中心隊列由1個隊列構成,在每一次輪詢服務的過程中,其自身的性能參數都是固定不變的,這在局部的意義上可以說是一種對稱性的體現(xiàn);此外,由于多個普通隊列中,每個隊列都有其獨立不同的性能參數(到達率、服務時間、轉換時間)設置,體現(xiàn)多個普通隊列之間所存在的非對稱性,所以需要對中心隊列和普通隊列,分別采用兩種不同的輪詢服務.

圖1 兩級輪詢服務模型Fig.1 Two-level polling service model

圖2 系統(tǒng)的查詢服務順序Fig.2 System query service sequence

設定在tn時刻隊列i(i=1,2,···,N)接受到服務器的發(fā)送服務,第i個隊列中所包含的數據信息量為ξi(n),定義系統(tǒng)的隨機變量為{ξ1(n),ξ2(n),···,ξN(n),ξh(n)}, 其所耗費的服務時間定義為νi(n).隊列在接受服務期間不斷地會有數據信息量加入隊列,在此時間段到達第j(j=1,2,···,N,h)個隊列的數據信息量為ηj(νi).服務器所提供給普通隊列的服務完成之后,會經過一個查詢轉換時間,在時刻服務器為中心隊列h提供發(fā)送服務,此刻中心隊列中所存在的數據信息量為ξh(n?),定義系統(tǒng)的隨機變量為{ξ1(n?),ξ2(n?),···,ξh(n?),ξh(n?)}. 中心隊列h需要的服務時間定義為νh(n?),隊列中的數據信息量采用完全服務的方式期間,進入到第j(j=1,2,···,N,h)個隊列的數據信息量為ηj(νh).服務完成之后,在tn+1時刻第i+l個普通隊列開始接受服務,定義隨機變量{ξ1(n+1),ξ2(n+1),···,ξN(n+1),ξh(n+1)}.服務器經第i個隊列轉換到中心隊列,再經中心隊列轉換到第i+l個隊列,其所耗費的轉換時間為μi(n),在此時間段加入到第j(j=1,2,···,N,h)個隊列的數據信息量為μj(μi),輪詢系統(tǒng)的隨機變量存在以下關系為

1.1 工作條件

1)在任何時刻加入隊列的數據信息量服從于彼此獨立的、且同分布的泊松過程,其分布概率母函數為Ai(zi),均值為,方差為其中i=1,2,···,N;中心隊列的分布為.

2)服務器對任意一個隊列進行發(fā)送時,隊列中所包含的數據信息量在發(fā)送的時候所耗費的時間滿足于彼此獨立的、且同分布的過程,其分布概率母函數為Bj(zj),均值為,方差為,其中j=1,2,···,N;中心隊列的分布為.

3)服務器完成隊列的發(fā)送服務,隊列之間進行切換時,所耗費時間的分布過程的概率母函數為Rk(zk),均值為,方差為,其中k=1,2,···,N;中心隊列的分布為.

4)設定服務系統(tǒng)中任何一個隊列的緩存容量足夠大,不存在數據信息量丟失的情況發(fā)生;

5)每一個加入進隊列的數據信息量,將會按照先到先服務(First come first served,FCFS)的方法接受服務[11].

1.2 系統(tǒng)分析定義的變量

ui(n):第i個普通隊列在接受完服務之后,查詢轉換到中心隊列所耗費的時間;

vi(n):服務器完成對第i個普通隊列中數據信息量的發(fā)送服務所耗費的時間;

vh(n?):服務器完成對中心隊列所包含的數據信息量的發(fā)送服務所耗費的時間;

μj(ui):設定為在ui(n)這段時間長度內加入進第j個隊列的數據信息量;

ηj(vi):設定為vi(n)這段時間長度內加入進第j個隊列的數據信息量;

ηj(vh):設定為在vh(n?)這段時間內加入進第j個隊列的數據信息量.

概率母函數定義為

在tn?時刻系統(tǒng)狀態(tài)變量的概率母函數為

在tn+1時刻系統(tǒng)狀態(tài)變量的概率母函數為

式中,Fi(zi)=Ai(Bi(ziFi(zi))),i=1,2,···,N表示服務器對任意一個隊列,在任一時段內到達的數據信息量以及在服務期間到達的數據信息量使用完全服務的方式所需時間的隨機變量的概率母函數[13].

2 輪詢系統(tǒng)的一階和二階特性

2.1 平均排隊隊長

根據式(4)和式(5)求得第i個普通隊列的平均排隊隊長的表達式為

同理,采用上述方法可以得到中心隊列的平均排隊隊長的表達式為

gih(h)表示為普通站點i所有的數據信息量接受完服務,轉換到中心站點之后,這段時間內以及在服務期間進入中心站點的所有數據信息量的平均排隊隊長,所以在以下對中心隊列進行分析時會出現(xiàn)多段各不相同的平均排隊隊長和平均等待時間的情況.

2.2 循環(huán)查詢周期

輪詢系統(tǒng)的循環(huán)查詢周期表示為:同一隊列被服務器前后兩次訪問時刻的時間差,其具體為N+1個隊列按規(guī)定的服務規(guī)則進行一次服務所花費時間的統(tǒng)計平均值[14].所以可以計算得到兩級非對稱輪詢系統(tǒng)的循環(huán)周期E(θ).

2.3 二階偏導量

定義:

則由式(4)和式(5)可以得到以下二階偏導量:

將式(18)求和,并利用式(20)化簡得到

2.4 基于循環(huán)查詢周期的近似分析方法

根據循環(huán)查詢周期的定義得到該隨機變量的概率母函數為θi(zi),并有如下關系式:

對此式進行二階求導,得到

因為系統(tǒng)的二階特性量有

根據式(22),式(24)及式(25)得到

根據式(26)并分別結合式(22)和式(18)可以得到gih(h,h)和gi(i,i)的近似表達式.

2.5 平均等待時間

信息分組的平均等待時間是指數據信息量到達隊列被發(fā)送出去所需的時間.根據上述計算得到的gi(i,i)和gih(h,h)的近似表達式,分別代入下面兩式即可求得平均等待時間的表達式.

普通站點的平均等待時間為

中心站點的平均等待時間為

3 仿真實驗及性能分析

基于上述所建立的兩級優(yōu)先級非對稱輪詢服務模型,同時根據以下所建立的工作條件進行理論值計算和實驗仿真[15?16].

1)各隊列的參數變量都應當服從相同的分布,但是各變量并不具備對稱性;

2)任一時隙內進入各隊列的數據信息量都滿足Poisson分布;

根據如下表1中所設置的初始參數的基礎之上,得到以下圖中服務模型性能特點的變化情況.

表1 服務模型的基礎參數Table 1 Basic parameters of the service model

圖3與圖4展示了普通隊列與中心隊列的平均排隊隊長隨到達率變化的情況,從圖中可以看出在到達率不斷增加的情況下,普通隊列服從于與到達率相同的變化規(guī)律,即到達率變大其也會隨之而變大,當然中心隊列亦滿足此種變化形式.同時,可以從圖中分析得到高優(yōu)先級的隊列與低優(yōu)先級隊列的隊長之間的區(qū)分度是比較高的,受到達率影響的情況下,低優(yōu)先級的隊長都遠大于高優(yōu)先級的隊長.

圖3 普通隊列平均排隊隊長隨到達率影響變化(N=5)Fig.3 The average queue length of ordinary queue varies with arrival rate(N=5)

圖4 中心隊列平均排隊隊長隨到達率影響變化(N=5)Fig.4 The average queue length of central queue varies with arrival rate(N=5)

圖5 普通隊列平均排隊隊長隨服務時間影響變化(N=5)Fig.5 Variation of average queue length with servicetime in ordinary queue(N=5)

從圖5與圖6可以看出普通隊列與中心隊列的平均排隊隊長受服務時間的影響比較明顯,服務時間增加時隊長也會隨之而變大.同樣,兩種具有不同優(yōu)先級的隊列,其平均排隊隊長有著很大的差別,很好地說明了輪詢系統(tǒng)的優(yōu)先級得到了較好的區(qū)分.除此之外,圖中1至h與5至h這兩段時長的中心隊列的平均排隊隊長的增長率與其他幾個隊列相比是比較小的.主要原因則由各隊列到達率的不同而引起的,這與理論分析相一致,由式(6)可以看出中心隊列的隊長與到達率成正比關系,所以這兩段時長到達率較小時,給中心隊列的隊長帶來的影響較小.

表2 兩種模型理論值與實驗值的對比Table 2 Comparison between theoretical values and experimental values of two models

圖6 中心隊列平均排隊隊長隨服務時間影響變化(N=5)Fig.6 The average queue queue length of central queue varies with service time(N=5)

圖7 循環(huán)查詢周期隨系統(tǒng)負載影響變化(N=5)Fig.7 Cyclic query cycle varies with system load(N=5)

圖7中系統(tǒng)的負載是指普通隊列的總負載,并不包含中心隊列的負載,主要是為了方便仿真圖形的構建,并與其他非對稱模型形成對比,此外需要說明的是中心的負載的改變,同樣會對系統(tǒng)的特性產生影響.圖7至圖8也是如此情況.從圖6中可以看出,輪詢系統(tǒng)的循環(huán)查詢周期隨著負載的增大而不斷變大,同時,循環(huán)查詢周期的理論值與實驗值之間有著較好的穩(wěn)合性.

從圖8到圖9可以看出,當選取的循環(huán)次數較大時,平均等待時間的理論值與實驗值是保持一致的且誤差較小.對于同一系統(tǒng)而言,當系統(tǒng)的負載變大時,平均等待時間也是隨之而變大的,同時,系統(tǒng)的隊列數增加時這種關系依然存在.系統(tǒng)在同一負載的情況下,中心隊列的平均等待時間小于普通隊列的平均等待時間,這也很好地說明采用混合的輪詢服務方式來進行優(yōu)先級的區(qū)分,是有顯著成效的,使得系統(tǒng)的性能得到了一個整體優(yōu)化.綜上所述,該服務模型運用循環(huán)查詢周期二階特性近似相等的方法得到了平均等待時間的近似解.該種近似方法運用在本文所建立的模型當中,比較適用于達到率較小的情況,同時,當系統(tǒng)的負載相對較高時,理論值與實驗仿真值的誤差就會相對變大,此時需要考慮該分析方法的容錯范圍.

表2中展示了非對稱門限服務與本文所提出模型的性能特性比較,從表2中可以看出當兩級優(yōu)先級非對稱輪詢模型普通隊列的總負載與非對稱門限服務的總負載在相同的情況下,兩級優(yōu)先級非對稱模型的平均排隊隊長和平均等待時間都略大于非對稱門限的兩種特性,從另一方面也說明了中心隊列的負載可以影響整個系統(tǒng)的服務特性,所以對非對稱性的輪詢服務系統(tǒng)進一步進行優(yōu)先級的區(qū)分,可以讓具備更高優(yōu)先級的隊列獲得更多的服務時間和更高的服務效率.此外兩種非對稱性的模型理論值與實驗值之間都有著較好的吻合性,誤差較小,說明了兩種非對稱模型的服務特性得到了較好的解析,進一步驗證了模型解析過程的正確性.

圖8 普通隊列平均等待時間受負載影響變化(N=5)Fig.8 Average waiting time of ordinary queues is affected by load changes(N=5)

圖9 中心隊列平均等待時間受負載影響變化(N=5)Fig.9 The average waiting time of the central queue is affected by load changes(N=5)

4 結論

本文采取了一種對稱性輪詢服務與非對稱輪詢服務相結合的區(qū)分優(yōu)先級的輪詢服務,即在具有低優(yōu)先級的普通隊列采用非對稱的門限服務,在具有高優(yōu)先級的中心隊列使用對稱性的完全服務.為了提高系統(tǒng)的利用率,所以本文選擇了非對稱性的輪詢服務,并且運用并行模式的服務機制構建了兩級優(yōu)先非對稱服務模型.服務模型的平均排隊隊長和循環(huán)查詢周期,得到了精確的解析.經過大量的實驗分析,使用了一種較為合理的方法較優(yōu)的對系統(tǒng)的二階特性量,平均等待時間進行了解析.并通過仿真實驗實驗與理論分析相比較,驗證了模型解析過程的正確性.

除此之外,需要說明的是此模型二階特性量的近似方法并不局限于本文中所使用的分析方法,還有許多的近似方法值得我們去進一步探索,去找到一種更優(yōu)的方法來對平均等待時間進行解析.當然,在未來工作當中,對其他的一些非對稱性混合服務模型,如對稱性完全–非對稱性完全、限定–非對稱性門限、門限–非對稱性門限等區(qū)分優(yōu)先級的兩級非對稱服務模型進行探討是非常有意義的.