Improved upper and lower bounds on the optimization of mixed chordal ring networks

James K. Lan, Victor W. Liu, Chiuyuan Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Recently, Chen, Hwang and Liu [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] introduced the mixed chordal ring network as a topology for interconnection networks. In particular, they showed that the amount of hardware and the network structure of the mixed chordal ring network are very comparable to the (directed) double-loop network, yet the mixed chordal ring network can achieve a better diameter than the double-loop network. More precisely, the mixed chordal ring network can achieve diameter about sqrt(2 N) as compared to sqrt(3 N) for the (directed) double-loop network, where N is the number of nodes in the network. One of the most important questions in interconnection networks is, for a given number of nodes, how to find an optimal network (a network with the smallest diameter) and give the construction of such a network. Chen et al. [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] gave upper and lower bounds for such an optimization problem on the mixed chordal ring network. In this paper, we improve the upper and lower bounds as 2 ⌈ sqrt(N / 2) ⌉ + 1 and ⌈ sqrt(2 N) - 3 / 2 ⌉, respectively. In addition, we correct some deficient contexts in [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16].

Original languageEnglish
Pages (from-to)757-762
Number of pages6
JournalInformation Processing Letters
Volume109
Issue number13
DOIs
StatePublished - 15 Jun 2009

Keywords

  • Diameter
  • Double-loop network
  • Interconnection network
  • Loop
  • Mixed chordal ring network
  • Optimization
  • Parallel processing
  • Ring

Fingerprint Dive into the research topics of 'Improved upper and lower bounds on the optimization of mixed chordal ring networks'. Together they form a unique fingerprint.

Cite this