Overlay Multicast is a promising approach to overcome the implementation problem of IP multicast. Real time services like internet broadcasting are provided by overlay multicast technology due to the complex nature of IP multicast and the high cost to support multicast function. Since multicast members can dynamically join or leave their multicast group, it is necessary to keep a reliable overlay multicast tree to support real time service without delay. In this paper, we consider path level reliability that connects each member node. The problem is formulated as a binary integer programming which maximizes the reliability of multicast tree. Tabu search based algorithm is presented to solve the NP-hard problem.
오버레이 멀티캐스트 (Overlay Mulicast)는 IP (Internet Protocol) 멀티캐스트를 구현하는데 있어 발생하는 문제점을 극복할 수 있을 것이라 평가되는 유력한 방법이다. 인터넷 방송과 같은 실시간 서비스는 IP 멀티캐스트 보다는 오버레이 멀티 캐스트로 제공하는 것이 더 효율적이다. 이는 멀티캐스트를 구현하기 위해서 높은 비용을 지불해야 하는 IP 멀티캐스트의 복잡한 기술적 특성에 기인한다. 하지만 오버레이 멀티캐스트에서는 각각의 멀티캐스트 멤버가 언제든지 멀티캐스트 그룹에서 떠나고 또 새로 그룹으로 들어올 수 있는 특성 때문에 신뢰성이 높은 오버레이 멀티캐스트 트리를 유지하는 것이 필요하다. 특히 이는 실시간 서비스를 시간 지연 없이 서비스 하기 위해 중요하다. 이 논문에서는 오버레이 멀티캐스트 트리 (tree) 를 구성하는 데 있어 각 멤버 노드를 연결하는 경로 수준의 신뢰성에 대해서 고려하였다. 이러한 문제를 이진 정수 계획법 (Binary Integer Programming) 으로 표현하였다. 주어진 문제는 NP-hard 문제로 이를 효율적으로 해결 하기 위하여 타부 서치 알고리즘 (Tabu Search Algorithm) 을 사용하였다.
