다중 제약이 있는 멀티캐스트 트리 문제에 관한 연구 = A study of Multicast Tree Problem with Multiple Constraints

국문 초록 (Abstract)

스위치 노드(switch node)로 구성된 네트워크에서 멀티캐스팅을 위한 트리를 구성하는 것은 NP-complete로 알려진 스타이너 트리 문제(Steiner tree problem)로 정형화된다. 현재의 멀티캐스트를 요구하는 서비스들은 대개 대용량의 멀티미디어 데이터를 요구하게 된다. 이러한 서비스들은 텍스트 기반의 서비스에 비해 서비스의 질(Quality of Service)이 아주 중요한 요소가 되고, QoS는 전송에 소요되는 시간에 매우 민감하게 반응한다. 단일 제약을 갖는 멀티캐스트 트리 문제에 적용되는 휴리스틱은 이미 많이 연구되었으나, 노드 연결도 제한과 평균 홉수를 고려하는 다중 제약이 있는 멀티캐스트 트리 문제에 적용되는 휴리스틱에 대한 연구는 없었다. 본 논문에서는 다중 제약을 만족하는 효율적인 멀티캐스트 트리 문제에 적용 가능한 알고리즘을 제안하고, 실험을 통하여 성능을 평가하였다.

다국어 초록 (Multilingual Abstract)

In the telecommunications network, multicasting is widely used recently. Multicast tree problem is modeled as the NP-complete Steiner problem in the networks. In this paper, we study algorithms for finding efficient multicast trees with hop and node degree constraints. Multimedia service is an application of multicasting and it is required to transfer a large volume of multimedia data with QoS(Quality of Service). Though heuristics for solving the multicast tree problems with one constraint have been studied, however, there is no optimum algorithm that finds an optimum multicast tree with hop and node degree constraints up to now. In this paper, an approach for finding an efficient multicast tree that satisfies hop and node degree constraints is presented, and the experimental results explain how the hop and node degree constraints affect to the total cost of a multicast tree.

참고문헌 (Reference)

1 "The Degree-Constrained Multicasting Algorithm Using Ant Algorithm" 1 : 370-374, 2003

2 "Steiner Tree Problems" 55-89, 1992

3 "Solution to QoS Multicast Routing Problem Based on Heuristics Genetic Algorithm" 24 : 55-61, 2001

4 "Optimization by a Colony of Cooperating Agents" 26 (26): 29-41, 1996

5 "Multicommodity Flow Models for Spanning Trees with Hop Constraints" 95 : 178-190, 1996

6 "Multicast Routing Algorithms and Protocols" 90-102, January/Feburuary2000

7 "How bad in naive multicast routing?" 82-89, 1993

8 "Degree-constrained multicasting in point- to-point networks" 1 : 369-376, April1995

9 "Ant Colony System" 1 (1): 53-66, 1997

10 "Ant Colony Optimization for Multicast Routing" 243-246, 2000

11 "A Survey of QoS Multicasting Issues" 82-87, June2002

12 "A Network- Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees" 24 : 310-324, 1997

13 "A Lagrangean Approach to the Degree-Constrained Minimum Spanning Tree Problem European Journal of Operational Research" enant : 325-331, 1989

14 "A Fast Algorithm for Steiner Trees" 141-145, 1981