Distributed Loop Computer Networks: A Survey

J.-C. Bermond I3S, CNRS bât 4, rue A. Einstein Sophia-Antipolis 06560 Valbonne, France

F. Comellas Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya Campus Nord, C3; c/ Gran Capitán s/n 08071 Barcelona, Spain

D. F. Hsu Department of Computer and Information Science Fordham University Bronx N.Y. 10458-5198 and Department of Mathematics Massachusetts Institute of Technology Cambridge, Massachusetts 02139 \begin{matrix}c \\ ◯ \end{matrix}1995 by Academic Press, Inc. Journal of Parallel and Distributed Computing, 24, pp. 2–10 (1995).

Abstract

Distributed loop computer networks are extensions of the ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. We give a survey of recent results on this class of interconnection networks. We pay special attention to the actual computation of the minimum diameter and the construction of loop networks which can achieve this optimal number. Some open problems are offered for further investigation.

1 Introduction and motivation

The advent of VLSI circuit technology has enabled the construction of very complex and large interconnection networks. These interconnection networks have been used in the design of local area networks, telecommunication networks and other distributed computer systems. They can also be inter-PE (processing element) communication networks which perform necessary data routing and manipulation function in many parallel architectures.

The study of loop networks has been motivated mainly by conception problems in the construction of local area networks and in the design of topologies for parallel processing computer systems. Local area networks consist of several stations placed at short distances (less than 4 or 5 km) that exchange data information at very high speeds. One of the main problems in the design of such networks is the choice of a good topology for which these exchanges can be optimized.

In a number of array processors, for instance the ILLIAC IV computer, the PE array (a PE consists of a CPU and a local memory) can be operated as a circulator. When depicted as a ring of PE’s, each PE of the ILLIAC IV network is connected to a fixed number of other PE’s. Each node i is connected to nodes i ± 1 and i ± s modulo n. On the other hand, it is a common practice to combine several independent memory modules into the memory systems in a high-performance computer to help with parallel block transfers. In this context, the network called memory circulator consists of a group of interconnected registers, one for each memory module, and the control circuitry. Each register is connected to a fixed number of other registers and the pattern is cyclically symmetric.

In the design and implementation of local area networks, the ring topology has been used frequently. This is due to its simplicity, expandability and regularity. The switching mechanism at each node can easily be implemented using building blocks of the same specification. Moreover, a token or message can be passed over the ring in a uniform way. Hence it is feasible to design software for message transmission or file transfer. However, the ring network has a low degree of reliability and hence very high vulnerability. More specifically, the connectivity of an unidirectional ring network of n nodes is 1 since the breakdown of any node i would disable any directed path from node i − 1 to node i + 1 taken modulo n. Another way of measuring the performance is the maximum distance among any pair of nodes. A large distance would contribute to the transmission delay between these two nodes. For a directed ring network, the maximum distance (or the diameter) is as big as n − 1 and for an undirected ring is ⌊\frac{n}{2}⌋.

One common way to improve the performance of a network is to increase its connectivity and decrease its diameter. That can be done by adding links to the network. However we want to add as few links as possible since the cost of more links would be a practical factor in the design and also the number of links going out of a node must be small to allow VLSI drawing. Furthermore one wants to add these few links in a homogeneous way such that the switching mechanism at each node can be easily implemented and messages or information can be routed in a systematic way.

Networks with at least one ring structure (i.e. hamiltonian cycle or circuit) are called loop networks. In what follows, we survey the various loop networks considered in the literature. For a given number of nodes n, one wants to find the smallest possible diameter of a loop network and give the construction of such a network. We will see that most of the time, the exact value is unknown. However one can obtain some good bounds. Another related question of interest is to find the minimum average distance of a loop network (i.e. the average transmission time in the network). It is also interesting, when possible, to exhibit the different routings between two nodes. Other issues include parameters such as vulnerability of the network. For general reference on computer architecture and parallel processing, see Hwang and Briggs [50].

2 Definitions and notation

Let G(n; s_{1}, s_{2}, ..., s_{k}) be the network with n nodes, labeled with integers modulo n, and k links per vertex such that each node i is adjacent to the k other nodes i + s_{1}, i + s_{2}, …, i+s_{k} (mod n). The network G(n; ±s_{1}, ±s_{2}, …, ±s_{k}) is the undirected version of G(n; s_{1}, s_{2}, …, s_{k}) where each node is adjacent to the 2k nodes i±s_{1}, i±s_{2}, …, i±s_{k}. This network has been called circulant graph and studied extensively. The reader is referred to the survey of Boesch and Tindell [13] and its references. We will call these networks multiple fixed step digraphs or multiple fixed step graphs to emphasize the fact that the s_{i}’s are given. We consider essentially the case s_{1} = 1 and also several variations of loop networks which have the ring property.

If G is a digraph (resp. graph), let d(x, y) be the length of a shortest directed (undirected) path from x to y (resp. between x and y). Let the diameter be the maximum of d(x, y) over all couples (resp. pairs) of vertices. We will denote by d(n; s_{1}, s_{2}, …, s_{k}) the diameter of the network G(n; s_{1}, s_{2}, …, s_{k}) and by d(n; ±s_{1}, ±s_{2}, …, ±s_{k}) the diameter of G(n; ±s_{1}, ±s_{2}, …, ±s_{k}). We use d̄(n; s_{1}, s_{2}, …, s_{k}) to denote the mean distance (or average distance) of G(n; s_{1}, s_{2}, …, s_{k}). The mean distance is de-

fined as: \frac{1}{n(n − 1)} ∑_{(x,y)} d(x, y). Since we are interested in optimizing the diameter

among all possible choices of s_{1}, s_{2}, …, s_{k}, let d(n) = min{d(n; s_{1}, s_{2}, …, s_{k}); 1 ≤ s_{1}, s_{2}, …, s_{k} ≤ n − 1}. The network G(n; s_{1}, s_{2}, …, s_{k}) is said to be optimal if d(n; s_{1}, s_{2}, …, s_{k}) = d(n). In some cases, it is difficult to obtain optimal networks; however, one can find general simple functions lb(n) and ub(n) which are for every n a lower bound and an upper bound for d(n). We will say that G(n; s_{1}, s_{2}, …, s_{k}) is tight if d(n; s_{1}, s_{2}, …, s_{k}) = lb(n). If a network is tight, then it must be optimal. The converse is certainly not true as it can be seen in the next section. A similar notation will be used in the undirected case.

