Implementing Exchanged Hypercube Communication Patterns on Ring-Connected WDM Optical Networks

Yu-Liang LIU  Ruey-Chyi WU  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.12   pp.2771-2780
Publication Date: 2017/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017PAP0008
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
Category: Interconnection networks
congestion,  exchanged hypercube,  interconnection networks,  ring-connected topology,  routing and wavelength assignment,  

Full Text: PDF(1.4MB)
>>Buy this Article

The exchanged hypercube, denoted by EH(s,t), is a graph obtained by systematically removing edges from the corresponding hypercube, while preserving many of the hypercube's attractive properties. Moreover, ring-connected topology is one of the most promising topologies in Wavelength Division Multiplexing (WDM) optical networks. Let Rn denote a ring-connected topology. In this paper, we address the routing and wavelength assignment problem for implementing the EH(s,t) communication pattern on Rn, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2s+t-2+⌊2t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.