Efficient broadcast in heterogeneous networks of workstations using two sub-networks

[[abstract]]This paper presents efficient algorithms for broadcasting on heterogeneous switch-based networks of workstations (HNOW) by two partitioned sub-networks. In an HNOW, many multiple speed types of workstations have different send and receive overheads. Previous research has found that routing by two sub-networks in a NOW can significantly increase system's performance (Proc. 10th International Conference on Computer Communications and Networks, pp. 68-73, 2001). Similarly, EBS and VBBS (Proc. 8th IEEE International Symposium on Computer and Communication, pp. 1277-1284, (2003)), designed by applying the concept of fastest nodes first, can be executed in O(nlog(n)) time, where n is the number of workstations. This paper proposes 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 combine EBS and VBBS to broadcast in an HNOW. Based on simulation results, TWO-VBBS outperforms EBS, VBBS, VBBSWF (Proc. 8th IEEE International Symposium on Computer and Communication, pp. 1277-1284, (2003)), the postorder recursive doubling (Proc. Merged IPPS/SPDP Conference, pp. 358-364, (1998)), and the optimal scheduling tree (Proc. Parallel and Distributed Processing Symposium, Proc. 15th International (2001)) generated by dynamic programming in an HNOW. © 2005 Springer Science+Business Media, Inc.[[fileno]]2030224010033[[department]]資訊工程學