Optical networks based on wavelength division multiplexing (WDM)and wavelength routing are considered to be potential candidates for thenext generation of wide area networks. One of the main issues in thesenetworks is the development of efficient routing algorithms whichrequire a minimum number of wavelengths. We focus on the permutationrouting problem in multistage WDM networks which we call 2-multinets. Wepresent a simple, oblivious probabilistic approach which solves thepermutation routing problem on 2-multinets with very high probability(in the usual theoretical sense) using O(log2N/loglogN)wavelengths, where N is the number of nodes in the network, therebyimproving the previous result due to Pankaj and Gallager (1995) thatrequires O(log3 N) wavelengths. Our approach is advantageousand practical as it is simple, oblivious, and suitable for centralizedas well as distributed implementations. We also note that O(logN)wavelengths will suffice with good probabilistic guarantee for the caseof dynamic permutation routing where requests arrive and terminatewithout any relation to each other. The above results are for networkswith wavelength converters and we show that the use of converters can beeliminated at the expense of a factor of log N more wavelengths. We alsoshow how our approach can be used to solve the dynamic permutationrouting problem well (in practice), using O(1) wavelengths on thehypercube and O(logN) wavelengths on the Debruijn network. These improvethe previous known bounds of O(logN) and O(log2N),respectively
展开▼
