DWDM 기반 차세대 광 인터넷 망에서 VS기반의 차등화된 멀티캐스트 라우팅 및 파장할당 알고리즘 연구 A Study on Virtual Source-based Differentiated Multicast Routing and Wavelength Assignment Algorithms in the Next Generation Optical Internet based on DWDM Technology원문보기
지난 수 십 년간 통신 기술의 발전과 웹 서비스의 팽창은 인터넷 사용자 수의 폭발적인 증가와 화상회의, 가상 증감 현실, 인터넷 게임 등 실시간 멀티미디어 멀티캐스트 서비스의 급격한 증가를 초래했다. 고밀도 파장분할다중화기술에 기반한 DWDM(Dense-Wavelength Division Multiplexing) 기술은 인터넷 사용자의 증가와 그에 따른 대역폭 요구를 수용하기 위한 방안으로 국가나 글로벌 영역 범위의 차세대 인터넷망 구현을 위한 백본망 기술로 여겨지며, 이러한 DWDM 전달망에서는 멀티캐스트 연결 요구에 대해 최적의 경로를 선택하고 선택된 경로에 효율적으로 파장을 할당하는 멀티캐스트 RWA(Routing and Wavelength Assignment) 문제가 파장 대역폭의 효율적인 활용 측면에서 매우 중요하게 다루어지고 있다. 주어진 파장 수 환경에서 최대한 많은 수의 멀티캐스트 연결을 달성하는 문제는 일반적으로 Non -deterministic Polynomial-time-complete 문제로 여겨지는 데, 본 논문에서는 가상소스를 기반으로 노드의 능력에 따른 차등화로 우선 순위를 적용하여 휴리스틱하게 멀티캐스트 라우팅 경로를 효율적으로 선정하는 DVS-PMIPMR (Differentiated Virtual Source-based Priority Minimum Interference Path Multicast Routing) 알고리즘을 제안한다. 마지막으로 같은 조건에서 더 많은 수의 멀티캐스트 라우팅 패스의 연결이 가능함을 시뮬레이션 및 성능분석 증명한다.
지난 수 십 년간 통신 기술의 발전과 웹 서비스의 팽창은 인터넷 사용자 수의 폭발적인 증가와 화상회의, 가상 증감 현실, 인터넷 게임 등 실시간 멀티미디어 멀티캐스트 서비스의 급격한 증가를 초래했다. 고밀도 파장분할다중화기술에 기반한 DWDM(Dense-Wavelength Division Multiplexing) 기술은 인터넷 사용자의 증가와 그에 따른 대역폭 요구를 수용하기 위한 방안으로 국가나 글로벌 영역 범위의 차세대 인터넷망 구현을 위한 백본망 기술로 여겨지며, 이러한 DWDM 전달망에서는 멀티캐스트 연결 요구에 대해 최적의 경로를 선택하고 선택된 경로에 효율적으로 파장을 할당하는 멀티캐스트 RWA(Routing and Wavelength Assignment) 문제가 파장 대역폭의 효율적인 활용 측면에서 매우 중요하게 다루어지고 있다. 주어진 파장 수 환경에서 최대한 많은 수의 멀티캐스트 연결을 달성하는 문제는 일반적으로 Non -deterministic Polynomial-time-complete 문제로 여겨지는 데, 본 논문에서는 가상소스를 기반으로 노드의 능력에 따른 차등화로 우선 순위를 적용하여 휴리스틱하게 멀티캐스트 라우팅 경로를 효율적으로 선정하는 DVS-PMIPMR (Differentiated Virtual Source-based Priority Minimum Interference Path Multicast Routing) 알고리즘을 제안한다. 마지막으로 같은 조건에서 더 많은 수의 멀티캐스트 라우팅 패스의 연결이 가능함을 시뮬레이션 및 성능분석 증명한다.
Over the past decade, the improvement of communications technologies and the rapid spread of www (World Wide Web) have brought on the exponential growth of users using Internet and real time multimedia multicast services like video conferencing, tele-immersive virtual reality, and Internet games. Th...
Over the past decade, the improvement of communications technologies and the rapid spread of www (World Wide Web) have brought on the exponential growth of users using Internet and real time multimedia multicast services like video conferencing, tele-immersive virtual reality, and Internet games. The dense-wavelength division multiplexing (DWDM) networks have been widely accepted as a promising approach to meet the ever-increasing bandwidth demands of Internet users, especially in next generation Internet backbone networks for nation-wide or global coverage. A major challenge in the next generation Internet backbone networks based on DWDM technologies is the resolution of the multicasting RWA (Routing and Wavelength Assignment) problem; given a set of wavelengths in the DWDM network, we set up light-paths by routing and assigning a wavelength for each connection so that the multicast connections are set-upped as many as possible. Finding such optimal multicast connections has been proven to be Non-deterministic Polynomial-time-complete. In this paper, we suggest a new heuristic multicast routing and wavelength assignment method for multicast sessions called DVS-PMIPMR (Differentiated Virtual Source-based Priority Minimum Interference Path Multicast Routing algorithm). We measured the performance of the proposed algorithm in terms of number of wavelength and wavelength channel. The simulation results demonstrate that DVS-PMIPMR algorithm is superior to previous multicast routing algorithms.
Over the past decade, the improvement of communications technologies and the rapid spread of www (World Wide Web) have brought on the exponential growth of users using Internet and real time multimedia multicast services like video conferencing, tele-immersive virtual reality, and Internet games. The dense-wavelength division multiplexing (DWDM) networks have been widely accepted as a promising approach to meet the ever-increasing bandwidth demands of Internet users, especially in next generation Internet backbone networks for nation-wide or global coverage. A major challenge in the next generation Internet backbone networks based on DWDM technologies is the resolution of the multicasting RWA (Routing and Wavelength Assignment) problem; given a set of wavelengths in the DWDM network, we set up light-paths by routing and assigning a wavelength for each connection so that the multicast connections are set-upped as many as possible. Finding such optimal multicast connections has been proven to be Non-deterministic Polynomial-time-complete. In this paper, we suggest a new heuristic multicast routing and wavelength assignment method for multicast sessions called DVS-PMIPMR (Differentiated Virtual Source-based Priority Minimum Interference Path Multicast Routing algorithm). We measured the performance of the proposed algorithm in terms of number of wavelength and wavelength channel. The simulation results demonstrate that DVS-PMIPMR algorithm is superior to previous multicast routing algorithms.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 DWDM 기술에 기반한 차세대 광인터넷 백본 전달망 구간에세PTV, 화상회의, 가상증감 현실, 인터넷 게임 등 실시간 멀티미디어 멀티캐스트 서비스의 급격한 증가에 따른 멀티캐스트 RWA문제를 해결하기 위해 DVS-PMIPMR (Differe entiated Virtual Source-based Priority Minimum Interference Path Multicast Routing) 알고리즘을 제안하였다.
본 논문은 IPTV, 화상회의, 가상 증감 현실, 인터넷 게임 등 실시간 멀티미디어 멀티캐스트 서비스의 급격한 증가에 따른 멀티캐스트 RWA문제에 대한 것으로, 주어진 파장 수 환경에서 최대한 많은 수의 멀티캐스트 연결을 달성하는 문제를 좀 더 효과적인 방법으로 해결하는 방법을 제안한다. 기존 연구 결과들을 분석해보면, 멀티캐스트RWA 문제는 파장 할당기법보다 라우팅 방식의 선택에서 큰 성능 차이를 보이는데, 본 연구에서는 파장 할당 방법으로 FF (First-Fit)방법을 사용하고, 이에 대한 효율적인 라우팅 방법을 제안한다[13].
본 논문의 저자들은 데이터의 중복 전송으로 인한 네트워크의 대역폭의 낭비 방지 및 네트워크 사용효율의 극대화를 위해 멀티캐스트 기반에서 2가지 RWA 방법을 제안하였다[7, 8].
가설 설정
그림 5에서 미래의 잠재적 연결 요청을 P1=(S1, Dll/ D12), P2=(S2, D21), P3=(S3, D31) 3개로 가정하고, 파장의 연속 제약성을 만족하는 두 DVS 노드 간의 모든 경로인 세그먼트를 S1=(DVS1, Nl, N2, DVS2), S2=(DVS1, N3, N4, N5, DVS2), S3=(DVS1, N6, N7, N8, DVS2) 3개로 가정한다[10, 18].
네트워크의 각 링크는 30개의 파장 수 (채널 수)를 가질 수 있다고 가정한다. 또한 멀티캐스트 서비스에 참여한 소스 노드와 목적지 노드들의 개 수를 나타내는 그룹 크기(GS: Group Size)는 각각의 모델에 대해 03과 0.
의미 한다. 또한 각 VS 노드는 파장 변환율을 고려하여 차등화된 VS(DVS: Differentiated VS) 노드를 적용한 것이며, 오각형으로 나타낸 DaC 노드를 제외한 나머지 노드들은 분할 노드라 가정한다.
네트워크의 각 링크는 30개의 파장 수 (채널 수)를 가질 수 있다고 가정한다. 또한 멀티캐스트 서비스에 참여한 소스 노드와 목적지 노드들의 개 수를 나타내는 그룹 크기(GS: Group Size)는 각각의 모델에 대해 03과 0.4로 설정하였고, 소스 노드에 따른 목적지 노드들의 위치는 동일한 분산 네트워크와 그렇지 않은 분산 네트워크에 균일하게 분포한다고 가정한다.
제안 방법
해결하는 방법을 제안한다. 기존 연구 결과들을 분석해보면, 멀티캐스트RWA 문제는 파장 할당기법보다 라우팅 방식의 선택에서 큰 성능 차이를 보이는데, 본 연구에서는 파장 할당 방법으로 FF (First-Fit)방법을 사용하고, 이에 대한 효율적인 라우팅 방법을 제안한다[13].
따라서 이를 개선하기 위해 파장 변환율에 따라 차등화된 능력을 가지는 VS 노드를 활용하고, 각 세그먼트 구성 노드들의 능력치에 따른 우선순위를 고려함으로써, 미래의 잠재적 연결 요청에 대한 혼잡을최소화시키는 VS-rooted 기반의 멀티캐스트 라우팅 알고리즘(DVS-PMIPMR: Differentiated Virtual Source-based Priority Minimum Interference Path Multicast Routing algorithm)을 제안한다. 제안된 알고리즘은 파장 및 채널 사용 측면과 비용 면의 효율성을 제고할 수 있다.
그리고 각 노드가 제공하는 기능(분할, 변환 등)에 따라 우선 순위를 부여하여 홉 수가 같은 노드가 여러 개 존재할 경우, 노드 선택 시 우선순위를 고려하여 경로를 설정한다. 또한 미래의 잠재적인 서비스 요청에 의한 간섭을 최소화함으로써 최저 비용의 광 자원으로 최대의 광 경로를 제공하는 DWDM 기반 최적의 멀티캐스트 라우팅 및 파장 할당 알고리즘을 제안한다.
본 연구에서는 VS-rooted 접근 방식을 기반으로 하여 노드 배치의 복잡성을 줄이고, 기존의 PMIPMR 알고리즘을 응용하여 각 노드를 광 파장 분할 및 변환 기능을 갖는 VS노드와 파장 분할 기능만을 하는 분할 노드, 분할 및 변환 기능이 없는 DaC(Drop and Continue) 노드로 구분한다. 그리고 각 노드가 제공하는 기능(분할, 변환 등)에 따라 우선 순위를 부여하여 홉 수가 같은 노드가 여러 개 존재할 경우, 노드 선택 시 우선순위를 고려하여 경로를 설정한다.
제안된 알고리즘은 가상소스를 기반으로 주어진 파장 수 환경에서 최대한 많은 수의 멀티캐스트 연결을 달성하며, 또한 노드의 능력에 따른 차등화로 우선 순위를 적용하여 휴리스틱하게 멀티캐스트 라우팅 경로를 효율적으로 선정하는 방법이다.
해당 네트워크 모델의 시뮬레이션 환경은 14-노드 토폴로지의 경우, 노드 4, 10, 11를 DVS 노드로 하고 노드 6, 9, 14를 DaC 노드로 설정하였으며, 24- 노드 토폴로지의 경우에는 노드 7, 9, 11, 16, 17을 DVS 노드로, 노드 6, 12, 14, 15, 19를 DaC 노드로 설정하였다. 네트워크의 각 링크는 30개의 파장 수 (채널 수)를 가질 수 있다고 가정한다.
데이터처리
제안된 DVS-PMIPMR 알고리즘의 효율성 검증을 위해, 그림 7과 같이 NSFnet(National Science Foundation Network) 인, 14개의 노드와 19개의 광 링크로 이루어진 14-노드 토폴로지 네트워크 모델과 그림 8과 같이 24개의 노드와 42개의 광 링크로 구성된 24-노드 토폴로지 네트워크 모델을 대상으로 Matlab을 활용하여 시뮬레이션 및 성능평가 하였다.
성능/효과
각 가중치들의 중요도를 고려할 때, 세그먼트의 노드 우선순위가 가장 높으나 잔여 파장 수가 적은, 즉 파장 이용률이 높은 경로의 경우 해당 경로보다 우선순위가 낮더라도 잔여 파장 수가 좀 더 많은 경로로 우회하는 것이 파장 사용 즉면에서 더 효율적이다. 즉, 파장 이용률이 노드 우선순위 가중치보다 더 중요한 요소이다.
9 및 그림 10과 같다. 같은 GS를 가지는 조건에서 제안된 DVS -PMIPMIR알고리즘이 기존의 VS- MIPMR 알고리즘에 비해 최대 요구되는 파장 수 측면에서, 14-노드 토폴로지의 경우 0.87%(GS: 0.3)와 0.84%(GS: 0.4)의 거의 비슷한 수치의 개선을 보였으며, 24-노드 토폴로지 의 경우 25%(GS: 0.3) 및 29.28 %(GS: 0.4)가 개선되는 결과가 나타났다.
결과적으로 식 (6)과 같이 노드 우선순위 가중치와 세그먼트의 잠재적인 혼잡도를 고려한 각 세그먼트의 총 가중치 所(SQ 값을 최소화하는 방법으로 RWA 문제를 해결하는 것으로 귀착된다.
결과적으로 제안된 DVS -PMIPMIR알고리즘은기존의 VS-MIPMR 알고리즘에 비해 멀티캐스트 세션 요청에 따른 최대 파장 수 측면에서 0.85%(L4-노드 토폴로지)와 27.14%(24-노드 토폴로지)의 개선을 보이며, 전체 채널 수 측면에서 22.87%(14-노드 토폴로지) 및 13.18%(24-노드 토폴로지)의 개선을 달성하였다.
그러나 망 상황에 따라 세 번째 멀티캐스트 세션 요청 P3도 세그먼트 S1 을 선택할 경우, 세그먼트 S1에 트래픽이 집중되고, 이로 인해 차단 확률이 증가한다. 그러므로 세그먼트 S1 보다는 홉 수가 많으나, 세그먼트 S2보다 노드 우선순위가 높고 미래의 다른 멀티캐스트 세션 요청에 대해 최소한의 영향을 미치는 세그먼트 S3을 선택하는 것이 더 효율적이다.
노드 수가 상대적으로 적은 14-노드 토폴로지에서의 개선율은 GS값에 관계없이 거의 같으나, 더 많은 수의 노드로 구성된 24-노드 토폴로지의 경우에는 14-노드 토폴로지보다 높은 개선율을 가지며, 또한 GS값이 클수록 더 큰 개선을 보였다. 즉, 네트워크의 규모 및 GS 값이 클수록 파장 사용 측면의 더 높은 개선을 달성하였다.
요청을. 달성하기우1해, 기존의 VSeMIPMR 방식에 비해 0.85%(14 노드 토폴로지의 평균 개 선율)와 27.14% (24-노드 토폴로지의 평균 개선율)의 필요 파장 수 감소와 22.87 %(14-노드 토폴로지의 평균 개선율) 및 13.18%(24- 노드 토폴로지의 평균 개선율)의 전체 사용 채널 수감 소로 트래픽 집중으로 인한 연결 블로킹 확률이 크게 감소됨을 시뮬레이션 결과로 증명되었다.
본 시뮬레이션에 대한 결과 분석 및 평가는 멀티캐스트 세션 요청에 따른 최대 파장 수와 전체 채널 수 측면에서, 기존의 VS-rooted 접근 방법인V* NHPMR 알고리즘과 비교하여 성능이 우수함을 입증한다.
본 연구의 결과는 하이퍼 광대역 서비스, 원격회의 및 협업, 원격 진료, 원격교육, 사물정보통신, 스마트 그리드 서비스, IP-USN 서비스, IPTV, VOIP 등의 하이퍼 광대역 멀티캐스트 서비스를 DWDM 전달망을 거쳐 효과적으로 제공하기 위해 효율적인 멀티캐스트 셰션 구성에 적용이 가능하다.
제안된 알고리즘은 파장 및 채널 사용 측면과 비용 면의 효율성을 제고할 수 있다.
파장의 채널 수를 도식화한 것이다. 제안된 알고리즘이 기존의 VS-MIPMR 알고리즘에 비해 채널사용 측면어}서, 노드 토폴로지의 경우 2261% (GS: 0.3)와23.14%(GS: 0.4)의 개선율을 보였으며, 24-노드 토폴로지의 경우 12.59%(GS: 0.3) 및 19.2% (GS: 0.4)가 개선되었다.
GS값이 클수록 더 큰 개선을 보였다. 즉, 네트워크의 규모 및 GS 값이 클수록 파장 사용 측면의 더 높은 개선을 달성하였다.
즉, 전체 채널 사용 측면에서 DVS-PMIPMR 알고리즘은 최대 파장 수 측면에서와 마찬가지로, 같은 토폴로지 모델에서 GS 값이 증가할수록 더 높은 개선율을 보였다.
최종적으로 멀티캐스트 세션 요청에 따른 예비 세그먼트 중 각각의 총 가중치가 가장 작은 세그먼트를 선택함으로써 노드 우선순위 및 미래의 잠재적 혼잡을 고려한 최적의 세그먼트 경로 설정이 가능하다.
참고문헌 (18)
H. Zang, Jason P. Jue, and B. Mukheriee, "A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks," Optical Networks Mag., Vol.1, pp.47-60, 2000.
A. Zyane, W. Pierre, and Z. Guennoun, "A New Approach for Routing and Wavelength Assignment for Permanent and Reliable Wavelength Paths in Wide All-optical WDM Networks," Photonic Network Communications, Vol.15, No.1, pp.77-82, 2008.
Z. Na, S. Haijin, and Z. Naifu, "Ant colony optimization for dynamic RWA in WDM networks with partial wavelength conversion," Photonic Network Communications, Vol.11, No.2, pp.229-236, 2006.
E. Calle, A. Urra, J. L. Marzo, G. S. Kuo, and H. B. Guo, "Minimum Iinterference Routing with Fast Protection," IEEE Communications Magazine, pp.104-111, 2006.
L. Du, X. H. Bi, and X. J. Wang, "A Dynamic RWA Algorithm for Optical Networks with Wavelength Conversion Capacity," IEEE 2010 First International Conference on Pervasive Computing Signal Processing and Applications (PCSPA), pp.197, 2010.
Banerjee D. and Mukherjee B., "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, 1996.
N. Sreenath, K. Satheesh, G. Mohan, and C. S. R. Murthy, "Virtual source based multicast routing in WDM optical networks," Proc. of IEEE ICON 2000, pp.385-389, 2000.
C. Siva Ram Murthy and Mohan Gurusamy, "WDM OPTICAL NETWORKS: Concepts, Design, and Algorithms," Published by Prentice Hall PTR. ISBN: 0130606375 Published: Nov. 26, 2001. Copyright 2000.
Jun Song, Hung Keng Pung, and L. Jacob, "A multi-constrained distributed QoS routing algorithm," ICON 2000 Proceedings, IEEE International Conference, pp.165-171, 2000.
김성운, 박선영, "IP/DWDM 기반 차세대 광 인터넷 망에서 가상 소스와 플러딩에 기초한 QoS 제공 유니캐스트 및 멀티캐스트 라우팅 방법 연구," 한국멀티미디어학회, 제14권, 제1호, pp. 33-43, 2011년 1월
J. G. Hwang, Jae-Il Jung, Yong-Jin Park, Jung-Hyun Bae, et al., "A RWA Algorithm for Differentiated Services with QoS Guarantees in the Next Generation Internet based on DWDM Networks," Photonic Network Communications, Vol.8, No.3, pp.319-334, 2004.
N. Sreenath, N. Krishna Mohan Reddy, G. Mohan, and C. S. R. Murthy, "Virtual Source Based Tree: A New approach for WDM Optical Multicasting," Proc. Of IEEE Workshop on High Performance Switching and Routing, 2001.
Xijun Zhang, John Y. Wei, and Chunming Qiao "Constrained multicast routing in WDM networks with sparse light splitting," IEEE/ OSA Journal of Lightwave Technology, Vol.18, No.12, pp.1917-1927, 2000.
L. Li and A. K. Somani, "Dynamic Wavelength Routing Using Congestion and Neighborhood Information," IEEE/ACM Transactions on Networking, Vol.7, No.5, pp.779-786, 1999.
N. Sreenath, N. Krishna Mohan Reddy, G. Mohan, and C. S. R. Murthy, "Virtual source based multicast routing in WDM networks with sparse light splitting," Proc. of 2001 IEEE Workshop on High Performance Switching and Routing, pp.141-145, 2001.
Hui Zang, Jason P. Jue, and Biswanath Mukherjee, "A Review of Routing and Wavelength Assignment Approaches for Wavelength Routed Optical WDM Networks," Optical Networks Magazine, Vol.1, No.1, pp. 47-60, 2000.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.