Design and analysis issues for current and future telecommunication/ Internet infrastructure are considered. Formulations of the problems and algorithms for them which are based on the mathematical programming approaches are presented.
First, a new network design problem of stacking multiple BLSRs (Bidirectional Line Switched Ring) on a conduit ring is considered. This problem is of great concern to Telcos and ISPs, which however has not been seriously addressed as yet. This scarcity, despite the practical importance of resource-efficient BLSRs, may be attributed to the problem complexity. The problem has been formulated as a natural IP model and reformulated as a set-partitioning model via the column generation approach. An iterative solution method of alternating between two phases of generating and fixing columns was developed and experimented with demand graphs of six different and practical scales. Computational experience gained from hundreds of test problems strongly supports the real-world applicability of the proposed model and the solution method.
Furthermore, the proposed solution framework is flexible enough to easily accommodate the real-world features like various ADM capacities or the other architecture (UPSR) by simply modifying the subproblem structure. An immediate extension of practical importance would be to stack both types of SHRs on a given conduit ring infrastructure.
Second, a unified approach of stacking multiple SHRs of two types of architectures (UPSR and BLSR) is presented. A column generation algorithm is also developed and experimented the algorithm with various demand patterns. Computational results show that the optimal hybrid stacked SHR configuration is more cost-effective than either one-type-only configurations.
Third, network approaches for MPLS traffic engineering is described in an online setting where future requests for bandwidth-guaranteed ingress-egress paths can be accommodated without rearranging existing paths. Ideas for routing that permit the best usage of the network infrastructure in this online scenario were described.
동기식전송망(SDH: Synchronous Digital Hierarchy), 파장분할다중화망(WDM: Wavelength Division Multiplexing)으로 대표되는 광전달망(optical transport network)은, 전통적인 음성뿐 아니라 급증하는 인터넷 트래픽을 처리하는 데 핵심적인 역할을 할 것으로 기대된다. 동기식전송망과 파장분할다중화망 모두에서 지배적인 구조로 평가되는 자가복구링(SHR: self-healing-ring)은, 단방향링(UPSR: unidirectional path switched ring)과 양방향링(BLSR: bidirectional line switched ring)으로 대별된다. 단방향링은 간단한 수요처리로 장비가격이 저렴한 반면, 양방향링은 양방향으로 수요처리를 가능하게 해서 보다 효율적인 수요처리가 가능하지만, 장비가격은 상대적으로 비싼 구조이다. 본 논문에서는 두 가지 링구조의 경제성 비교분석을 위해서, 자가복구링의 설계문제들과 수리계획모형에 기초한 해법을 제시하고 있다.
첫째, 링 형태의 관로망과 처리해야 할 트래픽 요구사항이 주어져 있을 때, 중첩된 양방향링(stacked BLSRs) 구성을 구하는 문제를 다룬다. 즉, 모든 트래픽 각각을 임의의 양방향링에 할당하고, 해당 양방향링에서는 할당된 수요의 양끝노드에 링장비를 설치하되, 개별 링에 할당되는 트래픽의 부하가 링의 용량을 넘지 않도록 하는 의사결정대안들 중에서 장비 비용이 최소화되는 대안을 찾는다.
이 문제에 대해서 정수계획(integer programming) 모형을 제시하고 열생성기법(column generation algorithm)과 변수고정법(variable fixing scheme)을 이용한 해법을 개발하였다. 열생성기법을 적용하기 위해서 모형을 주문제(master problem)와 부문제(subproblem)로 분해되는 정수계획모형으로 재정의하였으며, 부문제를 풀기 위한 분지-절단법(branch-and-bound)을 제시하였다. 주문제에 대한 선형계획완화문제(linear programming relaxation)의 해로서 하한값(lower bound)을 구하고, 제한된 열로 구성된 주문제에 대해서 분지-절단법을 적용함으로서 상한값(upper bound)을 구했다. 해를 개선하기 위해서 변수고정 후에 추가적인 열생성을 허용한 후 다시 분지-절단법을 적용함으로서 최적해에 근접한 해를 구할 수 있었다. 제시된 해법은 최적해를 보장하지는 못하지만, 전산실험을 수행한 결과 거의 모든 실험문제에 대해서 비교적 빠른 시간 안에 최적해를 제공하였다.
둘째, 링 형태의 관로망과 처리해야 할 트래픽 요구사항이 주어져 있을 때, 중첩된 혼합링(stacked UPSRs/BLSRs) 구성을 구하는 문제를 다룬다. 즉, 모든 트래픽 각각을 임의의의 단방향링 또는 양방향링에 할당하고, 해당 링에서는 할당된 수요의 양끝노드에 링장비를 설치하되, 개별 링에 할당되는 트래픽의 부하가 링의 용량을 넘지 않도록 하는 의사결정대안들 중에서 장비 비용이 최소화되는 대안을 찾는다. 이 문제에 대해서 열생성기법(column generation algorithm)과 변수고정법(variable fixing scheme)을 이용한 해법을 개발하였다. 전산실험을 수행한 결과 거의 모든 실험문제에 대해서 비교적 빠른 시간 안에 최적해를 제공하였다.
한편, 다양한 패턴의 트래픽에 대해서 단방향링과 양방향링의 장비가격을 변화시키면서 모형을 적용시켜본 결과, 주어진 패턴의 수요에 대해서, 상대적 장비가격이 상승할수록 단방향링 구조의 효율성이 점차 증가함을 알 수 있었고, 모든 상대가격에 대해서 혼합구조의 경우가 가장 저렴한 대안임을 알 수 있었다. 단방향링과 양방향링의 총비용이 동일해지는 상대가격(break-even point)에서 혼합구조의 가격절감효과가 가장 컸으며, 이 경우에 단방향링과 양방향링이 고루 섞인 구성이었음을 확인할 수 있었다.
