The Optimization of Chordal Ring Networks

P. Morillo, F. Comellas and M.A. Fiol Department of Mathematics, E.T.S.E. Telecomunicació Universitat Politècnica de Catalunya, Barcelona, Spain \begin{matrix}c \\ ◯ \end{matrix}1987 by World Scientific Publishing Co. Pte. Ltd. Communication Technology, Eds. Q. Yasheng and W Xiuying, World Scientific, pp. 295–299,1987, ISBN 9971-50-349-9

This paper deals with the design of multi-(micro)computer interconnection networks modelled by graphs. In particular we concentrate upon the optimization of a new family of such networks that turn out to be a generalization of the well-known Arden and Lee’s chordal ring networks. This optimization problem leads to the search for certain 3-regular graphs with minimum diameter for a given order and/or maximum order for a given diameter. The use of a geometrical approach based on plane tessellations facilitates the solution of the problem.

1 Introduction

Interconnection networks for distributed computer systems can be modelled by graphs [1, 2], in which the vertices represent the nodes, or processing elements, of the network and the edges represent the communication links between them. One of the main factors to be considered in the design of interconnection networks is their topology, which is related to the communication delay, throughput, routing of the messages, etc. These characteristics correspond respectively to some parameters and properties in the associated graphs: diameter, degree, existence of short paths between vertices, etc. So, let us begin by recalling some concepts from graph theory.

A graph G = (V, E) consists of a set V of points called vertices and a set A of (nonordered) pairs of distinct vertices called edges. If there exists an edge incident to the vertices i,j, that is i, j ∈ V, we say that i and j are adjacent. The degree of a vertex is the number of edges incident to it and G is 3-regular if all its vertices have degree 3. The distance d(i, i) between two vertices i, j ∈ V is the minimum number of edges which must be used in a path between them. The maximum distance among pairs of vertices is the diameter of the graph

D = max_{i,j∈V}{d(i, j)}

An isomorphism between two graphs, G_{1} = (V_{1}, A_{1}) and G_{2} = (V_{2}, A_{2}) is a bijection from V_{1} to V_{2} that preserves adjacency. Then G_{1} and G_{2} are said to be isomorphic and represent, in fact, the same graph. An isomorphism of G into itself is called an automorphism. A graph G = (V, E) is bipartite if there exists a partition of V, V = V_{1} ∪ V_{2}, V_{1} ∩ V_{2} = ∅, such that all its edges are incident to a vertex of V_{1} and a vertex of V_{2}.

In a multicomputer system, the communication between processor-memory units requires in general the use of some intermediate network nodes. As a consequence, there are some delays that cause a loss of performance in the system. The smallest delays occur when every computer is directly connected to each other. However, with a large number of computers this structure is not possible because of the limited number of connections that each computer may support owing to of technical and economical reasons.

On the other hand, one of the simplest topologies for interconnection networks is the ring one, in which each node is connected to two others making up a bidirectional loop. This structure has also some inconveniences: a poor reliability (any link or processor failure disconnects the network) and a low performance (some messages must travel along half the ring to reach their destination).

The ring topology can be improved by adding links between nodes in a regular form. If only one link is added to each node the corresponding graphs are 3-regular. This is the case of the chordal ring networks, proposed by Arden and Lee [3] as candidates for efficient and reliable multi-(micro)computer interconnection topologies. These networks have an even number of nodes labelled with the integers 0, 1, 2, …, n − 1, and each even node i is connected to the (i ± 1) mod n and (i + c) mod n for some odd integer c. Consequently, each odd node j is connected to the nodes (j ± 1) mod n and (j − c) mod n. Therefore we have a ring structure with additional links called chords, as shown in figure 1 for n = 14 and c = 9.

Figure 1: A chordal ring ( an empty circle denotes an even node and a black circle an odd node).

It is known that certain families of graphs (and digraphs) can be fully represented by plane tessellations when their vertices are associated with regular polygons [4, 5, 7]. This geometrical representation characterizes the graph and facilitates the study of some of its parameters, particularly those related with the distance.

