In this thesis, we propose new fault-tolerant, high-performance multistage interconnection networks (MIN's) and new fully-adaptive, deflection, self-routing schemes for the networks. These networks can provide more alternate paths than the related previous networks between an input/output pair of a network by adding extra links between switching elements (SE's) in the same stage and modifying the self-routing scheme of the regular MIN. These routing schemes use not only the augmented links but also all already existing links to make the path when a fault, or a conflict, is occurred. Furthermore these networks are the internal packet-lossless MIN's, and have the same number of SE's as the banyan network. The presented fully-adaptive self-routing schemes are as simple as that of the regular MIN, which is based on the topological properties of the banyan network, which are discovered in this thesis. We show the SE's in a stage are arranged regularly from an algebraic point of view: each stage of the banyan network is composed of the sequences of a cyclic group of SE's. To derive the self-routing schemes, therefore, we can use not only the inter-stage relationships as the banyan network, but also the intra-stage relationships and even all relationships of all SE's of the banyan network. Simple local routing decisions can be made, while the penalty is small. The SE's of these schemes have a uniform structure respectively. We present algebraic proofs to show the correctness of the routing schemes, and present analytic reliability and performance analysis to provide quantitative comparisons with the banyan network, some augmented banyan networks, and other networks. Of the special notes is the finding that the networks are more cost-effective than the regular MIN and other augmented MIN's in terms of the reliability, and even than the replicated MIN's in terms of the performance. We also present the fault diagnosis methodology.
본 논문에서는 새로운 고장 감내, 고성능 다단 상호연결 망들과 새로운 완전 적응, 편향, 자기 경로제어 기법들을 제안한다. 이 망들은 동일한 단 내의 스위칭 요소들 사이에 링크들을 추가하고 기존의 베니안 네트워크의 경로제어법을 수정하므로써, 관련된 기존의 대부분의 네트워크 보다 입력단과 출력단 사이에 더 많은 다중 경로들을 제공할 수 있다. 이들은 고장 또는 충돌이 일어났을 때 페킷의 경로제어를 위해서, 추가된 링크 뿐만 아니라, 모든 기존의 링크들을 모두 사용한다. 다시 말해서, 이 망들은 내부적으로 페킷을 잃어버리지 않는 다단 상호연결 망들이며, 베니안 망과 동일한 수의 스위칭 요소들을 가지고 있다. 제시된 완전 적응 자기 경로제어 방법들은 일반적인 다단 상호연결 망의 그것과 같은 정도로 간단하며, 이들은 본 논문에서 발견한 베니안 망의 위상적 특성들에 기반을 두고 있다. 우리는 동일한 단 내의 스위칭 요소들이 대수적 관점에서 규칙적으로 배치되어 있음을 보인다. 즉, 베니안 망의 각 단은 스위칭 요소들로 이루어진 시클릭 그룹의 배열들로 이루어져 있다. 따라서 자기 경로제어 법을 만들기 위해서, 베니안 망에서와 같이 단 간의 관계들 뿐만 아니라, 단 안에서의 관계들 그리고 베니안 망에 존재하는 모든 스위칭 요소들 사이의 관계들을 사용할 수 있다. 이로써 불이익이 적으면서도, 간단한 지역적인 경로제어가 가능하다. 또한 이 방법들의 스위칭 요소들은 각각 동일한 구조를 갖는다. 본 연구는 이 경로제어 법들의 정당성을 보이는 대수적 증명을 제공하며, 베니안 망과 몇몇 추가된 베니안 망, 그리고 다른 망들과의 정량적인 비교를 제공하기 위해서 신뢰성과 성능에 관한 분석을 제공한다. 특기할 사항은 이 망들이 보통의 다단 상호연결 망과 다른 추가된 상호연결 망들보다 신뢰성 면에서 더 비용-효과적이고, 성능 측면에서는 중복된 상호연결 망들보다 더 비용-효과적이라는 사실이다. 또한 본 연구에서는 고장 진단 방법도 제시된다.
