具有兩階段故障的流模型近似解分析

劉煜飛,葉晴晴

(南京信息工程大學數學與統計學院,江蘇 南京 210044)

1.引言

流模型研究了一類輸入輸出系統,此類系統在許多領域具有廣泛的應用,例如制造系統[1]、計算機通信系統[2]、視頻流量[3]等領域,作為具有離散單元的標準排隊系統的近似,流模型可為系統優化提供參考.關于流模型的具體介紹和經典參考文獻的綜述,可參閱文[4].

完全可靠的排隊系統在現實生產生活中幾乎不存在,因此,具有故障或工作故障策略的排隊系統在過去幾十年里受到了相當多的關注,對于具有故障策略的排隊系統研究可以追溯到文[5],對于具有部分故障策略的排隊系統研究可以追溯到Kalidass等文[6]及其參考文獻.隨后,眾多學者考慮了具有各種特征的不可靠排隊系統.Sherman等[7]研究了具有無限容量的不可靠M/M/1重試排隊系統,并給出了該系統的平穩條件與系統性能指標的顯示解.YE等[8]研究了具有工作故障的MAP/M/1排隊系統,利用矩陣幾何解法得出了系統在穩態下的客戶數,并對系統性能指標進行了分析.GAO等[9]研究了具有災難與故障策略的離散時間排隊系統,利用嵌入式馬爾可夫鏈和補充變量法,確定了顧客到達前時刻與任意時刻的系統隊長分布,并得到了顧客在系統中的逗留時間.YANG等[10]研究了一個具有異構服務器的M/M/2排隊系統,利用擬生滅過程與矩陣幾何解法得到了系統的平穩分布,并利用粒子群優化算法對系統的近似最優服務率進行數值求解.

很少有學者研究具有故障或工作故障策略的流模型.Vijayalakshmi和Thangaraj[11]研究了由生滅過程驅動的流模型,利用Laplace變換與連分數,得到了該模型性能指標的穩態概率分布.Vijayashree等[12]研究了一個由具有災難與后續修復的M/M/1/N排隊系統驅動的流模型,該驅動系統在進行維修時將以較低的速率為到達系統的流體提供服務,通過構建該模型所滿足的微分差分方程組,利用第一類Bessel 函數得到了該流模型庫存量穩態概率分布的顯式表達式.Vijayashree等[13]在文[12]的基礎上將驅動系統拓展為具有災難與后續修復的M/M/1排隊系統,利用該模型所滿足的微分差分方程組與Laplcae變換,得到了該排隊系統庫存量的穩態概率的精確表達式.Seenivasan等[14]研究了一個包含工作休假和故障的多服務器流模型,利用矩陣幾何解法得到了該流模型庫存量的穩態分布.Felicia等[15]研究了帶有反饋顧客和故障的M/M/1排隊系統驅動的流模型,并通過Laplace變換得到了庫存量的平穩分布.Nabli[16]在研究有限狀態不可約馬爾可夫鏈驅動的流模型中,提出了一種基于遞推關系的用于逼近流模型庫存量尾分布的算法,并給出了計算截斷步長(Truncation step)的算法.

隨著現代計算機技術的發展,社會中對于大數據產品業務的需求不斷增長,為了提供此類產品,供應商增加了服務器的數量,與此同時維護此類服務器的壓力也隨之增大.各種軟、硬件故障而造成的業務中斷成為影響大數據服務穩定性的重要因素之一.為了減少因故障而產生的服務中斷,大數據服務供應商不約而同的開始了硬件自愈的研究.在阿里云對于硬件自愈[17]的研究中提及當系統發現故障發生時,系統將啟動一階段維修,在降低服務速率的同時開始維修,當維修完成時再以正常服務速率提供服務;若在一階段維修時再次出現故障,系統將停止服務進行徹底的維修.本文受這類硬件自愈研究與流模型的啟發,考慮了一個具有兩階段故障策略的流模型,即當系統處于正規忙期時若故障發生,系統將進入部分故障期并立刻開始維修,且在維修期間緩沖器將以較低的服務速率為到達系統的流體提供服務,直到維修完成系統重新進入正規忙期;若當系統處于部分故障期時再次發生故障,系統將完全停止服務并繼續維修,直到維修完成后進入正規忙期.不失一般性,本文使用流體到達速率作為流模型的輸入率,使用緩沖器的輸出速率作為流模型的輸出率.

