B-TREE - A HIGH-PERFORMANCE FAULT-TOLERANT ATM SWITCH

A high-performance fault-tolerant ATM switch (B-tree) is proposed. Thi s switch embeds multiple baseline networks tightly to improve the faul t tolerance and throughput of conventional multistage interconnection networks. This proposed switch retains the advantages of multistage in terconnection networks but is much more robust in the sense that multi ple paths are available between each input-output pair. The proposed n etworks have properties such as very simple routing algorithms (self-r outing) and that they can be recursively constructed in a modular way. The sufficient multiple paths are used to route cells under the condi tion that internal conflicts occur in switching elements. The intercon nection algorithm offers many access points to the output ports to res olve the output conflict. When carrying very high traffic load, the sw itch has ideal performance even in the presence of fault(s) in the swi tch.