WDM방식을 기반으로 한 광 네트워크상에서 최대 EDPs(Edge Disjoint Paths)을 이용한 라우팅 및 파장할당 알고리즘
Routing and Wavelength Assignment in Optical WDM Networks with Maximum Quantity of Edge Disjoint Paths
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서 파장 분할 다중화(WDM) 방식을 이용한 광 네트워크상의 라우팅과 파장할당 알고리즘을 고찰해 보겠다. 선형 프로그래밍(Linear Programming)과 그래프 컬러링(Graph Coloring)의 조합으로 이루어진 기존의 RWA기법들은 복잡하며, 발견적 방법(Heuristic Method) 사용이 요구된다. 이와 같은 방법은 실행시간이 길며, 최악의 경우에는 실행이 불가능하여 결과를 얻지 못한다. RWA를 해결하기 위한 다른 방법은 최대 EDPs(Edge Disjoint Paths)를 얻기 위해 greedy algorithm을 적용하는 것이다. 이것은 실행시간이 짧지만 파장의 수를 최적으로 사용하지 못한다. 본 논문에서 최대의 EDPs를 얻기 위해서 최대 흐름 기법(Maximum Flow Technique)을 이용한 새로운 알고리즘을 제안한다. 그리고 제안한 알고리즘과 기존에 제시된 최대 EDPs 알고리즘을 비교해 보겠다.
Abstract
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 applied to the RWA.
참고문헌 (12)
- "A review of routing and wavelength assignment approaches for wavelength- routed optical WDM networks", 1(1), pp.47~60 (2000)
- "Routing and Wavelength Assignment in All-Optical Network", 3(5), pp.489~500 (1995)
- "Practiacal Approach for Routing and Wavelength Assignment in LargeWavelength Routed Optical Networks", 14(5), pp.903~908 (1996)
- "Routing and Wavelength Assignment in Optical Network From Edge Disjoint Path Algorithms", 6(ha 5), pp.211~213 (2002)
- "A Practical RWA Algorithm Based on Lookup Table for Edge Disjoint Paths", 2713, pp.138~147 (2003)
- "An Efficient Heuristic for Routing and Wavelength Assignment in Optical WDM Networks", 5, pp.2734~2739 (2002)
- "Practical Routing and Wavelength Assignment Algorithms for All Optical Networks with Limited Wavelength Conversion", 5, pp.2750~2755 (2002)
- "Rrovisioning algorithms for WDM optical networks IEEE", ACM Trans. On Networking, 1999, pp.7(5), 767~778
- "Lightpath (wavelengthrouting in large WDM networks", 14(5), pp.909~913 (1996)
- "Approximation algorithms for disjoint paths problems" (1996), MIT, Cambridge, May, 1996.
- "Flows in Network" (1962), Princeton University Press Princeton
- "Path Set Selection in Mobile Ad Hoc Networks" (2002)