We consider several routing and wavelength assignment problems for the design of WDM(Wavelength Division Multiplexing) network. We present integer programming formulations of the problems and algorithms for them.
First, We consider routing and wavelength assignment problem(RWA) in WDM ring network employing wavelength routing. We are given a physical ring network, a set of selected pairs of nodes, the number of required connections for each selected pair of nodes. Required connection between a pair of nodes is realized on the given network by establishing a path between that pair of nodes and assigning a specific wavelength to the path. RWA is to realize all the given required connections on the given network under the constraint that the paths which share a link should be assigned to different wavelengths. The objective is to minimize the number of required wavelengths. We present an integer programming formulation for the problem which is decomposed into a master problem and a column generation problem. We proposed a branchand-price algorithm to solve the problem. We develop a polynomial time algorithm for the column generation problem by decomposing it into several subproblems. We also develop a pseudo polynomial time algorithm to find kth optimal solution to the column generation problem. Using the algorithm, we can generate columns in branch-and-bound tree. Computational results show that the algorithm find an optimal solution in reasonable time.
We also consider the RWA in survivable WDM mesh network. We assume an optical layer path protection scheme under the single-link failure. When a physical network and a set of working paths are given, we must select a link-disjoint protection path for each working path. We also assign a wavelength for each working and protection path. We will call this problem survivable routing and wavelength assignment(SRWA) problem. In wavelength assignment for protection paths, there are two possible methods. One method assigns an arbitrary wavelength for each protection path (method-I). The other method assigns the same wavelength to the protection path as its corresponding working path (method-II).
We consider SRWA under the two wavelength assignment methods. We present an integer programming formulation and an algorithm based on column generation and variable fixing procedure for the problem under each method. For each column generation problem, we also present an integer programming formulation which is decomposed into a master problem and a column generation problem. We develop a branch-and-price algorithm to solve each column generation problem by devising a branching rule such that the column generation is possible after branching. In variable fixing procedure, we fixed a variable to 1 and then we generated more columns at a stage until an integral solution is obtained. The algorithm does not guarantee optimal solution but we can get optimal solutions to all randomly generated test problems under the both methods.
본 논문에서는 파장분할 다중화 기술을 사용하는 국간 전광통신망 설계를 위한 경로설정 및 파장할당문제들에 대한 정수계획모형과 정수계획기법에 기초한 해법을 제시하고 있다.
첫째, 링형 구조를 갖는 통신망의 경로설정 및 파장할당문제를 연구하였다. 링 형태의 물리망과 광경로의 수립이 요구되는 노드쌍 및 각 노드 쌍에 요구되는 경로의 수가 주어졌을 때, 최소의 파장을 사용하도록 각 노드 쌍에 대하여 경로를 수립하고, 수립된 경로에 파장을 할당하는 문제이다. 본 연구에서는 이 문제에 대해 주문제와 부문제로 분해되는 정수계획모형을 제시하고 열생성기법과 분지-평가법을 이용한 최적 해법을 제시하였다. 열 생성문제에 대하여 여러개의 하부 문제로 나누고 각 하부 문제를 순차적으로 해결하여 최적해를 구하는 다항시간 알고리즘을 수립하였다. 또한, 열 생성 문제의 k 번째 최적해를 구할 수 있는 의사 다항시간 알고리즘을 제안 하였고, 이를 이용하여 분지-평가법에서 분지 후에도 계속하여 열 생성이 가능함을 보였다. 전산 실험 결과 제안된 알고리즘은 빠른 시간안에 실험 문제의 최적해를 제공함을 확인 하였다.
둘째, 생존도를 고려한 파장분할 다중화 방식의 통신망에서의 경로설정 및 파장할당문제를 연구하였다. 생존도의 고려를 위해, 링크는 한 번에 하나의 링크만이 고장날 수 있음을 가정하였고, 경로 보호 방식을 가정하였다. 이는 운용 경로와 함께 보호 경로를 미리 수립하여 링크 고장 시 보호 경로를 사용하는 방법으로, 해당 운용 경로와 보호 경로는 링크를 공유하지 않는다. 물리망과 물리망 위에서의 운용 경로가 주어 졌을 때, 각 운용 경로에 대하여 링크를 공유하지 않는 보호 경로를 수립하고, 각 운용 경로 및 보호 경로에 파장을 할당하는 문제이다. 파장 할당은 각 운용 경로와 보호 경로가 동일한 파장을 사용하여야 하는 경우와 그렇지 않은 경우로 나뉘어질 수 있다. 본 연구에서는 두 가지의 경우에 대한 연구를 각각 수행하였다.
본 연구에서는 두 가지의 파장할당 문제들에 대하여 각각 정수계획모형을 제시하고 열생성기법과 변수 고정법을 이용한 해법을 제시하였다. 각 열 생성문제에 대하여 다시 주문제와 부문제로 분해되는 정수계획모형들을 제시하고 열생성기법과 분지-평가법을 이용한 최적 해법을 제시하였다. 각 열생성 문제들에 대하여, 분지 후에도 열생성이 가능한 분지 정책을 제시 하여 최적해를 구할 수 있었다. 제시된 해법은 최적해를 보장해 주지 못하지만, 전산실험을 수행한 결과, 모든 실험 문제에 대하여 비교적 빠른 시간안에 최적해를 제공하였고, 두 파장 할당 방법에따라 요구되는 파장 수의 차이가 10 ~ 30 % 정도임을 확인할 수 있었다.
