志愿計算系統(tǒng)時延分析*

(上海交通大學(xué) 區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實驗室，上海 200240)

志愿計算系統(tǒng)時延分析*

張 健**，李 東，葉 通

(上海交通大學(xué) 區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實驗室，上海 200240)

志愿計算(Volunteer Computing)系統(tǒng)是一種分布式計算系統(tǒng)，它利用全球空閑計算資源實現(xiàn)海量科學(xué)計算。隨著志愿計算的廣泛應(yīng)用，系統(tǒng)時延性能分析變得日益重要。現(xiàn)有文獻(xiàn)主要通過仿真和實驗觀察其時延特性，并不能深入分析系統(tǒng)參數(shù)的影響。為此，提出了一種新的數(shù)學(xué)模型對志愿計算系統(tǒng)時延特性進(jìn)行分析。志愿計算系統(tǒng)可以建模為一個變速率服務(wù)的單服務(wù)臺排隊系統(tǒng)。理論分析表明，系統(tǒng)的平均隊長與服務(wù)速率方差之間存在單調(diào)遞增的關(guān)系。因此，系統(tǒng)在服務(wù)速率方差趨于0和無窮大兩個極端情況下的平均隊長分別為系統(tǒng)平均隊長的下界和上界，而在這兩種極端情況下，可以通過對系統(tǒng)模型的簡化求得系統(tǒng)的平均隊長。仿真結(jié)果驗證了該方法所求平均隊長上下界的正確性和準(zhǔn)確性。

志愿計算；排隊網(wǎng)絡(luò)；時延分析；服務(wù)速率方差；馬爾科夫鏈

1 引 言

近些年，志愿計算(Volunteer Computing，VC)成為學(xué)術(shù)界進(jìn)行科學(xué)計算的一種新方法。全世界的計算和存儲能力不再集中于大型數(shù)據(jù)中心或者超級計算機(jī),相反，它們現(xiàn)在分布于全世界所有的個人電腦之中[1]。志愿計算利用社會大眾個人電腦的空閑計算能力進(jìn)行科學(xué)計算，這種計算方法不僅僅用很低的成本獲得了巨大的計算能力，還為社會大眾了解科技發(fā)展提供了一個途徑，也讓科學(xué)界更加了解社會的實際需求。

志愿計算在20世紀(jì)90年代首次出現(xiàn)[1-2]。1999年，加州大學(xué)伯克利分校的空間科學(xué)實驗室創(chuàng)立了SETI@home項目。這個項目將收集到的電磁信號數(shù)據(jù)分成許多小的工作單元，然后送到世界各地參與該項目的志愿者的電腦上進(jìn)行分析。志愿者的主機(jī)在自己空閑的時間內(nèi)為這個項目做科學(xué)計算的工作。計算任務(wù)完成之后，這些主機(jī)自動把結(jié)果提交回服務(wù)器[3]。SETI@home項目成功之后，加州大學(xué)伯克利分校的空間科學(xué)實驗室開發(fā)了一個開放平臺——BOINC(Berkeley Open Infrastructure for Network Computing)，這個平臺可以讓其他的科學(xué)計算項目更容易使用志愿計算的服務(wù)。到2016年11月，約有15 000 000臺主機(jī)加入了BOINC，其中有1 000 000臺主機(jī)長期保持在線，平臺運(yùn)行項目超過50個[4]。

隨著志愿計算系統(tǒng)的快速發(fā)展，其時延的性能分析也變得越來越重要[5]。一些應(yīng)用如分子動力學(xué)仿真[6]和啟發(fā)式優(yōu)化算法對系統(tǒng)的時延性能非常敏感，另外一些對實時性要求較高的系統(tǒng)，例如在線導(dǎo)航、在線視頻編解碼等應(yīng)用同樣要求對系統(tǒng)的時延性能有很好的估計[7]。針對這些業(yè)務(wù)，已有一些文獻(xiàn)[8-10]在傳統(tǒng)志愿計算系統(tǒng)的基礎(chǔ)上提出了一些新的方法來解決時延較大的問題。目前也有一些分析志愿計算系統(tǒng)時延特性的文獻(xiàn)，但這些文獻(xiàn)主要是用仿真[11-12]和實驗[13-14]進(jìn)行分析，并沒有一個很好的數(shù)學(xué)模型可以描述志愿計算系統(tǒng)的服務(wù)特性。要深入理解志愿計算系統(tǒng)，需要一個完整的數(shù)學(xué)模型。

