| 摘要: | 非同質網路(Heterogeneous Networks of Workstation)是指連接網路的工作站或電腦具有不同的速度, 其中包括CPU, Memory, I/O 介面,網路卡,及資訊接收或傳送速度等.相反的, 同質性網路(Homogeneous Networks of Workstation)其所連接的工作站或電腦有相同的速度, 實際上目前的區域路其switch及Hub 所連接的 電腦及 工作站 速度不同,皆屬非同質網路. 在Internet網路上, 無論是Switch 或 Hub, 可連接許多不同類型的電腦; 這些電腦有不同的傳送與接受資料速度, 功能比美超級電腦的Cluster 網路, 因連接電腦速度的不同,整個系統效益大受影響,例如資料的廣播傳送速度乃深受此因素的影響.本篇論文研究主體是在各類型的非同質性網路上提高資料傳送的速度. 共分兩類廣播(Broadcast)演算法,其一在無網路分割之情形,設計出三種不同廣播(Broadcast)演算法, 此三種演算法皆是無碰撞( Without Contention),演算法, 複雜度nlog(n). 其二是將網路分割成不同的兩個子網路, 個別選取兩個不同的Source,接著兩個網路從Source 將資料平行傳送到他所屬子網路, 以上兩種皆可大大提升網路傳送效益 In an Heterogeneous Networks of Workstations (HNOW), many different speed types of workstations can have distinct send and receive overhead. Previous research has shown that finding an optimal routing scheme in an HNOW is not easy [16,2], because properly arranging all workstations in the scheduling tree is difficult. Therefore, this investigation focuses mainly on enhancing the performance of an HNOW by properly arranging fastest nodes into the internal nodes of upper levels in the scheduling tree and using two sub-networks to broadcasting an HNOW. This dissertation is organized into two parts. In the first part, three efficient contention-free algorithms for broadcasting on heterogeneous networks of workstations (HNOW) are presented. In the second part, we present broadcast algorithms using two sub-networks. Fastest node first is fundamental in designing an efficient algorithm. Three schemes called EBS,VBBS, and VBBSWF are presented in the first part. All of these three schemes can be executed in O(nlog(n)) time, where n is the number of workstations. They are all contention-free when broadcasting in an HNOW. Based on the simulation result, the proposed schemes outperform the broadcast with minimal steps [17] and the scheduling tree [31] generated by dynamic programming in an HNOW. Furthermore, we also present efficient algorithms for broadcasting on heterogeneous networks of workstations by two partitioned sub-networks. Previous research presented that routing by two sub-networks in a NOW can significantly increase system’s performance [20]. We propose two schemes TWO-EBS and TWO-VBBS for broadcasting in an HNOW. These two schemes divide an HNOW into two sub-networks that are routed concurrently, and simultaneously combine EBS and VBBS to broadcast in an HNOW. Based on simulation results, TWO-VBBS outperforms EBS,VBBS, VBBSWF[19], the postorder recursive doubling[17] , and the optimal scheduling tree [31] generated by dynamic programming in an HNOW. |