A routing is a function that assigns to each pair of nodes x and y a directed path r(x, y) from x to y in the network. Routing plays an important role in the design and implementation of distributed networks. The routing algorithm dictates token passing strategies and information transferring schedules.

A directed graph is said to be strongly connected if there exists at least one directed path from any vertex to any other one. It has node connectivity equal to k if the removal of some set of k nodes results in a disconnected graph while the graph remains strongly connected after removal of any set of less than k nodes. The connectivity of the network measures the degree of reliability and hence the fault tolerance of that network. Similar definitions hold in the undirected case.

3 Double fixed step digraphs

In this section, we consider the double-fixed step digraph G(n; s_{1}, s_{2}) as a model for loop networks. Each node is directly connected to two other nodes.

The network with s_{1} = 1 and s_{2} = −1 was considered by Liu [55], Wolf, Weide and Liu [75] and by Wolf and Liu [73]. This structure was called Distributed Double Loop Computer Network (DDLCN). A DDLCN has diameter ⌊\frac{n}{2}⌋ and mean distance roughly \frac{n}{4}.

Grnarov, Kleinrock and Gerla [42] considered the network G(n; s_{1}, s_{2}) with s_{1} = 1 and s_{2} = −2. It is known as daisy chain loop. It was shown that d(n; 1, −2) = ⌊\frac{n}{3}⌋ + 1 and d̄(n; 1, −2) is approximatively equal to \frac{n}{6}. In fact, Wong and Coppersmith [76] showed that taking s_{1} = 1 and s_{2} around \sqrt{n} gives rise to a small diameter, approximatively 2\sqrt{n}, and a small mean distance, approximatively \sqrt{n}. More exactly, they proved that d(t^{2}; 1, t) = 2t−2 and d̄(t^{2}; 1, t) = t−1. This was partly rediscovered by Raghavendra and Gerla [62], Raghavendra, Gerla and Avizienis [63] and Raghavendra, Gerla and Parker [64] (see also the comment of Hwang [48]). Simulation was then used to study the performances of these networks in case of node or link failures (see [63, 66]). Futhermore, Wong and Coppersmith [76] showed that lb(n) = ⌈\sqrt{3n}⌉ − 2 is a lower bound for d′(n) = min_{s} d(n; 1, s) and so lb(n) is also a lower bound for

d(n) = min_{s_{1},s_{2}} d(n; s_{1}, s_{2}). They also showed that \frac{5}{9} \sqrt{3n} − 1 is a lower bound for the mean

distance d̄′(n) and d̄(n).

The problem of determining d(n) = min_{s_{1},s_{2}} d(n; s_{1}, s_{2}) and of finding G(n; s_{1}, s_{2}) which

attain the value d(n) seems to be a difficult one. It might seem easier to determine d′(n) = min_{s} d(n; 1, s) and the optimal G(n; 1, s). But that is not the case. Furthermore, most of the time, among the solutions s_{1} , s_{2} that give the values d(n), there is one with s_{1} = 1. Fiol, Yebra, Alegre and Valero [38] have shown by using an exhaustive search that the smallest value of n such that d(n) ≠ d′(n) is n = 450. In that case d(450) = 35 = d(450; 2, 185) and d′(450) = 36 = d(450; 1, 59). Their search shows also that the function d(n) does not increase monotonically with n: for example d(20) = d(20; 1, 4) = 7 while d(21; 1, 9) = 6. Similarly, d̄(n) has no regularity, here again d̄(20) = d̄(20; 1, 4) = 3 500 but d̄(21) = d̄(21; 1, 9) = 3 429. Some optimal graphs for d̄ are not optimal for d: for example d̄(59; 1, 8) = d̄(59) = 6 576 but d(59; 1, 8) = 13 > 12 = d(59) = d(59; 1, 25). However, their computer search showed that for n ≤ 256, lb(n) = \sqrt{3n}−2 ≤ d(n) ≤ \sqrt{3n}−1 and \frac{5}{9} \sqrt{3n}−1 ≤ d̄(n) ≤ \frac{5}{9}(\sqrt{3n}−1). Recently Esqué, Aguiló and Fiol [37] exhibit an infinite family of values of n for which d(n) ≠ d′(n)).

Cheng [22], see also Cheng and Hwang [23], gives a simple algorithm to compute d′(n) = min_{s} d(n; 1, s). Consider all pairs of non-negative integers p,q such that ∑ p+q ≠ 0 is minimum and ps + q ≡ 0 (mod n). Among all these pairs define the pair P, Q as the one with minimum P. Let S be the smallest positive integer such that Ss mod n ≤ S. Let T be the smallest integer such that T ≡ ts (mod n) for some positive integer t < T. Then it can be shown that d(n; 1, s) = max{P + T − 2, Q + S − 2}. Using this algorithm, a computer search shows that there are several n’s, 1 ≤ n ≤ 30000 for which d′(n) − lb(n) = 3; and there are three n’s, 1 ≤ n ≤ 75000 such that d′(n) − lb(n) = 4, these are n = 53749 (d′(n) = d(n; 1, 985) = 404), n = 64729 (d′(n) = d(n; 1, 394) = 443) and n = 69283 (d′(n) = d(n; 1, 1764) = 458).

It seems that lim sup d′(n)−lb(n) increases, but in a slow fashion. That is confirmed by a recent result of Coppersmith (private communication to D.F. Hsu) who showed the existence of an infinite set of values of n for which d′(n) is greater than \sqrt{3n}+c(log n)^{\frac{1}{4}} for some constant c.

On the other hand it was not known until recently whether the function lb(n) = ⌈\sqrt{3n}⌉ − 2 could be achieved by d(n) for infinite values of n. We recall that a digraph is called tight if its diameter achieves this bound. Infinite families of tight digraphs and also of families of digraphs for which d(n) is known have been found by different authors [35, 37, 38, 49]. Furthermore in [37] Esqué, Aguiló and Fiol completely characterized the values of n for which tight digraphs exist. An algorithm to find the values of s_{1} and s_{2} of tight digraphs and digraphs with diameter d(n) is given by Aguiló and Fiol [1].

Erdős and Hsu [35] used the following approach. All nodes are labeled modulo n, these nodes are evenly distributed on a circle. In order to find s such that d(n; 1, s) = d′(n), they travel around the circle at steps of 1 or s counterclockwise (or the other way around as long as it is consistent). The optimization problem is then to find suitable s such that all nodes on the circle can be reached in as few steps as possible. That gives rise to infinite families of tight digraphs. An example is given in Figure 1 with n = 3t^{2} + 3t, d(n; 1, 3t + 2) = 3t = d′(n) and t = 3. Hence n = 36 and d(36) = 9. We note that d(36; 1, \sqrt{36}) = d(36; 1, 6) = 10 > d(36) = 9.

