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 language||English (US)|
|Title of host publication||Proceedings - 18th Conference on Local Computer Networks, LCN 1993|
|Publisher||IEEE Computer Society|
|Number of pages||10|
|ISBN (Electronic)||0818645105, 9780818645105|
|State||Published - 1993|
|Event||18th Conference on Local Computer Networks, LCN 1993 - Minneapolis, United States|
Duration: Sep 19 1993 → Sep 22 1993
|Name||Proceedings - Conference on Local Computer Networks, LCN|
|Conference||18th Conference on Local Computer Networks, LCN 1993|
|Period||9/19/93 → 9/22/93|
Bibliographical noteFunding Information:
*Researchs upported in part by the University of Minnesota Army High Performance Computing Research Center and the International Business Machine corporation
© 1993 IEEE.
Copyright 2019 Elsevier B.V., All rights reserved.