This thesis investigates three different models of configuring both backbone and logical networks in various reconfigurable networks with unreliable links. In those models, the network reliability issue, as well as the network capacity expansion issue, is analytically treated to take into account routing and rerouting polices desired at each link failure occurrence. Moreover, the models consider economic trade-offs between backbone link capacity expansion cost and inferior network performance penalty in a situation where the associated networks are subject to link failures.
The first model considers the problem of configuring backbone and logical networks in a reconfigurable circuit-switched network where network topological states are subject to link failures, which is formulated as a zero-one nonlinear mixed integer programming problem. The objective of the problem is to find jointly the link capacities of the backbone network, the physical paths for logical links on the backbone network, the capacities of the logical links, and the routings on the logical network that minimize the network cost, given the topology of a backbone network and its associated logical network topologies for each network operation (failure) state, and the traffic demand between each origin-destination pair. In the problem, the network cost includes the backbone link capacity expansion cost, the expected lost-call traffic cost and the hop cost. The expected lost-call traffic and the number of hops are incorporated to reflect the network performance in circuit-switched networks. A solution procedure is derived based on a Lagrangean relaxation that generates feasible solutions, together with lower bounds on the optimal objective function value. Two heuristic methods, for generating a good initial primal feasible solution and for improving the upper bounds, are also incorporated into the solution procedure. The solution procedures are exploited and their efficiencies are tested with various numerical examples.
The second model considers a design problem of a reconfigurable packet-switched network subject to link failures, that has the objective of minimizing the backbone link expansion cost and the average network delay cost on logical links. The average packet delay is selected as a performance measure of the packet-switched network and incorporated into the objective function as the performance penalty function. The problem is to be modeled as a zero-one nonlinear mixed integer programming problem. The Lagrangean relaxation and a subgradient optimization method are used for finding a lower bound to derive an effective solution procedure. In the meantime, a heuristic procedure is developed for converting any intermediate solution generated at each subgradient iteration into a better feasible solution so as to result in a better upper bound on the problem solution. The algorithm is tested for its performance evaluation.
The last model addresses the problem of determining jointly the VP topology, the capacity assignment of the physical links, the bandwidth allocation of VPs, and the routing assignments of traffic demand in a reconfigurable ATM network with unreliable links to minimize the total network cost composed of the cost of expanding backbone links and the performance penalty related with the network throughput. For the problem a heuristic solution procedure is exploited based on a Lagrangean relaxation, and tested extensively with practical-sized problems to show how effective it is.
본 논문은 링크 고장을 고려한 다양한 재구성 가능망에서의 백본망 (backbone network)과 논리망 (logical network)을 동시에 구성하는 세가지의 서로 다른 모델을 다룬다. 이 모델들에서는 망 용량의 확장 이슈 뿐 아니라 망의 신뢰성 이슈도 함께 다룬다. 또한, 모델들은 백본 링크 용량의 확장 비용과 링크 고장시 망의 자원 감소로 인한 망 성능 저하에 따른 비용사이의 경제적 타협점 (economic trade-off)을 고려한다.
첫번째 모델은 망의 상태가 링크의 고장에 따라 변화하는 재구성 가능 회선교환망에서의 백본 및 논리망의 구성 문제를 고려한다. 이 모델은 0-1 비선형 혼합 정수계획 문제로 정형화된다. 문제의 목적은 백본망과 망 상태별 논리망의 토폴로지 및 각 노드쌍 사이의 트래픽 수요가 주어진 상태에서, 백본 링크의 용량 확장 비용과 망 성능 저하에 따른 비용으로 구성된 전체 비용을 최소화하기 위한 각 백본 링크들의 용량, 백본망상에서 논리 링크들의 물리적 경로, 논리 링크들의 용량 및 논리망에서의 루팅들을 함께 결정하는 것이다. 여기서 망 성능과 관련된 비용은 트래픽 손실 비용과 노드에서의 처리비용의 기대값으로 구성된다. Lagrangean relaxation에 기초한 문제의 해법이 및 초기 가능해를 결정하기 위한 발견적 방법과 가장 우수한 가능해를 구하기 위한 발견적 방법이 제시된다. 해법을 시험하기 위하여 여러 예제들이 이용된다.
두번째 모델은 링크의 고장을 고려한 재구성 가능 패킷교환망의 설계 문제이며, 백본 링크의 확장 비용과 논리 링크들 상의 평균 패킷지연 비용의 최소화를 목적으로 한다. 망 성능 평가를 위해 고려된 평균 패킷 지연은 패킷망에서 가장 중요한 성능 지표이다. 이 문제는 0-1 비선형 혼합 정수계획 문제로 정형화된다. 효과적인 해법을 유도하기 위한 방법으로 최적해의 우수한 하한값을 제공하는 Lagrangean relaxation 및 subgradient 방법을 사용하며 subgradient 방법의 중간 해로 부터 우수한 가능해를 도출하기 위한 발견적 방법이 개발되며, 알고리즘의 성능 평가를 위한 여러 시험이 수행된다.
마지막 모델은 링크 고장 가능성이 있는 ATM 망의 설계 문제로써, 백본 링크 확장 비용과 망의 throughput 성능 비용으로 구성된 전체 망 비용의 최소화를 위한 백본 링크 용량 및 가상 경로망의 구성을 결정한다. Lagrangean relaxation에 바탕을 둔 발견적 기법이 제시되며 알고리즘의 효과를 측정하기 위하여 실제 운용 중인 망을 대상으로 시험한다.
