[논문]Deep Q 학습 기반의 다중경로 시스템 경로 선택 알고리즘

정병창; 박혜숙

doi:10.6109/jkiice.2021.25.1.50

Deep Q 학습 기반의 다중경로 시스템 경로 선택 알고리즘
Path selection algorithm for multi-path system based on deep Q learning 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.25 no.1, 2021년, pp.50 - 55

정병창 (Electronics and Telecommunications Research Institute) , 박혜숙 (Electronics and Telecommunications Research Institute)

초록
AI-Helper

다중경로 시스템은 유선망, LTE망, 위성망 등 다양한 망을 동시에 활용하여 데이터를 전송하는 시스템으로, 통신망의 전송속도, 신뢰도, 보안성 등을 높이기 위해 제안되었다. 본 논문에서는 이 시스템에서 각 망의 지연시간을 보상으로 하는 강화학습 기반 경로 선택 방안을 제안하고자 한다. 기존의 강화학습 모델과는 다르게, deep Q 학습을 이용하여 망의 변화하는 환경에 즉각적으로 대응하도록 알고리즘을 설계하였다. 네트워크 환경에서는 보상 정보를 일정 지연시간이 지나야 얻을 수 있으므로 이를 보정하는 방안 또한 함께 제안하였다. 성능을 평가하기 위해, 분산 데이터베이스와 텐서플로우 모듈 등을 포함한 테스트베드 학습 서버를 개발하였다. 시뮬레이션 결과, 제안 알고리즘이 RTT 감소 측면에서 최저 지연시간을 선택하는 방안보다 20% 가량 좋은 성능을 가지는 것을 확인하였다.

Abstract ▼ AI-Helper

Multi-path system is a system in which utilizes various networks simultaneously. It is expected that multi-path system can enhance communication speed, reliability, security of network. In this paper, we focus on path selection in multi-path system. To select optimal path, we propose deep reinforcement learning algorithm which is rewarded by the round-trip-time (RTT) of each networks. Unlike multi-armed bandit model, deep Q learning is applied to consider rapidly changing situations. Due to the delay of RTT data, we also suggest compensation algorithm of the delayed reward. Moreover, we implement testbed learning server to evaluate the performance of proposed algorithm. The learning server contains distributed database and tensorflow module to efficiently operate deep learning algorithm. By means of simulation, we showed that the proposed algorithm has better performance than lowest RTT about 20%.

주제어

표/그림 (8)

그림 Fig. 1 Example of multi-path system
그림 Fig. 2 Typical Q learning algorithm
그림 Fig. 3 Deep Q learning algorithm
그림 Fig. 4 Block diagram for proposed learning algorithm
그림 Fig. 5 Design of learning server
그림 Fig. 6 Example operation of distributed database
그림 Fig. 7 Average RTT of comparable schemes
그림 Fig. 8 RTT of particular network in each iteration

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 이러한 다중경로 시스템에서의 경로 선택 문제를 강화학습을 이용하여 풀고자 한다. Ⅱ장에서는 강화학습에 대하여 간단히 대해서 소개하고, Ⅲ장에서는 논문의 제안 시스템에 강화학습 기법을 어떻게 적용하는지에 관해 설명하고자 한다.

가설 설정

보여준다. x축은 시간으로, 1번의 iteration이 5000 번의 타임슬롯을 가진다고 가정한다. y축인 평균 지연시간은 5000번의 타임슬롯 동안 각각 망이 얻은 지연시간을 모두 합쳐 평균값으로 계산하였다.

제안 방법

