Breadcrumb

 
 

Multicasting algorithms for mesh and torus networks

Title:

Multicasting algorithms for mesh and torus networks

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

[img]
Preview
PDF
2989Kb

Abstract

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 > Faculty 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:Theses (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Date:2003
Thesis Supervisor(s):Harutyunyan, Hovhannes A
ID Code:2021
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:24
Last Modified:08 Dec 2010 10:24
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

Document Downloads

More statistics for this item...

Concordia University - Footer