本文將兩階段故障策略與流模型相結合,利用歸一化技術,通過遞推得到了該流模型庫存量尾分布函數的近似解,并給出了給定誤差限下截斷步長的計算方式,為該模型性能指標的求解提供了一種新的方法.其理論成果存在潛在的應用,可將該模型應用于云計算服務中具有硬件自愈的系統分析中.

2.流模型描述

考慮具有兩階段故障的流模型,假設如下: 流體以參數為λ的泊松流到達緩沖器,即流體的輸入速率為λ.當系統處于正規忙期時,流體的輸出速率為μ.在正規忙期內,每次故障發生的間隔時間服從參數為α的指數分布,即故障的發生服從參數為α的泊松過程,一旦遭遇故障,系統將進入部分故障期,其長度服從參數為β的指數分布.在部分故障期內,流體的輸出速率降低為η(η<μ).在部分故障期內,緩沖器可能再次遭遇故障,不失一般性,假設在部分故障期內故障的發生也服從參數為α的泊松過程.一旦處于部分故障期內的緩沖器遭遇故障,系統將進入完全故障期,其長度服從參數為β的指數分布.當完全故障期結束時,系統將進入正規忙期.假設顧客到達的時間間隔,緩沖器在正規忙期的輸出速率,緩沖器在部分故障期的輸出速率,故障發生時間與維修時間相互獨立.此外,假設服務順序為先進先出(FIFO).

該流模型的狀態可以用馬爾可夫過程X=(X(t),t ≥0)來表示,其中:X(t)為時刻t流模型所處的狀態,且

狀態空間為S=(0,1,2),對應的無窮小生成元為

令Q(t)表示時刻t的庫存量,且為非負隨機變量.設流模型庫存量的凈輸入速率(輸入速率-輸出速率)為二維隨機程{(Q(t),X(t)),t ≥0}的函數,滿足

其中,d0>0,d2<0,d1符號待定.具體來說,當流模型處于完全故障期時,庫存量將以速率|d0|線性增加;當流模型處于正規忙期時,庫存量將以速率|d2|線性減少;當流模型處于部分故障期時,庫存量將以速率|d1|線性變化(d1>0時增加,d1<0時減小,d1=0時不變).當庫存量為空時,流模型所處的狀態不會發生改變,且只有故障發生或修復完成時流模型的狀態才會改變.此外,定義依賴于凈輸入速率的狀態空間

定義π=(π0,π1,π2)為X=(X(t))的穩態概率.行向量π滿足

其中,0與1分別是由0和1構成的三維行向量,T為轉置算子.該流模型的穩態條件為

因此,過程{(Q(t),X(t)),t ≥0}是一個二維馬爾可夫過程,定義該馬爾可夫過程在時刻t的尾分布函數為

當穩態條件(2.5)成立時,記過程{(Q(t),X(t)),t ≥0}的極限分布為{Q∞,X∞}.令

為了便于表示,引入矩陣

由文[18],行向量F(x)滿足下列微分方程

其中,F′(x)為F(x)在x處的導數.為了求解尾分布函數Fi(x),需要求解微分方程(2.10),并確定初始條件F(0).當Fi(x)確定時,流模型庫存量在穩態條件下的尾分布函數可由全概率公式計算得到

同時,該流模型的平衡方程(輸出速率=輸入速率)可表示為

3.模型分析

在本部分中,本文將使用歸一化技術求解具有兩階段故障的流模型尾分布函數的近似解,并給出計算截斷步長的算法,詳細的理論可參閱文[16].令a=max(-aii),其中:aii為矩陣A的第i個對角線元素,事實上a=α+β.同時,令d=min{di|di>0}.隨后定義

其中:I是一個三維單位矩陣.顯然,矩陣P是隨機的,即矩陣P的所有元素都是非負的且每一行和為1.此外,矩陣P滿足

由式(2.2)與穩態條件(2.5),可以確定d0>0且d2<0,但d1的符號是不確定的,故本部分將根據d1的符號進行分類討論,用遞推表達式給出庫存量Q(t)的尾分布函數的近似解.

情形一d1>0

由于d1>0且d0>0,d2<0,故矩陣D是可逆的,由式(2.10),可得

