Survivability has become the focal point in network planning for optical fiber tele-communications networks. In designing survivable networks, the standard SONET(Synchronous Optical Network) technology has recently adapted to make rings(particularly SHR(self healing ring)) more preferred architectures. Thus, this thesis is interested in the issue of designing an optical network in self-healing ring structure.
Specifically, this thesis considers a problem to find a set of unidirectional self-heal rings(USHRs) which cover all COs and satisfy all demands at minimum cost, given one hub node, central offices(COs) and conduits.
The problem is expressed in an integer programming model, and found that it is NP-Complete. For the problem, a greedy-type heuristic algorithm is derived. The algorithm begins with no initial ring, and increases the number of rings one by one. The algorithm efficiency is evaluated with various numerical examples. Near-optimal solutions are found for small size problem.
광 통신망은 대용량 전송, 높은 신뢰성, 장거리 전송 등의 특성을 가지고 있다. 하지만 대용량 전송으로 인해 어떤 링크나 노드의 장애 발생시 매우 많은 트래픽이 손실되게 되므로 이러한 망의 장애 발생에 대비하여 생존도를 고려한 망을 구축하게 된다. 그러한 망을 구성하는 방법 중에 ADM이용한 Self-Healing Ring(SHR)이 있다. 본 논문에서는 모든 COs에 서비스를 하고, 각 CO에서 발생하는 수요를 모두 처리할 수 있는 design을 구현하는 문제를 다루고 있다. 이 문제는 NP-complete이므로, Dijkstra algorithm을 이용한 greedy-type heuristic algorithm을 제시하였다. 또한 실제 데이터를 대상으로 한 실험을 통하여 작은 size의 문제에 대하여는 reasonable time내에 optimal에 가까운 값이 결과로 나온다는 것을 보였고 큰 size의 문제에 대하여서도 빠른 시간 안에 값이 나올 수 있음을 보였다.
