멀티캐스트 지연변이 문제에 대한 효율적인 코어 선택 추정 알고리즘 = The Algorithm of Efficient Core Selection Estimation for the Multicast Delay Variation Problem and Minimum Delay Variation

국문 초록 (Abstract)

멀티캐스트 기술이 발전함에 따라 멀티캐스트 라우팅을 지원하는 실시간 그룹 어플리케이션들이 정점 증가하고 있으며 더욱 중요하게 되어가고 있다. 실시간 어플리케이션의 가장 중요한 요소 중의 하나는 지연변이 문제가 있으며 이는 DVBMT(Delay- and delay Variation-Bounded Multicast Tree) 문제로 잘 알려져 있다. DVBMT 문제란 제한된 시간 내에 종단간의 지연과 지연변이를 만족시키는 것을 뜻한다. DVBMT는 NP-Complete 문제로 알려져 있으며, 이를 풀기위한 시도로 DVMA(Delay Variation Multicast Algorithm), DDVCA(Delay and Delay Variation Constraint Algorithm) 등이 제안된 바 있다. 본 논문에서는 이러한 알고리즘보다 더욱 효율적인 알고리즘을 제안한다. 성능평가를 통한 본 알고리즘의 효율성은 DDVCA보다 더욱 높은 것으로 평가되었으며 그 효율 정도는 9%～29%의 성능향상을 보인다. 본 논문의 시간복잡도는 DDVCA와 같은 O(㎟)이다.

다국어 초록 (Multilingual Abstract)

With the development of the multicast technology, the realtime strategy among the group applications using the multicast routing is getting more important. An essential factor of these real-time application is to optimize the Delay- and delay Variation-Bounded Multicast Tree (DVBMT) problem. This problem is to satisfy the minimum delay variation and the end-to-end delay within an upper bound. The DVBMT problem is known as NP-complete problem. The representative algorithms for the problem are DVMA, DDVCA, and so on. In this paper, we show that the proposed algorithm outperforms any other algorithm. The efficiency of our algorithm is verified through the performance evaluation and the enhancement is up to about 9% to 29% in terms of the multicast delay variation. The time complexity of our algorithm is O(㎟).

참고문헌 (Reference)

1 "On multicasting with minimum costs for the Internet topology" 2400 : 736-744, August2002

2 "On Generating Random Network Structures: Connected Graphs" 3090 : 483-491, 200409

3 "On Efficient Core Selection for Reducing Multicast Delay Variation under Delay Constraints" 9 : 2385-2393, September2006

4 "Multicast routing with end-to-end delay and delay variation constraints" 15 (15): 346-356, April1997

5 "Multicast routing for multimedia communication" 286-292,

6 "An approximate solution for the steiner problem in graphs" 573-577, 1980

7 "A fast and efficient heuristic algorithm for the delay- and delay variation-bound multicast tree problem" 25 : 825-833, 2002

8 "A fast algorithm for steiner trees" 15 : 141-145, 1981