Communication in Chordal Ring Networks

The chordal ring networks have been the objects of a great deal of attention in recent years, and several parallel computers have configurations based on the chordal ring topology. Common ways to improve the network performance are to increase its connectivity and decrease its diameter. Therefore...

Full description

Saved in:
Bibliographic Details
Main Author: Matroud, Atheer Abbas
Format: Thesis
Language:English
English
Published: 2006
Subjects:
Online Access:http://psasir.upm.edu.my/id/eprint/153/2/549006_fsktm_2006_4_abstrak_je__dh_pdf_.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-upm-ir.153
record_format uketd_dc
spelling my-upm-ir.1532013-05-27T06:46:02Z Communication in Chordal Ring Networks 2006-04 Matroud, Atheer Abbas The chordal ring networks have been the objects of a great deal of attention in recent years, and several parallel computers have configurations based on the chordal ring topology. Common ways to improve the network performance are to increase its connectivity and decrease its diameter. Therefore, this thesis addresses the fundamental problems of communication in chordal ring of high degree and studies the degree diameter problem in such topology. In particular, we concentrate on Compact Routing, a family of routing methods that minimizes the space and time complexity. An effecient boolean routing scheme that has O(1) time complexity and O(log n) space complexity is introduced. Based on the existing results in [61] done by Narayanan and Opatrny, we propose a new algorithm for some families of chordal ring of degree six graphs. New properties for this families of graphs have been introduced such as finding the maximum number of nodes for a given diameter; it has been found that the chordal ring that has the maximum number of nodes for diameter k is G(4k2 + 2k + 1; 2k + 1; 2k2). Moreover, a broadcasting scheme for this family of chordal rings of degree six has been constructed. It has been found that this scheme can broadcast the message to all nodes in the graph by time at most k + 3 where k is the diameter. The uniqueness property of the shortest path type between any two nodes in chordal rings of degree four and six has been introduced, this property helps us in deriving our results. Communication of technical information 2006-04 Thesis http://psasir.upm.edu.my/id/eprint/153/ http://psasir.upm.edu.my/id/eprint/153/2/549006_fsktm_2006_4_abstrak_je__dh_pdf_.pdf application/pdf en public phd doctoral Universiti Putra Malaysia Communication of technical information Faculty of Computer Science and Information Technology English
institution Universiti Putra Malaysia
collection PSAS Institutional Repository
language English
English
topic Communication of technical information


spellingShingle Communication of technical information


Matroud, Atheer Abbas
Communication in Chordal Ring Networks
description The chordal ring networks have been the objects of a great deal of attention in recent years, and several parallel computers have configurations based on the chordal ring topology. Common ways to improve the network performance are to increase its connectivity and decrease its diameter. Therefore, this thesis addresses the fundamental problems of communication in chordal ring of high degree and studies the degree diameter problem in such topology. In particular, we concentrate on Compact Routing, a family of routing methods that minimizes the space and time complexity. An effecient boolean routing scheme that has O(1) time complexity and O(log n) space complexity is introduced. Based on the existing results in [61] done by Narayanan and Opatrny, we propose a new algorithm for some families of chordal ring of degree six graphs. New properties for this families of graphs have been introduced such as finding the maximum number of nodes for a given diameter; it has been found that the chordal ring that has the maximum number of nodes for diameter k is G(4k2 + 2k + 1; 2k + 1; 2k2). Moreover, a broadcasting scheme for this family of chordal rings of degree six has been constructed. It has been found that this scheme can broadcast the message to all nodes in the graph by time at most k + 3 where k is the diameter. The uniqueness property of the shortest path type between any two nodes in chordal rings of degree four and six has been introduced, this property helps us in deriving our results.
format Thesis
qualification_name Doctor of Philosophy (PhD.)
qualification_level Doctorate
author Matroud, Atheer Abbas
author_facet Matroud, Atheer Abbas
author_sort Matroud, Atheer Abbas
title Communication in Chordal Ring Networks
title_short Communication in Chordal Ring Networks
title_full Communication in Chordal Ring Networks
title_fullStr Communication in Chordal Ring Networks
title_full_unstemmed Communication in Chordal Ring Networks
title_sort communication in chordal ring networks
granting_institution Universiti Putra Malaysia
granting_department Faculty of Computer Science and Information Technology
publishDate 2006
url http://psasir.upm.edu.my/id/eprint/153/2/549006_fsktm_2006_4_abstrak_je__dh_pdf_.pdf
_version_ 1747810148367204352