Login | Register

Efficient multicast routing algorithms for mesh-connected multicomputers


Efficient multicast routing algorithms for mesh-connected multicomputers

Wang, Shengjian (2005) Efficient multicast routing algorithms for mesh-connected multicomputers. Masters thesis, Concordia University.

[thumbnail of MR10298.pdf]
Text (application/pdf)
MR10298.pdf - Accepted Version


Multicast is a collective communication method in which a message is sent from a source to an arbitrary number of distinct destinations. Multicomputers refer to massively parallel computers that consist of thousands of processors built to handle computation intensive applications. Mesh is a kind of network topology widely used in multicomputers. Performance of multicomputers largely depends on that of the underlying network communications such as multicast, which is essential for processors to exchange data and messages. Two major parameters used to evaluate multicast routing are the time it takes to deliver the message to all destinations and the traffic which refers to the total number of links involved. Research indicated that these two parameters are normally not independent, but contradict each other. It has been proved that traffic optimal multicast problems such as Optimal Multicast Path/Tree in mesh-connected network are NP-complete. Hence, it is NP-hard to find multicast routing which is optimal on both time and traffic. In this thesis, we proposed three efficient multicast routing algorithms for mesh-connected multicomputers: DIAG, DDS and XY-path, all of which have a small complexity of O(KN) or less. The DIAG and DDS are two tree-based shortest path multicast routing algorithms designed for store-and-forward switched mesh network, which obtained near optimal time and reduced traffic significantly over its predecessor VH algorithm. XY-path is a dual-path-based multicast routing algorithm intended for wormhole routed 2D mesh network, which reduced the time and traffic significantly over LIN's Hamiltonian path-based algorithm. Performance evaluations of these algorithms resulted from simulations are given at the end of the thesis.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Wang, Shengjian
Pagination:xii, 134 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Harutyunyan, Hovhannes
Identification Number:LE 3 C66C67M 2005 W36
ID Code:8508
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:27
Last Modified:13 Jul 2020 20:04
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top