隨后,需要確定初始條件F(0).由式(2.3),d1>0時依賴于凈輸入速率的狀態空間為S+={0,1}與S-={2}.顯然,當X(t)=0,1時,庫存量Q(t)以概率1滿足Q(t)>0,故當i=0,1時,Fi(0)=πi.此外,由平衡方程(2.12)與S-={2},得F2(0)=-(d0π0+d1π1)/d2.在下面的定理中,將給出一個數值穩定的算法來計算向量F(x).

定理3.1當穩態條件(2.5)成立時,對于任意實數x ≥0,尾分布函數Fi(x)滿足

其中系數bi(k)≥0且滿足: 當k=0時,

證矩陣AD-1可以寫成分塊矩陣的形式

注意到,d/d2<0而1-αd/ad2>1,在進行計算時可能會發生正負抵消而使得算法不穩定.為了避免這一問題,給出另一個與i=2有關的遞推式,在這個式子中將只出現正數.

定義行向量d=(d0,d1,d2),可得

對于所有整數k,可得

考慮到b(0)=F(0),可得

由此,得到d0b0(k)+d1b1(k)+d2b2(k)=0,這就是定理中提到的與i=2相關的表達式.

由參數d與α的定義,可知α/a,β/a與d/di,i=0,1都是以1為界的正數,此外1-dβ/d0α與1-d/d1是非負的.由于bi(0)=Fi(0)且Fi(0),i=0,1,2是非負的,使用歸納法可證明對于所有k ≥0,有

證畢.

由式(2.11),可得

下一個定理將證明數列(bi(k))k∈N的單調性和收斂性.

定理3.2當i=0,1,2時,(bi(k))k∈N是一個以πi為上界的遞減數列,且滿足

證首先,通過歸納法證明數列(bi(k))k∈N的單調性.當i=1時,

由于b(0)=F(0),可得

考慮到πP=π,即π1[1-(α+β)/a]+π2α/a=π1,得到

由π0(1-β/a)+π2α/a=π0,得到

后,對b0(2)與b0(1)作差,得到

由于b0(1)-b0(0)=0,b1(1)≤b1(0),得到

由b2(0)=F2(0)=π2-P {Q=0}且d/d2<0,得到

由參數的定義,可知d/d0∈(0,1],d/d1∈(0,1],d2<0,同時α/a ∈(0,1],β/a ∈(0,1],(α+β)/a=1.由此,可以通過歸納法證明當i=0,1,2時,數列(bi(k))k∈N是單調遞減的.其次,證明數列(bi(k))k∈N的收斂性.由于數列(bi(k))k∈N是非負且遞減的,其極限一定存在.令li為數列(bi(k))k∈N的極限.由式(3.4),當x趨向無窮時,可得

由于當x趨向無窮時,尾分布函數Fi(x)=P {Q(t)>x,X(t)=i}趨向于0,故極限li必須為0.證畢.

為了計算定理3.1中給出的無窮級數,下面給出了一個算法,該算法可以保證結果誤差不超過給定的誤差限ε.對于一個給定的正實數x,首先定義泊松級數的截斷步長為R(x),滿足

具體的計算方式,可參閱文[19].由于數列(bi(k))k∈N的單調性與收斂性,定義另一個截斷步長

由定理3.1和式(2.11),可得

同時,誤差項e(n0)滿足

且,當R(ax/d)

當R(ax/d)≥nε時,由k>nε時b(k)1T≤ε,得

從數值計算的角度來看,若想要計算庫存量的尾分布,并使得計算誤差在給定的誤差限ε內,只需要對式(3.4)從0到n0求和即可.

情形二d1≤0

由于d1≤0,無法確定矩陣D是否可逆.此時,有S+={0}且S-={1,2}.求解式(2.10)在初始條件下的解這一問題可以轉化為下列有解問題

引理3.1[17]當i=0,1,2,n ∈N+且k=0,···,n-1時,可得

引理3.2[17]當n ∈N+且k=0,···,n-1時,可得

定理3.3式(3.31)存在一個解為Gi(x),且Gi(x)滿足

證與文[17]中定理3.4的證明類似.

由初始條件b0(n,0)=π0,b1(n,n)=b2(n,n)=0與式(3.2),可得d/d0=1,d/(d-di)∈[0,1],i=1,2,故當i=0,1,2時,數列bi(n,k)滿足

由于數列(bi(n,k))n≥k是以πi為上界的單調遞減數列,由引理3.1,其極限bi(k)存在.

