1、以混合式負載平衡策略提昇三階以混合式負載平衡策略提昇三階層式點對點網路拓樸之執行效能層式點對點網路拓樸之執行效能報告人：張俊盛朝陽科技大學朝陽科技大學嚴國慶嚴國慶 王淑卿王淑卿 陳秀芳陳秀芳 王順生王順生內容大綱n摘要n前言n文獻探討n網路拓樸架構n排程演算法nLBMM排程演算法n研究方法與流程n子管理者門檻值的設定n可利用的資源節點門檻值的設定n研究假設與實例n結論與未來工作摘要n由於科技的進步及網路的普及，使得點對點計算逐漸成為分散式應用的主流。但由於點對點計算主要是透過分散的節點合作完成一個大型的工作，因此如何將工作有效的分配到每一個節點上，使系統中每個節點的工作達成負載平衡，是一個值得
2、探討的議題。n在一個三階層式點對點網路拓樸架構下，提出混合式負載平衡排程演算法以進行工作的配置，透過門檻值的設定，使得每個需要執行的工作能快速的被分配到適當的節點上，除有效的改善每個節點的工作負擔外，還可依據工作的特性來選擇最合適的節點，提供三階層式點對點網路拓樸之負載平衡與執行效率的品質保證。前言n分散式系統概略可以分為主從式系統與點對點計算兩類。n主從式系統的架構是一種集中式的管理方式，架構中以伺服器為中心，提供各類資訊內容、電子郵件及資訊搜尋等服務。然而主從式架構最大的缺點是伺服器一旦發生故障，則整個主從式系統可能發生故障或癱瘓。n點對點計算因為資源是分佈在每個節點上，所以可以運用每個節
3、點的一些資源協同合作完成一個大的工作。n但是如何運用點對點計算的優點，讓需要運算的工作能在最短的時間內分配到最適當的資源則是一重要議題。文獻探討網路拓樸架構n在網路架構中，每台電腦(節點)連結的方式，即所連結的形狀稱之為拓樸，這些拓樸可以依據節點排列的形狀而加以分類。目前應用在點對點計算架構的網路拓樸，可區分為星狀拓樸、環狀拓樸與階層式拓樸。文獻探討網路拓樸架構n星狀拓樸n這種架構的應用方式是將所有的資料都集中存放在只有單一的中央伺服端中，並提供給很多的客戶端直接連接，以取得所需要的資料。n在點對點計算架構中，可使用這種星狀拓樸的服務型態，提供很多的客戶端搜尋資料。n在點對點系統架構中，伺服端
4、只提供很多的客戶端做資料的搜尋，並沒有提供客戶端直接在伺服端做資料的存取。文獻探討網路拓樸架構n環狀拓樸n由於星狀拓樸的服務方式只有一台伺服端的設備，因此可以服務客戶端的數量有限。為解決星狀拓樸所產生之問題，因此將多個伺服器連結起來，形成一個環狀拓樸。n為了防止單一鏈結的環狀拓樸中會發生連結斷裂，因此在每個節點中另外建立一條備份連結(Backup link)，形成多連結(Muti-ring)的環狀拓樸，使訊息傳送封包遺失率相對較低。n當環狀拓樸節點需要搜尋資訊時，如果環狀網路拓樸的節點數非常多時，可能造成繞送時間過久，影響搜尋的效能。文獻探討網路拓樸架構n階層式拓樸n階層式系統的使用已有很長的
5、一段歷史，如領域名稱伺服器(Domain Name Server；DNS)所形成的拓樸，就是採用階層式的網路架構。n階層式拓樸(Hierarchical Topology)的形成方式，主要會有一個名稱伺服器(Root name sever)來負責驗證的機制，每個下層節點都需要上層節點的驗證許可，依照這樣的方式形成樹狀的拓樸。其優點是每一個節點只須記錄其上一節點之位置，因此可有效降低記錄節點資料。文獻探討網路拓樸架構n在本研究中將以三階層式網路拓樸做為研究的架構。n主要原因為在階層式拓樸中，其工作可以依階層的分配給下一階層，因此，不會有星狀式拓樸只有一台伺服端造成服務資源數量有限之問題，且每一個
6、節點只須記錄其上一節點之位置，因此可有效降低記錄節點資料。三階層式網路拓樸文獻探討排程演算法nOLB(Opportunistic Load Balancing)nMET(Minimum Execution Time)nMCT(Minimum Completion Time)nMin-min(Minimum-minimum completion time)文獻探討排程演算法nOLB(Opportunistic Load Balancing)n讓每一部電腦都保持忙碌的狀態，不考慮各個電腦目前的工作量，而以任意的順序將尚未被執行的工作分配給目前可以用的電腦進行執行。nOLB排程演算法最大的優點是相當
7、簡單，但卻因為未考慮每個工作的期望執行時間(Expected task execution time)，所以整體而言所將獲得完成時間(Makespan)非常的差。文獻探討排程演算法nMET(Minimum Execution Time)n讓每個工作可以獲得最好的電腦支援，不考慮電腦目前的工作量，以任意的順序將可以得到最短執行時間的電腦分配給尚未被執行的工作。nMET排程演算法可能導致整個系統中各電腦間負載的不平衡，不適用於異質性電腦系統之應用。文獻探討排程演算法nMCT(Minimum Completion Time)n將目前具有最小完成時間的電腦以任意的順序分配尚未被執行的工作，但仍可能有部
8、份的工作無法獲得最小的執行時間。文獻探討排程演算法nMin-min(Minimum-minimum completion time)n針對每一個未排程的工作建立最小的完成時間，並將工作指派給可提供最小完成時間的電腦進行處理。n因對工作或電腦都取最小的完成時間(Minimum-minimum completion time)，因此稱之為Min-min 排程演算法。n優點是會考慮到所有工作的最小完成時間，但也因為需要考慮到所有工作的最小完成時間而必須花費額外的計算成本。n只考慮每一個工作在節點上的完成時間而未考慮每個節點的負載狀況，因此可能造成有些節點總是非常忙碌而有些節點則是閒置的情況。文獻探討
9、排程演算法n由於OLB 排程演算法簡單且容易實行，並能使所有的節點盡可能地都處於工作狀態，因此本研究將在三階層式網路拓樸的中間階層使用OLB 排程演算法，進行工作的分配並將工作切割成若干個子工作。而為了能提供系統中各節點工作之負載平衡，本研究將改善Min-min 排程演算法，期能有效的降低每個節點的執行時間。文獻探討LBMM 排程演算法n執行步驟Step 1:針對各個子工作分別在每個的節點上找尋可以使用的最小執行時間之資源節點，並形成一個Min-Time 資源節點集合。Step 2:再從Min-Time 資源節點集合中選出其中最小執行時間的節點。Step 3:將子工作分配給節點。Step 4:
10、將被完成的子工作從任務集合中刪除。Step 5:將被分配到執行子工作的節點重新排在所有資源節點的最後。Step 6:重複Step 1 到Step 5，直到所有的子工作完成。文獻探討LBMM 排程演算法n結合OLB 排程演算法與LBMM 排程演算法之特性，讓工作可平均的分配到各個節點上，並考慮所有工作在節點上執行的最小完成時間，讓工作皆可在最短的時間內被完成。研究方法與流程n由於節點的組成是在一個異質性的環境上，亦即每個節點執行工作的能力不盡相同，因此在選擇節點執行工作時，不僅需考慮節點CPU 的使用率，還需考慮其他影響節點有效性的因素，因此對於CUP 剩餘量、記憶體剩餘量與傳輸速度有其限制，決
11、策變數可定義為：V1=CPU 剩餘量；V2=記憶體剩餘量；V3=傳輸速度。研究方法與流程n藉由加入限制條件來提高整體的執行品質。其中，管理者利用“子管理者門檻值”挑選適合的子管理者。n由於在階層式點對點網路拓樸架構下，由同一個子管理者所管理的群組可利用的資源節點(階層3)，必已滿足“子管理者門檻值”方能彙聚在同一群組中。n待選定子管理者後，接著將以“可利用的資源節點門檻值”來選擇最佳執行節點。研究方法與流程n子管理者門檻值的設定假設在一特定的應用中，所要執行的工作有如下之需求：(1)CPU 剩餘量=490 MB/s(2)記憶體剩餘量=203698 KB/s(3)傳輸速度=7.09 MB/s為了
12、能執行此特定的工作，因此以這三個需求因素做為“子管理者門檻值”，當子管理者的CPU剩餘量、記憶體剩餘量及傳輸速度都跨過這個門檻值時，才會是OLB 挑選的候選子管理者之一。研究方法與流程n可利用的資源節點門檻值的設定其步驟分為下列四點：步驟(1)：計算每個子工作的平均執行時間。步驟(2)：當子工作需要執行的時間平均執行時間時，則可正常執行。步驟(3)：當子工作需執行的時間平均執行時間時，最小執行時間會被設定為“”(無窮大)表示無法執行，並讓其他已執行過的節點重新進入系統參與工作的執行。步驟(4)：重複步驟(1)(3)，直到工作執行完畢。研究方法與流程管理者(N0)將工作依序存放在佇列中並利用代理
13、人機制來收集子管理者資訊以OLB 排程演算法將工作分配給子管理者判斷子管理者的能力是否符合執行此工作的“子管理者門檻子管理者負責將工作切割成不同邏輯單位大小的子工作開始YN利用LBMM 排程演法將子工作分配到第三階層的工作執行者判斷被選出來執行工作的節點是否符合“可利用的資源節點門檻值”判斷所有子工作是否執行完畢讓所有節點重新進入系統中執行結束NNYY研究假設與實例n本研究假設執行的環境如下：1、傳輸時間是可掌握的。2、每個工作所需執行的時間可以被預測。3、工作具可分割性，且每一個節點皆可將分配到的子工作執行完成。4、節點的總數量大於工作切割成的子工作之總數量，即每個子工作都可以對應到一個節點
14、執行。研究假設與實例n假設目前有五個工作，分別為A、B、C、D、E 需被執行，其執行步驟如下說明：步驟一：步驟一：節點N0 收集要執行的工作A、B、C、D及E，並存放到工作佇列中(圖4)，方便於工作執行時，可依佇列中之順序分配給下一階層。同時派出行動代理人收集節點(子管理者)的相關資訊(CPU剩餘量、Memory 剩餘、傳輸速率等)，如表1 所示。研究假設與實例步驟二：步驟二：以OLB 排程演算法將工作佇列中待執行之工作依序分配給子管理者，亦即依工作的限制條件將工作A 分配給節點N1、N2、N3、N4、或N5；繼之，再依工作的條件限制選擇合適節點將工作B分配給節點N1、N2、N3、N4、或N5
15、(去除掉已執行工作A 的節點)；工作C、D、E 依此類推。步驟三：步驟三：由於工作A 的“子管理者門檻值”為“子管理者限制條件A”：(1)CPU 剩餘量=500 MB/s(2)記憶體剩餘量=256 MB/s(3)傳輸速度=20 MB/s其中，節點N1滿足“子管理者限制條件A”；節點N2 的CPU 剩餘量與傳輸速率都不符合“子管理者限制條件A”；節點N3 的CPU 剩餘量、Memory剩餘與傳輸速率皆不符合“子管理者限制條件A”，因此將工作A 分配給節點N1。研究假設與實例步驟四：步驟四：當子管理者(N1,N2,N3,N4,N5)接收到不同工作(A,B,C,D,E)時，則將每個工作以邏輯為單位分
16、割成若干個子工作。步驟五：步驟五：利用LBMM 排程演算法，計算出該子工作分配到C個不同資源節點上的最小執行時間如表2 所示。假設子工作A1 在節點N13上的執行時間為最小，則可記為Min-Time=(A1,N12)=14，其中Min-Time 是一個含C 個元素的一維陣列，代表一個由各個最小執行時間組成的集合，如式(1)所示。研究假設與實例步驟六：步驟六：計算每個子工作的門檻值(Avg)，並與每個子工作的最小執行時間比較，如工作A1 則為1424，執行時間在門檻值範圍內，因此正常運作；A2 則為1217，執行時間在門檻值範圍內，工作亦正常運作，依此類推。步驟七：步驟七：再從Min-Time
17、陣列中找最小值，此例中為(A2,N12)，其對應的工作是A2，對應的節點是N12。因此把子工作A2 交給節點N12 執行，並將A2從任務集合中刪除，同時更新工作分配前每個節點執行時間，如表3 所示。研究假設與實例步驟八：步驟八：從表3 得知，由於已經把子工作A2 分配給節點N12，所以A2 會從集合中被刪掉，而節點N12 會重新排在所有節點的最後面，等到所有節點都被分配到工作時才會又重新進入排程中。接著會再選出每個子工作的最小執行時間(Min-Time)，並與一開始計算出來的門檻值(Avg)作比較，因每個子工作執行時間都在門檻值範圍內，因此正常運作，並形成一個Min-Time 資源節點集合，如
18、式(2)所示。再從Min-Time 陣列中找出最小值，這裏為(A1,N11)，其對應的子工作為A1，對應的節點為N11，因此把子工作A1 交給節點N11去執行，將A1 從任務集合中刪除，同時更新工作分配前每個節點執行時間如表4 所示。研究假設與實例步驟九：步驟九：從表4 可知，由於已把子工作A1 分配給節點N11，所以A1 從集合中刪掉，而節點N11 會重新排在所有節點的最後面，等到所有節點都被分配到工作時才會又重新進入排程中。接著繼續選出最小執行時間(Min-Time)的子工作，並與一開始計算所得的門檻值(Avg)進行比較，因子工作A4 的執行時間在門檻值範圍內，因此可正常運作。但子工作A3
19、 的執行時間超過門檻值(4241)，因此最小執行時間會暫時被設定為“8”，表示無法執行，並重新形成一個Min-Time 資源節點集合，如式(3)所示。再從Min-Time 陣列中找出最小值，這裏為(A4,N13)，其對應的子工作為A4，對應的節點為N13，因此把子工作A4 交給節點N13 去執行，將A4 從任務集合中刪除，同時更新工作分配前每個節點執行時間如表5 所示。研究假設與實例步驟步驟10：從表5 得知，由於已把子工作A4 分配給節點N13，所以A4 從集合中刪掉。而因為A3 的最小執行時間超過門檻值，在步驟9 中曾暫時被設定為“”，此時除將其回覆為原執行時間“42”外，更讓所有已完成執
20、行的節點重新進入系統中，如表6 所示。最後，把剩下的最後一個子工作A3交給在此最短時間完成的節點N12 執行(式4)，即完成子管理者(N3)的分配工作，其他工作依此類推。結論n依據三階層式網路拓樸的架構，結合OLB排程演算法與LBMM 排程演算法同時利用行動代理人機制收集節點相關資訊以進行工作的配置，透過OLB 排程演算法讓每個節點都是處於工作狀態，進而實現負擔平衡。n除此之外，並利用LBMM排程演算法使得每個工作在節點上的執行時間最小，且達到整體的完成時間最小，並透過階層式的架構來設定二階門檻值，即可依工作特性來篩選合適的節點，讓處理忙碌的節點或是執行效率較差的節點無法進入系統執行工作，因此考慮到在異質性環境下，每個節點的能力與其忙碌程度，讓工作除了可以快速的被分配到合適的節點上之外，更可以快速的被執行完成，提升整體系統的效能。
