Finding Complex Cycles through a Set of Nodes
Arun K. Somani, David Lastine, Samyukta Sankaran · 2011
A cycle could support a SONET ring, a reliable multicast, a multipoint to multipoint traffic request, or service as a dependable connection, backup paths for requested number of pairwise connection or be used as a p-cycle. In this paper we develop a novel and efficient heuristic to find a cycle in a mesh network that includes a specified set of nodes. We allow links to be used only once in a cycle whereas a node may appear multiple times. This cycle, called a non-simple cycle, reduces the total number of links required to form the cycle. The simulation results show that the proposed heuristic outperforms other cycle finding heuristic algorithms like Optimized Collapsed Ring (OCR) and Enumeration in terms of percent blocking.