為證明當穩態條件(2.5)成立時行向量G(x)=(G0(x),G1(x),G2(x))是式(3.31)的一個解.根據定理3.3中給出的遞推式,可得

定理3.4當穩態條件(2.5)成立時,式(3.31)存在唯一解.

證與文[17]中定理3.5的證明類似,證明將分為2部分,即d1<0與d1=0.

當d1<0時,矩陣D是可逆的,此時式(2.10)可改寫為

與定理3.1類似,當向量F(0)確定時,庫存量尾聯合分布函數F(x)便可以唯一確定.由穩態條件(2.5)可知F(0)是唯一的.同時注意到當i=0,1,2時Fi(x)=0,且F0(0)=π0.由文[17]中定理3.4,此時式(3.31)的解是唯一的.

當d1=0時,定義狀態空間S0={1}與={0,2}.矩陣A與對角矩陣D可以改寫為以下形式

利用文[17]中定理3.5的證明方式,即可證明此時式(3.31)的解是唯一的.綜上,當d1≤0時式(3.31)的解是唯一的.證畢.

由定理3.3與定理3.4,流模型庫存量的尾聯合分布函數可以表示為

從數值計算的角度來看，當(b(n,k))0≤k≤n=(b0(n,k),b1(n,k),b2(n,k))0≤k≤n確定后，便可得到庫存量尾聯合分布函數F(x).

為了計算定理3.3中給出的無窮級數,與d1>0的情況類似,下面給出一個算法,該算法可以保證庫存量尾分布函數誤差不超過給定的誤差限ε的2倍.在計算庫存量尾分布前需要確定系數bi(k),即(n,k).故,首先定義截斷步長n∞為bi(n,k)的迭代次數.由推論3.1,可以尋找到一個n∞使得b(n∞,n∞)1T≤ε.同時,注意到,存在一個n∞,滿足

故,截斷步長n∞最終可定義為

由數列(bi(n,k))0≤k≤n的定義,可得

故,對于k=0,1,···,n∞-1有

由此,對于任意的k ∈N,數列b(n,k)1T

n的極限將在n∞取得,即對于任意的k ∈N

為了提高計算庫存量尾分布函數的效率,定義另一個截斷步長n0,滿足

由于n∞的存在,保證了b(n∞,n∞)1T≤ε,故截斷步長n0一定小于n∞.由式(3.33)與式(2.11),流模型庫存量尾分布的近似解可由下列表達式給出

通過對部分工作狀態下流模型凈輸入率d1的分類討論,本文最終得到了庫存量的尾分布函數的近似解,并通過確定截斷步長,使得該近似解的誤差不超過給定誤差限ε的2倍.

4.庫存量的矩

5.數值例子

假設顧客流以參數為λ的泊松流到達某云計算服務系統緩沖器.該云計算服務系統允許發生兩次故障,且故障發生的間隔時間服從參數為α的指數分布,修理時間服從參數為β的指數分布.在正規忙期內緩沖器的輸出速率為μ,故障發生時,系統將進入部分故障期,輸出速率降低為η(η<μ).系統處于部分故障期時,若再次發生故障,系統將完全停止工作,直到修復完成后,系統進入正規忙期.基于以上假設,本部分將云計算服務中顧客到達視為輸入系統的流體,將服務器視為流模型中輸出流體的緩沖器,構建了一個具有雙階段故障的云計算服務流模型.

情形一d1>0

當d1>0時,顧客流體的到達速率λ大于流模型在部分故障期內緩沖器輸出速率η.

當λ=2.5,α=1,β=1.25時,圖5.1給出了部分故障期內緩沖器輸出速率η分別為1.6,1.8,2.0的情況下平均庫存量E(Q)隨正規忙期內緩沖器輸出速率μ的變化趨勢圖.可以看出,隨著參數μ的增大,平均庫存量E(Q)不斷減小,并趨于一個接近于0的常數.

當α=1,β=1.25,η=2時,圖5.2給出了正規忙期內緩沖器輸出速率μ分別為10,11,12的情況下平均庫存量E(Q)隨顧客流體到達速率λ的變化趨勢圖.可以發現,隨著到達率λ的增加,平均庫存量也會增加.在到達率λ相同的情況下,正規忙期內緩沖器輸出速率μ越大,平均庫存量越小.

