The rapid development of high capacity transmission facilities such as fiber optic has rendered the structure of present-day communication networks much simpler than it used to be. Whereas the simplicity in network structure lessens the cost burden associated with network construction and maintenance, it in return makes networks more susceptible to severe network-service degradation under some component failures. On the other band, the performance standards imposed on the networks are getting stricter as the society itself becomes more dependent on the information provided via such networks. These technological and environmental changes, in turn, must call for the highly reliable and survivable network structure to be employed. Particularly, a two-level hierarchy with multiple homing of user nodes and general mesh-like structures are considered as most promising alternatives for present-day survivable networks.
In accordance with this line of advances, this thesis first analyzes the network survivability with focus placed on lick failures. To authorize the more quantitative analysis than possible with the conventional connectivity-oriented approach, the network link survivability is defined as the relative portion of traffic amount still intact under a set of link failures. We then exploit it's characteristics on the case of two-link failures to provide an efficient computation procedure. Based on a graph-theoretic result, the so-called cycle-factoring operation is devised, which reduces the network at hand into two simpler ones. We also develop a branch and bound procedure for two-link survivability of a general network, which successfully incorporates a sequence of cycle-factoring operations and some other computation-saving subprocedures.
Next we investigate the design methodologies for the networks on which a certain kind of survivability conditions are imposed. With a two-level hierarchical network with full-mesh interconnection of backbone nodes, we show that two kinds of survivability conditions, connectivity and link survivability conditions, could be transformed into the usual homing requirements of user nodes. A mathematical model is formulated as a mixed zero-one integer programming model and a modified dual-based solution procedure is developed. We also deal with a general network design problem on which the link survivability conditions are imposed. Given with the locations of nodes and the traffic requirements between them, a cost-minimizing set of links to be established are investigated. We will show that the link survivability conditions could be described with an exponential numbers of the well-known cut inequalities and make a comparison with the well-known connectivity models. Consequently the structural differences between two models are analyzed and a modified solution procedure is provided for the case of two-link survivability conditions.
최근의 통신망은 그 전송기술 및 운용의 면에서 매우 급격한 진전을 보여주고 있다. 광섬유와 같은 대용량 전송설비의 도입이 이루어지고 있으며, 지능화된 교환 및 전송기술이 개발되고 있다. 이러한 기술적인 발전은 컴퓨터 기술발전과 더불어 통신망의 구조 및 관련 서비스의 개념에 커다란 변화를 불러일으키고 있다. 특히 광섬유의 도입은 전송용량의 증대를 통하여 망의 구조적 단순화를 가능하게 해주고, 망요소의 지능화는 보다 다양하고 고도화된 서비스의 제공을 가능하게 해줌으로써, 사회전체의 통신에의 의존을 더욱 강화시키게 되는 것이다. 이러한 기술의 발전은 통신망의 구조 및 설계의 관점에서 두 가지의 필수적인 변화를 수반하게 된다. 즉, 구조의 단순화를 통한 통신망의 설치 및 운용면에서의 경제성이 제고되며, 통신망을 흐르는 서비스의 양 및 가치의 증가로 인한 서비스 제공의 연속성 등 품질수준의 강화가 보다 절실하게 요구되는 것이다. 이러한 두가지의 서로 상반되는 변화속에서 적정규모의 통신망을 효율적으로 설계·운용하기 위해서는 서비스의 연속성에 대한 새로운 성능지표의 개발과 이에 대한 분석 및 이를 토대로 한 망 설계기법에의 연구가 절실하게 필요하게 된다. 본 논문에서는 이러한 기술적·상황적 변화를 감안하여 망의 생존도 분석 및 이를 감안한 통신망의 설계에 관한 연구를 수행하였다.
먼저, 전송링크에 고장이 발생했을 때의 서비스제공능력을 보다 체계적으로 분석하기 위하여 "특정의 전송링크가 고장난 경우에도 여전히 제공 가능한 서비스의 상대적 비율"로서 망의 생존도를 정의하였다. 그리고 그래프 이론에서 전송링크고장으로 인한 망의 분할과 싸이클과의 관계를 토대로 Cycle-Factoring 절차를 고안하여 망 생존도에 대한 효율적인 계산절차를 제시하였다. Cycle-Factoring은 주어진 망을 보다 단순화된 두개의 하위망으로 줄여가는 절차이다. 또한 이러한 Cycle-factoring 절차를 도입함으로써 망의 생존도 계산에 분지한계법 (Branch & Bound method)이 사용될 수 있음을 밝혔으며, 폭넓은 계산실험을 통하여 제시된 생존도 계산방법이 매우 효율적임을 보였다.
둘째로, 이와 같은 망 생존도의 개념을 계층구조를 갖는 망의 설계문제에 적용하였다. 상위망의 완전그물구조와 하위망의 중복연결을 전제로 하여, 망 생존도에 대한 제약이 하위노드의 상위노드에로의 연결에 대한 조건으로 해석될 수 있음을 보였으며, 이러한 조건이 주어진 문제에 대한 수리적 모형을 제시하였다. 또한 문제의 특성을 효율적으로 이용하는 쌍대기반해법을 개발하였으며, 계산실험을 통하여 그 효율성을 검증하였다.
마지막으로 링크 생존도에 대한 제약이 있는 일반적인 망설계문제를 분석하였다. 기존의 connectivity제약을 이용한 망설계와 달리 링크 생존도에 대한 제약을 이용하는 경우, 보다 효율적인 망설계 결과를 얻을 수 있음을 보였으며, 이러한 망 생존도 제약이 추가된 문제를 수리적으로 모형화하였다. 또한 이 문제는 Minimum Spanning Tree 문제, Steiner Tree 문제, k-connected Network Design 문제 등 널리 알려진 여러 문제들을 일반화하고 있음을 보였다. 그리고 망 생존도에 제약이 주어지는 경우, 외형적으로는 기존의 connectivity를 이용한 모형과 동일한 형태로 표현되지만, 외형적인 동일성에도 불구하고 내부적인 조건식 사이의 관계에서 두 모형사이에 본질적인 차이가 있음을 발견하였다. 이와 같은 차이에 대한 분석을 토대로 링크 생존도에 제약이 있는 문제의 경우에는, 2장에서 개발된 Cycle-Factoring 방법이 중간단계의 해법으로 유용하게 사용될 수 있음을 보였다. 이와 같이 본 논문은, 망의 생존도에 관한 계산절차 및 생존도에 대한 제약을 반영한 계층적, 일반적 망에 대한 설계기법 등에 관한 결과를 제시하고 있지만, 그 활용의 면에서 몇가지 보완적인 연구를 필요로 한다. 특히 노드설비의 고장에 대한 망 생존도의 연구 및 본 논문에서 제시된 일반적인 망설계문제에 대한 체계적인 해법의 연구는 현실적인 문제해결의 폭을 넓힐 수 있는 중요한 연구과제라 하겠다.
