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. 
Venkatesan, G.
Murthy, C.S.R.
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.
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
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 Jan 19, 2023


checked on Jan 19, 2023

Page view(s)

checked on Jan 26, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.