為網(wǎng)格計算的可靠工作選擇機器

1、為網(wǎng)格計算的可靠工作選擇機器o credible worker selection mechanism for grid computing摘要摘要o 隨著網(wǎng)絡的高速發(fā)展，網(wǎng)格計算的概念開始浮現(xiàn)。有效的網(wǎng)格工人選擇機制是對有效網(wǎng)格計算非常重要的，因為每個網(wǎng)格里面的工作者都是不同種類的。在本文中，我們提出了選擇可靠的機器工作者的方法最大化網(wǎng)格計算，是利用合理的為每個計算者分配任務。不同的工人能夠被網(wǎng)格計算軟件有效的利用，通過工人可信度的過程隊列。一開始，網(wǎng)格中工人的可信度只由一些靜態(tài)的參數(shù)決定，例如cpu的速度，內存大小，存儲能力和網(wǎng)絡帶寬。后來，隊列被動態(tài)信息優(yōu)化，例如失敗率，任務完成后時間提

2、供，和正確的返回值。在試驗中，我們發(fā)現(xiàn)我們所提出的機制能夠提高網(wǎng)格計算效率和高可信度。1緒論緒論o應用軟件程序要求大規(guī)模計算和高資源能力這幾年發(fā)展得很快，隨后出現(xiàn)了一個思想就是利用地理區(qū)域分散的數(shù)量龐大的計算機去完成這些任務。隨著網(wǎng)格中間設備，高速連接地理上分散計算機，已經(jīng)被發(fā)展了?；诰W(wǎng)格概念的使用工具已經(jīng)成為可能。典型的網(wǎng)格計算中間件是globus toolkit，為了解決網(wǎng)格計算中的巨大問題，網(wǎng)格工人發(fā)現(xiàn)空閑的資源，網(wǎng)格表為每個網(wǎng)格工人分配任務，網(wǎng)格安全器負責系統(tǒng)的穩(wěn)定，網(wǎng)格使用者計算所需要使用的必要的資源。o由于實際中的原因，包括工人失敗，新工人注冊，在網(wǎng)格計算中的共存的執(zhí)行工人，網(wǎng)格

3、工人的不斷變化，所以，有效的網(wǎng)格工人選擇機制對完成可靠的網(wǎng)格計算系統(tǒng)是非常重要的因為每個參與網(wǎng)格計算的工人都是不同的。這個選擇機制就是一種各種形式的適當?shù)木W(wǎng)格工人的任務匹配的方法。首先，很多網(wǎng)格工人被只用靜態(tài)的信息連接起來，例如硬件能力，隊列，然后用適當?shù)娜蝿掌ヅ?。第二，每個工人的最初結果被用來更新工人隊列，然后去適合將來所要分配的任務。任務安排表算法必須是能夠被擴展的，然后能夠有效的處理個種類型的網(wǎng)格計算系統(tǒng)的動態(tài)學錯誤。在本文中，一個機制估計得到結果要多少時間，從信息中傳遞任務的達到，用心跳信號檢測存活的網(wǎng)格工人被發(fā)展了。2相關工作相關工作o 反向向導主工人結構用歷史信息關于每個網(wǎng)格工人的

4、活動信息被提出。結構的完全工人和遞送信息在網(wǎng)格計算系統(tǒng)中是很有效的。每個主人分配任務考慮到每個工人隊列或者任務特點，不斷更新工人隊列考慮的信息動態(tài)，然后用再次使用他們?yōu)閷砣蝿兆鰷蕚洹 在本文中，有效地處理每個工人的可信度，我們提出一個新的分等級的工人結構，如圖1所示，利用投票和抽樣算法，這2個是一種分組機制用來測量結果的正確性，是在同時間間隔中測量結果的正確性和任務分配之后 o為了避免喚醒工人的壞的信息，這個方法要求返回的正確的結果，需要每個工人都返回正確的結果，這是必須的。一般的做法是使用容錯技術增加正確性，用奇偶校驗或者校驗和算法，但是我們用投票和點校驗策略因為前者是故意攻擊的一個弱點

