As multimedia services including video, voice, and data communications are increasing, the broadband integrated services digital network (B-ISDN), as an infrastructure of future networks to enable multimedia services, has been intensively studied. [1, 56]. Many of multimedia services require multicast communications in addition to conventional point-to-point communications [26,30]. Multicast communication which the same message is delivered from a source to an arbitrary number of destinations, is fundamental in supporting communication primitives including terrestrial broadcasting, teleconferencing, and video-on-demand (VOD) services in B-ISDN environments [11, 22, 65]. On the other hand, multicast in multicomputer systems is a fundamental operation in several applications including data replication, barrier synchronization, and protocol for cache coherence in order to implement distributed shared-memory systems [5, 21, 38, 41, 71].
Multistage interconnection networks (MINs) are a popular class for constructing the internal architecture of the asynchronous transfer mode (ATM) switch which was accepted as the switching and transmission technique to support B-ISDN services and the interconnection architecture of multicomputer systems [1, 30, 56, 59, 65]. Many of the ATM switches and multicomputers based on MINs are proposed, such as the Synoptics Communications Lattis-cell[17], the DEC GIGAswitch [60], Phoenix switch[39], the IBM SP-1 [29, 62] / SP-2 [61], and the NEC Cenju-3 [37]. As the number of inputs/outputs in the MIN-based system increases, the total communication bandwidth and processing capability of the system as scale up as well.
There are two alternative approaches to support multicast connections in the MIN-based systems. The first is to add a copy network at the front of a routing network, which replicates the cell to obtain the number of copies requested by a given multicast connection [8, 26, 40, 42, 67]. Those copies will be transmitted through the routing network to the desired destinations. Instead of designing the copy network which additional hardware is required, the second approach is a recursive scheme which simulates the function of a copy network by using the routing network recursively [12, 13, 18, 57, 67, 70]. Most of the proposed multicast algorithms for ATM switch and multicomputers do not consider deadlock which radically degrades the system's performance for multiple multicast connections [13, 42]. Also, performance of these multicast algorithms is evaluated in terms of the number of recycling passes for single multicast connection (static behaviour). However, their performances are not analyzed where occurrence of blocking between several multicast connections is concerned (dynamic behaviour).
To provide multicast connection with the MIN-based systems, a multicast packet should contain its own routing header which specifies reachable destinations in one cycle so that switching elements make appropriate routing decisions. As one of multicast header encoding scheme, a multi-address encoding scheme has the advantage that a multicast packet is directly sent to all destination nodes at a time through the MIN [14, 13]. However, such a multi-address encoding scheme is not suitable for ATM switches handling fixed-sized cells, because of the need for constructing variable-sized headers. Most of multicast ATM switches employ a restricted-address encoding scheme [12, 18, 40, 57, 67, 70] which constructs the small- and fixed- sized multicast header. The single region and the single cube encoding schemes belonging to the restricted-address encoding scheme is employed in the copy network [26, 40], the NEC Cenju-3, or the nCUBE-2.
In this thesis, we propose recursive multicast algorithms for the MIN-based ATM switches, which employ restricted-address encoding schemes. While it takes two phases for the algorithm employing region encoding scheme to send the multicast packet to its own desired destinations, it takes two or three phases for the algorithm employing cube encoding scheme. In the proposed algorithms, the constituent packets which are copied from the single multicast packet arrive at their own destinations without blocking through the MIN. For link utilization, algorithms coalescing destinations of a given multicast packet into set of regions or cubes are presented. We also present a novel deadlock avoidance approach in the unbuffered MIN. The proposed recursive multicast algorithms are more efficient than other algorithms in terms of the number of phases through the MIN, hardware cost processing a multicast header, and the amount of the internal links used for sending a multicast packet.
In this thesis, we design the MIN-based multicast ATM switch to employ the proposed recursive multicast algorithms and propose the performance model for the switch in unbuffered or buffered MIN. By such performance model, we analyze their performance characteristics in terms of switch delay and throughput, concerning occurrence of blocking between multiple multicast connections. The performance of the multicast ATM switch has characteristics that throughput decreases against increasing fanout and multicast rate.
The proposed recursive multicast algorithms are applied into wormhole or virtual cut-through switched multicomputers. Unlike MIN-based ATM switches, a multicast packet has an additional field including its desired destinations in multicomputer systems. We define the multicast header formats and present the multicast algorithms for unidirectional/bidirectional MIN-based multicomputers. The proposed multicast algorithms in MIN-based multicomputers have better performance than other algorithm employing restricted-address encoding scheme.
영상, 음성, 데이타 통신을 포함하는 멀티미디어 서비스가 증가함에 따라서, 그러한 서비스를 가능케 하는 통신망의 하부구조로써 광대역 종합정보 통신망에 대한 많은 연구가 이루어지고 있다. 대부분의 멀티미디어 서비스는 기존의 점대점 통신 뿐만아니라 멀티캐스트 통신을 요구한다. 같은 내용의 메시지를 여러개의 목적지로 전달하는 멀티캐스트 통신은 광대역 종합정보 통신망을 이용한 텔레비젼 방송, 원격 화상회의, 주문형 비디오 서비스를 지원하기 위한 통신의 근간이 된다. 한편, 다중컴퓨터 시스템에서 분산 공유-메모리 시스템을 구현하기 위한 데이타의 복제, 경계선 동기화, 캐쉬 일관성 유지 프로토콜에 필수적이다.
다단계 상호 연결망(MIN)은 광대역 종합정보 통신망 서비스를 지원하는 스위칭과 전송 기법으로 승인된 비동기식 전달 모드(ATM)의 기반 구조와 많은 수의 ATM 스위치와 다중컴퓨터가 MIN을 기반으로 제안되었다. 이와같은 MIN을 기반으로 하는 시스템에서 입출력단의 수를 늘림으로써, 시스템의 통신 대역폭과 처리 능력을 증가시킬 수 있다.
MIN을 기반으로 하는 시스템에서 다음과 같은 두가지 방법으로 멀티캐스트 통신을 지원한다. 하나의 방법은 멀티캐스트 통신이 요구하는 목적지의 수만큼 패킷을 복사하는 복사 네트워크를 사용하고, 복사된 패킷을 라우팅 네트워크를 통해서 원하는 목적지로 보내어 멀티캐스트를 지원한다. 다른 하나의 방법은 부가적인 복사 네트워크를 두는 대신에, 라우팅 네트워크를 순환하면서 패킷을 복사하는 재귀적인 방법이다. ATM 스위치와 다중컴퓨터에서 제안된 대부분의 멀티캐스트 알고리즘은 여러개의 멀티캐스트 연결시 시스템의 성능을 급격히 감소시키는 교착상태에 대해 고려하지 않고 있다. 또한, 이러한 멀티캐스트 알고리즘의 성능은 하나의 멀티캐스트 연결시에 드는 비용으로 정적인 분석만 이루어졌으며, 여러개의 멀티캐스트 연결시에 발생하는 충돌을 고려한 동적인 분석은 이루어지지 않았다.
MIN을 기반으로 하는 시스템에서 멀티캐스트 연결을 제공하기 위해서 멀티캐스트 패킷은 스위칭 소자에서 경로를 배정하여 출력단에 도달가능한 목적지를 표시하는 라우팅 헤더를 포함하여야 한다. 멀티캐스트 헤더 부호화 기법 중의 하나인 다수-주소 부호화 기법은 멀티캐스트 패킷을 MIN을 통하여 한번에 모든 목적지로 보낼 수 있는 장점이 있다. 그러나, 가변적인 크기의 헤더를 구성하기 때문에 ATM 스위치에는 적합하지 않다. 대부분의 멀티캐스트 ATM 스위치는 적고 고정된 크기의 멀티캐스트 헤더를 구성하는 제한-주소 부호화 기법을 사용한다. 제한-주소 부호화 기법으로 영역 부호화 기법과 큐브 부호화 기법이 있으며, 각각 Lee의 복사 네트워크, NEC의 Cenju-3, nCUBE-2에서 사용된다.
본 논문에서는 제한-주소 부호화 기법을 사용하여 MIN을 기반으로 하는 ATM 스위치에 적합한 재귀적인 멀티캐스트 알고리즘을 제안한다. 멀티캐스트 패킷을 원하는 목적지까지 보낼 때, 영역 부호화 기법을 사용하는 알고리즘은 MIN을 두번 순환하는데 반하여, 큐브 부호화 기법을 사용하는 알고리즘은 두번 또는 세번 순환하여야 한다. 제안된 알고리즘에서 하나의 멀티캐스트 패킷에서 복사된 패킷들은 서로 충돌을 일으키지 않으면서 각각의 목적지로 전달된다. 시스템의 자원의 효율을 위해서, 멀티캐스트 목적지들을 영역들의 집합 또는 큐브들의 집합으로 병합하는 알고리즘도 제시하였다. 그리고, 버퍼가 없는 MIN에서 여러개의 멀티캐스트 연결시에 발생가능한 교착상태를 방지하는 기법도 제시하였다. 제안된 재귀적인 알고리즘은 MIN을 순환하는 횟수와 멀티캐스트 헤더를 처리하는 하드웨어 비용과 자원의 사용량 측면에서 효율적이다.
본 논문에서는 제안된 재귀적인 멀티캐스트 알고리즘을 구현한 MIN을 기반으로 하는 멀티캐스트 ATM 스위치를 설계하여 버퍼가 없는 MIN과 버퍼가 있는 MIN에서 스위치의 성능모델을 제안하였다. 이 모델에 의해서, 여러개의 멀티캐스트 연결시에 발생하는 충돌을 고려한 스위치의 처리율과 지연시간 측면에서 성능특성을 분석하였다. 멀티캐스트 ATM 스위치의 성능은 목적지의 수가 많을수록 멀티캐스트 패킷이 많을수록 처리율은 감소하고 지연시간을 늘어나는 특성을 보인다.
제안된 재귀적인 멀티캐스트 알고리즘을 웜홀 또는 가상 컷-쓰루 스위치를 사용한 다중컴퓨터 시스템에 응용하는 점에 대해서도 논하였다. MIN을 기반으로 하는 다중컴퓨터 시스템은 ATM 스위치와 달리, 멀티캐스트 패킷은 원하는 목적지에 관한 모든정보를 포함하는 부가적인 데이타가 필요하다. 단방향 또는 양방향 MIN을 기반으로 하는 멀티컴퓨터를 위한 멀티캐스트 헤더의 형태를 정의하고 멀티캐스트 알고리즘을 제안하였다. 제안된 알고리즘은 제한-주소 부호화 기법을 사용하는 다른 알고리즘에 비해서 더 나은 성능을 보인다.
