KAUTZ GRAPHS AS ATTRACTIVE LOGICAL TOPOLOGIES IN MULTIHOP LIGHTWAVE NETWORKS

In this paper, we propose Kautz graphs as attractive logical topologie s for multihop WDM lightwave networks. Logical topologies proposed in the literature include the ShuffleNet, De Bruijn graph, Manhattan Stre et Network, and Hypercube. We show that for a given nodal in-degree an d out-degree and average number of hops between stations, a network ba sed on Kautz graphs can support a much larger number of stations than competing topologies (ShuffleNet and De Bruijn networks). Our experime ntal and analytical results show that despite its larger size (more nu mber of stations), a Kautz graph based network shows similar delay and throughput performance as a De Bruijn graph based network. Further, a topology based on Kautz graph has more uniform optical channel loadin g and utilizes, the installed network capacity more efficiently than a De Bruijn network. In addition, fault tolerance properties of Kautz g raphs are better than those of De Bruijn graphs. To deal with non-unif orm and asymmetric traffic, an adaptive routing scheme is proposed for Kautz networks, which relieves the network of congestion bottlenecks resulting from non-uniform traffic. Finally, we give the VLSI design a nd layout a router for Kautz graph-based networks using OASIS (Open Ar chitecture Silicon Implementation Software). (C) 1997 Elsevier Science B.V.