Given a set of connection requests, the problem of setting up a lightpath by routing and assigning a wavelength to each connection is called the RWA problem. It is known to be NP-complete. As a result, various heuristics have been proposed and evaluated under different networking assumptions. We prove that RWA with converter is NP-hard. And present heuristics also. We solve the minimizing the number of wavelengths problem and analyze trade off between the cost of a converter and a wavelength. We present IP formulation and heuristic both of them. We compare our heuristic with CPLEX. Our heuristic is more powerful than CPLEX. CPLEX can solve the problem of small size only. But our heuristic can solve the problem of large size although the computational time is small by far. We present LP bound using LP relaxation also. Consequently, one can be aware of upper bound and lower bound of the minimizing the numbder of wavelengths problem.
최근 각 가정까지 광통신 네트웍이 깔려 있는 상황 아래서 광네트웍을 어떻게 효율적으로 운영할까 하는 문제는 매우 중요한 문제로 인식되고 있다. 통신 수요자들에게는 기본적으로는 통신을 하고자 하는 개수만큼의 파장이 할당되어야 한다.
그러나 경로설정과 파장할당을 지능적으로 한다면 전체 네트웍상에서 필요한 파장의 개수를 현저히 줄일 수 있다. 즉 파장의 개수를 최대한 줄여서 네트웍을 운영하는 것은 매우 효율적이다. 이때 파장변환기를 사용할 수 있다면 파장변환기를 통과하는 파장은 파장종류가 바뀌어서 통신을 할 수 있다. 때문에 파장변환기를 이용할 수 있다면 전체 네트웍에서 필요로 하는 파장의 개수를 더욱 줄일 수 있다.
본 논문에서는 광네트웍에서 모든 통신수요를 만족하면서 필요로 하는 파장의 전체 개수를 줄이고자 노력했다. 이때 모든 노드에서 파장변환이 가능하다는 가정하에 파장할당 문제를 풀었다.
또한 파장변환기의 가격을 고려하여 파장변환기의 가격이 상대적으로 비쌀때와 저렴할때로 구분하여 이때 필요한 파장의 개수와 파장변환기의 개수 사이의 상관관계에 대한 분석을 하였다.
이때 파장변환기를 이용한 파장할당 문제가 NP-hard라는 것을 증명하고, Heuristic을 제시하였다.
