A balanced ring (b-ring) proposed by Gu et al. [Journal of Systems Architecture, 53, (2007), 902–912.] is more effective than a fault ring (f-ring) in providing fault tolerance for mesh and torus networks. By properly utilizing the b-ring, an efficient fault tolerant routing algorithm can be achieved without using any virtual channel. Traffic congestion can also be significantly reduced. However, the algorithm presented by Gu et al. for the formation of b-ring has the demerits that it involves all the nodes of the network each time a b-ring needs to be formed, and thereby increasing the overhead to the whole system. In this paper, we first present an improved algorithm for the formation of b-ring by considering only the nodes on the fault ring in contrast to all. We next present a distributed algorithm for the same, which is also based on the local knowledge, thereby avoiding overhead and thus, enhancing the overall network performances. We show that our sequential algorithm requires O(|f-ring|) time and the distributed algorithm runs in constant time.
http://www.actapress.com/Abstract.aspx?paperId=38563