Wong and Coppersmith [76] and Fiol, Yebra, Alegre and Valero [38] have visualized the problem in a geometrical manner. If the link (i, i+s_{1}) is represented by an horizontal segment and the link (i, i + s_{2}) by a vertical one, then the distance between two nodes is obtained by adding the number of horizontal and vertical segments between them. It is then possible to represent a network by a tessellation of the plane, see Figure 2.

The optimization problem consists in finding an L-shape tile of n unit squares which periodically tessellates the plane with minimum diameter and/or mean distance. Then the problem consists of finding, for a given tile, the values of s_{1} and s_{2} that enable this construction. It was pointed out that, for a given n, there might be different optimal solutions s_{1} and s_{2} (that is d(n; s_{1}, s_{2}) = d(n)) and that one of them is a solution with s_{1} = 1 with very few exceptions. For example, in [38] the authors obtained that d(n) = lb(n) for infinite values of n like d(3t^{2} + t; 1, 3t) = d(3t^{2} + 2t; 1, −3t) = 3t − 1; d(3t^{2} + 2t + 1; 1, 3t + 1) = d(3t^{2} + 3t + 1; 1, 3t + 2) = d(3t^{2} + 4t + 1; 1, −3t − 2) = 3t; d(3t^{2} + 4t + 2; 1, 3t + 3) = d(3t^{2} + 5t + 2; 1, 3t + 4) = d(3t^{2} + 6t + 2; 1, −3t + 4) = 3t + 1. In some other cases they showed that although a tight tile exists, there do not exist corresponding values of s_{1} and s_{2}. For example, if n = 3t^{2} then d(3t^{2}; 1, 3t + 2) = d(3t^{2}) = 3t − 1 but lb(3t^{2}) = 3t − 2 (see also Erdős and Hsu [35] or Hwang and Xu [49]). Finally in some cases there cannot exist tight tiles for example for n = 25 or 46. As we said, recently Esqué, Aguiló and Fiol [37] fully characterized the tiles associated with tight digraphs and when there exists possible choices of s_{1} and s_{2}. They fall into 9 different families (at most 3 for a given value of n). As an example for n ≤ 50 there exist tight digraphs for all n except n = 12, 20, 25, 27, 32, 46 and 48. Note that optimal tiles do not exist only for 25 and 46. For the other exceptional values the impossibility comes from the non existence of values of s_{1} and s_{2}.

Since the problem of optimizing d(n; 1, s) is not completely solved, one might be interested in finding an upper bound for d′(n). We note that as mentioned before, Wong and Coppersmith [76] proved that if n = t^{2}, then d(t^{2}; 1, t) = 2t − 2 = 2\sqrt{n} − 2. Hwang and Xu [49] showed that for n ≥ 6348, d(n; 1, s) < \sqrt{3n} + 2(3n)^{\frac{1}{4}} + Δ − 1 where Δ = ⌊\frac{\sqrt{n−1}}{a_{0}}⌋ − 3a_{0} and a_{0} = ⌊\frac{\sqrt{n}}{3}⌋. Erdős and Hsu [35] gave an asymptotic result using Diophantine approximation. For every ϵ > 0 there exists an n_{0}(ϵ) such that if n > n_{0}(ϵ) there exists a number s such that d(n; 1, s) < (1 + ϵ)\sqrt{3n}.

The routing problems and fault tolerance for G(n; 1, s) and G(n; s_{1}, s_{2}) were studied by Erdős and Hsu [35]; Hu, Hwang and Li [46]; Fiol,Yebra, Alegre and Valero [38] and Escudero, Fábrega and Morillo [36]. The last authors also showed that the diameter of the network after a node failure is at most d(n; 1, s) + 1. Furthermore, Fiol and Yebra [39] determined when G(n; s_{1}, s_{2}) has a directed hamiltonian cycle. Further references can be found in the forthcoming survey of Hwang [47].

4 Double fixed step graphs

One can also consider the same problems for undirected double fixed step networks G(n; ±s_{1}, ±s_{2}). This class of networks is also known as 2-jump circulant graphs. If s_{1} < s_{2} ≤ \frac{n−1}{2}, these graphs are 4-regular. They are connected if and only if gcd(s_{1}, s_{2}, n) = 1. In this case it has been proved by Bermond, Favaron and Maheo [8] that they can be decomposed into two hamiltonian cycles.

It is easy to show that if G(n; ±s_{1}, ±s_{2}) has diameter D, then n ≤ 2D^{2} + 2D + 1 (see [10, 14, 76, 78]). Solving for D, we obtain d(n) ≥ ⌈\frac{\sqrt{2n−1}−1}{2}⌉ = ulb(n), where d(n) = min_{s_{1},s_{2}} d(n; ±s_{1}, ±s_{2}). Beivide, Viñals and Rodríguez [4], Bermond, Illiades and

Peyrat [10] and Boesch and Wang [14] showed that this lower bound ulb(n) can be achieved by taking s_{1} = ulb(n) and s_{2} = ulb(n) + 1. Furthermore in [10, 78] it is shown that d(2t^{2} + 2t + 1; ±s_{1}, ±s_{2}) = t if and only if s_{1} ≡ tp and s_{2} ≡ (t + 1)p where p is any integer less than n and relatively prime with n. An algorithm to compute the diameter of G(n; ±s_{1}, ±s_{2}), analogue to that of Cheng and Hwang [23] has been given by Žerovnik and Pisanski [79].

The mean distance d̄(n) for the double fixed step graphs is asymptotically equal to \sqrt{\frac{2n}{3}} (see [10]). Moreover, it was proved by Boesch and Wang [14] that the graph G(n; ±ulb(n), ±ulb(n) + 1) has maximum connectivity four.

