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

Yu-Liang LIU; Ruey-Chyi WU

doi:10.1587/transinf.2017PAP0008

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

Yu-Liang LIU, Ruey-Chyi WU

Full Text Views

0

Share
Cite this

Summary :

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 R_n 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 R_n, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2^s+t-2+⌊2^t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2^t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.12 pp.2771-2780

Publication Date: 2017/12/01

Publicized: 2017/08/04

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

Authors

Yu-Liang LIU
Aletheia University
Ruey-Chyi WU
National Taipei University

Keyword

congestion, exchanged hypercube, interconnection networks, ring-connected topology, routing and wavelength assignment

Cite this

Copy

Yu-Liang LIU, Ruey-Chyi WU, "Implementing Exchanged Hypercube Communication Patterns on Ring-Connected WDM Optical Networks" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 12, pp. 2771-2780, December 2017, doi: 10.1587/transinf.2017PAP0008.
Abstract: 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 R_n 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 R_n, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2^s+t-2+⌊2^t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2^t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2017PAP0008/_p

Copy

@ARTICLE{e100-d_12_2771,
author={Yu-Liang LIU, Ruey-Chyi WU, },
journal={IEICE TRANSACTIONS on Information},
title={Implementing Exchanged Hypercube Communication Patterns on Ring-Connected WDM Optical Networks},
year={2017},
volume={E100-D},
number={12},
pages={2771-2780},
abstract={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 R_n 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 R_n, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2^s+t-2+⌊2^t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2^t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.},
keywords={},
doi={10.1587/transinf.2017PAP0008},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Implementing Exchanged Hypercube Communication Patterns on Ring-Connected WDM Optical Networks
T2 - IEICE TRANSACTIONS on Information
SP - 2771
EP - 2780
AU - Yu-Liang LIU
AU - Ruey-Chyi WU
PY - 2017
DO - 10.1587/transinf.2017PAP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2017
AB - 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 R_n 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 R_n, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2^s+t-2+⌊2^t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2^t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.
ER -