이용해서 해결하였다. 강화학습에 적용할 수 있도록 지연시간 기반의 상황, 행동, 보상을 모델링하였다. 모델링 구조 상 전체 상황의 개수가 많아져 기존의 일반적인 강화학습으로는 문제를 풀기 어려우므로, 인공신경망을 이용하는 deep Q 학습 방안을 제안하였다.
모델링 구조 상 전체 상황의 개수가 많아져 기존의 일반적인 강화학습으로는 문제를 풀기 어려우므로, 인공신경망을 이용하는 deep Q 학습 방안을 제안하였다. 덧붙여 네트워크의 특성에 맞게 replay buffer, delay compensation 등의 과정을 적용하여 전체적인 알고리즘을 설계하였다. 제안하는 알고리즘의 성능 검증을 위해 학습 데이터를 수집하고, 그로부터 학습을 수행할 수 있는 학습 서버를 개발하였다.
해당 모델링에서는 4개의 개별 무선망을 고려하였으며, 기지국의 위치, pathloss 모델에 차이를 두어 특성이 달라지게 구성하였다 [9]. 덧붙여 무선의 특징 이외에도 코어망에서도 각 망의 배경 트래픽에 따라 각각의 망이 다른 service rate를 가지도록 모델링하였다. 각 망의 배경 트래픽은 무선망의 성능 변화보다긴 시간 스케일로 변화하도록 설정하였다.
마지막으로, 각각 기지국이나 게이트웨이 같은 주요 제어 정보들이 분산 데이터베이스에 저장되는 것은 비효율적이다. 따라서 이 정보들은 MariaDB 에 저장되도록 설계하였고, 이것을 python으로 가져오는 것은 happybase 라이브러리를 이용해 구현하였다. 아래 그림 6은 구성한 학습 서버 내 hbase shell 구동 예시를 보여준다.
마지막으로 인공신경망을 통해 Q 값을 예측하면, 무조건 최적의 Q 값을 고르는 것이 아니라 최적의 Q 값을 높은 확률로 고를 수 있도록 설계한다. 무조건 최적의 Q 값을 고르지 않는 이유는 학습 알고리즘 특성상 다양한 시도를 통해 다양한 경우의 Q 값을 확보하고, 특정 경로의 상황이 변하는 것에 대처하기 위함이다.
강화학습에 적용할 수 있도록 지연시간 기반의 상황, 행동, 보상을 모델링하였다. 모델링 구조 상 전체 상황의 개수가 많아져 기존의 일반적인 강화학습으로는 문제를 풀기 어려우므로, 인공신경망을 이용하는 deep Q 학습 방안을 제안하였다. 덧붙여 네트워크의 특성에 맞게 replay buffer, delay compensation 등의 과정을 적용하여 전체적인 알고리즘을 설계하였다.
본 논문에서는 다중경로 시스템의 경로 선택 문제를 강화학습을 이용해서 해결하였다. 강화학습에 적용할 수 있도록 지연시간 기반의 상황, 행동, 보상을 모델링하였다.
y축인 평균 지연시간은 5000번의 타임슬롯 동안 각각 망이 얻은 지연시간을 모두 합쳐 평균값으로 계산하였다. 비교 방안으로는 임의로 선택하는 방안(random selection)과, MPTCP 표준에서 제시한 매 순간 최소 지연시간을 선택하는 방안(lowest RTT)을 적용하였다 [10].
제안 방안에서 실제 지연시간 측정은 기지국 또는 게이트웨이 노드에서 수행되므로 범용적인 인터페이스인 REST API를 통해 지연시간을 수신하고, 데이터 용량이 커지는 상황을 고려하여 분산 데이터베이스의 일종인 HBase에 저장하도록 하였다 [8]. 제안 알고리즘에서는데이터량이 이미지나 영상만큼 크지는 않으나, 향후 네트워크 플로우 정보 등의 다른 정보를 학습 알고리즘의 입력값으로 사용할 수 있도록 분산 데이터베이스를 이용해 저장소를 구성하였다.
저장하도록 하였다 [8]. 제안 알고리즘에서는데이터량이 이미지나 영상만큼 크지는 않으나, 향후 네트워크 플로우 정보 등의 다른 정보를 학습 알고리즘의 입력값으로 사용할 수 있도록 분산 데이터베이스를 이용해 저장소를 구성하였다. REST API와 HBase client 가 Java spring framework에서 동작하는 반면 tensorflow는 python 기반으로 동작한다.
제안하는 알고리즘을 평가하기 위해 tensorflow, HBase, spring framework 등을 활용하여 제안하는 강화학습 알고리즘을 구동할 수 있는 학습 서버를 구축하였다. 학습 서버의 구성도는 아래 그림 5와 같다.
덧붙여 네트워크의 특성에 맞게 replay buffer, delay compensation 등의 과정을 적용하여 전체적인 알고리즘을 설계하였다. 제안하는 알고리즘의 성능 검증을 위해 학습 데이터를 수집하고, 그로부터 학습을 수행할 수 있는 학습 서버를 개발하였다. 이 학습 서버에서 시뮬레이션을 통해 알고리즘의 성능을 검증한 결과, 해당 알고리즘을 적용하였을 때 전체적인 평균 지연시간이 감소하고 품질이 좋지 않은 경로의 포화가 줄어든 것을 확인하였다.
5를 사용하였고, 인공신경망은 4개의 레이어로 구성하였다. 즉, 40개의 입력값으로 시작해 최종적으로 보상값 1개를 예측하는 신경망을 구현하였다.
네트워크 구조는 4개의 품질이 다른 망을 모델링하였다. 해당 모델링에서는 4개의 개별 무선망을 고려하였으며, 기지국의 위치, pathloss 모델에 차이를 두어 특성이 달라지게 구성하였다 [9]. 덧붙여 무선의 특징 이외에도 코어망에서도 각 망의 배경 트래픽에 따라 각각의 망이 다른 service rate를 가지도록 모델링하였다.

