Ethernet is becoming the technology of choice for a wide variety of networking applications, mainly for offering high bandwidth, economies of scale, and flexibility. To further promote the preferential status of Ethernet technology and to expand its competition arena into new types of network infrastructure, efforts are on their way to equip the traditional Ethernet with the necessary features for supporting essential require-ments among which survivability from failures is the most important. The significance of survivability is fur-ther manifested with the advent of high speed fiber optic networks in which a short term failure may result in severe service loss.
Consequently, several Ethernet-based redundancy protocols have been identified in IEC 61850 as po-tential candidates for industrial communication networks. In particular, the High-availability Seamless Re-dundancy (HSR) protocol recently introduced by the IEC 62439-3 is drawing much attention for its capabil-ity of providing high availability with a zero failover time. This makes HSR attractive not only to industrial networks, but to other real-time and mission-critical networking applications such as smart grid, motion con-trol, and military communications. On the other hand, the increasing frequency and damage severity of dis-asters have influenced network operators to become more concerned with providing disaster-resiliency measures for their optical network infrastructures. However, mitigating network service interruption due to disaster region failures at the optical physical medium, by increasing network redundancy, is deemed spatial-ly-inefficient and very costly. Therefore, there is a growing attention in the research community on providing new approaches capable of overcoming existing limitations.
In this dissertation, we study the design of highly survivable Ethernet-based optical communication networks. As for this effect, two design problems are defined and investigated. In the first problem, we ad-dress an optimization problem of finding the topological layout of a mesh network which complies with HSR survivability conditions and satisfies a given network availability requirement at a minimal cost. We begin by investigating possible relaxation of HSR mesh architecture to enable the design of arbitrary HSR mesh net-works, and introducing an availability evaluation model for HSR mesh networks considering exact and esti-mation methods. The problem is investigated with a proposed topology-based enumeration algorithm which we later modify based on the fact that the search space can be efficiently reduced by exploiting the concept of meta-mesh. Due to the NP-hardness of the problem, however, obtaining the optimal design solution for large-size networks using enumeration algorithms becomes infeasible. Therefore, we develop two heuristic algorithms, the first is based on Minimum Spanning Tree (MST) and the second is based on a semi Hamilto-nian (SemiHam) cycle, to find a suboptimal solution at a polynomial time. It is shown that the proposed heu-ristic algorithms, especially the latter, are capable of achieving a performance comparable to the optimal solution in solving a design problem for large-scale complex networks.
In the second research problem, we address the challenge of providing the necessary counter-measures to protect optical network infrastructures from random disaster region failures exploiting the fact that medium diversification, which is still a largely unexplored technical field, has the potential to overcome the limited performance of wired infrastructure. We begin by introducing our system model and assumptions for the design of disaster-resilient wireless link-up augmented optical network infrastructures. We then formu-late this problem as an optimization model of finding the subset of links in an optical network topology whose wireless augmentation maximizes post-disaster overall network availability for a given budget con-straint. To overcome the computational complexity of finding the optimal design solution, a novel greedy-based heuristic algorithm is proposed. Performance comparisons with exhaustive enumeration search and simple heuristics validate the efficiency and scalability of our algorithm.
이더넷은 높은 대역폭, 경제성, 확장성을 제공하기 위한 네트워크 기술로 널리 이용되고 있다. 이더넷은 보다 넓은 응용에 적용하기 위하여 다양한 측면에서 개선되어 왔으며, 특히 장애로부터 네트워크를 효과적으로 보호하기 위한 디자인이 활발히 연구되어 왔다. 네트워크 보호는 짧은 시간의 장애가 큰 영향을 미치는 초고속 광 네트워크에서 더욱 중요한 의미를 가진다.
결과적으로, 산업용 통신 네트워크 (industrial communication networks) 를 위한 이더넷 기반의 보호 프로토콜들이 IEC 61850 에서 제안되었다. 특히, 최근에 IEC 62439-3 에서 제안된 High-availability Seamless Redundancy (HSR) 은 zero failover time 과 높은 네트워크 가용성을 제공한다는 점에서 많은 흥미를 끌고 있으며, 이러한 장점을 바탕으로 HSR은 산업용 네트워크 뿐만 아니라, smart grid, motion control, and military communications 와 같은 실시간 및 mission-critical 네트워크 응용에 적용될 수 있다. 반면, 재난상황 발생의 빈도 많아지고 재난이 네트워크 서비스 사업자에게 미치는 영향이 커짐에 따라, 재난에 강건한 광 네트워크 디자인이 중요해지고 있다. 이러한 재난 상황에서의 네트워크 장애를 극복하기 위해 광 네트워크의 redundancy를 증가시키는 기존의 방법은 spatially-inefficiency 문제와 비용 비효율적인 문제를 가지고 있다. 이러한 문제를 극복하기 위해서 새로운 접근 방법이 제안되어야 한다.
본 학위논문에서는 고신뢰 이더넷 기반 광 네트워크의 효율적 디자인 연구를 수행한다. 세부적으로, 다음 두개의 디자인 문제를 정의하고 연구한다. 첫번째 문제로서, 우리는 최소의 비용으로 주어진 가용성 요구사항을 만족시키는 HSR 토폴로지 디자인 문제를 다룬다. 먼저 HSR 메쉬 디자인을 위한 모델을 제시하고, 해당 디자인의 가용성을 측정하기 위한 방법을 제시한다. 최적 HSR 디자인을 위해서, topology 기반 열거 알고리즘 및 graph reduction을 이용한meta-mesh 알고리즘을 제안한다. 제안 알고리즘은 최적 디자인을 제시하는 반면, 높은 복잡도를 요구하여 실제 큰 네트워크에 적용하지 못하는 한계가 있다. 이를 극복하기 위하여, Minimum Spanning Tree (MST) 과 semi Hamiltonian (SemiHam) cycle 기반의 두개의 휴리스틱 알고리즘을 제시한다. 시뮬레이션 성능분석을 통하여 제안한 두개의 알고리즘들은, 특히 SemiHam 알고리즘, 최적에 근접한 디자인을 제시함을 보였다.
두번째 문제로, spatially-inefficiency 문제를 효율적으로 해결하기 위해 medium diversification 을 고려한 네트워크 디자인 문제를 다룬다. 이를 위해서, 무선 링크업을 이용한 광 네트워크 보호 시스템 모델을 소개하고, 주어진 비용을 가지고 향후 재난상황에 대해서 네트워크 가용성을 최대화 하는 무선 링크업 포설 위치를 찾는 최적화 알고리즘을 제안한다. 제안한 최적 알고리즘은 높은 복잡도를 가지고 있는 알고리즘으로써, 큰 네트워크에 적용할 수 없는 문제가 있다. 이를 해결하기 위해서, greedy-based 휴리스틱 알고리즘을 제안한다. 시뮬레이션 분석으로 통하여 최적 디자인과 비교 분석한 결과, 제안한 휴리스틱 알고리즘은 효율적으로 최적에 근접한 디자인을 찾아냄을 보였다.