Surprisingly, the problem of determining d′(n) = min_{s} d(n; ±1, ±s) is more difficult. By the result above, we have that for n = 2t^{2} +2t+1, d′(n; ±1, ±(2t+1)) = t = ulb(n). But for n = 2t^{2} +2t, Du, Hsu, Li and Xu [33] and Tzvieli [71] showed that d′(2t^{2} +2t) = t + 1 = ulb(n) + 1. Let n_{t} = 2t^{2} + 2t + 1, and R(t) = {n_{t−1} + 1, …, n_{t}}. For example R(4) = {26, …, 41}. Du, Hsu, Li and Xu [33] obtained new classes of values of n for which loop networks G(n; ±1, ±s) can be found that achieve lower bound ulb(n). Namely these classes contains, for each t ≥ 3, 10 values of R(t) (that independently of t). In [71] Tzvieli found several other classes, each of which intersects each R(t) in a set of cardinality O(\sqrt{t}). Recently Bermond and Tzvieli [12] found dense infinite such classes. They proved that if n ∈ R(t), d′(n) = ulb(n) when gcd(n, t) = 1 or when gcd(n, t + 1) = 1, or when gcd(n, t − 1) = 1 and n ≤ 2t^{2} + 1. As a corollary, it is proven that when t is prime and n is in R(t), n ≠ n_{t} − 1, d′(n) = ulb(n). This equality also holds when t + 1 is prime, n is in R(t), n ≠ n_{t} − 1, with a possible exception when n = 2t^{2} − 2. In [70] Tzvieli conjectured that d′(n) is always smaller than or equal to ulb(n) + 1, and verified the conjecture for n up to 8 000 000.

A double fixed step graph G(n; ±1, ±s) is said to be optimal if d(n; ±1, ±s) = d′(n). Hsu and Shapiro [44] defined the notion of one-optimality which is stronger than being optimal. They gave a complete census of double step graphs which have diameter equal to ulb(n) and are one-optimal. Using the concept of one optimality, Hsu and Shapiro [45] also showed that d′(n) < (\frac{n}{2})^{\frac{1}{2}} + (\frac{n}{8})^{\frac{1}{4}} + 2.

5 Multiple fixed step graphs and digraphs

A natural extension of the preceding results includes the consideration of the general network G(n; s_{1}, s_{2}, …, s_{k}) or G(n; ±s_{1}, ±s_{2}, …, ±s_{k}). The general problem is far from being solved. Results for several special cases have been obtained.

In the case of fixed k-step digraphs, Wong and Coppersmith [76] have shown that the maximum number of vertices of such a digraph with diameter D is \binom{k+D}{k}. From that, one can deduce a lower bound for d(n): d(n) ≥ (k!n)^{\frac{1}{k}} − \frac{1}{2}(k + 1). Fiol, in his thesis (see [38]) showed that in fact one always has n < \binom{k+D}{k} as soon as D > 1. It is not known whether there exists an infinite class of n for which optimal networks can be constructed for k ≥ 3. Wong and Coppersmith [76] gave an upper bound by showing that if n = t^{k} (where t is an integer), d(t^{k}; 1, t, t^{2}, …, t^{k−1}) = k(t − 1) = kn^{\frac{1}{k}} − k. Therefore, d(n) is bounded by a function of the order kn^{\frac{1}{k}}. They also give lower and upper bounds for the average distance.

For k = 3, Erdős and Hsu [35] showed that for some classes of n, there exist s_{2}, s_{3} such that d(n) ≤ d(n; 1, s_{2}, s_{3}) ≤ (\sqrt{3c} + \frac{1}{c})n^{\frac{1}{3}} − 3. The constant c can be suitably chosen to minimize the function \sqrt{3c} + \frac{1}{c}. Then they generalized the result to the cases when k > 3. That is, for some classes of n, there exist s_{2}, s_{3}, …, s_{k} such that d(n; 1, s_{2}, s_{3}, …, s_{k}) ≤ (((k − 1)!c)^{\frac{1}{k−1}} + \frac{1}{c})n^{\frac{1}{k}} − \frac{k+2}{2}. Recently, Hsu and Jia [43] showed that d(n; 1, s_{2}, s_{3}) ≤ (16n)^{\frac{1}{3}} and d(n; 1, s_{2}, s_{3}) ≥ (14 − 3\sqrt{3})^{\frac{1}{3}} n^{\frac{1}{3}} . The upper bound (16n)^{\frac{1}{3}} is an improvement of the result of Erdős and Hsu [35]. However, the lower bound (14 − 3\sqrt{3})^{\frac{1}{3}} n^{\frac{1}{3}} is the first new result which improves the bound (6n)^{\frac{1}{3}} − 2 in the case k = 3 obtained by Wong and Coppersmith [76].

In the undirected case Wong and Coppersmith [76] gave an upper bound on the maximum number of vertices of a fixed k-step graph G(n; ±s_{1}, ±s_{2}, …, ±s_{k}) with di-

ameter D. They showed that n ≤ 1 + ∑_{i=0}^{k−1} \binom{k}{i}\binom{D}{k − i}2^{k−i} (This was rediscovered by

Boesch and Wang [14]). In the case k = 2, we obtain again n ≤ 2D^{2} + 2D + 1 and in the case k = 3, n ≤ 1 + \frac{4D^{3}+6D^{2}+8D}{3} . From this result Wong and Coppersmith deduced a lower bound for d(n) of the order of \frac{1}{2}(k!)^{\frac{1}{k}} n^{\frac{1}{k}}. Recent results on lower bounds for d(n), has been given by Garcia and Solé [40, 41] using a different approach. Wong and Coppersmith also gave a lower bound for d̄(n) of the order of \frac{1}{2} \frac{k}{k+1}(k!)^{\frac{1}{k}} n^{\frac{1}{k}}.

On the other hand, they showed that for n = t^{k}, d(n; ±1, ±t, ±t^{2}, ±t^{k−1}) = \frac{k}{2}(t − 1) = \frac{k}{2}n^{\frac{1}{k}} − \frac{k}{2} (in the geometrical approach, this corresponds to a tessellation of the space with k-dimensional cubes). In the case k = 3, these bounds give that f(n) ≤ d(n) ≤ g(n) where f(n) is of the order of (\frac{3}{4}n)^{\frac{1}{3}} and g(n) of the order of (\frac{27}{8}n)^{\frac{1}{3}} . C. Peyrat (private communication) has shown that g(n) can be lowered to a function of order (\frac{9}{8}n)^{\frac{1}{3}} . C. Delorme (private communication) exhibited a geometrical construction that gives rise to generalized 3-step graphs with diameter bounded by a function of order (\frac{27}{32}n)^{\frac{1}{3}} . (In that case, the vertices are considered as element of a group, two vertices i and j being joined if j − i = ±s_{1}, ±s_{2}, …, ±s_{k} where the s_{i}’s are elements of the group). Recently Chen and Jia [21] obtained the same result for k = 3 as a particular case of the following upper bound d(n) ≤ (\frac{2k^{k}}{4^{k}} n)^{\frac{1}{k}}.

