具有負(fù)載平衡動(dòng)態(tài)路由選擇的排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性研究

唐柏榮， 王知人， 涂建新， 李泉林

(1.燕山大學(xué)計(jì)算數(shù)學(xué)系 河北秦皇島066004;2.燕山大學(xué)管理科學(xué)與工程系 河北秦皇島066004)

，即增廣流體模型弱不穩(wěn)定．必要性證

0 引言

排隊(duì)網(wǎng)絡(luò)服務(wù)顧客的效率高低與排隊(duì)網(wǎng)絡(luò)是否穩(wěn)定密切相關(guān)，而排隊(duì)網(wǎng)絡(luò)收益與排隊(duì)網(wǎng)絡(luò)服務(wù)顧客的效率也是密切相關(guān)的，因此排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題倍受關(guān)注．許多學(xué)者對(duì)具有多個(gè)顧客類(lèi)的排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題進(jìn)行了研究，如文獻(xiàn)［1-2］得出了具有多個(gè)顧客類(lèi)的排隊(duì)網(wǎng)絡(luò)穩(wěn)定的充分條件，其主要條件是排隊(duì)網(wǎng)絡(luò)相應(yīng)的流體模型穩(wěn)定．一些學(xué)者對(duì)每個(gè)服務(wù)站具有單服務(wù)臺(tái)的排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題進(jìn)行了研究，如文獻(xiàn)［3］中每個(gè)到達(dá)者隨機(jī)選取兩個(gè)服務(wù)臺(tái)，然后加入較短的隊(duì)列，得到了隊(duì)長(zhǎng)的漸近分布存在的充分條件．文獻(xiàn)［4］得到隊(duì)長(zhǎng)過(guò)程正常返的充分條件．文獻(xiàn)［5］中到達(dá)間隔時(shí)間和服務(wù)時(shí)間都服從一般分布，當(dāng)J=2時(shí)通過(guò)流體模型得到了一個(gè)排隊(duì)網(wǎng)絡(luò)穩(wěn)定的充要條件以及一個(gè)排隊(duì)網(wǎng)絡(luò)不穩(wěn)定的充分條件．一些學(xué)者對(duì)每個(gè)服務(wù)站具有多服務(wù)臺(tái)的排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題進(jìn)行了研究，如文獻(xiàn)［6］研究了具有J個(gè)服務(wù)站且每個(gè)服務(wù)站都具有N個(gè)服務(wù)臺(tái)的排隊(duì)網(wǎng)絡(luò)，到達(dá)間隔時(shí)間和服務(wù)時(shí)間都服從指數(shù)分布，一個(gè)突出的特點(diǎn)是出現(xiàn)了檢驗(yàn)數(shù)分布的概念．每個(gè)到達(dá)者和每個(gè)接受完服務(wù)但仍留在網(wǎng)絡(luò)的顧客都要加入到一個(gè)服務(wù)臺(tái)集(樣本)中的某個(gè)最短隊(duì)列，得到了q過(guò)程和r過(guò)程正常返的充分條件和必要條件．與文獻(xiàn)［6］中模型不同的是，文獻(xiàn)［7］的模型中每個(gè)到達(dá)者選取的樣本所包含的服務(wù)臺(tái)數(shù)不變;而文獻(xiàn)［8-9］的模型中外部到達(dá)過(guò)程與服務(wù)站相關(guān)，而不是與檢驗(yàn)數(shù)分布相關(guān)，通過(guò)流體模型得到在一些假設(shè)下流體逼近存在．文獻(xiàn)［10］研究的是具有K個(gè)更新到達(dá)流和N個(gè)服務(wù)臺(tái)的JSQ(進(jìn)入最短隊(duì)列)網(wǎng)絡(luò)，每個(gè)到達(dá)者進(jìn)入選擇集(服務(wù)臺(tái)集)中具有最短隊(duì)列的服務(wù)臺(tái)前排隊(duì)，而且每個(gè)顧客的服務(wù)時(shí)間服從一般分布，而本文中每個(gè)到達(dá)者在哪個(gè)服務(wù)臺(tái)前排隊(duì)是與檢驗(yàn)數(shù)分布有關(guān)的，并且到達(dá)流都是泊松到達(dá)流，每個(gè)顧客的服務(wù)時(shí)間服從指數(shù)分布．綜上所述，對(duì)于具有負(fù)載平衡動(dòng)態(tài)路由選擇的網(wǎng)絡(luò)的穩(wěn)定性研究尚不多見(jiàn)．

