A Comparative Study of Doubly Connected Directed Topologies for LANs and MANs Tein Y. Chung Computer Engineering and Science Department, Yan-Ze Institute of Technology, Taipei, Taiwan 104 Dharma P. Agrawal, Suresh Rai, and Tzau J. Chung Electrical and Computer Engineering, Box 791 1, North Carolina State University, Raleigh, North Carolina 27695-7911 ; E-mail: dpa@ncsu.edu This article provides an overview of doubly linked networks. We first classify the doubly linked network on the basis of the number of tuples used to represent each node address in the network. Then, each subclass of network is further partitioned into loop or nonloop categories. Various routing algorithms are studied and grouped into static or adaptive routing type, based on the number of paths between nodes used in the point-to-point message transmission. The useful protocols of the token ring and the register insertion ring and their relative advantages are also described. Some issues, such as multiple destinationsrouting, graceful degradation on cluster faults, and network behavior under unbalanced traffic conditions, in a doubly linked network are still open. There seems to be a need for new protocols when optical fiber is used as the medium for message transmission, which necessitates high-quality and large bandwidth data transmission. 0 7 996 John Wiley & Sons, Inc. INTRODUCTION As workstations and personal computers have become popular, the networks for interconnecting these small computers in the form of local area networks [ 11 ( LANs) or metropolitan area networks (MANs) have received greater interest in recent years. The LAN and MAN are relatively cheaper to implement while providing users the function of facility sharing and distributed processing [2]. Since the way computers (or topology) are interconnected affects network performance, it is very useful to compare various topologies in terms of appropriate performance parameters, such as the network diameter, defined as the maximum value of the distance between any pair of network nodes along the shortest path and the average path Icwgrh, representing an average communication delay from a source node to an arbitrary destination. In the past, both bus and ring topologies [ 11 have received great interest for the interconnection of computers NETWORKS, VOI. 27 (1996) 35-51 0 1996 John Wiley & Sons, Inc. in local areas and wide areas. A bus allows its attached computers to exchange information in a single hop. However, transmission conflict occurs when several computers try to access the bus at the same time. This led to the development of CSMA/CD and token bus protocols [ 11 for scheduling access to a bus. While the bus topology seems to provide the shortest possible diameter and average distance for LANs and wide area networks ( WANs), its characteristics are altogether very different from the fiber optics, which, theoretically, provides unlimited bandwidth and high-quality signal transmission. Therefore, the bus topology has limited application in the future high-speed multimedia information world. The other very popular way of implementing LANs is a single-directed loop such as a token ring with the IEEE 802.5 protocol. The directed feature of the ring-type networks fits very well with that of fiber optics. In fact, a ring type of network, the Fiber Data Distributed Interface (FDDI ) [ I 1, has been implemented using fiber optic links CCC 0028-3045/96/010035-17 35 36 CHUNG ET AL. and the directed network is expected to continue as the main stream for high-speed fiber optic network designs. In this paper, we are concerned only with the directed type of networks. Although a single directed loop network has become very popular as a LAN, its diameter and, hence, the maximum communication delay, in terms of number of hops between a pair of nodes, is equal to the network size minus one and its average path length is equal to half the size of the network. These performance parameters become prohibitively large even in an average-size network. Moreover, a link failure causes the loop to be disconnected. A costeffective alternative [ 221 for improving the reliability and the network performance of a directed loops is to increase the degree of each node to two, which allows the use of several methodologies in defining the network topologies suitable for LANs and MANs. In this article, we review various two-input and two-output networks and compare their underlying attributes and the performance parameters. To examine the characteristics of a computer network, a graph is used to model the computer network by representing the computers and their links, respectively, by the nodes and edges of the graph. A network is modeled by a directed graph (digraph) by showing unidirectional communication links by directed edges while representing an undirected edge by two directed edges. Thus, a digraph is seen to model a more general class of topologies than do undirected graphs and it is practical to consider only the digraph model of computer networks. The topologies for LANs and MANs are classified by their employed addressing schemes, i.e., the number of tuples (or dimensions) used in representing the node addresses (Box A ) . For instance, a network is classified as an m-dimensional network if the addresses of all nodes in the network are denoted in an m-tuple form (a,, a,-l, . . . , al). Each subclass of networks is again divided as a loop-type and a nonloop-type network. A network is a loop type if a directed loop (not self-loop) exists in the network and the addresses of the nodes connected by the loop only differ in one address tuple. Furthermore, a loop is formed by links given by equation of the type b = ( a +- 1 ) mod m . Examples of such one-dimensional loop-type networks include the distributed double-loop computer network [ 221 (DDLCN), daisy chain [ 15 1, forward loop backward hop [ 2 2 ] (FLBH), and some of the optimal circulant digraphs [ 131. On the other hand, a network is a nonloop type if it does not contain such a directed loop. The de Bruijn network [ 181 presents one example of such a network. It is clear that loop-type graphs are suitable for LANs or MANs as they can be easily extended from existing ring networks. We next examine the subject of message routing. In this article, we consider only deterministic techniques, as such algorithms employ a set of topology-dependent rules loop --C Circulant loop digraph e g . UDLCN, daisy chain FLBH, optimized circulant digraph --c Generalized de Bruijn digraph and its variants I mesh connected network wlth 2 and 3 lump choices. Manhattan Street Network I Doubly-connected m-dimensional networks L Line digraph lteratlon one time from an 1-D digraph, d e Erui7n digraph of s i z e 4 I a 0 0 loop r-dimensional loop * networks with s i z e ’ n=Xr*..*% +Line digraph iteration ( r - 1 ) Box A. Classification of various 2-in and 2-out networks. which are observed to be efficient and popular [ 241. Con. trary to this, a random routing is topology-independen’ and a node transmits a message to a randomly selectec output link except when the destination node is adjacent to it. In addition, we also discuss the usefulness of loopbased protocols for doubly linked networks. AN OVERVIEW OF VARIOUS TOPOLOGIES Preliminaries As mentioned earlier, a computer network is modeled as a digraph G( n , d ) , where “n” is the number of computers in the network and ‘‘d” is the maximum number of communication links one processor connects to other processors. The vertices or nodes V (G ) in this digraph represent the processors and interconnecting communication lines are indicated by the edges or links E( G). For completeness of this article, several graph theoretic terms are defined (refer to Box B). These include in-degree, out-degree, diameter. average path length, node (link) connectivity, regular, d-regular, symmetry, isomorphic, k-optimal, self-routing, circulant digraph, and strongly connected digraph. Box C contains common abbreviations and the notations used. Considering the nodes V ( G ) in a one-dimensional network and labeling them (0, . . . , n - 1 ), the hop length from any node i to node j is expressed as ( j - i) mod n . In an m-dimensional network, the network size n is represented as X,,, X X,-, X . . . X XI and a node 0 5 n, I( n - 1 ) is denoted by m-tuple ( a r n ,a m - l , . . . , a l ) , DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS BOX B. COMMONLY USED TERMS BOX C Out(in)-degree: The out(in)-degree represents the number of minimum outward (inward) links of a node in a network. Network diameter: The diameter of a network is the maximum value of the shortest path (number of hops) between any pair of nodes in the network and thus represents the maximum point-to-point possible message transmission delay of the network. Average path length: The average path length of the network is the average of the path lengths between all node pairs and, therefore, symbolizes the average message delay in the network. Node (link) connectivity: The node (link or edge) connectivity of a digraph G is the minimum number of nodes C,’,(G) [edges C,(C)] whose removal will disconnect G. Hence, the node and link connectivities indicate the reliability of a network. For any dregular network, C,,(C)I C,(G)I d. Regular (irregular) network: A network is said to be regular (irregular) if the degree of all its nodes are (not) equal. &Regular network: A network is d-regular if the network is regular and both the out-degree and indegree of every node in the network are exactly d. Symmetric network: A network is said to be symmetric if every node views the network identically. Isomorphic graphs: Two graphs G I and Gz are isomorphic if they differ only in their node labeling and one could be mapped as another (or there is one to one correspondence between nodes of the two graphs). k-Optimal: A network is k-optimal if C,(G) = d. Self-routing: A network possesses the self-routing property if for any given any pair of nodes i a n d j in the network a path (z, j ) can be determined by i and .j alone. Circulant digraph: A direct graph is a circulant if node i is connected t o j when (j - i) mod n belongs to its jump choices S. Hence, a circulant graph G(n, S) consists of nodes V(G)= (0, I , 2, . . . ,n - I ) and edges E(G)?where edge (i, j) E E(G) iff 0’ - i) mod n=.r,wheres€S,S{1,2 , . . . , n - l ) , a n d n > l . Obviously, a circulant digraph is symmetric and is k-optimal if it satisfies any one of the following two suficient conditions: ( 1 ) g.c.d.(n, s) = 1 for all s E S; (g.c.d. meaning the greatest common divisor); (2) i E S for i = I , 2, . . . , rISl/21, where 1st denotes the number of elements in S. Strongly connected digraph: A digraph G is said to be strongly connected if there is at least one directed path from each vertex to every other vertex. (a) Common Abbreviations 37 DDLCN: Distributed double loop computer network FLBH: forward loop backward hop g.c.d.: greatest common divisor LAN: Local area network MAN: Metropolitan area network MSN: Manhattan street network (b) Notations Used (d, k ) digraph: A digraph designed by using (d, k ) and (d, n) problem methodogy. G(n, 4: A digraph with n nodes and d maximum adjacent nodes that a node has. V(G):The set of vertices or nodes in graph G. E(G):The set of links or edges in graph G. C,(G) [edges C,(G)]:Node (link) connectivity of graph G. X I :The ith dimensional size for a multidimensional network. U’,: The weight of the ith address field for a multidimensional network. S: Jump choice set or, in the other words, the set of hop length. Gs: A generalized de Bruijn digraph. G,: A variant of a generalized de Bruijn digraph. D, and H,: A modified de Bruijn digraph with n nodes. LST: Local address table L(G): Line digraph of graph G. where 0 I a,< X I . Associated with each address field is a weight W, such that C a, X U< = n, , where 1- I w,= n x,= x,-1 x XI-, . . . x XI. /= I Hence, the hop length of a link connecting node n,, ( a m r am-,, . . . , a l ), to node n,, denoted as (b,,, bm-,, . . . , bl ), with exactly identical address fields except a, and b, , is given as [ ( h , - a, )mod X , ] X W,. The number of different hop lengths that exist in a network is referred to as the number of jump choices 1 S / and a subset of jump choices are used at each node in defining the topology. To utilize all hop lengths in set I SI , a tree is constructed in a breadth-first manner from a node until all jump choices have been used at least once by the spanned nodes. The maximum height of such trees constructed from any reference nodes is referred as the spanning radius [ 7 ] (SPR) of the network. 38 CHUNG ET AL. Fig. 1. Circulant digraph G(12,{2,5]). One-dimensional Networks Directed Circulant Loop Networks (Circulant Digraphs) Circulant digraphs G( n , S ) are networks that have I S jump choices, and there is a directed edge from node i to j iff ( . j - i) mod n = .s, where s E S . For 2-input 2-output networks, 1 S / is equal to two. Therefore, all such onedimensional networks can be represented by circulant digraph notation G( n , { s,, s2 } ) if every node i is linked to nodes [(i + s , ) m o d n ] and [(i s2)mod n ] . Figure 1 shows an example of circulant digraph G ( 12, { 2, 5 ] ). It is obvious that if 1 E S the circulant digraphs G ( n , S ) are of loop type; otherwise they are nonloop type. Since a circulant digraph G( n , { I , s } ) can be naturally extended from a single-ring network, it has become very popular in recent years. It has been proved [ 251 that the lower bound for this class of loop circulant digraphs is r 13nl - 2. For a given diameter k 2 3 , an exact formula has also been obtained [ 161 to give a network, with maximal size n = ~ k ( k 4)/3] I , that has a diameter smaller than or equal to k . A circulant digraph G ( n , { l , s } ) is optimal if its diameter is equal to its lower bound. An optimal loop circulant digraph, of course, is the network that possesses the maximal network size n given. Fiol et al. [I31 obtained analytic solutions for some values of n by optimally selecting s, and s2.However, an optimal network for most network sizes could be obtained only by an exhaustive computer search and is usually not unique. It is found that for almost all network sizes there exists a solution with sI = I , except for some exceptional values of n . Hwang and Xu [ 171 also developed a heuristic method to determine s such that the loop-type circulant digraphs G( n , { 1, s } ) are near-optimal or optimal. They also give some infinite classes of N for which optimal loop- + + type topologies can be found. Erdos and Hsu [I21 presented a systematic and unified approach for designing optimal or near-optimal G( n , { 1, s ) ). The approach is demonstrated for several classes of N in obtaining optimal networks. Besides, they show that a G( n , { I , s } ) close to optimal can always be constructed asymptotically for reasonably large N . Hwang and Xu’s and Erdos and Hsu’s works enable us to design optimal or near-optimal loop circulant networks without any exhaustive computer search. Raghavendra and Gerla [22] also studied a class of loop networks G( n , { 1, n - 1vn 1 } ) ,called optimal FLBH. This class of networks, however, is not optimal most of time [ 121. An example of an optimal FLBH network with 12 nodes and s = 3 is given in Figure 2. Earlier attempts to design reliable and fault tolerant network led to the DDLCN [22] and the daisy chain [15], which are subclasses of loop-type circulant digraphs and, hence, belong to G( n , { I , r2 } ). Although DDLC“ and daisy chain networks (Fig. 3 ) are far from optimal, their topologies are very appropriate for real-world applications. Parameters for these circulant digraphs are listed in Table I. ( d , k ) Nonloop Networks In the past, a special class of networks, called ( d , k ) digraphs, was derived for solving the N ( d , k ) and k ( d , n ) digraph problems. The N ( d , k ) digraph problem maximizes the number of nodes “n” for a given maximum out-degree “ d ” and network diameter “k” such that “n” is close to the Moore bound of [ d” ’ / ( d - 1 )]. It is known that this bound cannot be attained [ 3 ] for d > 1 and k > I . The k ( d , n ) digraph problem minimizes k for a given out-degree d and nodes n . It can be shown that the lower bound for k is Llogd n J . Among the ( d , k ) networks, de Bruijn digraphs [ 181 are the most widely known ( d , k ) digraphs that have d” + Fig. 2. FLBH with n = 12, s = 3. DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS 39 Although some Gu and GI possess Hamitonian circuits [ 1 11 for d = 2, they generally do not contain a loop [ 121 and are not suitable for LANs or MANS. The de Bruijn networks, however, are useful for the construction of multistage networks, such as Stone’s shuffle-exchange network and Laurie’s Q-network and a recently introduced [ 41 class of a scalable hierarchical network. Two-dimensional Loop Networks In a two-dimensional network group, each node address is represented by two-tuples ( a , , a 2 ) . For a two-dimensional loop network, n is expressed as m , X m2 and the generalized link equations for these networks are expressed as Fig. 3. Daisy chain network for 12 nodes. nodes with each node represented by an m-tuple of radixd or d-ary notation. This digraph possesses a very simple self-routing property, while the design is feasible only for some specific values of n and the in-degree and/or the out-degree is not constant for all nodes (Fig. 4 ) . Hence, most recent researchers have concentrated on designing a topology without any restriction on n and making the node connectivity close to d-regular. Link equations for the generalized de Bruijn digraphs are as follows: given i, obtain; = ( a X 2 ‘ + 6 , ) mod n ; for all 6, E b , where a is a constant and b is a set consisting of two integer elements. Figure 5 shows such a generalized de Bruijn digraph GB [ 181 with the coefficients of the link equations a = I and b = { 0, 1 } . However, the node connectivity is impaired by the presence of at least two selfloops. One possible way of improving the node connectivity of GB is to eliminate the self-loops by altering the corresponding connection patterns. Examples of such modified de Bruijn’s digraphs include D, and H n digraphs [ l o ] as shown in Figure 6, while the topologies are described in Table 11. The other variant of de Bruijn digraph, the GI graph [I91 (Fig. 7 ) , has link equations with coefficients a = -1 and h = { - 1. -2 1. GI may have self-loops at node i when 1 = ( n - l ) / 3 , ( n - 2)/3, ( 2 n - 1)/3, or ( 2 n - 2 ) / 3 . Thus, the node connectivity is not improved for all values of n . But, as compared to GB,GI does not always contain self-loops. In fact, a 2-regular G I , or a network with indegree = out-degree = 2, can be constructed if n = 2 h 2h I . Another similar digraph isomorphic to GI has been designed by Fiol et al. [ 141 which has coefficients a = - I and h = { I , 2 ) . + + where o p , and op2 are the arithmetic operator or -. Three such loop networks (Fig. 8 ) are the 4-ary 2-cube [9] , the mesh-connected network with three jump choices [ 7 ] and the Manhattan street network [ 201 (MSN). For a 4-ary 2-cube, the op, and op2 are always while for MSN, they can be either or - depending on ( a , ,a*). In a mesh with three jump choices, only up, or up, can be while the other can be either or - as a function of one particular address field. For example, node ( 3 , 2) in a 6 X 4 MSN is connected to node ( ( 3 1 ) mod 6 , 2 ) or node (4, 2 ) , and node ( 3 , ( 2 - 1 ) mod 4 ) or node (3. 1 ) . Here, o p 1 / o p 2= +(-) i f u 2 / a l iseven ( odd) . Chung et al. [ 5 , 7 ] observed that for the mesh-connected networks the larger the number ofjump choices is the smaller the network diameter and the average path length are. Hence, MSN satisfying this property has the best parameters (Table 111) among these three networks. The network diameter and average path length of these networks are given in Table IV. +, + +, + + M-dimensional Networks Loop Network Extending the above concept of a mesh-connected network, Chung et al. [ 7 ] proposed the design of an m-dimensional network where n is represented as the multiplication of m integers, say .Ti, X X . . . X X , . Each node is denoted as an m-tuple address and is selectively connected to two other nodes with the address differing in only one field. The format of the link equations are exactly similar to the mesh network. Since, for the link equation, each address field could be either increased or decreased, an m-dimensional network can have up to 2 X m different hop lengths or jump choices. A spanning 40 CHUNG ET AL. '2 II h 'k I I $ z E __ 2 I c DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS D 41 S 100 001 110 011 Fig. 5. lmase and Itoh's G, (12,2) (unmodified). Fig. 4. 3-D de Bruijn digraph for eight nodes [the dotted lines show the routing path from (001) to (loo)]. radius and the number ofjump choices are both effective attributes in representing a configuration with a better network diameter and average path length. As seen from the simulation results of Table IV, an rn-dimensional network [ 6 ] performs better when the number of jump choices is increased. ( d , k ) Nonloop Network The de Bruijn digraph and the line digraph iteration are the two noteworthy approaches under this category. In a de Bruijn digraph of size d'", rn dictates the dimension while two self-loops always exist for nodes 0 and (d'" - 1 ) . The line digraph [ 141 addresses the ( d , k ) digraph problem by using a 1 -dimension d-regular digraph as the base. The corresponding line digraph could be constructed by utilizing the method given in Table I1 with each iteration extending it to one higher dimensional network. As illustrated in Figure 9, the address field contains the digits denoting the original graph. COMPARISON OF NETWORKS Generally, there are three factors in selecting a network topology: ( 1 ) the performance parameters, ( 2 ) the ex- Fig. 6. (a) Du et al.'s D,2 (H,*) (where the dotted links are to be removed when is constructed. (b) H,3 (where the dotted links are the added modified links and the dotted node is the added node. 42 CHUNG ET AL. U $ 3 Y: w '- c DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS 43 works are equally simple because of the self-routing property. The ( d , k ) networks, of course, do not seem as appropriate for LAN and MAN as compared to others. The simulation results for loop networks shown in Table IV indicate that an m-dimensional loop network performs better in terms of diameter and reliability when n is large. However, for an m-dimensional network, the network size restriction makes it less attractive as compared to a circulant digraph. From an expandability viewpoint, DDLCN is the most attractive option. As far as W Fig. 7. lmase and Itoh's G, with 12 nodes (n = 2 k + 2k-' for k = 3). pandability, and ( 3 ) the application. Parameters such as diameter affect its average path length, node connectivity, and reliability. The expandability is important for the network evolution. It is desirable that when a node is added the network should be modified as little as possible while the network characteristics ought to be kept nearly unchanged. The application, on the other hand, is related to geographic suitability of the topology and the routing simplicity. In ( d , k ) networks, GI performs better than do any other networks in terms of the diameter and size (or order) restrictions. Line digraph iteration, on the other hand, is limited to 2" X n nodes, where n is the size of the initial digraph, although it is possible to construct C, of size 2 k 2'-' with the smallest diameter rlog,nl - 1. From the reliability aspect [ 8 3 , 13, is k-optimal and has the best node connectivity among the generalized de Bruijn digraph and its variants. Actually, H, is evolved from D, by modifying links in D,when n is odd. As could be easily seen, for odd n and n 2 5, there does not always exist a directed path between all node pairs in D, (i.e., D, is not strongly connected) when node L(n - 1 )/2 J is removed. Figure 6 ( b ) shows how H, is constructed from H,- I ( DnP1) by adding a node number ( n - 1 ) and two links and modifying two link connections ( n - 1 ) / 2 --* 0 and 0 --* ( n - 2) to improve the node connectivity. The self-loop in the ( d , k ) networks allows addition of nodes without affecting the network property. From the routing point of view, H , with odd n is the worst topology as the modified links make the routing between nodes require some additional information other than the source and destination addresses. This means that the self-routing property of GB is no longer valid. Routing in all other ( d , k ) net- + (a) 4-ary 2-cube network (b) Mesh connected network having three jump choices (c) Manhattan Street Network (MSN) Fig. 8. Two-dimensional loop networks: (a) 4-ary 2-cube network; (b) mesh-connected network having three jump choices; (c) Manhattan street network (MSN). 44 CHUNG ET AL. routing simplicity is concerned, all circulant loop digraphs and two-dimensional loop networks perform better if only shortest paths between nodes are to be used. It is clear that a complicated shortest path routing algorithm is needed for loop networks with a dimension higher than 2. Networks belonging to (or designed as per) different classifications are not necessarily completely disjoint. For example, four-node DDLCN is isomorphic to all twodimensional loop networks of the same size, while GI of size 2' 2'- ' is isomorphic to the line digraph iterated ( k - 1 ) times from a DDLCN of three nodes. In fact, the de Bruijn digraph can also be constructed by a line digraph iteration. Therefore, the address system need not necessarily indicate a network to be of a unique class. + ROUTING ALGORITHMS The deterministic routing algorithms are classified as either static or adaptive [24]. A static algorithm always employs a predetermined fixed path between a given node pair. In an adaptive algorithm, nevertheless, an alternate path is selected when the network traffic pattern enforces this to happen. Since there is a unique shortest path between the nodes in almost all ( d , k ) graphs, generally, the shortest path algorithm for a ( d , k ) graph network turns out to be static. However, in a line digraph iterated from a digraph G, several shortest paths can exist if G possesses multiple shortest paths between nodes. Thus, whether the shortest routing scheme is static or adaptive depends on the base graph G. Static Routing in Loop Networks In this case, we describe routing schemes proposed for the forward loop backward hop network and a two-dimensional loop network with two jump choices, which represent typical examples of one- and two-dimensional loop topology, respectively. Forward Loop Backward Hop Networks Raghavendra et al. [22] proposed a routing algorithm based on a local address table (LST) (Fig. 10) which contains addresses of all nodes with an undirected distance less than the backward jump distance. The algorithm first matches the destination address with the LST and then, based on the search result, selects the forward or backward link. This algorithm is static and fails to utilize the selfrouting characteristics of the network. Moreover, it cannot prevent a loop of the link waiting queues and, hence, is poor in avoiding a deadlock. However, as the links and nodes status are reflected through LST, faults can be bypassed effectively. DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS Two-dimensional Loop Network with Two Jump Choices L 9 2c c 2 m W 0 9 .-Y) s - h h I N ‘4 5 a 9 a0 2 W h N, N “: L -2 0 L c W 9 - E m 6 Y + N, Y EW c + z c W 0 c c G w -+ Dally and Seitz [ 91 proposed a fixed routing scheme for 3-ary 2-cube in which deadlock is prevented by eliminating the loop of link waiting queues. In their algorithm, each link is identified by its dimension and the node from which it emerges (Fig. 1 1 ). Each link is associated with two virtual channels, upper channel 1 and lower channel 0, and each channel has its own queue. The upper channel is used when the transmission in the chosen direction is from a smaller address field to a larger one; otherwise, the lower channel is chosen. These virtual channels are denoted in the form ‘Guvx,”where z1 is the dimension, v is the channel type, and x identifies the source node of the channel. For instance, the upper channel for link LOO 1 is identified as 0- 1-01. So, the routing is done starting from the one-dimensional plane until that address field is matched and, then, follows the zero-dimensional plane. Deadlock is prevented by restricting the routing path to follow channels of descending order [ 91. Considering the message transmission from node 10 to 0 1, e.g., the message is first routed to 00, then to 02, and, finally, to 01. The channel selected in each link corresponding to the routing path is the lower channel from 10 to 00, the upper channel from 00 to 02, and the lower channel from 02 to 01. Therefore, the channel sequence is from channel 1-0-10, through 0- 1-00, to 0-0-02, which is in a descending order. This routing scheme is vulnerable to the faults, and if an alternate path is used to bypass a fault, the traversed path is no longer guaranteed to be loop-free. Also, only one path out of many available paths between nodes is used. Hence, the routing flexibility in using the self-routing property is sacrificed by the deadlock prevention. + N 0 .-c 45 Z+ -+ G- Static Routing in ( d , k ) Networks de Bruijn Digraph and Its Variants The static routing scheme for de Bruijn digraphs selects a link such that there is a better match between the highorder bits of the destination address and the low-order bits of the current address. A link is identified as 0 or 1 if a link connects to a node whose least significant bit of the address is 0 or 1, respectively. As an example, a path from source 00 1 to destination 100 is shown by the dotted line in Figure 4. Initially, the matched bit number is one. To increase the match bit number to two, link 0 is selected and leads to 010. Next, link 0 is chosen to reach the destination. The scheme for GBis to rout the message according to the sequence of the m-tuple 2-ary number (a,, a,-l, . . . , a l )representing the residue (v - 2 ~ * 2 ~ ) m on d, where U , v, and k are the source, destination, and diameter, respectively. The rule is to route the messages along the link with connection pattern 2*i 1 (mod n ) or 2*i(mod n ) + 46 CHUNG ET AL. I I I Fig. 11. Deadlock free routing for a mesh network with 2 jump choices (L represents “link”). depending on whether a, = 1 or a, = 0, respectively, and starts downward from a,,, until the destination is reached. Taking the same source “ 1 ” and destination “4” in the last section as an example, the 3-tuple 2-ary representation of residue ( 1 - 4*2 3, mod 8 is (0, 0, I ). Therefore, the routing path is from node “ 1 ” through node “2” to node “4,” which is the same path as the routing scheme of the last section. The routing scheme for GI is the same as that of Go except that the a, is assigned the value 1” and “0” corresponding to the connection patterns -2*i - 1 (mod n ) and - 2 * i - 2( mod n ) , when n is even. When n is odd, the residue is modified to be [ v - ( 2 1 1)*2‘] mod n and the m-tuple 2-ary number ((I,,, a,,,. , . . . , a , ) is the complement of the residue’s m-tuple 2-ary expression. “ + , (c) L(L(G(4))) Fig. 9. Line digraph starting with DDLCN of four nodes (the dotted lines show how two shortest paths between node (121) and (3011: (a) G(4); (b) L(G(4)); (c) L(L(G(4))). forward direction7, ,7T backward direction Line Iteration Digraph The routing algorithm for a line iteration digraph is very close to that of the de Bruijn digraph [ 141. It first matches the low-order digits of the destination address with the high-order digits of the current node. If some of them match, then the unmatched part of the destination address digits determines the routing path. If no match exists, the shortest path between the highest-order digit of the current node address and the lowest-order digit of the destination address is taken up. For example, consider the 3-node digraph G of Figure 12( a ) with address digits: 0, 1, and 2. To transmit a message from node ( 12 1 ) to node (20 1 ) in the line digraph L ( L ( G ) )of Figure 12(b), the first selection is the shortest path from 1 to 2 in G, which is unique in Figure 12(a) and leads to corresponding node (212) of Figure 12(b). Then, the next path is based on the unmatched high-order digits 0 and 1, which leads to a path from ( 2 12) to ( 2 10) through ( 120). The routing for this example is static due to the uniqueness of the shortest path between nodes in G . Another example employing this algorithm as an adaptive one is shown in Figure 9( c), which possesses two shortest paths from node 1 to 3. DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS 47 Manhattan Street Network (Mesh Connected Network with Four Jump Choices) Fig. 12. Static routing in line digraph: (a) original fully connected digraph G; (b) line digraph after two times iteration [the dotted lines show the routing path from (121) to (201)l. Adaptive Routing Forward Loop Backward Hop Network In this algorithm, the necessary routing information [ 231 is kept in the two counters associated with the header of every message. These counters keep the updated record of the number of forward and backward hops required to transmit the message and are initialized at the message origination. The output link corresponding to the nonzero counter is a candidate to be selected as the message transmission path. Each time a message is transmitted, the counter corresponding to the selected link is decreased by 1, and the destination is reached when both counters become zero. This algorithm utilizes the self-routing characteristics in computing the initial values of the counters and routes the messages only according to the counters, thereby routing the messages adaptively to the traffic conditions. However, since the fault information is not recorded at any node, a message may possibly be kept routing in the network without ever reaching the destination (or livelocked) when the faults are present. Also, this algorithm cannot prevent a deadlock. Routing in the Manhattan street network (MSN), being cyclic in structure, is dependent only upon the relative location of the current node with respect to the destination. Hence, the routing schemes [21] for the MSN are based on the relative address space, instead of the real address space. The routing schemes divide the relative address space ( a z , a , ) into four quadrants, as shown in Figure 13(c), and consider the preferred routing direction differently for each quadrant. To route the messages along the shortest paths between any pair of nodes, the routing decision for the nodes located at ( 1 ) the outer boundaries of quadrant 1 and 3 and ( 2 ) the boundaries along the axes in quadrant 2 and quadrant 4, shown as a shadowed area in Figure 13(b) , are considered differently from those nodes in the same quadrant. However, if we neglect the difference in the routing decision for the nodes in ( 1 ), a simpler routing scheme [ 2 I ] is obtained, while only a very small number of nonshortest paths are occasionally selected. A simpler routing scheme [20] is obtained if we consider only the routing decision differently for those nodes located at the boundaries along the y axis in quadrant 2 and the ,Y axis in quadrant 4 and is illustrated in Figure 13(c ) . Once the preferred routing direction is decided, a message is transmitted from the current node to the outgoing link that matches the preferred routing direction. If none or both of the outgoing links of the current node matches the preferred routing directions, a message is transmitted to a randomly selected outgoing link. The fault-tolerant capability of this routing scheme totally relies on the presence of the multiple paths between the node pair so that faulty elements are avoided by adaptive message routing. But messages may possibly be livelocked under a faulty environment because of the lack of the fault information. COMPARISON OF ROUTING ALGORITHMS It has been observed that the performance of an adaptive routing scheme heavily depends on the traffic load of the network. These studies, however, assume that each node maintains a list of alternate paths of different lengths and a set of criteria is defined to pick an alternate path as per existing traffic and fault condition. Thus, the adaptive routing algorithm is not attractive in practical applications if the alternate paths are longer than the original path. Nevertheless, in a regular network, such as FLBH and 3ary 2-cube networks, multiple shortest paths do exist and an adaptive routing performs well even under heavy loads. On the other hand, the adaptive routing may result in an unordered sequence of messages transmission, while a static algorithm always transmits messages in the right 48 CHUNG ET AL. (a) Absolute address for each node in MSN . Relative address for the other nodes with respect to the destination node whose relative address is (0,O). n Boundary along the axes Outer boundary of the quadrant r>O c<o r>O c=o D t r<O c<o r<O c<o -c- t (c) The preference direction for each quadrant in the relative address plane. Note: 1. Black arrow represents the preference direction. 2 . Dotted arrow denotes the r = ~ , c , ~ possible alternate path. 3 . r and c are the relative address of the current node corresponding to row and column address field. r<0 0 0 Fig. 13. Routing in MSN: (a) absolute address for each node in MSN; (b) relative address for the other nodes with respect to the destination node whose relative address is (0, 0); (c) the preference direction for each quadrant in the relative address plane. order and therefore is simple from its protocol implementation viewpoint. To achieve an efficient and fault-tolerant routing scheme, use of both self-routing characteristics and a local status table are desirable. All routing algorithms considered here employ only one of these and, hence, are deficient either in routing efficiency or in fault tolerance. Deadlock prevention using a fixed routing algorithm can- not be justified on the basis of traffic adaptability and fault tolerance, although it is superior to a buffer reservation scheme in terms of link buffer utilization. Besides network parameters, such as diameter and average path length, the simplicity and efficiency of a routing scheme are also important. The ( d , k ) network H, performs well in terms of network reliability and diameter, but its routing algorithm is difficult to implement. On the DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS 49 other hand, a 3-ary 2-cube network has large diameter while its routing algorithm is simple and efficient. MEDIUM ACCESS PROTOCOL The medium access protocol plays a key role in the performance of a doubly linked network. Some of the existing protocols, e.g., slotted ring [ I ] and register insertion ring [ 1 3 , originally introduced for a single-ring network can be readily adopted for a doubly connected network [ 20, 221. The token ring, however, requires some enhancement before it can become effective for a doubly connected network. In fact, the fiber distributed data interface (FDDI) protocol used in a DDLCN-like network is the enhanced version of the token ring protocol. In a register insertion protocol shown in Figure 14(a), each node contains an output buffer and a shift register large enough to store the largest-size message. When a message arrives from an adjacent node, the message is shifted into the register and the header of the message is checked. If the message is not for the receiving node, it is transmitted out right away if the output link is idle; otherwise, it is buffered in the shift register until the output link becomes free. On the other hand, when a station has a packet to transmit, it loads the packet into the output buffer and waits until the output link is idle. In this protocol. messages can be of various sizes and simultaneous transmission of multiple messages in the network is feasible. Hence, it can be easily adopted to take advantage of the additional links of the doubly linked network. In the slotted ring protocol, shown in Figure 14(b), the round-trip delay is slotted into a fixed time slot or a packet slot with an associated bit indicating whether the slot is full or empty. When a station wants to transmit, it has to wait for an empty slot to come around, mark it as full, and put its data in the slot. The packets of data in this protocol are of fixed size and are transmitted synchronously. Since this protocol can operate with multiple packets at the same time, it can be extended to a doubly connected network and the added links can be well utilized to improve the network throughput. The FDDI topology consists of two independent fiber optic rings, each carrying data in the opposite direction. A node can attach either to one or both rings. If all nodes in the FDDI network attach to both rings, the network topology is isomorphic to a DDLCN network. Thus, the FDDI protocol can only be useful for the DDLCN type of networks. In the FDDI protocol [I], each ring uses an enhanced token ring protocol for data transmission [in Fig. 14 (c) ] . A node attached to a ring must capture a free token before it can transmit. After the transmission of one or more data packets, the transmitting node appends a free token. The next node down in the ring can then capture the S: Start of Message E: End of Message (a) Register insertion ring protocol (b) Slotted ring protocol 131 and removes the data from the ring. The token is released after the data is sent. (c) Token ring protocol Fig. 14. Three basic ring access protocols that can be useful for a doubly linked network: (a) register insertion ring protocol; (b) slotted ring protocol; (c) token ring protocol. token and start transmission. Note that the source node is responsible for removing its transmitted data from the ring after the data loops back. A node that is not transmitting repeats the packets that it receives. If the node is the destination of the data packet, it copies the packet 50 CHUNG ET AL. ring networks. IEEE Trans. Comput. C-34 ( 1985) 853855. D. 2. Du, D. F. Hsu, F. K. Hwang, and X. M. Zhang, The Hamiltonian property of generalized De Bruijn digraphs. J . Comb. Theory, Ser. B. 52 ( 1991 ) 1-8. P. Erdos and D. F. Hsu, Distributed loop networks with minimum transmission delay. Theor. Comput. Sci. 100 (1992) 223-241. M. A. Fiol et al., A discrete optimization problem in local networks and data alignment. IEEE Trans. Comput. C36 (1987) 702-713. M. A. Fiol, I. Alegre, and J. L. A. Yebra, Line digraph iteration and the ( d , k ) problem for directed graphs. Proc. 10th Annu. In/. Sym. on Computer Architecture (1983) 174-1 77. A. Grnarov, I.. Kleinrock, and M. Gerla, A highly reliable distributed loop network architecture. Proceedings o?/'thcJ Intcrnational S~w~porizirn on F a i d - Tolcwnt Cotnpziting, Kyoto, Japan (Oct. 1980) 3 1'3-324. D. F. Hsu and X. D. Jia, Extremal problems in the construction of distributed loop networks. SJAM J. Di.scr Matlz., to appear. F. K. Hwang and Y. Xu, Double loop networks with minimum delay. Discr. Mall?. 66 (1987) 109-1 18. M. Imase and M. Itoh, Design to minimize diameter on building-block networks. IEEE Truns. Cotnpzii. C-30 (1981)439-442. M. lmase and M. Itoh, A design for directed graphs with minimum diameter. IEEE Tran.~. C'otnpzri.C-32 (1983) 782-784. N. F. Maxemchuk, Regular mesh topologies in local and metropolitan area networks. AT&T 7cJc.h.J. 64 ( 1985) 1659-1685. N. F. Maxemchuk, Routing in the Manhattan Street Network. IEEE Truns. Comtmm. COM-35 ( 1987) 503-5 12. C. S. Raghavendra, M. Gerla. and A. Avizienis, Reliable loop topologies for large local computer networks. IEEE Tram. Co/nyzri.C-34 ( 1985) 46-55. J. A. Sjlvester and C. S. Raghavendra, Analysis and simulation of a class of double loop network architecture. Procrcdings I994 INFOC'OM. 30-3 5. M. Schwartz, Tc.l~.c.otnmiinicaii,n ~V~~tworks: Protocols. h'udding and '4nal),.vis. Addison-Wesley, Reading, MA (1987). C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organization. J. Assoc. Cotnpiri. Muchin. ( 1974) 392-40 I . into its buffer while it repeats the packets. The FDDI network is fault-tolerant. When the two rings are operational, a node can choose either ring for data transmission. If faults happen, leading the failure of both rings, the network is reconfigured to form a single loop so that data transmission can be pertained. Since a slotted system transmits a fixed-size packet in each time slot, a message with a size larger than a data packet must be disassembled before being transmitted. Hence, overhead is incurred due to both the associated header and the partial usage of the time slot for the small packets. The register insertion ring protocol, on the other hand, can asynchronously transmit variable message length and, hence, is more efficient than is a slotted system. The token ring protocol, in general, cannot effectively utilize the extra links of a doubly linked loop network. Although FDDI has been developed for quite sometime, it can only be applied to DDLCN-like networks. This work was partially supported by Department of the Army, Army Research Office. RTP. Contract No. DAAG-2985-k-0236 and NASA Contract Nos. NAG 2-337 and NAG 2-449. REFERENCES B. W. Abeysundara and A. E. Kamal, High-speed local area networks and their performance: A survey. ACM Cotnpirt. Szirv. 23( 2 ) ( 1991 ) 221-264. D. P. Agrawal, V. K. Janaskiram, and G. C. Pathak, Evaluating performance of multicomputer configurations. IEEE Cotnprrf.17(3) (1985) 41-53. W. G . Bridges and S. Toueg, On the impossibility of directed Moore graphs. J . Comb. Thcory 29 ( 1980) 339341. C. Chen, D. P. Agrawal, and J. R. Burke, dBCube: A new class of hierarchical multiprocessor networks and its area efficient layout. IEEE Trans. Parallel Distrih. Syst., 4 ( 1 2 ) ( 1 9 9 3 ) 1332-1343. T. Y. Chung and D. P. Agrawal, Design and analysis of multidimensional Manhattan Street Network. IEEE Trans. Commun., 41 ( 2 ) (1993) 295-298. T. Y. Chung, D. P. Agrawal, and J. R. Burke, O n network characterization of and optimal broadcasting in the Manhattan Street Network. Proceedings of the IEEE INFOCOM '90, San Francisco (June 5-7, 1990) 465-472. T. Y. Chung, S. Rai, and D. P. Agrawal, Doubly connected multi-dimensional networks for LANs and MANS. Proceedings I988 INFOCOM, 55 1-557. T. Y.Chung, N. K. Sharma, and D. P. Agrawal, Cost performance tradeoffs in Manhattan Street Networks v / s 2-D Torus. IEEE Trans. Comput., 43 ( 2 ) (1994) 240-243. W. J. Dally and C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput. C-36 (1987) 547-553. D. Z. Du, D. F. Hsu, and F. K. Hwang, Doubly linked Received March 27, 199 1 Accepted March 30, 1995 Further Reading General I. S. B. Akers and B. Krishnamurthy, On group graphs and their fault tolerance. IEEE Trans. Comput. C-36( 7 ) ( 1987) 885-888. DOUBLY CONNECTED DIRECTED TOPOLOGIES FOR LANS AND MANS M. A. Fiol, J. L. A. Yebra, and I. A. De Miquel, Line digraph iterations and the ( d , k ) digraph problem. IEEE Trans. C’ornplit. C-33 ( 1984) 400-403. 3. M. Imase. T. Soneoka, and K. Okada. Connectivity of regular directed graphs with small diameters. IEEE Trans. C’ompul. C-34 (1985) 267-273. 4. W. Stallings, Data and Conlpiit~rCornrniinications. Macmillan. New York (1985). 5 . E. A . Van Doorn, Connectivity of circulant digraphs. J. Gruph Tlicorj’ 10 ( 1986) 9- 14. 6. R. S. Wilkov, Analysis and design of reliable computer networks. IEEE 7run.T. Cornmiin. COM-20 ( 1972) 660-678. 2. Topology I. 2. D. K. Pradhan and S. M. Reddy, A fault-tolerant communication architecture for distributed systems. IEEE 7 ’ r ~ n . \ C‘ornpiif. . C-31 ( 1982) 863-870. C. S. Raghavendra and J. A. Silvester. A survey of multiconnected loop topologies for local computer networks. C’om/~ut.Nc~tnwk.sISDN Sj:st. I 1 ( 1 ) ( 1986) 29-42. 3. 51 J. Wolf, M. T. Liu, B. Weide, and D. Tsay, Design of a distributed fault-tolerant loop network. Procrcdin,qs o f t h r 9th Annuul Intrrnationul Sjwposiiirn on Faiilt-Tol~~rant C‘omputirzg, Madison, WI (June 1979) 17-24. Routing D. Bertsekas and R. Gallager, Data Netir.ork.7. Prentice-Hall. Englewood Cliffs. NJ ( 1987). W . Chou, A. W. Bragg, and A. A. Nilsson, The need for adaptive routing in the chaotic and unbalanced traffic environment. IEEE Truns. Cornmiin. COM-29( 4 ) ( 198 I ) 48 1-490. R. T. Provsser. Routing procedures in communications networks-Part I : Random procedures. IRE Trans. Com~ n i i nSjat. . ( 1962) 322-329. P. Scheuermann and G . Wu, Heuristic algorithms for broadcasting in point-to-point computer networks. IEEE Truns. Cornpiit. C-33(9) ( 1984) 804-8 12.

1/--страниц