Current Issue

SDN 환경에서 라우팅 트리를 생성하는 방법으로는 스타이너 트리 문제(Steiner tree problem)를 해결하는 것과 동일하다[2][3]. 스타이너 트리 문제의 시간 복잡도는 NP-Hard이므로 다항 시간에 해결할 수 없어 TM[4]와 같은 근사 알고리즘을 이용한 다양한 연구들이 존재한다[5]. 하지만 근사 알고리즘을 이용한 방법은 계산시간이 오래 걸린다는 단점이 있다. 반면, 딥러닝을 이용한 방법은 모델을 학습하는 데 시간이 오래 걸릴 수 있다는 단점이 있지만 학습 이후에는 짧은 시간 내 결과를 도출한다는 장점이 있다. 따라서 본 논문에서는 메타 강화학습을 이용한 딥러닝 기반의 모델을 제안한다.

강화학습은 인공지능에서 매우 중요한 주제 중 하나로 그림 1과 같이 학습하는 주체인 에이전트가 주어진 환경과 상호작용을 하면서 특정 목표를 달성한다. 이때 환경에 놓여진 에이전트가 액션을 수행하면 환경은 에이전트에 액션에 대응하여 다음 상태와 보상치를 부여한다. 이와 같이 강화학습은 최적의 행동을 선택하는 방법을 스스로 학습하며 보상을 통해 학습을 이루어 낸다. 하지만 이러한 강화학습 구조는 하나의 태스크에 대해서만 학습하여 단일 태스크에 대해서만 최적이므로 만일 학습한 태스크와 조금이라도 다른 태스크가 환경으로 주어진다면 최적의 행동을 선택하지 못한다. 따라서 이러한 강화학습 방법을 통해 학습하는 방식은 가변적인 네트워크 환경에 적합하지 않다. 이에 본 논문에서는 후술하겠지만 다양한 태스크가 환경으로 주어져도 최적의 행동을 선택할 수 있는 강화학습에 메타 러닝을 적용한 메타 강화학습을 이용하여 가변적인 네트워크 환경에서도 최적의 행동을 선택할 수 있는 효율적인 방법을 제안한다.

Fig. 1. 
Reinforcement learning structure

메타 강화학습은 크게 3가지 접근방법에 따라 나뉜다. 첫 번째는 순환 정책 메타 강화학습, 두 번째는 최적화 기반 메타 강화학습, 그리고 세 번째로 컨텍스트 기반 메타 강화학습이다. 식 (1)과 같이 메타 강화학습은 기존 강화학습과 달리 내부 단계에서 각각의 태스크인 MDP M_o에 대해 태스크 적응 Φ_i = f_θ(M_o)을 수행하며 외부 단계에서는 이를 통합하여 각 태스크의 보상합에 대한 기댓값을 최대화하는 최적의 메타 파라미터 θ^*을 찾는다.

이러한 메타 강화학습은 동일한 태스크의 다양한 변종들이 존재하거나, 새로운 태스크가 주기적으로 등장하는 경우 유용하게 적용될 수 있다. 이는 유사하지만 링크 분포나 노드의 개수에 차이가 있는 가변적인 네트워크 환경에 적합하다. 본 논문은 메타 강화학습 모델 중 컨텍스트 기반 메타 강화학습 중 하나인 PEARL을 이용하여 고정되어 있지 않는 새로운 태스크인 링크 가변적인 네트워크 환경이 주어져도 최적에 가까운 멀티캐스트 라우팅 트리 생성 방법을 제안한다.

PEARL[6]은 앞서 소개한 메타 강화학습 기법 중 컨텍스트 기반 메타 강화학습 알고리즘이다. 여기서 컨텍스트란 태스크를 유추할 수 있는 일련의 상호작용 데이터를 의미하며 M_i을 경험하며 추론된다. 에이전트는 이러한 컨텍스트 정보를 활용하여 메타 정책을 업데이트하고 새로운 태스크에서의 최적 행동을 선택한다. 따라서 식 (2)[6]처럼 컨텍스트 c로부터 추론된 잠재 컨텍스트 변수 z가 정책함수의 조건부에 붙게 된다.

컨텍스트 기반 메타 강화학습의 대표적인 모델인 PEARL은 순환 정책 메타 강화학습의 대표적인 모델인 RL²[7] 와 최적화 기반 메타 강화학습의 대표적인 모델인 MAML[8]이 on-policy 기반이기 때문에 샘플 효율성이 낮고 새로운 태스크를 학습할 시 새로운 태스크의 불확실성을 구조적으로 탐색할 수 방법이 부족하다는 단점을 해결하였다. PEARL은 off-policy 기반의 메타 강화학습 알고리즘으로 Replay Buffer를 활용하여 높은 샘플 효율성을 보이며 태스크 추론을 위해 강화학습 부분과 태스크 추론 부분을 분리한 방법을 제안하였다. PEARL에서 각 태스크는 MDP로 표현하되, 상태 전이 확률과 보상함수는 알려지지 않았으므로 식 (3)[6]와 같이 태스크를 정의한다. 또한 식 (4)[6]와 같이 컨텍스트를 정의하여 수집 및 샘플링한 N개의 컨텍스트를 C1:NT (이하 c)과 같이 정의한다.

