Least cost heuristic for the delay-constrained capacitated minimum spanning tree problem

This study deals with the Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) problem arising in topology discovery of local network. While the traditional Capacitated Minimum Spanning Tree (CMST) problem deals with only traffic capacity constraint of a port of a source node, and Delay-Constrained Minimum Spanning Tree (DCMST) considers only the maximum end-to-end delay constraint, the DC-CMST problem deals with mean network delay and traffic capacity constraints simultaneously. The DC-CMST problem consists of finding a set of minimum cost spanning trees to link end-nodes to a source node which satisfy the traffic requirements at end-nodes and the required mean delay of a network. We formulate the DC-CMST problem and present the Least-Cost DC-CMST Heuristic, which consists of node exchange algorithm, node shift algorithm, and mean delay link capacity algorithm to solve the DC-CMST problem. Results from performance analysis show that the proposed heuristic can produce, in a very short computation time, better results than the previous CMST algorithms modified to solve the DC-CMST problem. The proposed Least-Cost DC-CMST Heuristic can be applied to the topological design of large local networks and to the construction of least cost broadcast and multicast trees for efficient routing algorithms. (c) 2005 Elsevier B.V. All rights reserved.