A Modified Gomory-Hu Algorithm with DWDM-Oriented Technology

Abstract

Optimization of the topology of computer networks based on the classical Gomory-Hu algorithm does not take the specific transfer technology into account. For WDM technology requirements this leads to a redundancy of channel capacities. To reduce the redundancy of allocating network resources, we propose a modification of the Gomory-Hu algorithm which takes account of the specifics of DWDM technology - not at the final stage but already at intermediate stages in the process. The original algorithm proposed by Gomory and Hu involves the decomposition of the graph of the input network into ring subnets of different dimensions. Our modified algorithm takes account of the technical parameters of the DWDM technology for each ring during the decomposition. We illustrate our method by an example. The technique can be extended to large networks, which may lead to a significant economic effect.