DIRSMIN: a fault-tolerant switch for B-ISDN applications usingdilated reduced-stage MIN

摘要

We have developed and analyzed a dilated high-performancenfault-tolerant fast packet multistage interconnection network (MIN).nThis new switch, (d,d')-DIRSMIN, uses dilation to improve performancenand fault-tolerance of a network. The links at the input and outputnstages of the dilated banyan-based MIN are rearranged to create multiplenroutes for each source-destination pair in the network, after removingnthe first stage in the network. These multiple paths are link- andnnode-disjoint. This new MIN can provide low packet-loss probability andnhigh reliability with very little hardware overhead, compared tond-dilated banyan networks (BN). Fault tolerance at low latency isnachieved by transmitting multiple copies of each input-packetnsimultaneously using different routes. A multiple-priority scheme allowsnalternate paths to be explored simultaneously, which results in highernthroughput and reliability under both fault-free and faulty conditions.nThis guarantees that high throughput is maintained even in the presencenof a fault. Throughput is analyzed using analytic and simulationnmethods; this new design has considerably higher performance in thenpresence of a permanent faulty switching-element (SE) or link, inncomparison to dilated networks. Under non-faulty conditions, bothnanalytic and simulation results show that a (d,d)-DIRSMIN performsnbetter than the original dilated BN with the same SE complexity. Wenanalyze the network reliability and show that the new design hasnsuperior reliability compared to competing proposals. In particular,nthis new design is considerably better than the SEN+, the best knownnthus far