The advances of networking and computing technologies leveraged large scale group communication applications such as multimedia streaming. Supporting group communications basically inquires the multicasting ability. Application layer multicast has been focused because it can support group communication without router level support.
In this dissertation, we assumed the environment that multicast session members are not known a priori and their joining sequence is also unaware. To support this extreme distributed environments, we formulated a problem named DBMDT-S that effectively models the sequenced joining problem. DBMDT-S problem aims at minimizing the diameter in the situation that session members joins sequentially. Hence given problem is not polynomial time solvable, we devsied a new heuristic algorithm named BrotherHood algorithm. The designed algorithm can evolve to a better state as the population of the session increases as time goes by.
We performed a simulation study to evaluate and the result is very promising. It is better than another heuristic algorithm named ICT, a known best until now, in terms of diameter and average distance from root to any node. Also BH does not require many repositioning of already joined nodes.
응용 계층 멀티캐스트(혹은 오버레이 멀티캐스트)는 IP 멀티캐스트의 대안으로 많은 그룹 기반의 통신에 적용이 가능한 효율적인 통신 기법이다. IP 멀티캐스트는 많은 표준화와 연구에도 불구하고 시장에서 적용하려는 시도가 성공하지 못하면서 인터넷에서 널리 사용되지 못하고 있다. 응용계층 멀티캐스트는 유니캐스트 통신 방법을 사용함으로써 라우터의 도움없이도 멀티캐스트를 지원할 수 있는 장점이 있다.
대규모의 그룹 통신을 지원하기 위해서는 응용 계층 멀티캐스트를 위한 트리 구성 방법이 매우 중요한 요소이다. 트리의 구성 방법이나 사용되는 메트릭 등에 따라 많은 종류의 멀티캐스트 트리가 생성될 수 있다. 멀티미디어 스트리밍을 위해서 많이 사용되는 메트릭은 종단간 지연시간 (end to end delay), 가용 대역폭 (available bandwidth) 등이 있을 수 있다. 트리를 구성하는 노드의 구성 요소에 따라 멀티캐스트 서비스 노드를 위한 트리, 종단 시스템을 위한 트리 구성 등이 있을 수 있다. 본 논문에서는 종단 시스템을 위한 트리를 분산된 방식으로 만드는 기법에 관해 연구하였다.
본 논문에서는 많은 그룹 통신 방법에서 시작과 끝이 정해져 있는 경우가 많으며, 세션에 참여하는 노드들이 세션에 접속하려는 시도는 시작 시점에서 많이 일어날 수 있다는 가정을 하였다. 세션의 참여하는 노드의 규모와 순서 등은 알 수 없으므로 이런 환경을 고려하기 위하여 디그리 제한 최소 지름 트리 (degree bounded minimum diameter tree, DBMDT) 문제를 확장하여 순서있는 디그리 제한 최소 지름 트리 (degree bounded minimum diameter tree with sequential joining, DBMDT-S) 문제를 정의하엿다. 드리의 지름(diameter)은 루트 노드로부터 트리에서 가장 먼 노드까지의 거리를 의미하는데, 세션의 지연을 결정하는 중요한 요소이다.
완전히 분산된 트리 구성을 위하여 노드 간의 거리를 측정하는 효율적인 기법과 지름을 최소화하기 위하여 부모 노드를 찾는 기법이 필수적이다. 본 논문에서는 Meridian라는 가장 가까운 노드를 찾는 기법을 응용하여 m개의 가장 가까운 노드를 찾는 기법을 고안하였고, 이를 토대로 부모 노드를 찾는데 사용하는 BrotherHood 알고리즘을 제안하였다.
DBMDT와 DBMDT-S 문제는 모두 NP에 속하는 문제들로 최적의 트리를 구성하는 것은 복잡도가 높다. DBMDT-S 문제를 휴리스틱(heuristic)한 알고리즘으로 풀 수 있는 BrotherHood 알고리즘은 세션의 참여자 수가 늘어나면서 각 노드의 위치에 적응적으로 트리를 구성할 수 있는 장점이 있다. 실험을 통하여 루트 노드로부터 먼 노드부터 조인하거나 가까운 노드부터 조인하는 시나리오에서도 큰 차이를 보이지 않음을 볼 수 있었다. 기존에 제시된 Greedy 알고리즘을 활용하여 트리를 구성했을 경우에 비해 노드의 재배치 수에 있어서는 유사하거나 좋지 않은 결과를 보여주는데, 지름과 재배치를 동시에 고려하였을 때는 BH 알고리즘이 더 좋은 결과를 보였다.
제안한 알고리즘을 활용하여 많은 수의 참여자가 있는 경우, 종단 시스템을 활용한 멀티캐스팅 애플리케이션 등에 효율적으로 활용할 수 있다. 특히 세션의 지속 시간이 짧은 경우 기존의 연구에서는 최적화 과정이 오래 걸려서 효율적인 트리를 구성할 수 없었던 문제를 해결할 수 있다.
