在階層式點對點網路拓撲下以負載平衡為導向之排程機制

A Load Balance Oriented Scheduling Scheme in a Hierarchal Peer-to-Peer Network

由於網路快速的進步，人們對電腦的需求也越來越高，生活中到處充滿著運算的需求，因此如何利用網路資源達成協同合作之運算是近年來重要的研究議題之一。而在科技的進步及網路的普及下，點對點計算(Peer-to-Peer Computing)逐漸成為分散式應用的主流，它不僅可以提供大量的運算資源，協助無法在單一電腦上解決之複雜計算問題之外，更可達到資源有效的整合與共享。但由於點對點計算主要是透過分散的節點協力合作完成一個需要大量計算資源的工作，且每個節點皆有自己的中央處理器、時脈、記憶體、與匯流排，因此如何在這種異質性的環境下，確保進入點對點系統中的每個工作，可以如期完成工作並快速且負載平衡的分配資源則是一個值得探討的議題。本研究將利用能力函數與分群法來建立一個動態階層式點對點網路拓樸架構，並在此網路拓樸下，提出三階段排程演算法。首先利用BTO(Best Task Order)排程演算法，針對進入系統待執行的工作，透過有效的工作排序給予一個最佳的執行順序； 接著使用本研究所提出之TOLB(Threshold based Opportunistic Load Balancing) 排程演算法與TLBMM(Threshold based Load Balance Min-Min)排程演算法進行工作的配置與執行，使得每個工作可以分配到最適的節點來執行，讓資源達到最佳的配置，且可依節點的負載狀況及執行工作的時間進行工作的分配，藉以維護系統整體的執行效能與達到較佳的負載平衡。