In the survivability and simplicity aspect, SONET Self-healing Ring(SHR) is one of the most important schemes for the high-speed telecommunication networks. Since the ring capacity requirement is defined by the largest STS-1 cross-section in the ring, load balancing is the key issue in the design of SONET SHR. Recently, most of the research on load balancing problem have been concentrated on the SONET single-ring case. However, in certain applications, multiple-ring configuration is necessary because of the geographical limitations or the need for extra bandwidth. In this thesis, the load balancing problem for SONET dual-ring is considered. Two models are examined: a SONET dual-ring only with inter-ring demands and the one with inter- and intra-ring demands. Symmetric demand pattern is assumed for both cases. A SONET sigle-ring network with asymmetric demand pattern is also examined. We present a linear programming based formulation of each problem. Computational experiments are performed on various size of networks with randomly generated demand sets.
네트웍의 전달매체가 광섬유로 바뀜에 따라 통신수요의 처리용량이 크게 증대되었으나, 이와 함께 사고나 고장에 의해 발생할 수 있는 피해의 크기도 역시 대규모화 하게 되었다. 그러므로, 네트웍의 설계시에 생존도를 높일 수 있는 방법을 고려하지 않으면 안되는데, Self-Healing Ring은 여러 가지 네트웍 형태 중 통신 네트웍의 생존도를 보장하는 가장 앞선 형태 중 하나이다. SONET 표준은 이러한 SHR의 현실적, 경제적인 구현을 가능케 해 준 통신표준이다.
SONET SHR의 설계시에 주어진 수요를 처리할 수 있는 최소한의 용량을 결정하는 load balancing문제를 해결해야 하는데, 지금까지의 연구는 주로 하나의 SONET SHR에서의 문제를 다루고 있었다. 그러나, 지리적, 경제적 환경여건에 의해서나 혹은 추가적인 용량이 필요한 경우 다중링 구조가 필요하게 된다. 다중링에 있어서의 load balancing 문제는 단일링에 비해 매우 복잡한 문제가 되는데, 다중링의 가장 간단한 형태인 이중링의 load balancing 문제해결이 연구의 목적이었다.
2 장에서는 링간 수요만 존재하는 경우를 상정하여 load balancing 문제를 다루었다. 두 링의 노드 수는 서로 다를 수 있고, 수요는 하나의 경로로만 전송되며, 수요는 대칭적이라고 가정하였다. 가장 큰 전송량이 걸려 있는 경로를 피해가는 방법으로 초기해를 얻고, 각 링크의 가중치를 검사하여 경로를 바꾸는 방식으로 이를 개선해 나가는 알고리듬을 제시하였다.
3 장에서는 링간 수요와 링내 수요가 모두 존재하는 경우의 load balancing 문제를 다루었고, 2 장에서 개발한 알고리듬과 기존에 알려진 DENS 알고리듬을 결합한 알고리듬을 제시하였다.
4 장에서는 수요가 대칭적이라는 가정을 완화한 모델을 단일링에 적용시켜 다루었다.
