The rearrangeability and routing algorithms of multistage interconnection networks are studied in this thesis. The main contribution of this thesis is the generalization of rearrangeable networks. Two generalized classes of rearrangeable networks, called {\it Symmetric Bit-Permute Multistage Interconnection Networks(Symmetric BPMIN's)} and {\it Generalized Rearangeable Networks(GRN's)}, are proposed. The general routing algorithms for the classes of networks are also proposed. For the asymmetric $2\log N$ stage networks including the omega-omega network, the problems of inside-out routing algorithm suggested by Feng and Seo are addressed. A modified necessary and sufficient condition for proper routing in the omega network, which can be used for routing in the omega-based networks, is also suggested.
At first, a class of $\log N$ stage interconnection networks, called {\it Bit-Permute Multistage Interconnection Networks(BPMIN's)}, is introduced. In a BPMIN, the ports of each switching element of a stage have labels which are different at only one bit position. The BPMIN's have recursive decomposition structures, and all of BPMIN's are topologically equivalent and some of them are functionally equivalent. Based on the recursive decomposition structures of the BPMIN's, a new class of $2\log N$ stage rearrangeable networks, called {\it Symmetric BPMIN's}, are proposed. They are constructed by concatenating two $\log N$ stage BPMIN's in sequence, and are either symmetric or asymmetric, regular or irregular in their inter-stage connections, and can be reduced into $2\log N-1$ stages by combining the two center stages. It is shown that the Symmetric BPMIN's constitute larger class of rearrangeable networks than the equivalent Benes networks suggested by Yeh and Feng. A general routing algorithm for the Symmetric BPMIN's is suggested by modifying slightly the looping algorithm of the Benes network.
Next, a more generalized class of rearrangeable networks, called {\it Generalized Rearrangeable Networks(GRN's)}, is proposed. Networks in this class consist of all of the networks which have the same recursive decomposition structures as the Benes network. It is shown that the GRN's constitute larger class of rearrangeable networks than ever known. Necessary conditions for a network to satisfy to be a GRN are proposed, and a network labeling scheme to check whether a network satisfies the conditions is also proposed. A general routing algorithm for the GRN's is proposed by modifying slightly the looping algorithm of the Benes network.
The rearrangeability of asymmetric $2\log N$ stage networks including the omega-omega network has been studied by many authors, but, it was not known. Recently, Feng and Seo proposed a new routing algorithm, called inside-out routing algorithm, which routes an arbitrary permutation in the omega-based $2\log N$ stage networks including the omega-omega network. The inside-out routing algorithm, however, has some problems. It is shown that the routing algorithm needs backtracking in the terminal number assignment procedure and the conditions for proper routing in the omega network suggested by them are insufficient. An extended necessary and sufficient condition for proper routing in the omega network, which can be used for routing the omega-based $2\log N$ stage networks, are proposed in this thesis.
본 논문에서는 다단계상호연결망의 재설정성및 경로설정 알고리즘에 대해 연구하였다. 본 논문에서는 대칭 BPMIN과 GRN이라는 두 부류의 재설정가능 연결망을 제안하고, 그들에 대한 일반적인 경로설정 알고리즘을 제안하였다. 오메가-오메가 연결망을 포함한 2logN 단계 비대칭 연결망에 대해서는 Feng과 Seo가 제안한 Inside-out 경로설정가능할 새로운 필요충분조건을 제시하였다.
먼저, 한 단계의 스위치소자들의 포트들은 한 비트위치에서만 다른 레이블들을 갖는, 비트순열 다단계상호연결망(BPMIN)이라는 logN 단계 연결망을 제안하고, BPMIN은 재귀적 분해구조를 가짐을 보였다. 또한, BPMIN은 모두 위상적동치이고 같은 제어벡터를 가진 두 BPMIN은 기능적동치임을 보였다. BPMIN의 분해성질에 기초하여 두 BPMIN을 연결한 대칭 BPMIN이라는 새로운 부류의 재설정가능 연결망들을 제안하였다. 이 대칭 BPMIN은 위상적으로 대칭 또는 비대칭일 수 있고, 단계사이의 연결이 정규적 또는 비정규적일 수 있으며, 가운데 두 단계를 하나로 합침으로써 2logN-1 단계로 축소될 수 있다. 대칭 BPMIN은 Yeh와 Feng에 의해 제안된 동치 Benes 연결망을 포함함을 보였고, 그들에 대한 경로설정 알고리즘을 제시하였다. 다음으로, 대칭 BPMIN을 확장한 GRN이라는 새로운 부류의 재설정가능 연결망을 제안하였다. GRN은 Benes 연결망에서 단계사이의 연결과 스위치소자들을 재배열하므로써 얻어지는, 재귀적 분해구조를 갖는 모든 연결망으로 구성된다. 이 GRN은 기존의 모든 재설정가능 연결망보다 큰 부류임을 보였고, 또한 GRN이 될 필요조건을 제시하고 임의의 연결망이 이 조건을 만족하는지 검사하는 망 레이블링 프로시져를 제시하였다. 오메가-오메가 연결망을 포함한 2logN 단계의 비대칭 연결망의 재설정성에 대해서는 많은 연구가 있었지만 별로 알려진 것이 없었는데, 최근 Feng과 Seo는 오메가망에 기초한 2log N 단계의 연결망들에 대한 Inside-out이라는, 임의의 순열에 대한 경로설정 알고리즘을 제시하였다. 본 논문에서는 Inside-out 알고리즘이 터미널번호 할당과정에서 퇴각검색이 필요함을 보였다. 또한 그 들이 제시한 오메가 망에서 경로설정가능할 조건이 불충분함을 보이고 수정된 새 필요충분조건을 제시하였다.
