Efficient embedding of a hypercube in an irregular WDM network

Kenneth A. Williams, David H.C. Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A heuristic algorithm is presented for efficiently embedding a virtual hypercube into an irregular wavelength division multiplexing (WDM) network so that the message propagation delay is minimized. Embedding a hypercube allows the communications of the many hypercube-base algorithms to map directly to the virtual network. The authors' algorithm optimizes the embedding by effective assignment of virtual addresses as well as the efficient routing of virtual connections. The three-step approach is first based on embedding the irregular graph in a hypercube so that the number of virtual edges that correspond to physical edges is minimized. The routing of the virtual connections and their assignment to logical channels is performed while minimizing the number of wavelengths that must be supported by the WDM system. Experiments with the proposed algorithm show it to produce embeddings with significantly shorter path lengths and requiring fewer wavelengths than previous methods for practical networks.

Original languageEnglish (US)
Title of host publicationProceedings - 18th Conference on Local Computer Networks, LCN 1993
PublisherIEEE Computer Society
Number of pages10
ISBN (Electronic)0818645105, 9780818645105
StatePublished - 1993
Event18th Conference on Local Computer Networks, LCN 1993 - Minneapolis, United States
Duration: Sep 19 1993Sep 22 1993

Publication series

NameProceedings - Conference on Local Computer Networks, LCN


Conference18th Conference on Local Computer Networks, LCN 1993
Country/TerritoryUnited States

Bibliographical note

Funding Information:
*Researchs upported in part by the University of Minnesota Army High Performance Computing Research Center and the International Business Machine corporation

Publisher Copyright:
© 1993 IEEE.

Copyright 2019 Elsevier B.V., All rights reserved.


Dive into the research topics of 'Efficient embedding of a hypercube in an irregular WDM network'. Together they form a unique fingerprint.

Cite this