The Fault Tolerance of Interconnection Network HCN ( n , n ) and Embedding between HCN ( n , n ) , and HFN ( n , n )


The KIPS Transactions:PartA, Vol. 9, No. 3, pp. 333-340, Sep. 2002
10.3745/KIPSTA.2002.9.3.333,   PDF Download:

Abstract

Embedding is a mapping an interconnection network G to another interconnection network H. If a network G can be embedded to another network H, algorithms developed on G can be simulated on H. In this paper, we first propose a method to embed between Hierarchical Cubic Network HCN(n, n) and Hierarchical Folded-hypercube Network HFN(n, n). HCN(n, n) and HFN(n, n) are graph topologies having desirable properties of hypercube while improving the network cost, defined as degree x diameter, of Hypercube. We prove that HCN(n, n) can be embedded into HFN(n, n) with dilation 3 and congestion 2, and the average dilation is less than 2. HFN(n, n) can be embedded into HCN(n, n) with dilation O (n), but the average dilation is less than 2. Finally, we analyze the fault tolerance of HCN(n, n) and prove that HCN(n, n) is maximally fault tolerant.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. S. Kim and H. O. Lee, "The Fault Tolerance of Interconnection Network HCN ( n , n ) and Embedding between HCN ( n , n ) , and HFN ( n , n )," The KIPS Transactions:PartA, vol. 9, no. 3, pp. 333-340, 2002. DOI: 10.3745/KIPSTA.2002.9.3.333.

[ACM Style]
Jong Seok Kim and Hyeong Ok Lee. 2002. The Fault Tolerance of Interconnection Network HCN ( n , n ) and Embedding between HCN ( n , n ) , and HFN ( n , n ). The KIPS Transactions:PartA, 9, 3, (2002), 333-340. DOI: 10.3745/KIPSTA.2002.9.3.333.