데이터처리

x축은 시간으로, 1번의 iteration이 5000 번의 타임슬롯을 가진다고 가정한다. y축인 평균 지연시간은 5000번의 타임슬롯 동안 각각 망이 얻은 지연시간을 모두 합쳐 평균값으로 계산하였다. 비교 방안으로는 임의로 선택하는 방안(random selection)과, MPTCP 표준에서 제시한 매 순간 최소 지연시간을 선택하는 방안(lowest RTT)을 적용하였다 [10].

이론/모형

본 논문에서는 경로 선택 문제를 deep Q 학습을 이용하여 풀고자 한다. 먼저 Q 학습[2]을 소개하면 다음과 같다.
강화학습이 효율적으로 이루어지기 위해서는 좋은 행동을 다수 실행하는 것(exploitation)과 변화 감지를 위해 다른 행동을 수행해보는 것(exploration)의 조화가 필요하다. 본 연구에서는 Boltzmann distribution에 따라 행동을 결정하였다 [5]. 여기서 p(a_i)는 행동 a_i를 고를 확률이고, c에 따라 최적의 Q 값을 고르는 확률 분포가 달라진다.

성능/효과

시간이 지날수록 지연시간이 늘어나서 포화하는 경우가 발생하지 않는 것을 볼 수 있다. 다시 말해, 제안 알고리즘은 지연시간을 보상으로 학습을 진행하였으므로 다중경로 네트워크의 지연시간을 최적화하는 방향으로 경로 선택을 하는 것을 확인할 수 있다.
점이다. 다시 말해서, 기존의 강화학습 시스템이 상황과 행동에 따라서 얻는 보상이 즉각적이라면, 이 시스템에서는 상황과 행동에 따라서 얻는 보상이 일정 지연시간 후에 일어난다는 뜻이다. 따라서 이를 학습 알고리즘의 입력값으로 반영할 때 이 지연시간만큼을 보정해서 학습시켜야 한다.
따라서 HBase 에서 python으로 데이터베이스를 가져오기 위해 thrift 를 이용하였다. 마지막으로, 각각 기지국이나 게이트웨이 같은 주요 제어 정보들이 분산 데이터베이스에 저장되는 것은 비효율적이다. 따라서 이 정보들은 MariaDB 에 저장되도록 설계하였고, 이것을 python으로 가져오는 것은 happybase 라이브러리를 이용해 구현하였다.
기존의 알고리즘은 시간 차이를 보정하는 부분을 반영하여도 고전적인 Q 학습만을 도입하거나, 수렴성과 효율을 위해 최단 경로만 선택지로 활용하는 등의 방식을 채택하였다. 반면, 제안 방안에서는 알고리즘을 deep network로 구성하였기 때문에 state와 action 수가 증가하더라도 알고리즘이 수렴할 확률이 높아진다.
하지만 iteration이 반복될수록, deep Q 학습 알고리즘은 어떤 망을 많이 선택할수록 지연시간이 단축되는지를 인지하게 되고, 점점 최적의 망 선택을 수행한다. 상대적으로 임의 선택방안의 성능 열화가 크기 때문에 그래프 상에서 제안 방안과 최소 지연시간 선택 방안의 차이가 두드러지게 나타나지는 못하지만, 제안 방안과 최소 지연시간 선택 방안의 RTT 차이를 비교하면 약 21% 정도 제안 방안이 우수한 것을 확인할 수 있다.
제안하는 알고리즘의 성능 검증을 위해 학습 데이터를 수집하고, 그로부터 학습을 수행할 수 있는 학습 서버를 개발하였다. 이 학습 서버에서 시뮬레이션을 통해 알고리즘의 성능을 검증한 결과, 해당 알고리즘을 적용하였을 때 전체적인 평균 지연시간이 감소하고 품질이 좋지 않은 경로의 포화가 줄어든 것을 확인하였다.

