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

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

張 健**，李 東，葉 通

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

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

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

1 引 言

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

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

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

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

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

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

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

2.1 系統(tǒng)描述

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

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

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

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

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

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

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

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

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

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

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

在本文中，我們定義如下符號(hào)：

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

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

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

用pi,j表示系統(tǒng)穩(wěn)定時(shí)，系統(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)的一個(gè)差分方程：

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

(4)

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

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

(5)

類似地，等式左右兩邊同時(shí)對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)的平均隊(duì)長E[nc]仍然無法求解。

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

3 服務(wù)速率波動(dòng)和時(shí)延的上下界

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

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

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

(8)

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

(9a)

(9b)

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

(10a)

(10b)

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

(11)

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

3.2 時(shí)延上下界

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

(a)μc=0.1

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

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

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

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

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

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

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

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

(12)

上式等價(jià)于

(13)

因此，有

(14)

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

(15)

因此，

(16a)

(16b)

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

(17)

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

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

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

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

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

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

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

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

(18)

因此，系統(tǒng)中志愿者個(gè)數(shù)大于1的概率可以忽略，因此服務(wù)模型可以簡化為一個(gè)兩狀態(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時(shí)系統(tǒng)中任務(wù)個(gè)數(shù)的生成函數(shù)如下：

(19a)

(19b)

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

(20)

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

(21)

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

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

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

ρc<ρs,

(22a)

或者等價(jià)的

(22b)

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

4 結(jié)束語

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

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

后續(xù)工作包括具體求解志愿計(jì)算系統(tǒng)模型的平均隊(duì)長或嘗試得到平均隊(duì)長的一個(gè)近似以及嘗試用文中的方法對其他類似的變速服務(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

張健，李東，葉通.志愿計(jì)算系統(tǒng)時(shí)延分析[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)為碩士研究生，主要研究方向?yàn)榉植际接?jì)算網(wǎng)絡(luò)、排隊(duì)論;

Email：2011aad@sjtu.edu.cn

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

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