Trade-offs between latency, complexity, and load balancing with multicast algorithms

Article English OPEN
Al Dubai, A.Y. ; Ould-Khaoua, M. ; Mackenzie, L.M. (2010)
  • Publisher: IEEE
  • Related identifiers: doi: 10.1109/TC.2009.104
  • Subject: QA75
    acm: ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS

The increasing number of collective communication-based services with a mass interest and the parallel increasing demand for service quality are paving the way toward end-to-end QoS guarantees. Although many multicast algorithms in interconnection networks have been widely reported in the literature, most of them handle the multicast communication within limited performance metrics, i.e., either delay/latency or throughput. In contrast, this study investigates the multicast communication within a group of QoS constrains, namely latency, jitter, throughput, and additional traffic caused. In this paper, we present the Qualified Groups (QGs) as a novel path-based multicast algorithm for interconnection networks. To the best of our knowledge, the QG is the first multicast algorithm that considers the multicast latency at both the network and node levels across different traffic scenarios in interconnection networks. Our analysis shows that the proposed multicast algorithm exhibits superior performance characteristics over other well-known path-based multicast algorithms under different operating conditions. In addition, our results show that the QG can significantly improve the parallelism of the multicast communication.
  • References (20)
    20 references, page 1 of 2

    [1] N.-C. Wang, C.-P. Yen, and C.-P. Chu, “Multicast Communication in Wormhole-Routed Symmetric Networks with Hamiltonian Cycle Model,” J. Systems Architecture, vol. 51, no. 3, pp. 165-183, Mar. 2005.

    [2] A. Al-Dubai, M. Ould-Khaoua, and L. Mackenzie, “An Efficient Path-Based Multicast Algorithm for Mesh Networks,” Proc. Int'l Parallel and Distributed Processing Symp. (IPDPS), p. 283, 2003.

    [3] J. Duato, C. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Elsevier Science, 2003.

    [4] A. Touzene, “Optimal All-Ports Collective Communication Algorithms for the k-Ary n-Cube Interconnection Networks,” J. Systems Architecture, vol. 50, no. 4, pp. 169-236, 2004.

    [5] C. Busch, M. Magdon-Ismail, and J. Xi, “Optimal Oblivious Path Selection on the Mesh,” IEEE Trans. Computers, vol. 57, no. 5, pp. 660-671, May 2008.

    [6] P.K. McKinley and C. Trefftz, “MultiSim: A Simulation Tool for the Study of Large-Scale Multiprocessors,” Proc. Int'l Symp. Modeling, Analysis and Simulation of Computer and Telecomm. Systems (MASCOTS '93), pp. 57-62, 1993.

    [7] CSIM: Internet:, 2009.

    [8] E. Fleury and P. Fraigniaud, “Strategies for Path-Based Multicasting in Wormhole-Routed Meshes,” J. Parallel and Distributed Computing, vol. 60, pp. 26-62, 1998.

    [9] D. Xiang, Y. Zhang, and Y. Pan, “Practical Deadlock-Free FaultTolerant Routing in Meshes Based on the Planar Network Fault Model,” IEEE Trans. Computers, vol. 58, no. 5, pp. 620-633, May 2009.

    [10] X. Lin, P. McKinley, and L.M. Ni, “Deadlock-Free Multicast Wormhole Routing in 2D-Mesh Multicomputers,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 8, pp. 793-804, Aug. 1994.

  • Metrics
    No metrics available
Share - Bookmark