以混合式負(fù)載平衡策略提升三階課件

1、以混合式負(fù)載平衡策略提昇三階層式點(diǎn)對(duì)點(diǎn)網(wǎng)路拓樸之執(zhí)行效能報(bào)告人：張俊盛朝陽科技大學(xué)嚴(yán)國(guó)慶 王淑卿 陳秀芳 王順生以混合式負(fù)載平衡策略提昇三階層式點(diǎn)對(duì)點(diǎn)網(wǎng)路拓樸之執(zhí)行效能報(bào)內(nèi)容大綱摘要前言文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)排程演算法LBMM排程演算法研究方法與流程子管理者門檻值的設(shè)定可利用的資源節(jié)點(diǎn)門檻值的設(shè)定研究假設(shè)與實(shí)例結(jié)論與未來工作內(nèi)容大綱摘要摘要由於科技的進(jìn)步及網(wǎng)路的普及，使得點(diǎn)對(duì)點(diǎn)計(jì)算逐漸成為分散式應(yīng)用的主流。但由於點(diǎn)對(duì)點(diǎn)計(jì)算主要是透過分散的節(jié)點(diǎn)合作完成一個(gè)大型的工作，因此如何將工作有效的分配到每一個(gè)節(jié)點(diǎn)上，使系統(tǒng)中每個(gè)節(jié)點(diǎn)的工作達(dá)成負(fù)載平衡，是一個(gè)值得探討的議題。在一個(gè)三階層式點(diǎn)對(duì)點(diǎn)網(wǎng)路拓樸架構(gòu)下

2、，提出混合式負(fù)載平衡排程演算法以進(jìn)行工作的配置，透過門檻值的設(shè)定，使得每個(gè)需要執(zhí)行的工作能快速的被分配到適當(dāng)?shù)墓?jié)點(diǎn)上，除有效的改善每個(gè)節(jié)點(diǎn)的工作負(fù)擔(dān)外，還可依據(jù)工作的特性來選擇最合適的節(jié)點(diǎn)，提供三階層式點(diǎn)對(duì)點(diǎn)網(wǎng)路拓樸之負(fù)載平衡與執(zhí)行效率的品質(zhì)保證。摘要由於科技的進(jìn)步及網(wǎng)路的普及，使得點(diǎn)對(duì)點(diǎn)計(jì)算逐漸成為分散式前言分散式系統(tǒng)概略可以分為主從式系統(tǒng)與點(diǎn)對(duì)點(diǎn)計(jì)算兩類。主從式系統(tǒng)的架構(gòu)是一種集中式的管理方式，架構(gòu)中以伺服器為中心，提供各類資訊內(nèi)容、電子郵件及資訊搜尋等服務(wù)。然而主從式架構(gòu)最大的缺點(diǎn)是伺服器一旦發(fā)生故障，則整個(gè)主從式系統(tǒng)可能發(fā)生故障或癱瘓。點(diǎn)對(duì)點(diǎn)計(jì)算因?yàn)橘Y源是分佈在每個(gè)節(jié)點(diǎn)上，所以可以運(yùn)用

3、每個(gè)節(jié)點(diǎn)的一些資源協(xié)同合作完成一個(gè)大的工作。但是如何運(yùn)用點(diǎn)對(duì)點(diǎn)計(jì)算的優(yōu)點(diǎn)，讓需要運(yùn)算的工作能在最短的時(shí)間內(nèi)分配到最適當(dāng)?shù)馁Y源則是一重要議題。前言分散式系統(tǒng)概略可以分為主從式系統(tǒng)與點(diǎn)對(duì)點(diǎn)計(jì)算兩類。文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)在網(wǎng)路架構(gòu)中，每臺(tái)電腦(節(jié)點(diǎn))連結(jié)的方式，即所連結(jié)的形狀稱之為拓樸，這些拓樸可以依據(jù)節(jié)點(diǎn)排列的形狀而加以分類。目前應(yīng)用在點(diǎn)對(duì)點(diǎn)計(jì)算架構(gòu)的網(wǎng)路拓樸，可區(qū)分為星狀拓樸、環(huán)狀拓樸與階層式拓樸。文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)在網(wǎng)路架構(gòu)中，每臺(tái)電腦(節(jié)點(diǎn))連結(jié)的方文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)星狀拓樸這種架構(gòu)的應(yīng)用方式是將所有的資料都集中存放在只有單一的中央伺服端中，並提供給很多的客戶端直接連接，以取得所需要的資

