Most of present large-scale communication networks adopt a two level hierarchical network whose structure consists of a backbone network in the upper level and a family of local access network in the lower level. This hierarchical structure offers extensive integration and sharing of functions to reduce the overall network costs and to operate the network with flexibility. The topological design is one of the most important problems that arise in connection with the design of two-level hierarchical networks.
The objective of this study is to provide some mathematical formulations and efficient solution methods for the topological design problem of a special type of two-level hierarchical network. Unlike the conventional approaches of partitioning the global design problem into the design of backbone network and the design of local access networks, we adopt the unified approach, which the whole design problem is directly dealt with in such a general setting that both a backbone network and local access networks attached to it are to be simultaneously determined.
First, we examine the dual based algorithms for the network design related problem We provide a broad overview of major algorithms by briefly describing different types of the dual based algorithms that have been studied and then indicate which characteristics of the exploited special structure of the problems make possible to apply the dual ascent algorithm.
Secondly, we focus on the design of a network with a two-level "tree-star" hierarchical structure (THNTS) where the upper-level backbone network is tree-shaped, and the lower-level local access networks are of star type. As a means to widen the real-world applicability over the existing network design studies, a backbone node not opened is allowed to be used as a transhipment node bridging the established backbone links. The problem is modelled as a mixed 0-1 linear program, whose special structure is exploited for the development of an efficient dual-based lower bounding procedure. The procedure is incorporated in the branch and bound solution method, whose effectiveness is well demonstrated by the computaional experiments conducted with a variety of problems ranging up to 50 backbone nodes and 200 user nodes.
Finally, as an extension of the THNTS design problem, the two-connected two-level hierarchical network (TTHN) design problem is considered. The upper level network in the TTHN design problem has two-connected structure which ensures that every open backbone node has at least two edge disjoint paths to the root node. TTHN design problem is formulated as a mixed 0-1 integer programming model. Also peculiar properties of the TTHN design problem are in-vesigated and then a modified dual-based solution method which exploits the special structure is developed. Through the computaional experiments, the performance of the solution procedure is tested.
컴퓨터 기술과 통신기술의 급속한 발전, 그리고 다양한 통신 서비스에 대한 사회적 욕구는 대규모 통신망의 출현을 가져오게 되었으며 이와 관련하여 통신망 설계는 매우 중요한 문제로 인식되어 왔다. 이러한 현실적 요구에 부응하여 본 연구에서는 통신망의 설계에 효과적으로 활용할 수 있는 수리계획모형과 해법의 개발을 주요 목표로 하고 있다.
대부분의 대규모 통신망들은 망의 설치 및 운용상의 기능적인 이유와 경제적인 이유로 인해서 하나의 기간망과 주변의 근거리 접속망으로 구성되는 계층적 구조를 갖고 있다. 이런 사실을 감안하여 CATV망, 전화망, MAN, 그리고 사설망 등의 설계에 매우 효율적으로 이용될 수 있는 '나무-성형' 계층구조를 갖는 중앙집중형 2계위 통신망의 설계에 연구의 촛점을 맞추었다. 더구나 본 연구에서는 기간망의 설계와 근거리 접속망의 설계를 분리하여 해결하는 기존의 접근방법과는 달리 이 두 가지 문제를 하나의 틀 안에서 해결하는 접근 방법을 사용하였다. 본 연구에서 고려한 내용은 다음과 같이 요약될 수 있다.
첫째, 입지선정 문제, Steiner tree 문제, 그리고 무한 용량을 갖는 망 설계문제 등과 같이 통신망 설계에 자주 활용되어 지는 주요 문제들의 쌍대기반해법에 대해 조사연구를 하였다. 이 조사에서 쌍대기반해법이 적용된 주요문제들의 쌍대구조를 분석하여 각 문제가 공통적으로 같고 있는 특성을 찾아냄으로써 쌍대기반해법의 적용이 가능한 문제의 구조를 규명하는데 노력하였다.
둘째, 기간마디들(backbone nodes)로 구성되는 기간망이 나무(tree) 형이고 각 수요중심마디(user node)가 하나의 기간마디에 연결되는 형태의 통신망, 즉 "나무-성(tree-star)" 형의 2계위 망을 설계하는 문제(THNTS)를 고찰하였다. 이 문제는 먼저 기간마디들의 후보 중에서 각 수요중심마디에 서비스를 제공하는 기간마디들을 선택한 후, 이 선택된 기간마디들을 주어진 기간망의 중심마디에 연결하기 위한 가지들(arcs)을 고르는 문제로 정형화하였다. 또한 이 문제는 세 종류의 비용 - 수요중심마디를 선택된 기간 마디에 접속시키는 비용, 기간마디의 설치비용, 그리고 선택된 기간마디들을 중심마디에 연결시키기 위한 가지들의 비용 - 들의 합을 최소화하는 것을 목적함수로 하는 혼합 0-1 정수계획모형으로 정식화되었다. 특히 이 모형이 갖고 있는 특징은 선택되지 않은 기간마디들도 선택된 기간마디들을 중심마디에 연결시키기 위해 비용이 추가적으로 발생됨 없이 사용될 수 있게 함으로써 현실성을 강조하였다. 아울러 이 모형의 쌍대구조는 Erlenkotter가 제시한 입지선정모형과 Wong이 제시한 Steiner tree 모형들의 쌍대구조가 내재되어 있는 특수한 형태를 갖고 있는 데, 이 쌍대구조의 특수성을 최대한도로 이용하는 쌍대기반해법을 개발하였다. 개발된 해법이 성공적이란 사실은 다양한 예제에 대한 실제 계산실험을 통하여 충분히 입증되었다.
마지막으로 THNTS 문제의 확장문제로서 기간망이 이중구조를 갖는 중앙집중형 통신망의 설계문제(TTHN)를 다루었다. 이 문제는 선택된 각 기간마디에서 중심마디까지의 연결되는 경로가 최소한 2개 이상이 되도록 기간망을 설계하는 문제로 기간망의 가지를 광 전선(fiber optic cable)으로 설치할 때 유용하게 활용될 수 있는 모형이다. THNTS 문제에서와 유사하게 이 문제도 또한 혼합 0-1 정수계획모형으로 모형화되었다. 또한 두 모형 사이의 유사성을 활용함에 의해 이 문제를 풀기 위한 수정된 쌍대기반 해법이 개발하였으며, 이의 효율성도 실제 계산실험을 통해 입증하였다.