In section 2 we define one of such families which include, as a particular case, the chordal ring networks and whose vertices are identified with equilateral triangles. The design of efficient generalized chordal ring networks leads, in section 3, to the search for such graphs with maximum order n for a given diameter D. This question is related to the converse optimization problem, considered in section 4, which consists of finding the minimum diameter of a generalized chordal ring graph with given order n. Our study leads to the optimal solutions, in the first case for all values of D and in the second one for infinitely many values of n, thus improving the values given by Arden and Lee in [3].

2 Generalized chordal ring graphs

We consider a family of 3-regular graphs which have an even number n of vertices labelled with the integers modulo n. More precisely, the set of vertices of the generalized chordal ring graph, CR_{n}(a, b, c), is V = V_{0} ∪ V_{1} with V_{0} = {0, 2, 4, …, n − 2} and V_{1} = {1, 3, 5, …, n − 1}. Each vertex i ∈ V_{0} is adjacent to the vertices (modulo n) i + a, i + b, i + c ∈ V_{1}, for three different odd integers a, b, c. Consequently, each vertex j ∈ V, is adjacent to the vertices j − a, j − b, j − C ∈ V_{0}, see figure 2. It is very simple to show that, for any odd integer r, the graphs CR_{n}(a, b, c) and CR_{n}(a + r, b + r, c + r) are isomorphic. Hence, without loss of generality, we can fix one of these parameters, say a = 1. In particular, note that the graphs CR_{n}(1, −1, c) are chordal rings in the sense of Arden and Lee, though they were already introduced by Coxeter [5] in another context.

From the definition, it is clear that the generalized chordal ring graphs are bipartite. Moreover they have a high degree of symmetry because of the existence of the automorphisms i → i + α for α even and i → β − i for β odd. In graph theoretical terminology we say that these graphs are vertex-symmetric.

3 Largest chordal ring networks

In this section we solve the problem of maximizing the number of vertices of a generalized chordal ring graph with any given diameter.

Figure 2:

Let us consider the graph CR_{n}(a, b, c). Its symmetry enables the study of its characteristics from any vertex. For convenience we choose vertex 0. From this vertex, the vertices a, b and c are reached in a single step, the vertices (modulo n) a − b, a − c, b − c, b − a, c − a and c − b are reached after two steps, and so on. If we associate to each even (respectively odd) vertex an equilateral triangle in “right” (respectively “down”) position, these vertices can be arranged in a planar pattern as shown in figure 3.

Note that, because of the particular adjacency conditions, in these graphs there are at most 3l vertices at distance l (> 0) from vertex 0. Therefore, the maximum number of vertices, n_{D}, of a generalized chordal ring graph with diameter D is bounded by

n_{D} ≤ 1 + ∑_{l=1}^{D} 3l = \frac{3}{2}D(D + 1)  (1)

As we shall see, this bound cannot be attained.

Before advancing in our study, notice that, to move between the even vertices we use the “double-steps” ±A, ±B, ±C, where A = b − c, B = c − a and C = a − b = −(A + B). Therefore it is not difficult to show that a necessary and sufficient condition to reach all the even vertices from vertex 0 is

(A, B, C, n) = (a − b, a − c, n) = 2  (2)

Then the odd vertices can also be reached from vertex 0. For more details about the proof, we refer to [4]. In fact, (a − b, a − c, n)/2 is the number of connected components of the graph CR_{n}(a, b, c).

Our study is based in the following two remarks of a geometric nature:

1) Periodicity: Consider the regular tessellation of the infinite plane with equilateral triangles. We number them following the pattern of figure 3 starting with 0 in an arbitrary one of type Δ. Then every triangle contains a number from 0 to n−1 and the distribution of these numbers in the plane repeats itself periodically. This fact is illustrated in figure 4 for the graph CR(1, −1, 9), drawn in figure 1.