5、。然而，先前的投票和點校驗算法被用來區(qū)分有錯誤的工人，只有當工人的表現(xiàn)有壞的信息的時候。網(wǎng)格計算系統(tǒng)出現(xiàn)錯誤的可能性是一般發(fā)生在特定組合里面的任務分配，判斷每個工人的返回值的正確性。o有一個算法，是要求任務完成的時間的，它是隨機分配任務去每個網(wǎng)格工人評估。然而，因為所請求的資源有限，很多時候是不能很好匹配的。同時，它還有一個缺點，這個缺點是不能夠計算工人們最好的負荷量因為它有不同標準的混合結構，同時安排表只允許round-robin方法。有一個智能算法，叫螞蟻算法，它利用歷史信息分配計算資源，這個資源叫做信息素。信息素被表示為歷史信息，是一個中間匹配資源的中間值，它是利用先前資源收集和傳遞的信

6、息。然而，正確或錯誤的任務結果的判斷機制是不能用的，而且只考慮更新信息素的正確性，排除動態(tài)元素，例如失敗率和翻轉時間。o在本文中，我們設計一個可靠的工人選擇機制使網(wǎng)格計算表現(xiàn)最大化，用合理的任務分配機制。換一句話說，這個提出的機制考慮隊列中的每個網(wǎng)格工人的可信度基于靜態(tài)和動態(tài)信息的歷史信息素。首先，網(wǎng)格工人的可靠度只依靠一些靜態(tài)信息，例如cpu頻率，內存大小，存儲能力和網(wǎng)絡帶寬。然后，隊列被動態(tài)因素更新，例如失敗率，任務完成后的翻轉時間。3網(wǎng)格計算體系結構網(wǎng)格計算體系結構o 我們才用分等級的主控工人結構，這個比以前的結構先進的結構。圖1顯示了主控和工人間的關系。主控只能分辨比它下一級的工人任務

7、分配給第一級的工人和整合工人收集上來的結果，這些工人是完成任務的工人。工人能夠成為擴展后的主控。假定一個任務能夠被分成許多小的部分，每個節(jié)點作為一個工人一旦傳遞任務就是給它下一級的工人。 3.1工人注冊和可信隊列管理o 一個網(wǎng)絡中愿意加入網(wǎng)格計算的候選的工人由注冊過程連接到主控機（如圖2所示）。工人必須記錄它自己的靜態(tài)信息連接給主控機。主控機利用被控機的注冊信息。主控機用基于排列輸出量分配相同的任務，和從正確的結果中刷新工人的可信度。最后，主控機按照隊列的可信度為每個工人分配任務。當相同組的工人分配到任務以后，給予網(wǎng)格計算輸出的很小的時間變化增加了。因此，全部網(wǎng)格工人的利用率增加了。o 圖3顯

8、示了由主控節(jié)點和它的任務管理，資源管理，資源池和數(shù)據(jù)庫的組成。o 3.2 工人的靜態(tài)信息o 當每個工人想被注冊到網(wǎng)格計算系統(tǒng)中時，我們要提供他們自己本身的系統(tǒng)信息給主控機。表1顯示了組中工人的靜態(tài)信息，這些是工人計算時的表現(xiàn)和計算資源更新的后的刷新。每個組中的工人由等式1表示。當一個工人在群中時，它能夠被下一級工人用元素k表示。o 每個工人可能的5種狀態(tài)由圖4表示出來，o 第i組中第j個工人的cpu，內存，存儲和網(wǎng)絡帶寬信息用下面的等式2表示。o 只利用這些靜態(tài)信息的話，我們能夠決定網(wǎng)格計算系統(tǒng)中先前一個工人在網(wǎng)格問題中的特征。例如，計算導向網(wǎng)格任務把cpu速度放在更高的位置上，和數(shù)據(jù)精度網(wǎng)格

9、任務把存儲能力放在更重要位置。為了表現(xiàn)以上的情況，我們用等式3定義在第i組中的第j個工人.3.3 一個工人的動態(tài)信息（dynamic information）o 工人的動態(tài)信息被用來測量結果可信度和現(xiàn)場校驗算法和歷史信息，例如失敗率far，翻轉時間tat，和正確率crt，用等式4表示。o 平均翻轉時間atat和atat的標準背離用等式5和等式6表示反應時間的小變化網(wǎng)格計算結果的可能性由等式6表示。也就是說，工人組中最小標準背離是最適合聯(lián)合完成任務。3.3 失敗率o 失敗率是工人在計算過程中可能產生的錯誤。我們提出的這個機制利用心跳機制去辨認工人的失敗率，和決定失敗率因素由圖5表示。o 任務管理

