신뢰성 있는 망 연결을 위한 스테이너 문제에 관한 연구

최근 네트웍의 규모는 커지고 있으며 이에 따른 노드 수의 증가로 많은 트래픽과 고장에 따른 지연 등이 문제시되고 있다. 그러나 이러한 망연결을 위해 신뢰성 있는 경로를 찾는 스테이너 문제는 NP-완전 문제로 알려져 있기 때문에 P≠NP의 경우 신뢰성 있는 경로를 찾기 힘들다. 또한 기존의 K-SPH 알고리즘은 트래픽등으로 인한 지연 문제를 고려하지 않았기 때문에 링크 값이 변할 경우 올바른 경로를 찾아주기 힘들다. 따라서, 본 논문에서는 polynomial 시간 안에 수행될 수 있는 휴리스틱 알고리즘을 네트웍 특성에 따라 각각 소개하고 기존의 K-SPH 알고리즘의 단점을 해결하는 방법으로 각각의 노드에 라우팅 테이블과 네이버 테이블을 갖게 하여 링크 값의 변화시 거대한 트리를 만들어 줌으로써 네트웍 상황에 따라 신뢰성이 높아지는 멀티캐스팅 알고리즘을 제안한다. 제안된 알고리즘의 구현된 결과로 네트웍 지연에 다라 링크 값이 변화했을 때 기존의 K-SPH 알고리즘을 적용한 결과보다 더 낮은 값을 가진 경로를 찾아주는 결과가 나타나고, 지연으로 인한 라우팅 테이블 루핑을 막을 수 있었다.