PEARL에서는 현재 태스크를 어떻게 수행해야하는 지에 대한 지식을 확률적 잠재 컨텍스트 변수 z로 묘사하며 정책을 π_θ(averts, z)로 조건화하여 태스크에 대한 행동을 적응시킨다. 이러한 확률적 잠재 컨텍스트 변수인 z를 잘 추론하기 위해선 컨텍스트 c가 주어졌을 때 posterior p(zvertc)를 추론해야 한다. 하지만 이 posterior p(zvertc)를 계산하는 것은 어렵기 때문에 Φ를 매개변수로 하는 추론 네트워크 q_Φ(zvertc)를 학습하여 posterior p(zvertc)를 근사한다. 근사하기 위해 PEARL은 생성 모델 VAE[9]의 변분적 추론 개념을 바탕으로 추론 목적 함수를 정의하였고 그 식은 식 (5)과 같다.

식 (5)[6]에서 E_T는 모든 태스크에 대해 기댓값을 취하며 Ez∼qΦzvertcΤ는 추론 네트워크 q_Φ(zvertc^T)를 이용해 컨텍스트 변수 z를 샘플링하여 이를 이용해 RT,z+βDKLqΦzvertcTpz의 값을 계산한다. 여기서 p(z)는 z에 대한 unit Gaussian으로 가정한다.

R(T, z)는 식 (2)에서 보듯 에이전트인 π_θ(averts,z)을 학습함에 따라 z를 잘 추론했는지 판단하는 목적함수가 되며 βDKLqΦzvertcTpz는 z와 c사이의 상호 정보량을 제한하는 정보 병목 현상[10]에 대한 변분적 근사(Variational approximation)로 해석한다.