在志愿計算系統(tǒng)中，每個任務(wù)都是同時被很多志愿者服務(wù)，總的服務(wù)速率取決于系統(tǒng)中工作中的志愿者的個數(shù)。而系統(tǒng)中的志愿者總是隨機(jī)地到達(dá)或離開系統(tǒng)[2，15]，因此，系統(tǒng)的服務(wù)能力是隨時間變化的。即使在一個任務(wù)的服務(wù)過程中，系統(tǒng)的服務(wù)能力也可能經(jīng)歷很多次變化。本文將志愿計算系統(tǒng)建模為一個變速率服務(wù)的單一隊列，這個隊列的服務(wù)器有許多不同的服務(wù)狀態(tài)，每個狀態(tài)有不同的服務(wù)速率，而服務(wù)器在不同時間可能處在不同的狀態(tài)。

這類變速服務(wù)的隊列在數(shù)學(xué)上也是很難處理的，難點(diǎn)在于不同任務(wù)的服務(wù)時間并不是獨(dú)立同分布的，因此傳統(tǒng)的M/G/1隊列的求解方法在這里并不適用。為了解決這個問題，文獻(xiàn)[16]提出了開始服務(wù)概率的概念，但其中提到的開始服務(wù)概率只能在某些特殊情況下求得。文獻(xiàn)[17]求解了一般情況下兩狀態(tài)服務(wù)的開始服務(wù)概率，并給出了兩狀態(tài)服務(wù)的平均時延公式，但需要求解一組線性微分方程，而我們的模型中有無窮多的狀態(tài)，線性微分方程組無法求解。

本文基于系統(tǒng)平均隊長與服務(wù)速率波動之間的聯(lián)系，給出了系統(tǒng)平均隊長的上下界。我們發(fā)現(xiàn)在系統(tǒng)的平均服務(wù)速率固定的情況下，任務(wù)平均服務(wù)時間的均值和方差均與服務(wù)速率方差正相關(guān)。由M/G/1隊列的平均隊長公式(P-K公式)所給出的，系統(tǒng)的平均隊長與任務(wù)服務(wù)時間的一階矩和二階矩正相關(guān)。由此，我們建立起系統(tǒng)平均隊長與服務(wù)速率波動的單調(diào)性關(guān)系。根據(jù)這個關(guān)系，我們考慮系統(tǒng)服務(wù)速率波動的兩個極端狀態(tài)并得到平均隊長的上界和下界：當(dāng)服務(wù)速率的方差趨于0的時候，系統(tǒng)的平均隊長趨于下界；反之，當(dāng)服務(wù)速率的方差趨于無窮的時候，系統(tǒng)的平均隊長趨于上界。

2 志愿計算系統(tǒng)的馬爾可夫模型

2.1 系統(tǒng)描述

志愿計算項目一般都符合如下流程：當(dāng)一個任務(wù)到達(dá)之后，它首先在隊列中等待。當(dāng)它處于隊頭時，就會被分割成許多小的工作單元等待志愿者服務(wù)。志愿者總是隨機(jī)到達(dá)，并且在到達(dá)之后馬上請求需要服務(wù)的工作單元。工作單元的分配服從某種特定的分配策略[2]，而在本文中，我們僅考慮先到先服務(wù)的策略，即只要有志愿者請求工作單元，就立即將一個工作單元發(fā)送給這個志愿者。由于志愿者主機(jī)僅在其空閑時才服務(wù)工作單元，而且志愿者主機(jī)也可能在服務(wù)工作單元的過程中就被關(guān)機(jī)，志愿者接收到工作單元之后也并不能連續(xù)不斷的服務(wù)。但是，數(shù)據(jù)處理程序會周期性地把運(yùn)行結(jié)果寫入文件，并且在重新開始服務(wù)的時候讀取文件。因此，盡管服務(wù)的過程不是連續(xù)不斷的，數(shù)據(jù)處理也能完成[3]。當(dāng)工作單元計算完成之后，志愿者自動將結(jié)果提交回服務(wù)器，并請求下一個服務(wù)單元。