Several variations of the networks described above have also been considered mainly for triple and quadruple step digraphs or graphs. These networks are not optimal for the diameter but they have nice regularity properties , a good mean distance and are highly fault-tolerant. Furthermore they are associated to particular tessellations of the plane. For example, Morillo, Fiol and Fábrega in [60] considered the class G(n; s_{1}, s_{2}, s_{1} + s_{2}). The maximum order of such a graph with diameter D is (D + 1)^{2} and furthermore the minimum diameter d(n; s_{1}, s_{2}, s_{1} + s_{2}) = ⌊\sqrt{n − 1}⌋, this minimum being attained for s_{1} = 1 , s_{2} = ⌊\sqrt{n − 1}⌋ + 1. After deletion of one edge or one vertex, the diameter increases at most by one. These digraphs are associated with hexagonal tessellations of the plane. Similarly in the undirected case, it is proved in [78] that the maximum order of a triple loop graph G(n; a, b, a + b), where a = ±s_{1}, b = ±s_{2} and 0 < s_{1} < s_{2} < ⌊\frac{n}{2}⌋, with diameter D is 3D^{2} + 3D + 1. The bound can be achieved for s_{1} = 1, and s_{2} = 3D + 1. The problem of determining their diameters has been only solved for some families of infinite values of n (see [57]). Here again, these graphs are associated with hexagonal tessellations.

6 Generalized loop networks

Other related constructions include the chordal ring networks studied by Arden and Lee [3] although they were introduced by Coxeter [28] more than thirty years ago. These graphs are formed by adding chords in a regular manner to an undirected cycle or loop. The simplest example is given by the cubic graph obtained by adding a perfect matching (maximal set of disjoint edges) to an even cycle. A nice way to construct such a cubic graph is as follows. Let the set of vertices be V = V_{0} ∪ V_{1} where V_{0} = {0, 2, …, n − 2} and V_{1} = {1, 3, …, n − 1} and n is even. Join every vertex i in V_{0} to the vertices i ± 1 in V_{1} (these edges forming the cycle) and then join every vertex i in V_{0} to the vertex i+s in V_{1} (where s is odd) and consequently every vertex j in V_{1} is joined to the vertex j − s in V_{0}. For example the Heawood graph is obtained with n = 14 and s = 5 (or 9). Arden and Lee [3] constructed such graphs with a diameter D and a number of vertices equal to D^{2} + O(D). This was improved by Alegre, Comellas, Fiol, Morillo and Yebra (see [78, 58]) who showed that the maximum number of vertices of such a graph with diameter D is \frac{3D^{2}+1}{2} if D is odd (in that case the bound is achieved with s = 3D) and \frac{3D^{2}}{2} − D if D is even (in that case the bound is achieved with s = 3D + 1). In [78] the authors studied also two kinds of generalizations. In the first one every vertex i of V_{0} is joined to the vertices i ± s_{1} of V_{0} and i + s_{3} of V_{1} and every vertex j of V_{1} is joined to the vertices j ± s_{2} of V_{1} and j − s_{3} of V_{0}. The graphs thus obtained are cubic and known as generalized Petersen graphs [72]. +s are of order \frac{1}{2} \sqrt{n}. In fact the extremal graphs were already considered by Bermond, Delorme and Farhi [5] as a special product of K_{2} by C_{2k^{2}+2k+1}. In the second case, each vertex i of V_{0} is joined to the vertices i + s_{1}, i + s_{2} and i + s_{3} in V_{1} (the s_{i}’s being odd) and consequently each vertex j of V_{1} is joined to the vertices j − s_{1}, j − s_{2} and j − s_{3} in V_{0}. The graphs thus obtained are bipartite and related in some way to hexagonal tessellations of the plane (see [78]). Generalized bipartite or quadripartite graphs are also considered by Comellas, Morillo, Fiol and Yebra (see [61, 57, 27]). The case where vertex i is joined to vertices i ± s_{1} and i + s_{2} is studied by Morillo and Fiol in [59].

Another generalization consists in considering Cayley graphs or digraphs. These graphs are associated to groups. The fixed step loop graphs or digraphs considered in the preceding paragraphs correspond to the case when the group is the additive group of the integers modulo n. The vertices are the elements of the group, a vertex i being joined to the vertices i + s_{1}, i + s_{2},..,i + s_{k} (in case of digraphs) and i ± s_{1}, i ± s_{2},…, i±s_{k} (in case of graphs), where s_{1},…, s_{k} are given elements of the group. For diameter related properties of these graphs, see for example the articles of Bond and Delorme [17], Bond, Delorme and de la Vega [18], Campbell et al. [19], Carlsson, Cruthirds, Sexton and Wright [20], Chudnovsky, Chudnovsky and Denneau [24] and Hsu and Jia [43].

In all the above cases, the diameter is of order n^{\frac{1}{k}}. Using the classical Moore bound for the maximum number of vertices of an undirected Δ-regular graph with diameter D, n ≤ 1+Δ+Δ(Δ−1)+…+Δ(Δ−1)^{D}, one obtain that the diameter of a Δ-regular graph on n vertices is at least log_{Δ−1} n − \frac{2}{Δ}. It has been shown by Bollobás and de la Vega [16] that a random Δ-regular graph has diameter of order log_{Δ−1} n with probability close to 1. Recently, Bollobás and Chung [15] showed that a random cubic loop graph obtained by adding a random perfect matching to a cycle has a diameter also of the order log_{Δ−1} n. Therefore there is some hope to construct loop networks, Δ-regular and with a diameter of order log_{Δ} n. For digraphs, such networks were constructed a long time ago for particular values of n. Indeed the de Bruijn digraphs , which exist for n = d^{D}, and the Kautz digraphs, which exist for n = d^{D} + d^{D−1} are hamiltonian digraphs with in- and out-degree equal to d and diameter D (see the surveys [6] or [11] for different definitions and properties). They are hamiltonian because they can be defined as iterated line digraphs of complete symmetric graphs (with or without loops) and it is well known that the line digraph of an eulerian digraph is hamiltonian.

