Among multicast routing methods, a Protocol Independent Multicast - Sparse Mode (PIM-SM), especially used in IPTV services, is based on core-based tree protocol. The core node of PIM-SM is called Rendezvous Point (RP). The PIM-SM can reduce resource usage such as bandwidth rather than the source-based tree protocol. The group members can join/leave with a multicast group by only sending JOIN/PRUNE messages to a RP. So, this property can help to be scalable easily. These benefits are known as considerable gain in the real networks.
In the PIM-SM, the RP is very important node, because it handles all of traffic from sources and manages members' join or leave. A centrality measurements is used to judge a important node. According to cretation of importance, there are various methods in centrality measurements like as degree, closeness, betweenness, and eigenvector. To reduce delay of traffic transmission, in this paper, the closeness centrality which minimizes average distance between other nodes is more proper to proposed schemes. This centrality can consider states of networks; and it help to arrive traffic fast to receivers.
Also, the optimalized location of RP should be changed according to traffic states of networks. Because of a characteristic of PIM-SM, sources should send data to receivers first. In this time, it can use the unicast protocol. After that, the RP replicates data and transmits it to receivers in that multicast group. Like this, because all of traffic is centralized to the RP, it causes congestion at the RP. Therefore, users suffer delay and can't have guaranteed QoS. Also, the PIM-SM doesn't reflect states of networks so that it doesn't place at an appropriate location. In the networks, links flowing traffic changes continuasely as changes of sources and receivers; and there are effectiveness of unwanted traffic flowing through paths except traffic from sources. Therefore, the RP should reflect traffic states of networks to distribute traffic evenly in the networks and to prevent congestion by locating the RP to where has less traffic utilization. Selecting of RP at the appropriate place is a very important technique. Also, the static RP mechanism does not guarantee QoS because of delay of not reflecting states of sources and receivers changing continuously and delay of congestion. It needs to relocate the RP to an appropriate place according to situations.
To solve these problems, in this paper, we proposed two schemes to select an appropriate RP. Because the RP should have capacity which is able to store and handle all of data such as contents and multicast information, proposed schemes calculate with only nodes which has enough capacity measuring memory of nodes at first. This consideration helps to calculate only nodes which are satisfied basic standards when it is applied to real networks. These two schemes are called ordered RP relocation scheme and hybrid RP relocation scheme. These schemes choose a new RP when the conventional RP is at the unappropriate place. The procedures of schemes are as follows.
1. Ordered RP Relocation Scheme : At first, this scheme selects new candidate RPs which nodes have shortest paths between sources and receivers through the RP in the multicast group. This method is that it enrolls nodes which have paths longer or shorter as $\varepsilon$ of path through original RP than path lengths of original RP to candidates. After that, with candidate RPs, it measures traffic between sources and receivers in the networks. It assigns a node which has low network utilization to new RP to prevent congestion and distribute traffic evenly.
2. Hybrid RP Relocation Scheme : It measures cost of each node with a cost function combined with a closeness centrality and available bandwidth. It selects a new RP with node which has lowest cost which can get with the proposed cost function. With this cost function, it can choose the new appropriate RP controlling a importance of each factor as the closeness centrality or the bandwidth. In this cost functions, it has a weight factor, so it can control the weight factor flexibly according to states of networks .
These schemes can locate the RP to the optimized place. The dynamic RP relocation scheme guarantees better performance in terms of delay than the static RP. Also, with proposed RP relocation schemes, it induces traffic to where the utilization is less, so that it can help to distribute traffic to the whole networks. It prevents congestion at the around of RP and distributes traffic effectively via a RP relocation. Also, due to the distance between sources and receivers is shorter, it reduces delay and provides improved QoS to users. Therefore, our RP relocation schemes archive the performance enhancement in terms of delay and utilization.
멀티캐스트 방식 중에서, 특히 IPTV 서비스 분야에서 가장 많이 쓰이고 있는 PIMSM은 중심 기반의 트리 프로토콜을 기본으로 하고 있으며 중심 노드는 Rendezvous Point (RP)로 불리운다. 이는 소스 기반의 트리 프로토콜에 비해 대역폭 등 자원 사용을 줄일 수 있고, 그룹 멤버들이 단순히 JOIN/PRUNE 메시지를 중심 노드에게 보냄으로써 멀티캐스트 그룹에 가입/탈퇴할 수 있다. 이러한 장점은 실제 네트워크 상에서 상당한 이득으로 꼽히고 있기에 널리 이용된다.
수진측에서 오는 모든 트래픽을 다루는 RP는 PIM-SM에서 가장 중요한 노드이다. 중요한 노드를 판단하는 데에는 노드의 중요도를 측정할 수 있는 Centrality가 이용된다. 중요도의 기준에 따라서 Degree, Closeness, Betweenness, Eigenvector 등 여러 가지 방법이 있다. 기본적으로 트래픽 전송에 대한 지연을 줄이기 위해서는 다른 노드들과의 평균 거리를 최소화 시켜주는 노드를 중요함의 기준으로 삼는 Closeness Centrality가 제안한 알고리즘에 더 적합하다. 이를 통해 네트워크의 상황을 고려하되, 트래픽이 빠르게 수신자에게 도착할 수 있도록 도와줄 수 있다.
또한 네트워크의 트래픽 상황에 따라서도 최적화된 RP의 위치는 달라질 수 있다. PIM-SM의 동작 특성상 송신자는 보내려는 정보를 RP로 먼저 보내주어야 한다. 이 때에는 Unicast 방식을 사용하여도 무방하다. 이후 RP에서는 정보를 복사하여 멀티캐스트 그룹에 속해있는 수신자들에게 보내어 진행한다. 이처럼 모든 트래픽이 RP로 몰리게 되어 RP 에서는 혼잡이 일어나게 되고, 이로 인해 사용자들은 QoS를 보장받지 못하고 지연을 겪게 된다. 또한 네트워크의 상황을 반영하지 못하기 때문에 항상 적절한 위치에 자리잡고 있다고 보기 어렵다. 송신자와 수신자가 지속적으로 변하여 트래픽이 흐르는 구간이 매번 바뀌고, 송신자에 의해 보내지는 트래픽 이외에 네트워크를 흐르고 있는 원하지 않는 트래픽으로 인한 영향이 있을 수 있다. 따라서 최대한 네트워크의 트래픽 상황을 반영하여 대역폭 사용도가 적은 곳으로 RP를 위치시켜주어 트래픽이 골고루 분배되고 혼잡을 미리 방지할 수 있어야 한다.
이처럼 최적화된 위치로 RP를 지정해주는 것은 상당히 중요한 기술이다. 또한 고정된 RP를 사용하게 되면 혼잡으로 인한 지연과 지속적으로 변하는 송신자와 수신자의 상태의 미반영으로 인한 지연이 발생하게 되어 QoS를 보장해줄 수 없다. 때문에 상황에 맞게 적절한 위치로 RP를 재위치 시켜주는 기술 또한 필요하다.
이 논문에서는 적절한 위치로 RP를 지정해주는 알고리즘을 두가지로 제안하였다. RP는 트래픽과 멀티캐스트 정보를 모두 저장하고 다룰 수 있는 용량을 가지고 있어야 하기때문에, 두 가지 알고리즘 모두 처음에 노드들의 메모리를 계산하여 충분한 양을 가지고 있는 노드로만 계산한다. 이는 실제 네트워크에 적용할 때에 기본적인 기준을 만족시킨 노드에 대해서 계산할 수 있게 도와준다.
1. Ordered RP Relocation Scheme: 우선 Closeness Centrality를 이용하여 멀티캐스트 그룹에서 RP를 거쳐가는 송신자와 수신자 사이의 경로 중 가까운 경로를 가지고 있는 노드를 새로운 RP의 후보에 올린다. 기존의 RP의 경로 길이와 비교하여 그 길이의 $\varepsilon$ 만큼 짧거나 긴 경로를 가진 RP를 후보로 등록한다. 이후, 후보로 등록된 RP를 대상으로 송신자와 수신자 사이에 흐르는 네트워크 내의 트래픽을 측정한다. 트래픽이 적은, 즉, 네트워크 사용도가 적은 노드를 새로운 RP로 지정하여 혼잡을 방지하고 트래픽이 골고루 분배될 수 있도록 한다.
2. Hybrid RP Relocation Scheme : Closeness Centrality와 트래픽 측정을 함께 하여 하나의 Cost function으로 각 노드에 해당하는 Cost를 측정한다. 적은 Cost를 가진 노드를 새로운 RP로 지정한다. Cost factor를 이용하여 상황에 따라 closeness centrality와 트래픽 측정에 대해 각각에 대한 중요도를 조절하여 상황에 따라 적절한 새로운 RP를 지정할 수 있다. 이 Cost function에서는 가중치 인수를 두어 네트워크 상황에 맞게, 또는 가중치를 두기 원하는 요소를 조절할 수 있다.
이러한 알고리즘은 RP를 최적화된 장소로 지정해 줄 수 있다. 알고리즘을 통해 선택되는 최적화 된 장소는 사용도가 적은 쪽으로 트래픽을 유도할 수 있어 네트워크 전체에 트래픽이 골고루 분산될 수 있도록 도와준다. 이는 RP 재지정을 통해 RP 주변에서 혼잡이 일어나는 것을 막아줌과 동시에 트래픽을 효과적으로 분배시킬 수 있도록 한다. 또한 송신자와 수신자와의 거리가 가깝기 때문에 지연을 줄여 사용자들에게 향상된 QoS를 제공할 수 있다.
