Lightwave Networks Based on de Bruijn Graphs

Abstract

We propose de Bruijn graphs as logical topologies for multihop lightwave networks. After deriving bounds on the throughput and delay performance of any logical topology, we compute the throughput and delay performance of de Bruijn graphs for two different routing schemes and compare it with our bounds and the performance of shufflenets. For a given maximum nodal in- and out-degree and average number of hops between stations, a logical topology based on a de Bruijn graph can support a larger number of stations than a shufflenet and this number is close to the maximum that can be supported by any topology. We also propose de Bruijn graphs as good physical topologies for wavelength routing lightwave networks consisting of all-optical routing nodes interconnected by point-to-point fiber links. The worst-case loss experienced by a transmission is proportional to the maximum number of hops (diameter). For a given maximum nodal in- and out-degree and diameter, a physical topology based on a de Bruijn graph can support a large number of stations using a relatively small number of wavelengths. © 1994 IEEE