Different generalizations of these digraphs have been proposed. Reddy, Pradhan and Kuhl [68] and Imase and Itoh [51] defined generalized de Bruijn digraphs as follows : the vertices are the integer modulo n and there is an arc from i to j if and only if j ≡ di + a (mod n) for some a , 0 ≤ a ≤ d − 1. The de Bruijn digraphs corresponds to the case when n = d^{D}. Imase and Itoh [51] defined generalized Kautz digraphs in a similar way: the vertices are the integers modulo n and there is an arc from i to j if and only if j ≡ −di − b (mod n) for some b, 1 ≤ b ≤ d. Kautz digraphs correspond to the particular case when n = d^{D} + d^{D−1}. These digraphs have in and out degree equal to d and diameter at most ⌈log_{d} n⌉.

It was not known until recently if they were hamiltonian. The results of Du, Hsu, Hwang and Zhang [32, 34] showed that they are in fact hamiltonian except when d = 2 and n is odd for the generalized de Bruijn digraphs and d = 2, n is odd and n ≠ 3^{k} for the generalized Kautz digraphs. When d = 2, a class of networks called H_{n} obtained by modifying the generalized Kautz digraphs has been proposed by Du, Hsu and Hwang [31]. They showed that H_{n} is hamiltonian, has connectivity 2 and diameter at most ⌈log_{2}(n − 1)⌉ + 1. The connectivities and other reliability properties of the generalized de Bruijn and Kautz digraphs have been settled recently (see the survey [9]). It appears that these digraphs and also the associated undirected graphs are highly fault tolerant; for example, their connectivities are in most cases equal to their minimum degrees (which is best possible).

Itoh, Imase and Yoshida [53] and Du, Hsu and Hwang [30] have proposed the class of consecutive-d digraphs G(d, n, q, r); their nodes are labeled by integers modulo n and vertex i is joined to the d consecutive vertices qi+r +k (mod n) where 0 ≤ k < d < n and q is a non zero element. Du and Hsu [34] and Du, Hsu and Hwang [30] studied their hamiltonian and connectivity properties. Note that when q = d and r = 0, one obtains the generalized de Bruijn digraphs and that when q = n − d and r = n − d the generalized Kautz digraphs. Another generalization, called c-circulant digraphs, has been introduced by Mora, Serra and Fiol [56, 69]. The nodes are labeled by integers modulo n and node i is joined to the nodes ci + a_{s}, where the a_{s} take d given values. When these digraphs are strongly connected and gcd(c, n) = 1 they are hamiltonian.

All these results are good answers for the problem of constructing optimal loop directed networks. It will be nice to construct in a similar way digraphs that are not only hamiltonian but also admit a Hamilton decomposition; therefore they can be considered as the union of arc-disjoint loops.

The undirected graphs associated to the digraphs defined above give examples of good networks but they are far from being optimal; for example, we obtain 4-regular graphs with a number of vertices of order 2^{D}, but the Moore bound is of order 3^{D}. Similarly, the best known constructions of cubic graphs give a diameter of 1.47 log_{2} n; but one can hope, in particular in view of the results on cubic random graphs mentioned above, a diameter of order log_{2} n.

7 Conclusions and problems

The class of distributed loop computer networks plays an important role in the design and implementation of interconnection networks. We have given a survey on recent literature which deal in particular with the issues of diameter, connectivity and hamiltonian properties. It appears that already some good classes of networks exist: the double fixed step graphs or digraphs with diameter of order \sqrt{n} and nice regularity and routing properties, or the generalized de Bruijn graphs or digraphs with diameter of order log n.

The tutorial edited by Wu and Feng [77] provides a general survey of interconnection networks. Other properties can be found in [54]. The reader might find some other information in the recent surveys concerning the (Δ,D)-graph problem (construction of the largest known graphs with given maximum degree Δ and diameter D) by Bermond, Delorme and Quisquater [6, 7]; diameters of graphs by Chung [25, 26]; fault tolerant (or vulnerability) properties of interconnection networks by Bermond, Homobono and Peyrat [9].

Finally we list some open problems for further investigations. Some partial results concerning these problems have been mentioned in the current survey.

(1.) In the case of double fixed step digraphs find d(n) = min d(n; s_{1}, s_{2}) or d′(n) = min d(n; 1, s) for any given n. Moreover, find optimal loop networks G(n; s_{1}, s_{2}) or G(n; 1, s) having this diameter.

(2.) Study the function f(n) = d(n) − lb(n) or f′(n) = d′(n) − lb(n) where lb(n) = ⌈\sqrt{3n}⌉ − 2. In particular, how large can lim sup f(n) or lim sup f′(n) be.

(3.) Do the same as in (1) and (2) for the class of double fixed step graphs G(n; ±1, ±s).

(4.) Study the generalization of problems (1),(2),(3) for the k fixed step graphs and digraphs, G(n; 1, ±s_{2}, …, ±s_{k}) and G(n; s_{1}, s_{2}, …, s_{k}).

(5.) Find hamiltonian networks, Δ-regular on n vertices with a diameter of order log_{Δ−1} n. In particular construct cubic hamiltonian graphs with diameter of order log_{2} n.

(6.) Construct networks with a good diameter which can be decomposed into hamiltonian cycles.

References

[1] Aguiló, F., and Fiol, M.A. An efficient algorithm to find optimal double loop networks. 14th British Combinatorial Conference, Keele, England, July 1993.

[2] D. Ameter and Max de Gree. Graph and Interconnection Networks. Forthcoming book.

[3] Arden, B.W., and Lee,H. Analysis of chordal ring networks. IEEE Trans. Comput., C-30 ,1981 , pp. 291–295.

[4] Beivide, R., Viñals, V., and Rodríguez, C. Optimal topologies with four bidirectional links and its applications. Proc. IAESTED Int. Symp. AI’87, Grindelwald, Switzerland , 1987, pp.66–69.

[5] Bermond, J-C., Delorme, C., and Farhi, G. Large graphs with given degree and diameter II. J. Combin. Theory Ser. B, 36, 1984, pp. 32–48.

[6] Bermond, J-C., Delorme, C., and Quisquater, J.J. Strategies for interconnection networks: some methods from graph theory. J. Parallel and Distrib. Comput., 3, 1986, pp. 433–449.

[7] Bermond, J-C., Delorme, C., and Quisquater, J.J. Table of large (Δ, D)-graphs. Discrete Appl. Math., 37/38, 1992, pp. 575–577.

[8] Bermond, J-C., Favaron, O., and Maheo, M. Hamiltonian decomposition of Cayley graphs of degree four. J. Combin. Theory Ser. B,46 , 1989, pp. 142–153.

[9] Bermond, J-C., Homobono, N., and Peyrat, C. Large fault tolerant interconnection networks. Proc. First Japan International Conference on Graph Theory and Applications, Hakone, Japan, 1986. Graphs and Combinatorics 5, 1989, pp. 107– 123.