2) Tessellation: Assuming that condition (2) holds, form a tile with n triangles labelled from 0 to n − 1. By the stated periodicity, this tile tessellate the plane as shown in figure 4.

Now it is easily seen that, for any diameter D > 1, the tiles corresponding to the maximum number of vertices (1), do not tessellate the plane, see figure 5. Therefore we conclude that the bound (1) is not attained.

Stated in this context our concern is to find and construct (i.e. find integers a, b and c that can generate it) tiles that tessellate the plane and have maximum area (=number of unit triangles) for a given diameter D.

Let us see, first that the bound (1) can be improved. Since the considered graphs are bipartite, the vertices of V_{0} are at even distance of vertex 0, while the vertices of V_{1}, are all at odd distances from it. Therefore the maximum order n_{D} is bounded by twice the number of vertices in V_{0}. (when D is odd) or V_{1} (when D is even) at distance less or equal to D − 1 from vertex 0. Therefore, we have Figure 4: Periodic pattern of CR_{14}(1, −1, 9). Figure 5: Tiles with n(area)= \frac{3}{2}D(D + 1)

n_{D} = 2(1 + ∑_{l=2,even}^{D−1} 3l) = \frac{3D^{2} + 1}{2} D odd  (3a)

n_{D} = 2 ∑_{l=1,odd}^{D−1} 3l = \frac{3D^{2}}{2} D even  (3b)

We next show that this bound can be attained when D is odd but cannot when D is even, D > 2. In the first case the appropiate tile is the shaded polygon of figure 5(a) which tessellates the plane as shown in figure 6(a).

Figure 6:

It remains to show that it can be generated by an adequate choice of a, b and c. For this it suffices that these values produce the given periodic pattern, which is characterized by the position of the “zeros”. To obtain this distribution we have to express the null effect of translations along two independent vectors (each of them associated to a path as shown in figure 6) that generate the pattern. Choosing them as in figure 6, a, b and c must satisfy

\frac{D − 1}{2}a + \frac{D + 1}{2}b − Dc = 0  (mod n)  (4)
−Da + \frac{D − 1}{2}b + \frac{D + 1}{2}c = 0  (mod n)

together with condition (2) that prevents the presence of any other zeros within each tile.

System (4) can be solved by fixing a = 1 and writting (in matrix form), for some integers α and β

( \frac{D+1}{2} −D_{\frac{D−1}{2} \frac{D+1}{2}} ) ( \begin{matrix}b \\ c \end{matrix} ) = ( \begin{matrix}α \\ β \end{matrix} ) n_{D} + ( \begin{matrix}−\frac{D−1}{2} \\ D \end{matrix} )  (5)

so that its solutions, that can be understood modulo n_{D}, are given by

( \begin{matrix}b \\ c \end{matrix} ) = ( \begin{matrix}D + 1 & 2D \\ −D + 1 & D + 1 \end{matrix} ) ( \begin{matrix}α \\ β \end{matrix} ) + ( \begin{matrix}1 \\ 1 \end{matrix} )  (6)

For instance, for α = −2, β = 1, we obtain the solutions b = −1 and c = 3D which, jointly with a = 1, trivially satisfy (2).

The study for D even is similar but now the tile with maximum area \frac{3D^{2}}{2} , that also tessellates the plane, (shaded area of figure 5(b) ) leads always to a system whose solutions do not satisfy (2) when D > 2. Hence this tile cannot be generated and we must to look for smaller ones.

The best we can do is to use the tile bordered by heavy lines in figure 5(b), obtained from the optimal shaded one by removing a shortest row of adjacent triangles. This tile corresponds to the number of vertices ( i.e. has area) n_{D} = \frac{3D^{2}}{2} − D and tessellates the plane as shown in figure 6(b). From this figure, the equations for the distribution of the zeros are now

\frac{D − 2}{2}a + \frac{D}{2} b − (D − 1)c = 0  (mod n_{D})  (7)
−Da + \frac{D}{2} b + \frac{D}{2} c = 0  (mod n_{D})