10、工具分配為每個任務分配資源然后等待結果。這個結果被適用于基于工人的點工作的暫停，工人是第一個給結果的工人，和給同組工人發(fā)送心跳。如果其他工人對確定時間間隔內心跳沒有回應，那么就認為工人錯誤了。等式7表示了第i組第j個工人刷新了它先前的失敗率的信息。3.3.2翻轉時間o 反轉時間是消逝時間的持續(xù)時間的結果從一個工人到另外一個工人后開始它的工作的時間。為了獲得精確的時間，網(wǎng)絡延遲也要考慮到。圖6顯示了翻轉時間模型和它的計算方法用等式8給出3.3.3正確性o 工人的正確性是由在相同組完成同一個任務之后比較返回值決定。由等式9給出3.4工人可信度o 工人的動態(tài)信息是由基于失敗率，翻轉時間，和等式10中

11、的每個工人的正確性計算的。o 最后，工人的可信度由等式11定義o 可信性是由最初的靜態(tài)和動態(tài)信息和以后的工人不斷更新增加任務所得到的結果的隊列計算出的。在等式12中，新的可信性是由分解舊的總和可信度和完成所有分配任務的可信性獲得。o 圖7是全部網(wǎng)格結構開始由任務接受者插入任務過程開始，為每個工人分配任務，確認結果，和產生隊列和用結果重新排列工人隊列。4 執(zhí)行評估執(zhí)行評估o 表2是每個工人的靜態(tài)信息和被使用的最初分組。o pri信息是由定義的所有權重計算的。表3是一個動態(tài)信息的例子（參照等式10中的i/o流）利用上面提到的靜態(tài)。每個權值設定為： 自從i/o流比far和crt大受網(wǎng)絡條件影響之后，

12、所以tat就故意設成2倍大小。表4顯示了工人隊列考慮了全部的動態(tài)和靜態(tài)信息。o 首先，觀測lan環(huán)境中的i/o流，和表4中第3組工人排除他們不屬于同一個組因素。圖8是估計i/o流時間在不同大小從100到600兆用5個工人有5到9個隊列的不同可信度。文件i/o流時間對系統(tǒng)可信度并沒有太大的影響。沒有太大的背離當分配任務給每個同組工人之后。反而，低容量的工人需要的時間更短?？紤]到接受和發(fā)送的網(wǎng)絡條件，狀態(tài)正確性比系統(tǒng)容量更好。o 圖9顯示了可信度的反應時間和工人數(shù)量。o 當有一定數(shù)量的參與者參與到網(wǎng)格計算系統(tǒng)和可信度提高時，有可能縮短反應時間。這個結果暗示有很多工人的投票，失敗率下降和返回值的正確

13、性增加。很難合適目標正確率在任務大小和工人系統(tǒng)能力之間在分配任務給獲得好的回應時間，但是匹配資源用最好的能力給最大任務將能夠成為最合適的匹配標準。o 失敗率的影響對反應時間由圖10給出。o 反應時間的在圖中的變化依照不同的失敗率和園羅賓算法（round-robin）。這里，失敗率給出了工人匹配任務的正確性，10%的失敗率意思是能夠正確匹配到工人的任務是90%。當失敗率到30%的時候，它顯示了更好的表現(xiàn)，比匹配工人用園羅賓算法，和縮短反應時間是獲得當更小失敗率的時候?？紤]可信信息例如失敗率，最少比2倍于有效反應時間表現(xiàn)能夠被達到，盡管接受失敗率只有10%。o 圖11顯示了正確性依照失敗率和同組工

14、人數(shù)量。o 它利用投票算法，和度量正確性在假設大量工人返回同一個值的情況下。例如，有一個組有3個工人，失敗率是40%，那么有可能得到正確結果的可能性是60%。因此，增加更多工人和降低失敗率，能夠增加正確性。o 圖12是一個表顯示監(jiān)視圈t依照高架m和系統(tǒng)可能改變能力p，它表示了最好的t假設，這個是m是由監(jiān)視系統(tǒng)m發(fā)生能力改變和p是信息可能改變，在工作過程t中?？赡苄愿蟮墓と诵畔⒏淖儼l(fā)生，一個更短的得到正確工人信息的圈。所以工人的正確性能夠被t增加。o 在圖13中，deadline sort and first-come first-serverd算法被考慮來比較網(wǎng)格計算系統(tǒng)的表現(xiàn)用我們提出的機制。o 在這次試驗中，我們采用試驗參數(shù)。任務相應時間從5到11秒被平均使用，和給出5個不同的先決條件。工人們被分為31組依照任務的不同性和每組由3個工人組成。這個反應時間被評估作