一般來說，志愿計算的項目都是計算密集型的，數(shù)據(jù)處理時間要遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)傳輸?shù)臅r間，因此，在建模分析的過程中，我們忽略了數(shù)據(jù)和結(jié)果傳輸?shù)臅r間。例如：在SETI@home這個項目中，工作單元的大小通常為350 KB，而反饋結(jié)果的大小只有1 KB左右，數(shù)據(jù)傳輸通常幾秒之內(nèi)就可以完成，而這樣一個工作單元需要一個志愿者主機(jī)運(yùn)行一天左右的時間[3]。

綜上所述，在系統(tǒng)建模中，我們做出如下假設(shè)：

(1)任務(wù)的到達(dá)過程是一個參數(shù)為λc的泊松過程；

(2)志愿者的到達(dá)過程是一個參數(shù)為λs的泊松過程；

(3)志愿者的服務(wù)能力都是一致的，均為μc；

(4)志愿者持續(xù)工作的時間是一個服從參數(shù)為μs的負(fù)指數(shù)分布的隨機(jī)變量，志愿者中斷服務(wù)即被認(rèn)為離開系統(tǒng)，當(dāng)其重新開始服務(wù)便被認(rèn)為是一個新的到達(dá)；

(5)志愿者的數(shù)目很大，可以認(rèn)為趨近無窮；

(6)志愿者到達(dá)之后總是有工作單元可以分配。

圖1 志愿者數(shù)量的連續(xù)時間馬爾可夫鏈Fig.1 The continuous-time Markov chain of the server process

在排隊論中，服務(wù)器數(shù)量可變的系統(tǒng)可以看作是一個有可變服務(wù)速率的單一隊列。我們將所有的志愿者視為一個大的服務(wù)器，而它的服務(wù)速率是所有志愿者的服務(wù)速率之和。由于志愿者的到達(dá)和離去都是隨機(jī)的，整個系統(tǒng)的服務(wù)速率是隨時間變化的。系統(tǒng)的服務(wù)速率可以這樣理解：如果在服務(wù)一個任務(wù)的過程中，志愿者的數(shù)量保持不變，那么任務(wù)的服務(wù)時間服從負(fù)指數(shù)分布。但在這個系統(tǒng)中，在服務(wù)一個任務(wù)的過程中，志愿者的數(shù)量是在不斷改變的，因此任務(wù)服務(wù)時間的分布是未知的。而且由于任務(wù)服務(wù)時間之間存在相關(guān)性，排隊論中的肯德爾標(biāo)注(Kendall’s notation)方法已不再適用。

在本文中，我們定義如下符號：

2.2 連續(xù)時間馬爾可夫鏈

根據(jù)之前的系統(tǒng)描述，圖2所示為志愿計算模型的連續(xù)時間馬爾可夫鏈，其狀態(tài)空間為{(i,j),i=0,1,2,…;j=0,1,2,…}，其中i表示系統(tǒng)中任務(wù)的個數(shù)，j表示系統(tǒng)中志愿者的數(shù)量。

圖2 志愿計算系統(tǒng)連續(xù)時間馬爾可夫鏈Fig.2 The continuous-time Markov chain of the VC queueing model

用pi,j表示系統(tǒng)穩(wěn)定時，系統(tǒng)處于狀態(tài)(i,j)的聯(lián)合穩(wěn)態(tài)概率

pi,j=Pr{nc=i,ns=j}。

(1)

式中：i=0,1,…表示系統(tǒng)中任務(wù)的數(shù)量，j=0,1,…表示系統(tǒng)中志愿者的數(shù)量。由圖2所示的狀態(tài)轉(zhuǎn)移圖，可以直接寫出系統(tǒng)的平衡方程如下：

(λc+λs)p0,0=μsp0,1,i=0,j=0；

(2a)

(λc+λs)pi,0=λcpi-1,0+μspi,1,i≥1,j=0；

(2b)

(λc+λs+jμs)p0,j=λsp0,j-1+(j+1)μsp0,j+1+jμcp1,j,
i=0,j≥1；

(2c)

(λc+λs+jμs+jμc)pi,j=λspi,j-1+λcpi-1,j+(j+1)μspi,j+1+jμcpi+1,j,i≥1,j≥1。

(2d)

定義pi,j的生成函數(shù)為

(3)

根據(jù)公式(2)的平衡方程，可以直接推導(dǎo)出關(guān)于生成函數(shù)F(z1,z2)的一個差分方程：

(λc-z1λc+λs-z2λs)F(z1,z2)=

(4)

