Algebraic analysis of the topological properties of a banyan network and its application in fault-tolerant switching networks

Abstract

In this paper. we introduce abstract algebraic analysis of the topological structure of a banyan network, which has become the baseline for most switching networks. The analysis provides the following key results: (1) The switching elements of a switching stage are arranged in order. that is. each stage of a banyan network consists of a series of a cyclic group. (2) The links between switching stages implement a homomorphism relation ship in terms of self-routing. Therefore, we can recover the misrouting of a detour fault link by providing adaptive self-routing. (3) The cyclic group of a stage is a subgroup of that of the next stage, so that every stage and its adjacent stage make up a factor Group. Based on this analysis, we introduce a cyclic banyan network that is more reliable than other switching networks. We present mathematical analysis of the reliability of the switching network to allow quantitative comparison against other switching networks. (C) 2005 Elsevier Inc. All rights reserved.