[논문]정책 기울기 값 강화학습을 이용한 적응적인 QoS 라우팅 기법 연구

한정수

doi:10.9708/jksci.2011.16.2.093

정책 기울기 값 강화학습을 이용한 적응적인 QoS 라우팅 기법 연구
A Study of Adaptive QoS Routing scheme using Policy-gradient Reinforcement Learning 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.16 no.2, 2011년, pp.93 - 99

초록
AI-Helper

본 논문에서는 강화학습(RL : Reinforcement Learning) 환경 하에서 정책 기울기 값 기법을 사용하는 적응적인 QoS 라우팅 기법을 제안하였다. 이 기법은 기존의 강화학습 환경 하에 제공하는 기법에 비해 기대 보상값의 기울기 값을 정책에 반영함으로써 빠른 네트워크 환경을 학습함으로써 보다 우수한 라우팅 성공률을 제공할 수 있는 기법이다. 이를 검증하기 위해 기존의 기법들과 비교 검증함으로써 그 우수성을 확인하였다.

Abstract ▼ AI-Helper

In this paper, we propose a policy-gradient routing scheme under Reinforcement Learning that can be used adaptive QoS routing. A policy-gradient RL routing can provide fast learning of network environments as using optimal policy adapted average estimate rewards gradient values. This technique shows that fast of learning network environments results in high success rate of routing. For prove it, we simulate and compare with three different schemes.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문은 네트워크 상의 전체 상태정보에 대한 사전 지식 없이 지역적으로 라우팅할 수 있는 새로운 라우팅 기법을 제안하였다. 제안된 라우팅 기법은 강화학습 환경 하에서 기대 보상값에 대한 기울기 값을 정책에 반영하는 정책 기울기 값 강화학습 라우팅 기법을 통해 네트워크 상황을 보다 빠르고 정확하게 그 때 그 때 적응할 수 있는 적응적 라우팅 기법을 함께 제안하였다.
본 절에서는 논문에서 제안하는 정책 기울기 값 강화학습 기법을 사용한 QoS 라우팅 기법에 대한 성능을 알아보고자 한다. 이 기법은 네트워크 환경에 대한 정보를 빠르게 획득하고 이를 라우팅 정책에 적용함으로써 정확한 라우팅을 제공할 수 있다.
요청에 대한 연결 결과에 따라, 노드 s상에서 s′로의 라우팅 정보를 갱신하는 것이 필요하다. 이는 앞서 언급한 바와 같이 기대 보상값에 대한 근사값들의 편차를 줄임으로써 빠른 학습 즉, 빠른 라우팅 정보갱신을 이루고자 한다. 이는 결과적으로 최적화 정책 즉, Q ^π(s,a)에 적용되어 라우팅 경로 선택시 결정적 역할을 하게 된다.
이것은 값 함수 접근방법을 사용하는 알고리즘의 정확성에 심각한 문제를 발생시키게 된다. 이에 본 논문에서는 정책(행동 선택)을 위해 값 함수를 근사화하는 대신 기대 보상값의 기울기 값을 정책에 적용함으로써 근사화하는 방법인 정책 기울기 값 강화학습(policy-gradient RL) 기법을 사용하고자 한다. 이 기법에서는 정책 파라미터(Θ)가 정책에 대한 보상값(ρ), 즉 기대 보상값에 대한 기울기 값에 비례하여 갱신될 수 있으며 #로 표현할 수 있다는 것이다.

가설 설정

먼저 모든 회선은 무방향성이고, 각 방향으로 똑같은 C unit의 대역폭을 갖는다. 네트워크에 도착한 연결 요청은1 unit 대역폭을 요구한다고 가정하자. 연결 요청(평균 도착율)은 소스 노드에 k를 갖는 포아송 프로세스를 따르며, 목적지는 소스 노드를 제외한 모든 노드로부터 랜덤하게 선택된다.

제안 방법