참고문헌 (10)

M. S. Kim, J. Y. Lee, and B. C. Kim, "Design of MPTCP congestion control based on BW measurement for wireless networks," Journal of the Korea Institute of Information and Communication Engineering, vol. 21, no. 6, pp. 1127-1136, Jun. 2017.

원문보기 상세보기
K. Jang, "Reinforcement learning for node-disjoint path problem in wireless ad-hoc networks," Journal of the Korea Institute of Information and Communication Engineering, vol. 23, no. 8, pp. 1011-1017, Aug. 2019.

원문보기 상세보기
S. Park, B. Lim, and H. Jung, "CNN-Based Toxic Plant Identification System," Journal of the Korea Institute of Information and Communication Engineering, vol. 24, no. 8, pp. 993-998, Aug. 2020.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, "Human-level control through deep reinforcement learning," Nature, vol. 518, pp. 529-533, Feb. 2015.
B. C. Chung and D. H. Cho, "Semidynamic cell-clustering algorithm based on reinforcement learning in cooperative transmission system," IEEE Systems Journal, vol. 12, no. 4, pp. 3853-3856, Dec. 2018.

상세보기
S. P. M. Choi and D. Y. Yeung, "Predictive Q-Routing: A Memory-based Reinforcement Learning Approach to Adaptive Traffic Control," in Proceedings of Advances in Neural Information Processing Systems, pp. 945-951, 1996.
S. Hoceini, A. Mellouk, and Y.Amirat, "K-Shortest Paths Q-Routing: A New QoS Routing Algorithm in Telecommunication Networks," in Proceedings of International Conference on Networking 2005, pp. 164-172, 2005.
Apache HBase, [Internet]. Available: https://hbase.apache.org/.
M. Series, "Guidelines for evaluation of radio interface technologies for IMT-Advanced," International Telecommunication Union (ITU), Geneva, Switzerland, Technical Report ITU-R M.2135-1, Dec. 2009.
C. Raiciu, M. Handley, and D. Wischik, "Coupled congestion control for multipath transport protocols," RFC 6356, IETF, Oct. 2011. [Internet]. Available: https://tools.ietf.org/html/rfc6356.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증