TY - JOUR

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

AU - Lan, James K.

AU - Liu, Victor W.

AU - Chen, Chiuyuan

PY - 2009/6/15

Y1 - 2009/6/15

N2 - 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].

AB - 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].

KW - Diameter

KW - Double-loop network

KW - Interconnection network

KW - Loop

KW - Mixed chordal ring network

KW - Optimization

KW - Parallel processing

KW - Ring

UR - http://www.scopus.com/inward/record.url?scp=67349201679&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.03.017

DO - 10.1016/j.ipl.2009.03.017

M3 - Article

AN - SCOPUS:67349201679

VL - 109

SP - 757

EP - 762

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 13

ER -