제안된 라우팅 기법은 강화학습 환경 하에서 기대 보상값에 대한 기울기 값을 정책에 반영하는 정책 기울기 값 강화학습 라우팅 기법을 통해 네트워크 상황을 보다 빠르고 정확하게 그 때 그 때 적응할 수 있는 적응적 라우팅 기법을 함께 제안하였다. 또한, 다중경로 탐색을 위해 SEMA 알고리즘을 제안했다.
이렇게 강화학습 환경과 네트워크 환경을 연결하여 성능을 분석한 노력들은 [3][5]들에서 잘볼 수 있다. 마지막으로 논문에서 제시한 기법을 시뮬레이션을 통해 그 우수성을 검증하고자 한다.
이 기법은 네트워크 환경에 대한 정보를 빠르게 획득하고 이를 라우팅 정책에 적용함으로써 정확한 라우팅을 제공할 수 있다. 이를 검증하기 위해 기존의 다양한 기법들과 네트워크부하에 따른 라우팅 성공률 즉, 서비스 성공률을 네트워크 부하와 시뮬레이션 시간으로 비교하여 살펴보기로 한다. 특히, 여기서 비교하는 기법들은 본 논문에서 제안하는 policy-gradient RL routing과 [1]와 [5]에서 제시한 기법들인 RL 기법을 이용한 TD Routing(Temporal Difference routing) 기법과, 앞서 서론에서 언급한 psr 기반의 Localized QoS Routing 기법이다.
이제까지 강화학습과 POMDP 연구 모두가 행동 선택에 있어서 측정된 값을 기반으로 한 ‘greedy' 방식의 값 함수 (value function) 접근방법을 사용했다.
정책 기울기 값 강화학습 라우팅 모델에서 사용할 다중 경로에 대해 본 논문에서는 S.Banerjee가 제안한 SSP(Single-Sink Program) 알고리즘[8]을 변경한 SEMA 알고리즘을 제안한다. SEMA 알고리즘은 Dijkstra의 최단 거리 알고리즘을 반복적으로 사용하여 송신지에서 목적지까지의 최소 가중치를 갖는 여러 개의 edge-disjoint 경로들을 찾는 것이다.
본 논문은 네트워크 상의 전체 상태정보에 대한 사전 지식 없이 지역적으로 라우팅할 수 있는 새로운 라우팅 기법을 제안하였다. 제안된 라우팅 기법은 강화학습 환경 하에서 기대 보상값에 대한 기울기 값을 정책에 반영하는 정책 기울기 값 강화학습 라우팅 기법을 통해 네트워크 상황을 보다 빠르고 정확하게 그 때 그 때 적응할 수 있는 적응적 라우팅 기법을 함께 제안하였다. 또한, 다중경로 탐색을 위해 SEMA 알고리즘을 제안했다.

데이터처리

또한, 본 논문에서 제안한 기법을 검증하기 위해 세 가지 기법들을 비교 검증하였는데, 각 기법들의 특성에 맞는 결과를 도출할 수 있었다. 즉, psr routing 기법은 최적화 정책을 도출하기 위한 시간적인 문제점을, TD routing은 단순한 보상값을 토대로 라우팅 결정을 하여 그 성능 면에서 제안하는 기법보다 낮은 성능을 보여주고 있다.

이론/모형

또한 연결 요청을 전송할 사용 가능한 경로는 위에서 살펴본 다중 경로 찾기 알고리즘(SEMA)을 통해 주 경로(primary path)와 보조 경로(alternative path)들로 분류하여 사용한다. 마지막으로 라우팅 경로 선택은 greedy-기법을 적용 하는 것을 원칙으로 한다.
또한 연결 요청을 전송할 사용 가능한 경로는 위에서 살펴본 다중 경로 찾기 알고리즘(SEMA)을 통해 주 경로(primary path)와 보조 경로(alternative path)들로 분류하여 사용한다. 마지막으로 라우팅 경로 선택은 greedy-기법을 적용 하는 것을 원칙으로 한다.
이를 검증하기 위해 기존의 다양한 기법들과 네트워크부하에 따른 라우팅 성공률 즉, 서비스 성공률을 네트워크 부하와 시뮬레이션 시간으로 비교하여 살펴보기로 한다. 특히, 여기서 비교하는 기법들은 본 논문에서 제안하는 policy-gradient RL routing과 [1]와 [5]에서 제시한 기법들인 RL 기법을 이용한 TD Routing(Temporal Difference routing) 기법과, 앞서 서론에서 언급한 psr 기반의 Localized QoS Routing 기법이다.

