본 논문에서 파장 분할 다중화(WDM) 방식을 이용한 광 네트워크상의 라우팅과 파장할당 알고리즘을 고찰해 보겠다. 선형 프로그래밍(Linear Programming)과 그래프 컬러링(Graph Coloring)의 조합으로 이루어진 기존의 RWA기법들은 복잡하며, 발견적 방법(Heuristic Method) 사용이 요구된다. 이와 같은 방법은 실행시간이 길며, 최악의 경우에는 실행이 불가능하여 결과를 얻지 못한다. RWA를 해결하기 위한 다른 방법은 최대 EDPs(Edge Disjoint Paths)를 얻기 위해 greedy algorithm을 적용하는 것이다. 이것은 실행시간이 짧지만 파장의 수를 최적으로 사용하지 못한다. 본 논문에서 최대의 EDPs를 얻기 위해서 최대 흐름 기법(Maximum Flow Technique)을 이용한 새로운 알고리즘을 제안한다. 그리고 제안한 알고리즘과 기존에 제시된 최대 EDPs 알고리즘을 비교해 보겠다.
In the present paper routing and wavelength assignment (RWA) in optical WDM networks is considered. Previous techniques based on the combination of integer linear programming and graph coloring are complex and require extensive use of heuristics. Such methods are mostly slow and sometimes impossible to get results due to infeasibility. An alternative approach applied to RWA employs on the greedy algorithm for obtaining the maximum edge disjoint paths. Even though this approach is fast, it produces a solution for any connection request, which is very far from the optimal utilization of wavelengths. We propose a novel algorithm, which is based on the maximum flow technique to obtain the maximum quantity of edge, disjoint paths. Here we compare the offered method with previous maximum edge disjoint paths algorithms ap plied to the RWA.
