The concept for communication network design has been drastically altered from the conventional one by the changing environment ignited by the advent of the optical transmission system. Owing to the possibility of severe service loss in the event of a single fiber link failure, the network survivability becomes one of the most important issues in planning and designing a fiber-optic network. Focusing on the up-to-date technology of synchronous transmission, various design issues are reviewed in building such fibre optic transmission networks which are not only cost-effective but also immune to catastrophic link failures.
First, we consider a modified ring architecture, so called USHR with Diverse Protection (USHR/DP), which is concerned with constructing a SHR in a cost-effective manner in a region covered by a single hub facility and a number of central offices. The regional network is assumed to have the two-level structure: the upper level of the SHR and the lower level of the point-to-point diverse protections. We suggests a mixed 0-1 integer program for USHR/DP, proposes some heuristics for constructing an initial feasible solution and for improving a given feasible solution, and provides computational results of our heuristics for several randomly generated test problems.
Second, we considers the ring loading problem which arises in the design of SONET bidirectional rings. We have developed an efficient algorithm which optimally solves the ring loading problem. This problem can be modelled as a linear programming (LP) problem, and can be solved by any commercially available LP code. The ring loading problem, however, is only a subproblem within the comprehensive planning tool, which has to be solved in excess of several thousand times in practical applications. Therefore, we suggest an optimal algorithm, far superior to any LP solution method, cannot be overvalued when designing a real-world large-scale SONET broadband network. For the problem without demand splitting, an integer problem of the ring loading problem, we presents an approximation algorithm which produces a solution whose objective value is within twice the optimal value of its linear programming relaxation. Our algorithm is simple but produces a feasible solution with the stronger worst-case bound than any other heuristic previously developed. Moreover, when deriving a feasible solution, we can also obtain a lower bound of the problem which is useful to estimate the quality of the obtained feasible solution.
The survivable mesh network architecture using DCSs is a crucial part of an integrated network restoration system, which is primarily applied to areas where high demand and connectivity involved. Unlike Automatic Protection Switching (APS) systems and self-healing rings, the DCS mesh network restores services via spare capacity which is reserved for protection. There are some different models to install working and spare channel which are affected by the protection switching schemes to restore traffic requirement under link or node failures. Demand restoration using DCS can be considered at two different levels: line restoration and path restoration. For line restoration, we shows that the separation problem of spare channel assignment problem is a special case of the minimum cut problem. For path restoration, we suggest a sequential algorithm to solve working and spare channel assignment problem.
대용량ㆍ고속 전송을 특징으로 하는 광통신망이 광범위하게 구축됨에 따라 통신망의 생존도는 매우 중요한 요소가 되고 있다. 즉 광케이블이나 광전송 장비에 장애가 일어나게 되면, 대규모의 통신장애를 초래하므로 이는 개인이나 기업뿐만 아니라 국가적으로 매우 심각한 사태를 발생시킬 수 있다. 이러한 문제점을 고려하여 동기식 광전성망(SONET 또는 SDH) 기술이 제안되고 있다. SONET은 광전송에 필요한 신호형식 및 이의 전송과 관련된 표준을 규정해 놓은 것으로 SONET을 이용한 광통신망은 광선송 장비의 장애시에 이를 자동적으로 감지하여 단시간 내에 복구가 가능하다. 이는 동기식 광전송장비인 TM, ADM 및 DCS를 이용하므로서 자동적인 망의 복구가 가능하게 되는데, 이러한 망장비들은 특성에 따라 TM을 이용한 단대단 복구 방식, ADM을 이용한 링구조, DCS를 이용한 메쉬(mesh) 구조가 대표적인 망구조로 제안되고 있다. 생존도가 보장되는 광통신망의 구축은 이들 망구조가 다양하게 결합되는 복잡한 형태가 되는데, 전체적인 망의 효율적인 구축을 위해서는 여러 가지 요소들을 복합적으로 고려하여야 한다. 본 논문에서는 생존도를 보장하는 동기식 광전송망의 구축에 필요한 여러 가지 문제들을 해결하는 데 역점을 두었다.
먼저, ADM을 이용한 자가복구가 가능한 링 (SHR)을 구축하려고 할 때, 모든 지역을 관장하는 SHR을 설치하는데는 많은 비용이 발생하게 된다. 이러한 단점을 해결하기 위해 본 논문에서는 SHR과 단대단 복구 방식된 구조를 제안하고, 이 구조가 SHR로 전체지역을 관장하는 것과 동일한 생존도를 보장하면서 비용측면에서 유리함을 보였다. SHR과 단대단 복구방식을 결합한 망의 구축은 매우 복잡한 수리문제가 되는데, 본 논문에서는 특히 단방향의 SHR(USHR)을 이용한 망 구조인 USHR/DP를 제시하였다. 그리고 이를 효과적으로 해결할 수 있는 해법을 제안하고, 이 해법이 실제 문제의 해결하는데 매우 효과적임을 보였다.
둘째, SHR은 앞에서 언급한 USHR 이외에 양방향으로 운용이 가능한 SHR (BSHR)이 있다. USHR은 주어진 노드의 트래픽 수요의 합에 의해 그 용량이 결정되어지는데 반하여, BSHR의 경우는 노드간 트래픽 수요의 처리가 두 가지 방향 중 한 방향을 선택하여 결정되므로 USHR과는 다르게 용량이 결정되어 진다. 즉 BSHR의 용량은 주어진 트래픽 수요를 두 개의 방향중 한 방향으로 처리한다고 할 때, BSHR에 부과되는 링크 중 최대의 트래픽 수요를 가지는 링크의 부하를 처리할 수 있어야 한다. 본 논문에서는 이러한 BSHR의 용량을 최소화할 수 있는 문제가 NP-complete임을 보이고, 이의 선형완화된 문제에 대한 새로운 해법을 제시하였다. 선형완화된 문제의 특별한 구조를 이용하여 이를 현재까지 제시된 어떤 해법보다도 효율적으로 해결할 수 있는 해법을 제시하고, 이 해법이 선형완화된 문제의 최적해를 보장함을 보였다. 그리고 이 해법을 원래 BSHR의 용량결정문제를 해결하는데 적용할 수 있도록 변형하였고, 변형된 해법이 이론적으로도 기존의 연구보다 우수할 뿐만 아니라 계산결과에 있어서도 좋은 결과를 보장함을 보였다.
마지막으로, DCS를 이용한 메쉬망은 라인방식과 경로방식에 의한 자동복구의 두 가지 방식이 있다. 라인방식의 경우는 기존에 제안된 해법들이 많은 계산시간을 필요로 하는 단점을 안고 있는데, 이는 방대한 제약식을 가진 문제를 column generation method로 해결하려고 할 때, 이의 중간 결과가 실제문제의 실행가능해 인지를 알아보는데 많은 시간을 소요하는데 기인한다. 따라서 본 논문에서는 이를 개선할 수 있는 이론적 결과를 제시하여 이의 계산시간을 단축시킬 수 있도록 하였다. 그리고 경로방식의 경우는 simulated annealing을 이용한 방법이 제안되고 있는데, 이 역시도 하나의 실행가능해를 구하는데 많은 계산시간을 필요로 한다는 단점이 있다. 이러한 문제점을 극복하면서 실행가능해를 제공하는 빠른 시간에 제공하는 매우 효과적인 해법을 제시하였다.
이와 같이 본 논문은 동기식 광전송망에 자동복구가 가능하게 하는 망의 구축과 관련된 문제점들을 효율적으로 해결할 수 있는 방안을 개발하여 제시하고 있다. 실제 동기식 광전송망이 구축에 있서는 이 외에도 해결되어야 할 많은 문제점들이 존재하지만, 우선적으로 해결할 수 있는 부분들을 면밀히 살펴보고 이의 문제점을 해결하는데 본 논문은 역점을 두고 있다.
