Group Communication System (GCS) is an important building block for reliable, fault-tolerant distributed applications. This is useful especially when processes geographically span over large networks like the Internet. Despite its usefulness, when GCS operate over multiple WANs, GCS needs to cope with frequent membership changes due to highly variable and unpredictable latency in WANs.
Most membership management schemes used in the existing systems are LAN-oriented group membership services. They are not suitable if exchanging messages among member processes becomes expensive in terms of process computation or network load, which is common in WANs.
There are a few GCSs supporting a group membership service for WANs, the schemes also cope with heavy computation and do not scale when they spans over multiple WANs.
In this thesis we propose a new scheme that improves the scalability of a group membership service for WANs by exploiting dedicated membership servers configured into multiple layers and reaching global agreement on the view through layered servers. It improves the scalability of a process group of N member process from O($N^2$) to O($N^3$) with three layers. Computer simulation verifies that the proposed scheme requires much smaller number of messages for reaching an agreement and does that much quicker. In addition, the proposed scheme prevents applications from being blocked until reaching the final view agreement when the applications permit temporary inconsistency.
그룹 통신 시스템(GCS)은 분산 어플리케이션의 신뢰성과 결함 감내 능력을 보장할 수 있는 중요한 도구로서 그룹 통신 시스템은 분산 시스템에서 신뢰성을 위해 널리 사용되는 프로세스 그룹의 일관성을 보장할 수 있다. 이러한 일관성 보장은 모든 목적지로 정확하게 메시지를 전송함으로써 가능하며 이를 위해서 각 멤버 프로세스들이 인지하고 있는 멤버쉽(현재 그 그룹에 소속된 멤버들의 리스트)관리가 중요하다.
현재 네트워크 환경은 인터넷의 보급과 장비의 성능 향상으로 인하여 지역적으로 멀리 떨어진 다수의 프로세스들의 협동 작업 요구가 커지고 있다. 그러나, 이러한 WAN환경에서는 네트워크의 연결성이 약하고 통신의 지연 정도가 크며 또한 그 지연 정도를 예측하기조차 힘들기 때문에, 그룹의 멤버쉽이 번번히 변경된다.
ISIS[9,12], Totem[6,7,8,28], Transis[4,15,16,17], Horus[21,22,29], Netwop[19]등 GCS에 관한 기존 연구의 대다수는 LAN또는 소수 LAN이 연결된 네트워크상에서 구성된 프로세스 그룹의 통신을 전제로 하고 있다. 모든 멤버 프로세스들이 자신이 인식하고 있는 멤버쉽의 정보를 주고받아 모두 일치할 때 작업을 진행할 수 있는 그들의 방식이 그대로 WAN에 적용 된다면 막대한 비용의 계산 및 통신 비용을 요구하며 결과적으로 그 확장성에 한계를 가진다.
Relacs[10,13,26]나 [2,23,24]은 WAN환경의 그룹 통신을 시스템을 제안하고 있지만, 그들 또한 대규모의 프로세스들이 협동하는 경우에는 마찬가지의 계산 및 통신 비용을 필요로 한다.
본 논문에서 우리는 WAN용의 그룹 멤버쉽 서비스의 확장성을 향상시키기 위하여, 전용 멤버쉽 서버를 계층 구조로 구성하고 점진적으로 멤버쉽에 대한 멤버 프로세스들의 동의를 얻는 새로운 방법을 제안한다. 각 멤버 프로세스들은 자신의 지리적 위치에 근접한 멤버쉽 서버에 자신을 등록하고 멤버쉽 결정과정에는 참여하지 않는다. 멤버쉽 서버는 자신이 관리하고 있는 멤버들의 상태와 네트워크의 연결상태를 모니터하면서 멤버쉽 변경을 감지하며 다른 멤버쉽 서버와의 정보교환을 통해 멤버쉽을 결정하여 자신의 멤버 프로세스들에게 통보한다. 멤버쉽 서버간의 정보교환은 계층 구조를 경유하는데, 멤버쉽 서버들은 지리적은 근접도를 기준으로 소집합을 구성한다. 따라서, 각 단계에서 소수의, 가까운 거리에 위치한 서버들끼리 메시지를 주고받으므로 통신 비용이 경미하며 동의에 이를 가능성 또한 크다. 하위 계층에서 동의된 정보를 가진 대표 서버들은 상위계층에서 다른 대표 서버와의 정보 교환을 통하여 동의를 얻는데, 하위 계층의 동의가 최상위 계층에서 만족되어질 때 멤버쉽은 결정되고 그 결정은 같은 계층 구조를 통하여 모든 서버에게 전파되고 각 서버들은 일제히 자신의 멤버 프로세스에게 변경된 새로운 멤버쉽을 통보한다. 뿐만 아니라, 하위 계층에서의 동의된 내용이 상위계층에서의 정보 교환으로 얻은 결과와 다를 때에도, 최하위 계층에서 다시 시작하기 보다는, 두 멤버쉽 정보의 포함관계를 검사하여 일관성을 유지할 수 있을 때는 멤버쉽 결정 과정을 계속 진행할 수 있다. 따라서, 일시적인 비일관성을 허용하는 어플리케이션의 경우라면 멤버쉽 변경의 과정 중에도 중단 없이 메시지 송신이 가능하다.
기존의 다른 멤버쉽 알고리즘과 3계층 구조를 가진 우리 방법의 확장성의 비교할 때, N개의 멤버 프로세스를 가진 그룹에 대해서, O($N^2$)에서 O($N^3$)로 향상시킨다. 논문 내 시뮬레이션 결과를 통하여 제안된 알고리즘이 멤버쉽의 동의에 이르기 위해 교환되는 메시지의 수와 소요되는 시간을 감소시킴을 보였다.