鑒于此，作者在文獻(xiàn)［5-6］的研究基礎(chǔ)上，對(duì)每個(gè)服務(wù)站具有多服務(wù)臺(tái)、出現(xiàn)了檢驗(yàn)數(shù)分布的概念、每個(gè)到達(dá)者和每個(gè)接受完服務(wù)但仍留在網(wǎng)絡(luò)的顧客都要加入到一個(gè)服務(wù)臺(tái)集(樣本)中的某個(gè)最短隊(duì)列，即利用概率知識(shí)對(duì)具有負(fù)載平衡動(dòng)態(tài)路由選擇的排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題進(jìn)行了隨機(jī)分析，所用的方法與文獻(xiàn)［11］類(lèi)似．

1 預(yù)備知識(shí)

首先介紹負(fù)載平衡模型并給出模型的假設(shè)．

定義1 對(duì)于任意的θ∈Θ，存在一個(gè)相應(yīng)的具有到達(dá)時(shí)間序列{ξθ(n):n≥1}的外部到達(dá)過(guò)程，被稱(chēng)為θ型外部到達(dá)過(guò)程．

假設(shè)每個(gè)服務(wù)臺(tái)都是非閑置的和每個(gè)服務(wù)臺(tái)的服務(wù)規(guī)則都是先進(jìn)先出．由于θ型外部到達(dá)過(guò)程，第1個(gè)顧客到達(dá)的時(shí)刻為 ξθ(1);第 n － 1、n個(gè)顧客的到達(dá)時(shí)間間隔為 ξθ(n)，n≥2．ηi，k(n)，n≥1 表示被服務(wù)臺(tái)(i，k)服務(wù)的第n個(gè)顧客的服務(wù)時(shí)間．假設(shè)對(duì)任意的θ∈Θ都有{ξθ(n):n≥1}獨(dú)立且同分布;對(duì)任意的(i，k)∈C都有{ηi，k(n):n≥1}獨(dú)立同分布;所有到達(dá)間隔時(shí)間序列和所有服務(wù)時(shí)間序列都相互獨(dú)立．若A為集合，則表示A中元素的個(gè)數(shù);若y為向量，則表示y的1范數(shù)．JSQ表示加入最短隊(duì)列，并且排隊(duì)網(wǎng)絡(luò)簡(jiǎn)稱(chēng)為網(wǎng)絡(luò)．

以下介紹網(wǎng)絡(luò)狀態(tài)和網(wǎng)絡(luò)過(guò)程．

用 X(t)=(Z(t)，U(t)，V(t))表示網(wǎng)絡(luò)在 t時(shí)刻的狀態(tài)，其中，Z(t)={Zi，k(t):(i，k)∈ C}，U(t)={Uθ(t):θ∈ Θ}，V(t)={Vi，k(t):(i，k)∈ C}．Zi，k(t)表示 t時(shí)刻服務(wù)臺(tái)(i，k)的隊(duì)長(zhǎng);Uθ(t)表示 t時(shí)刻 θ型外部到達(dá)過(guò)程的剩余到達(dá)間隔時(shí)間;Vi，k(t)表示(i，k)服務(wù)臺(tái)中正在服務(wù)的顧客在t時(shí)刻的剩余服務(wù)時(shí)間，則狀態(tài)空間S為R2NJ+|Θ|的子集．假設(shè)網(wǎng)絡(luò)過(guò)程X={X(t):t≥0}右連續(xù)且具有左極限，則由文獻(xiàn)［1］的命題2．1可知，X是強(qiáng)馬爾可夫過(guò)程．

2 流體模型