目前，我們無法通過這個差分方程得到F(z1,z2)的表達(dá)式，從而確定系統(tǒng)的平均隊長。我們僅能從這個差分方程中得到一些方便后續(xù)處理的公式。

首先，等式(4)左右兩邊同時對z1求導(dǎo)并代入z1=z2=1，可以得到

(5)

類似地，等式左右兩邊同時對z1求二階導(dǎo)并代入z1=z2=1，可以得到

(6)

由公式(5)和(6)可得

ρcE[nc]=E[nsnc]-ρc。

(7)

這里，由于系統(tǒng)中任務(wù)的數(shù)量與志愿者的數(shù)量是相關(guān)的，即無法求得E[nsnc]，因此系統(tǒng)的平均隊長E[nc]仍然無法求解。

得到式(7)，說明傳統(tǒng)的排隊論求解方法在求解這個問題的過程中需要知道任務(wù)的數(shù)量與志愿者數(shù)量的相關(guān)性，而這正是問題的困難之處。因此，我們只能嘗試從其他的角度求解該排隊模型。

3 服務(wù)速率波動和時延的上下界

對于志愿計算系統(tǒng)的排隊模型，求解系統(tǒng)平均隊長的難點(diǎn)在于任務(wù)服務(wù)時間的分布是未知的，而且任務(wù)的服務(wù)時間之間存在相關(guān)性。我們已知的信息只有在系統(tǒng)穩(wěn)態(tài)下志愿者數(shù)目的分布是泊松分布，因此在本節(jié)中，我們首先探究服務(wù)速率的波動與系統(tǒng)平均隊長之間的關(guān)系，然后據(jù)此得到系統(tǒng)平均隊長的上界和下界。

3.1 服務(wù)速率波動的影響

直觀上來看，服務(wù)速率的波動越大，服務(wù)時間的均值和方差都會越大。事實上，如果固定平均服務(wù)速率不變，服務(wù)時間的均值和方差隨服務(wù)速率的方差增大而增大，本節(jié)將說明這個性質(zhì)成立。

(8)

那么g(μ)的均值和方差可以近似表示為

(9a)

(9b)

因此，服務(wù)時間的均值和方差S=g(μ)=1/μ近似表示為

(10a)

(10b)

對于一個到達(dá)速率為常量的排隊系統(tǒng)，系統(tǒng)的平均隊長與服務(wù)時間的均值和方差成正相關(guān)。M/G/1排隊模型的平均隊長公式——P-K公式闡述的就是這一性質(zhì)[18]：

(11)

但P-K公式的成立，要求每個任務(wù)的服務(wù)時間是獨(dú)立同分布的隨機(jī)變量，而這個條件在志愿計算的模型中并不成立。因此，如果簡單地將上面推導(dǎo)出的服務(wù)時間均值和方差的近似直接代入P-K公式，結(jié)果與真實情況會相差很大。盡管通過上述分析沒有得到志愿計算模型的平均隊長，但得到的單調(diào)性關(guān)系可以幫助我們得到平均隊長的上界和下界。

3.2 時延上下界

我們知道系統(tǒng)中志愿者的個數(shù)ns是一個服從均值為ρs的泊松分布的隨機(jī)變量，因此可以得到如下參數(shù)的表達(dá)式：

(a)μc=0.1

(b)μc=1圖3 系統(tǒng)服務(wù)速率隨時間波動 (μc/μs=10,λs=10)Fig.3 The fluctuation of service rate μ

直觀來講，μc和μs較大意味著每一個志愿者的服務(wù)速率都比較大而系統(tǒng)中存在的志愿者個數(shù)比較少。在這種情況下，每一個志愿者的到達(dá)或者離去都將使系統(tǒng)的服務(wù)速率發(fā)生較大的變化；反之則每一個志愿者的服務(wù)速率都比較小，那么志愿者的到達(dá)和離去對服務(wù)速率的影響就比較小，這樣系統(tǒng)的服務(wù)速率就更加穩(wěn)定。

當(dāng)保持μc與μs的比值和λs不變時，系統(tǒng)的平均隊長將隨著服務(wù)速率波動的增大而增大。因此，我們分析兩種極端情況：當(dāng)μc→0時，系統(tǒng)將達(dá)到平均隊長的下界；當(dāng)μc→時，系統(tǒng)將達(dá)到平均隊長的上界。

當(dāng)固定保持μc與μs的比值和λs不變時，系統(tǒng)的平均服務(wù)速率保持不變，在這種情況下，當(dāng)μc→0時，系統(tǒng)應(yīng)表現(xiàn)出如下服務(wù)行為：

