k-링크생존도 산출을 위한 분지한계절차의 개발

Abstract

네트워크에 주어지는 서비스 요구에 기반을 둔 정량적 생존도 지표로서 k-링크생존도는 k개의 링크에 동시장애가 발생하는 경우에도 여전히 처리되어지는 서비스 요구의 비율로서 정의되며, 그 값을 정확히 계산하는 문제는 이미 NP-hard 클래스에 속하는 문제임이 밝혀져 있다. 본 연구예서는 k-링크생존도 산출을 위한 분지한계절차(branch and bound procedure)를 구현하였다. 기존의 k-링크생존도 산출을 위한 정수계획모형을 바탕으로 추가적인 유효부등식을 도입하고 선형계획 완화문제의 특성을 분석하여, 문제 단순화, 상한값 및 하한값 산출절차를 통합하였으며, 서울지역 전화망을 기반으로 하는 문제와 임의추출방식으로 만들어진 문제를 대상으로 이루어진 실험계산 결과를 제시하였다. 결과분석을 통하여 기개발되었던 선형계획 완화모형이나 유효부등식, 그리?? 상한값 및 하한값을 구하는 휴리스틱 절차의 효과를 분석한 수 있었으며, 적정한 규모까지의 네트워크에 대해서 분지한계절차를 통한 링크생존도 산출방법이 효과적으로 사용될 수 있음을 확인하였다.

The flow-based &-link survivability of a network is defined as the percentage of total traffic requirements surviving the worst case failures of k links and the problem of computing k-link survivability is known to be NP-hard. This paper implements a Branch and Bound procedure for the exact value of the k-link survivability. Based on the Integer Programming model for the network survivability, an additional valid inequality is introduced to reinforce the Linear Programming relaxation problem. A preprocessing process and upper/lower bounding procedures for the LP relaxation are integrated into a Branch and Bound procedure. Computational results for evaluating the performance of proposed procedures are also presented. The results show that the valid inequality and bounding procedures incorporated are so efficient and effective that they are applicable to large-size real world problems.

The flow-based &-link survivability of a network is defined as the percentage of total traffic requirements surviving the worst case failures of k links and the problem of computing k-link survivability is known to be NP-hard. This paper implements a Branch and Bound procedure for the exact value of the k-link survivability. Based on the Integer Programming model for the network survivability, an additional valid inequality is introduced to reinforce the Linear Programming relaxation problem. A preprocessing process and upper/lower bounding procedures for the LP relaxation are integrated into a Branch and Bound procedure. Computational results for evaluating the performance of proposed procedures are also presented. The results show that the valid inequality and bounding procedures incorporated are so efficient and effective that they are applicable to large-size real world problems.