Simple, Efficient Routing Schemes for All-Optical Networks

All-optical networks promise data transmission rates several orders of magnitude higher than current networks. The key to high transmission rates in these networks is to maintain the signal in optical form, thereby avoiding the prohibitive overhead of conversion to and from the electrical form, and to exploit the large bandwidth of optical fibers by sending many signals at different frequencies along the same optical link. Optical technology, however, is not as mature as electronic technology. Hence it is important to understand how efficiently simple routing elements can be used for all-optical communication. In this paper we consider two types of routing elements. Both types can move messages at different wavelengths to different directions. If in the first type a message wants to use an outgoing link that is already occupied by another message using the same wavelength, the arriving message is eliminated (and therefore has to be rerouted). The second type can evaluate priorities of messages. If more than one message wants to use the same wavelength at the same time, then the message with the highest priority wins. We prove nearly matching upper and lower bounds for the runtime of a simple and efficient protocol for both types of routing elements, and apply our results to meshes, butterflies, and node-symmetric networks. Received January 6, 1998, and in final form July 17, 1998.