This thesis investigates three problems in related with multicast in IP network. We present formulations and the algorithms.
First, the multiple multicast tree allocation problem is discussed and algorithms are proposed to solve the congestion problem in the IP network. The multicasting is defined as the distribution of the same information stream from one to many nodes concurrently. There has been an intensive research effort to design protocols and construct multicast routing graphs for a single multicast group. As the congestion measure the minimum residual capacity is considered. Two phase algorithm MMTA is investigated for multiple multicast tree allocation both for identical and different bandwidth requirement by the multicast groups. The central and distributed implementation of the multiple multicast tree is discussed for the deployment in the real IP network. The performance of the proposed MMTA is compared with other procedures. Computational results show that the two-phase MMTA outperforms other procedures. Approximately 3-7% improvement in the residual capacity is obtained by the MMTA. The solution gap from the upper bound by the well-known branch and bound is within 2-11% depending on the problem size.
Second, we consider the fairness as well as the transmission load in the layered multicasting. As a promising solution to tackle the network heterogeneity in multicasting, layered multicast protocols such as Receiver-driven layered multicast (RLM) and Layered video multicast with retransmission (LVMR) have been proposed. Lexicographically fair bandwidth allocation among multicast receivers is considered under the constraint of minimum bandwidth requirement and the link capacity of the network. The problem of transmission load in the layer multicasting due to the various user requirement is also examined by minimizing the number of layers in each session.
The bandwidth allocation is formulated as a nonlinear integer programming problem. A dual objective tabu search is proposed to solve the fairness and transmission load problem in the multicast network. Outstanding performance is obtained by the proposed tabu search. When only the fairness objective is considered, the solution gap from the optimal solution is less than 2% in problems with 50 virtual sessions. The complexity of the dual objective largely depends on the weighting factor of the two objectives. Even in tough cases the proposed tabu search provides excellent solution the gap of which is within 6% from the optimal solution.
Finally, a tree rearrangement problem in overlay multicast tree is considered when a node failure is occurred. The tree rearrangement problem is formulated as a binary integer programming problem. The problem in overlay multicast tree is solved by lagrangean relaxation based algorithm. The proposed algorithm provides the solution the gap of which is within 3% from the optimal solution.
멀티캐스트는 일대다 (one-to-many)를 위한 통신 방식이다. 멀티캐스트 방식을 사용하면 하나의 데이터 패킷이 인터넷을 통해 수많은 수신자에게 동시에 전달되므로 인터넷 방송을 비롯해 다자간 파일전송, 원격 소프트웨어 갱신, 멀티미디어 회의, 웹 캐스팅 등과 같은 멀티캐스트형 응용 서비스를 구현하는 요소기술로 활용할 수 있는 것 등의 장점이 있다. 그러나, 멀티캐스트 기술은 전송방식의 우수성과 수많은 연구에도 불구, 아직 크게 활성화되지 못한 상태이다. 이는 멀티캐스트가 가진 또 다른 특징, 즉 기술적 복잡성과 신뢰성 확보의 문제, 그리고 적합한 응용 서비스의 부재에서 원인을 찾을 수 있다. 그러나 최근 들어 인터넷 방송 서비스가 멀티캐스트의 주요 응용서비스로 부상하면서 멀티캐스트는 통신과 방송의 융합을 특징으로 하는 주요 기술로 떠오르고 있다.
미국과 유럽을 중심으로 10여 년의 연구 및 개발 결과를 기반으로 IETF, ITU-T 등 국제적인 통신기술 표준화기구에서 관련 기술의 표준화 작업이 진행되고 있으나 아직까지 인터넷에 본격적으로 적용되지는 않고 있다.
위와 같이 멀티캐스트는 효율성을 인정 받고 있고 수요도 있지만, 기술 자체의 복잡성 때문에 인터넷에 적용되지 않는 것이 가장 큰 문제점 중에 하나라고 할 수 있다. 본 논문에서는 IP 네트워크에서 여러 개의 멀티캐스트 세션이 존재할 때 네트워크의 병목현상을 최소화 하는 경로 설정 방식과 계층적 멀티캐스트 기술에서 수신자간 공평성과 세션의 부하를 최소화하는 네트워크 자원 할당 기법을 제안한다.
첫째, 인터넷 도매인 상에 여러 개의 멀티캐스트 세션이 존재할 때, 각각의 멀티캐스트 세션을 위한 멀티캐스트 트리를 결정하는 문제에 대해서 연구하였다. 기존의 연구에서는 이와 같이 여러 개의 멀티캐스트 트리를 결정하는 문제에서 고려하는 목적식이 크게 두 가지로 분류 할 수 있는데, 전체 트리 비용의 합을 최소화 하는 것과 각 네트워크 링크의 혼잡을 최소화 하는 것이 있다. 본 연구에서는 후자의 것을 목적식으로 하는 문제에 대해서 연구하였다. 이 문제에 대해 기존에 제안된 알고리즘보다 복잡도가 더 간단한 알고리즘을 제시하였고 실제 인터넷에 분산적으로 실행이 될 수 있는 알고리즘을 제시하였다. 또한 기존의 알고리즘에서는 각 멀티캐스트 세션이 동일한 트래픽 요구량을 갖는다고 가정하였지만, 본 논문에서는 다양한 트래픽 요구량을 갖는 경우에 대해해서도 해법을 제시하였다. 실험 결과 제안된 알고리즘인 MMTA가 기존의 알고리즘에 비해 3-7% 더 좋은 성능을 보여주고 있다.
둘째, 계층적 멀티캐스트는 동일한 멀티캐스트 세션에 속하는 수신자들이 서로 다른 수신 용량을 가지고 있을 경우 각 수신자의 용량에 따라 다른 속도로 데이터를 전송하는 방식이다. 계층적 멀티캐스트를 지원하기 위한 프로토콜들이 제시되어 왔지만 수신자간 그리고 세션간의 공평성을 고려하지 않았다. 또한 송신자에서 전송되는 데이터의 계층이 많아질수록 송신자측 부하가 많아지므로 계층의 수를 적절한 수준으로 유지 시킬 필요도 있다. 본 논문에서는 공평성과 세션의 부하를 최소화, 이 두 가지를 고려한 대역폭 할당 방법을 제시하였다. 이 문제를 해결하기 위해 본 논문에서는 타부 서치 알고리즘을 사용하였다. 또한 두 개의 목적식을 가지고 있으므로 이에 적합한 dual-objective 타부 서치를 제안하였다. Dual-objective 타부서치는 두 목적식중 먼저 중요도가 높다고 결정되어진 것에 대해 primary 타부 서치를 실행하고, 이 때 얻어진 최적해를 중요도가 낮은 목적식을 해결하기 위한 secondary 타부 서치의 제약식으로 추가하여 타부 서치를 실행한다. 제안된 알고리즘의 성능을 평가하기 위해 유전 알고리즘과 CPLEX를 이용해서 구한 최적해를 비교대상으로 하였다. 모든 실험 문제에서 제안된 알고리즘이 유전알고리즘에 의해 나온 해보다 좋은 해를 구할 수 있다.
마지막으로, 오버레이 멀티캐스트 네트워크에서 하나의 멀티캐스트 노드가 절단 되었을 때 연결이 끊어진 노드들을 다시 멀티캐스트 트리에 합류시키는 방법에 대해서 연구하였다. 연결이 끊어진 노드들이 다시 멀티캐스트 트리에 합류할 때 딜레이 바운드를 만족시키지 못하는 경우가 발생할 수 있다. 이러한 경우를 위해 본 논문에서는 멀티캐스트 서비스 노드를 딜레이 바운드를 만족시키기 위해 제안했다. 멀티캐스트 서비스 노드가 있을 때, 비용을 최소화 하면서 다시 멀티캐스트 트리에 합류하는 경로를 설정하는 문제를 정식화 했고, 이를 라그랑쥐 릴렉세이션을 기반으로한 알고리즘으로 이를 해결했다. 제안된 알고리즘은 최적해에서 3% 이내에 있는 해를 빠른 시간내에 구할 수 있으므로 매우 효과적이라 할 수 있다.