4、料。在點(diǎn)對(duì)點(diǎn)計(jì)算架構(gòu)中，可使用這種星狀拓樸的服務(wù)型態(tài)，提供很多的客戶端搜尋資料。在點(diǎn)對(duì)點(diǎn)系統(tǒng)架構(gòu)中，伺服端只提供很多的客戶端做資料的搜尋，並沒有提供客戶端直接在伺服端做資料的存取。文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)星狀拓樸文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)環(huán)狀拓樸由於星狀拓樸的服務(wù)方式只有一臺(tái)伺服端的設(shè)備，因此可以服務(wù)客戶端的數(shù)量有限。為解決星狀拓樸所產(chǎn)生之問題，因此將多個(gè)伺服器連結(jié)起來，形成一個(gè)環(huán)狀拓樸。為了防止單一鏈結(jié)的環(huán)狀拓樸中會(huì)發(fā)生連結(jié)斷裂，因此在每個(gè)節(jié)點(diǎn)中另外建立一條備份連結(jié)(Backup link)，形成多連結(jié)(Muti-ring)的環(huán)狀拓樸，使訊息傳送封包遺失率相對(duì)較低。當(dāng)環(huán)狀拓樸節(jié)點(diǎn)需要搜尋資訊時(shí)，如果環(huán)

5、狀網(wǎng)路拓樸的節(jié)點(diǎn)數(shù)非常多時(shí)，可能造成繞送時(shí)間過久，影響搜尋的效能。文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)環(huán)狀拓樸文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)階層式拓樸階層式系統(tǒng)的使用已有很長(zhǎng)的一段歷史， 如領(lǐng)域名稱伺服器(Domain Name Server；DNS)所形成的拓樸，就是採用階層式的網(wǎng)路架構(gòu)。階層式拓樸(Hierarchical Topology)的形成方式，主要會(huì)有一個(gè)名稱伺服器(Root name sever)來負(fù)責(zé)驗(yàn)證的機(jī)制，每個(gè)下層節(jié)點(diǎn)都需要上層節(jié)點(diǎn)的驗(yàn)證許可，依照這樣的方式形成樹狀的拓樸。其優(yōu)點(diǎn)是每一個(gè)節(jié)點(diǎn)只須記錄其上一節(jié)點(diǎn)之位置，因此可有效降低記錄節(jié)點(diǎn)資料。文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)階層式拓樸文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)在

6、本研究中將以三階層式網(wǎng)路拓樸做為研究的架構(gòu)。主要原因?yàn)樵陔A層式拓樸中，其工作可以依階層的分配給下一階層，因此，不會(huì)有星狀式拓樸只有一臺(tái)伺服端造成服務(wù)資源數(shù)量有限之問題，且每一個(gè)節(jié)點(diǎn)只須記錄其上一節(jié)點(diǎn)之位置，因此可有效降低記錄節(jié)點(diǎn)資料。三階層式網(wǎng)路拓樸文獻(xiàn)探討網(wǎng)路拓樸架構(gòu)在本研究中將以三階層式網(wǎng)路拓樸做為研究文獻(xiàn)探討排程演算法OLB (Opportunistic Load Balancing)MET(Minimum Execution Time)MCT(Minimum Completion Time)Min-min(Minimum-minimum completion time)文獻(xiàn)探討排程演算