由于ρs→，系統(tǒng)中志愿者的個數(shù)較多；

由于μs→0，每個志愿者連續(xù)服務(wù)的時間較長；

由于μc→0，每一個志愿者的服務(wù)能力都比較小。

圖4 系統(tǒng)處于平衡態(tài)時系統(tǒng)的服務(wù)速率近似于常量Fig.4 Service rate becomes a constant when system reaches equilibrium

(12)

上式等價于

(13)

因此，有

(14)

系統(tǒng)穩(wěn)定時，系統(tǒng)的平均隊長總是有限的，因此當(dāng)ε→0時，有

(15)

因此，

(16a)

(16b)

由等式(7)和(16b)可得，此時的系統(tǒng)的平均隊長，也即系統(tǒng)平均隊長的下界為

(17)

當(dāng)固定μc與μs的比值和λs不變時，系統(tǒng)的平均服務(wù)速率保持不變，在這種情況下，當(dāng)μc→時，系統(tǒng)應(yīng)表現(xiàn)出如下服務(wù)行為：

由于ρs→0 ，系統(tǒng)中志愿者的個數(shù)較少；

由于μs→，每個志愿者連續(xù)服務(wù)的時間較短；

由于μc→，每一個志愿者的服務(wù)能力都比較大。

圖5描述了這種情況下系統(tǒng)中的志愿者行為。由于每個志愿者連續(xù)服務(wù)的時間很短，系統(tǒng)中存在兩個或兩個以上志愿者同時服務(wù)的概率很小，系統(tǒng)可以近似等價于僅有一個志愿者，而它有時在服務(wù)，有時不在服務(wù)。

圖5 服務(wù)速率在極端情況下只有兩個狀態(tài)Fig.5 The two-state extreme scenario of VC systems

由于系統(tǒng)中僅有的志愿者都有很大的服務(wù)速率，系統(tǒng)仍能保證穩(wěn)定的運(yùn)行。從數(shù)學(xué)及角度來講，因為系統(tǒng)中志愿者的個數(shù)服從泊松分布，在極端情況ρs→0的情況下，系統(tǒng)中志愿者個數(shù)在2個或2個以上的概率為

Pr{ns≥2}=o(ρs2)→0。

(18)

因此，系統(tǒng)中志愿者個數(shù)大于1的概率可以忽略，因此服務(wù)模型可以簡化為一個兩狀態(tài)的服務(wù)。圖1所示的馬爾可夫鏈也就簡化為圖6所示形式。

圖6 兩狀態(tài)服務(wù)系統(tǒng)的狀態(tài)跳轉(zhuǎn)Fig.6 The transition diagram of the two service states

對于兩狀態(tài)變速服務(wù)的系統(tǒng)，很多文獻(xiàn)都有詳細(xì)的分析，例如文獻(xiàn)[17，19]。文獻(xiàn)[17]給出了系統(tǒng)處在狀態(tài)0和狀態(tài)1時系統(tǒng)中任務(wù)個數(shù)的生成函數(shù)如下：

(19a)

(19b)

此時系統(tǒng)的平均隊長，也即志愿計算模型的平均隊長的上界L2可以通過如下方式得到：

(20)

對式(19)求導(dǎo)并代入z=1，再取μc,μs→的極限即可得到平均隊長的上界

(21)

至此，已經(jīng)得到平均隊長的上界和下界。我們同樣用離散事件仿真驗證了這個上界和下界的正確性和準(zhǔn)確性。固定μc/μs=10和λs=10，任務(wù)到達(dá)速率λc在10～90中取值。圖7中下界和上界分別是公式(17)和(21)的計算結(jié)果，其余曲線為仿真結(jié)果。仿真結(jié)果表明，系統(tǒng)的平均隊長隨μc值的增大而增大，當(dāng)μc→時，系統(tǒng)平均隊長趨近于上界L2；而當(dāng)μc→0時，系統(tǒng)平均隊長趨于下界L1。

圖7 系統(tǒng)平均隊長L1≤L≤L2Fig.7 Mean queue length L is bounded by L1 and L2

從系統(tǒng)平均隊長的上界和下界中也可以得出系統(tǒng)穩(wěn)定的條件為

ρc<ρs,

(22a)

或者等價的

(22b)

