On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks

In this article, several schemes are proposed for embedding complete binary trees (CBT) into meshes. All of the proposed methods outperform those in the previous studies. First, a link congestion 1 embedding is achieved. Its expansion ratio is at the lowest level as we know now. Except for this supe...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 2003-05, Vol.151, p.51-70
Main Authors: Fang, Wei-Chen, Hsu, Chiun-Chieh, Wang, Chien-Ming
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article, several schemes are proposed for embedding complete binary trees (CBT) into meshes. All of the proposed methods outperform those in the previous studies. First, a link congestion 1 embedding is achieved. Its expansion ratio is at the lowest level as we know now. Except for this superiority, it also provides another capability for fault tolerance to resist abnormal system faults, thus the embedding structure can be more guaranteed and the node utilization is raised further. Second, a link congestion 1 embedding with no-bending constraint is obtained. This scheme provides efficient CBT embedding for both the optical mesh and general mesh at the same time while keeping those good properties as the previous scheme. The last one is an optimal embedding which is applied to a 3D cubic mesh, where the node is almost fully utilized and its link congestion is 2.
ISSN:0020-0255
1872-6291
DOI:10.1016/S0020-0255(02)00389-4