Minimal cost heuristic algorithm for delay constrained loop network

摘要

The delay constrained minimal cost loop problem (DMCLP) is one of problems arising in the design of local access networks. The problem consists of finding a set of loops to satisfy the traflic requirements of end-user nodes and to minimize the total link cost. This paper presents a heuristic algorithm which consists of two phases for this problem, under the constraints that the number of nodes served by a single loop is limited and network mean delay is within the desired time. The algorithm is derived using the loops obtained by the minimal cost loop problem (MCLP) algorithms and a trade-off criterion based on the node exchange and node transfer among loops. The simulation results show that the proposed algorithm produces more than ten percent better solution than the previous MCLP algorithm modified to satisfy the mean delay constraint. In addition, the algorithm has the relatively short execution time.