Please use this identifier to cite or link to this item:
|Title:||Randomized routing and wavelength requirements in wavelength-routed WDM multistage, hypercube, and de Bruijn networks||Authors:||Mohan, G.
|Issue Date:||Mar-2004||Citation:||Mohan, G., Venkatesan, G., Murthy, C.S.R. (2004-03). Randomized routing and wavelength requirements in wavelength-routed WDM multistage, hypercube, and de Bruijn networks. Journal of Parallel and Distributed Computing 64 (3) : 385-399. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jpdc.2003.12.002||Abstract:||This paper considers randomized routing in wavelength-routed wavelength division multiplexed (WDM) networks. Randomized routing is advantageous when compared to deterministic routing, as it is simple, oblivious, and suitable for centralized as well as distributed implementation. Recently, there has been a considerable interest in studying regular graphs such as shuffle networks and de Bruijn networks as a possible physical topology for wavelength-routed WDM networks (IEEE/ACM Trans. Network 3(3) (June 1995) 269; IEEE/ACM Trans. Network 2(1) (February 1994) 70; Comput. Networks ISDN Systems 30(24) (December 1998) 2349). In Pankaj and Gallager (1995), permutation routing has been taken as a benchmark problem to accept a network and a deterministic algorithm has been proposed for routing permutation traffic without any blocking in an N-node wrapped-around multi-stage shuffle network using O(log3N) wavelengths. In this paper, we look at the possible application of probabilistic techniques on a class of wrapped-around multi-stage networks called 2-multinets and study the wavelength requirements for routing permutation traffic, allowing a negligible blocking of sessions. We adopt the routing scheme proposed in (J. ACM 31 (1984) 507) for fast packet routing to find routes in the circuit-switched wavelength-routed WDM networks and analyze the wavelength requirements for different models. The models differ in their routing node architecture and wavelength selection policy. Our analysis shows that the permutation routing problem can be solved on these models with an overwhelming probability using O(log2N) wavelengths. We also study the routing problem on 2-multinets for a class of 1-expectedly bounded connection requests. For this class also, we propose two models and obtain similar bounds on the number of wavelengths required. We confirm the theoretical results by extensive simulation experiments. The theoretical as well as experimental results show that the number of wavelengths required is reduced significantly when randomized routing techniques are used. Finally, we discuss how the results obtained for 2-multinets can be extended to hypercubes and de Bruijn networks. © 2003 Published by Elsevier Inc.||Source Title:||Journal of Parallel and Distributed Computing||URI:||http://scholarbank.nus.edu.sg/handle/10635/82966||ISSN:||07437315||DOI:||10.1016/j.jpdc.2003.12.002|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 16, 2019
WEB OF SCIENCETM
checked on May 7, 2019
checked on May 13, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.