단위 수요를 가지는 링에서의 경로설정 및 파장할당에 관한 연구
A study on the routing and Wavelength assignment in ring with unit demands
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
링 루팅 및 파장할당 문제는 최근 활발하게 구축되고 있는 WDM 링의 설계 및 운용에 있어서 매우 중요한 문제이 다. 이 문제는 링 상의 노드 쌍간에 단위수요가 주어졌을 때, 각 수요들을 링상의 두 가지 가능한 경로 중 하나로 보내 기 위한 광경로의 설정과 설정된 광경로에 파장을 할당하는 두가지 의사결정을 동시에 결정하여야 되는 매우 복잡한 문제이다. 또한 파장할당시에 동일한 링크를 공유하는 광경로에는 동일한 파장을 할당할 수 없다는 제약이 있으면서, 목적함수는 할당하는 파장의 수를 최소화하는 것이 된다. 본 연구에서는 링 루팅 및 파장할당 문제에 대해 평행루팅을 만족하는 최적해가 항상 존재한다는 것을 보이고, 최적해의 다양한 특성들을 규명하기로 한다. 또한 새로운 하한을 제 시하고 이 하한이 기존의 하한에 비해서 매우 효과적임을 보이도록 한다
Abstract
The ring routing and wavelength assignment problem arose in the planning of optical communication networks which use WDM rings. Unit demands are given for each pair of nodes in an ring; each demand must be routed one of the two possible connections round the ring and the wavelength assignments must be made so that there are no conflicts; that is, no two connections whose routes share a link can be assigned the same wavelength along that link. The objective is to minimize the number of used wavelengths. We propose the parallel routing for the problem and show that there always exists an optimal solution satisfying it. Furthermore we suggest a new lower bound for the problem and show that it is very efficient for an exemplar network.
참고문헌 (13)
- "WDM 링에서의 루팅 및파장할당에 관한 연구", 27(4) (2002)
- "정수단위로만 루팅이 허용되는SONET링의 용량결정문제", 25(1) (1998)
- "분할 루팅이 허용되는 링의용량결정문제에 대한 개선된 해법", 26(4) (2001)
- "A new approximation algorithm for thedemand routing and slotting problem on rings with unitdemands", pp.210~220 (1999)
- "ExactSolution of the SONET Ring Loading Problem", 26, pp.119~129 (1999)
- "Optimalload balancing on SONET bidirectional rings", 45, pp.148~152 (1997)
- "An Efficient Algorithm for the RingLoading Problem with Integer Demand Splitting"
- "Finding Maximum Cliquesin Circle Graphs", 11, pp.269~278 (1981)
- "Thering loading problem", 11, pp.1~14 (1998)
- "Multimavelength OpticalNetworks: A Layered Approach" (1999), Addison Wesley
- "Coloring a family of circular arcs", 29(3)
- "Multicommodity flows in ring networks", 8, pp.235~242 (1996)
- "Ring Routing andWavelength Translation" (1998)