Login | Register

Multicasting algorithms for mesh and torus networks


Multicasting algorithms for mesh and torus networks

Liu, Xiaolin (2003) Multicasting algorithms for mesh and torus networks. Masters thesis, Concordia University.

Text (application/pdf)


Multicasting is an important interprocessor communication pattern existing in various parallel application algorithms. Mesh-connected topology is one of the most thoroughly investigated network topologies for parallel processing. The torus network has been proposed for metropolitan area networks (MAN). It can be divided into several mesh problems. Time and traffic are the main parameters considered in the multicasting communication environment. It is NP-complete in general to find an optimal multicasting algorithm which minimizes both time and traffic. This thesis proposes two kind of multicasting algorithms for torus/mesh networks, the VH algorithm with a time complexity of O(kD), and the DIST algorithm with a time complexity of O(kDN), where k is the number of destination nodes. D is the maximum distance, and N is the total number of nodes in the network. The VH algorithm guarantee that every destination node can receive the message from the source in a minimum multicasting time. The DIST algorithm generates less traffic compared to the VH algorithm, but at the price of an increased multicasting time.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Liu, Xiaolin
Pagination:xi, 103 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Harutyunyan, Hovhannes A
ID Code:2021
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:24
Last Modified:18 Jan 2018 17:18
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

Back to top Back to top