先給出描述JSQ網(wǎng)絡(luò)動(dòng)態(tài)行為的關(guān)系式組．

用 Ai，k(t)表示［0，t］中外部和內(nèi)部到達(dá)服務(wù)站 i中并要被服務(wù)臺(tái)(i，k)服務(wù)的顧客數(shù);Eθ(t)表示［0，t］中由于θ型外部到達(dá)過(guò)程而從網(wǎng)絡(luò)外部到達(dá)的顧客數(shù);Di(t)表示［0，t］中服務(wù)站i上接受完服務(wù)的顧客數(shù);Ti，k(t)，Ii，k(t)分別表示［0，t］中服務(wù)臺(tái)(i，k)的工作時(shí)間積累和空閑時(shí)間積累;Si，k(t)表示服務(wù)臺(tái)(i，k)花費(fèi)t單位時(shí)間服務(wù)完的顧客數(shù);Φi，θ(n)表示從服務(wù)站i上離去的前n個(gè)顧客獲得檢驗(yàn)數(shù)分布θ的個(gè)數(shù)．當(dāng)(i，k)∈C及t≥0時(shí)，描述JSQ網(wǎng)絡(luò)的動(dòng)態(tài)如下:

因?yàn)镾i，k(Ti，k(t))表示在［0，t］中服務(wù)臺(tái)(i，k)服務(wù)完的顧客數(shù)，Ai，k(t)表示［0，t］中外部和內(nèi)部到達(dá)服務(wù)站i中并要被服務(wù)臺(tái)(i，k)服務(wù)的顧客數(shù)，所以有

因?yàn)閠時(shí)刻服務(wù)臺(tái)(i，k)的隊(duì)長(zhǎng)至少為空，所以有

因?yàn)?Ti，k(t)，Ii，k(t)分別表示［0，t］內(nèi)服務(wù)臺(tái)(i，k)的工作時(shí)間積累和空閑時(shí)間積累，所以有

因?yàn)榉?wù)臺(tái)(i，k)都是非閑置的，所以有

如果對(duì)任意的 u∈ (s，t)都有 Zi，k(u)＞ 0，則

因?yàn)镾i，k(Ti，k(t))表示在「0，t■內(nèi)服務(wù)臺(tái)(i，k)服務(wù)完的顧客數(shù)，Di(t)表示［0，t］內(nèi)服務(wù)站i上接受完服務(wù)的顧客數(shù)，所以有

如果 Μ ?J，0≤s≤t且對(duì)任意的k，l=1，2，…，N，i∈ Μ，j∈J－ Μ，及u∈(s，t)都有Zi，k(u)＞Zj，l(u)，則有

式(7)和(8)執(zhí)行了顧客的JSQ路由選擇行為．

下面介紹流體極限的概念，先給出一個(gè)引理．

證明 因?yàn)閧ξθ(n)，n≥1}，θ∈Θ是獨(dú)立同分布隨機(jī)變量序列

由文獻(xiàn)［1］的定理4．1，給出了流體極限的定義．

定義2 對(duì)任意一個(gè)滿足(9)～(11)的ω及任意一個(gè)使得{xr/r:r＞0}有界的初始狀態(tài)集{xr:r＞0}，必存在一個(gè)子序列rn→∞ 使得在［0，∞)的任意一個(gè)緊集上都一致收斂到=(·)，(·)，(·)，(·))，則稱(chēng)為流體極限．

因?yàn)閍．s．是幾乎必然的意思，所以(9)成立;同理，(10)成立．

其中，xr=(zr，ur，vr)，則稱(chēng)為無(wú)延遲的流體極限．

根據(jù)文獻(xiàn)［12］知，如果利用流體極限來(lái)研究網(wǎng)絡(luò)的穩(wěn)定性問(wèn)題，則只需考慮無(wú)延遲的流體極限．

為了獲得流體模型關(guān)系式組，先給出引理2．

