вход по аккаунту



код для вставкиСкачать
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:
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.
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
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
Circulant loop digraph
e g . UDLCN, daisy chain
FLBH, optimized circulant
--c Generalized de Bruijn digraph
and its variants
mesh connected network wlth 2
and 3 lump choices.
Manhattan Street Network
Line digraph lteratlon one
time from an 1-D digraph,
d e Erui7n digraph of s i z e 4
r-dimensional loop
* networks with
s i z e ’ n=Xr*..*%
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.
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 ) ,
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
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
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
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
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
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.
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
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
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
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,
( 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
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
'k I
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.
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.
$ 3
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
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
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).
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.
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.
Two-dimensional Loop Network with
Two Jump Choices
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.
-+ 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 )
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))).
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.
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.
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
(a) Absolute address
for each node in
Relative address for
the other nodes with
respect to the
destination node whose
relative address is
n Boundary
along the
Outer boundary of
the quadrant
(c) The preference direction for
each quadrant in the relative
address plane.
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.
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
other hand, a 3-ary 2-cube network has large diameter
while its routing algorithm is simple and efficient.
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
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
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
M. lmase and M. Itoh, A design for directed graphs with
minimum diameter. IEEE Tran.~.
C'otnpzri.C-32 (1983)
N. F. Maxemchuk, Regular mesh topologies in local and
metropolitan area networks. AT&T 7cJc.h.J. 64 ( 1985)
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:
h'udding and '4nal),.vis. Addison-Wesley, Reading, MA
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
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)
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
S. B. Akers and B. Krishnamurthy, On group graphs and
their fault tolerance. IEEE Trans. Comput. C-36( 7 ) ( 1987)
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.
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.
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.
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 242 Кб
Пожаловаться на содержимое документа