圖5.2 d1 >0時E(Q)隨μ和λ的變化曲線

當α=1,β=1.25,λ=5,μ=15時,圖5.3給出了部分故障期內緩沖器輸出速率η分別為4.0,4.2,4.4的情況下庫存量尾分布函數P {Q∞>x}的變化趨勢圖.顯然,當x增大時,尾分布函數P {Q∞>x}趨向于0.同時,部分故障期內緩沖器輸出速率η越大,尾分布函數P {Q∞>x}將越快的趨向于0.

當α=1,β=1.25,λ=2.5,μ=4.4,η=1時,表5.1中展示了對于給定誤差限ε=1×10-9與不同x的取值下獲得的截斷步長nε與R(ax/d).不難發現,當系統參數固定時,截斷步長R(ax/d)隨著x的增加而增加,但是截斷步長nε是固定的.因此,當x較小時,可以選擇R(ax/d)作為計算尾分布函數截斷步長,但隨著的x的增大,應該選擇nε作為截斷步長.

表5.1 不同x取值下的截斷步長

情形二d1=0

當d1=0時,顧客流體到達速率λ與流模型在部分故障期內緩沖器輸出速率η相同.

當α=1,β=1.25時,圖5.4給出了顧客流體到達率λ與部分故障期內緩沖器輸出速率η相同時平均庫存量E(Q)隨到正規忙期內緩沖器輸出速率μ的變化趨勢圖.可以發現,隨著輸出速率μ的增加,平均庫存量隨之減小.且與d1>0情況下的圖5.1相比,平均庫存量E(Q)的值有顯著的下降.

圖5.4 d1=0時E(Q)隨μ的變化曲線

當α=1,β=1.25,μ=15時,圖5.5給出了庫存量尾分布函數P {Q∞>x}的變化趨勢圖.與圖5.3進行對比,可以發現,P {Q∞>x}在x=0處的值明顯更小,這說明流模型庫存量Q(t)有更大的概率處于Q(t)=0,即系統庫存量將更容易清空.

圖5.5 d1=0時P {Q∞>x}隨x的變化曲線

情形三d1<0

當d1<0時,顧客流體到達速率λ小于流模型在部分故障期內緩沖器輸出速率η.

當α=1,β=1.25,λ=2.5時,圖5.6給出了部分故障期內緩沖器輸出速率η分別為3,4,5的情況下平均庫存量E(Q)隨正規忙期內緩沖器輸出速率μ的變化趨勢圖.可以發現,隨著輸出速率μ的增加,平均庫存量隨之減小.且與圖5.1,圖5.4相比,平均庫存量E(Q)的值更小.

圖5.6 d1 <0時E(Q)隨μ和η的變化曲線

表5.2給出了當α=1,β=1.25,λ=2.5,μ=15時庫存量尾分布函數P {Q∞>x}的變化趨勢.仍然可以發現,隨著x的增大,P {Q∞>x}的值隨之減小.同時,在相同的x取值下,η越大,P {Q∞>x}的值越小.

表5.2 d1 <0時P {Q∞>x}隨η與x的變化

由圖5.1-5.6與表5.1-5.2可知,在存在硬件故障的云計算服務系統中,若想減少系統中顧客的排隊現象,降低顧客的平均等待時間,有以下解決方案: 1)提高正規忙期、部分故障期內的服務速率;2) 降低服務器發生故障的頻率,提高服務器無故障工作時間;3) 提高維修效率,降低服務器維修所需要的時間.

6.總結與展望

本文研究了具有兩階段故障的流模型,利用歸一化技術,得到了具有兩階段故障的流模型庫存量尾分布函數的遞推表達式,同時給出了給定誤差限條件下截斷步長的計算方式,并給出了流模型各階矩的表達式.最后將該流模型應用于云計算服務中,利用數值例子分析系統參數對整體系統性能指標的影響.

本文只研究了允許發生兩次故障的流模型,然而考慮到只允許發生兩次故障的系統在現實生產生活中占比較少,在未來的研究中可以考慮具有更多工作狀態的流模型.也可將N-策略、負顧客等其他策略加入流模型中,并考慮如何優化系統才能給社會帶來更多的經濟效益.另一方面,在故障流模型中加入帶寬共享網絡中用戶的延遲因素是未來可行的研究方向.最后,還可以在包級模型和流級模型間嚴格連接方面進行研究.