7、法OLB (Opportunistic L文獻(xiàn)探討排程演算法OLB (Opportunistic Load Balancing)讓每一部電腦都保持忙碌的狀態(tài)，不考慮各個(gè)電腦目前的工作量，而以任意的順序?qū)⑸形幢粓?zhí)行的工作分配給目前可以用的電腦進(jìn)行執(zhí)行。OLB排程演算法最大的優(yōu)點(diǎn)是相當(dāng)簡(jiǎn)單，但卻因?yàn)槲纯紤]每個(gè)工作的期望執(zhí)行時(shí)間(Expected task execution time)，所以整體而言所將獲得完成時(shí)間(Makespan)非常的差。文獻(xiàn)探討排程演算法OLB (Opportunistic L文獻(xiàn)探討排程演算法MET(Minimum Execution Time)讓每個(gè)工作可以獲得最好的電

8、腦支援，不考慮電腦目前的工作量，以任意的順序?qū)⒖梢缘玫阶疃虉?zhí)行時(shí)間的電腦分配給尚未被執(zhí)行的工作。MET排程演算法可能導(dǎo)致整個(gè)系統(tǒng)中各電腦間負(fù)載的不平衡，不適用於異質(zhì)性電腦系統(tǒng)之應(yīng)用。文獻(xiàn)探討排程演算法MET(Minimum Executio文獻(xiàn)探討排程演算法MCT(Minimum Completion Time)將目前具有最小完成時(shí)間的電腦以任意的順序分配尚未被執(zhí)行的工作，但仍可能有部份的工作無法獲得最小的執(zhí)行時(shí)間。文獻(xiàn)探討排程演算法MCT(Minimum Completi文獻(xiàn)探討排程演算法Min-min (Minimum-minimum completion time)針對(duì)每一個(gè)未排程的工作

9、建立最小的完成時(shí)間，並將工作指派給可提供最小完成時(shí)間的電腦進(jìn)行處理。因?qū)ぷ骰螂娔X都取最小的完成時(shí)間(Minimum-minimum completion time)，因此稱之為Min-min 排程演算法。優(yōu)點(diǎn)是會(huì)考慮到所有工作的最小完成時(shí)間，但也因?yàn)樾枰紤]到所有工作的最小完成時(shí)間而必須花費(fèi)額外的計(jì)算成本。只考慮每一個(gè)工作在節(jié)點(diǎn)上的完成時(shí)間而未考慮每個(gè)節(jié)點(diǎn)的負(fù)載狀況，因此可能造成有些節(jié)點(diǎn)總是非常忙碌而有些節(jié)點(diǎn)則是閒置的情況。文獻(xiàn)探討排程演算法Min-min (Minimum-min文獻(xiàn)探討排程演算法由於OLB 排程演算法簡(jiǎn)單且容易實(shí)行，並能使所有的節(jié)點(diǎn)盡可能地都處於工作狀態(tài)，因此本研究將在三

10、階層式網(wǎng)路拓樸的中間階層使用OLB 排程演算法，進(jìn)行工作的分配並將工作切割成若干個(gè)子工作。而為了能提供系統(tǒng)中各節(jié)點(diǎn)工作之負(fù)載平衡，本研究將改善Min-min 排程演算法，期能有效的降低每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間。文獻(xiàn)探討排程演算法由於OLB 排程演算法簡(jiǎn)單且容易實(shí)行，並文獻(xiàn)探討LBMM 排程演算法執(zhí)行步驟Step 1:針對(duì)各個(gè)子工作分別在每個(gè)的節(jié)點(diǎn)上找尋可以使用的最小執(zhí)行時(shí)間之資源節(jié)點(diǎn)，並形成一個(gè)Min-Time 資源節(jié)點(diǎn)集合。Step 2:再從Min-Time 資源節(jié)點(diǎn)集合中選出其中最小執(zhí)行時(shí)間的節(jié)點(diǎn)。Step 3: 將子工作分配給節(jié)點(diǎn)。Step 4: 將被完成的子工作從任務(wù)集合中刪除。Step 5

11、:將被分配到執(zhí)行子工作的節(jié)點(diǎn)重新排在所有資源節(jié)點(diǎn)的最後。Step 6:重複Step 1 到Step 5，直到所有的子工作完成。文獻(xiàn)探討LBMM 排程演算法執(zhí)行步驟文獻(xiàn)探討LBMM 排程演算法結(jié)合OLB 排程演算法與LBMM 排程演算法之特性，讓工作可平均的分配到各個(gè)節(jié)點(diǎn)上，並考慮所有工作在節(jié)點(diǎn)上執(zhí)行的最小完成時(shí)間，讓工作皆可在最短的時(shí)間內(nèi)被完成。文獻(xiàn)探討LBMM 排程演算法結(jié)合OLB 排程演算法與LBM研究方法與流程由於節(jié)點(diǎn)的組成是在一個(gè)異質(zhì)性的環(huán)境上，亦即每個(gè)節(jié)點(diǎn)執(zhí)行工作的能力不盡相同，因此在選擇節(jié)點(diǎn)執(zhí)行工作時(shí)，不僅需考慮節(jié)點(diǎn)CPU 的使用率，還需考慮其他影響節(jié)點(diǎn)有效性的因素，因此對(duì)於CUP

12、 剩餘量、記憶體剩餘量與傳輸速度有其限制，決策變數(shù)可定義為：V1 = CPU 剩餘量；V2 =記憶體剩餘量；V3 =傳輸速度。研究方法與流程由於節(jié)點(diǎn)的組成是在一個(gè)異質(zhì)性的環(huán)境上，亦即每個(gè)研究方法與流程藉由加入限制條件來提高整體的執(zhí)行品質(zhì)。其中，管理者利用“子管理者門檻值”挑選適合的子管理者。由於在階層式點(diǎn)對(duì)點(diǎn)網(wǎng)路拓樸架構(gòu)下，由同一個(gè)子管理者所管理的群組可利用的資源節(jié)點(diǎn)(階層3)，必已滿足“子管理者門檻值”方能彙聚在同一群組中。待選定子管理者後，接著將以“可利用的資源節(jié)點(diǎn)門檻值”來選擇最佳執(zhí)行節(jié)點(diǎn)。研究方法與流程藉由加入限制條件來提高整體的執(zhí)行品質(zhì)。其中，管研究方法與流程子管理者門檻值的設(shè)定假設(shè)

13、在一特定的應(yīng)用中，所要執(zhí)行的工作有如下之需求：(1) CPU 剩餘量 = 490 MB/s(2) 記憶體剩餘量 = 203698 KB/s(3) 傳輸速度 = 7.09 MB/s為了能執(zhí)行此特定的工作，因此以這三個(gè)需求因素做為“子管理者門檻值”，當(dāng)子管理者的CPU剩餘量、記憶體剩餘量及傳輸速度都跨過這個(gè)門檻值時(shí)，才會(huì)是OLB 挑選的候選子管理者之一。研究方法與流程子管理者門檻值的設(shè)定研究方法與流程可利用的資源節(jié)點(diǎn)門檻值的設(shè)定其步驟分為下列四點(diǎn)：步驟(1)：計(jì)算每個(gè)子工作的平均執(zhí)行時(shí)間。步驟(2)：當(dāng)子工作需要執(zhí)行的時(shí)間平均執(zhí)行時(shí)間時(shí)，則可正常執(zhí)行。步驟(3)：當(dāng)子工作需執(zhí)行的時(shí)間平均執(zhí)行時(shí)間時(shí)

14、，最小執(zhí)行時(shí)間會(huì)被設(shè)定為“ ”(無窮大)表示無法執(zhí)行，並讓其他已執(zhí)行過的節(jié)點(diǎn)重新進(jìn)入系統(tǒng)參與工作的執(zhí)行。步驟(4)： 重複步驟(1)(3)，直到工作執(zhí)行完畢。研究方法與流程可利用的資源節(jié)點(diǎn)門檻值的設(shè)定研究方法與流程管理者(N0)將工作依序存放在佇列中並利用代理人機(jī)制來收集子管理者資訊以O(shè)LB 排程演算法將工作分配給子管理者判斷子管理者的能力是否符合執(zhí)行此工作的“子管理者門檻子管理者負(fù)責(zé)將工作切割成不同邏輯單位大小的子工作開始YN利用LBMM 排程演法將子工作分配到第三階層的工作執(zhí)行者判斷被選出來執(zhí)行工作的節(jié)點(diǎn)是否符合“可利用的資源節(jié)點(diǎn)門檻值”判斷所有子工作是否執(zhí)行完畢讓所有節(jié)點(diǎn)重新進(jìn)入系統(tǒng)中執(zhí)

15、行結(jié)束NNYY研究方法與流程管理者(N0)將工作依序存放在佇列中並利用代理研究假設(shè)與實(shí)例本研究假設(shè)執(zhí)行的環(huán)境如下：1、傳輸時(shí)間是可掌握的。2、每個(gè)工作所需執(zhí)行的時(shí)間可以被預(yù)測(cè)。3、工作具可分割性，且每一個(gè)節(jié)點(diǎn)皆可將分配到的子工作執(zhí)行完成。4、節(jié)點(diǎn)的總數(shù)量大於工作切割成的子工作之總數(shù)量，即每個(gè)子工作都可以對(duì)應(yīng)到一個(gè)節(jié)點(diǎn)執(zhí)行。研究假設(shè)與實(shí)例本研究假設(shè)執(zhí)行的環(huán)境如下：研究假設(shè)與實(shí)例假設(shè)目前有五個(gè)工作，分別為A、B、C、D、E 需被執(zhí)行，其執(zhí)行步驟如下說明：步驟一：節(jié)點(diǎn)N0 收集要執(zhí)行的工作A、B、C、D及E，並存放到工作佇列中(圖4)，方便於工作執(zhí)行時(shí)，可依佇列中之順序分配給下一階層。同時(shí)派出行動(dòng)代

16、理人收集節(jié)點(diǎn)(子管理者)的相關(guān)資訊(CPU剩餘量、Memory 剩餘、傳輸速率等)，如表1 所示。研究假設(shè)與實(shí)例假設(shè)目前有五個(gè)工作，分別為A、B、C、D、E 研究假設(shè)與實(shí)例步驟二：以O(shè)LB 排程演算法將工作佇列中待執(zhí)行之工作依序分配給子管理者，亦即依工作的限制條件將工作A 分配給節(jié)點(diǎn)N1、N2、N3、N4、或N5；繼之，再依工作的條件限制選擇合適節(jié)點(diǎn)將工作B分配給節(jié)點(diǎn)N1、N2、N3、N4、或N5(去除掉已執(zhí)行工作A 的節(jié)點(diǎn))；工作C、D、E 依此類推。步驟三：由於工作A 的“子管理者門檻值”為“子管理者限制條件A”：(1) CPU 剩餘量 = 500 MB/s(2) 記憶體剩餘量 = 256

17、 MB/s(3) 傳輸速度 = 20 MB/s其中，節(jié)點(diǎn)N1滿足“子管理者限制條件A”；節(jié)點(diǎn)N2 的CPU 剩餘量與傳輸速率都不符合“子管理者限制條件A”；節(jié)點(diǎn)N3 的CPU 剩餘量、Memory剩餘與傳輸速率皆不符合“子管理者限制條件A”，因此將工作A 分配給節(jié)點(diǎn)N1。研究假設(shè)與實(shí)例步驟二：以O(shè)LB 排程演算法將工作佇列中待執(zhí)行研究假設(shè)與實(shí)例步驟四：當(dāng)子管理者(N1, N2, N3, N4, N5)接收到不同工作(A, B, C, D, E)時(shí)，則將每個(gè)工作以邏輯為單位分割成若干個(gè)子工作。步驟五：利用LBMM 排程演算法，計(jì)算出該子工作分配到C個(gè)不同資源節(jié)點(diǎn)上的最小執(zhí)行時(shí)間如表2 所示。假設(shè)

18、子工作A1 在節(jié)點(diǎn)N13上的執(zhí)行時(shí)間為最小，則可記為Min-Time =(A1, N12)= 14，其中Min-Time 是一個(gè)含C 個(gè)元素的一維陣列，代表一個(gè)由各個(gè)最小執(zhí)行時(shí)間組成的集合，如式(1)所示。研究假設(shè)與實(shí)例步驟四：當(dāng)子管理者(N1, N2, N3, N研究假設(shè)與實(shí)例步驟六：計(jì)算每個(gè)子工作的門檻值(Avg)，並與每個(gè)子工作的最小執(zhí)行時(shí)間比較， 如工作A1 則為1424，執(zhí)行時(shí)間在門檻值範(fàn)圍內(nèi)，因此正常運(yùn)作；A2 則為1217，執(zhí)行時(shí)間在門檻值範(fàn)圍內(nèi)，工作亦正常運(yùn)作，依此類推。步驟七：再從Min-Time 陣列中找最小值，此例中為(A2, N12)，其對(duì)應(yīng)的工作是A2，對(duì)應(yīng)的節(jié)點(diǎn)是N

19、12。因此把子工作A2 交給節(jié)點(diǎn)N12 執(zhí)行，並將A2從任務(wù)集合中刪除，同時(shí)更新工作分配前每個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間，如表3 所示。研究假設(shè)與實(shí)例步驟六：計(jì)算每個(gè)子工作的門檻值(Avg)，並與研究假設(shè)與實(shí)例步驟八：從表3 得知，由於已經(jīng)把子工作A2 分配給節(jié)點(diǎn)N12，所以A2 會(huì)從集合中被刪掉，而節(jié)點(diǎn)N12 會(huì)重新排在所有節(jié)點(diǎn)的最後面，等到所有節(jié)點(diǎn)都被分配到工作時(shí)才會(huì)又重新進(jìn)入排程中。接著會(huì)再選出每個(gè)子工作的最小執(zhí)行時(shí)間(Min-Time)，並與一開始計(jì)算出來的門檻值(Avg)作比較，因每個(gè)子工作執(zhí)行時(shí)間都在門檻值範(fàn)圍內(nèi)，因此正常運(yùn)作，並形成一個(gè)Min-Time 資源節(jié)點(diǎn)集合，如式(2)所示。再從Min

20、-Time 陣列中找出最小值，這裏為(A1,N11)，其對(duì)應(yīng)的子工作為A1，對(duì)應(yīng)的節(jié)點(diǎn)為N11，因此把子工作A1 交給節(jié)點(diǎn)N11去執(zhí)行，將A1 從任務(wù)集合中刪除，同時(shí)更新工作分配前每個(gè)節(jié)點(diǎn)執(zhí)行時(shí)間如表4 所示。研究假設(shè)與實(shí)例步驟八：從表3 得知，由於已經(jīng)把子工作A2 分研究假設(shè)與實(shí)例步驟九：從表4 可知，由於已把子工作A1 分配給節(jié)點(diǎn)N11，所以A1 從集合中刪掉，而節(jié)點(diǎn)N11 會(huì)重新排在所有節(jié)點(diǎn)的最後面，等到所有節(jié)點(diǎn)都被分配到工作時(shí)才會(huì)又重新進(jìn)入排程中。接著繼續(xù)選出最小執(zhí)行時(shí)間(Min-Time)的子工作，並與一開始計(jì)算所得的門檻值(Avg)進(jìn)行比較，因子工作A4 的執(zhí)行時(shí)間在門檻值範(fàn)圍內(nèi)，因此可正常運(yùn)作。但子工作A3 的執(zhí)行時(shí)間超過門檻值(4241)，因此最小執(zhí)行時(shí)間會(huì)暫時(shí)被設(shè)定為“8 ”，表示無法執(zhí)行，並重新形成一個(gè)Min-Time 資源節(jié)點(diǎn)集合，如式(3)所示。再從Min-