Network Survivability requires intelligence in the network to rapidly interpret the results of network diagnostics. Providing survivability in all parts of the SONET and ATM Networks in a cost effective way is therefore a key challenge. Self-healing techniques which offer a high level of protection and fast restoration response, while using a minimum of spare resources, are needed in order to obtain a high level of end-to-end service availability. In this thesis, the design and management problems of survivable communication networks are considered.
First, a ring-chain architecture with dual homing survivability is considered for metropolitan telecommunication networks. In the architecture, hub and high traffic nodes are covered with a SHR and other nodes with chains. Given a ring topology, the ring-chain design problem is formulated as an integer programming model which minimizes the link cost of chains while satisfying the dual homing constraint. An efficient tabu search procedure is proposed to solve the problem. Computational results show that the proposed tabu search provides near optimal solution within a few seconds.
Next, an integrated ring-mesh architecture is proposed in survivable networks. It is known that the mixed architecture can be more economical than the architecture which is composed of only rings or mesh. Design of ring-mesh network consists of three subproblems; the assignment of ADM rings and DCS mesh, the ring fiber routing and the working and spare capacity dimensioning in the mesh portion. Given a set of demand requirements, the assignment of ADM rings and DCS mesh is to find an optimal assignment of ADM and B-DCS equipments to the nodes in the network to cover all demand requirements such that the equipment cost of ADM and B-DCS is minimized. An efficient tabu search procedure is proposed to solve the problem. Computational results show that the proposed tabu search provides an optimal solution within a few minutes.
Next, a design of self-healing ATM network is proposed based on the backup virtual path(VP). It is known that the self-healing scheme by using the backup VP is simpler, faster and easier to implement than the conventional flooding scheme. Under irregular traffic fluctuations and multiple link falures, however, the flooding mechanism is more flexible and adaptive than the backup VP scheme. In the backup VP scheme, the flexibility is improved by employing multiple backup VPs. Given a set of bandwidth requirements and the working routes for VPs, the problem is formulated as an integer linear programming model. The objective is to find the backup route of each VP and the spare bandwidth of each physical link which are required to restore the services in link failures, such that the cost of total spare bandwidth is minimized. The efficient heuristics including an initial and two improvement heuristics are proposed to solve the problem. Computational results for realistic networks show that the proposed heuristics provides an nearly optimal solution within a reasonable running time.
Finally, the transmission of multiple real-time video sources is considered over ATM networks. To allow uniform picture quality of each video service, it is assumed that MPEG encoder generates each frame by employing constant quantization rate. Multiple real-time VBR videos are multiplexed into an ATM switch to transmit cells over ATM network. Given ATM switch capacity, the problem is to dynamically allocate the required channel bandwidth for each source such that the encoder buffer occupancy is maintained at a target level. The mathematical formulation is presented and an algorithm for optimal dynamic bandwidth allocation is proposed. To test the performance of the proposed scheme, two performance metrics are employed; the number of encoder rate controls required and the gap from a target buffer occupancy level to current buffer occupancy at each frame period. Based on these two performance metrics, the effects of the proposed scheme are analyzed for various system parameters such as ATM switch capacity, buffer size, LB token generation rate and target buffer occupancy.
본 논문은 광대역종합정보통신망의 설계 및 관리문제를 다룬다. 통신의 광대역수요에 따라 통신망은 지금까지 X.25, Frame Relay, SMDS, SONET/SDH 등의 진화 단계를 거쳐, 현재 ATM 기반 광대역 통신망으로 나아가고 있다. B-ISDN 망은 SONET/SDH를 기반으로하는 물리적계층과, ATM 기술을 기반으로 하는 ATM 계층으로 나누어진다. 광대역통신망 설계 및 관리에 있어서 생존도는 매우 중요한 문제이다. Gbps 급의 트래픽을 전송하는 전송링크의 고장발생시, 온라인으로 전송되는 중요 데이터의 손실은 매우 큰 경제적 손실을 가져다 준다. 따라서 본 논문에서는 망의 생존도를 중심으로, 이와 관련된 망 관리 및 설계 문제를 다루고자 한다. 본 논문은 크게 두 부분으로 나뉘어진다. 2장과 3장은 SONET 기반 물리적 계층에서의 망설계 문제를 다룬다. 4장과 5장은 ATM 망에서의 생존도 문제와 MPEG (Moving Picture Expert Group) 기반 실시간 비디오 전송 문제를 다룬다.
먼저 2장에서는 대도시 통신지역을 서비스하기 위한 Ring-Chain 망구조가 제안된다. Ring-Chain 망구조는 각각 ADM 장비를 각 교환국에 설치하여, 회선고장시 50 ms 안에 서비스를 복구하는 망복구능력을 제공한다. 제안된 Ring-Chain 구조에서는 트래픽이 많고 수익이 높은 교환국들을 OC-48 ADM Ring으로 연결하고, 나머지 교환국을 OC-3 혹은 OC-12 ADM Chain으로 연결 한다. Ring-Chain 망구조 설계를 위해 소요되는 망구축비용을 최소화하는 수리적모형이 제안되고, 최적 망설계를 위해 Cutting-Plane 알고리즘 및 Tabu Search 기법이 적용된다. 실험결과, Tabu Search 알고리즘은 1 - 2 분 안에 최적해에서 1 - 4%에 가까운 해를 제공한다.
3장에서는 광대역 통신 백본망의 설계를 위해 Ring-Mesh 구조가 제안된다. 기존의 통신망은 가입자망에서의 Ring 구조와 백본망에서의 Mesh 구조가 사용되어 왔으나, Ring 구조는 망확장이 어렵고, Mesh 구조는 DCS 등의 관련 장비비용이 비싸다는 단점이 있다. 본 논문은 Ring-Mesh 통합망구조를 제안하고, 소요되는 망구축비용을 최소화하는 최적화 문제를 다룬다. 해법으로 short-term memory와 long-term memory를 사용하는 Tabu Search 알고리즘이 제안된다. 실험결과 Ring-Mesh 통합망구조는 개별적인 Ring 및 mesh 구조에 비해, 최대 25%까지의 비용절감을 얻을 수 있다.
4장에서는 백업 VP를 기반으로 하는 ATM 통신망 설계 문제를 다룬다. ATM 망은 VP를 기반으로 트래픽을 전송한다. 망요소의 고장시, VP는 타격을 받게 되고, 이에 따라 백업 VP를 이용한 서비스 복구 문제가 해결되어야 한다. 백업 VP의 경우 평상시에는 대역폭을 필요로 하지 않는다. 다만 운용 VP가 작동할 수 없을 때에, 망으로부터 필요한 대역폭을 부여받아, 운용 VP의 역할을 수행하게 된다. 본 논문에서는 이러한 백업 VP에게 요구되는 여유대역폭이 최소화 되도록, 백업 VP 경로를 선정하는 문제를 다룬다. 이와 관련된 최적화 모형이 제안되고, 운용 및 백업 VP의 특성에 기반한 3가지의 알고리즘이 개발된다. 실험결과 빠른 시간안에 최적해에 근사한 값을 갖는 백업 VP 경로들이 구해진다.
마지막으로, 5장에서는 ATM 망에서의 MPEG 기반 실시간 비디오 전송을 위한 대역폭할당 문제를 다룬다. 화상회의와 같은 실시간 비디오 MPEG 트래픽은 지연시간에 민감한 VBR 트래픽 특성을 갖는다. 본 논문에서는 ATM 교환기 용량이 주어져 있을 때, 여러 명의 가입자가 동시에 실시간 비디오를 전송 하는 비디오 전송시스템을 고려한다. 여러 개의 비디오 소스 트래픽이 다중화되어, 주어진 교환기를 경유하여 ATM 망으로 진입한다. 이 때, 각 비디오 서비스에서 요구되는 전송지연시간을 적정수준으로 유지하면서, 망자원의 이용률을 극대화하는 "대역폭할당" 문제의 해결이 요구된다. 관련된 수리적 모형과 함께 최적 대역폭할당 알고리즘이 제안된다. 제안된 알고리즘의 성능평가를 위해 다양한 ATM 시스템 변수 - 버퍼크기, 트래픽 변수, 교환기 용량 등 - 을 대상으로 대역폭 할당 알고리즘이 적용된다.
