Double Loop Interconnection Networks With Minimal Transmission Delay.

The interconnection network is a critical component in massively parallel architectures and in large communication networks. An important criterion in evaluating such networks is their transmission delay, which is determined to a large extent by the diameter of the underlying graph. The loop network is popular due to its simplicity, symmetry and expandability. By adding chords to the loop, the diameter and reliability are improved. In this work we deal with the problem of minimizing the diameter of double loop networks, which model various communication networks and also the Illiac type Mesh Connected Computer. A double loop network, (also known as circulant) G(n,h), consists of a loop of n vertices where each vertex i is also joined by chords to the vertices i $\pm$ h mod n. D$\sbsp{\rm n}{*}$, the minimal diameter of G(n,h), is bounded below by k if n $\in$ R(k) = $\{$2k$\sp2$ - 2k + 2,...,2k$\sp2$ + 2k + 1$\}$. An integer n, a hop h and a network G(n,h) are called optimal (suboptimal) if Diam G(n,h) = D$\sbsp{\rm n}{*}$ = k (k + 1). We determine new infinite families of optimal values of n, which considerably improve previously known results. These families are of several different types and cover more than 94% of all values of n up to $\sim$8,000,000. We conjecture that all values of n are either optimal or suboptimal. Our analysis leads to the construction of an algorithm that detects optimal and suboptimal values of n. When run on a SUN workstation, it confirmed our conjecture within $\sim$60 minutes, for all values of n up to $\sim$8,000,000. Optimal (suboptimal) hops, corresponding to optimal (suboptimal) values of n, are provided by a simple construction