Optimal delay-constrained minimum cost loop algorithm for local computer network

This study deals with the delay-constrained minimum cost loop problem (DC-MCLP) of finding several loops from a source node. The DC-MCLP consists of finding a set of minimum cost loops 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-MCLP, the objective function is to minimize the total link cost. This paper proposes a dynamic programming based three phase algorithm that solves the DC-MCLP. In the first phase, the algorithm generates feasible solutions to satisfy the traffic capacity constraint. It finds the capacitated minimum loops 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 network with less than thirty nodes and light traffic. Our proposed algorithm can be applied to any network regardless of its configuration, and used for the topological design of FDDI and SONET.