Permutation routing in wavelength-routed wrapped-around shuffle networks using fewer wavelengths

Optical networks based on wavelength division multiplexing (WDM) and wavele ngth routing are considered to be potential candidates for the next generat ion of wide area networks. One of the main issues in these networks is the development of efficient routing algorithms which require minimum number of wavelengths. In this paper, we focus on the permutation routing problem in WDM networks with the shuffle network topology. In Pankaj and Gallager [Wa velength Requirements of All-Optical Networks, IEEE/ACM Transactions on Net working 3, No. 3 (June 1995) 269-280], an algorithm has been proposed for p ermutation routing in wrapped-around multi-stage shuffle networks using O(l og(3)N) wavelengths, where N is the number of nodes. Here, the messages are routed using one (light) hop. We present a routing algorithm in these netw orks with only O(log(2)N) wavelengths, which routes the messages using O(lo glog N) hops. We also discuss how our approach can be extended to the gener alized routing. We study the worst case buffer requirement and bandwidth re duction due the use of multiple hops. We evaluate the performance of the pr oposed algorithm through extensive simulation by measuring the average numb er of hops required and delay incurred by a message. We also study the aver age number of messages queued at a node and average number of messages that share a lightpath at Various time intervals. We also evaluate the system t hroughput achieved by our multi-hop routing algorithm. (C) 1998 Elsevier Sc ience B.V. All rights reserved.