Fault-tolerant routing algorithms in interconnection networks are studied in this thesis. Interconnection networks are used in various areas including multicomputer systems and internal networks for ATM switching systems. A multicomputer with a large number of processing nodes is one of the most promising means to meet the increasing demand of computational power. These nodes communicate with each other by passing messages over an interconnection network. In order to exploit parallelism at smaller granularities, the network size in a multicomputer has increasingly grown. Low-dimensional mesh networks are popularly used in multicomputers, since they offer good scalability. Asynchronous transfer mode (ATM) was chosen as a standard transmission and switching technology for broadband integrated services digital network (B-ISDN). The internal networks for ATM switches should provide high-speed connection and large-scalability to support broadband services. Multistage interconnection networks (MINs) are widely used in ATM switches as well as multicomputers because of their self-routing capability and regular structure.
As the size of interconnection networks increases, the probability that their components fail also increases. The network failure causes the incorrect operation and the degradation of performance in the system. Fault-tolerance in networks is one of the important factors in the design and implementation of the systems using the networks. Fault-tolerant routing aims at achieving fault-tolerance in the network without the need for hardware reconfiguration.
Fault-tolerant routing schemes in mesh networks have been proposed by several researchers [40, 25, 17, 13, 6, 4, 5, 7, 60]. Most of their routing algorithms restrict the number or pattern of faults. The algorithms proposed in [13, 6, 7, 27, 60] assumed that the fault region should be shaped as a rectangular block. Boppana and Chalasani [5] have presented the algorithm to tolerate more general fault shape, called a solid fault region that covers some non-convex fault shapes such as L, T, and +. However it cannot tolerate concave fault regions. The restriction on fault shape results in excessive loss of the computational power, since several fault-free nodes should be deactivated in order to change faults to manageable shape. We propose a fault-tolerant routing algorithm to deal with any number of concave fault regions. It exploits the concept of the fault ring/chain composed of fault-free elements surrounding faults. It can prevent deadlock at the reasonable cost of three and four virtual channels per physical link for fault rings and fault chains respectively. The proposed algorithm is based on deterministic xy-routing, and is extended for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.
There are two approaches to achieve fault-tolerance in MINs. One is to add switching elements (SEs) and/or links in the network to provide multiple paths to detour faults [29, 44, 66]. Another is to provide dynamic full access (DFA) capability by recycling of packets through the network to bypass faults [65, 64, 9]. Most of them have considered only one-to-one communication. Multicast communication is fundamental in supporting broadband services in ATM switches as well as several operations such as data replication, barrier synchronization in multicomputers. Multicast communications in MIN-based systems are usually provided by two methods. One is to add a copy network in front of routing network [37, 63, 23, 38]. Another is to perform both copying and routing functions in routing network by recycling packets through the network [15, 11, 51, 46]. In these methods, the features of fault-tolerance were not considered. We have observed that the packet recursion through the network is used for bypassing faulty elements or replicating a multicast packet for multiple destinations. We propose a simple multicast routing scheme to tolerate faulty SEs in MIN-based ATM switches. It can employ both the region and cube encoding schemes for the address encoding. It is proved that the proposed algorithm can route any multicast packet to its own destinations in only two passes in MIN having a single faulty SE, by exploiting the intrinsic nonblocking property of MIN. After replicating a multicast packet to intermediate outputs in the first pass, the replicated packets are routed to the desired destinations in the second pass. It is extended to tolerate a certain set of multiple faulty SEs in MIN. We also apply the scheme proposed for ATM switches to MIN-based multicomputers. In multicomputer, the packet in the first pass contains an additional information for routing to the desired destinations in the second pass. We describe the packet format used in each pass and present a fault-tolerant multicasting algorithm. We enhance the algorithm to reduce the number of packets that intermediate nodes send. The performance of the proposed algorithms for multicomputers is evaluated by simulation.
본 논문에서는 상호연결망 (interconnection network)에서의 고장 감내 (fault-tolerant) 라우팅 알고리즘에 대해 연구하였다. 상호연결망은 다중 컴퓨터 시스템과 ATM 스위칭 시스템을 비롯한 다양한 영역에서 활용되고 있다. 다중 컴퓨터에서는 시스템을 구성하는 다수의 계산 노드가 상호연결망을 통해 메세지를 교환하여 단일 작업을 수행한다. 대규모의 병렬 처리 작업에 대한 필요성의 증가로 연결망의 확장성은 다중 컴퓨터에서 중요한 요구 사항의 하나로 부각되고 있다. 뛰어난 확장성을 제공하는 저차원 메쉬망은 다중 컴퓨터에서 널리 이용되고 있다. 한편, 광대역 종합정보 통신망 (B-ISDN)을 위한 표준 스위칭 및 전송 방식으로 승인된 비동기식 전달 모드 (ATM)에서 스위칭 시스템의 내부 연결구조는 광대역 서비스를 원활히 지원하기 위해 고속성과 확장성을 제공해야 한다. 다단계 상호연결망 (MIN)은 자가 경로 제어 (self-routing) 특성과 규칙성을 지니고 있어서, 많은 ATM 스위치와 다중 컴퓨터가 이를 기반으로 제안되었다.
다중 컴퓨터 시스템 및 ATM 스위칭 시스템에서 연결망이 커짐에 따라, 망에서 고장이 발생할 가능성은 점점 증가한다. 시스템의 신뢰성을 높이기 위해서는 연결망에서 고장을 감내하는 효율적인 기법이 필요하며, 고장 감내 라우팅은 부수적인 하드웨어없이 이를 실현하고자 하는 것이다.
먼저, 본 논문에서는 메쉬망에서의 고장 감내 웜홀 라우팅 알고리즘을 제안하였다. 기존에 제안된 많은 알고리즘은 고장 요소들의 수나 형태를 제한하였고, 현재까지 허용되던 고장군의 형태는 사각형 또는 십자가의 모양이었다. 이러한 고장군 형태의 제한은 정상 노드의 희생을 초래하여, 시스템의 전체 계산능력을 저하시킨다. 본 논문에서 제안한 알고리즘은 다수의 오목한 고장군 (concave fault region)을 감내하여 정상 노드의 희생을 줄일수있다. 그리고, 고장링과 고장체인에 대해 각각 세개와 네개의 가상채널을 사용하여 교착상태를 방지하고 있다. 이 알고리즘은 결정적 xy-라우팅을 기본 방식으로 활용하고, 이를 적응적 라우팅 알고리즘으로 확장하였다.
다음으로, ATM 스위치를 위한 MIN에서의 고장 감내 멀티캐스트 라우팅 알고리즘을 제안하였다. MIN을 기반으로 하는 시스템에서 멀티캐스트 통신을 지원하기 위한 라우팅 기법들과, 일대일 통신을 위한 고장 감내 라우팅 기법들이 기존에 각각 제안되었으나, 고장을 감내하는 멀티캐스트 라우팅에 대한 연구는 거의 이루어지지 않았다. 본 논문에서 제안한 알고리즘은, MIN에서 중간 출력단을 통해 패킷을 순환하는 방법이 멀티캐스트 패킷을 복사하거나 고장 요소를 피하기 위해 기존의 일부 기법에서 공통적으로 응용되고 있음을 관찰하고 이를 활용하였다. 이 알고리즘은 MIN 기반의 ATM 스위치에서 널리 이용되는 멀티캐스트 주소의 부호화 방식인 영역 부호화 및 큐브 부호화 방식을 모두 적용할수있다. 또한, 하나의 고장난 스위칭 요소(SE)가 있는 MIN에서 패킷을 두번 순환시켜 임의의 멀티캐스트 패킷을 라우팅 할수있음을 증명하였고, 다수의 특정 SE 들이 고장인 경우도 멀티캐스팅이 가능하도록 확장하였다. 그리고, ATM 스위치를 위해 제안한 기법을 MIN 기반의 다중 컴퓨터에 적용하는 알고리즘을 제시하고, 두번째 순환에서 보내는 패킷의 수를 줄이도록 개선하였다. 또한 시뮬레이션을 통해 이들 알고리즘에 대한 성능을 비교 분석하였다.