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