In this thesis, we propose optimization models and algorithms for the design of telecommunication networks with ring topology.
First, we consider the problem of designing a local network in a two-level telecommunication network. Given a cluster with one or two hubs, central offices (COs) and conduits which connect them, the problem is to find a set of unidirectional path switched rings (UPSRs) which covers all COs and hubs, and satisfies all the traffic demands at minimum cost. We decomposed the problem into master problem and subproblem and presented integer programming models of them. Since master problem formulation has exponentially many columns, we applied the column generation technique to solve the LP relaxation. Then we used a branch-and-bound algorithm to obtain an integer solution. For the optimization of subproblem that generates profitable columns of the master problem formulation, a class of strong valid inequalities was derived and a branch-and-cut algorithm was applied. Computational results on problem instances of practical size show that our algorithm yields optimal or near optimal solutions to the problem in a short time.
Second, we consider the traffic grooming problem for the design of SONET/ WDM (Synchronous Optical NETwork/Wavelength Division Multiplexing) ring networks, which is also referred to as the stacked ring design problem. Given a physical network with ring topology and a set of traffic demands between pairs of nodes, we are to obtain a stack of rings with the objective of minimizing the number of ADMs installed at the nodes. This problem arises when a single ring capacity is not large enough to accommodate all the given demands. We consider all types of SONET ring architectures: UPSR, two-fiber bidirectional line switched ring (BLSR/2), and BLSR/4. As a solution method, an efficient algorithm based on the branch-and-price approach has been reported in the literature for the problem in which only UPSR was considered. In this study, we suggest integer programming models and the algorithms based on the same approach as the previous one, considering BLSR/2 and BLSR/4 additionally. Computational results show that our algorithms can solve problem instances of practical size to optimality within a reasonable time. Using the results, we compare the number of required ADMs for all types of the ring architecture.
Third, we consider a routing and wavelength assignment (RWA) problem on WDM ring networks without wavelength conversion. Given a physical network with ring topology, required connections between pairs of nodes and a set of available wavelengths, the problem is to maximize the number of established connections. We propose new mathematical formulations of the problem and efficient algorithms based on the branch-and-price approach. Computational experiments on randomly generated data show that the algorithms yield optimal solutions in much shorter time on average than the one which has been known to give the best performance so far.
본 논문에서는 국간 환형 통신망 설계를 위한 최적화 모형과 정수계획법에 기반한 해법을 제시한다.
첫째, 이계위 망 구조의 하부 구조에 해당하는 지역망 설계 문제를 다룬다. 지역망의 물리망은 하나 또는 두 개의 허브 또는 일반 교환국들에 해당하는 마디들과 이들을 연결하는 관로로 이루어진다. 본 문제는 주어진 관로도 상에서 수요를 만족하면서 모든 허브들과 교환국들을 연결할 수 있는 최소 비용의 단방향 자가복구링의 집합을 구하기 위한 것이다. 링의 용량은 세 가지를 고려하며, 링들간의 통신은 허브를 통해 이루어지므로 각 링은 허브를 반드시 포함하도록 설계하였다. 문제의 복잡도를 고려하여 이 문제를 주문제와 부문제로 나누어 모형화하고 열 생성 기법과 분지한계법을 이용한 해법을 제시하였다. 주문제의 열을 생성하는 부문제를 해결하기 위해 강력한 절단평면을 이용한 분지절단법을 적용하였다. 실제 크기의 데이터에 대해 본 연구의 알고리즘을 실험한 결과 빠른 시간 내에 최적해 또는 근사 최적해를 구할 수 있었다.
둘째, SONET/WDM 계층망에서 발생하는 트래픽 그루밍 문제를 다룬다. SONET/WDM 망은 WDM 기술을 이용하여 하나 또는 두 개의 광섬유 쌍에 저렴한 비용으로 여러 개의 SONET 자가복구링을 구현하기 위한 구조로서, 하나의 링에는 하나의 파장이 할당되기 때문에 가용한 파장의 개수만큼 링을 구현할 수 있다. 각 마디에는 광분기결합 다중화기가 놓인다. 특정 마디에 도착하는 특정 파장 채널이 그 마디에서 수신되는 트래픽을 포함하지 않는다면 광분기결합 다중화기는 그 파장을 통과시킬 수 있으며 결과적으로 그 마디에서 해당 파장에 대한 SONET 분기결합 다중화기를 고려하지 않아도 된다.
본 연구는 환형 물리망과 마디 쌍 사이들에 대한 수요, 가용한 파장의 개수가 주어졌을 때, 모든 수요를 만족시킬 수 있는 중첩 구조의 링집합을 구하기 위한 것이다. 본 연구의 목적은 트래픽 그루밍을 통해 마디들에 설치되는 SONET 분기결합 다중화기의 개수를 최소화하는 것이다. 이 문제를 해결하기 위한 해법으로, 단방향 자가복구링을 고려하는 분지평가법에 기반한 해법이 보고되었지만, 양방향 링에 대해서는 단순 분지한계법을 제외하고는 아직 보고되지 않고 있다. 본 연구에서는 2섬유/4섬유 양방향 자가복구링을 대상으로 기존의 최적화 해법을 응용한 해법을 제시하고 있다. 실제 크기의 데이터에 대해 본 연구의 알고리즘을 적용한 결과 적절한 시간 내에 최적해를 구할 수 있었다. 실험 결과를 바탕으로 링 유형에 따른 분기결합 다중화기의 개수를 비교한 결과 단방향 링을 적용했을 때보다 2섬유 양방향 링은 최대 10%, 4섬유 양방향 링은 50%까지 그 개수가 줄어들었다. 또한 모든 수요를 만족시키기 위한 최소의 파장의 개수도 단방향 링, 2섬유 양방향 링 , 4섬유 양방향 링의 순으로 크다는 것을 확인하였다. 이것은 가용한 파장의 개수에 따라서 2섬유 또는 4섬유 양방향 링으로만 망의 구성이 가능할 수도 있다는 것을 의미한다.
셋째, WDM 기반의 전광통신망에서 발생하는 경로 설정 및 파장 할당 문제를 고려한다. 환형 물리망과 마디 쌍별로 주어진 연결요구량, 가용한 파장의 개수를 입력으로, 설정 가능한 연결의 개수를 최대화하는 문제 (RWA1)를 다룬다. 각 연결은 하나의 광경로를 통해서 설정되며, 하나의 광섬유를 지나는 광경로가 두 개 이상인 경우 각 경로에는 서로 다른 파장이 할당되어야 한다. 본 연구에서는 이 문제의 최적해를 제공하는 두 가지의 새로운 최적화 문제 (RWA1-1), (RWA1-2)와 수리 모형을 제시하였다. 그리고 언급한 세 문제를 해결하기 위해 분지평가법에 기반한 해법을 제시하였다.(RWA1)의 선형완화 문제가 제공하는 최적값의 상한은 최적값과 거의 일치하기 때문에 본 연구에서는 최적값에 가까운 하한을 구하는 데 주안점을 두었다. 각 모형의 성능을 비교하기 위해 탐색나무의 시작 마디에서 분지한계법을 적용하여 최적값의 하한을 구하였다. 실험 결과, (RWA1-1), (RWA1-2)의 알고리즘이 제공한 최적값의 하한이 (RWA1)의 알고리즘이 제공한 하한과 같거나, 그 보다 더 크다는 것을 확인하였다. 결과적으로 모든 실험 문제에 대해 (RWA1-2)의 알고리즘을 이용하여 시작마디에서 (RWA1)의 최적해를 구할 수 있음을 보였다.
본 연구의 모형화 기법은 전광통신망 설계뿐 아니라 다양한 분야의 응용문제에 적용이 가능하기 때문에 활용도가 높고 앞으로도 많은 관련 연구가 이루어 질 것이라 기대된다.