with solutions, say, a = 1 and

( \begin{matrix}b \\ c \end{matrix} ) = ( \begin{matrix}D & 2(D − 1) \\ −D & D \end{matrix} ) ( \begin{matrix}α \\ β \end{matrix} ) + ( \begin{matrix}1 \\ 1 \end{matrix} )  (8)

for any integers α and β. For instance, for α = −2 and β = 1 we obtain b = −1 and c = 3D + 1. These values clearly satisfy (2) and, so, they generate the tile.

Summarizing, we have obtained two families of chordal ring graphs with maximum number of vertices for any given diameter, namely:

D odd:  CR_{n_{D}}(1, −1, 3D), n_{D} = \frac{3D^{2} + 1}{2}  (9)
D even:  CR_{n_{D}}(1, −1, 3D + 1), n_{D} = \frac{3D^{2}}{2} − D (D > 2)

(For D = 2, we have the graph CR_{6}(1, −1, 3) that does attain the bound (3b).) For D = 3, CR_{14}(1, −1, 9) is the so-called Heawood graph of figure 1 and whose tessellation is shown in figure 4.

These values of n_{D} improve those of Arden and Lee in [3] that where n_{D} = D^{2} + 2D − 6 for D ≥ 5 odd and n_{D} = D^{2} + 3D − 12 for D ≥ 8 even .

4 Chordal ring networks with minimum diameter

The problem of minimizing the diameter of a generalized chordal ring graph with given number of vertices n is much more difficult to solve than the one considered in section 3. This is due mainly to the fact that the diameter of these graphs does not always increase with n. For example, the minimum diameter for 46 vertices is D = 7, take for instance CR_{46}(1, 19, 1), whereas the graph CR_{48}(1, 19, −1) on 48 vertices has diameter D = 6. Therefore, no close formula giving the minimum diameter as a function of the number of vertices seems to exist.

Using the geometrical representation of the graph the problem is now to find constructible tiles with given area n, that tessellate the plane and correspond to graphs with minimum diameter.

Some of these tiles can be obtained from the ones associated to the largest graphs, with order n_{D}. given in [4], by removing some outer rows of adjacent pairs of triangles as shown in figures 7 and 8. The way of finding values a, b and c that generate the depicted tiles is essentially the same than in section 3.

Table I gives the results obtained for each corresponding values of n. Note that in all cases we have values 1 and −1, so that the graphs are chordal rings.

\begin{matrix}n & D & a & b & c \\ 6p^{2} + 4p & 2p + 1 & −1 & −6p − 1 & 1 \\ 6p^{2} + 2p − 2 & 2p + 1 & −1 & −6p + 1 & 1 \\ 6p^{2} + 2p & 2p + 1 & −1 & 6p − 1 & 1 \\ 6p^{2} − 2 & 2p + 1 & 1 & -1 & −6p + 3 \\ 6p^{2} + −4p & 2p & 1 & -1 & −6p + 1 \end{matrix} Table 1:

Figure 8: 11

References

[1] N.Deo, Graph Theory with Applications to Engineering and Computer Science. Englewood Cliffs, NJ: Prentice-Hall, 1974.

[2] J.C.Bermond, C.Delorme and J.J.Quisquater, “Strategies for interconnection networks: some methods from graph theory”, J. of Parallel and Distributed Computing, 3 (1986), pp. 433–449 .

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

[4] Yebra, J.L.A., Fiol, M.A., Morillo, P., Alegre, I. The diameter of undirected graphs associated to plane tessellations. Ars Combinatoria, 20B (1985), pp. 159–172.

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

[6] H.B.M.Coxeter, “Self-dual configurations and regular graphs”, Bull. Amer. Math. Soc., 56 (1950) , pp. 413–455.

[7] Wong, C.K., Coppersmith, D. “A combinatorial problem related to multimodule memory organizations”. J. Assoc. Comput. Mach., 21 (1974), pp. 392–402.