式(13)～(19)為流體模型關(guān)系式組，其解稱(chēng)為流體模型的解．都 Lipschitz連續(xù)以及(13)～ (19)成立即可，在文獻(xiàn)［2］中可以找到另外兩個(gè)要證的結(jié)論．設(shè)ω滿足(9)～(11)，則可以選取xr的子序列xrn使得對(duì)某個(gè)(·)，在非負(fù)有理數(shù)集上恒有

證明 只需證明

同理可得

在先進(jìn)先出規(guī)則下，用 Γi，k(n)表示服務(wù)臺(tái)(i，k)服務(wù)完的前 n個(gè)顧客的服務(wù)時(shí)間之和，則恒有Γi，k(Si，k(Ti，k(t)))≤ Ti，k(t) ＜ Γi，k(Si，k(Ti，k(t))+1)，即

由(10)可知，對(duì)任意給定的ε＞0以及足夠大的n，(23)的最右邊項(xiàng)都小于等于

而對(duì)任意給定的ε＞0以及足夠大的n，(23)的最左邊項(xiàng)都大于等于

取n→∞，夾逼得

由(11)、(24)可知，當(dāng)n→∞ 時(shí)，

與上一段的證明類(lèi)似，由(9)可知

所以當(dāng)(7)、(8)中 s→ t時(shí)，(18)、(19)成立．又因?yàn)?·)Lipschitz連續(xù)，所以(·)也 Lipschitz連續(xù)．如果選取一個(gè)子序列 rn使得(0)存在，由(1)、(24)和(27)可知因?yàn)?·)和(·)都Lipschitz連續(xù)，所以(·)也Lipschitz連續(xù)．由(1)、(2)、(24)、(27)以及(28)可知，(13)、(14)成立．當(dāng)(5)中 s→ t時(shí)，由(22)、(28)可知，(17)成立．引理2證畢．

下面給出流體模型穩(wěn)定和弱不穩(wěn)定的定義，為了將網(wǎng)絡(luò)和其相應(yīng)的流體模型聯(lián)系起來(lái)，給出了引理3和引理4．

引理3［1］如果流體模型穩(wěn)定，則馬爾可夫過(guò)程是Harris正常返的．

引理4［14］如果流體模型弱不穩(wěn)定，則馬爾可夫過(guò)程不穩(wěn)定，即對(duì)每個(gè)固定的初始狀態(tài)x，當(dāng)t→∞時(shí)都以概率1收斂到無(wú)窮．

3 增廣流體模型

其中，Ρx－a．s．表示初始狀態(tài)為x時(shí)以概率1收斂．所以對(duì)每個(gè)具有固定的初始狀態(tài)的流體極限，都有

現(xiàn)選擇一個(gè)緊集K?S，使得 π(K)=∫SΡ(z，u，v)(X(t)∈ K)dπ(z，u，v)＞ 0，t≥0．因?yàn)閷?duì)任意的 x ＞ 0，都有 Ρ(ξθ(1)≥ x)=1 － Ρ，所以存在一個(gè) t0＞ 0，使得對(duì)任意的(z，u，v)∈ K 都有 Ρ(z，u，．因此有

故由(30)得到(29)．引理5證畢．

式(13)～(19)及式(29)為增廣流體模型關(guān)系式組，其解稱(chēng)為增廣流體模型的解．

引理6對(duì)證明馬氏過(guò)程不是Harris正常返非常有用，因?yàn)橹恍枰C明增廣流體模型弱不穩(wěn)定即可．

4 主要結(jié)果

文獻(xiàn)［5］研究的是單服務(wù)臺(tái)情形，而作者研究的是至少具有兩個(gè)服務(wù)站、每個(gè)服務(wù)站至少具有兩個(gè)服務(wù)臺(tái)的情形;文獻(xiàn)［6］中服務(wù)強(qiáng)度恒為1，而作者研究的是服務(wù)強(qiáng)度與服務(wù)站有關(guān)，即文中的模型較文獻(xiàn)［5－6］復(fù)雜，所以通過(guò)假設(shè)1使得模型稍微簡(jiǎn)單一些．

