본 논문은 광통신망에서 (s,t)에 대한 다중 패킷 통신 요구에 대해 최적의 광 경로를 설정하고, 최소 파장 수를 배정하는 경로설정과 파장 배정 문제 (RWAP)를 다룬다. RWAP는 지금까지 다항시간으로 최적 해를 구하는 알고리즘이 알려져 있지 않은 NP-완전으로 근사 해를 다항시간으로 구하고 있다. 본 논문은 주어진 망의 모든 (s,t)에 대해 최단 광 경로로 동일한 홉 수를 갖는 주경로와 대체경로를 사전에 결정하고, (s,t)에 대한 실제 특정 다중 패킷 통신이 요구될 때 이들 이중 경로를 이용하여 최대로 이용되는 간선의 이용횟수를 b개로 줄이고, b개의 파장 수 상자에 중복 간선 없이 담는 방법으로 O(kn) 계산 복잡도로 최적 해를 구할 수 있었다. 2개의 실험 데이터 망에 적용한 결과, 제안된 알고리즘은 기존에 알려진 최적 해를 얻을 수 있음을 보였다.
본 논문은 광통신망에서 (s,t)에 대한 다중 패킷 통신 요구에 대해 최적의 광 경로를 설정하고, 최소 파장 수를 배정하는 경로설정과 파장 배정 문제 (RWAP)를 다룬다. RWAP는 지금까지 다항시간으로 최적 해를 구하는 알고리즘이 알려져 있지 않은 NP-완전으로 근사 해를 다항시간으로 구하고 있다. 본 논문은 주어진 망의 모든 (s,t)에 대해 최단 광 경로로 동일한 홉 수를 갖는 주경로와 대체경로를 사전에 결정하고, (s,t)에 대한 실제 특정 다중 패킷 통신이 요구될 때 이들 이중 경로를 이용하여 최대로 이용되는 간선의 이용횟수를 b개로 줄이고, b개의 파장 수 상자에 중복 간선 없이 담는 방법으로 O(kn) 계산 복잡도로 최적 해를 구할 수 있었다. 2개의 실험 데이터 망에 적용한 결과, 제안된 알고리즘은 기존에 알려진 최적 해를 얻을 수 있음을 보였다.
This paper deals with the routing and wavelength assignment problem (RWAP) that decides the best lightpaths for multiple packet demands for (s,t) in optical communication and assigns the minimum number of wavelengths to given lightpaths. There has been unknown of polynomial-time algorithm to obtain ...
This paper deals with the routing and wavelength assignment problem (RWAP) that decides the best lightpaths for multiple packet demands for (s,t) in optical communication and assigns the minimum number of wavelengths to given lightpaths. There has been unknown of polynomial-time algorithm to obtain the optimal solution for RWAP. Hence, the RWAP is classified as NP-complete problem and one can obtain the approximate solution in polynomial-time. This paper decides the shortest main and alternate lightpath with same hop count for all (s,t) for given network in advance. When the actual demands of communication for particular multiple packet for (s,t), we decrease the maximum utilized edge into b utilized number using these dual-paths. Then, we put these (s,t) into b-wavelength bins without duplicated edge. This algorithm can be get the optimal solution within O(kn) computational complexity. For two experimental data, the proposed algorithm shows that can be obtain the known optimal solution.
This paper deals with the routing and wavelength assignment problem (RWAP) that decides the best lightpaths for multiple packet demands for (s,t) in optical communication and assigns the minimum number of wavelengths to given lightpaths. There has been unknown of polynomial-time algorithm to obtain the optimal solution for RWAP. Hence, the RWAP is classified as NP-complete problem and one can obtain the approximate solution in polynomial-time. This paper decides the shortest main and alternate lightpath with same hop count for all (s,t) for given network in advance. When the actual demands of communication for particular multiple packet for (s,t), we decrease the maximum utilized edge into b utilized number using these dual-paths. Then, we put these (s,t) into b-wavelength bins without duplicated edge. This algorithm can be get the optimal solution within O(kn) computational complexity. For two experimental data, the proposed algorithm shows that can be obtain the known optimal solution.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 (s,t)의 수를 k, 망의 간선 수를 n이라 할 때, RWAP의 최적 해를 O(kn)의 다항시간으로 얻을 수 있는 휴리스틱 알고리즘을 제안한다.
본 논문은 NP-완전으로 분류되어 최적 해를 얻을 수 있는 다항시간 알고리즘이 제안되지 않고 있는 RWAP에 대해 다항시간 알고리즘을 제안하였다.
[1]은 그림 2의 RWAP에 대해 그래프 색칠 문제 (graph coloring)로 풀고자 하였다. 주어진 광 경로를 정점으로, 광 경로들이 중첩되는 경우를 간선으로 표현하여 최소 채색 수 (minimum chromatic number, x(G)를 구하고자 하였다. 채색수 방법으로는 Li와 Simha[11]의 연구도 있다.
제안 방법
본 장에서는 근방탐색 (neighborhood search) 개념을 적용하여 O(m+n)수행 복잡도의 BFS (breadth-first search)나 DFS (depth-first search)의 트리 탐색으로 최적의 경로를 찾는 방법을 제안한다. 이 방법은 s의 인접 노드들 v1을 N1(s), N1(v1)의 인접 노드들 v2를 s의 2차 근방 N2(s)로 하여 t까지의 중간 노드들을 찾아 최소의 동일한 홉 수 (hop count)를 가진 주경로 (main path)와 대체경로 (alternate path)를 설정한다.
제안된 알고리즘은 사전에 파악된 m×n개의 (s,t) 주경로와 대체경로 테이블 데이터를 활용하여, 실제로 통신이 요구되는 (i,j)들을 대상으로, 행을 (s,t), 열을 s에서 t까지 거치는 스위치들 간의 간선으로 표현한 행렬을 이용한다.
첫 번째로 15개의 (s,t)에 대한 주경로를 표시한 결과 {1,2} 간선이 6회 사용되어 (1,8)과 (2,3)을 대체경로로 변경하여 {1,2}, {3,4}와 {3,7}이 4회 사용되도록 하였다. 따라서 이 결과에 대해 4개의 파장 수 상자에 채울 수 있다면 최소 파장 수는 4를 얻을 수 있다.
최소 파장을 배정하는 방법으로 본 장에서는 채색수 알고리즘에서 적용한 독립집합을 하나의 파장(색)으로 배정하는 방법을 응용하여 #를 가진 b개의 (s,t)들을 각각 b개 상자에 채우는 방법을 적용한 독립집합 상자 채우기 알고리즘 (independent set bin packing algorithm, ISBPA)을 제안한다. 일단 b개 상자에 하나씩 (s,t)를 채운 후 나머지 미배정된 (s,t)들은 각 상자에 채워진(s,t)와 동일한 열 (간선)을 갖지 않는 (s,t)들을 선정하여 채우는 방법이다.
성능/효과
(2) 파장변환장치가 없는 상태에서 하나의 광 경로는 자신의 경로 상에 있는 각 회선 (간선)에서 동일 파장을 차지해야만 한다. 이 제약사항을 파장 연속성 제약조건 (wavelengthcontinuity constraint)이라 한다.
2개의 실험 데이터 망에 적용한 결과, ISBPA는 기존에 알려진 최적 해를 모두 찾을 수 있음을 보였다. 따라서, 본 논문은 NP-완전으로 분류된 RWAP에 대해 다항시간으로 최적해를 얻을 수 있는 알고리즘이 존재함을 보였다.
LFFP는 6/45, MNH은 4/45, LFAP는 4/47, HPLD는 4/49로, 제안된 LFAP와 HPLD는 기존에 알려진 MNH에 비해 동일한 파장 수는 얻었지만 홉 수가 +2와 +4로 보다 나쁜 결과를 얻었다.
표 3은 4개 상자 w1,w2,w3,w4의 각 상자에(s,t)들의 열 간선이 중복되지 않도록 채운 결과를 보여주고 있다. 결론적으로 파장 수는 4, 홉 수는 45를 얻었다.
2개의 실험 데이터 망에 적용한 결과, ISBPA는 기존에 알려진 최적 해를 모두 찾을 수 있음을 보였다. 따라서, 본 논문은 NP-완전으로 분류된 RWAP에 대해 다항시간으로 최적해를 얻을 수 있는 알고리즘이 존재함을 보였다.
본 논문에서 제안된 ISBPA는 (s,t)의 최단 광 경로로 동일한 홉 수를 갖는 주경로와 대체경로를 사전에 결정하고, 실제 (s,t) 통신이 요구될 때 이들 이중 경로를 이용하여 최소로 이용되는 간선을 결정하고, 파장 수 상자에 담는 방법으로 O(kn) 수행 복잡도로 최적 해를 구할 수 있었다.
제안된 ISBPA는 (s,t) 수를 k, 망의 간선 수를 n이라 할 경우 O(kn)수행 복잡도로 최적 해를 얻을 수 있는 장점을 갖고 있다. 즉, NP-완전으로 분류되어 다항시간 알고리즘이 알려져 있지 않은 RWAP에 대해 다항시간 알고리즘이 존재함을 보였다.
제안된 ISBPA는 N2 망에 대해서는 채색 수 알고리즘과 동일한 파장 수를 얻었지만 홉 수를 1개 감소시켰다. N2 망에 대해서는 MNH과 동일한 파장 수와 홉 수를 얻었다.
제안된 ISBPA는 (s,t) 수를 k, 망의 간선 수를 n이라 할 경우 O(kn)수행 복잡도로 최적 해를 얻을 수 있는 장점을 갖고 있다. 즉, NP-완전으로 분류되어 다항시간 알고리즘이 알려져 있지 않은 RWAP에 대해 다항시간 알고리즘이 존재함을 보였다.
질의응답
핵심어
질문
논문에서 추출한 답변
RWAP에서 경로 설정은 어떤 과정인가?
이를 RWAP (routing and wavelength assignment problem)라 한다[1]. 여기서 경로 설정은 원천 s 로부터 망 패킷 (network packet)이 중간 노드 (intermediate nodes)들을 거쳐 목적지 t 까지 전달되는 망의 최적의 경로 (best paths)들을 선택하는 과정이다. 이와 같이 설정된 경로를 따라 광통신은 레이저의 다른 파장을 통해 신호가 전송된다.
경로설정과 파장 배정을 해야하는 경우는 무엇인가?
m개의 패킷 스위치들로 구성된 광통신망에서 k개의 s에서 t 로의 패킷 전송이 동시에 요구될 경우, 경로설정 (routing)과 파장 배정 (wavelength assignment)을 해야 한다. 이를 RWAP (routing and wavelength assignment problem)라 한다[1].
RWAP는 근사 해를 어떻게 구하는가?
본 논문은 광통신망에서 (s,t)에 대한 다중 패킷 통신 요구에 대해 최적의 광 경로를 설정하고, 최소 파장 수를 배정하는 경로설정과 파장 배정 문제 (RWAP)를 다룬다. RWAP는 지금까지 다항시간으로 최적 해를 구하는 알고리즘이 알려져 있지 않은 NP-완전으로 근사 해를 다항시간으로 구하고 있다. 본 논문은 주어진 망의 모든 (s,t)에 대해 최단 광 경로로 동일한 홉 수를 갖는 주경로와 대체경로를 사전에 결정하고, (s,t)에 대한 실제 특정 다중 패킷 통신이 요구될 때 이들 이중 경로를 이용하여 최대로 이용되는 간선의 이용횟수를 b개로 줄이고, b개의 파장 수 상자에 중복 간선 없이 담는 방법으로 O(kn) 계산 복잡도로 최적 해를 구할 수 있었다.
참고문헌 (12)
H. Zang, J. Jue, and B.Mukherjee, "A Review of Routing and Wavelength Assignment Approaches for Wavelength Routed Optical WDM Networks," Optical Networks Magazine, Jan. 2000.
I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath Communications:An Approach to High Bandwidth Optical WAN's," IEEE Transactions on Communications, Vol. 40, No. 7, pp. 1171-1182, Jul. 1992.
J. P. Jue, "Lightpath Establishment in Wavelength- Routed WDM Optical Networks," Optical networks, Kluwer Academic Publishers, pp. 99-122, 2001.
G. Z.Markovic and V. S. Acimovic-Raspopovic, "Solving the RWA Problemin WDM Optical Networks Using the BCO Meta-Heuristic," Telfor Journal, Vol. 2, No. 1, pp. 43-48, Jan. 2010.
C. Dzongang, P. Galinier, and S.Pierre, "A Tabu Search Heuristic for the Routing and Wavelength Assignment Problemin Optical Networks," IEEE Communications Letters, Vol. 9, No. 5, pp. 426-428, May 2005.
S. Baroni and P. Bayvel, "Wavelength Requirements in Arbitrarily Connected Wavelength-Routed Optical Networks," IEEE/OSA Journal of Lightwave Technology, Vol. 15, No. 2, pp. 242-251, Feb. 1997.
J.H. Siregar, H, Takagi, and Y. Zhang, "Efficient Routing and Wavelength Assignment in Wavelength-Routed Optical Networks," Proceedings of 7th Asia-Pacific Network Operations and Management Symposium, pp. 116-127. Oct. 2003.
D. Banerjee and B. Mukherjee, "A Practical Approach for Routing and Wavelength Assignment in Large Wavelength-Routed Optical Networks," IEEE Journal on Selected Areas in Communications, Vol. 14, No. 5, pp. 903-908, Jun. 1996.
S. Even, A. Itai, and A. Shamir, "On the Complexity of Timetable and Multi-commodity Flow Problems," SIAM Journal on Computing, Vol. 5, No. 4, pp. 691-703, 1976.
C. Hendrik, "RFC1058, Routing Information Protocol," The Internet Society, Jun. 1988.
G. Li and R. Simha, "The Partition Coloring Problem and its Application to Wavelength Routing and Assignment," Proceedings of the First Workshop on Optical Networks, pp. 1-19, 2000.
T. F. Noronha and C. C. Ribeiro, "Routing and Wavelength Assignment by Partition Colouring," European Journal of Operational Research,Vol. 171,No. 3, pp. 797-810, Jun. 2006.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.