[10] Bermond, J-C., Illiades, G., and Peyrat, C. An optimization problem in distributed loop computer networks. Third International Conference on Combinatorial Math., New York, U.S.A., June 1985. Annals of the New York Acad. Science, 555 , 1989, pp. 45–55.

[11] Bermond, J-C., and Peyrat, C. The de Bruijn and Kautz networks a competition for the hypercube and distributed computers. Proc. First European Workshop on Hypercubes, Rennes, France, October 1989. Elsevier Science Pub., North Holland, 1989, pp. 279–293.

[12] Bermond, J-C., and Tzvieli, D. Minimal diameter double-loop networks: Dense optimal families. Networks, 21, 1991, pp. 1–9.

[13] Boesch, F.T., and Tindell, R. Circulants and their connectivity. J. Graph Theory 8, 1984, pp. 487–499.

[14] Boesch, F.T., and Wang, J.K. Reliable circulant networks with minimum transmission delay. IEEE Trans. Circuits Syst. CAS-32 , 1985, pp. 1286–1291.

[15] Bollobás, B. and Chung, F.R.K. The diameter of a cycle plus a random matching. SIAM J. on Discrete Math., 1, 1988, pp. 328–333.

[16] Bollobás, B. and De la Vega, W.F. The diameter of random graphs. Combinatorica, 2, 1982, pp. 125–134.

[17] Bond, J., and Delorme, C. A note on partial Cayley graphs. Discrete Math., 114 (1993), pp. 63–74.

[18] Bond, J., Delorme, C., and De la Vega, W.F. Large Cayley graphs with small degree and diameter. LRI Research Rep. 392. Laboratoire de Recherche en Informatique. C.N.R.S. Orsay. Paris.

[19] Campbell, L., Carlsson, G.E., Dineen, M.J., Faber, V., Fellows, M. Langston, M.A., Moore, J.W., Mullhaupt, A.P., and Sexton.H.B. Small diameter symmetric networks from linear groups. IEEE Trans. on Comput., 41, 1992, pp. 218–220.

[20] Carlsson, G.E., Cruthirds, J.E., Sexton, H.B., and Wright, C.G. Interconnection networks based on a generalization of cube-connected cycles. IEEE Trans. on Comput., C-34, 1985, pp. 769–772.

[21] Cheng, S., and Jia, X. Undirected loop networks. Networks, 23, 1993, pp. 257–260.

[22] Cheng, Y. Diameters of double loop local computer networks. Preprint.

[23] Cheng, Y., and Hwang, F.K. Diameters of weighted double loop networks. J. Algorithms 9 , 1988, pp. 401–410.

[24] Chudnovsky, D.V., Chudnovsky, G.V., and Denneau, M.M. Regular graphs with small diameter as models for interconnection networks. Proc. 3rd. Int. Conf. on Supercomputing International Computing Institute, Boston, 1988, pp. 232–239.

[25] Chung, F.R.K. Diameters of graphs: old problems and new results. Congressus Numerantium, 1987, 60, pp. 1–18.

[26] Chung, F.R.K. Diameters of communication networks. AMS Short Course on the Mathematics of Information Processing A.M.S., Providence, 1986, 34, pp. 1–18.

[27] Comellas, F., Morillo, P., and Fiol, M.A. Diameter and mean distance of bipartite graphs related to plane tessellations. Ars Combin., 29B, 1990, pp. 245–254.

[28] Coxeter, H.S.M. Self dual configurations and regular graphs. Bull. Amer. Math. Soc. 56 , 1950, pp. 413–455.

[29] Du, D.Z., Hsu, D.F. On hamiltonian consecutive-d digraphs. Combinatorics and Graph Theory, Banach Center Publications, 25, 1989, pp. 41–55.

[30] Du, D.Z., Hsu, D.F., and Hwang, F.K. The hamiltonian property of consecutive d-digraphs. Math. Computer Modeling, 17 (1993), pp. 61–63.

[31] Du, D.Z., Hsu, D.F., and Hwang, F.K. Double-linked Ring Networks. IEEE Trans. on Comput., 34, 1985, pp. 853–855.

[32] Du, D.Z., Hsu, D.F., Hwang, F.K., and Zhang, X.M. The hamiltonian property of generalized de Bruijn graphs. J. Combin. Theory Ser. B, 52,1991, pp. 1–8.

[33] Du, D.Z., Hsu, D.F., Li, Q., and Xu, J. A combinatorial problem related to distributed loop networks. Networks, 20, 1990, pp. 173–180.

[34] Du, D.Z., and Hwang, F.K. Generalized de Bruijn digraphs. Networks, 18, 1988, pp. 27–38.

[35] Erdős, P. and Hsu, D.F. Distributed loop networks with minimum transmission delay. Theoret. Comp. Sci., 100, 1992, pp. 223–241.

[36] Escudero, M., Fábrega, J., and Morillo, P. Fault-tolerant routings in double-loop networks. Ars Combin. , 25A , 1988, pp. 187–198.

[37] Esqué, P., Aguiló, F., and Fiol, M.A. Double commutative step digraphs with minimum diameters. Discrete Math., 114, 1993, pp. 147-157.

[38] Fiol, M.A., Yebra, J.L.A., Alegre, I., and Valero, M. A discrete optimization problem in local networks and data alignment, IEEE Trans. Comput. C-36, 1987, pp. 702–713.

[39] Fiol, M.A., and Yebra, J.L.A. Ciclos de Hamilton en redes de pasos conmutativos y de paso fijo. Stochastica XII-2, (3) 1988, pp. 113–129.

[40] Garcia, C. Diamétre des Graphes de Cayley Abeliens. Ph.D. Thesis, 1993.

[41] Garcia, C., and Solé, P. Diameter lower bound for Waring graphs and multiloop networks. Discrete Math.,111, 1993, pp. 257–261.

[42] Grnarov, A., Kleinrock L., and Gerla, M. A highly reliable distributed loop network architecture. Proc. 1980 Int. Symp. Fault-Tolerant Comput., Kyoto, Japan , 1980, pp. 319–324.

[43] Hsu, D.F. and Jia, X.D. Extremal problems in the combinatorial construction of distributed loop networks. SIAM J. on Discrete Math., 7 (1994), pp. 57–71.