這個條件保證了系統(tǒng)平均隊長的上界和下界均是正值且有限。同時，這個結(jié)論也符合我們對系統(tǒng)的直觀認(rèn)識，只要系統(tǒng)的平均到達(dá)速率小于系統(tǒng)的平均服務(wù)速率，無論系統(tǒng)的服務(wù)速率如何波動，系統(tǒng)總能保證是穩(wěn)定的。

4 結(jié)束語

本文對志愿計算系統(tǒng)建立了二維馬爾可夫模型，在這個模型中，系統(tǒng)的任務(wù)和服務(wù)器均隨機(jī)到達(dá)和離開。然而，這個系統(tǒng)在數(shù)學(xué)上是無法得出平均隊長的表達(dá)式的。受M/G/1隊列的平均隊長表達(dá)式P-K公式的啟發(fā)，我們建立起系統(tǒng)的平均隊長與系統(tǒng)服務(wù)速率波動之間的關(guān)系，并在極端情況下得到了系統(tǒng)平均隊長的上界和下界。

目前，隨著計算機(jī)系統(tǒng)越來越復(fù)雜，用可變速率服務(wù)的系統(tǒng)對實際網(wǎng)絡(luò)應(yīng)用的建模變得越來越困難。除了一些很簡單的模型之外，大部分可變速率服務(wù)的系統(tǒng)在數(shù)學(xué)上都是無法求解的。因此，我們的方法可能會給以后求解這類問題提供一個新的方法，雖然無法得到平均隊長的表達(dá)式，但可以很直觀地給出一個平均隊長的估計。也希望我們的方法將能在如云計算和節(jié)能以太網(wǎng)等其他領(lǐng)域的建模中有所應(yīng)用。

后續(xù)工作包括具體求解志愿計算系統(tǒng)模型的平均隊長或嘗試得到平均隊長的一個近似以及嘗試用文中的方法對其他類似的變速服務(wù)系統(tǒng)進(jìn)行分析。

[1] ANDERSON D P. Boinc:a system for public-resource computing and storage[C]//Proceedings of Fifth IEEE/ACM International Workshop on Grid Computing.Pittsburgh,PA,USA:IEEE,2004:4-10.

[2] DURRANI M N,SHAMSI J A. Volunteer computing:requirements,challenges,and solutions[J].Journal of Network and Computer Applications,2014,39(1):369-380.

[3] ANDERSON D P,COBB J,KORPELA E,et al.SETI@ home:an experiment in public-resource computing[J].Communications of the ACM,2002,45(11):56-61.

[4] WILLY D Z. BOINCstats[EB/OL]. (2014-07-15)[2017-04-15].http://boincstats.com.

[5] ESTRADA T,TAUFER M,REED K. Modeling job lifespan delays in volunteer computing projects[C]//Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid.Shanghai:IEEE,2009:331-338.

[6] VIJAY P.Folding@home[EB/OL]. (2000-09-19)[2017-04-15].http://folding.stanford.edu/.

[7] YI S,JEANNOT E,KONDO D,et al.Towards real-time,volunteer distributed computing[C]//Proceedings of the 2011 11th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.Newport Beach,CA,USA:IEEE,2011:154-163.

[8] BRUNO R,FERREIRA P. FreeCycles:efficient data distribution for volunteer computing[C]//Proceedings of the Fourth International Workshop on Cloud Data and Platforms. New York:ACM,2014:1-6.

[9] TARIGAN J T,JAYA I,HARDI S M. Distributed Rendering on Volunteered Mobile Resources[C]//Proceedings of the 5th International Conference on Communications and Broadband Networking.Bali Island,Indonesia:ACM,2017:25-29.

[10] HEIEN E M,FUJIMOTO N,HAGIHARA K. Computing low latency batches with unreliable workers in volunteer computing environments[C]//Proceedings of 2008 IEEE International Symposium on Parallel and Distributed Processing.Miami,FL,USA:IEEE,2008:1-8.

[11] ESTRADA T,TAUFER M,ANDERSON D P. Performance prediction and analysis of BOINC projects:an empirical study with EmBOINC[J].Journal of Grid Computing,2009,7(4):537-554.

[12] MONSALVE S A,CARBALLEIRA F G,MATEOS A C. Analyzing the performance of volunteer computing for data intensive applications[C]//Proceedings of 2016 International Conference on High Performance Computing & Simulation (HPCS).Innsbruck,Austria:IEEE,2016:597-604.

