Overlay multicast can effectively use the Internet as a lower level infrastructure to provide services to members. Overlay multicast is proposed as an alternative approach for providing multicast services in the Internet. In the overlay multicast protocols, each multicast member is responsible for forwarding the multicast packets. Thus, network failure can occur by leaving or joining of nodes. In such dynamic changes, we strive to recover overlay multicast tree to provide resilient services.
We address efficient recovery strategies of multicast in dynamic overlay network. One is instant strategy and the other is centralized strategy. In centralized strategy, we want to solve degree-bounded minimum maximum-delay spanning tree. This problem is known as NP-hard. Thus tabu search is introduced to solve our problem. Through the experiments, we have verified performance of recovery strategies.
멀티캐스트는 데이터를 수신자들에게 전달하는 전송방식 중 하나로, 둘 이상의 다른 수신자들에게 동시에 전송하는 방식이다. 특정한 한 사람의 수신자에게 데이터를 전송하는 유니캐스트와 대응하는 개념이다. 유니캐스트는 수신자의 수만큼 데이터를 반복해서 보내야 하기 때문에 통신망의 효율을 저하시키고, 보내는 이의 전송 부담도 크다.
IP 멀티캐스트(Internet protocol multicast)는 하나의 소스로부터 LAN(Local area network) 또는 WAN (wide area network)상의 다수의 목적지로 IP 데이터그램을 전송하기 위한 프로토콜이다. 명백한 장점들이 있음에도 불구하고 구현 기술의 부족 등으로 아직 사용되지 못하고 있다.
오버레이 멀티캐스트(Overlay multicast)는 유니캐스트를 이용하여 멀티캐스트와 유사한 서비스를 제공할 수 있도록 해 준다. 멀티캐스트와는 달리, 데이터를 전달하는 기능이 노드(node)에 존재한다. IP 멀티캐스트에서는 멀티캐스팅의 기능이 라우터(router)에 있었지만, 오버레이 멀티캐스트에서는 노드에 존재한다. 따라서 멀티캐스트 멤버들이 데이터를 전송하는 역할을 담당한다.
멀티캐스트 서비스를 제공하기 위해서 소스(source)와 멀티캐스트 멤버들로 이루어진 멀티캐스트 트리(Multicast tree)를 구성할 수 있다. 시간이 흐르면서, 데이터를 다 받은 노드는 트리를 떠날 수 있고, 새로운 노드가 서비스를 받고자 트리에 합류하기를 요청할 수 있다. 이렇게 동적으로 변하는 네트워크에서 서비스가 끊임없이 재빨리 제공해야지 효율적인 멀티캐스트 트리라고 할 수 있을 것이다. 동적인 변화가 발생함에 따라, 트리 구조가 유지 되지 못해서 서비스가 원활하게 전달되지 않을 수 있다. 따라서 이러한 경우에 대비한 복구 전략을 제시하고자 한다. 복구 시에 중요하게 고려하고 있는 점들이 있다. 서비스가 끊김을 최소화하기 위해 신속하게 복구해야 하고 서비스 전송시간까지 최소화하는 효율적인 복구를 하고자 한다. 그래서 즉각적으로 복구하기 위한 즉각적인 전략과 전송시간이 최소화된 멀티캐스트 트리를 얻기 위한 중앙 전략을 제시하였다. 이 문제를 해결하기 위해서 정수계획법(Integer programming)과 타부 알고리즘(tabu algorithm)을 도입하였다. 실험을 통한 결과, 우리가 제시한 알고리즘이 좋은 성능을 주는 것으로 나타났다.
