There has been an increasing need of services with Quality of Service (QoS) guarantee on the real-time multimedia service. In multicast routing that will be the providing form of the multimedia service, the QoS guarantee is a principal issue together with the scalability and the reliability. In general, the existing core-based multicast routing protocols construct only the shortest paths between core and members in a multicast group without consideration of QoS. If there is little variation in QoS guarantee for different cores, a random core selection is sufficient. But the variation is substantial, more sophisticated methods to select a core are called for. Though various core selection algorithms have been proposed, there are few algorithms that take into consideration of multiple QoS constraints.
In this paper, we propose the QoS-based Core Selection Algorithm (QCSA) to guarantee the construction of QoS-based multicast tree for multimedia applications. As for the core selection in multicast routing, the proposed algorithm takes into consideration of multiple QoS constraints. The QoS constraints are defined as the minimum guaranteed bandwidth, the end-to-end delay, and the end-to-end delay jitter, respectively. Under rate-proportional service disciplines, it is shown that QoS-based routing is represented as polynomial among multiple QoS constraints.
The proposed algorithm computes QoS guaranteed paths between candidate core and members with QoS-based routing algorithm. When the QoS guaranteed path is computed, the core, which is able to guarantee QoS for all the members, is selected through the core selection process. We devise method to verify whether or not a member can join a multicast tree with adequate QoS, while not violating the existing QoS to the other on-tree members.
For the selection of the feasible core to guarantee QoS, first of all, the paths satisfying users' QoS requirements from each member to the other group members are computed. After computing QoS guaranteed paths to all other members, the maximum number of hops at each candidate core is chosen. Next, its criterion is made of this number and advertised to other members. On receiving other candidate core's criterion, the receiver's criterion is changed and forwarded to other members, in case that it is smaller than receiver's. As a consequence, each member knows the minimal maximum number of hops and sender's address, respectively. When broadcasting operations are completed, all members will have the same criterion. The member that advertises the minimal maximum number of hops is selected as the core of the multicast group. The core-based multicast tree rooted at this core is constructed to span all the group members.
When a new node wants to join this multicast group, QoS guaranteed paths from the core is computed. If the feasible path exists, this node is accepted as a member of this multicast group. When joins and leaves are occurred in frequent, the core reselection process is needed. If either of the following threshold values is exceeded, a new core should be decided based on the core selection process described previously. One threshold is the rejection rate of joins requests, and the other is the rate of the number of the changed members to the number of the total members.
Simulation results show the performance comparison of the proposed algorithm and the conventional algorithms, such as Maximum Centered Tree (MCT), Average Centered Tree (ACT), Initial Delay-Constrained Shared Tree (DCINITIAL), and Random Tree. According to the simulation results, the proposed algorithm improves the success rate of QoS guaranteed core selection and the inter-destination delay variation in comparison with the conventional algorithms along the number of multicast group members or the QoS constraints. The proposed algorithm outperforms the conventional algorithms in the success rate by about 10%, which denotes the frequency of QoS guaranteed core selection. Since the proposed scheme takes into consideration of QoS guarantee at the initial step, the success rate of core selection with satisfaction of QoS constraints to all members is higher than any other existing algorithms. It is also shown that the inter-destination delay variation, which is the important performance index in multicast routing, is improved in comparison with the conventional algorithms.
In this paper, we showed the QCSA's characteristics and performance under the multiple QoS constraints. The proposed algorithm outperforms the conventional algorithms in the sense of the core selection and the inter-destination delay variation, respectively.
Further study will include the improvement of the inter-domain scalability of the QCSA and reduction of the execution time on criterion exchange.
실시간 멀티미디어 서비스에서 Quality of Service(QoS) 보장의 필요성이 증가하고 있다. 멀티미디어 서비스 제공 형태의 대다수가 될 멀티캐스트 경로설정에서도 QoS 보장은 확장성, 신뢰성과 함께 매우 중요한 문제이다. 그러나, 기존 코어 기반 멀티캐스트 경로설정 프로토콜은 QoS를 고려하지 않고, 멀티캐스트 그룹 내의 코어와 멤버간의 최단 경로만을 계산하여 코어를 선택한다. 코어의 변화가 QoS 보장에 주는 영향이 거의 없다면, 임의의 코어 선택 방법만으로도 충분할 것이다. 그러나, 코어 선택이 QoS 보장에 주는 영향이 크기 때문에, 정교한 코어 선택 기법이 필요하다. 다양한 코어 선택 알고리즘이 제안되었지만, 다중 QoS 제약조건을 고려하는 알고리즘은 없었다.
본 논문에서는, 멀티미디어 서비스를 지원하기 위해서 QoS 기반 멀티캐스트 트리의 구성을 보장하는 QoS 기반 경로설정 알고리즘 (QCSA: QoS-based Core Selection Algorithm)을 제안한다. 제안 알고리즘은 멀티캐스트 경로설정에서 코어 선택시에 다중 QoS 제약조건을 고려한다. QoS 제약조건은 최소 보장 대역폭, 종단 지연, 종단 지연변이 등으로 정의한다. 속도 비례 서비스 규칙 하에서, QoS 기반 경로설정은 다중 QoS 제약조건간의 다항식으로 표현된다.
제안 알고리즘은 QoS 기반 경로설정 알고리즘으로 후보 코어에서 멀티캐스트 그룹 내의 모든 멤버까지 QoS를 보장해주는 경로를 계산한다. 요구된 다중 QoS 제약조건을 만족하는 경로들이 검색되면, 이 경로를 바탕으로 제안하는 코어 선택 과정을 거쳐서, 모든 그룹 멤버까지 QoS를 보장할 수 있는 코어를 선택한다. 기존 멀티캐스트 그룹 멤버의 QoS를 유지하면서 새로운 멤버에게도 QoS를 보장하는 경로를 검색하여, 새 멤버가 멀티캐스트 그룹에 참여할 수 있는 방법도 제안한다.
QoS를 보장하는 적합한 코어를 선택하기 위해서는, 먼저 각 멀티캐스트 그룹 멤버로부터 다른 멤버까지 사용자의 QoS 요구를 만족하는 경로를 계산한다. 모든 다른 멤버에 대한 QoS 보장 경로를 계산한 후에, 각 후보 코어에서의 최대 홉 수를 결정한다. 다음으로, 이 값을 기준값으로 정하고, 다른 멤버들에게 전송한다. 다른 후보 코어의 기준값을 수신하면, 자신의 기준값과 비교해서 수신한 값이 더 작은 경우에는, 이 값으로 기준값을 바꾸고, 다른 멤버들에게도 전송한다. 결국 각 멤버는 최소 최대 홉 수와, 이 값을 가진 후보 코어의 주소를 알게 된다. 이 과정이 완료되면, 모든 멤버는 같은 기준값을 가진다. 최소 최대 홉 수를 가진 멤버가 이 멀티캐스트 그룹의 코어로 결정되고. 이 코어로부터 모든 그룹 멤버에 걸쳐서 멀티캐스트 트리가 구성된다.
임의의 노드가 멀티캐스트 그룹 참여를 요청할 경우, 코어로부터 이 노드까지 가능한 QoS 보장 경로가 존재하는지 검색한다. 적합한 경로가 존재하면, 이 노드는 멀티캐스트 그룹 멤버로 받아들여진다. 이와 같은 멀티캐스트 그룹의 참여와 탈퇴가 빈번하게 되면, 코어의 재선택 과정이 필요하게 된다. 다음의 두가지 임계값이 초과되면, 새 코어를 선택하기 위해서 QoS 기반 코어 선택 과정을 기준으로 코어를 재선택 한다. 첫번째 임계값은 참여 요청의 거절 비율이고, 두번째 임계값은 총 멤버 수에 대한 변화된 멤버 수의 비이다.
모의 실험 결과는 제안한 QCSA와 Maximum Centered Tree (MCT), Average Centered Tree (ACT), Initial Delay-Constrained Shared Tree (Dcinitial), Random Tree (Random) 등의 기존 코어 선택 알고리즘의 성능을 각 항목별로 비교한다. 멀티캐스트 그룹 멤버 수와 QoS 제약조건을 인자로 한 모의 실험 결과는, 제안한 QoS 기반 코어 선택 알고리즘이 기존 코어 선택 알고리즘에 비해서 다중 QoS 제약조건 보장 코어 선택 성공률과 착신 노드간 지연변이에서 성능 개선 효과를 가짐을 보여준다. 제안 알고리즘이 QoS 기반 코어 선택의 정도를 나타내는 성공률에서 약 10% 정도 기존 알고리즘보다 우수함을 보인다. 이 결과는 제안 알고리즘이 코어 선택 과정의 초기부터 멀티캐스트 그룹 내의 모든 멤버에 대한 다중 QoS 제약조건을 고려하는 점이, QoS 기반 코어 선택에서 개선 효과를 나타낸 것이다. 멀티캐스트 경로설정에서 중요한 성능 지표인 착신 노드간 지연 변이에 있어서도, 제안 알고리즘이 기존 알고리즘에 비해서 성능이 개선되었다.
본 논문에서는 QoS 기반 코어 선택 알고리즘을 제안하고, 다중 QoS 제약조건에서의 제안 알고리즘의 특징과 성능에 대해서 기술했다. 제안 알고리즘은 코어 선택 성공률과 착신자간 지연변이에 있어서 기존 알고리즘보다 우수한 성능을 보였다.
향후에는 도메인간의 경로설정에 적용하기 위한 확장성의 개선과 알고리즘의 기준값 교환 부하를 줄이는 방안에 대해서 연구되어져야 한다.