[13] GULLAPALLI S. Atlas:an intelligent,performant framework for web-based grid computing[C]//Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering.Seattle,WA,USA:ACM,2016:1154-1156.

[14] DURRANI M N,IQBAL T,SHAMSI J A,et al.Towards real-time result verification using checkpointing in volunteer computing systems[C]//Proceedings of 2015 IEEE 18th International Symposium on Real-Time Distributed Computing (ISORC).Auckland,New Zealand:IEEE,2015:218-227.

[15] JAVADI B,KONDO D,VINCENT J M,et al.Discovering statistical models of availability in large distributed systems:an empirical study of seti@home[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1896-1903.

[16] MAHABHASHYAM S R,GAUTAM N. On queues with Markov modulated service rates[J].Queueing Systems,2005,51(1):89-113.

[17] HUANG L,LEE T T. Generalized pollaczek-khinchin formula for markov channels[J].IEEE Transactions on Communications,2013,61(8):3530-3540.

[18] KLEINROCK L.Computer applications[M]//Queueing systems:volume 1. New York:Wiley,1975:167-240.

[19] GUNASEELAN N,LIU L,CHAMBERLAND J F,et al.Performance analysis of wireless hybrid-ARQ systems with delay-sensitive traffic[J].IEEE Transactions on Communications,2010,58(4):1262-1272.

DelayAnalysisofVolunteerComputingSystems

ZHANG Jian,LI Dong,YE Tong

(State Key Laboratory of Advanced Optical Communication Systems and Networks, Shanghai Jiaotong University,Shanghai 200240,China)

Volunteer computing (VC) is a distributed computing system which uses spare computing power from general public to do scientific computing. With the rapid growth of volunteer computing,delay performance evaluation becomes more and more important. In existing literatures,delay performance of VC system is majorly observed by simulations and experiments,through which the influence of system parameters cannot be deeply analyzed. Therefore,a new model is proposed to analyze the delay performance of VC system. The VC system can be modeled as a single server queue with variable service rate. Analytical results show that the mean queue length increases with the fluctuation of service rate. Therefore,the mean queue length under two extreme cases,variance of service rate approaches to 0 and infinity,should be the lower bound and upper bound respectively. And the mean queue length under the two extreme cases can be obtained by the simplified system model. Simulation result validates that the two queue length bounds are both valid and accurate.

volunteer computing;queueing network;delay analysis;fluctuation of service rate;Markov chain

10.3969/j.issn.1001-893x.2017.12.002

張健，李東，葉通.志愿計算系統(tǒng)時延分析[J].電訊技術(shù)，2017,57(12):1356-1362.[ZHANG Jian,LI Dong,YE Tong.Delay analysis of volunteer computing systems[J].Telecommunication Engineering,2017,57(12):1356-1362.]

2017-05-04；

2017-07-11

date:2017-05-04；Revised date：2017-07-11

2011aad@sjtu.edu.cnCorrespondingauthor2011aad@sjtu.edu.cn

TN919

A

1001-893X(2017)12-1356-07

張健(1992—)，男，內(nèi)蒙古包頭人，2015年于上海交通大學(xué)獲學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為分布式計算網(wǎng)絡(luò)、排隊論;

Email：2011aad@sjtu.edu.cn

李東( 1948—) ，男，中國臺灣臺北人，分別于1976年和1977年獲紐約理工大學(xué)碩士學(xué)位和博士學(xué)位，1977～1983年于美國AT&T貝爾實驗室工作，1983～1993年在Bellcore (現(xiàn)為Telcordia Technologies)工作，1991～1993 年于紐約理工大學(xué)任教授，1993～2010年于香港中文大學(xué)任講席教授，現(xiàn)為上海交通大學(xué)致遠(yuǎn)講席教授、IEEE Fellow、HKIE Fellow，主要研究方向為寬帶交換理論、網(wǎng)絡(luò)性能分析、無線通信網(wǎng)絡(luò)；

葉通( 1976—) ，男，福建浦城人，分別于1998 年和2001年獲電子科技大學(xué)學(xué)士學(xué)位和碩士學(xué)位，2005年于上海交通大學(xué)獲博士學(xué)位，現(xiàn)為上海交通大學(xué)副教授，主要研究方向為寬帶交換網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)算法設(shè)計和性能分析和光網(wǎng)絡(luò)系統(tǒng)。