假設(shè)1 對(duì)任意一個(gè) θ∈Θ，p*i，pi，θ都與i無(wú)關(guān)．對(duì)于 Μ?，令PΜ=PiΜ，假設(shè)p*＜1，p*=p*i，pθ=p，λ*= Λ ．i，θJ

證明 因?yàn)閷儆谕环?wù)站的服務(wù)臺(tái)對(duì)稱(chēng)，所以Μ滿足(19)．由(19)有

將(32)減去(33)得

由(34)和(35)得

將(36)、(37)代入(33)得

由(13)、(37)有

將(38)代入(39)即可得到(31)．引理7證畢．

由引理7，對(duì)任意這樣的t，有

由(41)可知流體模型穩(wěn)定．由引理3可知充分性證畢．

再證必要性．根據(jù)引理6，只需證明如果(40)不成立，增廣流體模型則弱不穩(wěn)定．設(shè)存在Μ?J→使(40)不成立．設(shè)為一個(gè)具有(0)=0特點(diǎn)的增廣流體模型的解．

由(13)、(18)得

將(43)代入(42)，得

由(29)得

因?yàn)棣?40)不成立以及(44)，所以對(duì)所有的t≥0，都有

令畢．所以定理1證畢．

，即增廣流體模型弱不穩(wěn)定．必要性證

證明 由(13)、(18)得

在(19)中取 Μ =J，由(13)、(19)得

將(47)代入(46)，得

由引理8可知，對(duì)所有的t＞0有·f (t)＞ 0．從而f(t)＞ 0，因此對(duì)所有的t＞ 0，有 Z－(t) ＞0．故流體模型弱不穩(wěn)定，由引理4可知定理2得證．

［1］ Dai Jiangang.On the positive Harris recurrence of multiclass queueing networks:a unified approach via fluid limit models［J］.The Annals of Applied Probability，1995，5(1):49-77.

［2］ Maury B.Stability of Queueing Networks［M］.Berlin:Springer，2008:81-131.

［3］ Vvedenskaya N D，Dobrushin R L.Queueing system with the shortest of two queues:an asymptotic approach［J］.Problems of Information Transmission，1996，32(1):15-29.

［4］ Foley R D，Mcdonald D R.Join the shortest queue:stability and exact asymptotics［J］.The Annals of Applied Probability，2001，11(3):569-607.

［5］ Dai Jiangang，Hasenbein J J，Kim B.Stability of join-the-shortest-queue networks［J］.Queueing Systems，2007，57(4):129-145.

［6］ Suhov Y M，Vvedenskaya N D.Fast Jackson networks with dynamic routing［J］.Problems of Information Transmission，2002，38(2):136-153.

［7］ Martin J B，Suhov Y M.Fast Jackson networks［J］.The Annals of Applied Probability，1999，9(3):854-870.

［8］ 郭永江.每個(gè)節(jié)點(diǎn)具有多服務(wù)臺(tái)的Jackson網(wǎng)絡(luò)流體逼近的收斂速度［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2008，28(9):1118-1133.

［9］ Chen Hong.Fluid limits and diffusion approximations for networks of multi-server queue in heavy traffic［J］.Discrete Event Dymamic Systems，1994，4(3):269-291.

［10］ Bramson M.Stability of join the shortest queue networks［J］.The Annals of Applied Probability，2011，21(4):1568-1625.

［11］趙湘育，王東煒，張剛.網(wǎng)絡(luò)系統(tǒng)可靠度和單元概率重要度的隨機(jī)模擬分析［J］.鄭州大學(xué)學(xué)報(bào):理學(xué)版，2009，41(4):108-111.

［12］ Bramson M.Stability of two families of queueing networks and a discussion of fluid limits［J］.Queueing Systems，1998，28(1/2/3):7-31.

［13］徐麗.函數(shù)列一致連續(xù)和一致收斂及等度連續(xù)的關(guān)系［J］.上海電力學(xué)院學(xué)報(bào)，2007，23(3):284-287.

［14］ Dai Jiangang.A fluid-limit model criterion for instability of multiclass queueing networks［J］.The Annals of Applied Probability，1996，6(3):751-757.