Impairment aware cycle based routing algorithm (IACBRA)

A cycle could support a Synchronous optical networking (SONET) ring, or a reliable multicast, or a multipoint to multipoint traffic request, or a p-cycle protecting connections between any two-node pair that belong to the cycle. Determining a cycle passing through a specific set of nodes is a complex process. This paper presents a novel heuristic algorithm to find a least cost possible simple or non-simple cycle with multiple must-include nodes. In case the required cycle must be a simple cycle only, then it is apparent that our problem is similar to a Travelling Salesman Problem, in which the objective is to find the least cost simple cycle with all the nodes in a given travel network. In our algorithm, we allow complex cycles in the sense that links are allowed to be used only once, whereas a node may appear multiple times. This kind of cycle is called a non-simple cycle and it can increase the success rate of finding the cyclic route with desired set of nodes. The heuristic algorithm in this paper utilizes Breadth First Search and Tree construction algorithms to find a least cost and shortest route between nodes. The experimental results show that our algorithm has lower failure rate of requests than existing heuristic algorithms like Optimized Collapsed Ring (OCR) and Enumeration. The fault-tolerance for single link failure can be achieved by routing the traffic in both the directions of the cycle.