[44] Hsu, D.F. and Shapiro, J. A census of tight one-optimal double loop networks. In Y. Alavi et al. (Eds.). Graph Theory, Combinatorics, Algorithms and Applications. SIAM, 1991, pp. 254–265.

[45] Hsu, D.F. and Shapiro, J. Bounds for the minimal number of transmission delays in double loop networks. J. of Combinatorics, Information and System Sciences, 16, 1991, pp. 55–62.

[46] Hu, X.D., Hwang, F.K. and Li, W. W., Most reliable double loop networks in survival reliability. Networks, 23, 1993, pp. 451–458.

[47] Hwang, F.K. A survey on double loop networks. Proc. DIMACS Workshop on Reliability of Computer and Communication Networks. Rutger University, New Brunswick, New Jersey, December 2–4, 1989.

[48] Hwang, F.K. Comments on “Reliable loop topologies for large local computer network”. IEEE Trans. Comput. C-36 , 1987, pp. 383–384.

[49] Hwang, F.K. ,and Xu, Y.H. Double loop networks with minimum delay. Discrete Math. ,66 , 1987, pp. 109–118.

[50] Hwang, K. ,and Briggs, F. Computer Architecture and Parallel Processing. Mac Graw Hill, New York, 1985.

[51] Imase, M., and Itoh, M. Design to minimize diameter on building-block network. IEEE Trans. on Comput., C-30, 1981, pp. 439-442.

[52] Imase, M., and Itoh, M. A design for directed graphs with minimum diameter. IEEE Trans. on Comput., C-32, 1983, pp. 782–784.

[53] Itoh, M., Imase, M., and Yoshida, Y. A design method for regular graphs with nearly minimum diameters (in japanese). IECE Trans., J66A, 1, 1983, pp. 48–55.

[54] Leighton, F.T. Introduction to parallel algorithms and architectures. Ph. D. Thesis, Lousiana State University, August 1988.

[55] Liu, M.T. Distributed loop computer networks. Advances in Computers 17, Academic Press , 1978, 163-221.

[56] Mora, M., Serra, O., and Fiol, M.A. General properties of c-circulant digraphs. Ars Combin.,25C, 1988, pp.241–252.

[57] Morillo, P. Grafos y Digrafos Asociados con Teselaciones como Modelos para Redes de Interconexion. Ph. D. Thesis, Universitat Politècnica de Catalunya, Barcelona, Spain, 1986.

[58] Morillo, P., Comellas, F., and Fiol, M.A. The optimization of chordal ring networks. Proc. International Conference on Communication Technology, ICCT, Nanjing, China , 1987, pp. 295–299.

[59] Morillo, P., and Fiol, M.A. El diámetro de ciertos digrafos circulantes de triple paso. Stochastica, 10 , 1986, pp. 233–249.

[60] Morillo, P., Fiol, M.A., and Fábrega, J. The diameter of directed graphs associated to plane tessellations. Ars Combin.,20A , 1985, pp. 17–27.

[61] Morillo, P., Fiol, M.A., and Yebra, J.L.A. A new family of graphs associated with plane tessellations. Ars Combin., 20A, 1985, pp. 163–169.

[62] Raghavendra, C.S., and Gerla, M. Optimal loop topologies for distributed systems. Proc. 7th Data Communication Symposium Mexico City , 1981, pp. 218–223.

[63] Raghavendra, C.S., Gerla, M., and Avizienis, A. Reliable loop topologies for large local computer networks. IEEE Trans. Comput. C-34 , 1985, pp. 46–55.

[64] Raghavendra, C.S., and Gerla, M., and Parker, D.S. Multi-connected loop topologies for local computer networks. Proc. Conf. INFOCOM 82 , 1982.

[65] Raghavendra C.S., and Silvester, J.A. A comparative study of double loop network architectures. Links for the Future: Science, Systems and Services for Communications, IEEE/Elsevier Science Pub. B.V. , North Holland, 1984, pp. 149–152.

[66] Raghavendra C.S., and Silvester, J.A. Double loop network architectures - A performance study. IEEE Trans. Commun.,COM-33 , 1985, pp. 185–187.

[67] Raghavendra C.S., and Silvester, J.A. A survey of multi-connected loop topologies for local computer networks. Computer Networks and ISDN Systems 11 , 1986, pp. 29–42.

[68] Reddy, S.M., Pradhan, D.K., and Kuhl, J. Directed graphs with minimal diameter and maximal connectivity. School of Engineering Oakland University, Tech. Rep., 1980.

[69] Serra, O., Mora, M., and Fiol, M.A. On c-circulant digraphs. Proc. 1988 International Conference on Incidence Geometries and Combinatorial Structures, Mediterranean Press, Rende, 1991, 2nd Volume, pp 421–437.

[70] Tzvieli, D. Minimal diameter double-ring networks: Part I: Some very large infinite optimal families. Networks, 21, 1991, pp 387–415.

[71] Tzvieli, D. Double loop networks: optimal and suboptimal families. Morgan Kaufmann, 1992.

[72] Watkins, M.E. A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Combin. Theory, 6, 1969, pp. 152–164.

[73] Wolf, J., and Liu, M.T. A distributed double-loop computer network. Proc. 7th Texas Conf. Comput. Systems, U.S.A., 1978, pp. 6.29–6.34.

[74] Wolf, J., Liu, M.T., Weide, B., and Tsay, D. Design of a distributed fault-tolerant loop network. Proc. 9th Int. Symp. Fault-Tolerant Comput., Madison, WI, U.S.A., 1979, pp. 17–24.

[75] Wolf, J., Weide, B., and Liu, M.T. Analysis and simulation of the distributed double loop network. Proc. Comput. Networking Symp. NBS , 1979, pp. 82–89.

[76] Wong, C.K., and Coppersmith, D. A combinatorial problem related to multimode memory organizations. J. Assoc. Comp. Mach. 21 , 1974, pp. 392–402.

[77] Wu, C.L., and Feng, T.Y. Tutorial : interconnection networks for parallel and distributed processing. IEEE Computer Society, 1984

[78] Yebra, J.L.A., Fiol, M.A., Morillo, P., and Alegre, I. The diameter of undirected graphs associated to plane tessellations. Ars Combin. 20B , 1985, pp. 159–171.

[79] Žerovnik, J., and Pisanski, T. Computing the diameter in multiple-loop networks. J. Algorithms 14, 1993, pp. 226–243.

Figure 1: An optimal loop network G(36; 1, 11), d(36; 1, 11) = 9 = d(36). 17

0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5

Figure 2: Geometrical representation of G(9; 1, 7).