PEARL에서는 추론 네트워크를 설계할 때 관련 없는 종속성을 모델링하지 않으면서 태스크와 관련된 정보에 대한 최소한의 정보를 포착할 수 있을 만큼 충분히 표현력 있도록 구성하였다. 여기서 완전히 관찰 가능한 MDP의 인코딩은 permutation invariant 해야 한다. 즉, PEARL은 MDP 모델을 알기 위해 태스크가 무엇인지 추론할 필요도 없고 가치함수를 학습하기 위해 순서를 고려할 필요없이 단지 {s_i,a_i,r_i,s'_i}와 같은 데이터만 있으면 충분히 학습할 수 있다. 이러한 관찰을 기반으로 PEARL에서는 식 (6)[6]과 같이 q_Φ(zvertc_{1 : N})를 permutation invariant 표현을 사용하여 모델링한다.

여기서 Ψ_Φ(zvertc_n)는 정규분포에서 나오는 값으로 모델링 할 수 있으며 쉽게 다루기 위해, 가우시안 인자 ΨΦzvertcn=NfΦμcn,fΦσcn로 표현할 수 있고 이로 인해 가우시안 사후 분포가 생성된다. PEARL은 이 값들을 1 부터 N 까지 다 곱하여 q_Φ(zvertc_{1 : N})를 모델링할 수 있다. 여기서 함수 f_Φ는 c_n에 대한 함수로 Φ로 매개변수화 된 신경망으로 표현되며 평균 μ와 표준편차 σ을 출력한다.

위와 같이 PEARL은 확률적 잠재 컨텍스트를 모델링함에 따라 posterior 샘플링이 가능하며 이를 통해 탐험을 효율적으로 할 수 있다는 장점을 가진다. 그 결과 PEARL은 충분히 태스크 정보를 학습했을 때 테스트 과정에서 접하는 새로운 태스크에 대해 posterior 샘플링을 통해 빠르게 태스크 정보를 추론하고 이를 학습할 수 있게 된다.

본 논문은 PEARL을 기반으로 SDN 환경에서 최적의 멀티캐스트 라우팅 트리를 생성하는 방법에 대해 제안한다. 따라서 최적의 멀티캐스트 라우팅 트리를 만들기 위해서 최소 비용의 트리를 생성한다. 이것은 출발지에서부터 목적지까지 순서에 따라 어떤 링크를 선택해야 하는지 결정하는 순차적 행동 결정 문제로 정의할 수 있고, 이러한 순차적 행동 결정 문제는 MDP(Markov Decision Process)와 같이 수학적으로 모델링할 수 있다. 본 논문에서는 표 1과 같이 태스크 별 MDP를 정의하였다.

그림 2는 예시로 만든 노드 6개의 네트워크 토폴로지 그림이다.

Fig. 2. 
Network topology schematic

그림 3은 그림 2의 네트워크 토폴로지에 대한 인접행렬, 즉 상태 정보를 행렬로 나타낸 그림이다. 만일 노드 개수가 N 개면 N × N인 인접행렬로 표현되며 이 인접행렬에는 출발지 노드 정보와 목적지 노드 정보가 같이 들어있다. 이 예시에서는 노드 개수가 6개이기 때문에 6×6인 인접행렬로 표현되었고 노드끼리 연결된 링크 정보를 나타내기 위해 현재 연결된 노드들 간 행렬값은 1로 표기하고 연결되지 않은 노드들 간 행렬값은 0으로 표기하였다. 즉 활성화된 링크는 1의 값을 가지며, 활성화되지 않는 링크는 0의 값을 가진다. 그리고 출발지 노드 정보와 목적지 노드 정보를 표기하기 위해 출발지 노드는 1로 목적지 노드는 -1로 표기하였다. 위 MDP에서 행동의 경우에는 현재 연결된 멀티캐스트 라우팅 트리에서 연결 가능한 링크 중 하나를 선택한다. 즉 활성화되어 있지 않은 링크를 선택한다. 마지막으로, 보상의 경우는 에이전트의 액션 이후, 즉 링크 선택 후 그 링크를 통해 목적지 노드 도달 여부에 따라 다르게 부여된다. 목적지 노드에 도달하였을 경우 +1, 도달하지 않았을 경우 +0을 부여한다. 또한 이 보상은 감쇠율이 적용되어 있어 여러 번 곱해질수록 0에 가까워지게 된다. 그러므로 에이전트는 누적 보상의 합을 최대로 하기 위해 최대한 적은 행동으로 에피소드를 끝내도록 학습될 것이다. 최대한 적은 행동을 통해 에피소드를 끝내는 것은 결국 최대한 적은 링크 개수로 멀티캐스트 라우팅 트리를 만드는 것이므로 이는 에이전트가 학습을 통해 최적의 멀티캐스트 라우팅 트리를 생성할 수 있음을 의미한다.

Fig. 3. 
Adjacency matrix for the network topology in Fig. 2

PEARL의 메타 트레이닝 방법에 따라 본 논문에서 제안하는 모델 학습 방법은 다음과 같다. 앞서 언급하였듯 인코더 q_Φ(zvertc)학습을 위해 사용되는 데이터가 정책을 학습하는 데 사용하는 데이터와 동일할 필요가 없다. 정책은 Off-policy 강화학습 과정에서 컨텍스트 z을 상태의 일부로 다룰 수 있으며, 탐험 과정의 확률적 요소는 인코더 q_Φ(zvertc)의 불확실성에 의해 제공된다. Actor 네트워크와 Critic 네트워크는 항상 전체 리플레이 버퍼에서 샘플링한 Off-policy 데이터로 학습된다. 여기서 인코더 q_Φ(zvertc)학습을 위해 컨텍스트 배치를 샘플링하기 위한 새로운 샘플러 S_c를 정의한다. 만일 이 S_c가 리플레이 버퍼와 동일하게 샘플링된다면 On-policy 데이터와 극단적인 분포 불일치를 보이게 될 것이다. 그러나 컨텍스트 배치는 완전히 On-policy일 필요는 없으며 최근 수집된 데이터의 버퍼에서 샘플링하여 인코더 q_Φ(zvertc)를 학습하는 중간 전략을 택한다면 Off-policy의 장점을 가져가며 효율적으로 정책 성능을 유지할 수 있다. 또한 PEARL에서는 Off-policy 강화학습 알고리즘으로 Soft Actor-Critic[11]을 선택했다. Soft Actor-Critic은 강화학습 알고리즘 중 좋은 샘플 효율성을 보이며 엔트로피 개념을 활용해 알고리즘에 내포된 확률적 모델링 요소들은 PEARL의 인코더 학습 시 사용되는 확률적 잠재 컨텍스트와 잘 통합될 수 있다.

그림 4는 제안 모델의 학습 방법을 그림으로 나타낸 것이다. 제안 모델의 학습 방법은 먼저 인코더 q_Φ(zvertcⁱ)에서 컨텍스트 변수인 z를 샘플링한다. 샘플링한 컨텍스트 변수 z를 통해 Actor network인 π_θ(averts, z)에서 액션인 a를 샘플링하고 생성된 데이터인 (s,a,r,s')을 리플레이 버퍼 Bⁱ에 저장한다. 이후 리플레이 버퍼 Bⁱ에서 저장된 데이터인 (s,a,r,s')을 샘플링하여 컨텍스트 변수 cⁱ를 업데이트한다. 앞서 소개한 새로운 샘플러 S_c를 통해 인코더 q_Φ(zvertcⁱ)를 업데이트하기 위해 컨텍스트 변수 cⁱ를 샘플링한다. 그리고 Soft Actor-Critic agent을 업데이트하기 위해 리플레이 버퍼 Bⁱ에서 RL batch bⁱ를 샘플링한다. 그다음 인코더 q_Φ(zvertcⁱ)에서 컨텍스트 변수 z를 샘플링한 다음 샘플링한 컨텍스트 변수 z와 RL batch bⁱ를 이용하여 Actor network의 손실함수인 Lactori와 Critic Network의 손실함수인 Lcritici을 계산한다. 이후 앞서 소개한 변분적 추론으로 얻은 전체 목적 함수의 정규화 항인 βDKLqΦzvertcirz을 계산하여 정규화 손실함수인 LKLi을 계산한다. 이후 Critic Network의 손실함수 Lcritici와 정규화 손실함수 LKLi을 이용하여 인코더 parameter Φ를 업데이트하고 Actor 손실함수 Lactori을 이용해 Actor parameter θ_π를 업데이트하고 Critic 손실함수 Lcritici을 이용해 Critic parameter θ_Q를 업데이트한다.

Fig. 4. 
How to train a suggestion model

일반적인 강화학습에서는 누적 보상 또는 평균 보상에 따라 학습 정도를 파악한다. 그러나 본 논문에서는 태스크마다 목적지의 개수가 달라 얻을 수 있는 보상이 다르므로 누적 보상에 따라 성능을 평가하는 것은 적절하지 않다. 이에 본 논문에서는 각 태스크에서 만든 멀티캐스트 라우팅 트리 링크의 수를 활용하여 성능 평가 지표로 이용하였다.

출발 노드와 목적 노드의 집합이 모두 연결되기 위해서는 목적 노드의 집합 원소 수만큼 링크의 개수가 필요하다. 따라서 필요한 최소 링크 개수는 목적지 집합 원소의 개수와 같다. 그다음 만들어진 멀티캐스트 라우팅 트리 링크의 개수에 최소 필요 노드 개수를 나누어 식 (7)과 같이 성능 평가 지표인 Performance Ratio를 정의한다. 식 (7)의 Performance Ratio는 1에 가까우면 가까울수록 최적의 멀티캐스트 라우팅 트리에 가까워진다고 볼 수 있다.

다음 실험은 가변적인 네트워크 환경을 고려하기 위해 네트워크 노드 개수가 10개인 환경에서 링크 분포를 변화해가며 iteration에 따른 Performance Ratio의 변화를 기록한 그래프이다. 실험은 링크 분포가 random일 때, 링크 분포가 30%일 때, 링크 분포가 50%일 때, 링크 분포가 70%일 때로 총 4회 진행하였다.

그림 5는 네트워크 노드 개수가 10개일 때 iteration이 지남에 따라 Performance Ratio를 기록한 그래프이다. 약 200 iteration 이후 대략 1.2 정도의 값에 수렴함을 보인다.

Fig. 5. 
Performance Ratio when link distribution is random

그림 6은 링크 분포가 30%일 때의 Performance Ratio이다. 약 300 iteration 이후 대략 1.5 정도의 값에 근접함을 알 수 있다.

Fig. 6. 
Performance Ratio when link distribution is 30%

그림 7은 링크 분포가 50% 일 때의 Performance Ratio이다. 약 300 iteration 이후 대략 1.2 정도의 값에 근접함을 알 수 있다.

Fig. 7. 
Performance Ratio when link distribution is 50%

그림 8은 링크 분포가 70%일 때의 Performance Ratio이다. 약 250 iteration 이후 대략 1.08 정도의 값에 근접함을 알 수 있다.

Fig. 8. 
Performance Ratio when link distribution is 70%

그림 6, 그림 7, 그림 8의 실험 결과를 보면 링크 분포가 30% 일 때보다 링크 분포가 70%일 때 성능이 더 좋음을 알 수 있다. 이를 통해 링크 분포가 적을 경우 학습이 링크 분포가 많을 경우에 비해 어려움을 알 수 있다. 그 이유로는 링크 분포가 많을수록 탐색 공간과 경로가 많아 최적인 멀티캐스트 라우팅 트리를 만들 확률이 높고 어떤 방향으로 가든 최적에 가까울 확률이 높기 때문이다.

다음은 기존 근사 알고리즘[12]과의 비교이다. 표 2는 본 논문에서 제시한 성능 평가 지표인 Performance Ratio에 따라 기존 근사 알고리즘과 본 논문 간의 성능을 분석한 표이다. 위 표에서 보이는 것처럼 기존 근사 알고리즘보다 본 논문에서 제시한 모델의 성능이 뛰어남을 알 수 있다.