Exact algorithm for delay-constrained capacitated minimum spanning tree network

The delay-constrained capacitated minimum spanning tree (DC-CMST) problem of finding several broadcast trees from a source node is discussed. While the traditional CMST problem deals with only the traffic capacity constraint served by a port of the source node, and delay-constrained minimum spanning tree (DCMST) considers only the maximum end-end delay constraint, the DC-CMST problem deals with both the mean network delay and traffic capacity constraints. The DC-CMST problem consists of finding a set of minimum cost spanning trees to link end-nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-CMST problem, the objective function is to minimise the total link cost. A dynamic programming-based three-phase algorithm that solves the DC-CMST problem is proposed. In the first phase, the algorithm generates feasible solutions to satisfy the traffic capacity constraint. It finds the CMSTs in the second phase, and allocates the optimal link capacities to satisfy the mean delay constraint in the third phase. Performance evaluation shows that the proposed algorithm has good efficiency for any network with less than 30 nodes and light traffic. The proposed algorithm can be applied to any network regardless of its configuration, and used for the topological design of local networks and for efficient routing algorithms capable of constructing least cost broadcast trees.