Login | Register

Studies of interconnection networks with applications in broadcasting

Title:

Studies of interconnection networks with applications in broadcasting

Morosan, Calin Dan (2007) Studies of interconnection networks with applications in broadcasting. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR30133.pdf - Accepted Version
4MB

Abstract

The exponential growth of interconnection networks transformed the communication primitives into an important area of research. One of these primitives is the one-to-all communication, i.e. broadcasting. Its presence in areas such as static and mobile networks, Internet messaging, supercomputing, multimedia, epidemic algorithms, replicated databases, rumors and virus spreading, to mention only a few, shows the relevance of this primitive. In this thesis we focus on the study of interconnection networks from the perspective of two main problems in broadcasting: the minimum broadcast time problem and the minimum broadcast graph problem. Both problems are discussed under the 1-port constant model, which assumes that each node of the network can communicate with only one other node at a time and the transmitting time is constant, regardless of the size of the message. In the first part we introduce the minimum broadcast time function and we present two new properties of this function. One of the properties yields an iterative heuristic for the minimum broadcast time problem, which is the first iterative approach in approximating the broadcast time of an arbitrary graph. In the second part we give exact upper and lower bounds for the number of broadcast schemes in graphs. We also propose an algorithm for enumerating all the broadcast schemes and a random algorithm for broadcasting. In the third part we present a study of the spectra of Knödel graph and their applications. This study is motivated by the fact that, among the three known infinite families of minimum broadcast graphs, namely the hypercube, the recursive circulant, and the Knödel graph, the last one has the smallest diameter. In the last part we introduce a new measure for the fault tolerance of an interconnection network, which we name the global fault tolerance. Based on this measure, we make a comparative study for the above mentioned classes of minimum broadcast graphs, along with other classes of graphs with good communication properties.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Morosan, Calin Dan
Pagination:ix, 98 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:2007
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:975303
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:05
Last Modified:18 Jan 2018 17:40
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