In high speed networks, multicast is becoming an important requirement to support multimedia services. Multicast applications, such as audio- and video conferencing, collaborative environments and distributed interactive simulation, by and large, involve a source sending messages to a selected set of destinations with varying Quality-of-Service (QoS) delivery constraints. This requires the underlying network to provide multicasting and QoS capabilities to efficiently support these applications. QoS parameters are used to express the applications' requirements that must be guaranteed by the underlying network. Hence, the importance of multicast routing algorithms to satisfy the QoS requirements of each individual application is increasing.
In this thesis, we studied the relation between constrained algorithm and QoS. The unconstrained and constrained problem of least loaded routing in ATM networks was discussed. As a result we know that the constrained algorithm satisfies QoS requirement. Therefore we apply constrained algorithm to multicast routing for QoS. We survey some related works in multicast routing algorithm and considered these for real time applications, especially focusing on unconstrained and constrained algorithms. Finally we propose an efficient multicast routing algorithm that has QoS constraints.
In order to support real-time applications, several delay-constrained heuristics have been proposed in multicast routing. These delay-constrained algorithms try to heuristically construct a low cost tree subject to a given upper bound on end-to-end delay. However, some of these heuristics may fail to provide a low cost tree as they assume that network links are symmetric. Furthermore, the time required to construct such a tree may be prohibitive, especially for large networks, as they employ a breadth-first search algorithm to find feasible low-cost paths or iteratively replaces the edges in the tree until the tree cost cannot be further reduced. The proposed algorithm has fast execution time because it uses the average delay method and the efficient tree construction method which makes the destination nodes appear as new sources.
In addition to fast execution time, we consider inter-destination delay variation as well as end-to-end delay for QoS requirements. There are several situations in which the need for bounded variation among the path delays arises. While the delay bound represents an upper bound on the acceptable end-to-end delay along any path from a source to a destination in the multicast group, the inter-destination delay variation gives the maximum difference that can be tolerated between the end-to-end delays along the paths from a source to any two destinations.
Depending on the nature of applications, a user may require multicast services that fulfill a single QoS or a combination of several. The tree construction method problem that satisfies both end-to-end delay and inter-destination delay variation as QoS requirements is formulated as delay- and delay variation - bounded multicast tree (DVBMT) problem. To solve DVBMT problem an efficient heuristic algorithm, Delay Variation Dependent Multicast Routing (DVDMR) algorithm, is proposed.
Besides QoS requirements, it is very important to minimize the total cost of multicast tree as a network point of view. Also, as network is becoming lager and many real-time applications are requiring more bandwidth, the ability which scales well to large network and multicast group is needed.
We evaluated our DVDMR algorithm through extensive simulations, comparing with other heuristic multicast routing algorithms. The proposed algorithm generates efficiently cost multicast tree without violating end-to-end delay and delay variation constraints, with having fast execution time and has good scalability to the multicast groups in large networks.
초고속망에서 멀티미디어 서비스를 지원하기 위한 멀티캐스트는 점점 더 중요한 요구사항이 되고 있다. 음성 및 화상회의, 분산환경에서의 협동작업등 최근의 멀티캐스트 응용들은 다양한 서비스 품질 (QoS: Quality of Service)의 보장을 요구하고 있다. 따라서 네트워크는 이러한 응용들을 효과적으로 지원하기 위하여 멀티캐스팅을 제공할 수 있고, QoS 보장 능력이 있어야 한다. 이러한 배경 하에 각 응용들의 QoS 요구조건을 만족시킬 수 있는 멀티캐스트 라우팅 알고리즘의 중요성이 커지게 되었다.
멀티캐스트 라우팅 알고리즘은 그 구현방법과 QoS 고려여부에 따라 여러 가지 분류로 나뉠 수 있다. 일반적으로 제한조건 알고리즘은 라우팅 트리를 형성할 때 QoS 파라미터를 고려하기 때문에 QoS 요구조건을 만족시킨다.
본 논문에서는 이 분류 중에서 QoS 제한 조건 보유여부에 따른 분류인 제한조건 알고리즘과 비제한 조건 알고리즘에 대해 중점을 두어 지금까지 제안된 알고리즘들을 살펴보았으며, ATM네트워크에서 최저 부하 라우팅을 적용할 때의 제한조건 문제에 대해 연구하였다. 또한 결론적으로 QoS 제한조건을 가지는 효율적인 멀티캐스트 라우팅 알고리즘을 제안하였다.
멀티캐스트에서 실시간 응용을 지원하기 위해 지연시간을 제한조건으로 가지는 여러 가지의 휴리스틱한 알고리즘들이 제안되었다. 지연시간 제한조건 알고리즘은 단대단 지연시간에 대한 상위한계 값을 초과하지 않는 저비용의 트리를 휴리스틱한 방법으로 만든다. 그러나 몇몇 알고리즘은 네트워크의 링크가 대칭적이라고 가정함으로써 비대칭적인 경우 저비용의 트리를 형성하지 못하는 경우가 있다. 또한 지연시간을 만족시키는 저비용의 트리를 계산하는 시간이 과도하게 걸리는 문제점이 있었다. 계산 비용의 증가는 네트워크의 규모가 커짐에 따라 심하며 따라서 확장성을 가지는 제한조건 알고리즘이 필요하다. 제안된 알고리즘은 평균지연시간 방법과 목적지 노드들을 새로운 소스로 인식하는 효율적인 트리 구성 방법을 사용함으로써 빠른 계산시간을 가진다.
빠른 계산시간과 아울러 본 논문에서는 목적지간 지연시간 차이를 단대단 지연시간과 함께 QoS 요구조건으로 고려하였다. 각 응용들이 요구하는 QoS 중에 각 경로상의 지연시간 차의 최소 변화를 요구하는 상황을 생각할 수 있다. 예를 들어 회의를 할 경우 화자의 말이 참석자에게 동시에 들려지는 것이 중요하며, 분산 데이터 시스템에 있어서는 데이터 자료의 불일치 시간을 지연시간 편차를 줄임으로써 최소화 할 수 있다. 단대단 지연시간에 대한 QoS는 소스에서 멀티캐스트 그룹내의 목적지까지의 최대허용 가능한 지연시간을 의미하는데 비해, 목적지간 지연시간 변이는 소스에서 임의의 두 목적지까지의 단대단 지연시간 차이의 최대허용 범위에 대한 요구 조건이다.
응용들의 성격에 따라 사용자는 하나 혹은 여러 개의 조합으로 이루어진 QoS를 요구할 수 있다. 지연시간과 목적지간 지연시간 변이를 QoS 요구조건으로 가지는 멀티캐스트 트리를 형성하는 문제는 DVBMT ( Delay and delay variation multicast tree problem)이다. DVBMT를 해결하기 위해 효율적인 알고리즘인 DVDMR (Delay Variation Dependent Multicast Routing )을 제안하였다.
각 응용들이 요구하는 QoS 요구조건 외에 네트워크의 전체적 입장에서 보면 멀티캐스트 트리의 전체비용을 최소화하는 것이 중요하다. 또한 네트워크의 규모가 점점 커지고 실시간 응용들이 보다 더 많은 대역폭을 요구함에 따라 라우팅 알고리즘의 확장성이 필요하다.
DVDMR은 비대칭적인 링크 비용과 지연시간을 가지는 네트워크 환경을 고려하였으며 단대단 지연시간과 지연시간 변이를 제한 조건으로 가지는 저비용 멀티캐스트 트리를 빠른 시간 내에 만들 수 있는 효율적인 알고리즘이다. 기존의 다른 멀티캐스트 라우팅 알고리즘과의 비교 시뮬레이션 결과를 통해 제안된 알고리즘이 실시간 응용의 QoS를 만족시키며, 빠른 실행시간을 가지고, 대규모 네트워크 및 멀티캐스트 그룹에 대한 확장성이 있음을 알 수 있다.