성능/효과

강화학습 기법을 사용하는 라우팅 기법은 각 노드에서 네트워크에 대한 전체 상태정보를 알 수 없다는 지역적 라우팅 환경 하에서 적용하기 위한 기법으로 사용되고 있으며, 강화학습 환경하에서 정책 기울기 값 강화학습 라우팅 기법은 경로 선택으로 주어지는 보상값을 토대로 기대 보상값을 계산하고 이를 정책에 반영함으로써 보다 빠른 판단을 할 수 있게 도와준다. 더욱이 기대 보상값의 기울기 값을 반영함으로써 보다 최적화된 라우팅 정책 값을 도출할 수 있으며, 이를 통해 우수한 성능을 검증할 수 있었다.
하지만, TD routing기법과 policy-gradient RL routing 기법은 미리 정해진 경로를 통해 자신만의 노드에서 결정되어진 값을 토대로 라우팅 되기 때문에 비교적 좋은 성능을 보이고 있다. 더욱이, 본 논문에서 제안하는 policy-gradient RL routing 기법은 네트워크 트래픽 상황에 대한 빠른 판단과 이를 라우팅 정책에 적용하기 때문에 제일 좋은 성능을 보이고 있다. 특히, 부하값이 0.
하지만, 최적화된 정책은 주로 특정 확률을 갖는 행동들을 찾는 경우가 많기 때문에 결정적인 정책을 찾는 방법은 최적의 솔루션이 될 수 없다[6]. 두 번째, 행동에 대한 측정된 값이 작으면 선택되어질 수도 아닐 수도 있다는 것이다. 이것은 값 함수 접근방법을 사용하는 알고리즘의 정확성에 심각한 문제를 발생시키게 된다.
이 결과는 세가지 기법이 얼마나 빠르게 네트워크 상황을 판단하여 라우팅하는지에 대한 성능을 보여주고 있다. 즉, 시뮬레이션 시간이 길어질 수록 psr기법보다는 RL 기법을 사용하고 있는 TD routing 기법과 policy-gradient RL routing 기법이 더 나은 성능을 보여주고 있다. 특히, 평균 기대 보상값을 통한 정책 값을 결정하는 policy-gradient RL routing 기법이 단순히 보상값을 토대로 정책을 결정하는 TD routing 기법에 비해 보다 우수한 성능을 보이고 있음을 알 수 있었다.
더욱이, 본 논문에서 제안하는 policy-gradient RL routing 기법은 네트워크 트래픽 상황에 대한 빠른 판단과 이를 라우팅 정책에 적용하기 때문에 제일 좋은 성능을 보이고 있다. 특히, 부하값이 0.36 ~ 0.56 사이에 가장 좋은 성능을 보여주고 있는데, 이는 다른 기법에 비해 policy-gradient RL routing 기법이 갖는 장점(네트워크 상황에 대한 빠른 수렴)으로 인해 더 좋은 성능을 보이고 있는 것으로 파악된다. 세 가지 기법 모두 부하가 0.
즉, psr routing 기법은 최적화 정책을 도출하기 위한 시간적인 문제점을, TD routing은 단순한 보상값을 토대로 라우팅 결정을 하여 그 성능 면에서 제안하는 기법보다 낮은 성능을 보여주고 있다. 특히, 시뮬레이션 시간이 길어짐에 따라 네트워크 환경 변화를 빠르게 판단하는 policy-gradient RL routing기법이 다른 기법보다 우수함을 볼 수 있었다.
즉, 시뮬레이션 시간이 길어질 수록 psr기법보다는 RL 기법을 사용하고 있는 TD routing 기법과 policy-gradient RL routing 기법이 더 나은 성능을 보여주고 있다. 특히, 평균 기대 보상값을 통한 정책 값을 결정하는 policy-gradient RL routing 기법이 단순히 보상값을 토대로 정책을 결정하는 TD routing 기법에 비해 보다 우수한 성능을 보이고 있음을 알 수 있었다. 특히 25분이 경과되는 시점에서는 다른 기법들에 비해 우수한 성능을 보이고 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	MDP는 어떤 방법인가?	MDP(Markov Decision Process)는 복잡한 POMDP 문제를 해결하기 위한 기초를 제공한다. MDP는 에이전트(agent)와 환경 (environment)과의 상호관계와 이에 따른 강화 값(reinforcement value)을 통하여 에이전트의 행동을 개선해 나가는 방법으로서 환경에대한정확한사전지식없이학습및적응성을보장할수있는방법이다. 일반적으로 MDP는 각 시간 t∈{0,1,2,.
	정책 기울기 값 기법을 사용하는 적응적인 QoS 라우팅 기법이란?	본 논문에서는 강화학습(RL : Reinforcement Learning) 환경 하에서 정책 기울기 값 기법을 사용하는 적응적인 QoS 라우팅 기법을 제안하였다. 이 기법은 기존의 강화학습 환경 하에 제공하는 기법에 비해 기대 보상값의 기울기 값을 정책에 반영함으로써 빠른 네트워크 환경을 학습함으로써 보다 우수한 라우팅 성공률을 제공할 수 있는 기법이다. 이를 검증하기 위해 기존의 기법들과 비교 검증함으로써 그 우수성을 확인하였다.
	MDP는 무엇을 제공하는가?	MDP(Markov Decision Process)는 복잡한 POMDP 문제를 해결하기 위한 기초를 제공한다. MDP는 에이전트(agent)와 환경 (environment)과의 상호관계와 이에 따른 강화 값(reinforcement value)을 통하여 에이전트의 행동을 개선해 나가는 방법으로서 환경에대한정확한사전지식없이학습및적응성을보장할수있는방법이다.

참고문헌 (8)

Srihari Nelakuditi, Zhi-Li Zhang and Rose P.Tsang, "Adaptive Proportional Routing: A Localized QoS Routing Approach," In IEEE Infocom, April 2000.
Y.Liu, C.K. Tham and TCK. Hui, "MAPS: A Localized and Distributed Adaptive Path Selection in MPLS Networks," in Proceedings of 2003 IEEE Workshop on High Performance Switching and Routing, Torino, Italy, pp. 24-28, June 2003.
Yvn Tpac Valdivia, Marley M, Vellasco, Marco A. Pacheco "An Adaptive Network Routing Strategy with Temporal Differences," Inteligencia Artificial, Revista Lberoamericana de Inteligencia Aritificial, No. 12, pp. 85-91, 2001.
Jeongsoo Han, "Network-Adaptive QoS Routing Using Local Information," APNOMS 2006, LNCS 4238, pp. 190-199, 2006.
Leslie Pack Kaelbling, Michael L. Littman, Andrew W.Moore, "Reinforcement Learning:A Survey," Journal of Artificial Intelligence Research 4, pp. 237-285, 1996

상세보기
Richard S. Sutton etc, "Policy Gradient Methods for Reinforcement Learning with Function Approximation," Advances in Neural Information Processing System, pp. 1057-1063, MIT Press 2000.
Gregory Z. Grudic, Vijay Kumar, "Using Policy Gradient Reinforcement Learning on Automous Robot Controllers," IROS03, Las Vagas, US, October, 2003.
S.Banerjee, R.K. Ghosh and A.P.K Reddy, "Parallel algorithm for shortest pairs of edge-disjoint paths," Journal Parallel Distrib. Comput. pp. 165-171, 1996.

저자의 다른 논문 :

표제어: 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

연합인증

정책 기울기 값 강화학습을 이용한 적응적인 QoS 라우팅 기법 연구
A Study of Adaptive QoS Routing scheme using Policy-gradient Reinforcement Learning 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

이론/모형

성능/효과

질의응답

참고문헌 (8)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

정책 기울기 값 강화학습을 이용한 적응적인 QoS 라우팅 기법 연구 A Study of Adaptive QoS Routing scheme using Policy-gradient Reinforcement Learning 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

이론/모형

성능/효과

질의응답

참고문헌 (8)

이 논문을 인용한 문헌

저자의 다른 논문 :

한정수 (5)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

정책 기울기 값 강화학습을 이용한 적응적인 QoS 라우팅 기법 연구
A Study of Adaptive QoS Routing scheme using Policy-gradient Reinforcement Learning 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper