통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크 ...

통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크는 통신망에서 광범위하게 활용되고 있는 동기식 광전송망(SONET), 교통망, 전기회로 등을 표현하는데 흔히 사용되고 있다. 본 논문에서는 링 네트워크는 여러 개의 경로 네트워크(path network)으로 분할된다는 점에 착안하여 링 네트워크에서 망의 생존도를 구하는 다항시간해법을 개발하는 것이다.

Given an undirected network with a set of source-sink pairs, we are assumed to get a benefit if a pair of source and sink nodes are connected. The k-edge survivability of a network is defined as the total benefit secured after arbitrarily selected k e ...

Given an undirected network with a set of source-sink pairs, we are assumed to get a benefit if a pair of source and sink nodes are connected. The k-edge survivability of a network is defined as the total benefit secured after arbitrarily selected k edges are destroyed. The problem of computing k-edge survivability is known to be NP-hard and has applications of evaluating the survivability or vulnerability of a network. In this paper, we consider the k-edge survivability problem restricted to ring networks and develop an algorithm to solve it in polynomial time.

통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크 ...

통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크는 통신망에서 광범위하게 활용되고 있는 동기식 광전송망(SONET), 교통망, 전기회로 등을 표현하는데 흔히 사용되고 있다. 본 논문에서는 링 네트워크는 여러 개의 경로 네트워크(path network)으로 분할된다는 점에 착안하여 링 네트워크에서 망의 생존도를 구하는 다항시간해법을 개발하는 것이다.

(연구결과) 1) 문헌조사 및 관련 연구자의 최근 진행 연구에 대한 조사를 통해 최근까지 진행된 네트워크의 생존도 관련 연구에 대한 동향을 분석하였음. 네트워크의 구조가 특수한 경우 중, 링과 나무(tree)구조를 갖는 경우에 대한 유사연구를 비교 분석하였음.
2) 링 ...

(연구결과) 1) 문헌조사 및 관련 연구자의 최근 진행 연구에 대한 조사를 통해 최근까지 진행된 네트워크의 생존도 관련 연구에 대한 동향을 분석하였음. 네트워크의 구조가 특수한 경우 중, 링과 나무(tree)구조를 갖는 경우에 대한 유사연구를 비교 분석하였음.
2) 링 네트워크에서의 k-호 생존도를 구하는 문제 를 해결하기 위한 우리의 전략은 원문제를 여러 개의 부분문제로 나누어서 푸는 것이다. 부분문제는 경로 네트워크에서의 k-호 생존도를 구하는 문제가 된다. 본 연구에서는 부분문제를 Lagrangean 완화를 이용하여 다항시간에 해결하고, 최적의 Lagrangean 승수를 역시 다항시간에 찾는 방법을 개발하였다. 이를 이용하여 원래의 문제인 링 네트워크의 생존도 문제를 다항시간에 풀 수 있는 해법을 개발하였다.
(활용방안)
조합최적화 분야에서 생존도가 높은 네트워크의 설계와 네트워크의 생존도 또는 안정성의 분석은 중요한 연구과제로 꾸준히 연구되어 왔다. 이는 교통, 통신망 등이 대다수 국가의 중요한 기간시설이고 이러한 시설의 장애는 국가적으로 매우 심각한 사태를 발생시킬 수 있기 때문이다. 이러한 이유로 통신망의 생존도에 대한 연구는 수십년동안 경영과학 또는 OR분야 학술대회의 중요한 주제로 채택되어 왔다. 본 연구의 결과도 이러한 학회 중 하나인 세계OR학회(IFORS)에 발표할 예정이고, 학술지에 본 연구의 내용을 발표하여 정보통신산업계에서 통신망의 안정성을 평가하는 기술로 활용되도록 할 것이다.